于 畅 王雅文 林 欢 宫云战

(网络与交换技术国家重点实验室(北京邮电大学) 北京 100876)(shuoxunyc@bupt.edu.cn)

变异测试(mutation testing)是一种基于故障的软件测试分析方法[1]，它通过向被测软件注入一组人工故障，以模拟软件开发过程中引入的代码缺陷[2].这些故障被进一步用于评估测试充分性[3-5]，并辅助测试人员开发测试用例以提高测试质量[6-8].相关研究[9-10]表明，相较结构化覆盖准则[11]，该技术具有更强的检错能力.

在变异测试中，通过修改被测程序源代码的语法结构注入故障，被修改后的故障程序称为变异体，而代码修改规则称为变异算子.例如，关系运算符替换算子(relational operator replacement, ROR)对关系表达式xy，x≥y，x==y以及x≠y共5个变异体.在变异测试中，如果1个变异体m与被测程序p在测试输入x上的输出不同，则称变异体m被测试输入x杀死.

尽管变异测试能为被测程序生成大量变异体，然而并非所有变异体对测试数据质量的提高都有帮助[12-13].Ammann等人[14-18]的研究表明：现有的变异测试工具会生成超过80%的无效变异体.这些无效变异体不仅会增加测试成本和执行时间，同时还会降低变异分析的有效性，降低测试质量.其中一类对变异测试影响较大的无效变异体是等价变异体[19].

等价变异体指的是与原程序保持语义等价的变异体程序[20].这类变异体无法被任何的测试输入杀死，既不能有效地模拟故障缺陷，也无法改进测试数据充分性.因此在测试前，需要将程序中的等价变异体识别并移除.图1展示了一个示例程序以……