利用Honeybee和Intel处理器进行覆盖率指导的模糊测试

近日我们发布了一款名为Honeybee的覆盖率指导的Fuzzer，该Fuzzer使用Intel Processor Trace（IPT）技术记录了程序控制流。以前，由于捕获系统和跟踪分析效率低下，对IPT的性能并没有发挥出最大作用。我的研究集中于应对这些挑战，以使基于IPT的模糊测试变得切实有效。

https://github.com/trailofbits/Honeybee

IPT是一种异步记录程序控制流的硬件功能，在记录时仅花费8-15％的开销。但是，将IPT用作模糊覆盖机制并不可行，除了高度实验性的二进制覆盖解决方案外，因为源代码工具通常可提供更好的性能。Honeybee解决了这一限制，使IPT的捕获速度大大提高，分析速度提高了数百倍。因此，现在我们有了覆盖率指导的模糊测试，其性能与源码级别的覆盖率测试相比有时甚至更快。在这里，我将描述Honeybee背后的开发过程以及其设计的思路。

0x01 研究背景

IPT是特定于Intel的处理器功能，可用于一次记录几分钟所有进程的完整控制流历史，而对性能的影响最小。IPT大大改进了英特尔的较旧的硬件跟踪系统，例如Branch Trace Store，其性能损失可能超过100％。更好的是，IPT支持通过特定过程或虚拟地址范围对跟踪目标进行精细选择。

像IPT这样的硬件机制对于安全研究人员而言尤其诱人，因为它是闭源的，未经修改的目标二进制文件提供代码覆盖率信息。一个鲜为人知的事实是，IPT不仅比任何现有的黑盒方法（如QEMU，中断）都快得多，而且IPT还应该比源码插桩工具更快。

覆盖率检测工具通过对大型覆盖率缓冲区的频繁，随机写入来破坏各种CPU缓存，从而抑制了运行时性能。源代码级检测还抑制了许多重要的编译时优化，例如自动矢量化。此外，由于大多数程序的多线程性质，检测代码需要在原子位图上进行原子操作，这极大地限制了流水线吞吐量。

IPT应该在闭源和开源目标上都可以工作，而覆盖范围生成策略应保持不变，并且只产生最小的8-15％的性能损失。

0x02 研究现状

不幸的是，性能下降8-15％并不能说明全部问题。IPT的捕获开销很低，但分析开销却不低。为了捕获硬件上的长时间跟踪，IPT使用各种技术来最小化每个跟踪存储的数据量。一种技术是仅记录无法从底层二进制静态分析中轻易获得的控制流信息，例如已采用/未采用的分支和间接分支目标。尽管此优化假设IPT解码器可以访问底层程序二进制文件，但此假设通常是正确的。（例如，参见图1。）

IPT是一种非常密集的二进制格式。为了展示存储的信息，我在图1中将其转换为更具可读性的格式。数据包类型在左列，数据包有效负载在右列。

示例IPT跟踪显示IPT如何在程序执行过程中最大程度地减少存储的数据。

1. 在程序以0x7ffff7f427ef执行时开始跟踪。

2. 该程序命中条件分支并接受它。（第2行中的第一个！。）

3. 该程序将命中两个条件分支，并且不接受它们。（第2行中的.。）

4. 该程序命中条件分支，不接受它。（第2行中的最后一个！）

5. 该程序命中条件分支并接受它。（第4行。）

6. 程序到达一个间接分支，这时它跳转到最后一个指令指针，并用低2个字节替换为0x3301。

7. 该程序命中条件分支并接受它。

8. 程序继续进行，没有其他条件/间接分支，直到指令指针的最后四个字节为0xf7c189a0为止，此时由于程序退出或与过滤器不匹配的另一段代码开始执行而停止跟踪。

尽管提供了所有跟踪数据，但仍有大量信息被忽略。跟踪提供其开始的虚拟地址，最终的条件分支以及是否采用它们。但是，没有提供无条件的和控制流转移（即call和jmp指令）和有条件的分支目标。因为1）从未记录过非分支代码，2）条件分支表示为单个位，3）间接分支仅通过更改指令指针来表示，所以这减小了跟踪大小。

那么如何从这部分数据中重构出真正的控制流程呢？IPT解码器可以将跟踪数据与基础二进制文件配对，然后从跟踪起始地址“遍历”二进制文件。当解码器遇到无法确定的控制流转移时（例如条件分支），它会查询跟踪。跟踪中的数据指示已采取/未采取的分支以及间接控制流转移的结果。通过遍历二进制和跟踪直到跟踪结束，解码器可以重建整个流程。

但这是IPT的难题：尽管捕获速度很快，但表面上看代码却并非如此，因为解码器必须在每个解码步骤中分解并分析多个x86-64指令。尽管拆卸和分析的开销对于调试和概要分析方案而言不是问题，但它严重地阻碍了Fuzzing吞吐量。不幸的是，这种昂贵的分析从根本上是不可避免的，因为如果不分析原始程序就无法解码。

0x03 提升IPT的性能

在对英特尔参考IPT解码器libipt进行性能分析时，我注意到在跟踪分析过程中，有超过85％的CPU时间用于解码指令。鉴于必须通过遍历二进制文件查找IPT数据以进行控制流传输，因此这并不奇怪。但是，在指令解码期间花费大量时间实际上是个好消息。

为什么？Fuzzer需要针对同一二进制文件对大量Trace进行解码。连续分析一个二进制文件的单条Trace的指令可能是合理的，但是对于同一二进制文件，数百万次重新分析同一指令是非常浪费的。

声称是最快的IPT解码器（稍后会详细介绍）的开源解码器libxdc试图使用快速运行缓存来解决此问题。使用运行时缓存和其他性能编程技术，libxdc的运行速度比Intel的参考解码器快10至40倍，这表明缓存非常重要。

我对libxdc的批评是，它的动态指令高速缓存以两种方式引入了不必要和昂贵的开销。首先，动态缓存通常需要花费很多资源来查找，因为它需要计算目标的哈希值并确保缓存实际上是命中对象。这给整个算法中最热的部分之一带来了更多的开销和复杂性，并且不容忽视。

其次，坦率地说，更糟糕的是，通常期望动态缓存填充。即使是最好的缓存策略也将导致将来的工作：由于被Fuzzer永远不会仅将代码作为目标，因此任何被撤回的指令最终都将需要重新解码。每次逐出缓存都会造成重复的工作量和解码器性能的损失

我的想法是引入一个静态的，提前生成的高速缓存，该高速缓存保存所有可能需要的IPT解码数据。高速缓存将在多个线程之间共享而不会带来任何损失，并且无需哈希或锁定即可进行访问。通过完全消除二进制分析和缓存访问开销，我可以比libxdc更快地解码跟踪，这是因为我的解码器只会做更少的工作。

Honeybee架构。

遵循Honeybee的主题，我将这些静态的，提前生成的缓存称为“配置单元”，因为它们需要创建工作，但只需要创建一次即可。为了创建Honeybee Box，我创建了hive_generator，它使用ELF可执行文件并捕获解码跟踪可能需要的信息。hive_generator搜索所有控制流指令，并生成所有基本块的编码，并且代码可以继续执行。

首先，这种编码是对数据高速缓存友好的，因为不仅块的大小等于高速缓存行的大小，而且编码后的块以与原始二进制文件相同的顺序存储，这是一个很小的重要细节。这意味着Honeybee的解码器可以充分利用原始二进制文件的缓存局部性优化，因为编译器通常会将相关的基本块彼此靠近。在动态高速缓存中，例如在libxdc中，这通常是不可能的，因为高速缓存的哈希函数是根据设计将相邻块发送到随机位置的。这会影响性能，因为它会从CPU的数据高速缓存中找出有意义的数据。

另一个重要的功能是，块以按位友好的格式编码，因此Honeybee可以使用专有的高吞吐量ALU操作来处理压缩的块。这种设计使几个关键操作完全无分支-例如确定一个块是以直接分支，间接分支还是条件分支结束。将此与高吞吐量的ALU操作相结合，可以避免许多代价高昂的分支错误预测。

这些更改似乎相对来说是微不足道的，但是我希望它们能够结合起来，从而在当前的最新技术libxdc上取得可观的性能提升。

0x04 Honeybee解码器

为了比较Honeybee的解码器和Intel解码器的性能，我在100 kb到45 MB大小的二进制文件中运行了从几十千字节到1.25 GB不等的跟踪。测试进行了25次，并且我验证了这两个解码都对相同的跟踪文件使用了相同的控制流路径。

比较Honeybee的解码速度以提高速度。

这些测试显示出令人鼓舞的结果（图3）。在像clang这样的大型程序上，Honeybee优于Intel的解码器，它和libxdc是一个数量级。

就上下文而言，此测试套件中最大的跟踪“ honey_mirror_1 / clang_huge.pt”为1.25GB，源于对复杂的静态分析程序的跟踪，该程序分解了整个35MB的clang二进制文件。

Honeybee仅需3.5秒即可完成英特尔参考解码器在两分半钟内完成的工作，这是44倍的改进！

在这种情况下，Honeybee只需6.6微秒即可完成英特尔的参考编码器所需的451微秒的工作。

将Honeybee与honggfuzz集成。

现在，实际上将这种新的覆盖机制集成到Fuzzer中。我之所以选择Google的honggfuzz，是因为它是模块化的，尤其是因为它实际上已经有了使用英特尔参考解码器的基于IPT覆盖率的另一种方法。我的计划是淘汰英特尔的解码器，将Honeybee固定在适当的位置，并提升速度。但是，这比我预期的要复杂。

挑战在于Linux收集IPT数据，因为主线内核实际上已经对perf中内置的IPT提供了支持。但是我发现Honeybee需要清理IPT数据的复杂而激进的过滤机制暴露了perf中的稳定性和性能问题。

性能没有明显的提升，而且非常不稳定。Honeybee所使用的复杂配置会引发性能方面的严重错误，这可能会导致CPU配置错误，并且需要完全重新引导系统才能从锁定中恢复。可以理解的是，这两个问题最终使得在捕获与Honeybee有关的任何模糊测试任务中捕获IPT数据时都无法使用。

我为IPT编写了一个名为“ honey_driver”的小型内核模块，该模块专门针对模糊测试进行了优化。尽管这个新的内核模块肯定没有perf功能强大，并且可能存在安全隐患，但是honey_driver却非常快，它使用户空间客户端能够以很少的开销快速重新配置跟踪并分析结果。

因此，有了这小部分自定义代码，honggfuzz就可以使用Honeybee的IPT数据了！

0x05 提升模糊测试效率

Fuzzer性能测量很复杂，因此有许多更可靠和确定的方法来测量性能。作为一个粗略的基准测试，我坚持使用四种不同的覆盖策略对一个小型HTML解析器进行模糊测试。然后，在记录测试期间的平均执行次数之前，我允许honggfuzz使用所选的覆盖率技术对二进制文件进行模糊处理。

将Honeybee与Hongfuzz进行比较。

实验中的第一个样本工具没有任何覆盖面。通过将随机输入输入测试程序，它的运行速度与honggfuzz可以在此二进制文件上运行的速度一样快。在这种配置下，honggfuzz每秒平均执行239K次。在我的系统中，这是相当快的，但是仍然肯定会受到模糊目标的CPU性能的限制。

接下来，我通过在未启用其他功能的情况下使用检测编译器编译目标来测试honggfuzz的源代码级软件检测。与没有覆盖的基准相比，这导致平均每秒执行98K次，或效率降低41％，这是由于缺少编译器优化，许多函数调用，昂贵的锁定以及高速缓存抖动而导致的模糊测试时的普遍接受和预期的损失。

在进行软件检测之后，我们将介绍更有趣的覆盖技术。如前所述，honggfuzz支持使用libipt进行处理器跟踪以进行分析，并使用未经过滤的perf数据进行IPT捕获。但是，honggfuzz现有的IPT支持不会生成完整甚至正确的覆盖范围信息，因为honggfuzz仅从跟踪中提取间接分支IP，而完全忽略任何条件分支。此外，由于不使用perf进行过滤，因此honggfuzz会为过程中的每段代码生成覆盖率，包括诸如libc之类的无趣的库。

即使有了这些捷径，honggfuzz的现有IPT也只能平均每秒执行1.1K次（大约是理论最大值的一半）。由于覆盖率数据不正确，因此无法与软件工具进行真正的比较，因为它可能会更快地找到更困难的路径。但是，实际上，差距是如此之大，鉴于先前确定的perf和libipt的性能问题，该问题不太可能解决大部分开销。

最后，我们有Honeybee及其定制的解码器和捕获系统。与现有的honggfuzz实现不同，Honeybee对整个轨迹进行解码，因此能够生成完整，正确的基本块和边缘覆盖范围信息。Honeybee平均每秒执行17.1万次执行，与基线相比，性能下降仅为28％。

这不应该令人感到震惊，因为IPT仅具有8-15％的记录时间开销。这样就剩下了基线总执行时间的14-21％来处理IPT数据并生成覆盖范围。鉴于Honeybee解码器的出色性能及其快速解码轨迹的能力，完全有理由假设Honeybee数据处理的总开销可能会增加29％的性能损失。

我分析了Honeybee的覆盖范围，并确认它运行正常并正确处理了所有数据。因此，我很高兴地说Honeybee能够比传统的软件检测方法更快，更有效地Fuzzing 闭源和开源软件！

0x06 改进工作

如果这些模式更普遍地适用，那么对于那些需要进行源码模糊测试的人来说，这可能意味着极大的性能提速。但是，更令人兴奋的是，对于那些需要执行黑盒模糊测试并且一直依赖低速且不可靠的工具（例如QEMU仪器，Branch Trace Store（BTS））的用户来说，这绝对是一个绝佳的加速，因为这意味着他们可以在没有做出任何重大妥协的情况下，以与有源码相同或更高的速度进行模糊测试。这种高性能解码在模糊测试之外很有用，因为它支持许多新颖的应用程序，包括更高级的调试器和性能分析工具。