变异测试 Mutation Testing

什么是变异测试

通过创建程序的许多不同版本，将缺陷引入程序中，这些版本被称为变异体。

每个变异体都包含一个单独的缺陷。

测试用例会被同时应用到原始程序和变异程序上。

目标是让变异程序失败，从而证明测试用例的有效性。

  • 变异测试是一种向程序中插入缺陷的方法，用来测试已有测试是否能够发现这些缺陷，从而验证或否定这些测试的有效性。
  • 变异测试是一种关注度量测试用例充分性的测试技术。
  • 变异测试应该与传统测试技术结合使用，而不是取代传统测试技术。

变异程序

变异测试涉及为被测程序创建一组变异程序。

每个变异程序与原始程序只相差一个变异。

一个变异是对程序语句所做的一次单一语法修改。

变异程序示例

原始程序

1 int max(int x, int y)
2 {
3     int mx = x;
4     if (x > y)
5         mx = x;
6     else
7         mx = y;
8     return mx;
9 }

变异程序

1 int max(int x, int y)
2 {
3     int mx = x;
4     if (x < y)
5         mx = x;
6     else
7         mx = y;
8     return mx;
9 }

变异算子的类别

操作数变异算子

用另一个操作数或者常量替换某个单一操作数。

用常量5替换x

if (5 > y)

用常量5替换y

if (x > 5)

将x和y互相替换

if (y > x)

表达式变异算子

替换某个运算符，或者插入新的运算符。

例如

if (x == y)

可以变异为：

if (x >= y)

也可以变异为：

if (x == ++y)

如果所有的运算符集合为：{ +, -, *, / }

那么表达式a = b * (c - d)会生成6个变异体：

  • 替换*可以产生3个变异体
  • 替换-可以产生3个变异体

充分变异算子

这里的“充分变异算子”可以理解为：不一定需要使用所有可能的变异方式，而是选择一组具有代表性的变异算子，以降低变异测试的成本。

面向对象变异算子

识别变异算子是困难的，因为传统的变异技术不能轻易扩展到面向对象语言中；它们可能会产生无法编译的代码。

R. T. Alexander 等人在 2002 年使用对 Object Mutation Engine 的调用，对被测类进行变异。

包含

CollectionMutator - 删除、添加、改变顺序
ListMutator       - 删除最后一个元素、改变顺序
VectorMutator     - 删除最后一个元素
MapMutator        - 删除第一个元素、删除最后一个元素、置空
IteratorMutator   - 跳到下一个对象

也就是说，在面向对象程序中，变异不仅可以改表达式和运算符，还可以改集合、列表、映射、迭代器等对象相关行为。

变异测试资源库

Yue Jia 和 Mark Harman 在 2011 年发表的论文《变异测试发展的分析与综述》中，对变异测试的发展进行了系统分析和综述。

变异过程

变异过程图示

大致流程为：

  1. 从原始程序开始；

  2. 对程序进行多次变异，生成多个变异体；

  3. 使用测试集去测试这些变异体；

  4. 如果测试能够捕获某个变异，那么这个变异体就被杀死；

  5. 如果还有存活的变异体，就需要分析原因：

    • 是测试不充分？
    • 还是该变异体是等价变异体？

  6. 如果是测试不充分，就需要添加新的测试数据；

  7. 如果所有非等价变异体都被杀死，则测试完成。

任何被测试捕获到的变异都会被杀死。

也就是说，如果测试用例能够让变异程序和原始程序产生不同输出，那么这个变异体就算被测试发现了，也就是被“杀死”了。

等价变异体

可能存在一些存活的变异体，它们无法被杀死，这些变异体被称为等价变异体。

虽然它们在语法上和原程序不同，但通过测试无法区分它们。

因此，它们必须被人工检查。

例如：

while ...
...
i++
if (i == 5)
    break;

变异之后：

while ...
...
i++
if (i >= 5)
    break;

如果在这个程序上下文中，i 每次只增加 1，并且不会跳过 5，那么：i == 5和i >= 5在实际执行效果上可能完全一样。

所以这个变异体虽然语法不同，但测试无法观察到行为差异，这就是等价变异体。

变异分数

对于一组测试用例来说，变异分数表示：

测试数据杀死的非等价变异体所占的百分比。

Mutation Score = 100 * K / (T - E)

其中：

K = 被杀死的变异体数量
T = 总变异体数量
E = 等价变异体数量

如果一组测试用例的变异分数是 100%，则称这组测试用例是变异充分的。

也就是说，除了等价变异体以外，所有变异体都被测试杀死了。

Discuss

等价变异体的不可判定性，以及人工检查的成本。

等价变异体是否真的等价，在理论上存在不可判定问题。

同时，即使在实践中想要判断某个变异体是不是等价变异体，也往往需要人工检查，这会带来很高的成本。

变异测试虽然很强，但主要问题之一就是成本高，尤其是等价变异体的识别成本高。

变异测试的历史

变异测试在 20 世纪 70 年代末受到更多关注，代表人物是 DeMillo 等人。

后来由于成本问题，研究热度下降。

最近又重新受到研究关注，原因是计算能力大幅提升。

一些假设

胜任程序员假设 Competent Programmer Hypothesis

真实世界的 Bug 通常不是离奇的设计失误，而是微小的偏差，比如运算符写错或者逻辑取反。

被测模块是由有能力的程序员或设计者编写的。

因此，如果这个模块不正确，它与正确程序之间最多只相差少数几个小缺陷。

换句话说，真实程序中的错误通常不是完全离谱的大错误，而更可能是一些小的语法或逻辑偏差。

耦合效应 The Coupling Effect

如果一个测试集能够区分所有只包含简单缺陷的程序和正确程序，那么这个测试集已经足够敏感，也会隐含地区分更复杂的缺陷。

能杀死简单变异体的测试集，通常也有能力发现更复杂的错误。

变异测试总结

一个变异是一次单一的语法修改。

变异测试用于评价测试的充分性。

变异测试不是直接为了测试原程序有没有 bug，而是用来评价测试用例强不强。

如果测试用例连人为制造的小错误都发现不了，那么它对真实缺陷的发现能力也值得怀疑。

基于缺陷的测试 Fault-based Testing

设计测试来揭示人为植入的缺陷。

设计的目的有：

  1. 证明某些缺陷不存在；
  2. 揭示缺陷；
  3. 通过衡量测试集发现人为植入的假缺陷的能力，来判断它发现真实缺陷的有效性。

我们希望通过衡量一个测试集发现人为植入的假缺陷的能力，来判断它发现真实缺陷的有效性。

先人为制造一些“假缺陷”，再看测试能不能发现它们，从而评价测试集质量。

变异测试本质上就是一种基于缺陷的测试。

它通过构造“带缺陷的版本”，来检查测试集是否足够强。

缺陷类别

缺陷类别分为两大类：

  1. Operator Fault Class 操作符缺陷类别：4 类
  2. Operand Fault Class 操作数缺陷类别：6 类

操作符相关缺陷：主要是逻辑连接符、取反、括号优先级等错误；

操作数相关缺陷：主要是变量缺失、变量引用错误、条件组合错误、固定为 0 或 1 等错误。

操作符缺陷类别

原表达式为E = (a | b) & c

操作符引用缺陷 Operator Reference Fault，ORF

某个逻辑连接符 & 被替换成 |，或者 | 被替换成 &。

例如：E' = (a & b) & c

表达式取反缺陷 Expression Negation Fault，ENF

某个子表达式，条件除外，被替换成它的否定形式。

例如：E' = !(a | b) & c

变量取反缺陷 Variable Negation Fault，VNF

某个条件被替换成它的否定形式。

例如：E' = (a | b) & !c

结合性偏移缺陷 / 括号优先级缺陷 Associative Shift Fault，ASF

由于误解操作符优先级，省略括号而产生的缺陷。

例如：E' = a | b & c

操作数缺陷类别

元表达式为E = (a | b) & c

缺失变量缺陷 Missing Variable Fault，MVF

某个条件被省略。

例如：E' = (a | b)

变量引用缺陷 Variable Reference Fault，VRF

例如：E' = (a | b) & a

子句合取缺陷 Clause Conjunction Fault，CCF

某个条件 c 被替换成：c & c'

例如：E' = (a | b) & (c & a) 这里相当于把c加强成了c & a

子句析取缺陷 Clause Disjunction Fault，CDF

某个条件 c 被替换成：c | c'

例如：E' = (a | b) & (c | a) 这里相当于把c放宽成了c | a

固定为 0 缺陷 Stuck-At-0 Fault，SA0

某个条件被替换成 0，也就是永假。

例如：E' = (0 | b) & c

固定为 1 缺陷 Stuck-At-1 Fault，SA1

某个条件被替换成 1，也就是永真。

例如：E' = (1 | b) & c

测试条件

测试条件：E ⊕ E'，其中 ⊕ 表示异或，也就是 XOR。

如果一个测试用例 t 满足测试条件：E ⊕ E'

那么测试用例 t 就可以检测出原表达式 E 的变异体 E'。

当原表达式 E 和变异表达式 E' 的结果不同，这个测试就能杀死该变异体。

设原表达式为：E = (a | b) & c

变异表达式为：E' = (a | b) & !c

VNF 变量取反缺陷

当a = 1, b = 0, c = 1时，E = 1 E' = 0

测试条件的蕴含关系

蕴含关系：(E ⊕ E1) |= (E ⊕ E2)

记作：E1 |=E E2

如果能够检测出变异体 E1 的测试条件一定能够推出检测出变异体 E2 的测试条件，那么称：E1 比 E2 更强。

能杀死 E1 变异体的测试用例，一定也能杀死 E2 变异体。

如果测试集能够检测出 FA 这一类缺陷，那么它也能够检测出 FB 这一类缺陷，那么 FA 就比 FB 更强。

FA 的测试要求可以覆盖 FB 的测试要求

缺陷类别层次结构

缺陷类别层次结构