模糊测试

起源与发展

模糊测试是由 $\mathrm{Barton}\mathrm{P}.\mathrm{Miller}$ 在自己的操作系统课上首次提出模糊测试，在 $1990$ 年首次发表相关文章。

• 出发点：提升 $\mathrm{UNIX}$ 系统的可靠性。
• 核心组件：产生随机字符串的程序。
• 中心思想：以随机字符串作为输入，运行操作系统组件，观察是否崩溃。保留能够产生崩溃的字符串输入，分析崩溃的类型，对崩溃进行分类。

模糊测试目前在学界持续发展，热度很高，最主要的原因就是它具有简单的框架和多样的拓展。

概念与框架

模糊测试的定义：产生一些输入，并在软件系统上运行，最后观察运行的结果。

模糊测试的工具：一个（或一套）工具、一个目标、一个循环。

• 工具：模糊器。
• 目标：待测程序。
• 循环：执行程序和崩溃分派之间。
• 三个重要组件：输入生成组件（模糊器）、测试执行组件和输出分析组件。

整个模糊测试的构想可以从下图显示出来

模糊测试简单构想

相关术语解释

模糊（Fuzzing） 是指使用从模糊输入空间采样得到的输入来执行待测程序（PUT，Program Under Test）的过程。该模糊输入空间代表着测试人员针对待测程序定义的预期输入。

模糊测试（Fuzz Testing） 是一种应用模糊过程来验证待测程序是否违反正确性策略（Correctness Policy）的测试技术。在文献中可以和模糊互换。

模糊器（Fuzzer） 是一个或一组用于实现模糊测试的程序。

模糊运动 是指一个模糊器按照一组特定的正确性政策在一个给定待测程序上的一次具体的执行。

缺陷预言（Bug Oracle） 一个用于确定一次给定执行是否违反具体正确性策略的程序， 通常作为模糊器的一部分出现。

测试输入 是一组用于驱动待测程序执行的数据。

测试用例 是一组用于确定应用软件或软件系统是否能够正确工作的条件或变量。是对测试输入的进一步抽象。

种子输入 是一个或一组在模糊测试过程中为输入生成（Input Generation）提供基准的测试输入，简称种子（Seed）。类似随机数种子。

下面是模糊测试的全面框架：

模糊测试的全面框架

家族与分类

根据基础 Fuzzer 划分家族

• $\mathrm{AFL}$ 家族（$\mathrm{C}/\mathrm{C}++$）：AFL、AFLFast、AFLSmart、AFLNet、 AFLGo、AFLIoT、FairFuzz、Mopt.、Neuzz
• $\mathrm{LibFuzzer}$ 家族（$\mathrm{C}/\mathrm{C}++$）：LibFuzzer、Entropic
• $\mathrm{JQF}$ 家族（$\mathrm{Java}$）：JQF、BeDivFuzz、CONFETTI
• 其他（$\mathrm{Rust}$、$\mathrm{Python}$ 等）：Angora、DeepXplore

根据运行时信息

• 黑盒模糊测试：不监控执行过程，也不使用执行过程中产生的任何信息，仅从输入和输出端入手优化模糊测试。优点是效率高，但引导的有效性上面有所欠缺。
• 白盒模糊测试：使用混合执行、污点分析（Taint Analysis）等比较昂贵的白盒分析技术优化模糊测试过程。
• 灰盒模糊测试：采用轻量级插装对程序进行监控，在执行过程中收集各类信息，如分支覆盖、线程执行、堆栈状态等。利用收集到的执行信息（内部状态）引导测试执行。

根据输入生成的策略

• Mutation-based：基于随机或启发式变异策略来生成输入。本质是将种子输入转换为比特串，对比特串进行变换。优点是可拓展性强，易于泛化；缺点是容易破坏输入的结构、产生无效输入。$\mathrm{SLF}$ 进一步分析程序中的语义检查、识别比特串中与影响语义检查的域、并根据两者之间的关系制定变异策略。
• Generation-based：基于一定的文法规则/结构信息来生成输入。挖掘已有的测试输入，得到现有的测试输入分布，并根据该分布进行输入生成以得到预期的测试输入。 例如，我们可以先获取文法和一个测试输入，生成概率文法，再利用这一概率文法去生成更多的输入。

基于生成的模糊测试主要流程

根据引导方式

• Search-based：将测试转化为搜索问题，以代码覆盖率作为指示器、以启发式算法（类遗传算法）为核心，将测试导向更高覆盖的方向。
• Gradient-based：将测试转化为优化问题，以最大化缺陷发掘输入为目标构建目标函数，迭代求最优解 → 退而求覆盖率。难点在：计算梯度；优化目标（缺陷发现数目或覆盖率）是不连续的，无法直接适配梯度下降算法，此时一般使用程序平滑来消除目标函数的不连续性。

根据测试目的

• 非定向模糊测试：验证程序的正确性，检测程序中潜在的缺陷。地毯式广泛地去测试。
• 定向模糊测试：针对程序中的某个目标位置进行快而有效的测试。一般是用于缺陷复现、补丁检验、静态分析报告验证等。主要的思路是为更靠近目标位置的种子分配更多的能量。

目前难点

• 性能要求、语言和底层开发的困难；
• 种子的选取、能量的分配和种子的复用；
• 缺陷预言和原因分析。

AI 模糊测试

• 种子集准备：首先可以去收集若干已有的测试用例作为初始种子，然后对其进行预处理（如变异、生成）等，然后将种子打包成语料集，并进行语料集的筛选。
• 过程引导：包括语料集采样、能量函数引导和有效性检测。这样可以保证模糊测试的效率和有效性。
• 结果验证：对于模糊测试的结果进行验证，例如与参考物对比、是否崩溃等。