基于谓词的系统需求测试用例生成方法研究

刘珊艳

(荆楚理工学院 计算机工程学院,湖北 荆门 448000)

基于谓词的系统需求测试用例生成方法研究

刘珊艳

(荆楚理工学院 计算机工程学院,湖北 荆门 448000)

软件测试是保证软件可靠性的主要方法,为了提高测试的质量可以在需求分析阶段对测试对象进行分析，根据需求分析规则产生的谓词常常可以用于软件检测。讨论基于谓词的测试准则BOR和BRO，并使用该准则检测需求规则中所有的布尔运算符故障和关系运算符故障。结果表明，根据谓词信息生成的测试用例集合是最小的，且每个测试用例都能从不同方面暴露各种运算符故障，从而可以对软件需求规则进行充分地测试，提高软件设计的准确性。

软件测试；谓词；测试用例生成；测试充分性

随着软件系统规模和复杂性的增加，软件测试的任务也变得越来越复杂与繁重。为了减少测试过程的盲目性，提高测试效率，在需求分析的开始阶段就对测试任务进行明确的分析，对测试目标进行有效的组织，同时准确地记录测试结果尤为重要。正如需求分析是软件系统设计与实现的基础，软件测试也应该以准确而详尽的测试需求分析为基础[1]。

基于谓词的测试可以在早期软件需求完成后就进行需求正确性的验证。在软件的需求文档中会存在软件设计所需遵守规则的说明，这些规则可以成为测试集设计的依据。编程人员可能对这些规则进行正确的编码，也可能没有正确编码，导致程序中存在缺陷。根据谓词产生的测试用例，可以确保在测试中发现某种类型的所有缺陷，同时由于基于谓词的软件测试的关键问题是如何产生与选择高效的测试用例集，即生成与选择的测试用例集中测试用例的数量尽可能少，可以检测尽可能多的故障类型[2]。为此，可以使用面向谓词的测试用例生成准则，从不同角度考虑设计出存在差异的测试用例，从而提高软件的质量。

1 谓词

谓词就是需求规则形式化的表示。例如，考虑软件需求“若打印机处于ON状态且具备打印纸，则发送要打印的文件”，这句话包含一个条件和一个动作。下面的谓词，记为P表示这句话的条件部分。

P:(printerstatus=ON)∧(printertray!= empty)

一个条件可以表示成简单谓词或复合谓词。简单谓词就是一个布尔变量或关系表达式(关系表达式通过集合{<,>,≤,≥,=,≠}中的一个关系运算符连接)，其中各变量可以取非(！)。复合谓词可以是一个简单谓词，或是由若干简单谓词通过二元布尔运算符(∧,∨)连接起来的一个表达式。

2 谓词约束

定义对整个谓词的约束，该谓词由布尔变量、关系表达式通过布尔运算符连接而成。对于测试用例t，如果Pr的各组件都满足约束C中相应的约束，称测试用例t满足Pr上的约束C。谓词上的约束C可有效指导测试集的设计，为Pr中变量的取值提供了清晰的线索。约束条件还被用来动态地、启发式地产生测试用例。

给定谓词Pr的约束C，任意满足C的测试用例将使Pr取值为true或false。用Pr(C)表示Pr对所有满足约束C的测试用例的取值。将使得Pr(C)=true的约束C称为“真”约束，而将使得Pr(C)=false的约束C称为“假”约束。这样，就将约束集合S划分为2个子集St和Sf,有S=St∪Sf。其中，对于任意C∈St,有Pr(C)=true；对于C∈Sf，有Pr(C)=false。

3 生成充分性测试用例

我们最关心的是如何从给定的谓词Pr生成测试集T，使其满足：①T是最小集合；②T保证能够检测出Pr实现中存在的所有布尔运算符故障和关系运算符故障。为了获取这样的测试集，定义2个检测布尔运算符的准则，通常称为BOR、BRO测试准则[3-5]，名称BOR、BRO分别对应于布尔运算符、布尔关系运算符，2个准则的形式化定义如下：

1)对于复合谓词Pr，如果测试集T确保能够检测出Pr实现中存在的所有单/多布尔运算符故障，则T满足BOR测试准则，称T为BOR充分测试集，记为TBOR。

2)对于复合谓词Pr，如果测试集T确保能够检测出Pr实现中存在的所有单/多布尔运算符故障关系运算符故障，则T满足BRO测试准则，称T为BRO充分测试集，记为TBRO。

设Tx为从谓词Pr导出的测试集，其中x∈{BOR,BRO}。设Pf为通过向谓词Pr注入单/多故障而得到的另一谓词，注入的故障属于布尔运算符故障、关系运算符故障。若存在t∈Tx，使得Pr(t)≠Pf(t)，则称Tx确保能够检测出Pf中的故障。

首先，给出关于笛卡儿积的2个定义描述。

有限集合A和B的笛卡儿积记为A×B，定义如下:A×B={(a,b)|a∈A and b∈B}。

为了能生成最小的测试约束集，还需要另一种集合积的计算方法。集合的onto积(其运算符号记为⊗)定义如下：对于有限集合A和B，A⊗B为二元偶(u,v)构成的最小集合，其中u∈A、v∈B，且A中的各个元素至少出现一次，B中的各个元素也至少出现一次。根据该定义，当集合A、B包含2个或2个以上元素时，A⊗B的计算结果不是唯一的。

A⊗B={(u,v)|u∈A, v∈B, u 至少出现一次，v至少出现一次。}

下面给出检测布尔运算符故障和关系运算符故障测试用例集的生成算法。

3.1生成BOR约束集

图1 谓词Pr的抽象语法树

下面的算法用于生成BOR的约束集(CSET)。

由谓词Pr的抽象语法树生成最小BOR约束集的算法BOR-CSET。

输入：谓词Pr的抽象语法树AST(Pr)。Pr只包含奇异表达式。

输出：谓词Pr的BOR约束集，放置在抽象语法树AST(Pr)的根结点处。

算法开始:

步骤2:以自底向上的方式遍历AST(Pr)的每个非叶结点(内部结点)。如果结点N是一个and结点或or结点，设N1,N2是其直接后继。如果结点N是一个not结点，设N1是其直接后继。SN1,SN2分别代表结点N1,N2的BOR约束集。对每个非叶结点N，计算SN如下：

1)N是or结点：

2)N是and结点：

3)N是not结点：

步骤3:AST(Pr)根结点的BOR约束集就是谓词Pr的BOR约束集。

算法结束。

使用燃气报警器这种对安全性要求较高的系统得到的需求说明进行测试。燃气报警器是一种气体泄露检测报警仪器。当工业环境或家庭生活环境中燃气气体泄露，燃气报警器检测到气体浓度达到爆炸或中毒报警器设置的临界点时，燃气报警器就会发出报警信号，以提醒工作人员采取安全措施。燃气报警器系统是一种典型的实时系统，该系统为了保证安全性，不仅要求所产生的结果在逻辑上是正确的，而且要求执行时间必须满足规定的时间约束，任何动作出现时间上的延迟都会造成灾难性的后果。开发这类系统的成本较高，如果能够在系统开发过程中越早发现问题，就可以避免很多人力物力资源的浪费[6]。我们在需求分析阶段定义燃气报警器安全条件的需求规则为：报警器在一个时间周期pertime内探测空气中燃气的浓度，若探测的值不高于标准值stdvalue，可以判定为安全，用谓词Pr来表示安全条件，上述的燃气报警器安全条件需求规则可以用谓词Pr：gas

现在生成安全条件谓词Pr的BOR约束集。

输入：谓词Pr的抽象语法树AST(Pr)。

输出：谓词Pr的约束集，放置在抽象语法树AST(Pr)的根结点。

首先根据各叶点的类型标识其约束集如下：

然后自底向上，广度优先遍历AST(Pr)，从其直接后继结点的约束集计算各非叶结点的约束集。

SN3={(t,t),(f,t)(t,f)}。

得到谓词Pr的BOR约束集如图2所示(约束集放置在谓词抽象语法树的根结点旁)：

图2 谓词Pr的BOR约束集

根据图2中谓词Pr的BOR约束集，设计满足以上3个BOR约束的测试集T1：

T1={t1∶,满足(t,t)；t2∶，满足(f,t)；t3∶,满足(t,f)}。

说明：对于测试集T1中gas=stdvalue±1及time=pertime±1是指标准值加上或者减去一个很小的值，不代表具体的数。

由于T1满足BOR测试准则，从而确保能够检测出Pr中存在的所有单/多布尔运算符故障。通过针对测试集T1，计算Pr及其注入布尔运算符故障后得到的变体的真值，就能验证这一点。

谓词 Pr以及经注入单/多布尔运算符故障后得到的7个故障谓词见表1。对于每个谓词，都使用T1中的3个测试用例分别进行计算。

表1 燃气报警器安全条件的谓词BOR充分测试集对单/多布尔运算符故障的检测能力

注：故障谓词与安全条件谓词的计算结果的差异用斜体加粗标识。

1)验证测试集合T1最小。

删去测试用例t1，对于故障谓词6剩余的测试用例t2、t3其执行结果与正确谓词Pr的预期结果相同，无法暴露错误。

删去测试用例t2，对于故障谓词5剩余的测试用例t1、t3其执行结果与正确谓词Pr的预期结果相同，无法暴露错误。

删去测试用例t3，对于故障谓词4剩余的测试用例t1、t2其执行结果与正确谓词Pr的预期结果相同，无法暴露错误。

综上所述，如果从表中删去任意一个测试用例，则至少存在一个故障谓词对于剩余的2个测试用例，其真值与谓词Pr的真值相同，故测试集合T1是最小的。

2)验证测试集合T1能检测出谓词中所有布尔运算符故障。

从表1中可以得到，对于7种单/多布尔运算符故障，至少存在1个测试用例，能够使其真值与正确谓词Pr不同。

例如故障谓词1，测试用例t2、t3均可发现错误。分别执行测试用例t2、t3，预期结果分别是false、false，而实际的执行结果却是true、true，测试执行结果与预期结果不同，暴露错误。

例如故障谓词4，测试用例t3可发现错误。执行测试用例t3，预期结果是false，而实际的执行结果却是true，测试执行结果与预期结果不同，暴露错误。

因此，可以肯定，测试集T1最小且满足BOR的充分性。

3.2生成BRO约束集

对于关系运算符连接的表达式e1 rel e2的BRO约束集S={(>),(=),(<)}。如下所述，根据rel的不同，S的“真”约束集、“假”约束集的划分结果也不一样：

rel为>∶St={(>)}，Sf={(=),(<)}；

rel为≥∶St={(>),(=)}，Sf={(<)};

rel为=∶St={{=}},Sf={(<),(>)}；

rel为<∶St={(<)}，Sf={(=),(>)};

rel为≤∶St={(<),(=)},Sf={(>)}。

现在，修改前面介绍的用于生成谓词BOR约束集的算法BOR-CSET，以生成最小BRO约束集。修改后的算法如下：

输入：谓词Pr的抽象语法树AST(Pr)。Pr只包含奇异表达式。

输出：谓词Pr的BRO约束集，放置在抽象语法树AST(Pr)的根结点处。

算法开始：

步骤2:以自底向上的方式遍历AST(Pr)的每个非叶结点(内部结点)。如果结点N是一个and结点或or结点，设N1,N2是其直接后继。如果结点N是一个not结点，设N1是其直接后继。SN1,SN2分别代表结点N1、N2的BRO约束集。对每个非叶结点N，计算SN如下：

1)N是or结点：

2)N是and结点：

3)N是not结点

步骤3:AST(Pr)根结点的BOR约束集就是谓词Pr的BOR约束集。

算法结束。

对于燃气报警器安全情况下的谓词Pr：gas

首先根据各叶点的类型标识其BRO约束集如下：

然后自底向上，广度优先遍历AST(pr)，从其直接后继结点的BRO约束集计算各非叶结点的BRO约束集如下：

={(<)}⊗{(<),(=)}

={(<,<),(<,=)}；

=({(>),(=)}×{(<)})∪({(<)}×{(>)})

={(>,<),(=,<),(<,>)}；

SN3={(<,<),(<,=),(>,<),(=,<),(<,>)}。

得到谓词Pr的BOR约束集如图3所示(约束集放置在谓词抽象语法树的根结点旁)。

图3 谓词Pr的BRO约束集

根据得到谓词Pr的BRO约束集，设计满足以上5个BRO约束的测试集T2：

T2={t1∶，满足(<,<)；t2∶,满足(<,=)；t3∶，满足(>,<)；t4∶,满足(=,<);t5∶,满足(<,>)}。 T2集合中的t1，t3，t5与T1中的t1，t3，t2的测试用例完全相同，故测试集T2⊃T1。由于T1满足BOR测试准则，能够检测出Pr中存在的所有单/多布尔运算符故障，所以针对测试集T2，可以省略计算Pr及其注入布尔运算符故障后得到的变体的真值，只需计算关系运算符故障和组合故障来验证测试集对BRO测试准则的充分性。

谓词Pr以及经注入单/多关系运算符故障后得到的10个故障谓词见表2。对于每个谓词，都使用T2中的5个测试用例分别进行计算。

表2 燃气报警器安全条件的谓词BRO充分测试集对单/多关系运算符故障的检测能力

注：故障谓词与安全条件谓词的计算结果的差异用斜体加粗标识。

验证测试集合T1能检测出谓词中所有布尔运算符故障。

从表2中可以得到，对于10个故障谓词，至少存在一个测试用例，使其执行结果与正确谓词Pr的执行结果不同。

例如故障谓词1，测试用例t1，t2，t3均可发现错误。分别执行测试用例t1，t2，t3，预期结果分别是true，ture，false，而实际的执行结果却是false，false，true，测试执行结果与预期结果不同，暴露错误。

例如故障谓词8，测试用例t5可发现错误。执行测试用例t5，预期结果是false，而实际的执行结果却是true，测试执行结果与预期结果不同，暴露错误。

因此，可以肯定，测试集T2针对BRO测试准则是充分的。

4 总结

本文讨论使用谓词对软件的需求规则进行测试的方法，并根据该方法生成充分的测试用例集。为说明该方法的有效性，使用该方法对燃气报警器这种安全性要求较高的系统需求进行测试。定义燃气报警器系统需求安全条件的谓词，生成该谓词的BOR充分测试集及BRO充分测试集，并验证安全条件谓词的BOR测试集是充分检测出所有布尔运算符故障的最小集合，也验证了安全条件谓词的BRO测试集合的充分性。基于谓词的测试方法在提高测试效率的同时，保证了测试的充分性，是一种进行软件测试的有效方法。

[1] 杨波,吴际,徐珞,等.一种软件测试需求建模及测试用例生成方法[J].计算机学报,2014,37(3):522-538.

[2] 孙昌爱,程庆顺.基于故障的布尔表达式测试技术综述[J].计算机科学,2013,40(3):16-23.

[3] Burnim J,Sen K.Heuristics for scalable dynamic test generation[C].IEEE/ACM Internation Conference on Automated Software Engineering,2008:443-446.

[4] Tai KC.Predicate-based test generation for computer programs[C].International Conference on Software Engineering,2002:267-276.

[5] Ball T.A Theory of Predicate-Complete Test Coverage and Generation[C].International Conference on Formal Methods for Components and Objects,2004:1-22.

[6] 刘珊艳.基于UPPAAL的燃气报器的建模与验证[J].荆楚理工学院学报,2015,30(4):16-21.

(责任编辑高嵩)

Generating Test Case for System Requirement Based on Predicate

LiuShanyan

(Department of Computer Engineering,Jingchu University of Technology,Jingmen Hubei 448000)

For the sake of improving the test quality,Software testing,a main method of guaranteeing the software reliability,can be carried out in the stage of software analysis.Predicates,generated on the basis of the rules of the analysis,tend to be applicable to the testing.The paper,on the one hand,probes into BOR and BRO based on the predicate test criteria,on the other hand it exploits the criteria in the detection of all the malfunctions of the Boolean operators and the relational operators in the rules of analysis.The results indicate that the aggregate of the test case generated by the predicate information is minimal,and that each test case tends to expose the various faults of operators from different aspects.Thus,the paper suggests that the analysis rule can be tested fully for the purpose of raising the accuracy of the software design.

software testing;predicate;test case generation;test adequacy

2017-03-22

荆楚理工学院校级科学研究项目(项目编号：ZR201311)。

刘珊艳，讲师，硕士。

10.3969/j.issn.2095-4565.2017.04.008

TP312

：A

：2095-4565(2017)04-0039-06