模糊测试器与符号执行器的云端邂逅

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

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

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

GRR：极速模糊测试器

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

在DARPA网络大挑战赛中，我们实现网络级规模，在短短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位程序可寻址高达4GiB内存。PSE的指令模拟器也操作寄存器和内存，但不仅能存储“原始”字节——还能存储表达式。

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

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

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

全面性
任意程序二进制文件可能执行x86CPU数千条指令中的任何一条。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演示中的讨论话题，我们预计这些工具在不久的将来会再次出现。