Abstract
背景: Grammar Inference， 能够自动生成输入文法的技术。目前缺点: 一般是预先分析的，在fuzzing过程中的一些重要structures常常无法捕捉到
本文:
工具: GRIMOIRE
特点: 无需任何人工干预，无需预分析步骤，通过类似语法的组合和大量变异来生成高度结构化的测试用例
实验:
- GRIMOIRE比其他coverage-guided fuzzers更好
- 比现有的基于grammar-based的fuzzers更好
- 在实际程序上测出了19个memory corruption bugs, 11 CVEs
1. Intro
P1: AFL取得了成功；但是还是需要人工来设计某些cases；减少需要的领域知识有意义
P2: 语法语义有效性；
P3:
- 需要人工语法或者种子集的存在缺点：对没有文档的程序很难办；
- 有工作能通过静态分析推测语法，但是语法在运行中无法更正
本文工作：
P4:
前提：
- 可以用code coverage feedback来推测语法的结构属性
- 实践里并不需要准确正确的语法
- fuzzer的test case吞吐量很高，能够处理带一定噪声的语法
- 额外的噪音可测出程序的异常行为，反而会带来好处，比如能测错误处理不当
- 有时一些输入没在文档上及时标出来
P5:
本文与之前研究的区别：在fuzzing过程中合成语法
具体方法：
- 泛化方法：分析每个有新发现的输入，试着找到能够被替换或者重用的子序列
- 变异方法：从已有的输入中将这些fragments组合起来
P6: 工具GRIMOIRE
优点：
- 无需任何人工参与，也不需要种子集或者格式说明
- 不对程序或者程序环境做任何限定，因此也能用在闭源项目上（Q?)
P7:
实验A:
测试集：4个脚本语言解释器(mruby, PHP, lua, JavaScriptCore)，编译器(TCC), 汇编器(NASM)，数据库（SQLite），解析器(libxml)，SMT solver(Boolector)
效果：1. outperforms all existing coverage-guided fuzzers
实验B:
效果 1. 证明GRIMOIRE可以和现有的grammar fuzzer联用来增加效果
实验C:
效果 1. 与其他自动推测语法的方法相比，outperform
最终：找到19个memory-corrupted bugs, 11 CVEs
Ch2 Challenges in fuzzing structured languages
Fuzzing特点：大规模执行；随机探索状态空间；监视执行runtime
2.1 Blind Fuzzing
例子: RADAMSA, PEACH, Sulley, ZZUF
2.2 Coverage-guided fuzzing
使用轻量级程序覆盖率测量方法。
例子: AFL, ANGORA, QSYM, T-FUZZ, REDQUEEN
2.3 Hybrid Fuzzing
例子: SAGE, DRILLER, QSYM
VUzzer和ANGORA仅仅使用了taint tracking来完成轻量级的符号执行
缺点：不擅长处理整体结构上的约束
2.4 Coverage-based Grammar Fuzzing
例子: NAUTILUS, AFLSMART
2.5 Grammar Inference
例子: GLADE
方法:
- 用户给定一种黑盒oracle让GLADE知道是否语法有效
- GLADE将有效的输入集合转为最能表达这些有效输入的正则表达式
缺点:
- 耗时
- 需要人工提供oracle
- 生成的语法并不适合fuzzing
例子2: AUTOGRAM
假设在解析中被调用的函数反映了语法的Non-terminal Symbols
方法：使用源程序和taint tracking来推测语法
缺点：不适合recursive descent parsers
优点：无需人工oracle
例子3: PYGMALION
假设在解析中被调用的函数反映了语法的Non-terminal Symbols，而函数调用栈则能够反应语法的递归
方法：简化版符号执行
优点：无需标准输入集合
缺点：在解析器是表格表示的自动机的情况下无法工作
2.6 Shortcomings of Existing Approaches
3 Design
GRIMOIRE被设计为coverage-guided fuzzer上层额外的一步。
泛化(generalization):
- strip：用方框符号代替替换后不会带来新coverage的部分
- 将输入归约为能引起新覆盖的fragments
- 维护gaps（或者称为candidate positions, 即用方框代替的部分）的信息
例2：
为了获取if(x>1)的基本语法，可以将if(x>1)then x = 2 end用方框遮挡为 if(x>1)框（这里的代表可以放若干个空格）then框end
