快速生成两两组合测试用例集算法

周吴杰 张德平 徐宝文

(1东南大学计算机科学与工程学院，南京 210096)

(2南京大学软件新技术国家重点实验室，南京 210093)

(3南京航空航天大学信息科学与技术学院，南京 210016)

(4南京大学计算机科学与技术系，南京 210093)

组合测试是一种重要的软件测试方法，旨在用较少的测试用例有效地检测软件系统中各个因素间的交互作用对系统产生的影响.组合测试的一个关键问题是组合测试用例生成问题，即在保证因素组合覆盖能力的前提下，生成规模尽可能小的测试用例集，从而在保证测试用例错误检测能力的基础上尽可能节约测试成本.两两组合测试问题作为组合测试的简单情形已有大量的研究并在软件测试领域中获得广泛的应用.研究者们通过数学构造、贪心算法以及智能搜索等方法来生成规模尽可能小的测试用例集［1－7］，随后高维以及变强度的组合测试用例生成问题也得到研究［8－9］.由于两两组合测试用例生成问题的 NP－complete性质［1］，现有的近似算法均无法生成最优解.有些生成测试用例的启发式算法运行时间较长，只能在因素较少的测试场景中使用.本文提出一种简单快速的数学构造算法，该方法建立在二元的两两组合的最优测试数据集的生成算法基础上，在二元情形下能得到最优解.对于一般的待测软件系统，算法能确保得到的测试用例数据集规模是关于因素数目k对数阶增长的.算法的时间复杂性为O(klog k)，所以对于大规模的待测系统，算法生成测试用例集的速度很快.算法是分层构造的，这种分层性有利于测试结束后的故障定位，即一旦测试出软件失效，算法生成的测试用例集的分层结构有利于测试工作人员对导致软件故障的错误交互进行有效的定位与侦测.

1 组合测试基本概念与模型

假设影响待测软件系统(software under test，SUT)的因素共有 k个，用1，2，…，k表示，因素 i有vi(1≤i≤k)个可能的取值，用0，1，…，vi－1 表示.用记号［0，vi－1］表示集合{0，1，…，vi－1}.称(v1，v2，…，vk)为 SUT 的因素可取值数目向量.假设这些参数的取值是相互独立的，即某个参数的具体取值不会影响其他参数的取值或存在性.

定义1 设 k维向量 T={T1，T2，…，Tk}，其中Ti∈［0，vi－1］，i=1，2，…，k，则称该 k 维向量 T 为第i个因素取值为Ti的测试用例.

为了生成测试用例集，定义覆盖表如下:

定义2 设A是一个n×k表，表中第i列元素都取自［0，vi－1］，任取 A 中 2列(第 i列和第 j列)，则所有的二维组合都被表中某一行所对应的测试用例覆盖，即对任意的有序对(ai，aj)，ai∈［0，vi－1］，aj∈［0，vj－1］，至少存在一行 r，使得A［r，i］=ai，A［r，j］=aj.则称表 A 是一个两两组合覆盖表，记此表为 MCA(n;2，(v1，v2，…，vk)).称使得 MCA(n;2，(v1，v2，…，vk))存在的最小整数 n为两两覆盖表数，记为 MCAN(2，(v1，v2，…，vk))，当 v1=v2=…=vk=v时，简记为 CA(n;2，k，v)和 CAN(2，k，v).

若SUT中因素可取值数目为vi的因素个数为pi(i=1，2，…，s)，k=p1+p2+…+ps，不妨设 vi＞vj(i＜j)，则用一个简单记号来记此SUT的因素可取值数目向量，这时覆盖表记为MCA(n;2，).用覆盖表产生测试用例时，表中每列对应一个因素，每一行表示一个测试用例.

例如一个打印系统有2种类型打印机P1，P2，分别用0，1表示;打印的文件格式有JPEG，PDF，PS三种，分别用0，1，2表示.颜色及文件大小如表1所示.

表1 打印机系统的各个因素及其取值

如果对因素的所有可能取值组合进行测试，则需要2×3×2×3=36个测试用例，若只考虑任意2个因素之间的交互作用，则仅需要9条测试用例，如表2所示.

表2 打印机系统的两两组合测试用例集

称所有因素取值都是二元的SUT为二元待测系统，该系统的二维最小覆盖表构造问题已解决，其覆盖表数 CAN(2，k，2)=n，其中 k＞1，n 是满足条件的最小整数［10］.

对于一般的SUT，寻求最优的测试用例集问题是 NP－complete 问题［1］.但显然有 CAN(2，k，v)≥v2和所以表2中的测试用例集是最优的.

本文以下都假设SUT中因素数目k＞1.

2 生成两两组合测试用例集的快速算法

2.1 vk情形

在二元待测系统中，记 n1为满足条件的最小整数，构造最优的覆盖表为n1×k表，其中第1行全取0，其余的n1－1行中，对每一列取个1，使得各列互不相同.用这种方法构造出的二元覆盖表作为一个基本块，记为B(0，1).对任意的 a，b(a＜b)，记 B(a，b)为把基本块B(0，1)中的0置换成a，1置换成b得到的新基本块.这样把所有的基本块B(i，j)(0≤i＜j≤v－1)上下累加起来就构成了两两组合覆盖表.然而这种构造出来的覆盖表有很多冗余行，比如所有因素取值都为0的行有v－1行，为了消除这些冗余，需再引入另外的约简块 R(0，1).

在二元待测系统中，构造另外一个表，使得表中任取 i，j两列，(0，1)与(1，0)组合都至少在某一行出现.设n2为满足的最小整数，则根据Sperner定理，得到这种表的行数最少为n2，具有最少行数 n2的表可这样构造:每列中取个1，其余取值为0，使得各列互不相同.所构造出的满足上述性质的表称为约简块，记为R(0，1).对任意的 a，b(a＜b)，记 R(a，b)为把约简块R(0，1)中的0置换成a，1置换成b得到的新约简块.

运用基本块和约简块就可构造一般的两两组合覆盖表.对任意的 i，j(0≤i＜j≤v －1)，如果 i是偶数并且j=i+1时，用基本块B(i，j)来构造(i，j)对应的块，否则用约简块R(i，j)来构造，最后把所有的基本块B(i，j)和约简块R(i，j)上下累加起来就构成了两两组合覆盖表.具体算法如下.

算法1 构造两两组合覆盖表CA

输入:k，v(k＞1).

输出:覆盖表CA.

从基本块B(0，1)与约简块R(0，1)的构造，可得到如下定理:

定理1 算法1返回的CA就是覆盖表CA(n;2，k，v)，其行数为

证明 在CA中任取2列i，j列，对任意的组合(a，b)(0≤a，b≤v－1)，证明如下:

1) 当a＜b时，因为基本块B(0，1)或R(0，1)中都至少存在一行覆盖了组合(0，1)，所以对应的块 B(a，b)或 R(a，b)覆盖了(a，b).

2) 当a＞b时，基本块 B(0，1)或 R(0，1)中都至少存在一行覆盖了组合(1，0)，所以对应的块B(b，a)或 R(b，a)覆盖了(a，b).

3)当a为奇数，则组合(a，a)在基本块B(a－1，a)中被覆盖，当a为偶数且a≠v－1时，则组合(a，a)在基本块B(a，a+1)中被覆盖，当a为偶数且a=v－1时，则组合(a，a)被在算法1中最后添加的恒等行(v－1，v－1，…，v－1)所覆盖，所以算法1返回的CA是覆盖表CA(n;2，k，v).

由于算法1在构造过程中用了v(v－1)/2个块，当v为偶数时，基本块有v/2个，其余都是约简块，所以返回的覆盖表 CA的行数;当v为奇数时，基本块有(v－1)/2个，其余是约简块，最后是一个恒等行，所以覆盖表CA的行数.证毕.

定理2 算法1返回的覆盖表为CA(n;2，k，v)，其行数 n≤v(v－1)logk+1(k≥16).

证明 由于块B(0，1)或R(0，1)的每列互不相同，而互不相同的列最多有2n1或2n2个，所以2n1≥k，2n2≥k，即 n1≥logk，n2≥logk.

因为n1是满足条件的最小整数，所以，即

所以

而

故当n1≥14时，

因此，n1≤2logk(n1≥14).当 n1＜14时，列表3依次讨论.得到当 n1≥8时，即 k≥16时，n1≤2logk.

表3 n1＜14时因素数目k与n1的对应关系

与上述讨论类似，n2满足条件

即

所以

故当n2≥6时，

因此n2≤2logk(n2≥6).当 n2＜6时，列表4依次验证.得到对任意的k，都有n2≤2logk.

所以，n1与n2都满足

而算法1返回的覆盖表CA(n;2，k，v)是由v(v－1)/2个基本块或约简块构成，当v为奇数时再加上一个恒等行，所以其行数n≤v(v－1)logk+1(k≥16).证毕.

表4 n2＜6时因素数目k与n2的对应关系

由定理2知，当k→∞时，算法1返回的覆盖表行数是关于因素数目k对数阶增长的.

证明 由于生成块B(0，1)或R(0，1)是向表中每个位置写0或1操作，所以其时间复杂性是O(klogk)，所以算法1的时间复杂性为klogk).证毕.

由于在实践中很多SUT的各个因素可取值数目不一定都相等，所以需要把上述算法推广到因素可取值数目不一致的情形.假设因素可取值数目向量简写为，其中k=p1+p2+…+ps，且 vi＞vj(i＜ j).用 B(0，1，k)与 R(0，1，k)分别表示k列满足覆盖条件表中元素取值为0，1的基本块与约简块，另外若 k=1时，记 B(0，1，1)=R(0，1，1)=(1)，即为1 ×1 的表，表中唯一的元素取值为1，对任意的a，b(a＜b)，用B(a，b，k)和R(a，b，k)表示相应的置换后的基本块与约简块.用记号C(i)表示取值全是i的列向量，用D(i)表示每个元素可在［0，i－1］集合内任意取值的列向量.这时对任意的i，j，覆盖表中层的构造方法如下:

① 当0≤i＜j≤vs－1时，用具有 k列的块B(i，j，k)或 R(i，j，k)来构造.

② 当 i＜j且 vs－1 ＜j≤vs－1－1 时，用具有 k－ps列的块 B(i，j，k－ps)或 R(i，j，k－ps)来构造前面k－ps列.当0＜i≤vs－1时，后面的 ps列均为 C(i);当 vs－1 ＜ i≤vs－1－1 时，后面的 ps列均为D(vs).

③ 当i＜j且vs－1－1 ＜j≤vs－2－1 时，用具有k－ps－1－ps列的块 B(i，j，k －ps－1－ ps)或 R(i，j，k－ps－1－ps)来构造前面的列.当0 ＜i≤vs－1 时，后面的 ps－1+ps列均为 C(i);当 vs－1 ＜ i≤vs－1－1时，后面的列中前面ps－1列均为C(i)，后面的ps列均为 D(vs);当 vs－1－1 ＜ i≤vs－2－1 时，后面的ps－1+ps列中前 ps－1列均为 D(vs－1)，后 ps列均为D(vs).

如此继续进行，直至对0＜i＜j＜k都构造出相应的层.如果v1为奇数，最后并上1行，该行前P1个因素取值为v1－1，后k－p1个因素可取任意合法值.这样就可得到两两组合覆盖表，具体算法如下.

算法2 构造两两组合覆盖表MCA

输出:覆盖表MCA.

本文称算法2为 SpeedyPair算法，简称 SP算法.

根据上述分析及定理1～3，可得如下定理:

为了更清楚地看出SP算法中各个块的构成，举一个具体的例子如下:

假设SUT的因素可取值数目向量为5233210，用SP算法生成的两两组合覆盖表如图1所示.图中－1的位置表示“不关心”的位置，可用任意合法数值代替.

图1 CA(32;2，5233210)及其各个构成块

3 实验分析

为了研究SP算法的性能，本文通过实验比较了 AETG 系统［2］、PAIRTEST 系统［1］、Kobayashi等提出的代数方法［3］、Williams 提出的代数方法［4］，基于解空间树的组合测试工具［5］生成测试用例的规模，如表5所示.表5中前5种方法的试验数据均来自文献［5］.从表5中可看出，当各因素可取值数目较小时，SP算法效果较好，如 2100和41339235;当各因素可取值数目比较大时，如53443122，SP算法生成测试用例集比较大，甚至在34情形，SP算法没有生成最优解.

表5 测试用例集规模比较

但是SP算法的时间、空间效率高，针对大规模的待测系统，生成的测试用例集速度非常快，在编程语言为 Matlab，操作系统为 Windows XP，CPU 为 INTEL Pentium IV 2.93 GHZ，内存为512 MB的PC机上对大规模待测系统运行SP算法，结果如表6所示.

表6 大规模待测系统的运行效果

从表6中可看出SP算法时间效率很高，对大规模的SUT如有1.0×105个因素，每个因素有4个取值的 SUT，计算出两两组合覆盖表只需16.620 s.

用两两组合测试用例集来执行测试时，测试结束后如果检测出故障，就必须进行故障定位，这需要运行许多附加的测试用例.由于SP算法是分层的，发现故障后会很快确定哪一层出现故障，从而对故障定位阶段的工作提供帮助.

4 结语

本文提出了快速生成两两组合测试用例集的SP算法，其优点在于快速、简捷，当SUT是二元时能生成最小的测试用例集.实验表明该算法产生的测试数据与同类算法相比具有一定的特点与优势，可作为已有方法的重要补充.

由于SP算法局限在两两组合测试场景，如何把算法思想推广到多维组合测试场景，是需要进一步研究的问题.其次，SP算法生成的覆盖表有很强的分层结构性质，所以还需研究其结构，以便在故障出现时帮助和减轻在故障定位阶段的工作.

References)

［1］ Lei Y，Tai K C.In－Parameter－Oder:a test generation strategy for pairwise testing，TR－2001－03 ［R］.Raleigh，NC，USA:Department of Computer Science，North Carolina State University，2001.

［2］ Cohen D M，Dalal S R，Fredman M L，et al.The AETG system:an approach to testing based on combinatorial design［J］.IEEE Transactions on Software Engineering，1997，23(7):437－444.

［3］ Kobayashi N，Tsuchiya T，Kikuno T.A new method for constructing pair－wise covering designs for software testing［J］.Information Processing Letters，2002，81(2):85－91.

［4］Williams A W.Software component interaction testing:coverage measurement and generation of configurations［D］.Ottawa，Ontario，Canada:Ottawa－Carleton Institute for Computer Science，School of Information Technology and Engineering，University of Ottawa，2002.

［5］史亮，聂长海，徐宝文.基于解空间树的组合测试数据生成［J］.计算机学报，2006，29(6):849－857.Shi Liang，Nie Changhai，Xu Baowen.Pairwise test data generation based on solution space tree［J］.Chinese Journal of Computers，2006，29(6):849－857.(in Chinese)

［6］査日军，张德平，聂长海，等.组合测试数据生成的交叉熵与粒子群算法及比较［J］.计算机学报，2010，33(10):1896－1908.Zha Rijun，Zhang Deping，Nie Changhai，et al.Test data generation algorithms of combinatorial testing and comparison based on cross－entropy and particle swarm optimization method［J］.Chinese Journal of Computers，2010，33(10):1896－1908.(in Chinese)

［7］ Yan J，Zhang J.A backtracking search tool for constructing combinatorial test suites［J］.The Journal of Systems and Software，2008，81(10):1681－1693.

［8］ Lei Y，Kacker R，Kuhn D R，et al.IPOG－D:efficient test generation for multi－way combinatorial testing ［J］.Software Testing，Verification and Reliability，2008，18(3):125－148.

［9］ Cheng Xiang，Gu Qing，Li Ang，et al.Variable strength interaction testing with an ant colony system approach［C］//16th Asia-Pacific Software Engineering Conference.Batu Ferringhi，Penang，Malaysia，2009:160－167.

［10］Hartman A.Software and hardware testing using combinatorial covering suites［C］//Interdisciplinary Applications of Graph Theory，Combinatorics，and Algorithms.Norwell，MA，USA，2005:237－266.