杜畇岐 潘 娅 甘 佳

(1. 西南科技大学计算机科学与技术学院 四川绵阳 621010；2. 西南科技大学计算机应用技术研究所 四川绵阳 621010)

变异测试[1](Mutation Testing)是一种基于缺陷的软件测试方法，基本原理是使用变异算子(Mutants Operator)对被测程序做微小的合乎语法的变动，改变过后得到的程序被称为变异体(Mutants)。在产生变异体后，分别在原程序和变异体上运行测试用例，如果二者的结果相同，则表示该变异体是存活的(Alive)，如果二者的结果不同，则表示该变异体是被杀死的(Killed)。如果一个变异体在语义上和原程序保持一致，那么它将无法被杀死，这一类变异体称作等价变异体。

变异测试最终通过输出变异得分来评价测试用例集的缺陷检测能力，它是被杀死的变异体数量与变异体总数的比值，这个比值越高，代表着测试用例的缺陷检测能力越强。可以看出变异得分Score的取值是在0～1之间的，变异测试的最终目标就是希望Score能达到1，即测试用例集能杀死所有的非等价变异体。

变异测试总时间是变异体生成时间和变异体执行时间之和。其中生成时间受所选工具的影响，而执行时间的评价指标是每秒生成的变异体数量，减少生成和执行变异体数量的方法通常遵循以下3种策略之一： (1)“更少”：寻求以最少的信息损失运行更少的变异体; (2)“更聪明”：寻求在多台机器上并行执行； (3)“更快”：寻求一种方法尽可能快地生成或运行每个变异体。本文主要针对第一种方法，寻找一个变异算子的子集来替换原变异算子全集。

Offutt和King在已有研究工作的基础上，于1987年针对Fortran77首次定义了22种变异算子，这些变异算子的简称和描述如表1所示。这22种变异算子的设定为随后其他编程语言变异算子的设定提供了重要的指导依据。

表1 F77定义的常用22种变异算子Table 1 22 commonly used mutation operators defined by F77

从学术研究的角度来看，变异测试已经是基于缺陷的成熟的测试技术，但是应用到工业时存在一个技术难点，即变异测试产生的变异体较多，开销较大。例如，在Delamaro等[2]的实验中，针对一个简单的程序tcas(仅有137行非注释代码)，应用108个变异算子生成了4 937个变异体。而在Kintis M等[3]的实验中，针对6个程序Commons-Math，Commons-Lang，Pamvotis，XStream，Triangle，Bisect，使用了Major[4]的8种变异算子、Mujava[5]的15种变异算子、PIT[6]的23种变异算子，分别产生了808，1 854，3 169个变异体。因此，大量变异体的生成使得变异测试的分析和执行阶段的开销比较昂贵。

为了让变异测试技术适用于工业应用，研究人员已经在变异体选择优化方向上进行了深入研究。在Offutt等[7]的实验中，从Mothra系统的22中变异算子选择了5种，变异得分仅降低0.5%。在Barbosa[8]的实验中，从Proteum系统中的77种变异算子选择了10种，有效减少了65.02%的变异体，变异得分仅降低0.4%。Namin[9]在足够评估测试用例充分性的情况下从C语言的108种变异算子中选择了28种变异算子，可以减少92%的变异体。用较小子集在不影响变异得分的情况下替换全集的方法，仍然是变异测试领域研究的热点之一。

1 技术路线

1.1 技术基础

对变异算子的选择是变异测试技术中的经典问题，对该问题进行如下描述：

假设：给定测试用例T，变异体集M，Score(T，M)代表T在M上执行的变异得分。

问题：寻找M1∈M，使得Score(T，M)≈Score(T，M1)。

Mathur在1991年提出一个解决方法，并称之为选择性变异(Selective Mutation)。这类方法旨在不影响变异评分的前提下，通过对变异算子进行约简来缩小变异体的数量，从而减少变异测试的开销。

在针对表1中的22中变异算子中，ASR算子和SVR算子会生成大约30%～40%的变异体。Offutt等通过忽略ASR和SVR这两种算子，有效减少了生成变异的数量，并将该方法命名为“2-selective mutation”[7]，同时他们又提出了“4-Selective Mutation”和“6-Selective Mutation”。他们的实验表明应用“2-Selective Mutation”策略后，其变异评分均值为99.99%，可减少24%的变异体数量。应用“4-Selective Mutation”策略后，其变异评分均值为99.84%，可减少41%的变异体数量。而应用“6-Selective Mutation”策略后，其变异评分均值为88.71%，可减少60%的变异体数量。Offutt等在理论上将该方法扩展到了“N-Selective Mutation”。

本文基于Selective Mutation方法，从Mujava的19个java类级别变异算子忽略一些对变异得分的结果影响较小的算子，并在最后对所选算子进行充分性验证。

1.2 研究对象

在变异测试发展的40年中，研究人员和从业者已经开发并使用了许多变异测试工具[3]，对ISSTA上发表的和变异测试相关的论文进行调研，最常用的有3种工具：Major[4]，MuJava[5]和PIT[6]。而在Kintis[3]2017年对变异测试工具的评测中，对于相同的待测程序，MuJava，Major，PITRV三者分别会产生手工测试的数量为138，97，105，产生的变异体数量分别为203，94，382，最终依据Bug检测能力的评分为85，80，91。PITRV是PIT的研究版本，在该测评中能揭露97%的真实Bug,是效果最佳的工具，但在2016年的实验中[10]使用PIT的普通版时，发现PIT揭露Bug的能力远远低于MuJava和Major。为了避免PIT版本之间的不确定性对实验结果的影响，本文选择了得分第二的MuJava来开展变异算子的选择实验。

MuJava是一个针对Java语言的变异测试工具，它提供了可选择的19种Java类级别的变异算子，能够自动为原程序生成变异体，测试人员只需要提供符合Junit规范的测试用例，就能使用MuJava来自动判断是否杀死变异体并计算得分。表2展示了可操作的类级别变异算子和对应的描述。MuJava是一个Java变异测试中有很高研究价值的工具，MuJava提出了一种MSG/Bytecode技术来处理变异体，在编译生成和执行变异体时实现了平均6.79倍的加速。同时，MuJava开发了19种Java类级别的变异算子并提供源代码，测试人员可根据自己的需要自行选择所使用的算子。

表2 MuJava的19种变异算子及其变异规则Table 2 19 mutation operators and mutation rules of MuJava

1.3 待测程序

本文在Windows操作系统下采用Java 1.8在eclipse+MuJava的环境下进行试验，为避免所选程序的偶然性对实验结果的影响，选择了2017 全国大学生软件测试大赛提供的Java程序。该大赛由教育部软件工程专业教学指导委员会、中国计算机学会软件工程专业委员会、中国软件测评机构联盟、中国计算机学会系统软件专业委员会和中国计算机学会容错计算专业委员会联合举办，吸引了全国300余所大学的近4 000名学生参赛。由组委会提供来自开源社区的Java程序代码，在慕测WebIDE或者Eclipse客户端完成Junit测试脚本。待测程序为个人初赛和复赛的4个Java项目，共24个类进行测试。如表3所示。

表3 所选待测程序和描述Table 3 Selected programs to be tested and the description

1.4 技术方案

Offutt等依据各种变异算子修改语法元素的不同将其分为了三大类[7]：第一类，操作符替换类AAR，ACR，ASR，CAR，CNR，CRP，CSR，SAR，SCR，SRC，SVR；第二类，表达式修改类ABS，AOR，LCR，ROR，UOI；第三类，语句修改类DER，DSA，GLR，RSR，SAN，SDL。并用实验证明了表达式修改类的5个变异算子ABS，AOR，LCR，ROR，UOI对于22个变异算子具有ProbSubsumes关系[7]，该关系表明表达式修改类的变异算子具有代表整个变异算子集合的能力。Offutt等的实验结果为表达式修改类算子对所有算子的相对变异得分为99.51。

根据上述实验的分类方法，将MuJava中的变异算子进行分类，将其中6个表达式修改类AOIU，AOIS，ROR，AORS，AORB，LOR作为Java变异算子的子类选择集合。将通过子集得到的变异体组合简称为6M组，将通过全集得到的变异体组合简称为19M组，删除其中6M一个变异算子得到的变异体组合成为5M组，将对应生成的测试用例简称为T，手工检测到的等价变异体(Equivalent Mutants)简称为EM，变异得分Socre(T，M)表示测试用例集合T在M上执行所得的总分。技术方案如图1所示。

图1 技术方案Fig.1 Technical programmes

2 实验结果

实验步骤中的结果如表4所示，其中去掉了一些无法被测试的类(接口，main函数等)，为了缩短运行的时间，相同的测试用例会被合并，只保留一个，无法达到100%时会手工判断剩下的变异体是否为等价变异体，判定为等价变异体的会删除，判定为非等价变异体的会不断扩展测试用例直到杀死，最终达到100%。

表4 6M组的变异体数目和得分Table 4 The number of mutants and scores for the 6M group

得到的TC组保持不变，对19M组再次进行实验。结果如表5所示，同样手工排除等价变异体，没有杀死的变异体确定为TC组无法杀死的变异体，这些变异体由6M以外的其他变异算子生成。如果要杀死这些变异体，需要再次进行测试用例的扩展，这一部分为6M组所无法覆盖的部分。

表5 19M组的变异体数目和得分Table 5 The number of mutants and scores for the 19M group

19M组的变异得分情况如图2所示，考虑到Predicate，Value，Variable这3个类有相同的结构，测试代码也在形式上完全一致，因此只取其中一个计算。最高分100，最低分87.06，平均分95.01分，将AOIU，AOIS，ROR，AORS，AORB，LOR这6个算子作为Java 19个类级别的变异算子的充分子集，取得了95.01的平均分。

图2 19M组合变异得分情况Fig. 2 Mutation Score Line Chart of the 19M group

验证6M组的变异算子之间的充分性结果如表6所示，可以看出在整个变异算子中，AOIS是比较重要的部分，缺少AOIS来生成测试用例会导致评分降低20%～30%，另外AOIU，ROR和AORB有着能影响评分10%左右的作用，AORS和LOR的删除几乎不影响评分，这里从充分集合中删除LOR而保留AORS，因为AORS产生的变异体只能由自己对应的测试用例杀死，和其他变异体几乎没有交互，而LOR几乎没有产生变异体，这和所选择的初始程序的类型有关。关于LOR变异算子是否选择的问题，测试人员可以根据所测项目的实际情况进行增添删改，实验证明对于一般Java程序选用AOIU，AOIS，ROR，AORS，AORB这5个变异算子可以满足Java类级别的变异测试。

表6 删除任一变异算子后5M组对6M组的得分Table 6 The score of 5M group to 6M group after deleting any mutation operator

表7 QuadTree变异体数目分布Table 7 The number of mutants in the program QuadTree

取其中QuadTree的变异体数目分布情况，如表7所示，产生的数目排序为AOIS>SDL>ROR>AOIU>AORB>ODL>COI>COR>VDL>COD>AORS>LOI,其中删除类变异算子SDL+VDL+CDL+ODL的占比为27.04，该类算子与表达式修改类算子有很强的相关性，能够杀死表达式修改类产生的变异体的测试用例往往也能够杀死删除类产生的变异体，故不考虑把该类算子加入充分性集合中。

4 结论

本文针对MuJava的19个类级别的变异算子对4个Java项目进行了相关实验，选择其中5个作为变异算子的可替换子集已经足以有效实施变异测试，能够在平均变异得分95.01的情况下，减少1～2倍数量的变异体。由于所选程序的局限性，并不能完全断定LOR算子是无意义的。实验中发现删除类变异算子和表达式修改类变异算子具有强相关性，可以在Java变异测试中不使用删除类变异算子。

变异测试作为一种面向软件缺陷的技术，得到了国内外软件测试人员的关注，并取得了大量研究成果。目前，变异测试和自动化测试结合是一个待研究的新领域，面向变异测试的测试用例生成还是起步阶段，可以进一步考虑将基于遗传算法的测试用例生成和变异测试的思想进行结合，用变异得分来指导种群的迭代以减少种群迭代的次数并提高测试用例的生成效率。