模糊测试与符号执行的云端之旅

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

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

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

GRR：最快的模糊测试器

GRR是一个高速全系统模拟器，用于对程序二进制文件进行模糊测试。一次模糊测试“活动”涉及执行程序数千甚至数百万次，每次使用不同的输入。希望通过用海量输入轰炸程序，能够触发导致程序崩溃的漏洞。

注意：GRR的发音要伴随两个拳头举向空中

在DARPA的网络大挑战中，我们达到了网络级规模，在仅仅24小时内执行了数百亿次的输入变异和程序执行！以下是我们构建此模糊测试器时面临的挑战及解决方案。

吞吐量

通常，程序模糊测试分为离散步骤。样本输入被提供给输入“变异器”，生成输入变体。每个变体分别针对程序进行测试，希望程序会崩溃或执行新代码。GRR将这些步骤内部化，同时完全消除了磁盘I/O和程序分析启动时间，这些在其他常见工具的模糊测试活动中占据了大部分时间。

透明性

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

可重现性

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

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

符号执行作为一个主题难以深入理解。符号执行器“推理”程序中的每条路径，某处有个定理证明器，然后……漏洞就从另一端掉出来了。

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

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

CPU指令操作寄存器和内存。寄存器是超快但小的数据存储单元的名称。通常，寄存器保存四到八个字节的数据。而内存可以非常大；对于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二进制文件一起使用的教程。当时，我们对PIN进行了基准测试，发现甚至在我们开始优化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的演示中一直是讨论的话题，我们怀疑这些工具在不久的将来可能会再次出现。