1. 变异测试

1.1 变异测试提出的背景与动机

近年来人们逐渐发现一个问题，有些时候测试用例的代码覆盖能力和测试用例错误检测能力并不具有很高的相关性。

也就是说可能存在这样一些情况：一组测试用例的代码覆盖率很高，但却检测不到错误，而另一组测试用例能检测到很多错误，但它的代码覆盖率却并不高。为此，人们从错误检测的角度引入新的测试充分性度量标准 —— 变异测试（Mutation Testing）。

✅结论：变异测试是从错误检测角度引入的，用来测试和评估测试用例集的一种测试

1.2 变异测试的基本概念

• 变异测试定义：通过在程序中注入故障（fault）（称为 mutant 变异体），评估测试用例集的错误检测能力。
• 注入方式：通常为一个非常小、单一的语法变更，使得程序依然能成功编译。
• 目的：并非直接测试程序，而是测试用例集是否足够强大以捕捉这些变异，从而评估测试用例的设计质量。

注：我们为什么要在程序中注入故障（fault）？

首先变异测试是用来测试和评估测试用例集的一种测试，也就是说它本意上并不是来测试程序，它只是用来评估一个测试设计的充分性，某种意义上的错误检测能力。所以变异测试通常作为一种辅助手段，而不是替代传统测试方法的手段。

1.3 变异注入的示例

在注入变异的时候，我们需要强调：

• 必须是单个语法变更
• 必须编译通过，否则视为无效

我们来看这样一个注入：

我们在第四行代码 x > y 做了一个变化，变成 x < y 。所以我们说我们在第四行代码里注入了一个 mutant，变异后的程序，我们称之为变异体。

那么我们该如何注入变异？常见的注入方法有很多，举几个例子：

• 操作数替换：

  • 可以用另外一个变量或者一些常数来替代在程序当中的某些操作数
  • 如 x > y → 5 > y 或 x > 5，或 y > x。

• 操作符替换：

  • 逻辑：== → !=, >=, <=
  • 算术：+ → -, *, /

• 表达式重写：

  • 在表达式中注入其他操作，如 == y → == y + 1

• 控制流变异：

  • 逻辑连接符替换、关系运算符替换、单目运算符替换（如 i++ → --i）

1.4 哪种注入方法更充分？

由于有很多种变异的方法，所以人们就很好奇的，到底哪些变异方法才是充分的？于是在历史上就有很多研究者去研究什么样的一个变异操作才是充分的，也就是说用了它以后，其他的我们可以忽略掉。

其中有代表性的一篇就是 1996 年 A.J.Offutt 等发表的论文《An experimental determination of sufficient mutant operators》

在这篇文章里它介绍了五种最常见也最有用的变异，可以覆盖绝大多数情况：

• 绝对值替换
• 算数替换
• 逻辑连接符替换
• 关系运算符替换
• 一元操作符替换

1.5 变异测试的执行流程

这张图可以很清晰的展示变异测试的执行过程，大致可以分为四步：

1. 对原始程序进行变异： 每个变异使用一个 mutation operator，我们可以产生很多很多的变异体
2. 用现有测试用例执行原始程序和变异体
3. 比较输出是否一致：
   • 如果输出不一致 → 变异被"杀死"（killed）
   • 如果输出一致 → 未能检测出变异，需要补充测试用例
4. 持续迭代补充测试用例，直到足够充分检出所有测试用例，停止测试

1.6 等价变异

我们很容易构造出两个语法上不一样的程序，但语义上完全一致。就是代码上它看起来有一些不一样，但是对于任意的输入它的输出都一样。事实上这两个程序是语义上等价的，这个变异称之为等价变异。

非常不幸的是，这是一个不可判定问题，也就是我们没有通用的方法来判定一个变异是否是等价变异。而在实践操作当中，我们只能根据有经验的工程师通过人工的判别来判定哪些是等价，哪些不是等价变异，这是一个代价非常高的任务。

来看下面这两个程序，我们虽然进行了变异注入，由于 i 是累加的，所以原条件和替换的条件在语义上是完全一致的。

---

2. 评估测试用例集

我们通常用 Mutation Score 这个指标来评价一个测试用例集的好坏。对于测试用例集来说，一个测试用例集比另外一个测试用例集更强是指它的 Mutation Score 更高。

我们用以下公式来计算 Mutation Score：

$$
MutationScore = 100 * K / (T -E)
$$

其中：

• K 是指被"杀死"的变异体的数量
• T 是指所有变异体的数量
• E 是指等价变异体的数量

如果一个测试用例集的 Mutation Score 是 100% ，我们就称它是 mutation adequate。

---

3. 变异测试的发展历史

3.1 变异测试发展

• 奠基文献：

  • 1970年代 DeMillo 等人的论文被认为是变异测试的起点。
  • 早期未被广泛使用，主要原因：成本太高（需对每个 mutant 执行所有测试）。

• 发展趋势：

  • 2000年后工具数量激增，受益于计算能力提升。现如今 Java、C++、XML 等均有对应工具。

3.2 变异测试的两个核心假设

在早期 DeMillo 的那篇文献当中，他提出了两个假设：

熟练程序员假设：通常是用来模拟那些熟练的程序员不小心犯了一个极小的错误，这样的一个小错误，使得变异程序和原来的程序是非常相近的，也就是他认为一个熟练的程序员不可能把一大片代码都写错。这也为什么我们在变异当中是注入一个非常简单的语法改变，而且单一的 fault。

错误耦合效应假设（Coupling Effect Hypothesis）： 假如单一的一个 fault 能够被检测到，那么组合的比较复杂的 fault，我们也能检测到。

这两个假设并没有得到理论证明，只是人们在实际经验当中发现了一些现象，也正因为如此，这两个假设可能在一些特定条件并不满足，使得变异测试的作用降低。

这两者无理论证明，仅基于经验观测，但是变异测试的理论基础。