习 乐 贲可荣

基于关联矩阵的两两组合测试算法

习 乐 贲可荣

（海军工程大学计算机工程系 武汉 430033）

组合测试是软件黑盒测试中的一种常用方法，能有效检测软件系统中由各个因素相互作用所引发的软件故障。基于参数顺序的约束满足算法IPO-SAT是一种常用的组合测试用例生成算法，该算法约束控制能力突出，能生成精简的两两组合测试用例集，但其计算过程频繁调用约束求解器，导致较多的时间开销。针对该问题，论文提出一种基于关联矩阵的两两组合测试改进算法MIPO，采取将约束信息存储于关联矩阵中的方式来避免调用约束求解器，以减少测试用例生成过程中的整体时间。针对5组不同的参数组合进行实验，结果表明，改进后的算法与IPO-SAT算法相比，生成两两组合测试用例集的时间可节省90%以上。

约束控制；测试用例生成；关联矩阵；组合测试

AbstractCombination test is a method usually used in software black box testing，which can effectively detect the software fault caused by the interaction of factors in the software system.The IPO-SAT algorithm used to generate the combined test case has strong control ability and can generate right pairwise test suites，but the calculation process frequently calling the constraint solver is complex and time consuming.To solve this problem，this paper proposes an improved pairwise test algorithm based on the associa⁃tion matrix，storing the constraint information in the correlation matrix without calling the constraint solver to reduce the computa⁃tion time.Experiment shows that compared to the IPO-SAT algorithm，the algorithm generates pairwise test suite with 90%time re⁃duction.

Key Wordsconstraints control，test case generation，correlation matrix，combination test

Class NumberTP311.5

1 引言

软件运行会受到系统的配置、外部的输入等因素的影响，除了可能受单因素影响外，因素间的相互作用也可能对系统的运行造成影响。在软件黑盒测试中，组合测试是一种有效的测试用例生成技术［1］，它假定系统失效是由少数参数间相互作用所触发，因此可用较小规模的测试用例集完成测试工作。两两组合测试（Pairwise Test）是组合测试中最简单的一种方法，要求测试用例集中每个参数的单个取值和所有其他参数的取值至少存在一次组合，既可以将测试用例的数量控制在较低水平，同时也能有效地暴露软件中存在的问题。相对于完全组合测试，两两组合测试通常能用较少的测试用例发现系统中的绝大多数缺陷。对两两组合测试效率［2～3］的统计结果表明，67%的失效是由一个参数出错引起的，93%的失效是由不超过2个参数组合出错引起的，98%的失效是由不超过3个参数组合出错引起的。

两两组合测试的目标是通过测试每一对参数的不同取值来获得较高的暴露问题能力，所以要求每一对参数的组合至少在测试用例集中出现一次［4］。但边界值分析和等价类划分法，通常只能保证单个参数的覆盖，所以在测试效果上，两两组合测试方法明显更有优势［2］。然而，Lei等研究表明［5～6］，根据给定参数的候选值，寻找两两组合测试用例集是一个NP完全问题，所以很难找到一种高效的算法求解最小的组合测试用例集，大多数研究工作集中在算法改进和扩展上。

Cohen 等［7～8］提出了基于 one-test-at-a-time策略的组合测试用例生成方法AETG，每次增加一个新的测试用例，计算过程较为复杂，得到的测试用例集也不够精简。文献［9～10］用贪心算法来改进AETG的缺点，由于都基于AETG框架，只是启发策略不同，并没有本质的改进。Lei等［11］提出了基于in-parameter-order策略的IPO算法，该算法先构造前两个参数的两两组合，然后逐步扩展到全部参数。它减小了算法的复杂性，同时也得到更为精简的测试用例集，但是不能处理参数间的约束问题。Hnich等［12］尝试将组合测试的约束问题转化为SAT的子句集来解决约束问题，但是得到的不是最优解，严峻等［13］使用 SAT工具 zChaff解决了这个问题。Lei等［14］给出了增强约束控制能力的IPO（In-Parameter-Order）算法，文献［15］针对它的约束控制问题，进一步给出了优化算法IPO-SAT，但是仍需要频繁调用约束求解器。文献［16］中采用关联矩阵的形式，存储组合参数的覆盖信息，虽然计算快速简单，但是约束控制能力差。目前还找不到一种通用的方法来高效解决所有组合测试的求解问题，IPO算法可以很好地控制测试用例集的规模，但是在参数复杂时往往使得求解时间急剧增加。

针对上述问题，本文将关联矩阵和IPO算法相结合，提出一种改进的基于关联矩阵的两两组合测试算法（Matrix-based In Parameter Order，MIPO），通过对关联矩阵的属性进行扩展来增强约束控制能力，将约束信息保存在关联矩阵中，以摆脱对约束求解器的依赖，从而减少求解时间，快速生成满足约束条件的两两组合测试用例集。实验结果表明，MIPO算法相比IPO-SAT，生成测试用例集的时间大幅减少。

2 组合测试相关知识

令待测试的软件系统有m个输入参数，第i个参数有ni个可能的取值，Vi表示第i个参数取值的集合，那么 t=(v1，v2，…，vm)（其中 v1∈ V1，v2∈ V2，…，vm∈Vm）就表示一个测试用例，这样的t的全体组成测试用例集T。理想情况下，测试工作需要执行完T中所有的测试用例。当参数取值数ni较大时，执行T中全部的测试用例是不现实的，只能选择其中部分测试用例进行测试，所以要权衡发现问题的能力和测试用例的数量。组合测试就是要研究测试代价和测试效果间的平衡。

2.1 关联矩阵

设 G=V，E 是 无 向 图 ，V={v1，v2，…，vn} ，E={e1，e2，…，em} ，关联 矩阵 M=(mij)n×n，其中：mij=1表示vi和vj存在连接，mij=0表示vi和vj不存在连接。例如一个包含4个顶点，3条边的无向图，其关联矩阵如图1所示。类比无向图的关联矩阵，将待组合参数的所有取值依次编排起来，分别对应矩阵的行和列，构成参数取值的关联矩阵，矩阵中每个值都表示参数取值间的组合关系。由于关联矩阵的对称性和冗余性，约定参数的关联矩阵里的以下元素无效：表示同一参数的不同取值间的组合关系的元素、表示各个参数的取值和自身组合关系的元素、矩阵左对角线以下的元素，如图2中阴影部分所示。初始关联矩阵中的元素都为0，若测试用例集中出现了某两个参数取值之间的组合，就将关联矩阵中对应的元素标记为1。当两两组合的测试用例集满足覆盖要求时，则矩阵中对应的有效元素都为1，即为目标矩阵。设X、Y、Z三个参数的取值分别为{x1，x2，x3}，{y1，y2}，{z1，z2}，当存在(x3，y1，z2)组合时所对应的关联矩阵如图2所示。

图1 无向图及关联矩阵

图2 XYZ对应的初始关联矩阵

2.2 约束条件

约束条件是指各个参数的取值组合必须满足一定的条件，而不是完全组合自由的。约束条件增加了组合测试的难度。例如，在表1所示的平板电脑和浏览器之间的组合中，平板电脑可以选择ipad和 Surface，浏 览 器 可 以 选 择 safari、IE、chrome、Edge、firefox。组合（iPad，IE）是不会出现的，因此平板电脑和浏览器之间的组合并非完全自由，即为组合的一个约束条件。

表1 设备和浏览器的组合

最常见的两种约束类型是参数组合中的依赖和冲突［15］：

1）浏览器选择IE，平板电脑就必须选择Sur⁃face，这种约束条件就是依赖型约束。浏览器为IE时，平板电脑必须为Surface，平板电脑取其它的值都是无效的组合，因此组合（iPad，IE）是禁止的，同样禁止的组合还有（iPad，Edge）。

2）平板电脑选择iPad，浏览器就不能选择IE或Edge，这种约束条件就是冲突型约束。平板电脑为iPad时，浏览器只能选择IE和Edge之外的选项，否则都是无效的组合，所以这些组合的是禁止的：（iPad，IE）、（iPad，Edge）。

对于参数间的依赖约束和冲突约束，这些约束条件都可以用禁止出现的组合的来表示。

2.3 IPO算法

IPO（In-Parameter-Order）是一种贪心算法，常被用来求解两两组合测试用例集。IPO算法先求得前两个参数的完全组合，在此基础上，不断将后续的参数添加到测试用例集中。在添加参数的过程中，需要保证后续每一个参数的取值与之前所有参数取值的两两组合，当最后一个参数完成时，则算法结束。

针对3个参数A、B、C，其取值分别为{a1，a2}、{b1，b2}、{c1，c2，c3}的情况，IPO算法步骤如下：

1）先构建前两个参数A、B的取值的完全组合即：(a1，b1，_)，(a1，b2，_)，(a2，b1，_)，(a2，b2，_)，此时 未 覆 盖 的 组 合 为 a1c1，a1c2，a1c3，a2c1，a2c2，a2c3，b1c1， b1c2， b1c3， b2c1， b2c2， b2c3。

2）在已生成的测试用例中将后续参数补充完整。首先添加 c1到 (a1，b1，_)中得到 (a1，b1，c1)，则无覆盖的组合为 a1c2，a1c3，a2c1，a2c2，a2c3，b1c2，b1c3，b2c1，b2c2，b2c3。同样添加 (a1，b2，c2)，(a2，b1，c3)，(a2，b2，c1)，此时未覆盖组合为 a1c3，a2c2，a1c2，a2c3。

3）为未覆盖的组合添加新用例。由于还剩4个组合未覆盖，所以还需要添加新的测试用例来达到对所有组合的覆盖。对于a1c3，a2c2，可以添加(a1，_，c3)，(a2，_，c2)。注意到，当 (a1，_，c3)填充成(a1，b2，c3)时，可以覆盖 b2c3。同理 (a2，b1，c2)可以覆盖b1c2。此时没有未被覆盖的组合，算法结束。

3 两两组合测试改进算法M IPO

如何提高算法的约束控制能力，减少计算时间，生成更小的测试用例集是组合测试研究的重点。在两两组合测试中，各种算法的约束控制能力已经满足大部分需要，但是算法的求解时间还存在优化的空间。

3.1 问题分析及解决思路

文献［15］中的IPO-SAT算法，虽然能够生成规模适当的测试用例集，但是对约束求解器频繁调用增加了时间开销，尤其当参数个数和约束条件增多时，耗时急剧增加。受文献［16］中关联矩阵的启发，本文提出一种改进的基于关联矩阵的两两组合测试用例生成算法MIPO，以减少生成测试用例集所用时间。该算法过程为：首先引入关联矩阵，同时为解决复杂的依赖问题，对关联矩阵进行约束信息属性扩展，以达到约束求解要求。其次，与IPO-SAT算法不同，将禁止出现的组合信息添加到关联矩阵的扩展属性中，从而直接在关联矩阵中检查约束条件的满足情况，不再调用约束求解器，以降低IPO算法为验证所生成组合是否满足约束条件所带来的时间开销，缩短整个测试用例集的生成时间。

3.2 基于关联矩阵的M IPO算法

在关联矩阵的基础上，扩充矩阵元素的属性，将约束控制信息加入其中，使得每个元素包含两个属性：覆盖信息F和约束信息Y。用Cell［a，b］表示取值a和取值b在关联矩阵中对应的元素，Cell［end，b］表示b所在列最后一行的元素。关联矩阵的具体含义如表2所示。

表2 关联矩阵扩展后的属性和含义

由于关联矩阵的最后一行未被利用，可以用于统计各取值的覆盖情况和约束信息，每一列的覆盖信息F之和保存在最后一行对应的覆盖信息F中，每一列的约束信息Y之和保存在最后一行对应的约束信息Y中。改进的算法利用IPO的用例生成策略，在满足约束条件的状态下不断将新的参数取值添加到生成的测试用例集中。对于m个输入参数 P1，P2，P3，…，Pm，每个参数分别对应着 n1，n2，n3，…，nm个取值 (n1≥n2≥n3≥…≥nm)，在这些输入参数之中，存在着约束条件集C，C中的组合禁止出现在测试用例集中，最终算法退出时得到满足约束条件的测试用例集T。在下面给出基于关联矩阵的MIPO组合测试算法，其中算法1调用算法1.1和算法1.2。算法1初始化关联矩阵并生成覆盖前两个参数组合的测试用例。

算法1 基于关联矩阵的IPO组合测试算法

输入：参数 P1，P2，P3，…，Pm，及对应的候选输入个数 n1，n2，

n3，…，nm，约束集C 。输出：测试用例表T。

1.生成一个关联矩阵M；

2.For each Cell［x，y］∈M do

3.Cell［x，y］.F←0；

4.Cell［x，y］.Y←0；5.End for

6.For each（x，y）∈C do

7.Cell［x，y］.Y←1；

8.Cell［end，y］.Y←Cell［end，y］.Y+1；

9.End for

10.将P1，P2两两组合加入T，T=｛（P1.u，P2.v，_，…，_）|P1.u，P2.v分别为P1，P2的取值｝；

11.Cell［P1.u，P2.v］.F←1；

12.Cell［end，P2.v］.F←Cell［end，P2.v］.F+1；

13.For Cell［P1.u，P2.v］∈M do

14.If Cell［P1.u，P2.v］.Y=1&Cell［P1.u，P2.v］.F=1 then

15. 从T中删除（P1.u，P2.v，_，…，_）；

16.Cell［P1.u，P2.v］.F←0；

17.Cell［end，P2.v］.F←Cell［end，P2.v］.F-1；

18. End if

19.End for

20.For i：=3 to m do

21. 调用子算法ADDPARA（T，M，Pi）；//在T中添加参数Pi

22. 调用子算法ADDCASE（T，M，Pi）；//在T中添加Pi的新用例

23.End For

算法1主要生成前两个参数的两两组合，后续参数尚未加入测试用例集T中，所以针对每个后续参数Pi，都要调用算法1.1来将T中的每个用例中填入Pi的取值。

算法1.1 ADDPARA（T，M，Pi）

输入：已生成的测试用例集T及对应的关联矩阵M，参数Pi。

输出：更新后的测试用例集T和关联矩阵M。

假定Pi的取值分别为v1，v2，v3，…，vni；

1.For each t∈T do

2. For v：=v1to vmdo

4. End for

5.根据Cell［end，Pi.v］.F对v1，v2，v3，…，vni进行增序排序，

记录在数组A［］中；

6. For k：=1 to nido

7. 将A［k］对应的取值Pi.v加入到t中对应参数位置，并在关联矩阵中设置对应的覆盖信息；

8.If Cell［end，Pi.v］.Y=0 then

9. Break；

10. Else

11.For each Cell［a，Pi.v］∈M do

12. If Cell［a，Pi.v］.Y=1&Cell［a，Pi.v］.F=1&a≠end then

13. 将Pi.v从t中删除，并在关联矩阵中更新对应的覆盖信息；

14. Break；

15. End if

16. End for

17. End if

18.End for

19.End for

算法1.1在T中的每个测试用例中都加入了Pi的一个取值，但是不能排除Pi是否仍有未覆盖到的组合，因此调用算法1.2来将所有的Pi组合加入T中。

算法1.2 ADDCASE（T，M，Pi）

输入：已生成的测试用例集T及对应的关联矩阵M，参数Pi。

输出：更新后的测试用例集T和关联矩阵M。

假定Pi.v是Pi的取值，Ph.w是Ph的取值（h＜i）

1.For each Cell［Ph.w，Pi.v］∈M do

2.If Cell［Ph.w，Pi.v］.Y=0&Cell［Ph.w，Pi.v］.F=0 then

3. For each t∈T do

4. If t中 Ph为空 &Pi为 v then

5. 将Ph.w添加到t中Ph对应的位置；

6. 设置关联矩阵中对应的覆盖信息；

7. End if

8.For each Cell（a，b）∈M do

9.If Cell（a，b）.Y=1&Cell（a，b）.F=1&a≠end then

10. 从t中删除Ph.w，更新关联矩阵的覆盖信息；

11. End if

12. End for

13. End for

14.End if

15.End for

16.For each Cell［Ph.w，pi.v］∈M do

17.if Cell［Ph.w，Pi.v］.Y=0&Cell［Ph.w，Pi.v］.F=0 then

18. 在T中新增t’，分别设置Ph，Pi为w，v；

19. 更新关联矩阵的覆盖信息；

20.End if

21.End for

22.For each t∈T do

23.If t中参数Pj为空then

24. For v：=v1to vnjdo

26. End for

27. 根据 Cell［end，Pj.v］.F对v1，v2，v3，…，vnj进行增序排序，记录在数组A［］中；

28. For k：=1 to njdo

29. 将A［k］对应的Pj.v加入到t中Pj对应的位置，并在关联矩阵中设置对应的覆盖信息；

30.If Cell［end，Pj.v］.Y=0 then

31. break；

32. Else

33.For each Cell［a，Pj.v］∈M do

34.If Cell［a，Pj.v］.Y=1&Cell［a，Pj.v］.F=1&a≠end then

35 将Pj.v从t中删除，并更新关联矩阵中对应的覆盖信息；

36. Break；

37. End if

38. End for

39. End if

40. End for

41. End if

42.End for

算法1中，首先构建关联矩阵M并初始化，然后将所有的约束条件添加到M中。根据取值个数最多的两个参数，进行完全组合，添加到测试用例表T中，并更新M中的覆盖信息。根据覆盖信息和约束信息，检查T中组合的合法性，对于不合法的组合，从T中删除并清除M中对应的覆盖信息。

然后添加后续的参数Pi，调用算法1.1。对T中每一个用例t，先根据Pi当前所有取值各自已经参与组合的次数进行增序排序，选择次数最少的取值添加到t中，如果约束条件不被满足，则替换成下一个取值，直到满足为止，然后更新M中覆盖信息。

完善所生成的用例，再调用算法1.2。当T中所有的用例都添加了Pi的一个合法取值后，如果在M中，仍存在Pi未覆盖的组合(Pk.u，Pi.v)，则根据未覆盖组合对应的两个参数Pk，Pi，在T中寻找这两个参数未覆盖的测试用例t，将u和v添加到t中Pk，Pi对应的位置，然后检查合法性，如非法就从t中删除u和v，并清除对应的覆盖信息。然后用同样方法处理下一个未覆盖的组合，直到处理完所有未覆盖的组合。

如果在M中，仍然存在Pi未覆盖的组合(Pk.u，Pi.v)，则根据未覆盖组合对应的两个参数Pk和Pi，在T中增加测试用例t，将u和v分别添加到t中Pk和Pi对应的位置，并更新对应的覆盖信息。然后用同样方法处理下一个未覆盖的组合，直到处理完所有未覆盖的组合。

对T中每一个用例t，若t中存在未填充的参数Pj，先根据Pj当前所有取值各自已经参与组合的次数进行增序排序，选择次数最少的取值添加到t中相应位置，如果约束条件不满足，则换成下一个取值，直到满足为止，然后更新M中覆盖信息，添加Pi工作完成，接着继续添加下一个参数Pi+1，直到Pm添加完成。

4 实验

某舰艇指控软件从数据链接口获取当前舰艇航海信息，对其接口参数取值范围进行等价类划分和边界值分析后，得到接口参数的离散取值情况如表3所示。

表3 航海参数及离散取值情况

表3中一共有6个参数，每个参数有10个离散取值，覆盖参数间的所有组合需要106个用例，故考虑两两组合的测试方法减少测试用例。为了验证MIPO算法在缩减计算时间上的有效性，本文用C语言实现了MIPO算法和IPO-SAT算法，对6个参数、每个参数10个取值进行两两组合测试用例集生成时间对比实验，所有的参数间允许自由组合。实验平台配置为：处理器Core i5-2430M 2.4GHz、内存8GB DDR3-1333、操作系统Windows7 64位、集成开发环境VS2010专业版。两种算法的试验结果对比如表4所示。

表4 MIPO与IPO-SAT生成测试用例数量和时间

由表4中的实验结果看出，两种测试用例生成算法生成用例规模相当，但是MIPO算法生成时间远小于IPO-SAT算法。为了充分比较两种算法在生成用例规模和时间开销上的差异，本文补充了不同的对比实验，包括参数个数都为6个时，参数取值分别为20个、15个的情况以及参数的取值个数都为20个，参数数量分别为5个、7个的情况，分别记为ST1、ST2、ST3、ST4。具体的参数配置情况如表5所示。

表5 4组对比试验参数配置情况

分别使用IPO-SAT程序和MIPO程序来生成ST1、ST2、ST3、ST4的测试用例集，得到生成的测试用例数量以及所花费的时间，如表6所示。

表6 生成用例时间对比

从表6可以看出，在同样的输入参数情况下，MIPO算法在生成两两组合测试用例时，比IPO-SAT算法花费的时间减少90%以上。当参数个数不变时，取值个数增加，IPO-SAT算法的执行时间急剧增加，而MIPO算法的执行时间增加缓慢。当参数取值个数不变时，参数个数增加时，IPO-SAT算法的执行时间急剧增加，而MIPO算法的执行时间增加缓慢。实验结果表明，MIPO算法相比IPO-SAT，生成测试用例集的时间大幅减少，在参数增多的情况下，时间上的优势更为突出。

通过实验可以看出，MIPO与IPO-SAT相比，能够生成大小相当的测试用例集，能够在更快的时间内计算完成，计算效率更高。改进算法在求解时间上的优势主要在于MIPO不调用约束求解器，节省了大量的求解时间。但是需要付出的代价是牺牲了约束求解器的通用性，关联矩阵只能处理两个参数之间的约束问题。

5 结语

本文通过对已有两两组合测试用例生成算法的改进，提出了一种新的两两组合测试用例生成算法MIPO。基于关联矩阵的两两组合测试算法，执行步骤简单快速。另一方面，IPO-SAT方法能够很好地处理约束问题，同时也能够得到较为精简的测试用例集，但是当参数数量和约束增多时，计算耗时急剧增加。针对该问题，本文提出了一种两两组合测试用例集生成算法MIPO，利用关联矩阵存储约束信息，使用IPO策略生成测试用例集。实验表明，在给定同样的参数设置时，MIPO算法相比IPO-SAT算法，由于摆脱了约束求解器的依赖，能够大幅减少计算时间。受限于关联矩阵的二维结构，还不能处理三个及以上参数间的组合问题，如何将该算法推广到更高强度的组合测试中是需要进一步研究的内容。

［1］陈翔，顾庆，王新平，等.组合测试研究进展［J］.计算机科学，2010，37（3）：1-5.

CHEN Xiang，GU Qing，WANG Xinping，et al.Research Advances in Interaction Testing［J］.Computer Science，2010，37（3）：1-5.

［2］K.Go，S.Kang，J.Baik.Pairwise testing for systems with date derived from real-valued variable inputs［J］.Soft⁃ware：Practice and Experience，2016，46（3）：381-403.

［3］D.M.Cohen，S.R.Dalal，J.Parelius.The combinatorial design approach to automatic test generation［J］.Soft⁃ware：Practice and Experience，1996，13（5）：83-88.

［4］D.Richard，R.kacker，Yu Lei.Introduction to Combina⁃torial Testing［M］.Berlin：Springer，2013：34-35.

［5］王子元，钱巨，陈林，等.基于One-test-at-a-time策略的可变力度组合测试用例生成方法［J］.计算机学报，2012，35（12）：2541-2552.

WANG Ziyuan，QIAN Ju，CHEN Lin，et al.Generating Variable Strength Combinatorial Test Suite with One-test-at-a-time Strategy［J］.Chinese Journal of Com⁃puters，2012，35（12）：2541-2552.

［6］Lei Y，Tai KC.In-Parameter-Order：A test generation strategy for pairwise testing［J］.IEEE Transactions on Soft⁃ware Engineering，2002，28（1）：109-111.

［7］D.M.Cohen，S.R.Dalal，J.Parelius.The Combinatorial Design Approach to Automatic Test Generation［J］.IEEE Software，1996，13（5）：83-87.

［8］D.M.Cohen，S.R.Dalal，M.L.Fredman.The AETGSys⁃tem：An Approach to Testing Based on Combinatorial De⁃sign［J］.IEEE Transactions on Software Engineering，1997，23（7）：56-63.

［9］R.Bryce.A Deterministic Density Algorithm for Pairwise Interaction Coverage［C］//Proceedings of the International Conference on Software Engineering.Innsbruck：IEEE Press，2004.245-252.

［10］Y.W.Tung，W.S.Aldiwan.Automating test case genera⁃tion for the new generation mission software system［C］//Proceedings of IEEE Aerospace Conference.New⁃ark，2000.431-437.

［11］Y.Lei，K.C.Tai.In-parameter-order：a test generation strategy for pairwise testing［C］//Proceedings of High-As⁃surance Systems Engineering Symposium.Los Alamitos：IEEEPress，1998.254-261.

［12］Hnich B，Prestwich S，Selensky E.Constraint-Based ap⁃proaches to the covering test problem［C］//Joint Annual Workshop of ERCIM/CoLogNet on Constraint Solving and Constraint Logic Programming（CSCLP）.Berlin：Springer，2004.172-186.

［13］Yan J，Zhang J.Backtracking algorithms and search heu⁃ristics to generate test suites for combinatorial testing［C］//30th Annual International Computer Software and Applications Conference.Los Alamitos：IEEE Press，2006.385-394.

［14］Linbin Yu，Yu Lei.An Efficient algorithm for constraint handling in combinatorial test generation［C］//IEEE Sixth International Conference on Software Testing，Veri⁃fication and Validation（ICST）.Luxembourg：IEEE Press，2013.242-251.

［15］Shiwei Gao，Binglei Du，Yaruo Jiang.An efficient algo⁃rithm for pairwise test case generation in presence of con⁃traints［C］//International Conference on Systems and In⁃formatics（ICSAI）.Shanghai：IEEEPress，2015.406-410.

［16］宋道远.装备软件网络接口测试自动化研究［D］.武汉：海军工程大学，2013：31-35.

SONG Daoyuan.Research of Equipment Software Net⁃work Interface Test Automation［D］.Wuhan：Navy Uni⁃versity of Engineering，2013：31-35.

A Pairw ise Test Suite A lgorithm Based on Correlation M atrix

XI Le BEN Kerong
（Department of Computer Engineering，Navy University of Engineering，Wuhan 430033）

TP311.5

10.3969/j.issn.1672-9722.2017.09.006

2017年4月14日，

2017年5月21日

国防基金《基于容错机制的面向服务可信支持技术研究》项目（编号：513150402）资助。

习乐，男，硕士研究生，研究方向：软件质量保证技术。贲可荣，教授，博士生导师，研究方向：软件工程、人工智能。