基于约束条件的组合测试用例集构建方法分析

丁怀宝+龚蓬+高凤+周飞

摘要：该文充分深入地利用了待测系统中的约束条件，并在组合测试用例集中筛选出最优的测试用例。欲采取的方法是先将约束条件转化为布尔表达式，再将布尔表达式转化为合取范式，然后运用AETG--SAT算法，并通过实验表明了AETG--SAT算法的优越性。在该过程中，此翻译方法和调用工具的方式是较为可行的研究，值得深入学习。

关键词：组合测试用例；约束条件；布尔表达式；合取范式

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）11-0001-02

近些年人们对组合测试技术的深入研究和探讨，组合测试用例集的生成技术可以理解为：如何在满足覆盖所有输入参数的前提下，以节约成本为目标，生成规模尽可能小的测试用例集，一直是组合测试研究领域的重点内容之一。

1 对组合测试的理解

组合测试是用来检测带有覆盖数组的测试用例集，这些测试用例集能够覆盖待测系统中的所有参数值。组合测试的优点就是能够发现测试用例集中各参数之间的相互制约而导致测试失败。因此，对待测系统中的参数和各参数之间所产生的影响进行全面的考虑，是组合测试方法对软件故障有较强的判断和检测能力。

1）用形式化来表述

若在系统待测软件中设有变量m个，在第i个值可能取值有Ni个可能性。Wi代表第i个变量的某个取值，t=（W0，W1，...，Wm-1）， 所有可能出现的测试用例集由T代表，则t包含T，S表示某个并属于T。

所有参数在通常情况下都要进行组合测试，如果，参数的个数m和取值个数为N时，用例集将会发生大的增加。

2）约束条件的应用

我们通过图表来展示，以下为某系统在软件测试过程中的情况，观察测试用例，可预想到，如果是大型的软件系统是不切实际的。

表1 软件测试用例组件

[可能值＼&参数＼&M＼&N＼&O＼&P＼&Q＼&M1＼&N1＼&O1＼&P1＼&Q1＼&M2＼&N2＼&O2＼&P2＼&Q2＼&M3＼&N3＼&O3＼&＼&＼&约束

条件＼&1、（M3， N1）2、（M3， O1）3、（M2， O1）4、（N1， O3）5、（O3， P1）（M3， P1）6、（P2， Q1）7、（M1，N2， O1）＼&]

表1中，括号内的几个参数不能在系统的测试用例的过程中同时出现。如，（M3， N1）表示一个测试用例中不能同时出现，经过约束之后，测试用例个数大大减少，说明约束条件很大程度上优化了组合测试方法。约束出现的情况非常复杂。比如说，因为硬件条件的不统一，内存大小、软件情况以及营销方面的不同。

2 布尔的可满足性理解

1）对SAT问题的理解

布尔可满足性问题即“SAT问题”，是目前计算机科学技术、人工智能研究的重要的、核心内容，在逻辑学领域中有较高的地位。

概念：通过对存在的变量进行赋值，来决定命题公式是否成立。即，对变量进行真值赋值后，经化简归约束等技术，最后得到的命题公式的值是否为真，称为可满足性问题。

2）对合取范式的理解

概念：通过对少量的简单的析取式所合成的合取式，我们把它称为合取范式。

如果设A（i=l，2，…，y）为简单的、有限的析取式，则A=A∧A1∧A2∧…∧Ay称为：合取范式。当所有的赋值为真值的合取范式所包含的所有子句都满足性求解，通常都是合取范式的范围。

3 约束条件组合测试用例集的生成

1）生成算法优化组合测试用例集

本文为了缩小覆盖的矩阵，采用将AETG算法和SAT方法结合。

2）AETG、AETG—SAT两种算法的分析

AETG算法：通过给定的测试用例，运用贪心算法将软件测试中的一个能覆盖最多未被覆盖的多维组合测试用例，循环迭代……直至所有的多维组合都被覆盖的计算过程。

AETG--SAT算法：将待测软件中约束条件转化为合取范式，然后利用相关的SAT求解器精简测试用例，最后设计AETG-SAT算法来得出较优的约束组合测试用例集，如下所示：

具体算法如下（在原基础上加入了约束条件，进行了3处修改）：

（1）一致性检测，使得部分约束行受扩充部分行的满足。

（2）约束条件在参数组合中必须存在，并且对涉及的条件要近一步检测。

（3）如果一次性检测失败将结束检测，不必对参数值进行约束并进行二次检测。

算法设计过程：

初始化环节：

未被覆盖的多维组合个数=M；案例测试候选的个数=100、案例测试个数=n；案例测试总数=Q。

程序环节：

While M>=0 do

For n=1 t0 100 do

生成空测试案例的个数是0

While 布尔可满足性问题不存在

将显示X。

它是安全测试中的第一出现的值，也从中出现最多的值。

若布尔可满足性=参数值X的参数S取反∨测试案例进行一次测试匹配；

所剩的参数将自动排序，形成新的集合Q；

For M属于Q do

一次测试匹配次数从l到X；

While 可满足性不存在，同时测试匹配<=X；

显示y；

若布尔可满足性=参数S的值取反X案例测试相匹配；

次数+1、第2个参数就是测试案例的值；

案例测试的总数会增加，并做为候选案例，将会选择最佳的案例候选做测试，来更新未覆盖的。

测试案例个数+1：

End while；

End while；

End while；

3）通过两种算法生成配对组合测试用例集的比较分析

提取不同大小的样本系统，通过两种算法得出测试用例集个数，并详细说明和分析了生成环节。如表2所示。

通过对比，这两种算法都得到了最优化的测试用例集。但后者比前者更精简，当参数的指数在不断增大时，变化就会越明显，这说明AETG-SAT算法节约了软件测试成本，大大提高了测试效率。

表2 两种算法的比较分析

[算法分类＼&S0＼&S1＼&S2＼&S3＼&S4＼&S5＼&S6＼&S7＼&S8＼&AETG＼&11＼&9＼&17＼&15＼&29＼&21＼&59＼&48＼&26＼&AETG-SAT＼&10＼&9＼&15＼&1＼&23＼&17＼&47＼&38＼&15＼&备注

说明：＼&S0：6个4值参数，8个约束条件；

S1：6个参数，4个4值参数，3个3值参数，8个约束条件；

S2：25个4值参数，6个约束条件；

S3：25个参数，12个4值参数，9个3值参数，6个约束条件；

S4：44个4值参数，24个约束条件；

S5：46个参数，5个5值参数，17个4值参数，26个3值参数；24个约束条件；

S6：80个5值参数，38个约束条件；

S7：90个参数，45个4值参数，25个3值参数，9个2值参数：40个约束条件；

S8：100个2值参数，50个约束条件；＼&]

4 结束语

本文对含有约束条件的待测系统通过添加对约束条件的转换及提出新的算法进行处理的生成环节，去除不满足约束条件的测试用例，大大缩小了组合测试用例集的数量，同时，在保证测试质量的前提条件下，大大节约了测试的成本。最后通过实验得出AETG-SAT算法是一个较优的用于组合测试用例的算法。

参考文献：

[1] 胡岳峰，高建华.两两组合覆盖测试用例生成研究及优化[D].上海：上海师范大学，2008.

[2] 王子元，徐宝文，聂长海.组合测试用例生成技术[J].计算机科学与探索，2008，2（6）：571-588.

[3] 屈婉玲，耿素云，张立昂，等.离散数学[J].北京：清华大学出版社，2005.

[4] 张丹，高建华.k-n软件系统测试集生成方法设计与研究[D].上海：上海师范大学，2008.

[5] 杨晋吉，苏开乐.SAT问题中局部搜索算法的改进[J].计算机研究与发展，2005，42 （1）.