Un-bee-lievable Performance: Fast Coverage-guided Fuzzing with Honeybee and Intel Processor Trace

Allison Husain, UC Berkeley
March 19, 2021
fuzzing, internship-projects, research-practice

今天我们发布了一款名为Honeybee的实验性覆盖引导模糊测试工具，它使用Intel处理器追踪（IPT）技术记录程序控制流。此前，由于捕获系统的问题和低效的追踪分析，IPT一直因性能严重不足而受到质疑。我的冬季实习重点就是解决这些挑战，使基于IPT的模糊测试变得实用且高效。

IPT是一种硬件功能，可异步记录程序控制流，记录时的开销仅为8-15%。然而，除了高度实验性的仅二进制覆盖解决方案外，将IPT用作模糊测试覆盖机制并不实用，因为源代码插桩通常能提供更好的性能。Honeybee解决了这一限制，使IPT的捕获速度显著提升，分析速度快了数百倍。因此，我们现在可以实现覆盖引导的模糊测试——即使在没有源代码的情况下——其性能与源代码级覆盖插桩相当，有时甚至更快。在这里，我将描述Honeybee的开发过程及其设计概述。

How it started…

IPT是Intel特有的处理器功能，可用于以最小的性能损失记录任何进程的完整控制流历史，每次记录时间可达数分钟。IPT大幅改进了Intel旧的硬件追踪系统，如分支追踪存储（Branch Trace Store），其性能损失可能超过100%。更好的是，IPT支持通过特定进程或虚拟地址范围进行粒度选择追踪目标。

像IPT这样的硬件机制对安全研究人员特别有吸引力，因为它可以为闭源、未修改的目标二进制文件提供代码覆盖信息。一个较少被认识到的事实是，IPT不仅比任何现有的黑盒方法（如QEMU、中断或二进制提升）快得多，而且应该比插入源代码级插桩更快。

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

IPT应适用于闭源和开源软件，覆盖生成策略无需更改，且仅产生8-15%的性能损失。告诉你，这真是令人惊叹！

How it’s going…

不幸的是，8-15%的性能损失并不能说明全部问题。虽然IPT的捕获开销低，但其分析开销并不低。为了在商用硬件上捕获长追踪，IPT使用各种技术来最小化每条追踪存储的数据量。一种技术是仅记录无法从底层二进制文件的静态分析中轻易获得的控制流信息，如分支是否被采用和间接分支目标。虽然这种优化假设IPT解码器可以访问底层程序二进制文件，但这一假设通常是正确的。（例如，参见图1。）

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

示例IPT追踪，展示IPT如何最小化程序执行期间存储的数据。

• 追踪开始于程序在0x7ffff7f427ef处执行。
• 程序遇到条件分支并接受它。（第2行的第一个!。）
• 程序遇到两个条件分支但未接受它们。（第2行的. .。）
• 程序遇到条件分支但未接受它。（第2行的最后一个!。）
• 程序遇到条件分支并接受它。（第4行。）
• 程序遇到间接分支，此时它跳转到最后一个指令指针，其低两个字节被替换为0x3301。
• 程序遇到条件分支并接受它。
• 程序继续执行，没有其他条件/间接分支，直到指令指针的最后四个字节为0xf7c189a0，此时追踪停止，因为程序要么退出，要么开始执行另一段不匹配过滤器的代码。

尽管提供了所有追踪数据，但仍有许多信息被省略。追踪提供了其起始虚拟地址、最终的条件分支以及它们是否被采用。然而，无条件和无可争议的控制流转移（即call和jmp指令）和条件分支目标并未提供。这减少了追踪大小，因为：1）非分支代码从不记录；2）条件分支用单个位表示；3）间接分支仅通过指令指针的变化表示。

那么，如何从这些部分数据中重建真实控制流？IPT解码器可以将追踪数据与底层二进制文件配对，并从追踪起始地址“遍历”二进制文件。当解码器遇到无法轻易确定的控制流转移（如条件分支）时，它会查阅追踪。追踪中的数据指示哪些分支被采用/未采用以及间接控制流转移的结果。通过遍历二进制文件和追踪直到追踪结束，解码器可以重建完整流程。

但这就是IPT的陷阱：虽然捕获速度快，但遍历代码显然不快，因为解码器必须在每个解码步骤反汇编和分析多个x86-64指令。虽然反汇编和分析的开销对于调试和分析场景不是问题，但它严重阻碍了模糊测试的吞吐量。不幸的是，这种昂贵的分析基本上是不可避免的，因为不分析原始程序就无法解码追踪。

但是……这就结束了吗？IPT模糊测试的美好承诺只是……一个梦想？一个纯粹的幻觉？告诉我不是这样！

Making IPT faster!

在分析Intel的参考IPT解码器libipt时，我注意到超过85%的CPU时间在追踪分析期间用于解码指令。这并不奇怪，因为IPT数据必须通过遍历二进制文件寻找控制流转移来解码。然而，指令解码期间花费的大量时间实际上是个好消息。

为什么？模糊测试器需要针对同一二进制文件解码大量追踪。对单个二进制文件的单条追踪持续分析指令可能是合理的，但为同一二进制文件数百万次重新分析相同的指令是极其浪费的。如果你的“嘿，我们可能应该使用缓存”的感觉在刺痛，你完全正确！当然，指令解码缓存的重要性并不是一个新发现。

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

但我认为我可以做得更好。我对libxdc的批评是，其动态指令缓存以两种方式引入了不必要且昂贵的开销。首先，动态缓存通常有昂贵的查找，因为它需要计算目标的哈希并确保缓存实际上是命中的。这在整个算法最热的部分引入了更多开销和复杂性，不容忽视。

其次，更糟糕的是，动态缓存通常预期会填充和驱逐旧结果。即使是最好的缓存驱逐策略也会导致未来的工作：任何被驱逐的指令最终都需要重新解码，因为模糊测试器从不只针对代码一次。这会在每次缓存驱逐时产生重复工作和解码器性能损失。

我的想法是引入一个静态的、提前生成的缓存，保存所有IPT解码可能需要的所有数据。缓存可以在多个线程之间无惩罚地共享，并且可以在没有昂贵哈希或锁定的情况下访问。通过完全消除二进制分析和缓存访问开销，我可以比libxdc显著更快地解码追踪，因为我的解码器只需做更少的工作。

The Honeybee architecture.

遵循Honeybee的主题，我将这些静态的、提前生成的缓存命名为“hives”，因为它们需要工作来创建，但只需创建一次。为了制作hives，我创建了hive_generator，它消耗ELF可执行文件并捕获解码追踪可能需要的信息。hive_generator搜索所有控制流指令，并生成所有基本块及其代码执行可能继续的位置的极其紧凑的编码。这个新设计有两个重要特性值得讨论。（完整细节可在Github上找到。）

首先，这种编码对数据缓存友好，因为不仅块的大小是缓存行的大小，编码块还按原始二进制的相同顺序存储，这是一个小而重要的细节。这意味着Honeybee的解码器可以充分利用原始二进制的缓存局部性优化，因为编译器通常将相关的基本块放在彼此附近。这在动态缓存（如libxdc）中通常不可能，因为缓存的哈希函数设计上会将相邻块发送到随机位置。这对性能有害，因为它会从CPU的数据缓存中驱逐有意义的数据。

另一个重要特性是块以位友好的格式编码，因此Honeybee可以专门使用高吞吐量ALU操作处理压缩块。这种设计使几个关键操作完全无分支——如确定块是否以直接、间接或条件分支结束。将其与高吞吐量ALU操作结合，避免了许多代价高昂的分支预测错误和流水线清除。

这些变化似乎相对微不足道，但我希望它们能结合起来，相对于当前最先进的技术libxdc，带来可观的性能提升。

Honeybee decoder benchmarks

为了比较Honeybee解码器与Intel参考解码器的性能，我运行了从几十KB到1.25 GB的追踪，二进制文件大小从100 KB到45 MB。测试进行了25次，我验证了两种解码器对相同追踪文件遍历了相同的控制流路径。

比较Honeybee的解码速度与libipt。

这些测试显示了有希望的结果（图3）。在大型程序如clang上，Honeybee比Intel的参考解码器和libxdc快一个数量级（在一种情况下快两个数量级）。

作为背景，此测试套件中最大的追踪“honey_mirror_1/clang_huge.pt”为1.25GB，源自一个复杂的静态分析程序的追踪，该程序反汇编了整个35MB的clang二进制文件。

Honeybee仅需3.5秒完成Intel参考解码器需要两分半钟的工作，这是44倍的改进！这是追踪解码时离开与等待时喝一口水之间的区别。

这种差异在小追踪上更加明显，这些小追踪更类似于模糊测试负载，如“html_fast_parse/6_txt.pt”。在这种情况下，Honeybee仅需6.6微秒完成Intel参考解码器需要451微秒的工作。一个数量级的改进！

Integrating Honeybee with honggfuzz.

现在将这种新的覆盖机制实际集成到模糊测试器中。我选择了Google的honggfuzz，因为它是模块化的，而且值得注意的是，它实际上已经有一个使用Intel参考解码器的基于IPT覆盖的慢速且部分损坏的版本。我的计划是简单地移除Intel的解码器，将Honeybee固定到位，并获得美妙的加速。然而，这比我想象的更复杂。

挑战在于Linux通常如何收集IPT数据，这本应相当简单，因为主线内核实际上在perf中内置了对IPT的支持。但我发现，Honeybee需要清理IPT数据的复杂和激进过滤机制暴露了perf中的稳定性和性能问题。

这是有问题的。不仅perf一开始就不太快，而且它高度不稳定。Honeybee使用的复杂配置触发了perf中的严重错误，可能导致CPU配置错误，需要完全系统重启才能从锁定中恢复。可以理解，这两个问题最终使perf无法用于捕获任何与Honeybee相关的模糊测试任务的IPT数据。

但是，正如我母亲所说，如果你想把事情做好，有时你只需要自己动手。追随她的脚步，我写了一个名为“honey_driver”的小型内核模块用于IPT，专门为模糊测试优化。虽然这个新内核模块肯定比perf功能少，且可能存在安全风险，但honey_driver非常快，并允许用户空间客户端快速重新配置追踪并以低开销分析结果。

因此，通过这一小部分自定义代码，honggfuzz准备使用来自Honeybee的IPT数据！

Fuzzer benchmarks

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

比较Honeybee与源代码级插桩。

实验中的第一个竞争者没有任何覆盖。我认为这是基线，因为它本质上是honggfuzz通过向测试程序提供随机输入所能运行的最快速度。在此配置中，honggfuzz平均每秒达到239K次执行。在我的系统上下文中，这相当快，但仍然 certainly 受模糊测试目标的CPU性能限制。

接下来，我测试了honggfuzz的源代码级软件插桩，通过使用插桩编译器编译我的目标，没有启用其他功能。这导致平均每秒98K次执行，或与无覆盖基线相比效率下降41%，这是模糊测试时普遍接受和预期的惩罚，由于错过的编译器优化、许多函数调用、昂贵的锁定以及由于 essentially 随机写入覆盖位图导致的缓存破坏。

在软件插桩之后，我们进入更有趣的覆盖技术。如前所述，honggfuzz支持使用libipt进行分析和使用未过滤的perf数据进行IPT捕获的处理器追踪。然而，honggfuzz现有的IPT支持不生成完整甚至可能正确的覆盖信息，因为honggfuzz仅从追踪中提取间接分支IP，并完全忽略任何条件分支。此外，由于使用perf时未采用过滤，honggfuzz为进程中的每一段代码生成覆盖，包括无趣的库如libc。这导致位图污染。

即使有这些捷径，honggfuzz现有的IPT只能平均达到每秒1.1K次执行（大约理论最大值的0.5%）。由于不准确的覆盖数据，无法与软件插桩进行真正比较，因为它可能更早找到了更困难的路径。然而，实际上，差距如此巨大，鉴于先前建立的perf和libipt的性能问题，这样的问题不太可能占大部分开销。

最后，我们有Honeybee及其自定义解码器和捕获系统。与现有的honggfuzz实现不同，Honeybee解码整个追踪，因此能够生成完整、正确的基本块和边缘覆盖信息。Honeybee平均达到每秒171K次执行，与基线相比仅性能下降28%。

这不应令人震惊，因为IPT仅有8-15%的记录时间开销。这留下基线总执行时间的14-21%来处理IPT数据并生成覆盖。鉴于Honeybee解码器的惊人性能及其快速解码追踪的能力，完全有理由假设Honeybee的数据处理总开销可能加起来达到29%的性能惩罚。

我分析了Honeybee的覆盖，确认其操作正常并正确处理所有数据。因此，我很高兴地说，Honeybee（至少在这种情况下）能够比传统软件插桩方法更快、更高效地模糊测试闭源和开源软件！

What’s next?

虽然声称推翻行业标准模糊测试方法非常令人兴奋，但这些方法尚未经过严格测试或验证，无论是在大规模还是跨大量模糊测试目标上。然而，我可以证明，Honeybee在模糊测试许多不同的大型开源项目（如libpcap、libpng和libjpegturbo）时，要么更快，要么至少能与软件插桩相抗衡。

如果这些模式更普遍适用，这可能意味着那些需要执行源代码级模糊测试的人将获得巨大的加速。但更令人兴奋的是，这对于那些需要执行黑盒模糊测试并一直依赖慢速和不可靠工具（如QEMU插桩、分支追踪存储（BTS）或二进制提升）的人来说，是一个绝对美妙的加速，因为它意味着他们可以以等于或大于有源代码时的速度进行模糊测试，而无需做出任何严重妥协。然而，即使在模糊测试之外，Honeybee仍然是一个经过验证且极其快速的IPT解码器。这种高性能解码在模糊测试之外也有用，因为它支持许多新颖应用，从实时控制流完整性强制到更高级的调试器和性能分析工具。

Honeybee是一个非常年轻的项目，仍在GitHub上的家中积极开发。如果你对IPT、模糊测试或任何组合感兴趣，请随时通过Twitter（@ezhes_）或电子邮件（allison.husain@berkeley.edu）与我联系！

Acknowledgments

如前所述，IPT吸引了许多研究人员的目光，因此，自然，许多人尝试将其用于模糊测试。在开始我自己的项目之前，我研究了其他人的研究，从他们的工作中学习，并看看我可以在哪些方面提供改进。我首先要感谢PTrix（PTrix: Efficient Hardware-Assisted Fuzzing for COTS Binary）和PTfuzz（PTfuzz: Guided Fuzzing With Processor Trace Feedback）的作者，因为他们提供了关于如何围绕IPT数据构建模糊测试器的重要见解。此外，我要感谢libxdc背后的团队，因为他们快速的IPT数据包解码器构成了Honeybee中数据包解码器的基础。最后，我要大大感谢Trail of Bits的团队，特别是我的导师Artem Dinaburg和Peter Goodman，感谢他们在这个项目中的支持，并让我作为实习生度过这个冬天！

如果你喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News