模糊测试与符号执行的云端融合

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

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

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

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

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

注意：GRR的发音需要举起双拳

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

吞吐量

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

透明性

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

可重现性

GRR仿真CPU架构和操作系统，从而消除非确定性来源。GRR记录程序执行，使任何执行都能被忠实重放。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二进制文件结合使用的教程。当时，我们对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的演示中成为讨论话题，我们预计这些工具在不久的将来可能会再次出现。