白泽带你读论文丨NAUTILUS: Fishing for Deep Bugs with Grammars

$\text{[math]}$

NAUTILUS: Fishing for Deep Bugs with Grammars

开源项目地址: https://github.com/RUB-SysSec/nautilus

本文发表在NDSS 2019，第一作者是来自波鸿大学的Cornelius Aschermann。

1. 主要内容

Fuzzing那些需要有着复杂结构输入的程序，例如语言解释器，一直是学术界的一个难点。传统的基于突变的Fuzzer例如AFL，往往需要一个从互联网爬取的语料库，但这些语料库往往只包含了这些语言常用的语法，较难触发罕见的bug。而另一类基于生成的fuzzer则基于一定的模板或语法，往往能够生成结构性较强的输入，在fuzz语言解释器上取得了较好的效果。比较这两类fuzzer，作者认为前者使用了代码覆盖作为回馈，而后者能够生成高度结构化的输入，因此将这两种思路结合，提出了一个综合了语法和回馈的fuzzer——Nautilus。

2. 背景

上下文无关文法是编译原理中的一个重要的概念。几乎所有程序设计语言都是通过上下文无关文法来定义的。基于生成的fuzzer在fuzz这些语言的解释器时，往往就会利用这种语法来生成一串合法的输入。相对应地，突变也是以语法树上的节点为基础进行的，与AFL等传统fuzzer在字符串上进行突变不同。

3. 设计与实现

NAUTILUS工具的工作流程图如下，在传统的基于生成的fuzzer的基础上加入了插桩和回馈的步骤，即首先进行插桩，然后根据语法生成input，之后基于一些规则对input进行突变，最后将生成的input送入待测程序观察是否触发bug，根据插桩获得的反馈来判断有无到达新的路径，进而决定是否保留这个input进行下一轮的fuzz。

3.1插桩阶段

为了能够在fuzzing的过程中获得代码覆盖信息，从而能够得到反馈以指导fuzzer生成更好地输入，NAUTILUS在程序源代码上进行了插桩，其插桩方式与AFL相似。

3.2 Fuzz阶段

在Fuzz阶段，NAUTILUS首先会根据给定的语法生成一定数量的input。在有多种规约规则的时（即语法书上一个子树有多种替换方案），NAUTILUS提出了两种方案来进行选择：随机选择或根据可能生成的子树的数量来尽可能选择可能生成更多子树的规则。在最后的评估中，作者对两种方案的效率进行了测试，发现在对输入进行去重后，两种方案的效率其实相差不多。之后，NAUTILUS会尝试对输入进行缩减，在保证相同代码覆盖率的同时尽可能地缩短输入，以节省测试时间。缩短完成后，NAUTILUS就会尝试对输入进行突变，大部分突变都是在语法树上进行的，例如随机替换一个节点、将节点按照规则规约，将规则里存在递归的部分重复一定次数，替换输入中的一个子树为另一个输入中的一个合法子树等，使这些输入在保证语法正确的前提下尝试探索新的程序路径。另外地，与AFL类似，NAUTILUS也会进行字节翻转、加减和替换等。如下图所示，这种突变可能会将语法树中一个合法的节点改掉，但同样也可能会触发程序的错误，达到fuzzer的目标。