Gramatron: effective grammar-aware fuzzing
Gramatron: effective grammar-aware fuzzing
复制标题
DOI：
10.1145/3460319.3464814
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Prashast Srivastava;Mathias Payer
中科院分区：
文献类型：
--
作者：
Prashast Srivastava;Mathias Payer
知道输入语法的模糊器可以使用语法感知的突变来探索更深层次的程序状态。现有的语法感知模糊器在合成复杂的错误触发器时是无效的，这是由于：（i）语法由于其结构而在输入生成期间引入采样偏差，以及（ii）当前用于解析树的变异算子执行局部化的小规模变化。Gramatron使用语法自动机与积极的突变算子相结合，以更快地合成复杂的bug触发器。我们构建语法自动机来解决抽样偏差。它重新构造语法，以允许从输入状态空间进行无偏采样。我们重新设计了语法感知的变异算子，使其更具侵略性，即，进行大规模的改变。与使用传统语法和解析树相比，Gramatron可以以高效的方式始终如一地生成复杂的bug触发器。Gramatron从头开始生成的输入具有更高的多样性，因为它们相对于现有模糊器的覆盖率高出24.2%。Gramatron使输入生成速度提高了98%，输入表示尺寸缩小了24%。我们重新设计的突变算子的攻击性提高了6.4倍，同时执行这些突变的速度仍然提高了68%。我们评估Gramatron在三个解释器与10个已知的错误组成的三个复杂的错误触发器和七个简单的错误触发器对两个鹦鹉螺变种。Gramatron可靠且更快地找到所有复杂的错误触发器。对于简单的bug触发器，Gramatron在七次中有四次优于Nautilus。为了证明Gramatron在野外的有效性，我们在三个流行的解释器上部署了Gramatron，进行了为期10天的模糊测试，发现了10个新的漏洞。
Fuzzers aware of the input grammar can explore deeper program states using grammar-aware mutations. Existing grammar-aware fuzzers are ineffective at synthesizing complex bug triggers due to: (i) grammars introducing a sampling bias during input generation due to their structure, and (ii) the current mutation operators for parse trees performing localized small-scale changes. Gramatron uses grammar automatons in conjunction with aggressive mutation operators to synthesize complex bug triggers faster. We build grammar automatons to address the sampling bias. It restructures the grammar to allow for unbiased sampling from the input state space. We redesign grammar-aware mutation operators to be more aggressive, i.e., perform large-scale changes. Gramatron can consistently generate complex bug triggers in an efficient manner as compared to using conventional grammars with parse trees. Inputs generated from scratch by Gramatron have higher diversity as they achieve up to 24.2% more coverage relative to existing fuzzers. Gramatron makes input generation 98% faster and the input representations are 24% smaller. Our redesigned mutation operators are 6.4× more aggressive while still being 68% faster at performing these mutations. We evaluate Gramatron across three interpreters with 10 known bugs consisting of three complex bug triggers and seven simple bug triggers against two Nautilus variants. Gramatron finds all the complex bug triggers reliably and faster. For the simple bug triggers, Gramatron outperforms Nautilus four out of seven times. To demonstrate Gramatron’s effectiveness in the wild, we deployed Gramatron on three popular interpreters for a 10-day fuzzing campaign where it discovered 10 new vulnerabilities.