起源与发展

1. 1988，Barton Miller，为了提高 UNIX 操作系统的可靠性（发送字符信息乱码导致系统崩溃）
2. 技术构想：
   1. 核心组件：一组用于产生随机字符的程序
   2. 中心思想：以随机字符串作为输入，运行操作系统组件（Utilities），观察是否崩溃
   3. 最终结果：保留能够产生崩溃的字符串输入，分析崩溃的类型，对崩溃进行分类

概念与框架

三要素：一个工具、一个目标、一个循环

1. 工具：模糊器（Fuzzer）
2. 待测程序（PUT）
3. 循环：执行程序 $\leftrightarrow$ 崩溃分派（Crash Triage）

上述初始框架的问题：

1. 初始的输入从何而来，模糊测试的相关配置如何进行
2. 如何对输入进行调度（Schedule），如果控制执行的过程
3. 如何对输出进行分析，如何判断输出的有效性和可复用性

术语

1. 模糊（Fuzzing）与模糊测试（Fuzz Testing）
   1. 模糊：模糊是指使用从输入空间（模糊输入空间）采样得到的输入来执行待测程序（PUT，Program Under Test）的过程。该模糊输入空间代表着测试人员针对待测程序定义的预期输入
   2. 模糊测试：模糊测试是一种应用模糊（过程）来验证待测程序是否违反正确性策略（Correctness Policy）的测试技术
   3. 在文献中两者一般可以互换
2. 模糊器（Fuzzer）：一个（组）用于实现模糊测试的程序 $\rightarrow$ 核心组件
3. 模糊运动（Fuzzing Campaign）：模糊运动是指一个模糊器按照一组特定的正确性政策在一个给定待测程序上的一次具体的执行 $\rightarrow$ <fuzzer, program>（最简单情况下就是一个二元组，但可以在这个基础上增加其他，比如超时时间、异常等）
4. 缺陷预言（Bug Oracle）：一个用于确定一次给定执行是否违反具体正确性策略的程序，通常作为模糊器的一部分出现
5. 模糊配置（Fuzz Configuration）：一组控制和描述模糊（测试）算法的数据和约束
6. 测试输入（Test Input）、测试用例（Test Case）与种子输入（Seed Input）
   1. 测试输入：一组用于驱动待测程序执行的 数据
   2. 测试用例：一组用于确定应用软件或软件系统是否能够正确工作的条件或变量 $\rightarrow$ 输入 + 逻辑（调用序列）+ 预言
   3. 种子输入：一个或一组在模糊测试过程中为输入生成（Input Generation）提供基准的测试输入，简称 种子（Seed）

模糊测试框架

家族与分类

家族

根据基础 Fuzzer 划分家族

1. AFL家族（C/C++）：AFL、AFLFast、AFLSmart、AFLNet、AFLGo、AFLIoT、FairFuzz、Mopt、Neuzz
2. LibFuzzer家族（C/C++）：LibFuzzer、Entropic
3. JQF家族（Java）：JQF、BeDivFuzz、CONFETTI
4. 其他（Rust、Python等）：AngoraDeepXplore

分类

• 根据组建核心或技术贡献进行分类
  • 按照采用的运行时信息：黑盒、灰盒、白盒
  • 按照输入生成的策略：Mutation-based，Generation-based
  • 按照引导过程：Search-based（一些启发式算法），Gradient-based（梯度下降）
  • 按照测试的目的：定向、非定向、某一类缺陷
  • 按照应用领域：网络协议、Compiler、DNN、IoT、内核
  • 按照优化角度：种子调度、变异策略、能量调度、过程建模

按照运行时信息分类

1. 黑盒（Blackbox）模糊测试
   • 特点：不监控执行过程，也不使用执行过程中产生的任何信息，仅从输入和输出端入手优化模糊测试
   • 引导方式：利用输入格式或输出状态引导测试执行
   • 优缺点：效率高，但引导的有效性上面有所欠缺
   • 代表性工作：KIF、IoTFuzzer、CodeAlchemist
2. 白盒（Whitebox）模糊测试
   • 特点：使用混合分析，污点分析（Taint Analysis）等比较昂贵的白盒分析技术优化模糊测试的过程
   • 引导方式：利用详细的程序分析结果引导测试执行
   • 优缺点：反馈更加有效，但是效率不高、适配性较差
   • 代表性工作：Driller、QSYM、CONFETTI
3. 灰盒（Greybox）模糊测试
   • Coverage-based Greybox Fuzzing，CGF
   • 特定：采用轻量级插桩对程序进行监控，在执行过程中收集各类信息，如分支覆盖、线程执行、堆栈状态等
   • 引导方式：利用收集到的执行信息（内部状态）引导测试执行

按照生成策略分类

1. Mutation-based：基于随机变异或者启发式变异策略
   • 本质：将种子输入转换为比特串（Bits），对比特串进行变换
   • 优点：可拓展性强，易于泛化，理论上可用于任意输入（图片、文本、音视频）
   • 缺点：容易破坏输入的结构、产生无效输入（Invalid Input）；生成的大部分输入都无法通过语义检查（Semantic Checking），很难探测深层次的程序状态和程序元素（Program Elements）

2. Generation-based：基于一定的文法规则/结构信息
   • 本质：利用给定的、或者挖掘/学习得到的文法规则，来构建能够通过（语法）检查的结构化输入
   • 优点：容易生成合法、有效输入（Valid Inputs），适用于对输入结构性要求较高的乘警，如针对解析器（Parser）、解释器（Interpreter）以及编译器（Compiler）的测试
   • 缺点：需要人工赋予一定的领域知识，在没有人工指定文法的情况下，很难得到完整的文法规则。

按照引导方式分类

1. Text Execution、Output Analysis
2. Search-based：将测试转换为搜索问题，以代码覆盖率作为指示器、以启发式算法（类遗传算法）为核心，将测试导向更高覆盖的方向 $\rightarrow$ CGF

3. Gradient-based：将测试转化为优化问题，以最大化缺陷发掘输入为目标构建目标函数，迭代求最优解 $\rightarrow$ 退而求覆盖率
   • 目标退阶：缺陷离散分布且无法预知 $\rightarrow$ 替换为代码覆盖
   • 应用 DL 技术-Neuzz & MTFuzz；利用梯度下降取代符号执行的约束求解过程-Angora

4. 模糊测试中的马太效应（Matthew effect）：好的种子输入能够演化产生品质良好的子代测试输入

按照测试目的分类

1. 非定向模糊测试：Wider and Deeper
   • 目标：验证程序的正确性，检测程序中潜在的缺陷
2. 定向模糊测试：Directed and Targeted
   • 目标：针对程序中的某个目标位置进行快而有效的测试
   • 场景：缺陷复现、补丁检验、静态分析报告验证
   • 分类：白盒、灰盒

Reference

1. 南京大学本科三年级课程《自动化测试》
2. Fuzzing Test 有关的论文