模糊测试论文

Directed Greybox Fuzzing

AFLGo 由四个组件实现：图形提取器、距离计算器、仪器器和模糊器。通过集成到 OSS-Fuzz，我们证明这些组件可以无缝集成到原始构建环境（例如 make 或 ninja)中。整体架构如图7所示。下面我们解释一下这些组件是如何实现的。

(1) AFLGo 图形提取器 (GE) 生成调用图 (CG) 和相关的控制流图 (CFG)。 CG节点由函数签名来标识，而CFG节点由源文件和相应基本块的第一条语句的行来标识。 GE 是作为 AFL LLVM 通道的扩展来实现的，该通道由编译器 afl-clang-fast 激活。将编译器环境变量 CC 设置为 afl-clang-fast 并构建项目。

(2) AFLGo 距离计算器 (DC) 根据第 3.2 节采用调用图和每个过程内控制流来计算每个基本块 (BB) 的过程间距离。 DC 以 Python 脚本的形式实现，该脚本使用 networkx 包来解析图形并根据 Djikstra 算法进行最短距离计算。 DC生成BB距离文件，其中包含每个BB的基本块级目标距离。

(3) AFLGo Instrumentor 获取 BB 距离文件并检测目标二进制文件中的每个 BB。具体来说，对于每个BB，它确定各自的BB级目标距离并注入扩展的蹦床。蹦床是一段汇编代码，在每个跳转指令之后执行，以跟踪所覆盖的控制流边缘。一条边由 64kb 共享内存中的一个字节来标识。在 64 位架构上，我们的扩展使用 16 个额外字节的共享内存：8 个字节用于累积距离值，8 个字节用于记录已执行 BB 的数量。对于每个 BB，AFLGo Instrumentor 添加汇编代码 i) 加载当前累积距离并添加当前 BB 的目标距离，ii) 加载并增加已执行 BB 的数量，以及 iii) 将两个值存储到共享内存。该检测是作为 AFL LLVM pass 的扩展来实现的。编译器设置为 afl-clang-fast，编译器标志设置为引用 BB-distance 文件，并且该项目是使用 ASAN [35] 构建的。

(4) AFLGo Fuzzer 被实现到 AFL 版本 2.40b（已经集成了 AFLFast 的探索计划 [6]）。它根据我们基于退火的功率计划对检测后的二进制文件进行模糊测试（参见第 3.3 节）。共享内存中的额外 16 个字节告知模糊器当前的种子距离。当前种子距离的计算方法是将累积的 BB 距离除以已执行的 BB 数量。

Sequence Coverage Directed Greybox Fuzzing

Fuzz方法：

SS：statement sequence（语句序列）
BLS：basic block location sequence（转化为基本块位置序列）
TBBET：target basic block execution trace（目标基本块执行轨迹）

在每个目标基本块的入口，会添加如下指令：

获取共享内存的指针M
读取$M_0$的值，并为其加1，i.e. i = i + 1
将当前基本块的ID存入Mi
把第二步得到的值再存入$M_0$, i.e. $M_0$=i

在fuzz的过程中，当种子探索到目标基本块的时候，插桩的代码就会执行，因此，基本块的Trace就会被存储在共享内存中。

fuzzing的算法如下，主要分为两个部分，计算序列覆盖率（2-13行）和能量调度（14-22行）。