精读:REDQUEEN: Fuzzing with Input-to-State Correspondence

00 - About

作者:Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik and Thorsten Holz

01 – Why

近年来,基于模糊的抽象自动化软件测试经历了一次复兴,特别是反馈驱动模糊以其在有限输入语料库下高效地进行随机测试的能力而闻名(such afl)。尽管取得了许多进展,但有两个常见的问题是 magic numbers 和 checksums,这些问题通常使用 taint tracking 和symbolic execution 等计算开销较大的方法来克服这些障碍。不幸的是,这样的方法通常需要访问源代码、对环境的需求较高(例如,库调用或底层操作系统的行为)或平台指令集的确切语义。

1.png

因此,本文介绍了一种轻量级的、但非常有效的方法来替代 taint tracking 和 symbolic
execution,以方便和优化最先进的反馈模糊处理,这种模糊处理很容易扩展到大型二进制应用程序和未知环境。

02 – What

本文提出了一种新的基于 tracing 的方法,该方法基于一种假设:在运行时,部分 input 会直接传入到 memory(内存)或 registers(寄存器)中进行比较,于是在 input 与当前 status 存在极强的 input-to-status 关联性,这个方法首先在程序执行时追踪并识别比较指令,然后判断特定位置 input 的修改是否会对应程序 status(memory,registers)的修改,最后通过修改 fuzzing 中的输入,来确定修改是否给 fuzzing 带来了新的 code coverage。

2.png

本文基于这个方法实现了一个原型: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 问题,作者举了一个例子:

3.png

对于反馈驱动的模糊器(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 字节的值添加到特定的字典中。

以上步骤的部分演变过程如下图所示:

44.png

Checksum

另一个 fuzzer 面对的挑战就是如何处理 checksum。本文也举了一个例子。

4.png

现有的方法,如 FLAYER、TAINTSCOPE 或 T-FUZZ 都依赖于相同的思想:删除硬检查并在稍后修复它们。

TAINTSCOPE 和 T-FUZZ 都自动检测关键检查,然后,一旦发现 interesting 的行为, 就使用 symbolic execution 来修复检查。

本文提出了的方法步骤如下: