Full-speed Fuzzing:Reducing Fuzzing Overhead through Coverage-guided Tracing

摘要

本文把基于覆盖率的模糊测试分为了三部分

• 测试用例生成
• 代码覆盖率跟踪
• 崩溃分类

代码覆盖率跟踪是主要的开销来源，跟踪所有测试用例会导致严重的性能损失。

超过90%的模糊处理时间涉及执行和跟踪测试用例

1）绝大多数测试用例及其覆盖率信息由于没有增加代码覆盖率而被丢弃，所以本文只跟踪增加了覆盖率的测试用例；

2）随着时间的推移，增加覆盖率的测试用例变得越来越少。

Coverage-guided Tracing在目标二进制文件中对当前覆盖边界进行编码，以便可以自动报告测试用例生成新覆盖而不跟踪。减少处理没有覆盖率增加的测试用例的时间。

1.简介

通过控制流跟踪，以计算测试用例的代码覆盖率

修改目标二进制文件，称这种修改后的二进制文件为一些interest oracle（预测预言？）

首先，interest oracle以本机速度执行，不进行覆盖率跟踪。如果interest oracle报告一个测试用例导致覆盖率增加，则标记该测试用例，并且使用tracer来收集代码覆盖率。然后更新interest oracle部分，以反映之后新的覆盖范围，fuzz继续进行。通过这样做，Coverage-guided Tracing为处理覆盖率增加的测试用例（大约是我们实验中每个跟踪的两倍）以及以本地速度运行所有测试用例（最初）花了些开销。

贡献：

• Coverage-guided Tracing：只对覆盖增加的测试用例进行追踪从而减少guzz开销
• 实验量化了fuzz中变异生成覆盖率增加的测试用例频率之低
• 实验证明了两种不同类型的覆盖引导模糊器：AFL（“盲”测试用例生成）和Driller（“智能”测试用例生成），它们将大部分时间花在跟踪测试用例上
• 实现并评估UnTracer；UnTracer是我们基于Dyninst黑匣子二进制插桩的覆盖率导向跟踪程序。我们将UnTracer与三种流行的、最先进的白盒和黑盒二进制fuzz跟踪方法进行比较：AFL Clang（白盒）、AFL-QEMU（黑盒，动态二进制重写）和AFL Dyninst（黑盒，静态二进制重写）
• 将UnTracer与最先进的混合型fuzzer QSYM集成，实验结果表示QSYM UnTracer优于QSYM Clang和QSYM-QEMU。
• 我们开源我们的评估基准、外部基础设施和基于AFL的UnTracer的实施。

2.背景

2.1 fuzzing

测试用例生成：

• 基于语法
• 基于变异

对于大型应用程序，输入语法很复杂，而对于专业应用程序，输入语法很少可用。由于这些原因，大多数流行的fuzzer是基于变异的。

大多数基于变异的fuzzer是利用程序分析来决定测试用例的变异策略。directed fuzzer的目标是fuzz目标二进制文件中的特定位置；因此，它们优先处理似乎朝着这些位置靠近的变异测试用例。覆盖率引导fuzzer的目标是探索目标二进制代码的全部；因此，它们倾向于对到达新代码区域的测试用例进行变异。由于定向模糊的应用较窄，如污染跟踪或补丁测试，覆盖导向fuzzer的更受欢迎。

fuzzer根据它们所使用的程序分析程度进一步区分。

• 黑盒fuzzer只监视输入/输出执行行为（例如崩溃）。
• 白盒模糊器使用重型程序分析进行细粒度执行路径监视和约束求解。
• 灰盒模糊器是利用轻量级程序分析（如代码覆盖跟踪），是前两者之间的折衷。

2.2 基于覆盖率引导的fuzz

基于覆盖率引导fuzzer通过二进制插桩、系统仿真或硬件辅助机制跟踪执行期间的代码覆盖。所有覆盖引导fuzzer都基于代码覆盖的三个度量之一：基本块、基本块边或基本块路径。

代码覆盖的三种具体形式

• basic blocks
• basic block edges
• basic block paths

basic block edges表示实际控制流变化。可以将edge覆盖表示为一组（src，dest）元组，其中src和dest是basic block。以这种方式表示edge覆盖（即仅由basic block表示）允许从block覆盖推断edge覆盖。需要注意的是，这需要事先消除所有起始/结束基本块分别具有多个出/入的边。

2.3 追踪覆盖率的性能问题

VUzzer使用PIN动态（在运行时）插入黑盒二进制文件。AFL的QEMU用户模式仿真也是动态的，但是正如我们的实验所示（第六节），它比本机执行带来的开销高达1000%。为了解决动态重写必须实时转换基本块的弱点，Cisco Talos提供了静态二进制重写器AFL Dyninst。虽然先前的研究表明，在选定的二进制文件上，AFL Dyninst明显优于AFL-QEMU，但本文实验结果表明，性能差距并没有那么大。

阿姆达尔定律：仅仅系统的部分得到改进，整体系统可以得到的最大期望改进。

3.丢弃测试用例的影响

传统的覆盖引导的fuzzer依赖于“盲”（基于随机变异的）测试用例生成；增加覆盖的测试用例被保留并优先用于之后的变异，而绝大多数是不增加覆盖的测试用例将与其覆盖信息一起被丢弃。为了降低不会导致覆盖率增加的测试用例，一些白盒和灰盒模糊器使用“智能”测试用例生成。智能变异利用源分析（例如符号执行、程序状态和污点跟踪）生成更高比例的覆盖率增加测试用例。然而，还不清楚这些模糊器在测试用例生成上花费的时间是否比在测试用例执行/覆盖跟踪上花费的时间多得多，或者在增加覆盖率的测试用例中，智能变异的效果如何。

在本节中，我们研究了在两个流行的最新模糊器AFL（盲测试用例生成）和Driller（智能测试用例生成）中执行/跟踪非覆盖增加测试用例的性能影响。

AFL：AFL使用基于QEMU的黑盒二进制文件动态插桩或白盒二进制文件的汇编/编译时插桩跟踪测试用例覆盖率。

Driller在AFL的基础上加入了动态符号执行引擎，当模糊测试发生stuck时，使用动态符号执行去突破这些限制，生成满足fuzz需求的新输入，使得fuzz能够继续执行。

实验结果：尽管采用了不同的测试用例生成方法，但是覆盖引导模糊器AFL（blind）和Driller（smart）都花费了大部分时间来执行和跟踪非覆盖增加的测试用例。

4. COVERAGE-GUIDED TRACING

COVERAGE-GUIDED TRACING在测试用例生成和代码覆盖率跟踪之间引入了一个中间步骤：interest oracle。

interest oracle：是目标二进制文件的修改版本，其通过在每个未覆盖的基本块的开始处插入预先选择的软件中断。

只有产生了新覆盖的测试用例才会触发中断，从而在覆盖率增加时发送信号。

COVERAGE-GUIDED TRACING通过执行以下操作来增强传统的基于覆盖引导的fuzz：

1） Determine Interesting：根据interest oracle执行生成的测试用例。如果测试用例触发中断，则将其标记为覆盖率增加。否则，返回步骤1。

2） Full Tracing：对于每一个覆盖率增加的测试用例，跟踪执行它以获得其完整的代码覆盖率。

3） Unmodify Oracle：对于测试用例覆盖的每个新访问的基本块，从interest Oracle中移除相应的中断。

4） 返回步骤1。

• COVERAGE-GUIDED TRACING对整个fuzz过程的性能影响

考虑到随着fuzz的继续，原始二进制文件和oracle二进制文件以相同的速度执行不增加覆盖率的测试用例，COVERAGE-GUIDED TRACING接近0%的性能开销。

5. 实现

UnTracer包括一个interest oracle和一个tracer，基于afl，1200行代码：

• interest oracle：用于识别覆盖率增加的测试用例
• tracer：用于识别新覆盖

由于AFL使用了forkserver执行模型，因此我们将其合并到UnTracer的oracle和tracer二进制文件中。forkserver：通过fork（）启动新的进程，forkserver避免了重复的进程初始化，比传统的基于execve（）的执行速度快得多。

算法步骤如下：

在AFL完成其初始设置例程（例如，创建工作目录和文件描述符）（第1行）之后，UnTracer将插桩oracle和tracer二进制文件（第2-3行）；oracle二进制文件将获取forkserver，而tracer二进制文件将获取forkserver和基本块级插桩以进行覆盖率跟踪。由于oracle依赖块级软件中断来识别覆盖率增加的测试用例，unracer首先使用静态分析来识别所有基本块（第5行）；然后，unracer在oracle二进制文件中每个基本块的开头插入中断（第6-8行）。为了初始化oracle和tracer二进制文件进行fuzz处理，unracer启动各自的fork服务器（第9-10行）。在AFL的主模糊循环（第11-23行）中，UnTracer在oracle二进制文件（第13行）上执行AFL生成的每个测试用例（第12行）。如果任何测试用例触发一个中断，UnTracer会将其标记为覆盖率增加（第14行），并使用tracer二进制文件来收集其覆盖率（第15行）。然后，我们停止forkserver（第16行）来卸载每个新覆盖的基本块（第17-19行），删除它们相应的oracle中断；这确保了只有具有新覆盖率的未来测试用例才能正确地识别为覆盖率增加。在所有新覆盖的块都未修改之后，我们重新启动更新的oracle的forkserver（第20行）。最后，AFL完成其覆盖率增加的测试用例处理例程（例如，队列调度等）（第21行）和模糊转移到下一个测试用例（第12行）。

还有一些步骤的重复操作优化，hashmap，去除覆盖基本块的插入的中断中重复的基本块

6.实验

6.1 TRACING-ONLY 实验

本文的实验回答了以下问题：

1） UnTracer（coverage guided tracing，覆盖率引导跟踪）与跟踪所有测试用例相比如何？

2） 什么因素导致UnTracer的开销？

3） UnTracer的开销如何受到覆盖率增加的测试用例的影响？

6.2 混合fuzzer

最先进的混合fuzzer（如Driller和QSYM）将程序定向突变（如通过共扼执行）与传统的盲突变（如AFL）结合起来。混合方法以降低测试用例执行率为代价，在代码覆盖率方面提供了显著的提高。

实验结果：基于interest oracle的执行的性能优势远远超过了修剪和校准跟踪带来的性能缺陷。

7.讨论思考

A. UnTracer and Intel Processor Trace

因此，UnTracer的IPT变体将比我们基于Dyninst的实现快0%的开销，因为IPT的跟踪开销要低得多。

B、 合并边覆盖跟踪

UnTracer，我们实现的覆盖引导跟踪，使用基本块覆盖。
许多流行的fuzzer（例如AFL、libFuzzer、honggFuzz）使用边覆盖。

大多数使用边覆盖度量的fuzzer实际上依赖于基本的块级跟踪。在只跟踪基本块的情况下实现精确边覆盖的关键是删除临界边。临界边是控制流图中的边，其起始/结束基本块分别具有多个传出/传入边。临界边使得只知道执行过程中覆盖的基本块无法识别哪些边被覆盖。这会扩大覆盖范围，并导致fuzzer错误地丢弃覆盖范围增加的输入。

临界边问题的解决方案是通过插入一个中间基本块来分割每条边。插入的“虚拟”基本块由直接传输到原始目标基本块的控制流组成。

在性能方面，从基本块覆盖到边缘覆盖的影响不太明显。

C、 全面黑盒二进制支持

还未完全成功

8.结论

Fuzzing依赖于执行许多测试用例，希望找到覆盖率增加或产生崩溃的小子集。即使考虑到最近试图减少被丢弃的测试用例的数量，但它们仍然是常见的情况。另一个机会是，大多数代码本身是uninteresting，但必须执行才能获得interesting代码。因此，我们设想了一个比全速执行更快的未来，通过寻找跳过fuzz的其他“uninteresting”但常见的方面的方法是可能的。