模糊测试与符号执行的云端碰撞

在程序中寻找漏洞十分困难，而自动化这一过程更是难上加难。我们直面这一挑战，开发出两个生产级漏洞发现系统：GRR（高吞吐量模糊测试器）和PySymEmu（PSE，支持具体输入的二进制符号执行器）。

从宏观角度看，模糊测试是一种简单粗暴但效果惊人的方法，而符号执行则是涉及定理证明器判断程序“正确性”的复杂方法。从这个视角看，GRR是肌肉，PSE是大脑。但二者并非对立——这些工具是互补的，我们使用PSE为GRR提供种子输入，反之亦然。

让我们深入探讨设计和构建GRR与PSE时面临的技术挑战。

GRR：全球最快的模糊测试器

GRR是我们用于模糊测试程序二进制文件的高速全系统模拟器。一次模糊测试“战役”需要执行程序数千甚至数百万次，每次使用不同的输入。希望通过海量输入轰炸程序，最终触发导致程序崩溃的漏洞。

在DARPA网络大挑战期间，我们实现了web级规模——在短短24小时内执行了数百亿次的输入变异和程序执行！以下是开发该模糊测试器时面临的挑战及解决方案：

吞吐量优化 传统程序模糊测试分为离散步骤：样本输入交给输入“变异器”生成变体，每个变体分别测试程序是否崩溃或执行新代码。GRR将这些步骤内部化，完全消除了磁盘I/O和程序分析启动时间——这些在其他常见工具的模糊测试战役中占用了大部分时间。

透明性保障 透明性要求被测试程序无法观察或干扰GRR。GRR通过完美隔离实现透明性，能在其64位地址空间的内存中“托管”多个32位x86进程。每个托管进程的指令在执行时动态重写，在保持操作和行为透明性的同时确保安全性。

可重现性 GRR同时模拟CPU架构和操作系统，从而消除非确定性来源。GRR记录程序执行，使得任何执行都能被忠实重放。其强大的确定性和隔离保证让我们能够将GRR的优势与PSE的复杂性相结合。GRR可以对运行中的程序进行快照，使PSE能够从给定程序执行的深处启动符号执行。

PySymEmu：二进制符号执行的博士级工具

符号执行作为一个课题难以深入。符号执行器“推理”程序中的每条路径，涉及定理证明器…最终漏洞会从另一端掉出来。

高层次看，PySymEmu（PSE）是一种特殊的CPU模拟器：它为几乎每条硬件指令都提供了软件实现。当PSE符号执行二进制文件时，它实际上执行的是如果CPU本身执行代码时硬件会完成的所有操作。

PSE在一项非正统的科学实验中探索程序生与死的关系

CPU指令操作寄存器和内存。寄存器是超高速但小型数据存储单元的命名。通常寄存器保存4-8字节数据，而内存可以非常庞大——32位程序可寻址高达4 GiB内存。PSE的指令模拟器也操作寄存器和内存，但它们不仅能存储“原始”字节——还能存储表达式。

消费某些输入的程序每次执行通常做相同的事情。这是因为“具体”输入会触发代码中的相同条件，导致相同循环执行。PSE操作符号输入字节：最初可以取任何值的自由变量。完全符号输入可以是任何输入，因此代表所有输入。当PSE模拟CPU时，if-then-else条件对最初无约束的输入符号施加约束。询问“输入字节B是否小于10”的if-then-else条件会将B的符号约束在真路径的[0,10)范围和假路径的[10,256)范围。

if-then-else就像程序执行中的岔路口。在每个这样的岔口，PSE会询问其定理证明器：“如果我沿着岔口的一条路径走，是否还有满足该路径附加约束的输入？”PSE会分别跟随每个可行路径，忽略不可行路径。

那么我们在创建和扩展PSE时面临了哪些挑战？

全面性覆盖 任意程序二进制文件可以执行x86 CPU提供的数千条指令中的任何一条。PSE为数百条x86指令实现了模拟函数。在无法提供指令模拟的情况下，PSE回退到自定义的单指令“微执行器”。实践中，这种设置使PSE能够全面模拟整个CPU。

规模扩展 符号执行器试图通过在每个if-then-else条件处分叉，并沿每条路径以某种方式约束符号来跟踪程序中所有可行路径。实践中，程序中的可能路径数量是指数级的。PSE通过选择给定执行目标的最佳执行路径，并将程序状态空间探索过程分布到多台机器来处理可扩展性问题。

内存管理 符号执行产生表示简单操作的表达式，如将两个符号数字相加，或沿if-then-else代码块的一条路径约束符号的可能值。PSE优雅处理指向内存的地址是符号的情况。通过符号地址访问的内存可能指向任何地方——甚至指向“好”和“坏”（即未映射）内存。

可扩展性 PSE使用Python编程语言编写，易于修改。然而，修改符号执行器具有挑战性——很难知道在哪里进行更改，以及如何获得对数据的正确可见性以使更改成功。PSE包含智能扩展点，我们已成功用于支持具体符号执行和漏洞利用生成。

卓越性能衡量

GRR和PSE与最佳公开可用工具相比如何？

GRR对比 GRR既是动态二进制翻译器又是模糊测试器，因此适合与AFLPIN（AFL模糊测试器和Intel PIN动态二进制翻译器的混合体）比较。在网络大挑战期间，DARPA提供了有关如何将PIN与DECREE二进制文件结合使用的教程。当时我们基准测试发现，在我们开始优化GRR之前，它已经比PIN快两倍！

更重要的比较指标是漏洞发现能力。AFL的变异引擎智能有效，特别是在选择下一个要变异的输入方面。GRR将Radamsa（另一个过于智能的变异引擎）内部化作为其众多输入变异器之一。最终我们可能还会集成AFL的变异器。在资格赛期间，GRR与集成到Driller漏洞发现系统中的AFL正面交锋。我们的GRR+PSE组合发现了更多漏洞。除这一数据点外，正面比较将具有挑战性且耗时。

PySymEmu对比 PSE最容易与KLEE（LLVM位码的符号执行器）或angr二进制分析平台比较。LLVM位码与x86指令相去甚远，因此这是苹果与橘子的比较。幸运的是我们有McSema——我们开源且积极维护的x86到LLVM位码翻译器。我们对KLEE的体验大多是负面的；它难以使用、难以修改，并且仅在Clang编译器产生的位码上表现良好。

Angr使用Valgrind VEX中间表示的定制版本。使用VEX使angr能够在许多不同平台和架构上工作。许多angr示例涉及逆向工程CTF挑战而非利用挑战。这些逆向工程问题通常需要手动干预或状态知识才能进行。PSE设计用于在每个可能的模拟指令处尝试使程序崩溃。例如，PSE将使用其符号内存知识访问任何可能的无效类数组内存访问，而不仅仅是尝试解决到达无约束路径的问题。在资格赛期间，angr与GRR+PSE正面交锋，我们发现了更多漏洞。此后，我们改进了PSE以支持用户交互、具体和具体符号执行以及污点跟踪。

未来展望

自动化发现真实程序中的漏洞十分困难。我们通过开发两个生产级漏洞发现工具GRR和PySymEmu来应对这一挑战。

GRR和PySymEmu最近在我们CRS的演示中成为讨论话题，我们预计这些工具在不久的将来可能会再次出现。