Smart Greybox Fuzzing 阅读笔记

2021-09-27 本文已影响0人佩玖吟

摘要

对于处理复杂文件格式的应用，CGF 随机变异并不能产生有效的文件。本文介绍了 smart grebox fuzzing(SGF)，利用种子文件的高级结构化表示来生成新文件。与位级别变异相比，创新地定义了虚拟文件结构上的变异操作。本文引入了一种新的基于有效性的能量调度策略，使SGF能够花费更多的时间生成更有可能通过程序解析阶段的文件，这可能会暴露处理逻辑中更深层次的漏洞。

Introduction

CGF 的一个很重要的局限就是缺乏输入结构感知。变异是 bit-level 的，但是很多应用处理高度结构化的输入，如图片、音频等，所以不太可能影响文件结构的变化。有效文件 bit-level 的突变可能产生无效文件，从而在程序解析时就被拒绝。

为了解决这个问题，AFL 使用 dictionary，VUZZER 通过动态污点分析和控制流分析来推断输入数据的位置和类型。但是都不能从文件里面增删一个完整的trunk。

和 CGF 相比，一些 smart blackbox fuzzers 尽管输入结构感知，并且可以利用文件格式模型来构造新的有效问卷，但是灰盒的覆盖率反馈是需要的，否则效果甚至不如 AFL。

本文提出了 SGF，在虚拟文件结构上进行变异，根据种子的有效性来进行能量调度，这样可以尽可能生成有效文件通过解析阶段。

贡献：使得灰盒模糊测试输入格式感知。

SMART GREYBOX FUZZING

Virtual Struction

SGF 的有效性来源于变异操作的设计。

操作需要充分利用从种子输入中提取出的结构信息
操作需要统一，以支持所有 chunk-based 文件格式（如 MP3，PNG 等）
所有操作需要是轻量级的，以保持灰盒模糊测试的效率

所有的输入文件可以被表示为一棵树，内部节点称为 chunks，叶子节点称为 attributes

为了构建虚拟结构，需要文件格式规范和一个解析器。

Smart Mutation Operators

基于虚拟结构，有三种变异操作：

smart deletion

对种子文件 $s$ ，任意删除一个 chunk $c$
smart addition

将种子文件 $s_2$ 中的任一 chunk $c_2$ 加到种子文件 $s_1$ 的 chunk $c_1$ 后面，其中要满足 $c_1$ 和 $c_2$ 的父节点类型相同。
smart splicing

种子文件 $s_1$ 任一 chunk $c_1$ ，种子文件 $s_2$ 任一 chunk $c_2$ ，其中 $c_1$ 和 $c_2$ 类型相同，用 $c_2$ 替换 $c_1$ 。

挑战：

保持结构完整

bit-level 突变操作很难保证生成输入结构的完整性，主要通过结构化突变操作来解决。但是，结构化突变操作不保证结构完整性，严格强制结构的完整性并不总是可取，而要通过解析的有效性是必要的。
保持语义完整

任何变异的模糊测试的第二个关键挑战是数据字段间的隐式约束。修改一个字段的字节可能需要智能修改另一个字段的字节，如校验和。SGF 可能通过几种方式解决这个问题，首先，在插入的片段中维护这些约束，其次，一些约束，如校验和，可以时候修复（如，使用 Peach fixups）

Region-based Smart Mutation

Stacking Mutations

为了生成有趣的测试输入，同时使用 structural(high level) 和 bit-level(low level) 的突变操作是有意义的。

Fragment- and Region-based Mutation

AFLSMART 使用规范将文件分解为片段，片段是文件解析树中的子树。AFLSMART 使用 Peach Cracker 组件中的解析表为每个 chunk 和 attribute 派生 start index、end index 和 type。

Deferred Parsing

如果 SGF 为每个种子构建虚拟结构，效率会大大降低。本文通过概率 $p$ 来构建虚拟结构， $p$ 取决于发现新路径的时间， $t$ 为上次发现新路径到现在的时间， $s$ 为当前的种子输入（虚拟结构还未被创建）
$prob_{virtual}(s)=min(\frac{t}{\epsilon}, 1)$
如果 $t$ 大于阈值 $\epsilon$ ，概率就为 100%。

启发：AFL 可能会生成许多无效输入，重复通过几个短路径（通常是无效文件被拒绝），如果生成更多此类无效输入，那么很难发现新路径， $t$ 就会增加，超过阈值 $\epsilon$ 后允许构建虚拟结构。如果可以遍历新路径， $t$ 保持较小，我们不会产生创建虚拟结构的开销。因此，Deferred Parsing 允许 AFLSMART 在不牺牲 AFL 效率的情况下实现输入格式感知。

Validity-based Power Schedule

种子 $s$ 的能量调度 $p_v(s)$
$p_v(s)=\left\{ \begin{aligned} 2p(s) && if \space v(s)\ge 50\% \space and \space p(s)\le \frac{U}{2} \\ p(s) && if \space v(s)< 50\% \\ U && otherwise \end{aligned} \right.$
$p(s)$ 是之前的能量调度（如 AFL）， $U$ 是可以被 AFL 分配的最多能量。

FILE FORMAT SPECIFICATION

对于高度结构化的复杂文件格式，手工构建是耗时且容易出错的。

insights:

Chunk inheritance

很多 chunks 有一个通用的结构，所以我们首先建模一个通用的 chunk，包含所有的 chunk 共享的 attribute，然后再根据每个 chunk 进行修改。
Specification completeness

SGF 支持 chunk level 的变异操作，所以不需要指定 chunk 里面的所有 attribute。
Relaxed constraints

chunk 里面可能包含很多约束，如 identifier 必须为一个常数，chunk size 和实际长度要一致。本文使用 Choice 来放松约束，在 Choice 里面的 chunk 可以任意出现，在不阻止解析文件的同时，发现更多边界条件。
Reusability