摘要
对于处理复杂文件格式的应用，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
对种子文件
，任意删除一个 chunk
-
smart addition
将种子文件
中的任一 chunk
加到种子文件
的 chunk
后面，其中要满足
-
smart splicing
种子文件
挑战：
-
保持结构完整
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 为每个种子构建虚拟结构，效率会大大降低。本文通过概率 来构建虚拟结构，
取决于发现新路径的时间，
为上次发现新路径到现在的时间，
为当前的种子输入（虚拟结构还未被创建）
如果 大于阈值
，概率就为 100%。
启发：AFL 可能会生成许多无效输入，重复通过几个短路径（通常是无效文件被拒绝），如果生成更多此类无效输入，那么很难发现新路径， 就会增加，超过阈值
后允许构建虚拟结构。如果可以遍历新路径，
保持较小，我们不会产生创建虚拟结构的开销。因此，Deferred Parsing 允许 AFLSMART 在不牺牲 AFL 效率的情况下实现输入格式感知。
Validity-based Power Schedule
种子 的能量调度
是之前的能量调度（如 AFL），
是可以被 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
