00 - About
作者：Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik and Thorsten Holz
01 – Why
近年来，基于模糊的抽象自动化软件测试经历了一次复兴，特别是反馈驱动模糊以其在有限输入语料库下高效地进行随机测试的能力而闻名（such afl）。尽管取得了许多进展，但有两个常见的问题是 magic numbers 和 checksums，这些问题通常使用 taint tracking 和symbolic execution 等计算开销较大的方法来克服这些障碍。不幸的是，这样的方法通常需要访问源代码、对环境的需求较高(例如，库调用或底层操作系统的行为)或平台指令集的确切语义。
因此，本文介绍了一种轻量级的、但非常有效的方法来替代 taint tracking 和 symbolic
execution，以方便和优化最先进的反馈模糊处理，这种模糊处理很容易扩展到大型二进制应 用程序和未知环境。
02 – What
本文提出了一种新的基于 tracing 的方法，该方法基于一种假设：在运行时，部分 input 会直接传入到 memory（内存）或 registers（寄存器）中进行比较，于是在 input 与当前 status 存在极强的 input-to-status 关联性，这个方法首先在程序执行时追踪并识别比较指令，然后判断特定位置 input 的修改是否会对应程序 status（memory，registers）的修改，最后通过修改 fuzzing 中的输入，来确定修改是否给 fuzzing 带来了新的 code coverage。
本文基于这个方法实现了一个原型:REDQUEEN。其速度高于 KLEE,VUzzer,AFLFast,并且找到了 LAVA-M 未发现的 bug。同时 REDQUEEN 还发现了 2 个 linux 文件系统的 bug 和 55 个不同用户程序中的 bug。
03 – How
本文提出了一种新的模糊方法，该方法基于程序具有较强的输入状态对应关系。对于非常多的程序，在执行过程中，输入值直接用于不同的状态。通过观察这些值，可以对要替换哪些偏移量(类似于非常轻量级的 taint tracking)和要使用哪些值(类似于基于 symbolic
execution 的方法)进行有根据的猜测。
于是，作者利用了这种关系来处理 magic numbers 和 checksums 的问题。
Magic bytes
对于 magic numbers 问题，作者举了一个例子：
对于反馈驱动的模糊器（AFL 等）来说，这些构造很难解决，因为它们不太可能猜测出满意的 input。如这个例子中是 64 位输入 MAGICHDR，现有的一些方法经常使用 magic numbers 和checksums，这两种方法都会产生一定的性能开销。
对于 REDQUEEN 来说，这个问题很容易解决。每次遇到新路径时，REDQUEEN 都会挂起所有比较指令并执行一次跟踪运行。如果遇到与不同参数的比较，REDQUEEN 取两个参数并创建一个定制的突变 <pattern →repl> ，具体如下所述：
- Tracing
在 fuzzing 一个新的 input 时，进行一次 tracing，并且 hook 所有的比较指令（包括一些 switch 结构和比较函数）并提取参数。
Eg：将上例中的 input 设置为"TestSeedInput"，比较指令检查输入的前 8 个字节（解释为无符号 64 位值）是否等于字符串"magichdr"的 64 位无符号解释，由于整数通常以小端格式编码，因此比较中使用的最终值的 ASCII 表示形式是"deestest"和"rdhcigam"。
- Variation
在运行时，由于不知道比较后检查了哪些标志，因此不能区分不同的比较操作，如"小于" 和"等于"。因此，REDQUEEN 对比较值进行了一些变化，如加和减 1，但这种方法增加了触发 off-by-one 错误的概率
Eg：在上例中，对"RDHCIGAM"加减 1，得到"RDHCIGAL"和"RDHCIGAN"。
- Encodings
在达到理想比较效果之前，很可能以不同的方式处理了输入。为了处理输入和解码的最常见情况，并创造更多的变异候选，REDQUEEN 对变异使用了不同的编码，如：Zero/Sign Extend、Reverse、C-String、Memory、ASCII 等。
Eg：对当前的突变"RDHCIGAM"、"RDHCIGAL"应用小端编码，并获得 "MAGICHDR"、"LAGICHDR"和"NAGICHDR"。
- Application
REDQUEEN 使用突变<pattern →repl>的模式来标识输入中要替换 为突变 repl 的部分， 这种方法有两个好处：它可以用于原子比较，而不需要进一步 modification/hooking 目标， 并且可以大大减少尝试替换的候选位置的数量。
Eg：输入"TestSeedInput"的子字符串"TestSeed"与"MAGICHDR"进行比较。只用生成的突变 替 换 这 部 分 。 产 生 了 新 的 测 试 用 例 "MAGICHDRInput" ，" LAGICHDRInput" 和和"NAGICHDRInput"等。
-
Colorization
在初始输入中增加输入中的随机字节数以提高熵，让初始输入更有随机性，更像
"asdmohaoianxb",而不是"zzzzzzzzzzz"。 -
Strings and Memory.
对 memcmp 函数做了特定的特化处理。 -
Input Specific Dictionary.
将包含许多连续非零或非 0xff 字节的值添加到特定的字典中。
以上步骤的部分演变过程如下图所示：
Checksum
另一个 fuzzer 面对的挑战就是如何处理 checksum。本文也举了一个例子。
现有的方法，如 FLAYER、TAINTSCOPE 或 T-FUZZ 都依赖于相同的思想：删除硬检查并在稍后修复它们。
TAINTSCOPE 和 T-FUZZ 都自动检测关键检查，然后，一旦发现 interesting 的行为， 就使用 symbolic execution 来修复检查。
本文提出了的方法步骤如下：
具体步骤如下：
- Identification
本文用下面的规则来筛出有关于 checksum 的比较。- 在 bypass magic bytes 的过程中找到所有 mutation 规则左侧的 pattern
- 比较的两个参数都不是即时值 * 着色阶段的模式更改。在"着色"时，随着 input 的变化，patten 对应的 repl 也在变化。（值取决于输入字节的多少）
这样的规则并不完善，删除的指令可以是相关的边界检查，这可能带来一些 false positive，但 REDQUEEN 在将一个新输入加入队列时，会删除所有相关的 patch，可以避免 false positive。
-
Patch
在确定了一组可疑的哈希检查之后，用具有与成功比较相同副作用的 patch 替换指
令。 -
Verification
在 fuzzing 过程中生成的所有新输入在一个 real target 上，用之前在 magic bytes 部分提到的规则进行修正，如果修正后的输入能够在 real target 上触发新的 code coverage，就保留，否则就把对应的 patch 删除。
04 – Implementation details
kAFL Fuzzer
KAFL 是一个与操作系统无关的、受 afl 启发的反馈驱动内核 fuzzer，本文基于 KAFL 来实现 REDQUEEN，总共添加和更改了大约 10k 行代码，这些变化中的很大一部分并不是由本文中提出的技术。这些更改大部分是为了添加对 ring 3 fuzzing 的支持、在 KAFL 中供 VMI 功能以及修复 bug。此外，这些数字还包含大量用于评估和调试目的的代码。
Comparison hook
本文依靠硬件辅助的虚拟机断点来提取 input to state correspondence，每次运行时反汇编程序遇到一个 interesting 的类似结构的比较时，它的地址都会被存储起来，以便在下一个 REDQUEEN 分析阶段放置一个 hook，在 REDQUEEN 阶段，断点被放置在所有 interesting 的指令上，当一个断点被命中时，参数被提取并保存到一个缓冲区中，以供日后 fuzzing 逻辑使用。
这里的指令不仅仅是 cmp，也包括 call 指令。
Colorization
REDQUEEN 尽量用随机值替换尽可能多的字节，而不更改执行路径，这会增加输入中的熵，从而减少可应用观察到的模式的位置数。
这可以使用二进制搜索方法来完成，该方法通常会在少量执行（通常为几百次）内收敛。具体算法如下：
Instruction Patching
REDQUEEN 利用kvm 和qemu 的功能将比较指令替换为cmp al,al，同时用Intel Processor
Tracing（PT）来去掉那些产生意外的情况（Sometimes even benign C code and common compilers emit assembly that jumps in the middle of instructions）。
Input Validation and Fixing
本文使用如下算法来验证和修正初步结果（输入中的比较指令）：
该算法通过重复应用单个突变并观察 input-to-state correspondences 的结果，迭代地尝试修复所有比较。
Linux User Space Application Loader for KAFL
本文通过一个 Linux ring 3 加载器扩展了 KAFL，以针对其他 user space fuzzers 进行评估，证明该方法是通用的和健壮的。
扩展内容主要如下：
- 重新实现了 AFL fork server
- 使用 LD PRELOAD 将 fork server 功能注入到目标的启动例程中
- 在特定于模型的寄存器 ia32 rtit ctl msr 中设置了用户位
- 在 qemu-pt 中添加了 32 位模式分解，以支持 32 位模式 intel-pt 跟踪数据的解码
05 – Result
作者在本文章提了三个 RQ，具体如下：
- 基于 input-to-state correspondence 技术是否足够通用，能否在不同的目标和环境中工作?
- 与其他更复杂的技术（如基于 taint tracking 或 symbolic execution 的方法）相比， input-to-state correspondence 技术的结果如何？
- 在现实世界的模糊场景中，我们对基于 input-to-state correspondence 技术的输入提供了哪些改进？
为此，作者首先在一系列不同的环境中、LAVA-M,CGC 测试集上测试 REDQUEEN 的表现，接着在实际环境中运行，找到一系列真实软件的 bug，最后和其他以 kfal 为基础的工具比较了性能。
实验表明， 本文的方法比目前所有的方法都有显著的优势。其次， 作者演示了REDQUEEN 能够在各种经过良好测试的软件包中发现新的 bug。REDQEEEN 方法总共在两个不同的 Linux 文件系统驱动程序中发现了 10 个 bug，在16 个用户空间程序和软件库中发现了 55 个 bug。
到目前为止，本文获得了 16 个 cve, 4 个还在等待中。
总的来说，本文作者提出了一种非常简单的提升 fuzz 效率的方法，即基于一个简单的假设 —— 一个程序的输入很多时候被直接用来进行逻辑判断，所以在 tracing 中可以找到对应数据。这种假设虽然可能不能包含所有实际情况，但总体来说还是比较通用的，效率不错。