对比与理解：模糊测试(fuzzing)与变异测试(mutation)
1、前言
谈到模糊测试（fuzzing）与变异测试（mutation），在很多场合下这两个概念会被混为一谈，可能很多人分不清它们究竟有什么区别。他们之间的相同点在于，这两种方法都是通过<改变某些东西>来引入变化，从而实现检测<系统，接口，服务，测试用例集，etc.>的稳定性与有效性。
Fuzzing的维基百科定义如下：
模糊测试 （fuzz testing, fuzzing）是一种软件测试技术。其核心思想是将自动或半自动生成的随机数据输入到一个程序中，并监视程序异常，如崩溃，断言（assertion）失败，以发现可能的程序错误，比如内存泄漏。模糊测试常常用于检测软件或计算机系统的安全漏洞。
Mutation只找到了英文维基百科的定义：
Mutation testing (or mutation analysis or program mutation) is used to design new software tests and evaluate the quality of existing software tests.
fuzzing与mutation的核心区别可以总结为以下两点：
二者改变的对象不同：fuzzing改变程序输入；而mutation改变程序代码本身；
二者的测试目的不同：fuzzing是为了找出程序可能的bug；而mutation是为了检验测试用例集合的有效性和完备性，从而定位程序中的bug。
Fuzzing相对比较容易实践。举个简单的例子，将一个合法的HTTP请求参数进行变化再进行请求，就是一次fuzzing。Fuzzing是一个应用范围非常广的方法，并且同时出现在不同领域中，这些领域互相有交叉，我们下面会介绍到。而Mutation相对来说成本要高一些，因为改变程序代码需要重新编译，再通过执行整个测试集来验证mutation的结果。需要注意，mutation的概念和系统层面的故障注入还是有区别的。系统层面的故障注入（例如操纵设备状态使得CPU处于高负载状态）更多的是在宏观层面影响被测对象，而mutation则是改变被测对象的代码本身。
下面我们将从四个角度来了解一下fuzzing，再介绍一下对代码做mutation的流程。
2、从四个角度了解fuzzing
2.1 Fuzzing出现在三个互相独立的研究领域
传统的fuzzing community：主要通过fuzzing来寻找程序中的安全漏洞
Symbolic execution research community：静态分析和符号执行的研究领域，将程序逻辑转化为一个约束求解问题，在约束节点对变量值和变量类型进行fuzzing
Search-based software engineering research community：基于优化的软件工程研究领域，代表算法是基因遗传算法。例如在客户端测试中，通过fuzz app的输入序列并获得反馈，来生成比前代有改进的下一代的输入序列
2.2 Fuzzing也分为黑/白/灰盒的fuzzing
黑盒fuzzing: 对程序内部一无所知的fuzzing，也不需要程序的反馈来改进fuzzing的输入。黑盒fuzzing分为两种形式：1. generational-based，即从零开始生成fuzzing的输入。可以是随机生成的输入，或是基于规则的生成；2. mutational-based，即基于已有的种子测试输入进行变异。黑盒fuzzing生成用例容易，但是较难保证测试的效率和效果。典型的黑盒fuzz工具：PeachFuzzer
灰盒fuzzing: fuzzing过程中会得到少量的程序反馈，以调整后续的fuzzing方式。例如在程序中进行插桩，可以获得一条fuzzing用例在执行时对应的代码覆盖率。如果接触到了更多的程序内容，就把这一条用例记录下来，用于改进fuzzing的效果。典型的灰盒fuzzing工具：AFL（很多fuzzing工具的基石），LibFuzzer，Honggfuzz，OSS-Fuzz & ClusterFuzz (Google)，Angora
白盒fuzzing: 基于程序分析符号执行和约束求解的fuzzing。先变异约束节点的条件，然后生成新的程序输入。白盒fuzzing的技术栈比较深，但是能应对更复杂的需求，需要在效果和效率上做平衡。典型的白盒fuzzing工具：KLEE（开源，百度在用），SAGE（微软），DeepState，Mayhem
2.3 从fuzzing的对象分
命令行工具：AFL，KLEE
测API：LibFuzzer
另外还有一些开放问题供大家思考：
如何fuzz有状态的程序？
如何fuzz 基于GUI界面的app输入序列？
如何fuzz需要满足某些格式/协议的输入？
2.4 fuzz比赛和benchmark
Rode0day：主办方每个月都会放出一些有bug的程序，大家用fuzzing的手段来找bug
FuzzBench: Fuzzer Benchmarking As a Service，为fuzzing效果衡量提供benchmark
3、Mutation流程讲解
3.1 简介
Mutation（变异测试）是指通过将故意设计的故障注入程序，用于测试的方法。通常是为了衡量测试集的有效和充足程度，同时也能为测试用例的生成指导方向。如果现有的测试集无法检测出注入的故障，说明测试集不完备。被注入了故障的程序被称为"mutants"，其中因为语法错误编译不过的那些在执行前被淘汰掉。剩下的mutants里面，在测试用例执行过后有些可能会被测试用例发现，而有些可能会逃逸。通过合理的构造，我们可以生成几乎任意种类的故障。这些故障可以检测常见的编程错误、内部边界问题、有害的代码结构等。变异测试的主要应用层次是在单元测试上，但是近年来逐渐扩展到了集成测试和系统测试上。
总的来说，用变异测试的好处有三点：
指出哪些地方需要测试
可以断言测试终止的条件（当想覆盖的地方都被覆盖了之后）
衡量测试集的完备性
mutants可以作为潜在的bug，预防以后出现的bug无法被检测到的情况。并且容易定位bug 简单的mutants组合起来，可以成为复杂的bug 如果测试集能检测到mutants，说明测试集发现bug的能力很强
3.2 代码mutation的流程
a. 选择生成mutants的方法
不同的编程语言或系统有不同的生成mutants的方法。包括：对面向对象/面向方面/脚本语言，对Android系统内的mutants生成，基于代码仓的真实bug学习出mutants的方法，针对安全/内存/变量问题的mutants等等
b. 生成mutants，编译程序
一个mutants编译一次显然不是好方案。可以通过将mutants做成类似meta-function的方式，来进行批量生成。其他的方案还包括直接操作bytecode
移除不能编译的mutants，去掉功能上重复的mutants，去除和原程序无区别的mutants
可以依据测试的目的定向选择某些类型的mutants，或者根据基础mutants组合出更复杂的mutants(higher-order mutants)，或者根据mutants在语法树上的位置选择
可以根据调用链中，不同函数的重要程度选择mutants，只看重要的部分
可以根据历史bug数据做筛选
d. 生成测试用例集
方法1：基于静态分析约束条件的生成方法
方法2：经典动态符号动态执行，或混合执行（每次用真实值，约束求反）的方法
方法3：基于优化的测试用例生成，例如基因遗传算法
e. 执行mutants，收集执行结果
这里有两种作为衡量标准的数据收集方式，分别是mutation score 和mutation matrix。假设有N个mutants和M个测试用例
对于mutation score来说，如果一个mutant被一条测试用例发现了，就不需要在其他测试用例上run它了，可以减少时间成本
对于mutation matrix来说，需要收集N*M次。这个指标对于测试断言、精简测试集和测试用例优选上是有意义的
f. 基于测试执行的表现，观察有多少mutants被发现了，给测试集打分
g. 从测试集中去除表现不佳的测试用例，提高表现好的测试用例的权重
h. 通过人为预先定义的测试集打分表现的阈值来判断测试集是否完善。如果没达到，重复d—g
i. 通过测试集对mutants的有效检测，将发现的bug返回给研发人员，最后修复这个bug
4、参考
Böhme, Marcel, Cristian Cadar, and Abhik Roychoudhury. "Fuzzing: Challenges and Reflections." IEEE Software (2020).
Papadakis, Mike, et al. "Mutation testing advances: an analysis and survey." Advances in Computers. Vol. 112. Elsevier, 2019. 275-378.
参考了一个很好的文档但是不方便放在这儿
https://shonan.nii.ac.jp/seminars/160/
5、用户讨论群