0 引言

随着软件系统的广泛应用,软件质量日益得到人们的重视,特别是在安全关键软件领域,软件失效可能会造成难以估量的损失,因此,对于软件质量的要求需要更加严格。软件测试作为保证软件质量的有效手段,得到了越来越多的研究。软件测试通过设计和执行测试用例来判断被测系统的实际行为和预期行为是否一致,从而检测软件内部缺陷。

近几年,基于模型的测试技术越来越受到关注。模型是对软件行为和软件结构的描述^[1],软件生命周期中,模型可以被使用在软件生命周期的多个方面,其中包括软件设计、质量规范、代码生成、可靠性分析和测试用例生成等^[2]。基于模型的软件测试是指利用系统的需求和形式化模型来自动产生有效测试用例的测试。基于模型的测试的特点是:在产生测试用例和进行测试结果评价时,都是根据被测试应用的模型及其派生模型进行的^[3]。软件测试中使用的典型模型分别有:有限状态机(Finite-State Machine,FSM)模型^[4]、统一建模语言(Unified Modeling Language,UML)模型^[5]和Markov链^[6]等模型。

Markov链是以统计理论为基础的统计模型,是一种迁移具有概率特征的有限状态机,可以根据状态间迁移概率自动生成测试用例,对软件性能指标和可靠性指标进行度量。Markov链模型最大的优点在于可以使用Markov理论来分析使用模型,是目前研究和使用得较为广泛和相对成熟的模型表达方式。在净室软件工程中,软件Markov链模型主要根据软件的相关技术文档生成,通过提取软件运行中的激励、响应以及之间的交互关系来确定使用模型的状态与迁移,迁移概率可通过对早期版本使用情况进行分析等方式得到。基于Markov链模型的软件测试不要求了解软件内部结构,属于黑盒测试方法。

现有基于模型的软件测试技术中的典型模型只是描述了软件的功能与行为,不存在一个统一的模型描述软件的功能行为与代码结构信息。测试或者是在软件系统测试层面进行,使得测试数据生成的复杂性较高;或者是在单元测试层面进行,未利用软件的使用信息。由于软件的复杂性,尤其是安全关键的工业控制软件,一些错误只有在一定的运行环境下执行某些路径时才会暴露出来,并造成严重的系统失效^[7],因此,在软件测试中考虑功能与结构信息对提高软件质量至关重要。

统计测试是一种基于某种概率分布选取测试数据的测试方法^[8]。当概率分布是根据程序的结构或代码确定时,称为统计结构测试。统计结构测试以发现更多缺陷为目标^[8],依据输入的概率分布来生成测试数据,该概率分布必须满足根据被测软件内部结构所定义的充分性准则,如语句覆盖、条件覆盖^[9]等。Poulding等^[10]在统计结构测试中引入了启发式算法,实现了概率分布的自动生成,并提高了测试数据的失效发现能力。

为解决基于模型的软件测试方法无法考虑到软件结构的问题,本文提出了一种新的软件测试模型——软件层次化模型(Software Hierarchical Testing Model,SHTM),该模型包含了软件使用模型与输入数据分布模型两个层次,涵盖了软件的使用信息和结构信息。

1 软件层次化模型 1.1 相关概念

软件层次化模型(SHTM)包含两个层次：软件使用模型与输入数据分布模型。其中：软件使用模型与软件的功能和行为对应满足Markov链的统计特性；输入数据分布模型则与软件的代码结构关联。

如图 1所示，由软件规格说明以及UML模型等开发文档生成软件使用模型，该模型描述了软件与外部环境交互导致的状态变化过程；由软件的内部实现生成软件的输入数据分布模型，该模型描述了代码执行路径所对应的输入数据范围，是使用模型中的迁移在软件实现层次上的细化。通过分层次建模方法得到测试模型，使测试模型涵盖了软件的使用信息和结构信息，同时符合软件开发中由分析逐步到设计的过程。

软件运行过程中，不断与外部环境进行交互，以及执行内部的业务逻辑，本文定义软件中与外部环境之间直接交互的方法为外部方法，软件内部组件之间交互的方法为内部方法。外部方法直接和外部激励以及软件响应相关，负责对从外部获取到的输入数据进行处理，以及输出外部环境要求的数据。内部方法代表着软件内部的处理逻辑。每个外部方法执行过程中或两个外部方法执行之间，可能存在着多个内部方法的执行。即内部方法有可能被某些外部方法调用，也有可能和某些外部方法并列顺序执行。

软件状态指软件内部数据在执行过程中出现的相对稳定的状态，等待着接受外部激励。状态表示了程序在执行中的某个确定时刻的一些信息，一般来说，状态可以用软件中一些变量的赋值集合来表示，这些变量所有可能的取值组成了软件的状态空间。迁移是状态之间的转换，指外部环境对软件产生激励，软件内部执行相关代码并对外部产生响应的过程，对应着外部方法的执行。

软件和外部环境进行交互时接收到的输入导致软件状态发生变化。软件接收到输入，执行相关代码，导致内部变量的数值发生变化，软件状态就会发生变化。在软件从一个状态到另一个状态迁移的过程中，执行了一系列代码语句，这一系列的代码语句构成了一条代码路径。从状态开始迁移的第一个外部方法开始，到迁移的最后一个外部方法结束，一条迁移所对应的路径可能涵盖了多个方法调用。因此在状态迁移的过程中，可能会存在多条可执行路径。

在软件测试中，要求软件与外部环境的交互要符合真实的使用情况，同时输入数据的选择也是一个重要问题：如何选定某些输入值，使这些输入值尽可能引发程序所有的缺陷，而提高路径的覆盖率有利于发现更多的缺陷。因此软件测试模型需要描述软件的使用情况和路径结构，本文的软件层次化模型以状态迁移描述软件的使用情况，同时将迁移的执行路径映射为参数的输入数据域和满足路径的逻辑约束条件。

1.2 模型定义

软件层次化模型定义为一个五元组(S，T，δ，q₀，f)，其中：

S是软件状态的集合。

δ是状态之间的转移关系S×T→S。

q₀是初始状态。

f是终止状态。

T是状态之间的迁移的集合，每个迁移t∈T是一个二元组(p_Transition，I_Iddm)。 p_Transition为迁移概率，特定状态所有出边的迁移概率之和为1。状态间的迁移满足Markov性，即下一个状态只与当前状态相关，不涉及历史信息。I_Iddm为对应的输入数据分布模型。

输入数据分布模型I_Iddm描述了软件的输入参数取值范围、需满足的逻辑约束条件以及其分布概率。输入数据的取值范围根据路径划分为不同的输入域，并为每个输入域赋予了一定的概率，代表了对应路径执行的可能性。基于输入数据分布模型的测试数据是在满足参数的输入域和逻辑条件的前提下生成的。

假设某迁移的路径有n条，输入参数有m个，则输入数据分布模型定义为一个n元组(D₁^CombVar，D₂^CombVar，…，D_n^CombVar)。

复合数据域D^CombVar表示变量输入数据域的组合，定义为(D_Var1，D_Var2，…，D_Varm，LogicConstraint，p_Path),其中：

变量输入数据域D_Var代表该变量的输入范围，定义为一个三元组(Name，Type，Interval)，Name表示参数名,Type表示参数类型,Interval表示参数输入域的分布区间。

LogicConstraint表示路径的逻辑约束条件，一条迁移所对应的路径可能涵盖了多个方法调用，故在状态迁移的过程中，可能会存在多条可执行路径，一条路径对应一个逻辑约束条件。

p_Path表示路径概率，模型中迁移对应的所有复合数据域的路径概率之和为1。

路径的逻辑约束条件LogicConstraint通过逻辑运算符将逻辑子条件连接起来，为程序解析方便，以析取范式表示。本文采用数学表达式的方式来描述逻辑约束。数学表达式由操作数和运算符构成，常见的运算符如算术运算符(+、-、*、/)，关系运算符(=、!=、>、＜、>=、＜=)，函数运算符(min(a,b)最小值、max(a,b)最大值等)，逻辑运算符(&&与、‖或、！非)。各逻辑子条件之间通过逻辑运算符连接，每个子条件内部通过关系运算符将左边的算术式和右边的常数连接起来。如以下程序所示：

class test{

void test(int a,b,c){

if((a+b-c>0) && (a+c-b>0) && (b+c-a>0) ){

System.out.print(“是三角形”)；

}

else if((a+b-c＜=0) ‖(a+c-b＜=0) ‖

(b+c-a＜=0) ){

System.out.print(“不是三角形”)；

}

}

}

其中：test是一个三角形判定的函数，要求输入正整数a、b、c，参数类型是int型。方法中存在两条路径，假设执行每条路径的概率相等，则分别赋予执行两条路径所对应的输入域的概率均为0.5。(0,2147483647]是参数输入域，2147483647代表int型参数的最大值，(a+b-c>0) && (a+c-b>0) && (b+c-a>0) 与(a+b-c＜=0) ‖(a+c-b＜=0) ‖(b+c-a＜=0) 分别是两条的逻辑约束条件。

迁移test的输入数据分布模型在程序中表示为：

迁移名：test

路径概率：0.5 0.5

参数名：a b c

参数类型：int int int

数据分布区间：

(0,2147483647) (0,2147483647)

(0,2147483647) (0,2147483647)

(0,2147483647) (0,2147483647)

逻辑约束条件：

(a+b-c>0) && (a+c-b>0) && (b+c-a>0)

(a+b-c＜=0) ‖(a+c-b＜=0) ‖(b+c-a＜=0)

2 软件层次化模型的构建

软件层次化模型的构建分为根据软件设计规格说明或UML模型构建使用模型层次，以及遍历使用模型的迁移构建输入数据分布模型层次两部分，流程如下：

1) 软件使用模型层次的构建：根据软件设计规格说明等相关开发文档手工构建，或者根据UML建模分析设计模型来自动生成；

2) 软件输入数据分布模型层次的生成：通过遍历软件的使用模型，针对每个迁移，首先生成其中方法的输入数据分布模型，然后集成得到迁移输入数据分布模型；

3) 层次化模型的有效性验证：检验迁移中的方法与软件实现的一致性，迁移中的方法在源代码中是否存在，状态的出边迁移概率之和是否为1，初始状态和终止状态是否唯一，迁移中方法的路径概率之和是否为1。

整个系统大体分为三个模块：主程序、软件使用模型层次生成和输入数据分布模型层次生成。三个模块协调工作，完成软件层次化模型构建的功能，图 2是系统的整体框架。

在软件层次化模型的具体实现过程中，采用UML建模工具提供的API访问UML模型信息，读取其中软件用例与对应的场景图，提供操作界面来定义场景执行后置条件与概率、用例执行顺序关系等内容，添加使用模型生成所需的信息，支持为UML模型加入测试约束，并根据扩展后的UML模型构造软件使用模型层次。

在生成输入数据分布模型的过程中，采用深度优先搜索算法遍历使用模型，针对每个迁移，首先获取其所对应的方法序列，根据方法名等信息找到其在代码中的实现，确定需要测试的路径集合，生成针对不同路径的参数输入数据域和逻辑约束条件，在获得逻辑约束条件时先进行初始化，把状态迁移中包含的表达式转化为仅包含变量和常量的表达式，得到方法的输入数据分布模型；然后集成方法输入数据分布模型，得到迁移输入数据分布模型，对所有迁移执行这个过程，直到结束使用模型的遍历。

统计结构测试属于单元测试的范畴，本文中针对迁移生成测试数据的过程与统计结构测试的思想类似，通过对代码分析获取与路径相关的输入域，建立输入数据分布模型，根据数据分布来生成测试输入数据。

3 基于软件层次化模型的测试数据生成

在基于软件层次化模型的测试数据生成过程中：一是要满足软件测试的统计要求，即测试需要符合软件实际使用情况；二是要提高测试数据的缺陷检测能力，即测试需要尽量提高代码路径的覆盖度。

软件层次化模型的使用模型层次描述了软件的使用情况。软件层次化模型的输入数据分布模型层次描述了软件输入数据与执行路径之间的映射。

在测试数据生成过程中，根据迁移边的迁移概率，从使用模型层次的初始状态到结束状态遍历使用模型层次的迁移边，得到的迁移序列即为测试序列，即软件与外部环境交互的方法序列，当程序执行迁移边时根据输入数据分布模型生成测试数据，即软件内部结构间交互的输入变量值，执行该迁移使软件进入下一状态，便完成了执行一次状态迁移时方法的输入变量的测试数据生成。

为了覆盖较多的测试路径，可将输入数据分布模型中每个复合输入域的概率设置相等，在生成测试序列中的输入参数时，依照输入数据分布模型中的参数输入域和逻辑约束条件求解来得到测试数据，每条路径的执行概率相等。

下面讨论如何根据层次化模型生成测试数据集合：

生成的测试数据集合需满足使用停止准则τ_Usage和结构覆盖要求τ_Structure，其中τ_Usage是指测试数据集需要满足使用模型的统计特性。根据生成的测试序列集，统计各状态下迁移的发生频率作为转移概率，可以构建一个Markov链，称为测试链，原使用模型所对应的Markov链为使用链。软件测试要求根据使用模型不断产生测试数据对软件进行测试，当测试链的相关数学特征达到覆盖准则要求时停止。一般以Discriminant值评估测试链接近使用链的程度，它是两个随机过程似然度的期望值，因此可以通过计算Discriminant值来进行测试充分性的判定。τ_Structure是指测试数据集需要满足的对输入数据分布模型的覆盖要求，指针对模型中迁移所对应的输入数据分布模型，使测试数据有同样的机会落在每个复合数据域中，即覆盖每条路径的概率尽可能相同，从而使测试数据尽可能覆盖所有的测试路径。以下是基于软件层次化模型生成测试数据的伪代码。

输入软件层次化模型。

输出测试数据集合。

BEGIN

WHILE 不满足使用停止准则τ_Usage

生成一条测试序列；

END WHILE

FOR EACH 测试序列集中的测试序列

执行软件，进入初始状态；

FOR EACH 测试序列中的迁移

判断迁移的输入数据分布模型中各输入数据域是否为空；

若空，则跳出该循环；

不空，则继续往下执行；

根据复合数据域生成测试数据；

以测试数据为输入，执行该迁移，软件进入下一状态；

END FOR

软件一次执行结束；

END FOR

END

图 3是基于软件层次化模型生成测试数据集合的流程。测试数据生成中，首先通过遍历使用模型层次生成测试序列，当测试链的Discriminant值不大于规定的阈值，即满足终止准则τ_Usage时停止；然后针对测试序列中的迁移集合，按照要求τ_Structure生成输入数据：对于方法输入域非空的迁移，首先从迁移的输入数据分布模型中选择一个复合数据域，然后依次为其中每个变量生成测试数据，逻辑约束条件描述了变量需要满足的约束，变量输入数据域定义了变量的取值区间，对变量的取值涉及到在取值区间内对逻辑约束的求解；生成完测试数据后，执行该迁移使软件进入下一状态，重复以上过程，为所有迁移生成输入数据。最后将所有的测试序列分别与对应的输入数据结合，即得到了测试所需的测试数据集合。

4 实验与分析

为了支持软件测试自动化，根据本文方法开发了基于软件层次化模型的测试数据生成工具。工具支持根据UML模型和软件代码来生成软件层次化模型，并根据层次化模型自动生成满足充分性准则的测试数据集合。工具主要分为两部分：层次化模型生成部分与测试数据生成部分。工具能够生成满足不同充分性准则的测试数据集合，包括最小边覆盖准则、欧几里得距离、Discriminant值。工具界面如图 4所示。

为了验证文中所提出方法的有效性，本文选取ATM和简单电话机模拟软件两个软件作为被测软件进行实验。

4.1 被测软件的层次化模型

图 5~6表示了ATM和简单电话机软件层次化模型的使用模型层次，其中每条迁移上标注了名称与迁移概率。

两个使用模型中的迁移存在几条可能的代码路径(实验结果对比表中用P₁，P₂，…，P_n表示)，不同的代码路径分别表示软件不同的运行状态，代码路径的概率相等。如ATM软件中的迁移TansferErr 存在三条路径，分别表示转账余额不足、转账金额超过上限、转账金额错误，概率均为1/3；简单电话机软件中的迁移DailUpErr存在两条路径，分别表示被叫忙音和呼叫错误，概率均为1/2。其中迁移TansferErr的输入数据分布模型如下文所示：

TransferErr

1/3 1/3 1/3

amount

int

(-1000,5000] (-1000,5000] (-1000,5000]

(balance-amount＜0)

(balance-amount>0) &&(amount+sum-10000>0)

(amount＜0)

其中：amount表示转账金额，balance表示账户余额，sum表示今日已转账金额。

4.2 测试数据生成

在基于Markov链模型的软件测试数据生成技术中，对测试序列中方法的参数赋值时采用随机方法，即根据变量值域的分布进行随机选择。分别采用基于软件层次化模型的测试数据生成技术与基于Markov链模型的测试数据生成技术为ATM和简单电话机软件生成测试数据集合，计算代码路径覆盖次数，以变异测试得到的变异分数作为对缺陷检测能力的度量指标，并评估两种测试数据生成技术的优劣。

变异测试经常被用来评估测试数据集的测试充分性。测试人员根据被测程序特征设计变异算子，变异算子一般在符合语法前提下仅对被测程序作微小改动，通过对被测软件应用变异算子得到变异体集合^[11]。使用测试数据集执行每个变异体，将被测试数据集杀死的变异体所占全部变异体的比例作为变异分数，以此评判测试数据集的缺陷检测能力^[12]。如果一个测试用例集合的变异分数达到100%，它被认为是变异测试完备的。本文要对比的两种测试数据集的不同主要在于路径覆盖的能力和输入数据的分布，因此采用选择性变异方式针对两个软件生成变异体集合，从变异算子集合中选择ABS(绝对值符号)、CRP(常量替代)、CSR(用常量替代变量)、ROR(关系运算符替代)、SCR(用变量替代常量)来生成变异体集合。最后通过比较各个变异算子生成的变异体集合的变异分数，来说明生成的测试数据对注入错误的敏感性。

在不同的Discriminant值约束下，分别采用两种方法生成测试数据集。dis代表Discriminant值，比较两种方法针对ATM软件中的迁移TransferErr、VerifyAccount和WithdrawErr和简单电话机软件中的DailUpErr和Talk的各条路径的测试数量，表 1~2表示了实验结果。图 7~8表示了利用变异测试检查数据集缺陷检测能力的实验结果，为了便于展示，横轴以-lg(dis)表示，纵轴代表变异分数。

表 1~2分别描述了在一定的使用分布概率下，两个软件的测试数据数量随Discriminant值的变化。从实验数据可以看出，在不同的用户使用情况下，随着Discriminant值的减小，测试数据的数量逐渐增加，即要使测试越接近软件的真实使用情况，所需的测试数据数量越多；在相同的Discriminant值下，基于软件层次化模型的方法对迁移中代码路径的覆盖率为100%，而基于Markov链模型的方法只能对迁移中部分代码路径的覆盖率做到100%，存在某些代码路径完全覆盖不到的情况，且由于其随机选择生成数据，各路径分配得到的测试量差异较大，会导致关键的小概率路径测试不充分。如表 1中ATM软件中的迁移VerifyAccount的代码路径P₂、简单电话机中的迁移DailUpErr的代码路径P₁以及迁移Talk中的代码路径P₂，由于该路径的输入参数为定值或位于极小分布区间，基于Markov链模型的方法生成的测试数据对这些代码路径的覆盖率近似为0。

由图 7~8可以看出，随着Discriminant值的减小，两个软件的测试数据集的变异分数逐渐增加。在相同的Discriminant值下，基于层次化模型的方法所生成的测试数据集的变异分数要高于基于Markov链使用模型的方法。随着两种方法的变异分数值趋于稳定，对于ATM软件，基于层次化模型方法的测试数据集变异分数接近于99%，而基于Markov链使用模型方法接近于75%；对于简单电话机软件，基于层次化模型方法的测试数据集变异分数接近于99%，而基于Markov链使用模型方法接近于72%。表 3展示了当-lg(dis)=5时，用两种方法对简单电话机软件生成的测试序列集合进行变异测试，五种变异算子生成的变异体集合的变异分数实验结果。

由实验结果可以发现，基于层次化模型的方法生成的测试数据集能基本全部检测出五种算子生成的缺陷，而基于Markov链模型的方法对各变异算子生成缺陷的检测率都较低，其中对ABS和ROR算子生成缺陷的检测率尤为低，其原因在于该方法生成的测试数据集对软件部分代码路径的覆盖率低甚至为0。

由变异测试的分析可以看出，在相同的充分性准则下，基于层次化模型的方法生成的测试数据集的缺陷检测能力要高于基于Markov链使用模型的方法；当测试数据集满足一定的充分性准则时，基于层次化模型的方法能检测出软件中存在的绝大多数错误。

基于软件层次化模型的测试数据生成方法与基于Markov链使用模型的方法相比，在满足软件测试的统计特性要求下，能够得到对被测软件的缺陷检测能力更高的测试数据集合，在测试资源一定的情况下，有助于提高软件的可靠性水平，改进软件的质量。

5 结语

本文在软件测试中考虑软件内部结构信息，将基于Markov链模型的测试与白盒测试相结合，提出了软件层次化模型的概念，并给出基于该模型的软件测试数据生成算法。通过对ATM和简单电话机模拟软件进行实验，结果表明相对于基于Markov链模型的方法，层次化模型方法在生成测试数据时对代码路径的覆盖率更高，生成的测试数据集有更高的缺陷检测能力，能够有效检测软件存在的缺陷，进而提高软件可靠性水平。

对安全关键软件进行测试，还需利用加速测试方法对关键操作充分测试^[13]。其主要利用重要抽样技术，在保证软件可靠性估计为无偏估计的前提下，通过修正操作剖面来控制估计的方差，提高估计的准确性^[14]。如何加速软件测试，在有限的测试资源条件下增强软件的可靠性还需要深入研究。

另外在层次化模型中，为迁移的路径赋予相同的执行概率，而在实际中有些路径可能由于关键程度的不同而需要不同的测试量，以更有效地利用测试资源，因此复合输入域的概率分配策略还有待进一步研究。