模糊测试器与符号执行器走进云端 - Trail of Bits博客

GRR：极速模糊测试器

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

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

吞吐量优化

传统模糊测试通常分为离散步骤：输入变异器生成输入变体，每个变体单独测试程序。GRR将这些步骤内部化，彻底消除磁盘I/O和程序分析启动时间——这些在其他工具中占用了大部分测试时间。

透明性保障

GRR通过完美隔离实现透明性，确保被测试程序无法观察或干扰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"的条件会将B符号的真路径约束到[0,10)范围，假路径约束到[10,256)范围。

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

PSE开发与扩展中的挑战

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

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

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

可扩展性：PSE使用Python编写，易于修改。但修改符号执行器具有挑战性——难以确定修改位置和如何获得正确数据可见性。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设计旨在每个可能的模拟指令处尝试使程序崩溃——例如使用符号内存知识访问任何可能的无效数组式内存访问，而不仅仅是尝试解决到达无约束路径的问题。在资格赛中，angr与GRR+PSE正面交锋，我们发现了更多漏洞。此后，我们改进了PSE以支持用户交互、具体和符号执行以及污点跟踪。

回归展望

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

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