简单循环约减三三组合测试用例生成方法

艾 华，宋晓秋，安 恒

(中国航天科工集团第二研究院706所，北京 100854)

0 引 言

软件测试在软件开发过程中占重要地位，而测试用例是进行软件测试工作的基石[1]，研究结果表明覆盖强度为n的最小测试用例集生成问题是NPC问题，随着参数数量的增多，测试用例集规模也成倍增长，覆盖所有的组合势必使得测试用例集过大，从而导致测试工作占用巨大花费，研究发现约70%的软件缺陷可以通过两两组合测试发现，而通过三三组合测试能发现90%的软件缺陷，最后可以通过六六组合测试发现几乎所有的软件缺陷。随着覆盖强度的增加，测试用例集规模成指数形式增长，因此研究人员在如何覆盖强度为2的最小测试用例集的问题上进行了大量的研究，从不同角度出发提出了多种算法[2,3]。

迄今为止，软件测试领域对两两组合测试已有充分的研究，而针对三三组合测试用例集的生成方法研究较少，主要包括IPOG算法、ITCH算法、Jenny算法等由两两组合测试算法改进而来的通用算法，以及王小银等提出的基于蚁群算法的三三组合测试用例集的生成方法[4]。三三组合测试能弥补两两组合测试缺陷发现率较低的不足，还能避免更高覆盖强度组合测试成本过大的问题，本文以贪心算法为基础[5]，借鉴IPO算法的思路，针对三三组合测试问题，提出了一种简单循环约减三三组合测试用例生成方法(simple-cyclic-reduce，SCR)，算法的基本思路是先找到取值最少的前3个参数形成的最小测试用例集，再对剩下的参数进行逐个扩展，在扩展的同时进行循环约减，寻找当前已扩展参数的局部最优解[6]，直到参数完全扩展，得到的解近似代替全局最优解[7]。

1 组合测试概念及其模型

假定待测系统SUT(software under testing)有n个输入参数，用集合X={x1,x2,x3,…,xn}表示，输入参数xi对应的值域为Yi(i=1,2,3,…,n)。

定义1 测试用例集：假定某集合Ts={t1,t2,t3,…,tn}，对于集合中任意元素ti∈Ts,ti={ti1,ti2,ti3,…,tin},且tij∈Yj(i=1,2,3,…,n;j=1,2,3,…,n;i,j不相等)，则称集合Ts为待测系统SUT的一个测试用例集，ti为待测系统的一个测试用例。

定义2 两两组合测试用例集：假定某集合Ts为待测系统SUT的一个测试用例集，如果集合X中任意两个不同参数组成的任意组合对(xi,xj)，满足如下条件，存在t∈Ts，使得任意xi∈t,xj∈t(其中i=1,2,3,…,n;j=1,2,3,…,n，i,j不相等)，则称Ts为待测系统SUT的一个两两组合测试用例集。

例：设待测系统SUT有3个输入参数{x1,x2,x3}，各参数对应的值域{a,b}、{c,d}、{e,f},则SUT共有12个两两组合对，见表1。

覆盖这些两两组合对至少需要4个测试用例：(a,c,e)、(a,d,f)、(b,c,f)、(b,d,e)。两两组合测试能保证由一个参数及两个参数间相互作用引发的软件缺陷能被发现。

表1 3个2值参数SUT的两两组合对

定义3 三三组合测试用例集：假定某集合Ts为待测系统SUT的一个测试用例集，如果集合X中任意3个不同参数组成的任意组合对(xi,xj,xk)，满足如下条件，存在t∈Ts，使得任意xi∈t,xj∈t,xk∈t(其中i=1,2,3,…n;j=1,2,3,…n;k=1,2,3,…n;i,j,k互不相等)，则称Ts为待测系统SUT的一个三三组合测试用例集。

例：设待测系统SUT有4个输入参数{x1,x2,x3,x4}，各参数对应的取值{a,b}、{c,d}、{e,f}、{g,h},则SUT共有32个三三组合对，见表2。

覆盖这些三三组合对至少需要8个测试用例(a,c,e,g)、(a,c,f,g)、(a,d,f,g)、(b,c,f,g)、(a,d,e,h)、(b,d,e,g)、(b,c,e,h)、(b,d,f,h)。三三组合测试能保证到一个参数、两个参数及3个参数间相互作用引发的软件缺陷能被发现。

表2 4个2值参数SUT的三三组合对

2 相关研究

通过几十年的研究与积累，在组合测试用例集生成的研究中，两两组合测试用例集的研究已经相当充分，相关的算法有很多，其中较为常见的有基于代数构造法的正交拉丁方技术，及其变种Williams算法和Kobayashi算法；有基于贪心算法的IPO算法、AETG算法等；有基于解空间树的PSST算法；有基于蚁群算法的ACO算法，以及在这些算法的基础之上进行的通用化研究，将这些算法中的部分算法扩展到了三三组合测试用例集生成甚至n-way组合测试用例集生成，以下介绍几种常用的组合测试用例生成算法。

2.1 AETG算法简介

Cohen等提出通过“one-test-at-a-time”的思想来构建测试用例集直到所有的两两组合对都被覆盖的AETG算法，AETG算法在构建测试用例时采用尽可能多地覆盖较多的未覆盖组合对的贪心策略来生成较小的测试用例集。最初AETG算法旨在生成两两组合测试用的组合测试用例集，随着AETG算法的丰富与发展，出现了较多以AETG算法为基础的变种以及通用的组合测试用例生成方法。

2.2 IPO算法简介

Yu Lei等提出了生成结对测试用例的IPO算法，IPO算法采用贪心算法依次对参数进行水平扩展和垂直扩展直到扩展完所有的参数。IPO算法的基本思想是先对所有参数按照取值域非递增排序，先用前两个参数构造初始测试用例集，再依此进行水平扩展和垂直扩展，水平扩展在测试用例数量不变的基础上，添加新的参数的取值，使之包含的未覆盖组合对数量最多；垂直扩展在参数数量不变的基础上，增加新测试用例使得包含的未覆盖组合数量较多，或者改变已有的测试用例来实现覆盖，直到所有组合对都被覆盖，再扩展下一个参数，直到所有的参数都扩展完成。

同样地IPO算法最初也是解决两两组合测试的测试用例集生成问题，Yu Lei等对IPO算法进行通用化改进，提出IPOG算法和IPOG-D算法，使得该算法能解决n-way(2≤n≤6)组合测试用例集生成问题。IPOG算法整体与IPO算法相似，在初始化测试用例集所用参数个数以及组合对的覆盖强度上有变化，IPOG-D算法改变了扩展方式，将参数分为两组采用递归的形式进行求解，水平扩展过程是直接将列复制的过程，垂直扩展是将两种覆盖强度的组合合并的过程，结果往往比IPOG算法差，但节省了遍历并判断所有的n-way组合对是否被覆盖的时间，速度方面比IPOG算法快。

2.3 ACO算法简介

王小银等提出了基于蚁群算法的解决思路(ant colony optimization，ACO)，和AETG算法一样，采用“one-test-at-a-time”的思想来逐个测试用例地生成组合测试用例集。在蚁群搜索组合测试用例生成过程中，将参数对应成节点，参数的取值对应为从节点引出的有向边，一个测试用例为经过各节点的一条路径。蚁群算法过程是先将所有的蚂蚁汇集在出第一个节点，然后每只蚂蚁根据当前节点各边的信息素和动态启发信息的概率来选择到下一节点的边，直到蚂蚁走完所有节点，此路径对应一条测试用例，并添加到测试用例集中，直到覆盖所有的三三组合对。

2.4 算法比较与工具介绍

AETG算法每次生成测试用例时都会产生M个候选的测试用例，Cohen通过实验验证M=50时，算法的时间花费和结果相对较好，但总体时间花费较大。IPO算法直接对参数进行扩展，每次扩展一个参数，生成测试用例的速度快，但局部寻优能力有限，产生的结果往往不如AETG算法。ACO算法将蚁群算法的思路应用到测试用例集的生成问题上，但该算法信息素计算过程复杂，产生的结果有局限。目前三三组合测试方面的研究相对较少，逐参数扩展方面还有待改进，本文就此进行了研究。

Bob Jenkins在用C语言写了基于贪心算法的Jenny工具并公布在个人网站上供测试人员研究，此工具能生成2～6-way的测试用例集，Jenny工具操作简单，无界面，能直接输入参数调用并返回测试用例集。IBM研究院综合几种代数方法用Java语言设计了ITCH(intelligent test case handler)工具。Yu Lei用Java语言实现了IPOG算法和IPOG-D算法等多种逐参数形式生成测试用例集的策略，开发了具有用户界面的ACTS工具，ACTS工具可操作性强，能选择不同策略，不同覆盖强度以及制定参数间的约束，生成测试用例集后还可以验证组合对的覆盖率。

3 SCR算法

SCR算法以贪心算法为基础，根据逐参数扩展的思想来逐步生成三三组合测试用例集[8]。先从参数集中选择取值最少的前3个参数生成一个初始测试用例集，初始测试用例集包含所选3个参数的所有取值组合，接着向测试用例集中添加第4个参数，在添加参数时，利用该参数的所有取值[9]对测试用例集中所有的测试用例进行直接扩展，最后再对测试用例集中所有测试用例进行循环约减，直到循环约减测试用例集前后测试用例的数量不变，再添加下一参数，重复直接扩展和循环约减过程，直到扩展完所有参数[10]。

直接扩展过程：在增加参数时对当前测试用例集的所有测试用例，直接利用待扩展参数的所有取值对测试用例集的所有测试用例逐一扩展，使得新的测试用例包含的参数个数比之前的测试用例多一个。

直接扩展保证了完全覆盖性，增加参数时利用该参数的所有取值情况对上一步得到的测试用例集逐一扩展，扩展该参数后，由已扩展参数组成的所有三三组合对均包含在测试用例集中，而且测试用例之间可能重复包含部分三三组合对，因此需要再进行循环约减过程来进一步找到局部最小测试用例集。

循环约减过程：直接扩展后的测试用例集中可能存在大量可以约减的测试用例，判断测试用例能否约减的依据是该测试用例包含的所有三三组合对是否都被其它测试用例包含。遍历直接扩展后得到的测试用例集中的每个测试用例，若可以约减则从测试用例集中删除，循环上述过程，直到循环前后测试用例集大小不变[11]。

循环约减保证了局部最优性，每次循环约减后的测试用例集是包含已扩展参数的局部最优解，并作为扩展下一个参数的初始测试用例集，重复以上过程当扩展完所有参数并循环约减后得到的测试用例集即为全局近似的最优解。

如图1所示，SCR算法求解过程中需要输入参数集X={x1,x2,…,xn}， X含有n个参数(n不小于3)，SCR算法输出测试用例集Ts。

图2举例说明了SCR算法求解4个2值参数SUT的具体过程，以下将结合SCR算法描述具体分析求解过程，以便进一步说明SCR算法的基本思路。

图1 SCR算法描述

图2 SCR算法求解4个2值参数SUT过程

算法首先将测试用例集Ts初始化为空(line 1)，在调整参数集X顺序,使得X中前3个参数的取值数最少(line 2)，并利用X中前3个参数x1、x2、x3的所有组合加入Ts(line 3)，得到的结果如图2(a)所示。

接着在Ts中的每个测试用例添加x4，使之扩展成新的Ts(lines 6-11)，因为x4有两种取值，此前Ts规模为8，故扩展之后的Ts包含16个测试用例。对于第一个测试用例(a,c,e)，应该扩展为(a,c,e,*)，因为x4可以是g或h，故(a,c,e)被扩展为(a,c,e,g)和(a,c,e,h)，将扩展后的测试用例添加到Ts，并将被扩展的测试用例删除，得到最终的结果如图2(b)所示。

最后循环约减Ts，遍历直接扩展后的Ts中所有的测试用例t(line 18)，如果t中是否包含只有t覆盖的三三组合对，则t不可约减，Ts不变(line 22)，否则t可约减，将t从Ts中删除(line 24)，循环对Ts进行约减处理，直到在约减前后Ts中测试用例数量不减少(line 16)。对于第一条测试用例(a,c,e,g),包含的三三组合对有(a,c,e)、(a,c,g)、(a,e,g)、(c,e,g)，而这些三三组合还分别被Ts中测试用例(a,c,e,h)、(a,c,f,g)、(a,d,e,g)、(b,c,e,g)包含，因此测试用例(a,c,e,g)可以被约减。对Ts中每个测试用例重复第一条测试用例的操作，可知(a,c,e,g)、(a,c,f,h)、(a,d,e,h)、(a,d,f,g)、(b,c,e,h)、(b,c,f,g)、(b,c,f,h)、(b,d,e,g)、(b,d,f,h)均可被约减，且此时Ts中的测试用例都不能被约减，即循环约减结束，则最终得到的结果如图2(c)所示。

4 实验验证

SCR算法使用贪心策略逐个地寻找局部最优解，在寻找添加下一个待扩展参数之后的局部最优解时，以当前局部最优解为基础，并利用待扩展参数的所有取值直接扩展，再循环约减得到添加下一个参数之后的局部最优解，直到找到所有参数都被扩展后的局部最优解，这个局部最优解近似地代替全局最优解。

本文最后通过Java编程语言在Eclipse编程工具下实现了SCR算法[12]，在搭载了Intel(R) Core(TM) i5-7500 处理器，8G内存的64位Windows 10的操作系统的台式机上进行了如下实验，为充分比较算法的有效性，还从http://ranger.uta.edu/～ylei/fireeye/下载了FireEye开源工具，FireEye工具实现了IPOG算法等多种逐参数扩展的方法，FireEye工具重新命名为ACTS，以下实验中用ACTS来进行表示。此外还有C语言编写的开源工具Jenny，同样地，从http://www.burtleburtle.net./bob/math/jenny.html下载了Jenny工具进行实验比较。

表3和图3展示了具有3～10个2值参数的SUT，SCR算法生成的结果规模与时耗，含有3个或3个以上的2值参数的系统满足三三覆盖的测试用例数量至少是23=8，因此在表3中3个、4个参数的系统的最终解即最优解，随着参数个数的增加，最终解偏离了最优解，但随着参数个数的增加，测试用例数量增加慢，测试用例的增长趋势大致成线性趋势增长，而不是指数趋势增长。

表4和图4展示了具有4个2值到7值参数的SUT，SCR算法生成的结果规模与时耗，含有3个或3个以上的2值参数系统满足三三覆盖的测试用例数量至少是23=8，在表4中4个2值参数的最终解即最优解，随着参数取值个数的增加，最终解偏离了最优解，随着参数个数的增加，测试用例数量增加较快，测试用例的增长趋势大致成指数趋势增长。

表3 3～10个2值参数结果

图3 测试用例数量与2值参数个数曲线

结果参数取值数量234567大小840120272520888时间0.1230.1760.6340.8822.0524.673

图4 测试用例数量与参数取值个数曲线

表5和图5展示了具有5-15个5值参数的SUT，SCR算法和基于蚁群算法的ACO算法结果规模的比较，ACO算法在求解过程中利用信息素能迅速得到结果，SCR算法采用循环约减的方式运行时间长，测试用例集规模小。

表5 5～15个5值参数生成结果比较

图5 SCR算法与ACO算法比较

表6展示了不同系统下各种算法的结果，其中工具ACTS有多种策略，对于此实验，IPOG算法生成结果较好，选择ACTS中IPOG算法生成的结果进行比较(实验系统：25314151表示5个2值参数，1个3值参数，1个4值参数和1个5值参数组成的系统)。

综合以上结果，可以看出SCR算法生成的三三组合测试用例集规模小，且方法简单只包含直接扩展和循环约减的过程，能逐个添加参数并输出测试用例，随着参数的增多测试用例集规模变大，在测试时可以给测试人员提供参考，根据测试成本与测试需求选择合理的参数规模。

表6 3种方式生成的结果比较

5 结束语

本文提出了以贪心算法为基础，逐参数生成测试用例的简单循环约减的三三组合测试用例生成算法(SCR算法)。此方法先生成包含3个参数的最小测试用例集，再进行直接扩展和循环约减，得到最终结果。使用直接扩展和循环约减的方式生成测试用例集，方法简单，结果较好，能输出每次添加待扩展参数的之后用例集，运行时间比基于蚁群的三三组合测试用例集的生成方法和IPOG方法长。此外，SCR算法在求解过程中，参数的顺序不同会导致结果有显著的差异，因此SCR算法的时间复杂度和参数排序方面有待进一步研究。