有参数约束的两两组合覆盖测试用例生成的研究

有参数约束的两两组合覆盖测试用例生成的研究

曾劲涛1,2 崔志明1 陈建明1 李金忠2,3

1苏州大学 智能信息处理及应用研究所 苏州（215006）

2井冈山学院 信息科学与传媒学院 吉安（343009）3广西大学 计算机与电子信息学院 南宁（530004）

E-mail:rarehorse@163.com摘 要 对组合覆盖测试用例生成的研究已不少见，但考虑有参数约束情况的并不多。本文针对有参数约束的两两组合覆盖测试用例生成的问题，提出了n参数约束的概念，证明了n参数约束与二参数约束之间的等价转换关系；同时提出了一种基于IPO策略的有参数约束的两两组合覆盖测试用例生成算法，并与经典的AETG方法作比较，实验表明该算法在某些待测软件系统上可以得到比AETG方法更小的测试集；另外，该算法的确定性组合的特性使其在实际应用中可以更有效地降低测试成本。

关键词 软件测试，组合覆盖，测试用例，测试集，参数约束

1 引言

两两组合覆盖测试方法是一种科学、实用和有效的测试方法. 该方法基于以下基本事实: (1) 软件系统的故障往往是由一些难以预料的系统因素及其相互作用而引起的,为了检测这些故障,必须设计一组测试用例,对系统因素的各种组合情况进行充分覆盖的测试; (2) 由于受到时间、费用等资源的限制,我们必须在数量庞大的各种组合情况和有限的资源之间作出一种科学、优化的选择; (3) 研究发现,有20%～40 %左右的软件故障是由某个系统参数引发,20 %～40 %左右的故障由某两个参数的相互作用引发,而大约70 %的软件故障是由一个或两个参数的作用引起的[1]; (4) 两两组合覆盖测试是一种覆盖任意单个系统因素、任两个系统因素间的组合以及尽可能多的多个因素间组合的方法. 因此,两两组合覆盖测试方法具有很重要的应用价值[2]。目前,关于两两组合覆盖测试方法的研究主要集中在测试用例生成方法方面，例如Williams[3,4]、AETG[5,6]、IPO[7,8]、和PSST[11]等方法。但是这些方法中大多数未考虑有参数约束的情况。在AETG中讨论过有参数约束的情况，并给出了一个解决方案，但效果并不理想。针对这一现状，本文对有参数约束的情况进行了研究，并给出了一种基于IPO策略的算法。

2 基本概念

设待测软件系统SUT(Software Under Testing)的参数个数为n，并假定每个参数Pi可在有限离散点集Ti中取值，Ti中有ti个元素：ti=|Ti|(1≤i≤n).

定义1 称n元组（p1，p2，…,pn）为SUT的一个测试用例，其中p1∈T1，p2∈T2，pi∈Ti(3≤i≤n)。

定义2 对某个SUT生成的测试用例的集合称为该SUT的测试用例集，简称测试集。 定义3 对于某个SUT的测试集，如果该测试集覆盖了这个SUT的任意两个参数的所有取值的两两组合，称该测试集为两两组合覆盖测试集。

定义4 称包含一个SUT的所有参数的部分或全部取值的关联表格为关联表。 定义5 如果一个SUT的某两个参数之间的某个取值组合存在约束，即该取值组合禁止在一个测试用例中出现，则称该约束为二参数约束。

定义6 对于一个SUT的某n个参数的一组取值，如果这组取值中的任意(n-1)个值形成

1

http://www.paper.edu.cn

(n-1)参数约束，则称该组取值形成n参数约束。

定理1 一个n参数约束(n>2)可以等价转换为Cn2个二参数约束，该二参数约束是n参数约束的任意两个参数的组合。

证明：设一个n参数约束为（p1，p2，…,pn），可以将它转换为Cn2个二参数约束(pi , pj)，其中(1≤i ,j≤n)且i≠j。如果二参数约束小于Cn2个，即至少存在一个(pi , pj)不是二参数约束，则包含pi和pj的任意3个参数值不能形成三参数约束，以此类推，包含pi和pj的任意(n-1)

2

个参数值不能形成(n-1)参数约束，故不能形成n参数约束。反之，若存在Cn个二参数约束，则必然存在Cn3个三参数约束，以此类推，存在Cn1个(n-1)参数约束，故n个参数值形成n参数约束。证毕。

3 AETG方法对有参数约束情况的解决方案

针对参数间有约束的情况，AETG采用了一种分解关联表的方法，先将原关联表分解为若干个子关联表，并保证每个子关联表不存在参数约束；然后对每个子关联表生成相应的测试集，最后合并两个测试集，得到了一个两两组合覆盖测试集。例如，对一个34型（4个3值参数）的SUT,存在一个二参数约束(a2,a3)，图1显示了分解的结果。根据AETG算法，先对其中一个子关联表(设子关联表1)进行处理，产生了一个包含9个测试用例的测试集，然后再对子关联表2进行处理，由于B,C,D三个参数的两两组合覆盖已在子关联表1的测试集中得到满足，因此只需考虑参数A分别与B,C,D的组合覆盖，显然仅需3个测试用例即可满足覆盖的要求，即产生了一个包含3个测试用例的测试集；合并这两个测试集，得到一个大小为12的两两组合覆盖测试集。但事实上，该SUT存在一个大小为10的两两组合覆盖测试集(表1)，表明该方法得到的结果不够理想。

图1 原关联表分解为子关联表1和子关联表2

4 基于IPO策略的有参数约束的两两组合覆盖测试算法

在2002年Lei和Tai利用贪心算法,提出一种基于参数顺序的渐进扩充的两两组合覆盖测试用例生成方法(IPO),也开发实现了相应的测试用例自动生成系统——PAIRWISE TEST 系统[7,8]。

4.1 IPO策略

IPO策略的基本思想是以参数为对象，初始时先生成覆盖两个参数所有可能组合的测试集T，随后每次加入一个参数，通过扩展算法覆盖该参数和当前测试集内各参数所能形成的组合，并尽可能使测试集最小，如此进行直至所有的参数都加入到测试集中。测试集合T的扩展分为两个部分:水平扩展和垂直扩展。水平扩展是在已有的测试用例基础上加入新参数的某一个取值，不产生新的测试用例;垂直扩展在水平扩展之后进行，对仍未被覆盖的配对，通过生成新的测试用例将其覆盖。

2

http://www.paper.edu.cn

假设已通过IPO算法得到了包含参数p1 ,p2 ,…,pi - 1 的测试集T。水平扩展算法

使得该测试用例具有i个参数。设参(IPO_H)[8]就是对测试集T的每个测试用例增加一个pi值，

数pi在水平增长算法过程中已经产生了对参数p1 ,p2 , …,pi-1的测试集T’；令π为未被T’覆盖的组合集,π中的组合元素是参数pi的某个取值和p1 ,p2 ,…,pi-1中的某个参数的某个取值的组合；垂直增长算法(IPO_V)[8]就是在测试集T’的基础上增加新的测试用例，以覆盖π中所有的组合元素。最终得到的测试集T″就是p1 ,p2 ,…,pi 的两两组合覆盖测试集。

4.2 有参数约束的两两组合覆盖测试算法

在有参数约束的情况下，可以对IPO算法做以下修改。首先修改水平扩展算法，做以下几点修改：(1)增加一个关键的函数参数Constraints,表示二参数约束的集合；(2)将未覆盖组合集π的初始化移出水平扩展算法，加入到主体算法中， 并且令π={pi的值与p1 ,p2 ,…,pi - 1的值之间的两两组合}－｛所有的约束组合｝；(3) 从扩展第i个参数的第一个值开始，就采用贪心算法，以覆盖最多的未覆盖组合。事实上，原算法对扩展第i个参数的前min(|T|,ti)个值时，已经达到了贪心算法的结果，但是增加了参数约束条件后，原算法已不再适用。以下是改进的水平扩展算法(PCIPO_H)：

算法 PCIPO_H(T ,Pi ,Constraints)

// T是当前测试集, Pi是当前要扩展的参数, //Constraints是约束组合集； { 设Pi的值域为{ v1 ,v2 ,… ,vti }；

π= {pi 的所有取值与p1 ,p2 ,…,pi - 1的所有取值之间的两两组合}－｛约束组合｝； for 1 ≤j ≤|T| , 选择pi的一个最佳取值来扩展T中的第j个测试用例，让扩展后的测试用例能覆盖π中最多的组合元素,并保证该测试用例中不存在约束组合；最后从π集中删除由已扩展的测试用例所覆盖的组合元素； }

对于垂直扩展算法，做以下几点修改：(1)增加一个关键的函数参数Constraints,表示二参数约束的集合；(2)在用w覆盖‘-’时，必须保证w不会与该测试用例的其它参数形成参数约束。以下是改进的垂直扩展算法(PCIPO_V):

算法 PCIPO_V(T ,π, Constraints)

// T是当前测试集, π是当前未覆盖的组合集, //Constraints是二参数约束集； { 设一空集T′;

对于π中的每一个组合

{ 设该组合包含了pk (1≤k＜i) 的值w 以及pi 的值μ;

if (T′中的某个测试用例的pi值为μ且pk的值为“-” 并且w不会与该测试用例的其它参数形成参数约束) then

修改这一测试用例, 用w替换“-”; else

产生一个新的测试用例, 以w作为pk的值,μ作为pi的值,而“-”作为其它参数的值，将该测试用例加到T′中。 }

T = T ∪T′; }

主体算法如下：

算法 PCIPO(Parameters , Constraints)

//Parameters为参数列表，Constraints是二参//数约束集合；

3

http://www.paper.edu.cn

{ 先对头两个参数生成测试集T; For 3≤i≤n

{ π= {pi 的所有取值与p1 ,p2 ,…,pi-1的所有取值之间的两两组合} — {约束组合}； PCIPO_H(T，Pi ，Constraints) If (π非空) then

PCIPO_V(T，π，Constraints); }

替换T中的存在的“-”,可在该处对应的参数的可能取值中任选一个，但需保证不出现参数约束；

输出最终的测试集T。 }

在算法PCIPO_H中，当确定pi的最佳取值时可能会遇到多种选择。考虑三种不同的选择策略[11]：Forward策略，Greater策略，和Random策略，对于同一个SUT采用不同的选择策略会得到不同大小的测试集。

现在将PCIPO算法应用于第3节提到的实例系统。用Forward策略和Greater策略去运算，得到了大小分别为11和10的两个测试集。表1为大小为10的测试集。对于具有n参数约束的SUT，可以先将该n参数约束转换为Cn2个二参数约束，再进行运算。例如一个三参数约束(pi,pj,pk),可以转换成(pi,pj)、(pi,pk)和(pj,pk)3个二参数约束。

表1 大小为10的测试集

参数A 参数B 参数C 参数D

1 2 3 4 5 6 7 8 9 10 a1b1c1d1

a1b2c2d2

a1b3c3d3

a2b1c2d3

a2b2c3d1

a3b1c3d2

a3b2c1d3

a3b3c2d1

a2b2c1d2

a1b3c1d2

4.3 PCIPO算法的特性

令n表示SUT的参数个数，d表示参数可取值的最大个数（d=max{ti|1≤i≤n}），则PCIPO

算法的时间复杂度为O(d5n3)。同其它的两两组合覆盖测试用例生成算法一样，PCIPO算法也是在保证覆盖所有可能两两组合的前提下尽可能地减少测试集的大小。和其它某些算法不同的是，PCIPO算法是一种基于参数的组合方法。对于相同的输入参数，PCIPO算法产生的测试集始终相同，故该方法是一种确定性组合方法。这种特性使得PCIPO方法在实际应用中可有效地减少测试成本。例如，考虑一个关于计算机整体性能的测试问题。假设可选择测试的硬件为显卡、声卡和主板，每类硬件都有三种型号供选择。令参数A、B和C分别表示显卡、声卡和主板。由于事先各种硬件之间的兼容性是未知的，故可以令初始的参

Φ）；利用PCIPO算法进行计算，得到如表2所示的测试集。数约束集为空集（Constraints =

假设在处理第6个测试用例时，由于第2块显卡和第3块声卡不兼容而导致故障，则需要重新产生测试集进行测试。此时存在一个参数约束(a2,b3)，修改参数约束集使Constraints={(a2,b3)}，并重新用PCIPO算法进行计算，得到如表3所示的测试集。可以发现，表2和表3的前5条测试用例是相同的，这意味着对前5条测试用例的测试工作仍然是有效的，只需要从第6个测试用例开始测试即可。显然，这可以大大减少测试成本。而对于AETG等非确定性组合方法，由于不能保证重新生成的测试集能包含已处理过的测试用例，因此很可能要增加额外的测试成本。

4

http://www.paper.edu.cn

表2 参数约束集为空

1 2 3 4 5 6 7 8 9 参数A a1参数B b1参数C c1

a1b2c2

a1b3c3

a2b1c2

a2b2c3

a2b3c1

a3b1c3

a3b2c1

a3b3c2

表3 参数约束集为{(a2,b3)}

参数A参数B参数C

1

2

3

4

5

6

7

8

9

10

a1b1c1

a1b2c2

a1b3c3

a2b1c2

a2b2c3

a3b1c3

a3b2c1

a3b3c2

a2b1c1

a3b3c1

5 实验分析

考虑一个83×62×33×22型(3个8值参数、2个6值参数、3个3值参数和2个2值参数)

，表示第i个参数的第m个取值和第j个参数的SUT。先做一个二参数约束的标记（Pim, Pjn）

，对的第n个取值不能在同一个测试用例中出现。设该SUT具有一个二参数约束（P12, P27）

该SUT分别采用AETG和PCIPO方法。对于AETG方法，先将83×62×33×22型的关联表分解为71×82×62×33×22型和81×71×81×62×33×22型的两个子关联表，两个子关联表都是无参数约束的，先对两个子关联表的其中一个进行运算(不妨设第一个)，产生的测试集大小S1满足[10]

S1≥8×8 =64，剩下的子关联表产生S2 =8个测试用例，合并的测试集的大小S= S1+S2 ≥72。若先对第二个子关联表进行处理，也将得到相同的测试集大小的估计范围。对于PCIPO方法，利用Forward策略得到的测试集大小为71,利用Greater策略得到的测试集大小为68，而Random策略得到的测试集大小有可能小于68，故PCIPO方法产生的测试集大小S≤68, 显然要优于AETG方法得到的结果。

表4 仅有1个二参数约束的SUT

AETG PCIPO

34{(P12,P27)} ≥12 ≤10

76{(P32,P66)} ≥56 ≤50

313{(P11,P104)}

≥13 ≤29

220{(P51,P202)}

≥6 ≤19

83×62×33×22{(P12,P27)} ≥72 ≤68

表5 具有3个二参数约束的SUT

203

{(P12,P27),(P215,P315)

,(P15,P320)}

AETG PCIPO

≥460 ≤410

75×42×27

{(P13,P26),(P24,P72),(P61,

P121)} ≥70 ≤53

83×35

{(P14,P24),(P38,P83),(P62,

P71)} ≥88 ≤65

表4和表5列出了AETG方法和PCIPO方法对不同类型的SUT产生的测试集大小的估计范围。其中表4是仅有1个二参数约束的SUT，表5是有3个二参数约束的SUT。数据表明，对于某些SUT采用PCIPO方法得到的结果明显要优于AETG方法。由于对AETG产生的测试集大小作了最小估计，而对PCIPO产生的测试集作了最大估计，故实际的结果要比表中给的结果更好一些。例如表4中的313型SUT，PCIPO很有可能得到接近甚至好于AETG

5

http://www.paper.edu.cn

的结果。

6 总结

本文对有参数约束的两两组合覆盖测试用例生成进行研究，提出了n参数约束的概念，证明了n参数约束与二参数约束的等价转换关系。分析了AETG这个经典算法对有参数约束情况的解决方法；介绍了IPO策略算法，并提出了一种基于IPO策略的有参数约束的两两组合覆盖测试用例生成算法；分析了该算法的确定性组合的特性，并举例说明了该特性在实际应用中可有效地减少测试成本。实验数据表明，在某些有参数约束的待测软件系统上，该方法可以得到比AETG方法更小的测试集；因此，该方法具有一定的理论和应用价值。

参 考 文 献

[1] Kuhn D. R. , Gallo A. M. . Software fault interactions and implications for software testing. IEEE Transactio- ns on Software Engineering, 2004, 30(6): 418～421

[2] Kuhn D. R. , Reilly M. J . . An investigation of the applicability of design of experiments to software testing. In : Proceedings of the 27th NASA/ IEEE Software Engineering Workshop ,NASA Goddard Space Flight Center , 2002 , 4～6

[3] Williams A. W. . Determination of test configurations for pair-wise interaction coverage. In : Proceedings of the 13th International Conference on the Testing of Communicating Systems( TestCom 2000) , Ottawa Canada , 2000 , 59～74

[4] Williams A. W. . Software component interaction testing : Coverage measurement and generation of configu- rations [ Ph. D.dissertation ] . Ottawa-Carleton Institute for Computer Science, School of Information Technology and Engineering , University of Ottawa , Canada , 2002

[5] Cohen D. M. et al . The AETG system: An approach to testing based on combinatorial design. IEEE Transac- Tions on Software Engineering, 1997, 23(7) : 437～444

[6] Cohen D. M. et al . The combinatorial design approach to automatic test generation. IEEE Software , 1996 , 13 (5) : 83～87

[7] Lei Y. , Tai K. C. . In _ Parameter _Order : A test generation strategy for pairwise testing. Department of Computer Science ,North Carolina State University , Raleigh , North Carolina :Technical Report TR-2001-03 , 2001

[8] Tai K. C. , Lei Y. . A test generation strategy for pairwise testing. IEEE Transactions on Software Engineeri- ng, 2002 , 28(1) : 109～111

[9] 朱小骏.参数配对组合的软件测试方法研究与实现.中国优秀硕士学位论文全文数据库，2004. [10] 聂长海.基于接口参数的黑箱测试用例自动生成算法.计算机学报，2004，27(3):322-388. [11] 史亮.基于解空间树的组合测试用例生成.计算机学报，2006，29(6):849-857.

6

http://www.paper.edu.cn

The Research on Pairwise Covering Test Data Generation

With Parameter Constraints

1

Zeng Jin-Tao1,2 Cui Zhi-Ming Chen Jian-Ming1 Li Jin-Zhong2,3

（The Institute of Intelligent Information Processing and Application, Suzhou University, Suzhou 215006）1

（College of information science and communication jinggangshan university， ji'an 343009）2（College of Computer and Electronic Information Guangxi University，Nanning 530004）3

Abstract There are many papers on generation of combinatorial covering test data，but few of them introduce restriction of parameter constraints．This paper researchs on pairwise covering test data generation with the restriction of parmeter constraints．A concept of n-parameter constaint is proposed and the equivalent convertion between n-parameter constaint and 2-parameter constraint is proved in this paper．A pairwise covering test data generation algorithm based on IPO method is proposed．Experiments show that in some softwares under testing，this algorithm can produce test set with smaller size than the classic AETG method．In addition，its characteristic of determinate combination makes it more effective to reduce the testing cost，so the new method is of some value both in theory and practice． Keywords software test，combinatorial covering，test data，test set，parameter constaint

7