REDQUEEN: Fuzzing with Input-to-State Correspondence
Abstract
虽然现在fuzzer取得了很多的进步，但是目前仍有两个常见的问题：magic numbers和(nested)checksum。通常使用污点追踪或符号执行之类的方法可以以昂贵的计算资源消耗为代价来解决这些问题，但是通常这些方法需要访问源代码、对环境的精确描述(例如，库调用或底层操作系统的行为)、平台指令集的确切语义。
Input-to-State Correspondence
Redqueen基于一个观察：大量程序中，输入的值在执行过程中会直接用于各种状态，即高度的Input-to-State对应。通过观察这些值，可以对要替换的偏移量（类似于轻量级的污点跟踪）以及要使用的值（类似于基于符号执行的方法）进行有根据的猜测。本文使用这一方法主要解决magic bytes和checksums问题。
A. Magic bytes
例：
if(u64(input)==u64("MAGICHDR"))
bug(1);
现有方法经常使用污点跟踪和符号执行，这两者都会带来一定的性能开销。另外，有些方法可以将多字节比较分解为多个单字节比较。
Redqueen思路：每次遇到新路径时，Redqueen都会hook所有比较指令并执行一次跟踪运行。如果遇到不同参数的比较，Redqueen将提取两个参数，并创建一个自定义突变$<pattern 7\rightarrow repl>$。
具体步骤
1. Tracing.当开始对新输入进行模糊处理时（进入kAFL的确定性阶段之前），Redqueen将执行一次运行，并hook所有比较指令并提取参数。包括一些由编译器发出的指令，用于替换普通比较指令或切换用例结构（通过计算跳转表中的偏移量）。
example 1: 比较指令检查输入中的前8个字节（被解释为无符号的64位值）是否等于字符串”MAGICHDR”。由于整数通常以little endian格式进行编码，因此实际比较中使用的值的ASCII表示为” deeStesT”和” RDHCIGAM”。
2. Variations.在运行时，我们不知道在比较之后检查了哪些标志。我们无法区分不同的比较运算，例如”低于”和”等于”。因此，Redqueen将一些变化应用于比较值，例如加减一。
作为这种启发式方法的副作用，本文根据经验发现，这种方法增加了触发off-by-one bug的可能性。
example 2: 示例代码中，我们对” RDHCIGAM”加1或减1，获得” RDHCIGAL”和” RDHCIGAN”。
3. Encodings.在到达实际的比较点之前，输入可能已经以不同的方式被处理了。为了处理输入编码/解码的最常见情况并创建更多的候选突变，Redqueen对突变应用了各种不同的编码，如：Zero/Sign Extend、Reverse、C-String、Memory、ASCII 。
example 3: Redqueen对当前的突变”RDHCIGAM”，”RDHCIGAL”应用小尾数编码，并获得” MAGICHDR”，” LAGICHDR”和” NAGICHDR”
4. Application.Redqueen使用突变模式$<pattern 7 \rightarrow repl>$来识别输入中要替换为突变repl的部分。这有两个优点：它可用于原子比较而无需进一步修改/hook目标，并且可大幅减少尝试替换的候选位置的数量。
example 4: 仅将输入”TestSeedInput”的子字符串”TestSeed”与”MAGICHDR”进行比较。
5. Colorization.本文设计了一种有效的过程来增加输入中的随机字节数，来提高输入的熵，从而大大减少要应用的剩余突变数。
example 5: 假设对示例代码的一个测试输入为：”ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ”，在这些突变中，我们会找到<ZZZZZZZZ→MAGICHDR>，带回到原输入，可以在许多(24)个不同位置应用此突变。在这种情况下，染色版本可以是任何随机字节串(例如”QYISLKFYDBYYSYWSIBSXEAXOKHNRUCYU”)。相应地，在重新运行时，相同的指令将产生突变：<QYISLKFY→MAGICHDR>，它仅适用于第一个位置。因此，我们仅在位置0产生一个候选突变。
6. Strings and Memory.除了上述整数比较，程序还经常使用函数比较两个字符串或字节数组的内容。为了克服这些构造，redqueen hook了所有函数调用。如果该函数至少有两个指针参数，则提取指向的前128个字节，并将它们与整作数相似对待。
7. Input Specific Dictionary.Redqueen将包含许多连续的非零或非0xff字节的值添加到特定字典中。以这种方式找到的字符串将仅在当前输入的havoc阶段使用。
B. Checksums
if(u64(input)==sum(input+8, len-8))
if(u64(input+8)==sum(input+16, len-16))
if(input[16]==’R’ && input[17]==’Q’)
bug(2);
现有的对策，如T-FUZZ，会patch这一部分checksum，即先对patched binary进行fuzz，当发现了interesting 行为时，再将checksum部分恢复回binary中尝试解决。
Redqueen根据input-to-state correspondence，使用以下过程替换TAINTSCOPE和T-FUZZ中使用的污点跟踪和符号执行：
- 确定看起来与checksum检查相似的比较(例如，一侧是input-to-state correspondence值，另一侧有规律地变化)。
- 将这个check替换为值为true的比较。
- 当对patched binary的fuzz发现了有趣的路劲时，进入验证模式。
- 在该模式下，使用上一节中介绍的技术来纠正所有patched的比较。 如果成功，我们将像以前一样继续该过程； 否则，删除此patch，以避免将来执行不必要的验证步骤。
具体步骤
1. Identification.这一步发生在魔术字节的处理过程中。使用下列启发式过滤方法筛选与checksum有关的比较：
- 能够使用相同的编码在所有输入中找到mutation pattern的左侧。
- 两个参数都不是立即值。
- pattern在着色阶段发生变化（这类似于TAINTSCOPE使用的约束：该值取决于许多输入字节）。
这种方法有一个很大的缺点：删除的指令可能是相关的边界检查，而删除它们可能会带来误报（即错误的新覆盖），甚至导致程序崩溃。因此，Redqueen引入了一个验证阶段，以清除潜在的误报并确定必须修补的比较指令。
2. Patching.在确定了一组可疑的哈希检查之后，Redqueen用与成功比较有相同副作用的补丁替换指令。
3. Verification.在一个输入的一次完整的fuzz测试之后，这些作用在patched binary上的输入可能无法在unpatched binary上显示预期行为。在验证阶段，Redqueen尝试通过应用从patched指令获得的基于输入状态的变异来固定这些无效输入。然后，在未打补丁的真实目标上执行固定输入。如果它们仍然触发新的覆盖，则将固定输入写入实际队列。
Implementation Details
Redqueen基于该团队之前的工作——kAFL。
A. kAFL Fuzzer
kAFL是一个与操作系统无关，受AFL启发，反馈驱动的内核fuzzer，使用硬件加速的跟踪功能Intel PT来获取覆盖率信息，而无需检测目标。
Redqueen在此基础上，修复了Intel PT数据包解码中的许多错误，并增加对Ring 3 fuzz的支持。
B. Comparison Hooking
Redqueen依靠硬件辅助的虚拟机断点来提取Input-to-State Correspondence。运行时每当disassembler 遇到一条有趣的类似比较指令时，都会存储其地址，以便可以在下一个Redqueen分析阶段放置一个挂钩。当运行到断点时，参数将被提取并保存到缓冲区中，以供后续的fuzzing logic使用。断点被命中几次后将被删除以限制其对性能的影响。
此处hook的指令不仅包含cmp指令，还包括call指令和减法指令(编译器通常用减法来代替cmp)。
C. Colorization
Redqueen尝试使用随机值替换尽可能多的字节，而不更改执行路径（更准确地说，是AFL bitmap的hash）。这增加了输入中的熵，因此减少了可应用的观察到的pattern的位置数。
在本文的实施中，Redqueen将搜索限制为最多1000个步骤。 即使对于文件系统驱动程序目标，此方法也很有效，最小输入大小为64KB。
Data: input is the uncolored input
Result: A version of input that has a significantly higher entropy
ranges ← (1... len(input))
original hash ← get bitmap hash(input)
while rng = pop biggest range( ranges ) do
backup ← input[rng]
input[rng] ← random bytes()
if original hash 6= get bitmap hash(input) then
add(ranges, (min(rng)... max(rng)/2))
add(ranges, (max(rng)/2 + 1 ... max(rng)))
input[rng] ← backup
D. Instruction Patching
一旦fuzzing logic从Input-to-State Correspondence数据中计算出了候选哈希比较指令的列表，Redqueen就用伪造的比较指令替换它们，这些指令总是产生true。 在本文实现中，Redqueen使用指令cmp al，al，因为它是x86指令集体系结构上可用的最小比较指令。
Redqueen使用KVM和QEMU调试工具在VM内部的内存中应用这些补丁。
E. Input Validation and Fixing
验证和固定初步结果算法：
Data: input is the preliminary input with unsatisfied checksums
Result: Either (None, cmps) if the comparisons cmps could not be fixed or (in f, None) if the new, fixed input in f satisfies all comparisons
in f←input
for cmp in reverse(patched cmps) do
in f ← try fix value for cmp(cmp, in f)
if cmp ∈ get broken cmps(in f) then
return (None, {cmp})
dependencies[cmp] ← get cmps influcenced()
if get broken cmps(in f) 6= ∅ then
in f←input
ordered cmps ← topological sort(dependencies)
for cmp in ordered cmps do
in f ← try fix value for patch(cmp, in f)
if get broken cmps(in f) 6= ∅ then
return (None, get broken cmps(in f))
return (in f, None)
该算法通过反复应用各个突变并观察所得的Input-to-State Correspondence，反复尝试固定所有比较。
在某些情况下，比较之间存在顺序关系，在固定输入时我们需要保留这些顺序。 通常，如果文件格式的标头包含对文件完整内容的校验和，并且文件内的某些块也受校验和保护，则会遇到这种情况。在这种情况下，我们必须先修复内部校验和，才能正确计算外部校验和。
F. Linux User Space Application Loader for KAFL
本文通过Linux ring 3加载程序扩展了kAFL。该加载程序重新实现了AFL fork服务器。
Redqueen的目标是二进制文件，因此Redqueen使用LD PRELOAD将fork服务器功能注入到目标的启动例程中。
为了支持KVM-PT中的ring 3跟踪，Redqueen将模型专用寄存器IA32 RTIT CTL MSR中的User bit置1。
为了将fuzzer扩展为支持32位目标，Redqueen向QEMU-PT添加了32位模式反汇编，以支持32位模式Intel PT跟踪数据的解码。
Evaluation
research questions:
- 基于Input-to-State Correspondence的技术是否足够通用，即是否可以跨各种目标和环境？
- 基于Input-to-State Correspondence的技术的结果与其他更复杂的技术（例如基于污点跟踪或符号执行的方法）相比如何？
- 在实际的模糊测试场景中，基于Input-to-State Correspondence的技术有哪些优点？
具体评估内容略。
Limitations
Redqueen给自己的定位是提出了一个轻量级的解决方法or替代方法。在本文中，Redqueen认为在大部分情况下，即使其他更复杂的fuzzer能够获取源代码，Redqueen的性能依旧优于这些fuzzer。
本文中给出了一些实验中遇到的Redqueen没有优势的示例：
- 包含压缩数据的PNG文件格式，解码器在执行过程中将其解压缩。
- 在binutils测试集的某些程序中，来自输入的字符串用于索引哈希图，返回一个整数，并在程序的后续运行中使用。
- LAVA-M数据集中的base64实用程序应用了base64解码。本文中的Redqueen实现尚未支持Base64编码。
在上述情况中，输入都不与转换后的状态相对应。因此Redqueen并不能有效解决这些情况之后的约束。
本文指出，1、2的情况，对于Concolic execution也难以解决；而情况3，Redqueen可以轻松地添加base64的编码器。
另外本文提出，可以将Redqueen作为使用更重量级的工具之前的第一步工具。
笔记
- Angora和Redqueen的paper中，对LAVA-M的fuzz结果中出现了这样一个情况：两个工具挖掘出了原作者未标注出来的bug。感觉这一点可以稍微去看一下LAVA这个测试集。
