《Skyfire: Data-Driven Seed Generation for Fuzzing》论文阅读

一句话

针对处理高度结构化输入的程序(比如解析XML的引擎程序)，本文提出了一种种子生成方法，通过大量样本训练带概率的上下文有关文法，通过训练好的文法，自动生成符合程序输入要求的种子，用于后续的Fuzz。

0x00 背景介绍

模糊测试是一种自动化的测试技术，它通过生成非预期的输入，监视程序的异常，挖掘程序的漏洞。

在fuzz的过程中，fuzzer对输入结构的理解会影响fuzz的效果。
怎么理解这句话呢？我们来看一个例子：
假设下图是XSLT引擎解析XML文档的过程。输入是XML文档，过程大概可以分为三个部分：句法分析（Syntax parsing）、语义检查（Semantic Checking）以及程序执行（Application Exection）。对于现有fuzz的种子生成技术而言，很难到达程序执行阶段。
比如基于变异的fuzz它生成的测试用例大部分在句法分析阶段便无法通过，而基于生成的fuzz生成的测试用例大部分在语义检查阶段无法通过。
由于程序深层次的漏洞一般隐藏在程序执行阶段，如果连程序执行阶段都无法到达，那么更谈不上挖掘这个文档解析引擎的漏洞了。
基于此，本文针对这种结构化输入的模糊测试提出了一种自动学习输入结构并且生成种子的方案–Skyfire。
通过收集目标程序的语料库，然后训练出一个带概率的上下文有关文法(Probabilistic Context-Sensitive Grammar，PCSG)，然后利用它来生成新的种子，执行fuzz。

0x01 方法

1.1 方法概述

下图为Skyfire生成种子的过程。
输入：语料库和语法
输出：种子
过程： 使用目标程序的语料库和语法来训练带概率的上下文有关文法（PCSG）。通过训练好的PCSG，从产生式池中选择产生式来生成种子，并选取和变异。最终输出种子用于后续的fuzz。

1.2 相关的文法介绍

在讲具体的方法之前，先简单介绍一下相关的文法。

在计算机科学中，形式语言是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法。

1.2.1 上下文无关文法（context-free grammar, CFG）

上下文无关文法定义为一个四元组 $G_{cf}=(N,\Sigma,R,s)$Gcf​=(N,Σ,R,s)，可以通过产生式从起始字符推导到一个句子。

符号	定义
$N$N	非终结符的有限集合
$\Sigma$Σ	终结符的有限集合
$R$R	产生式：$\alpha \rightarrow \beta_1 \beta_2 ... \beta_n$α→β1​β2​...βn​ 的有限集合
$s$s	起始字符的有限集合

比如下图，从$E$E开始，通过产生式：$E \rightarrow TE'$E→TE′，$T \rightarrow FT'$T→FT′…… 可以推导到叶子节点，比如红框框的部分是$T \rightarrow FT'$T→FT′，可以把$T$T替换成$FT'$FT′。
树的内部节点为非终结符，树的叶子节点都是终结符。上下文无关文法就是可以用推导式来替换内部节点的非终结符，而不需要管上下文。

但是，显然在本文处理的这种高度结构化输入的文件中，我们需要上下文信息，而上下文无关文法不能表达上下文相关的语义信息，因此可以使用上下文有关文法加入语义信息。

1.2.2 上下文有关文法（context-sensitive grammar, CSG）

上下文无关文法定义为一个四元组：$G_{cs}=(N,\Sigma,R,s)$Gcs​=(N,Σ,R,s)

符号	定义
$N$N	非终结符的有限集合
$\Sigma$Σ	终结符的有限集合
$R$R	产生式：$[c]\alpha \rightarrow \beta_1 \beta_2 ... \beta_n$[c]α→β1​β2​...βn​ 的有限集合
$s$s	起始字符的有限集合

上下文有关文法是在上下文无关文法的基础上，增加了上下文 $c$c。在本文中，$c$c包含的信息有<曾祖父母，祖父母，父类 ，第一个兄弟姐妹的值>。

比如图中节点e上下文信息为：<E, T, T’, null>，曾祖父节点为根节点E，然后祖父节点为下面的T，父节点为T’，但是没有第一个兄弟节点，因此为null。

为了能够生成不常见的输入来触发程序的漏洞，也就是要选出很少用的产生式，我们除了上下文信息，还需要产生式的概率，因此本文提出的带概率的上下文有关文法

1.2.3 带概率的上下文有关文法（Probabilistic context-sensitive grammar, PCSG）

带概率的上下文有关文法(PCSG)定义为元组：$G_p = (G_{cs}, q)$Gp​=(Gcs​,q)，它是在CSG的基础上，对产生式分配了概率，
并且保证对于给定的非终结符$\alpha$α，所有上下文下的产生式规则的概率总和为1。这个有点绕，看到后面PCSG学习后，输出的结果(1.3.3部分)的时候就会懂了。????

$\sum_{[c]\alpha \rightarrow \beta_1 \beta_2 ... \beta_n} q([c]\alpha \rightarrow \beta_1 \beta_2 ... \beta_n) = 1$[c]α→β1​β2​...βn​∑​q([c]α→β1​β2​...βn​)=1

ok，小结一下，为什么使用的是PCSG而不是上下文无关文法？

1. 上下文无关文法能很好地表达语法信息，但因为上下文无关，不能表达上下文相关的语义信息。因此，可以用上下文有关文法来加入语义信息
2. PCSG中的每一个产生式规则都可以和应用了产生式的上下文相关联，并且和上下文中应用了产生式的概率相关联

1.3 PCSG学习

1.3.1 样本解析为抽象语法树（AST）

Skyfire的第一个阶段，PCSG的学习阶段，首先是基于样本的语法，将样本解析为抽象语法树(AST)。

比如下图是一个XSL文件样本

我们可以基于它的语法将其解析为下图中的这样一棵抽象语法树（Abstract Syntax Tree，AST）。其中，树的内部节点是非终结符，也就是XSL文件中内容的一个抽象定义，比如根节点document，叶子节点是终结符，也就是XSL文件中的具体的内容。

根据这棵树，我们可以从中得到一些推导式，比如$document \rightarrow prolog$document→prolog   $element$element，$attribute \rightarrow version="1.0"$attribute→version="1.0"，这里的attribute就是一个非终结符，version="1.0"是终结符

1.3.2 计算parent children pair在相应的上下文条件下出现的次数

parent children pair，父子对，也就是产生式规则。这个步骤要计算的是在所有的AST中，当前的产生式在相应的下文条件下出现的次数。

我们来看一个例子。在下图的红框框中，Node 9是Node 16的父亲，他们形成了一个parent children pair，其实也就是产生式：$attribute \rightarrow version="1.0"$attribute→version="1.0"。它的上下文为：< null, document, element, <xsl:stylesheel >

曾祖父节点	祖父节点	父亲	第一个兄弟
null	document	element	<xsl:stylesheel

那么，我们要统计的就是在所有的AST中，在上下文< null, document, element, <xsl:stylesheel >的条件下，产生式 $attribute \rightarrow version="1.0"$attribute→version="1.0" 出现的次数，即：
$count(<null,document, element, <xsl:stylesheel >attribute \rightarrow version="1.0")$count(<null,document,element,<xsl:stylesheel>attribute→version="1.0")

当然，在具体的算法中，需要统计所有的产生式在相应的上下文条件下出现的次数，这里仅是拿Node9和Node16来举例。

1.3.3 计算每种产生式规则的概率

最后，我们要计算，给定一个非终结符$\alpha$α，也就是AST中的内部节点，我们要计算出在上下文$c$c的条件下，它的产生式的概率。
计算公式为：
$q([c]\alpha \rightarrow \beta_1 \beta_2 ... \beta_n) = \frac{count([c]\alpha \rightarrow \beta_1 \beta_2 ... \beta_n)}{count(\alpha)}$q([c]α→β1​β2​...βn​)=count(α)count([c]α→β1​β2​...βn​)​

也就是给定非终结符$\alpha$α，计算在上下文$c$c条件下$\alpha$α每种产生式规则的概率。 用所有的抽象语法树中，在上下文$c$c的条件下，这个$\alpha$α的产生式规则出现的次数，除以所有的抽象语法树中，非终结符$\alpha$α出现的次数。

理解：它计算的是在所有的抽象语法树中，这个子树（比如上图的Node9和16这棵）在当前上下文条件下出现的概率。上下文可以理解为是用于限制产生式规则的。

以上图为例，Node9是16的父亲，那么在这个上下文条件下，这种产生式的概率就等于，在所有的抽象语法树中，该上下文中这种产生式出现的次数，除以所有抽象语法树中这个非终结符出现的次数，要计算的概率就是：

$q(<null,document, element, <xsl:stylesheel >attribute \rightarrow version="1.0") =$q(<null,document,element,<xsl:stylesheel>attribute→version="1.0")=
$\frac{count(<null,document, element, <xsl:stylesheel >attribute \rightarrow version="1.0")}{count(attribute)}$count(attribute)count(<null,document,element,<xsl:stylesheel>attribute→version="1.0")​

最终，可以得到非终结符在不同上下文条件下产生式的概率，并保存到产生式池中。可以看到，对于同一个非终结符$\alpha$α，比如这里的element，由于在各个上下文条件下，产生式的概率的计算，分母都是count(element)，因此它们的概率和便为1.

1.4 种子生成

1.4.1 种子的生成

种子的生成采用的是最左推导的方式。
最左推导：

• 从一个起始字符开始
• 每次都用产生式规则替换最左边的非终结符
• 直到句子中没有非终结符为止

下图为生成种子的过程，蓝色的字符为非终结符，黑色的字符为终结符。
图中的$t_2$t2​到$t_3$t3​，就是把最左边的非终结符attribute替换成终结符version=“1.0”。下一步再把t3中最左边的非终结符替换成终结符，直到整个句子中没有非终结符则结束。

但是由于产生式规则存在递归的关系，因此，算法可能无法结束，或者得到的种子很复杂文件很大。

为了解决这两个问题，同时为了保证生成种子的正确性多样性和不常见性，本文提出了四个启发式：

• 优先选取低概率的产生规则，从而生成样本库中很难覆盖的输入；（粉色）
• 限制相同一产生规则的使用次数，优先应用频率低的规则；（黄色）
• 优先使用低复杂度的规则；（绿色）
• 还有就是限制所有规则的应用次数；（蓝色）

1.4.2 种子的选取

通过上面的种子生成步骤，可以生成很多的初始种子，但并不是所有种子都是唯一和重要的。本文以覆盖率作为选择种子的标准：

• 对于开源程序使用gcov获取代码和函数覆盖率
• 对于闭源程序使用PIN获取基本块覆盖率

1.4.3 种子的变异

为了保证种子的多样性，需要对种子进行变异。
本文采用的是大步变异，简单地说，就是在AST中选取叶子节点（终结符），并利用同种类型的叶子节点对其进行随机替换，只用右边是终结符的产生式进行变异。
好处：可以产生一般Fuzzer的small-step变异难以生成的种子，比如从version=“1.0”到encoding=“utf-8”，通过随机的按位翻转是非常困难的。

举个例子吧，在图中，可以把节点22的内容替换成另外的非终结符：omit-xml-declaration= “yes”

0x02 实验结论

测试目标：XSLT、XML，IE11的JavaScript引擎等

结果：
- 漏洞发现能力强
- 19个新的内存破坏型bug（其中16个新的漏洞）
- 32个拒绝服务bug

结论：
- 优点：
- 生成的种子能有效地发现深层次的漏洞
- 对于XML、XSL语言的应用效果很好
- 缺点：
- 对JS这种较为复杂的语言，实验效果有待提高

0x03 未来工作

改进方向
- 使用深度学习的方法学习输入的结构

应用方向
- 支持更多不同的语言，如：javascript、SQL、C、java等
- 使用生成的种子输入来查找编译器错误

---

0x04 参考资料

1. Skyfire: 一种用于Fuzzing的数据驱动的种子生成工具
2. Skyfire: Data-Driven Seed Generation for Fuzzing

---

有什么理解错的或是写错的还望各位师傅指正 ????