2015, Vol. 26
2. 中国矿业大学 信息与电气工程学院, 江苏 徐州 221116;
3. 中国矿业大学 理学院, 江苏 徐州 221116;
4. 江苏师范大学 计算机科学与技术学院, 江苏 徐州 221116
2. School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221116, China;
3. College of Science, China University of Mining and Technology, Xuzhou 221116, China;
4. School of Computer Science and Technology, Jiangsu Normal University, Xuzhou 221116, China
作为软件开发周期中的重要环节,软件测试能够发现程序中存在的缺陷,从而提高被测软件的质量.变异测试是一种直接面向缺陷的测试技术,包括3个主要环节:(1) 对原程序进行合乎语法的微小变动,生成被称为变异体的原程序副本,相应的语法变动规则称为变异算子;(2) 基于给定的测试用例集,分别执行原程序和变异体,如果某变异体执行结果不同于原程序,则称该变异体被杀死;(3) 计算变异得分(mutation score,被杀死变异体占所有可杀死变异体的百分比,不可杀死的变异体称为等价变异体),并对测试结果进行评价.
变异测试以人为的方式注入缺陷[1],可以选择注入缺陷的种类和发生的位置,具有很强的针对性[2].研究表明,这种变异缺陷很大程度上能够反映软件中的真实缺陷[3, 4].变异测试通过发现这些变异缺陷,评价和改善测试用例集的完备性.与其他结构化测试准则相比,满足变异测试准则的测试用例集具有更高的缺陷检测能力[5].研究结果表明:变异测试能够反映测试用例集的实际缺陷检测能力[6, 7, 8, 9, 10],而传统覆盖测试(如语句覆盖、分支覆盖、all-uses等)与测试用例的缺陷检测能力没有很强的联系[9, 10, 11, 12, 13].
变异测试的可行性基于如下两个基本假设:胜任的程序员假设(competent programmer hypothesis,简称CPH)[14]和组合效应假设(coupling effect hypothesis,简称CEH)[14, 15].CPH认为:胜任的程序员开发的程序“接近”正确版本[16],因此程序中的缺陷是有限的、可描述的,并可以通过简单的语法转化更正.CEH认为:复杂缺陷由简单缺陷组合而成[16],因此能够检测到所有简单缺陷的测试用例集,也能够检测到绝大多数的复杂缺陷.CPH和CEH在变异测试中被广泛认可,CEH更是得到充分的理论证明和实验验证[15, 17, 18].作为一种有效的测试方法,变异测 试已取得丰硕的研究成果,相关工具也已应用于实际的软件测试中[19].
实际的软件通常包含大量的代码、复杂的语句以及各种变量[20],这些显著增加了可变异的位置和可实施的变异算子类型,从而导致变异体数量急剧增加.为了杀死这些变异体,所需的测试用例也随之增加.这说明,庞大的变异体数量显著增加了变异测试的成本,从而降低了变异测试的效率.因此,采用合适的策略减少变异体的数量,将有助于提高变异测试的效率.尽管已经有一些约简变异体的方法[21],但是现有方法约简变异体的效率仍有待于进一步提高.
本文根据弱变异测试准则,提出基于统计占优分析的变异体约简新方法.该方法首先基于弱变异测试转化思想[22]构造反映杀死变异体必要性条件的变异分支;然后,利用统计方法分析变异真分支之间的占优关系,那些被占优变异分支对应的变异体就是需要约简的变异体.相应地,非被占优分支对应的变异体则是约简后的变异体;最后,依据本文所提方法建立变异体自动约简原型系统.8个典型程序的变异测试结果表明:所提方法能够大幅度约简变异体,从而提高变异测试效率.
本文第1节综述相关的研究工作和本文的研究动机.所提出的方法在第2节详细加以阐述,包括弱变异测试转化思想、统计占优分析模型以及变异体约简的方法.第3节建立基于本文方法的原型系统,并进行实验和分析.最后,在第4节中总结全文,并指出后续的研究内容.
1 相关工作降低变异测试代价一直是研究的热点,常用方法有:减少变异体数量和通过弱变异测试降低执行代价.此外,语句的相关性分析也有助于降低变异测试代价.本节从以上3个方面回顾已有的研究工作,并引入本文的研究问题.
1.1 变异体约简为数众多的变异体是影响变异测试效率的主要原因,因此,如何有效地减少变异体数量,成为相关研究的主要动机之一.Acree和Budd通过随机选择一定比例的变异体执行变异测试,首次提出抽样变异测试思想[23, 24]. Mathur等人在10%~40%的抽样范围内,以5%的步长考察抽样比例对变异测试充分度的影响,结果发现:随着抽样比例的减小,变异得分明显下降[25].
Mathur对各类变异算子进行分析,发现变异算子ASR(array reference for scalar variable replacement)和SVR(scalar variable replacement)产生30%~40%的变异体,因此建议舍弃这两类变异算子,并提出选择变异测试方法[26].Offutt等人的实验结果表明:随着被舍弃变异算子的增多,变异得分呈现明显的下降趋势[27].Offutt等人通过28个测试程序考察各类变异体的分布情况,发现仅保留ABS(absolute value insertion)等5类变异算子,能够维持较高的变异测试充分度[28].
与上述变异体约简方法不同的是,Jia等人利用元启发式搜索方法,将多个传统变异体组合成一个高阶变异体(high order mutant,简称HOM)[29].高阶变异体包含多个缺陷,而仅包含一个缺陷的变异体,称为一阶变异体(first order mutant,简称FOM).高阶变异体不仅能反映实际软件中的复杂缺陷,还能显著减少变异体的数量[30]. Polo等人通过生成二阶变异体,降低了约50%的变异测试成本,并维持较高的变异测试充分度[31].
抽样和选择方法能够有效地减少变异体数量,并维持较高的变异测试充分度.但是,随着约简率的提高,变异测试充分度受到明显的影响.因此对于实际的应用程序,抽样和选择很难在维持很高变异得分的同时取得较高变异体约简率.高阶变异测试无疑是一种有效、实用的测试技术,但是随着变异体阶次的提高,测试成本也急剧攀升.
1.2 弱变异测试要杀死变异体,首先,测试用例必须能够执行到变异语句;然后,执行变异语句后,程序的状态发生改变;最后,状态的改变必须影响到程序的输出结果.DeMillo等人将上述3个条件分别定义为可达性、必要性和充分性[32].强变异测试准则以满足充分性条件作为杀死变异体的判定依据.Howden认为,在强变异测试中,反复执行变异语句的后续语句是不必要和低效的,并提出弱变异测试准则[33].该准则考察执行变异语句后的程序状态,如果与原程序不同,则认为变异体被杀死,即,满足杀死变异体的必要性条件.
可达性、必要性和充分性这3个条件逐次增强,因此,满足充分性条件更加困难.而满足必要性条件并不能保证执行结果一定不同.Horgan等人的分析表明:在特定情况下,弱变异测试和强变异测试同样有效[34].DeMillo等人的实验结果也表明:满足必要性条件的测试数据,能够在很大程度上满足充分性条件[35].Offutt等人通过实验分析得出:在绝大多数的情况下,弱变异测试是强变异测试的有效替代,且弱变异测试能够节省50%的测试成本[16].
为了进一步降低弱变异测试成本,Papadakis等人根据杀死变异体的必要性条件,将变异前后的语句组合成变异分支,并把所有变异分支集成到原程序中,将变异测试问题转化为分支覆盖问题进行求解,进一步提高了变异测试效率[22].Papadakis等人还通过分析变异分支所在的路径,选择适当的路径,高效地生成覆盖相应路径的测试用例[36].但是,由于没有对变异体实施约简,变异体转化为等量的变异分支,集成到新程序中,极大地增加了转化后程序的复杂度,降低了测试用例的生成效率.
1.3 相关性分析弱变异测试方法能够显著降低变异测试代价;基于弱变异测试准则,将变异测试问题转化为分支覆盖问题,或路径选择问题进行求解,可以进一步提高变异测试效率.然而,弱变异测试或基于弱变异准则的测试转化方法并没有减少所需杀死的变异体数量,这说明,这类方法的测试效率仍有很大的提升空间.因此,采用合适的策略大幅度约简变异体,能够显著提高弱变异测试效率.研究表明:程序语句之间存在复杂的相关性,设计合适的测试策略,充分利用某种相关性,能够有效降低测试代价.
Ghiduk等人在研究语句覆盖测试问题时,根据目标语句之间的相关性,通过仅覆盖非被占优语句,有效减少了所需覆盖的目标语句数量[37].Gong等人利用分支之间的占优关系判定不可行路径,从而避免了试图覆盖不可行路径产生的不必要测试成本[38].对语句进行相关性分析,同样有益于提高变异测试效率.单锦辉等人分析同一位置产生的多个变异体,并利用杀死这些变异体条件的相似性将它们组合成复合变异体,从而显著减少了变异体数量[39].徐拾义根据变异语句之间的控制关系,得到非受控变异语句对应的变异体,即为约简后变异体,明显减少了变异体数量[40].
本文基于弱变异测试准则,研究变异体约简方法,以提高变异测试用例的生成效率.本文利用Papadakis等人[22]的弱变异测试转化思想,将变异测试问题转化为分支覆盖测试问题进行求解.利用统计分析方法,检测变异分支之间的占优关系,得到一个非被占优的分支集,该集合对应的变异体,即为约简后的变异体.覆盖非被占优分支集的测试用例,也能够以弱变异测试准则杀死所有变异体.
2 本文所提方法本节详细阐述基于统计占优分析进行变异体约简的方法,该方法首先根据弱变异测试转化思想,将变异体转化为变异分支,并集成到原程序中,形成新的被测程序;然后建立统计占优分析模型,自动检测新的被测程序中变异分支之间的占优关系;最后,约简被占优分支对应的变异体.本节主要从以上3个方面进行阐述,并给出相应的案例分析.
2.1 弱变异测试转化对于被测程序P,以语句为单位,记某变异点为s,对s实施某变异算子后,产生的变异语句记为s¢,对应的变异体为m.根据弱变异测试准则,如果测试数据t能够杀死m,那么t必须能够执行到s¢,并且执行s¢后状态发生改变,即s!=s¢.如果将s!=s¢作为条件构建分支语句b,那么覆盖b真分支的测试数据能够以弱变异测试准则杀死变异体m.这样,就将杀死m的变异测试问题转化为覆盖b的真分支的分支覆盖测试问题.
所构造的分支语句b仅反映杀死变异体的必要性条件,并且与变异体m一一对应,称b为变异分支.变异分支在程序P中,不执行任何实质性操作,因此不会对该程序的执行产生任何影响,而且b与变异前语句s具有相同的可达性.此外,b是由变异前后语句s和s¢通过“!=”组合而成的,因此容易构建.
对程序P实施所有变异算子,产生变异体集M,包含变异体m1,m2,…,m|M|,其中,|M|为M的元素个数,即变异体个数.相应地,所构造的变异分支集为B,包含变异分支b1,b2,…,b|B|,与变异体一一对应,|B|=|M|.将这些变异分支依次插入到程序P的相应位置,得到新的转化后程序P¢.至此,所有变异体都以变异分支的形式集成到程序P¢中.
图1为三角形分类程序Triangle[30]的部分代码,利用MuClipse变异测试工具[41],对第5行~第13行所对应的代码段实施全部的15类方法级(traditional-level)变异算子[42],共生成78个变异体,见表1.其中,代码第5行~第7行产生26个变异体,组合后得到26个变异分支,其分支条件见表2.图2为融入变异分支后,新程序的控制流程图.
|
图1 Triangle的部分代码 Fig.1 Part of Triangle program |
|
表1 实施的变异算子及产生的变异体 Table 1 Implemented mutation operators and generated mutants |
|
|
表2 构建的变异分支条件 Table 2 Predictions of constructed mutant branches |
|
图2 新程序的控制流程图 Fig.2 Control flow graph of the new program |
表2中,实施AOIS变异算子后得到的分支条件,其执行对原程序构成影响.例如,对if (a==b)的变量a实施AOIS变异算子,得到++a,--a,a++和a--(对应表2中的分支条件1、条件2、条件5和条件6),将++a和--a替换为(a+1)和(a-1).但是,a++和a--的影响具有滞后性,即,对后续引用变量a的语句产生影响,因此,如果确定后续存在对该变量引用的语句,可以通过变量替换的方式,在后续语句中植入变异分支,或者直接将a++和a--转化为(a+1)和(a-1),本文采用后者.
形成新的被测程序P¢后,杀死P所有变异体的变异测试问题就转化为分支测试问题,即,以B为目标集的分支覆盖测试问题.毋庸置疑,该转化方法能够进一步降低弱变异测试代价.但是为数众多的变异体,导致转化后新程序P¢中融入大量的额外分支,显著增加了转化后被测程序的复杂度,从而降低了转化后问题的求解效率.
图1中实施变异的代码段,其有效行数为9,分支语句个数为3,而新程序P¢中将增加78个变异分支,如果每个变异分支包含3行有效代码,那么,P¢的代码行将增加78x3¸9=26倍.这说明采用适当的方法减少所需覆盖的变异分支数量,从而显著简化转化后的新程序,非常有助于进一步提高变异测试效率.
2.2 统计占优分析P¢融入大量的变异分支,显著增加了新程序的复杂度.但是这些变异分支之间并非完全独立,它们之间存在某种相关性.例如表2中的分支条件19“if ((a==b)!=(~a==b))”,其真分支执行,分支条件5、分支条件6、分支条件14、分支条件15等对应的真分支必然执行;再如,分支条件23为“真”,分支条件22和分支条件24必然为“真”.这说明,P¢的变异分支之间存在某种必然联系.
如果能够判定进而充分利用这些相关性,将有助于减少所需覆盖的变异分支,从而降低所需杀死的变异体数量,达到约简变异体的目的.上述变异分支之间的关系称为占优关系,下面给出变异分支占优关系的定义.
定义1(变异分支之间的占优关系). P¢为转化后的新程序,bi,bjÎB为P¢的两个变异分支,以任一测试数据执行P¢,如果bi的真分支被执行,bj的真分支也必然被执行,那么称bi占优bj,记为bi$\succ$bj;称bi为占优分支,bj为被占优分支.
对于转化后的新程序P¢,占优关系描述变异分支之间的一种必然相关性,这种相关性可以通过统计分析的方法获得.为此,定义随机变量,并根据变异分支的覆盖情况计算这些随机变量之间的条件概率.对于被测程序P¢,其取值域为D,bi,bjÎB是P¢的2个变异分支,ωÎD为测试数据,定义随机变量X和Y.
\[X=\left\{ \begin{array}{*{35}{l}}
1,\text{ }covered(\omega ,{{b}_{i}}) \\
0,\text{ }\neg covered(\omega ,{{b}_{i}}) \\
\end{array} \right.\]
(1)
\[Y=\left\{ \begin{array}{*{35}{l}}
1,\text{ }covered(\omega ,{{b}_{j}}) \\
0,\text{ }\neg covered(\omega ,{{b}_{j}}) \\
\end{array} \right.\]
(2)
| \[Pro\{Y=y|X=0\}=\left\{ \begin{array}{*{35}{l}} 1-p,\text{ }Y=0 \\ p,\text{ }Y=1 \\ \end{array} \right.\] | (3) |
| \[Pro\{Y=y|X=1\}=\left\{ \begin{array}{*{35}{l}} 1-q,\text{ }Y=0 \\ q,\text{ }Y=1 \\ \end{array} \right.\] | (4) |
公式(4)表示当X=1时,Y=1或Y=0的概率,即:表示变异分支bi执行,bj执行或者不执行的概率.
定理1. q=1时,bi$\succ$bj.
证明:对于公式(4),当q=1时,Pro{Y=1|X=1}=1,这说明在X=1的条件下,Y=1是必然事件,即:当bi的真分支被覆盖时,bj的真分支必然被覆盖.因此,bi$\succ$bj.
对于bi和bj,只有q值确定,才能判定bi是否占优bj.对于q的取值,既不能依靠经验判断,更不能通过穷举定义域D上的所有取值得到,这将严重影响变异测试的自动化程度.因此,本文对q的取值进行极大似然估计.在D上随机取N组测试数据ω1,ω2,…,ωN,并以这些测试数据考察bi和bj的覆盖情况,那么得到容量为N的样本(X1,Y1),(X2,Y2),…,(XN,YN),其对应的值为(x1,y1),(x2,y2),…,(xN,yN),概率分布函数为
| \[Pro\left\{ Y=y|X=x \right\}={{q}^{xy}}{{(1-q)}^{x}}{{^{(1}}^{-y)}}{{p}^{(1-x)y}}{{(1-p)}^{(1}}^{-x)(1-y)},x,y=0,1\] | (5) |
样本的极大似然函数为
| \[L(p,q;{{x}_{1}},{{x}_{2}},...,{{x}_{N}})=\prod\limits_{i=1}^{N}{{{q}^{{{x}_{i}}{{y}_{i}}}}{{(1-q)}^{{{x}_{i}}(1-{{y}_{i}})}}{{p}^{(1-{{x}_{i}}){{y}_{i}}}}{{(1-p)}^{(1-{{x}_{i}})(1-{{y}_{i}})}}}\] | (6) |
为了求q的极大似然估计值,令:
| \[\frac{\partial (\ln (L(p,q;{{x}_{1}},{{x}_{2}},...,{{x}_{N}})))}{\partial q}=0\] | (7) |
得到:
| \[\hat{q}=\frac{\sum\limits_{i=1}^{N}{{{x}_{i}}{{y}_{i}}}}{\sum\limits_{i=1}^{N}{{{x}_{i}}}}\] | (8) |
利用上述方法,在程序P的取值域D上随机选取N个测试数据,执行并记录每个测试数据对P¢变异分支的覆盖情况.Pro{Y=1|X=1}=q,通过对随机变量X和Y的取值,计算参数q的极大似然估计值$\hat{q}.$根据定理1,当$\hat{q}=1$时,bi和bj的真分支之间存在占优关系.需要说明的是:有一类特殊的占优关系bi$\succ$bj且bj$\succ$bi,对于该类占优关系,本文只取bi$\succ$bj或bj$\succ$bi的其中之一.
通过上述统计分析方法,能够自动检测变异分支之间的占优关系.根据这些占优关系确定需要约简的变异体,是下一小节要解决的问题.
2.3 变异体自动约简对于bi和bj,如果bi$\succ$bj,那么根据弱变异测试准则,杀死mi的测试数据一定能够杀死mj.因此,mj可以被约简,即:所有被占优变异分支,其对应的变异体就是要约简的变异体;而非被占优分支对应的变异体,则是约简后的变异体.
定义2(非被占优变异分支集). 考虑P¢的变异分支集B,对于变异分支biÎB,如果不存在任何bjÎB,bj¹bi使得bj$\succ$bi成立,那么称bi为非被占优分支.所有非被占优分支构成的集合称为非被占优分支集,记为Bnd.
定理2. Bnd所对应的变异体,是约简后的变异体.
证明:采用反证法.假设Bnd对应的变异体不是约简后的变异体,那么至少存在一个可被约简的变异体,对应的变异分支为bÎBnd,即,b是被占优分支.这与Bnd是“非被占优分支集”矛盾.
以N个测试数据ω1,ω2,…,ωN作为输入,执行转化后程序P¢,并记录各测试数据对变异分支的覆盖情况.生成P¢的执行矩阵Exe=eij,见表3.该过程相当于采样,如算法1所示.
|
|
表3 变异分支的执行矩阵 Table 3 Execution matrix of mutant braches |
算法1. 执行矩阵的生成.
Input:测试数据ω1,ω2,…,ωNÎD;
Output:变异分支集B的执行矩阵Exe.
初始化执行矩阵Exe=eij,设置eij=0,i=1,2,…,N,j=1,2,…,|B|
函数covered(wi,bj),当测试数据wi能够覆盖变异分支bj时,返回布尔值true
for (i=1; i≤N; i++) {
for (j=1; j≤|B|; j++) {
if (covered(wi,bj)) {
eij=1
}
}
}
Exe记录各变异分支的覆盖情况,eij=1表示测试数据wi能够覆盖bj;否则,不能覆盖bj.如果所有测试数据都不能覆盖某变异分支,则需要进一步判断该变异分支是否可满足.如果对于任何测试数据都不能执行该变异真分支,如表2中的变异分支条件13,这在语义上等同于等价变异体,因此应排除这类变异分支.
对于执行矩阵Exe,可以利用统计占优分析方法,检测变异分支之间的占优关系,统计结果用占优矩阵Dom=dij,i,j=1,2,…,|B|存储.根据公式(8)和定理1,$\hat{q}={\sum\limits_{k=1}^{N}{({{e}_{ki}}\cdot {{e}_{kj}})}}/{\sum\limits_{k=1}^{N}{{{e}_{ki}}}}\;,$如果$\hat{q}=1,$那么dij=1;否则,dij=0.具体过程如算法2所示.
算法2. 生成变异体的占优矩阵.
Input:变异分支集B的执行矩阵Exe;
Output:变异分支集B的占优矩阵Dom.
初始化占优矩阵Dom=dij,设置dij=0,i,j=1,2,…,|B|
N为测试数据数量,也是样本容量
for (i=1; i≤|B|; i++) {
sumx=0
for (k=1; k≤N; k++) {
sumx+=eki
}
for (j=1; j≤|B|; j++) {
if (j==i)
continue
sumxy=0
sumy=0
for (k=1; k≤N; k++) {
sumxy+=eki×ekj
sumy+=ekj
}
if (sumxy!=0) {
if (sumxy==sumx) {
if (dji!=1)
dij=1
} else {
if (sumxy==sumy) {
if (dij!=1)
dji=1
}
}
}
}
}
算法2执行后,其输出结果为占优矩阵Dom,见表4.本质上,Dom存储的是以B的各变异分支为顶点,所包含的占优关系为边构成的有向图G(B)=(V(B),E(B)).dij=1表明,存在边＜vi,vj＞ñÎE(B),其中,vi,vjÎV(B),与B中的变异分支bi和bj相对应.
|
|
表4 变异分支的占优矩阵 Table 4 Dominance matrix of mutant branches |
在G(B)中,顶点vi的出度$outDegree({{v}_{i}})=\sum{{{d}_{i*}}}$表示bi占优的变异分支个数,vi的入度$inDegree({{v}_{i}})=\sum{{{d}_{*i}}}$表示占优bi的变异分支个数.因此,根据表4的输出结果,入度为0的顶点对应的变异分支是非被占优分支;所有非被占优分支构成的集合就是非被占优集Bnd.
2.4 案例分析对于图1中代码所产生的78个变异分支,采用本文的统计占优分析方法随机生成测试数据,对转化后的程序P¢实施分支覆盖测试;且在测试过程中,生成P¢的变异分支执行矩阵Exe.如表5所示,采用11个测试数据执行转化后的程序P¢(对应的样本容量N=11),得到对78个变异分支的覆盖信息.
|
|
表5 执行矩阵 Table 5 Execution matrix |
表5中,分支条件13(if ((trian+1)!=(-trian+1)),见表2)没有被覆盖.进一步分析发现,变量trian的初始值为0,因此,分支条件13是不可满足分支,对应的变体为等价变异体.对转化后的77个可满足分支,利用本文方法进行统计占优分析,得到Bnd={23,25,28,30,47,54,56},对应的变异分支条件为
if ((a==b)!=(a≤b));
if ((a==b)!=(a≥b));
if ((a==c)!=(a≤c));
if ((a==c)!=(a≥c));
if ((trian+2)!=(-trian+2));
if ((b==c)!=(b≤c));
if ((b==c)!=(b≥c)).
这些变异分支对应的变异体,即为约简后的变异体.将这7个变异分支集成到原程序P中,得到新的约简后测试程序P².事实上,覆盖上述7个变异分支的测试数据可以覆盖77个可满足变异分支.
如果仅考虑表2中的26个分支条件,利用本文方法得到Bnd={9,23,25}(见表2),对应的分支条件为
if (trian+1)!=(trian+1+1);
if ((a==b)!=(a≤b));
if ((a==b)!=(a≥b)).
而覆盖这3个分支的测试数据,可以覆盖表2中的所有25个可满足分支.对图1中代码第5行~第13行和第5行~第7行的分析结果表明:以原程序的语句段为单位,采用本文方法对转化后的变异分支进行占优分析,结果是有效的.
从以上案例可知,程序整体的分析结果可能不等于各部分结果的并集.这是因为该并集可能存在少量冗余,甚至得到不同的非被占优分支.但是覆盖该并集的测试数据,也能够覆盖原来的所有变异真分支.因此,对于复杂程序,可以进行分组统计分析.
表5中的样本值来自容量N=11的样本.分析还发现,N偏大将容易产生不必要的开销.例如对表2中的26个分支,仅需7个测试数据(相对应的,N=7)即可得到Bnd={9,23,25}.测试数据太少(样本容量太小)容易产生误判,即:实际不存在占优关系,误判成占优关系.这种误判一方面导致更多的变异体被约简;另一方面,约简后生成的测试用例集,其缺陷检测能力下降(变异得分减少).例如,对于77个可满足变异分支,当采用更少的测试数据进行分析时,尽管得到的Bnd更小,但是约简后生成的测试用例不能够覆盖所有的变异分支.
上述案例的分析结果初步说明本文方法是可行的,但仍需进一步进行实验,以验证所提方法的有效性.
3 实验与分析本节通过实验进一步检验所提方法的有效性.首先,给出实验需验证的问题;其次,介绍实验所用的程序;再次,建立实验模型,即,本文的变异体约简原型系统,并描述实验的基本过程;最后,给出实验结果和分析.
3.1 需要解决的问题本文的目的是通过减少变异体数量,进一步提高测试用例的生成效率.为此,需验证的问题如下:
(1) 本文方法能否显著减少变异体数量?这将通过约简前后的变异体数量进行比较,用被约简的变异体数量占所有非等价变异体数量的百分比,即,约简率进行比较;
(2) 利用本文方法进行变异体约简,是否能够提高变异测试用例的生成效率?这需要对转化后程序P¢以及约简后的新程序P²分别执行测试用例生成实验,并比较所花费的时间;
(3) 通过本文方法约简后,所生成的测试用例是否有效?这需要对约简前后的测试程序分别生成测试用例,执行分支测试和强变异测试,并比较变异分支覆盖情况(弱变异测试)和强变异得分情况;
(4) 约简后的变异体所生成的测试用例,其缺陷能力有何变化?这需要对约简前后所生成的测试用例分别执行强变异测试,并考察所用的测试用例数量以及杀死的变异体数量;
(5) 样本容量的大小是否影响本文方法的有效性?鉴于样本容量对于本文方法的重要性,考察不同容量的样本值对统计分析结果的影响.
3.2 实验程序选取8个程序,见表6,进一步验证所提方法的有效性,其中,J1,J2,J3和J5选自文献[22]的实验程序;J4是文献[30]的实验程序;J6,J7和J8来自http://commoms.apache.org,为文献[2]的部分变异测试程序.实验所用的8个程序均采用Java语言编写,其中,J1~J5为使用频率很高的变异测试基准程序,J6~J8则是工业应用程序.
|
|
表6 实验程序信息 Table 6 Information of tested programs |
采用Metrics统计各实验程序的代码行数和方法数[43],并利用MuClipse生成变异体.如表6所列,8个实验程序共包含811行有效代码、25种方法.其中,被测方法14种(绝大部分没有被测试的方法是形如“getXXX()”的简单方法).所有实验程序共生成2 232个变异体,其中,可测试2 055个;而对于177个不可测试变异体,在实验中被舍弃.这些不可测试变异体均为错误变异体,如对final变量实施AOIS变异算子所产生的变异体等.
3.3 实验过程实验基于Microsoft Window XP SP3操作系统和Eclipse 3.4集成开发环境.首先,采用MuClipse生成变异体,并通过对日志文件mutation_log的解析,自动生成变异分支集B.将所有变异分支插入到原程序P的相应位置,得到转化后的被测程序P¢;对P¢的变异分支进行统计占优分析,得到约简后的变异分支集Bnd,并插入到原程序P的相应位置,得到简化后的被测程序P².实验过程如图3所示.
|
图3 本文方法原型系统 Fig.3 Prototype system of the proposed method |
通过Bnd统计约简后变异体的数量,计算本文方法的变异体约简率.对约简前后的被测程序P¢和P²分别执行分支测试(branch testing),并生成覆盖各自变异分支集的测试用例集T ¢和T ²;同时,统计生成测试用例所需的时间和变异分支覆盖率,并对T ¢和T ²分别执行强变异测试,统计变异得分.实验中生成的单个测试用例,以JUnit的“assertXXX();”形式给出[44],若干测试用例构成一种测试方法.
3.4 实验结果与分析 3.4.1 变异体约简通过变异体约简率的计算,评价本文方法的有效性.约简率等于被约减的变异体数量占所有非等价变异体数量的百分比.构造变异分支的同时,判定和统计不可满足分支的数量以及等价变异体的数量,并采用本文方法进行变异体约简,结果见
|
|
表7 本文方法的约简率 Table 7 Reduction rates of the proposed method |
在表7所列的8个实验程序中,J6获得了最大的约简率,为94.52%((158-12-8)/(158-12)),仅保留8个变异分支.最小约简率来自J1,为85.57%.所有的8个测试程序共生成2 055个变异分支(45个不可满足),其中,等价变异体275个;通过统计占优分析,得到非被占优变异分支149个,所对应的变异体即为约简后的变异体;约简变异体1 631个,平均约简率为91.19%.这说明,本文方法能够约简90%左右的变异体,因此,本文所提方法能够显著减少变异体数量.
3.4.2 测试用例生成的效率对约简前后的测试程序分别执行分支测试,生成覆盖各变异分支的测试用例.本文对约简前后测试程序P¢和P²采用随机方法生成测试用例.测试用例生成时间以毫秒(ms)为单位,并通过速度比(约简前后所用时间的比值)来评价变异体约简前后测试数据生成效率的变化情况.结果见表8.
|
|
表8 约简前后测试用例生成成本 Table 8 Cost of generating test cases before and after mutant reduction |
对于实验的8个程序,约简前生成156.6个测试用例,用时54 606.250 0ms;约简后生成测试用例110.9个,用时5 942.915 1ms.表8中:约简后的8个程序,生成测试用例的速度是约简前的10.88倍;而单个测试用例生成速度是约简前的7.77倍.其中,J7速度比最高,达到16.52;J3获得速度比最小,为5.08.所获得速度比的大小与程序本身的复杂程度有关.同样,J3的单个测试用例生成速度比也最小,J7的单个测试用例生成速度比则最大.
无论从生成测试用例集还是从生成单个测试用例的角度,实验结果均表明,约简后测试用例生成速度都得到显著提高.这说明,本文方法能够明显提高变异测试用例生成效率.测试用例生成效率的提高,主要得益于所需覆盖的变异分支数量的显著减少.
3.4.3 测试用例的有效性对约简前后的所有实验程序,分别生成覆盖对应变异分支集的测试用例,并利用这些测试用例执行强变异测试.如表9所列,约简前生成的测试用例158.2个,覆盖2 006个变异分支,平均变异分支覆盖率为99.79%,其中,J7的分支覆盖率为98.34%,其他则实现变异分支全覆盖.约简前生成的测试用例能够杀死1 747.0个变异体,得到98.68%的平均变异得分,其中,J1,J2,J3和J6的变异得分均为100%;J7的变异得分最小,为96.46%.
|
|
表9 约简前生成测试用例 Table 9 Generated test cases before mutant reduction |
从表10可知,约简后的8个测试程序共生成112.1个测试用例,覆盖2 004个变异分支,取得99.63%的变异分支覆盖率,其中,6个程序达到全覆盖.约简后,所生成的测试用例能够杀死变异体1 737.1个,平均变异得分为98.20%.其中,J1,J3和J6得到100%的变异得分;J7的变异得分最低,为95.89%.
|
|
表10 约简后生成测试用例 Table 10 Generated test cases after mutant reduction |
对比表9和表10,变异体约简前后的各程序,变异分支覆盖率均超过99%,变异得分则超过95%.采用本文方法约简后,所得分支覆盖率和变异得分略有下降,分别降低了0.16%和0.48%.同时,所生成的测试用例数量减少了46.1个(减少29.14%).因此,本文方法在维持较高的变异充分度的前提下,不仅能够显著减少变异体的数量,还能有效减少生成的变异测试用例数量.
3.4.4 缺陷检测能力为了进一步分析变异体约简前后,测试用例杀死变异体的能力,即缺陷检测能力,分别设置50%,70%,90%和Top共4个采样点,考察变异体约简前后,达到采样点对应的变异得分时所需生成的测试用例数量.其中,Top是指所达到的最高变异得分(约简前的见表9,约简后的见表10).结果见表11.
|
|
表11 达到特定变异得分所需测试用例数量 Table 11 Number of test cases needed for different mutation scores |
表11表明,约简后达到指定变异得分,所需生成测试用例的数量明显小于约简前.例如:J4在约简前达到50%的变异得分,需要生成11.0个测试用例;达到70%需要16.3个测试用例;达到90%需要25.5个;而达到Top (98.14%,见表9)则需生成33.6个测试用例.利用本文方法约简变异体后,达到上述的变异得分则分别需要7.6,11.8,17.4和21.9个测试用例.8个实验程序中:J6在约简前后均只需1.0个测试用例就可达到90%的变异得分;而达到Top(100%),则分别需要6.4和4.6个测试用例.
表9和表10表明:约简后的测试程序生成的测试用例数量明显减少.表11进一步验证,达到指定变异得分时,约简后的测试程序所需测试用例的数量更少.
图4为约简后生成的测试用例数量占约简前生成测试用例数量的百分比.可以看出:对于所有测试程序(除J6之外),在达到50%,70%,以及90%的变异得分时,生成测试数据的数量占约简前的60%~90%;当变异得分达到Top时,生成测试用例仅为约简前的55%~85%.
|
图4 所需测试用例数量的比较 Fig.4 Comparison of number of needed test cases |
图5表明:对于每个约简后的测试程序生成的单个测试用例,其缺陷检测能力比约简前提升超过20%,其中J2提升最多,超过70%;8个实验程序平均提升超过35%.
|
图5 单个测试用例缺陷检测能力的提升 Fig.5 Improved fault detection capability of per test case |
样本容量在数值上等于统计分析时所用测试数据的数量,容量的大小影响到变异体约简的有效性.上述实验表明:本文方法能够大幅度减少变异体数量,从而有效提高测试用例生成的效率.鉴于本文变异体约简的方法与样本容量密切相关,因此有必要考察样本容量对本文方法有效性的影响.为此,对不同容量的样本值统计约简后变异分支(变异体)数量以及约简后所生成测试用例的变异分支覆盖率和变异得分.见表12.
|
|
表12 样本容量的影响 Table 12 Influence of sample size |
由表12可知:对于8个被测程序,采用本文方法,当样本容量较小时,约简后的变异体数量更少.相应地,约简后生成的测试用例取得的变异分支覆盖率和变异得分也比较差.这说明,当样本容量不充分时,采用本文方法容易产生误判,即,将不存在的占优关系误判为占优关系.尽管这种误判使得约简率有所提高,但却降低了本文方法的有效性.
表12中:随着样本容量的增加,约简后生成的测试用例,其变异分支覆盖率和变异得分趋于增长,并达到最大值.这说明,本文方法能够有效地判定占优关系,从而得到非被占优变异分支.实验过程中还发现:样本容量达到一定值后(见表12中各实验程序,取得最大变异分支覆盖率和最大变异得分时对应的样本容量),即使样本容量继续增加,对应的约简后变异分支数量、变异分支覆盖率和变异得分基本趋于稳定.
通过上述实验结果与分析可以得出如下结论:采用本文方法,能够大幅度约简变异体,维持很高的变异得分,并显著提高变异测试的效率;而且约简后生成测试用例的数量更少,在保持测试用例集整体缺陷检测能力的前提下,单个测试用例的缺陷检测能力更强.此外,尽管样本容量影响本文方法的有效性,但却容易确定保证本文方法有效性的样本容量.
4 总 结为数众多的变异体是影响变异测试效率的主要因素,弱变异测试或基于弱变异转化的测试方法同样受制于庞大的变异体数量,这表明其测试效率仍有很大的提升空间.因此,采用合适的方法有效减少生成的变异体数量,是提高变异测试效率的重要途径.然而迄今为止,仍缺乏高效的变异体约简方法.
本文基于弱变异测试准则研究变异体约简问题,以进一步提高变异测试效率.本文的主要贡献有:
(1) 提出利用统计占优分析的方法,高效地约简变异体.该方法通过弱变异测试转化,将变异体转化为变异分支,集成到原程序P中,得到新程序P¢;然后建立统计占优分析模型,分析P¢中变异分支间的占优关系,得到非被占优分支集,并集成到P中,得到约简后程序P²;
(2) 根据本文所提方法建立变异体约简原型系统,并应用于8个程序的实验.结果表明:本文方法能够在维持较高变异充分度的前提下大幅度减少变异体数量,提高变异测试效率,增强单个测试用例的缺陷检测能力.
此外,本文还考察了样本容量对本文方法有效性的影响.
本文所提方法是通过对传统变异算子的分析得出的,而实验也同样采用传统变异算子.目前广泛应用的面向对象语言,在产生大量传统变异体的同时也生成很多的类级变异体.因此作为后续工作,本文方法将被用于类级变异体的约简,以进一步检验所提方法的有效性.此外,根据本文思想开发的原型系统仍需进一步加以完善,从而适应更复杂的工业程序,以推进变异测试自动化的程度.
致谢 感谢各位审稿专家以及本刊编辑的辛勤工作.
| [1] | Chen JF, Lu YS, Xie XD. Research on software fault injection testing. Ruan Jian Xue Bao/Journal of Software, 2009,20(6): 1425-1443 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3526.htm |
| [2] | Fraser G, Zeller A. Mutation-Driven generation of unit tests and oracles. IEEE Trans. on Software Engineering, 2012,38(2): 278-292. |
| [3] | Zhu H, Hall PAV, May JHR. Software unit test coverage and adequacy. ACM Computing Survey, 1997,29(4):366-427. |
| [4] | Andrews JH, Briand LC, Labiche Y. Is mutation an appropriate tool for testing experiments. In: Roman GC, Griswold WG, Nuseibeh B, eds. Proc. of the 27th Int'l Conf. on Software Engineering. Washington: IEEE, 2005. 402-411. |
| [5] | Offutt AJ, Pan J, Tewary K, Zhang T. An experimental evaluation of data flow and mutation testing. Software: Practice and Experience, 1996,26(2):165-176. |
| [6] | DeMillo RA, Mathur AP. On the use of software artifacts to evaluate the effectiveness of mutation analysis in detecting errors in production software. Technical Report, SERC-TR-92-P, Lafayette: Purdue University, 1992. 1-32. |
| [7] | Do H, Rothermel G. A controlled experiment assessing test case prioritization techniques via mutation faults. In: Cantarella JD, ed. Proc. of the 21st Int'l Conf. on Software Maintenance. Washington: IEEE, 2005. 411-420. |
| [8] | Do H, Rothermel G. On the use of mutation faults in empirical assessments of test case prioritization techniques. IEEE Trans. on Software Engineering, 2006,32(9):733-752. |
| [9] | Andrews JH, Briand LC, Labiche Y, Namin AS. Using mutation analysis for assessing and comparing testing coverage criteria. IEEE Trans. on Software Engineering, 2006,32(8):608-604. |
| [10] | Inozemtseva L, Holmes R. Coverage is not strongly correlated with test suite effectiveness. In: Jalote P, Briand L, Hoek A, eds. Proc. of the 36th Int'l Conf. on Software Engineering. New York: ACM Press, 2014. 435-445. |
| [11] | Cai X, Lyu MR. The effect of code coverage on fault detection under different testing profiles. ACM SIGSOFT Software Engineering Notes, 2005,30(4):1-7. |
| [12] | Frankl PG, Weiss SN, Hu C. All-Uses vs mutation testing: an experimental comparison of effectiveness. Journal of Systems and Software, 1997,38(3):235-253. |
| [13] | Namin AS, Andrews JH. The influence of size and coverage on test suite effectiveness. In: Rothermel G, Dillon LK, eds. Proc. of the 8th Int'l Symp. on Software Testing and Analysis. New York: ACM Press, 2009. 57-68. |
| [14] | DeMillo RA, Lipton RJ, Sayward FG. Hints on test data selection: Help for the practicing programmer. Computer, 1978,11(4): 34-41. |
| [15] | Offutt AJ. Investigations of the software testing coupling effect. ACM Trans. on Software Engineering and Methodology, 1992,1(1): 3-18. |
| [16] | Offut AJ, Lee SD. An empirical evaluation of weak mutation. IEEE Trans. on Software Engineering, 1994,20(5):377-344. |
| [17] | Kapoor K. Formal analysis of coupling hypothesis for logical faults. Innovations in Systems and Software Engineering, 2006,2(2): 80-87. |
| [18] | Wah KSHT. An analysis of the coupling effect I: Single test data. Science of Computer Programming, 2003,48(2-3):119-161. |
| [19] | Jia Y, Harman M. Analysis and survey of the development mutation testing. IEEE Trans. on Software and Engineering, 2011,37(5): 649-678. |
| [20] | Lammermann F, Baresel A, Wegener J. Evaluating evolutionary testability for structure-oriented testing with software measurements. Applied Software Computing, 2008,8(2):1018-1028. |
| [21] | Domínguez-Jiménez JJ, Estero-Botaro A, García-Domínguez A, Medina-Bulo I. Evolutionary mutation testing. Information and Software Technology, 2011,53(10):1108-1123. |
| [22] | Papadakis M, Malevris N. Automatically performing weak mutation with the aid of symbolic execution, concolic testing and search-based testing. Software Quality Journal, 2011,19(4):691-723. |
| [23] | Acree AT. On mutation [Ph.D. Thesis]. Atlanta: Georgia Institute of Technology, 1980. |
| [24] | Budd TA. Mutation analysis of program test data [Ph.D. Thesis]. New Haven: Yale University, 1980. |
| [25] | Mathur AP, Wong WE. An empirical comparison of mutation and data flow based test adequacy criteria. Software Testing, Verification and Reliability, 1994,4(1):9-31. |
| [26] | Mathur AP. Performance, effectiveness, and reliability issues in software testing. In: Ladd D, ed. Proc. of the 15th Computer Software and Applications Conf. Washington: IEEE, 1991. 604-605. |
| [27] | Offutt AJ, Rothermel G, Zapf C. An experimental evaluation of selective mutation. In: Basili VR, DeMillo RA, Katayama T, eds. Proc. of the 15th Int'l Conf. on Software Engineering. Washington: IEEE, 1993. 100-107. |
| [28] | Offutt AJ, Lee A, Rothermel G, Untch RH, Zapf C. An experimental determination of sufficient mutant operators. ACM Trans. on Software Engineering and Methodology, 1996,5(2):99-118. |
| [29] | Jia Y, Harman M. Higher order mutation testing. Information and Software Technology, 2009,51:1379-1393. |
| [30] | Jia Y, Harman M. Constructing subtle faults using higher order mutation testing. In: Cordy JR, Zhang L, eds. Proc. of the 8th Int'l Working Conf. on Source Code Analysis and Manipulation. Washington: IEEE Computer Society, 2008. 249-258. |
| [31] | Polo M, Piattini M, Garcia-Rodriguez I. Decreasing the cost of mutation testing with second-order mutants. Software Testing, Verification and Reliability, 2009,19:111-131. |
| [32] | DeMillo RA, Offutt AJ. Constraint-Based automatic test data generation. IEEE Trans. on Software Engineering, 1991,17(9): 900-910. |
| [33] | Howden WE. Weak mutation testing and completeness of test sets. IEEE Trans. on Software Engineering, 1982,8(4):371-379. |
| [34] | Horgan JR, Mathur AP. Weak mutation is probably strong mutation. Technical Report, SERC-TR-83-P, Lafayette: Purdue University, 1990. |
| [35] | DeMillo RA, Offutt AJ. Experimental results from an automatic test case generator. ACM Trans. on Software Engineering and Methodology, 1993,2(2):109-127. |
| [36] | Papadakis M, Malevris N. Mutation based test case generation via a path selection strategy. Information and Software Technology, 2012,54(9):915-312. |
| [37] | Ghiduk AS, Girgis MR. Using genetic algorithms and dominance concepts for generating reduced test data. Informatica, 2010,34(3): 377-385. |
| [38] | Gong D, Yao X. Automatic detection of infeasible paths in software testing. IET Software, 2010,4(5):361-370. |
| [39] | Shan JH, Gao YF, Liu MH, Liu JH, Zhang L, Sun JS. A new approach to automated test data generation in mutation testing. Chinese Journal of Computers, 2008,31(6):1025-1034 (in Chinese with English abstract). |
| [40] | Xu SY. A method of simplifying complexity of mutation testing. Chinese Journal of Shanghai University (Natural Science Edition), 2007,13(5):524-531 (in Chinese with English abstract). |
| [41] | Segura S, Hierons RM, Benavides D, Ruiz-Cortés A. Automated metamorphic testing on the analyses of feature models. Information and Software Technology, 2011,53:245-258. |
| [42] | Ma YS, Offutt J. Description of method-level mutation operators for Java. 2005. http://ise.gmu.edu/-ofut/mujava/mutopsMethod. pdf |
| [43] | http://sourceforge.net/projects/metrics/ |
| [44] | http://sourceforge.net/projects/junit/ |
| [45] | 陈锦富,卢炎生,谢晓东.软件错误注入测试技术研究.软件学报,2009,20(6):1425-1443. http://www.jos.org.cn/1000-9825/3526. htm |
| [46] | 单锦辉,高友峰,刘明浩,刘江红,张路,孙家骕.一种新的变异测试数据生产方法.计算机学报,2008,31(6):1025-1034. |
| [47] | 徐拾义.降低软件变异测试复杂性的新方法.上海大学学报(自然科学版),2007,13(5):524-531. |