背景

最近一直放心不下漏洞挖掘工作，发现这篇“Skyfire: Data-Driven Seed Generation for Fuzzing”文章，简单了解了下，对xml和xsl支持比较好，用来生成测试种子，在漏洞挖掘工作中，种子的覆盖率能更大限度的提高fuzzing过程有效性，故此，先了解下算法的具体实现，和适用性。

算法学习

模糊测试的输入种子文件的质量是对测试效果的重要影响因素。
这篇文章的解决的中心点问题在于：

基于生成的方法能够实现对语法规则的描述和生成，但是想要通过语义规则的检查却是非常困难的。一方面，对于不同的程序有不同的语义规则，编写的生成规则难以复用；另一方面，这样的手动描述方法是非常耗时费力的，而且有时候甚至是难以实现的。

本文使用一种扩展的上下文敏感的文法（包含语义信息和概率信息）来生成测试用例，并将其作为Fuzzer的输入进行测试。Skyfire面向的目标程序是接收高度结构化输入的程序，目的是生成覆盖良好的测试用例。

2 方法概述

2.1 生成目标

（1）生成正确的种子：能够通过程序的语法和语义检测；

（2）生成多样性种子：能够多样化地覆盖语法和语义规则；

（3）生成不常见种子：能够生成一般Fuzzer生成不了的种子。

2.2 处理过程

Skyfire通过学习PCSG，可以生成覆盖良好的种子，供后续fuzzing。

输入：爬取的样本集合+程序的语法规则（github上ANTLR社区开源）；

输出：覆盖良好的种子。

包含以下主要步骤：

(1) PCSG学习：根据输入自动化抽取带概率的上下文有关文法规则；

(2) 种子生成：

初始种子生成：根据抽取的规则采用左推导方法进行初始种子生成；

种子选取：采用覆盖率作为衡量标准进行样本去重选取；

种子变异：利用随机替换原则对同种类型的叶子节点进行变异；

结论

这个算法适用xml这种语法简单的，提取语法规则然后用相关性生成种子，种子在符合语法的前提下也符合语义这样就能更大程度上保证种子的有效性，保证每条种子都能正常执行测试。

引申

安卓和c方面运用的话，要考虑提取出来集合的相关性怎么确定?比如，给一个

int func(int a,int b)
  {
      int arg1=a;
      int arg2=b;
      return arg1+arg2=?
  }

提取出相关性可以生成特定种子，确定是可以在这个函数中执行并能测试相关漏洞的？如果不知道这个可能就是从种子中随机参数变异fuzzing 浪费资源，而且不能挖掘更深层次的漏洞。

补充说明

==上下文无关法==

提到上下文无关文法有以下的特点：

• 一个终结符的有限集（A set of terminal symbols），构成文法的最基本的字符就是这个文法的终结符，例如一个能够产生个位数的文法规则digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9，则数字0～9就是这个文法的终结符，一个能够产生变量名的文法规则variable --> ('A'-'Z' | 'a'-'z') *(('A'-'Z' | 'a'-'z' | '0'-'9')，则所有的英文字母和数字就是文法的终结符。
• 一个非终结符的有限集（A set of nonterminals），例如上面的digit、variable就是非终结符。
• 一个产生式的有限集，例如上面的“digit --> ...”和“variable --> ...”两个规则可以构成一个产生式集
• 一个非终结符作为开始符号，在非终结符集中，必须指定其中一个作为开始符号。

虽然这4个特点已经规定了上下文无关文法的特征，但我们仍然好奇，为什么是“上下文无关”而不是“上下文有关”呢？这是因为在利用一个上下文无关文法生成语言的时候，我们可以随意将文法规则左边的非终结符派生（更换）为右边的终结符或非终结符。举个例子，如果有下面的文法：

• Number --> 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9
• Alpha --> 'A'-'Z' / 'a'-'z'
• AlphaNum --> Alpha / Number
• Variable --> Alpha *AlphaNum

假设Variable是这个文法的开始符号，我们要根据这个文法生成一个语言实例。先应用规则4，Variable派生为Alpha AlphaNum（星号表示后面的符号可以出现0到若干次，这里我们选择出现1次）。然后对Alpha应用规则2，派生为'A'，因此整个Variable就派生为'A' AlphaNum。现在来考虑AlphaNum如何派生，有没有限制这个AlphaNum可以派生为Alpha还是Number呢？它是否会受到前面的Alpha的影响而不同？我们说， 在一个上下文无关文法中，这个派生是不受上下文影响的，也就是说，我们可以随意的让其派生为Alpha或者Number，而不必考虑前后文的情况。有关解释可以参考 http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node37.html。

==上下文有关文法==

• 形式文法 G = (N, Σ, P, S) 是上下文有关的，如果在 P 中所有的规则都有如下形式
• αAβ → αγβ
• 这里的 A ∈ N (就是 A 是单一非终结符)，α,β ∈ (N U Σ)* (就是 α 和 β 是非终结符和终结符的字符串)而 γ ∈ (N U Σ)+ (就是 γ 是非终结符和终结符的非空字符串)。
• 此外还有如下形式的规则
• S → ε 假定 S 不出现在任何规则的右手端
• 这里的 ε 表示空串是允许的。增加空串允许声明上下文有关语言是上下文无关语言的真子集，而无须作出没有 →ε产生式的所有上下文无关文法也是上下文有关文法这种弱一些的声明。
• 上下文有关这个名称来源自 α 和 β 形成了 A 的上下文并且决定 A 是否可以被 γ 所替代。这不同于不考虑非终结符上下文的上下文无关文法。

参考链接

https://www.inforsec.org/wp/?p=2678

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课