fuzzing-6-grammer_fuzzing

projects

基于语法的fuzzing，主要面向黑盒测试。个人觉得这种方式可以再结合覆盖率动态调整演变方向，并且可以结合AI中的进化算法，演变出coverage更高的输入。

输入的语法

我们的所有”输入”都可以看作是语法构成的。无论是网络上的URL，计算器中的输入计算式，又或者是交互式程序中的输入，都有一定的格式。接下来假设所有的程序只有一种输入方式。

我们可以把有限状态机和常见语法结合起来，让它产生有意义的数据。我们称表达式和有限状态图灵机之间的联系为语法。下面介绍几个简单的例子。

1
2
<start> ::= <digit><digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

上面的式子就是一个简单的语法例子。为了生成一个start，我们先将他替换成<digit><digit>，之后看到最左边有一个位置的用尖括号包裹起来的<digit>，我们需要继续递归。看到下一行是<digit>的内容，并且没有尖括号，此时我们称digit碰到了terminal，也就是终止于此。那么digit就被赋值成一个数字，传递到上面。我们如果选择了”1”，那么<start>将变为1<digit>.递归运行第二步，从而得到一个完整的<start>。

介绍完例子，正式介绍一下定义

To read such a grammar, start with the start symbol (<start>). An expansion rule <A> ::= <B> means that the symbol on the left side (<A>) can be replaced by the string on the right side (<B>). In the above grammar, <start> would be replaced by <digit><digit>

上述定义可以是递归的。考虑下面的代码

1
2
3
<start>  ::= <integer>
<integer> ::= <digit> | <digit><integer>
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

第二行中<interger>生成了一个包含自己的表达式。虽然理论上来说，这种表达式可能无限扩张下去，我们可以设置一个演变值域，让这种变化限制在一个变异次数范围之内。

考虑下面的问题，可以看到式子中不可能出现两个加减符号，也没有出现小数点。选项就很简单了。

image-20220317215559023

实例：数学表达式

接下来，考虑一些更加实际的问题。例如数学表达式的语法，作为一个递归演算的练习。

1
2
3
4
5
6
<start>   ::= <expr>
<expr>    ::= <term> + <expr> | <term> - <expr> | <term>
<term>    ::= <term> * <factor> | <term> / <factor> | <factor>
<factor>  ::= +<factor> | -<factor> | (<expr>) | <integer> | <integer>.<integer>
<integer> ::= <digit><integer> | <digit>
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

image-20220317215958615

在python中编写语法

使用python的map，可以轻松的建立一种字符串-列表映射表，也就是我们的语法。一个例子如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
EXPR_GRAMMAR: Grammar = {
    "<start>":
        ["<expr>"],

    "<expr>":
        ["<term> + <expr>", "<term> - <expr>", "<term>"],

    "<term>":
        ["<factor> * <term>", "<factor> / <term>", "<factor>"],

    "<factor>":
        ["+<factor>",
         "-<factor>",
         "(<expr>)",
         "<integer>.<integer>",
         "<integer>"],

    "<integer>":
        ["<digit><integer>", "<digit>"],

    "<digit>":
        ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
}

由于map属性，使用下列方法可以轻松的获取某个grammar列中的内容

1
2
EXPR_GRAMMAR["<digit>"]
输出: ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

我们定义：非终止(non-terminal)是指不是以左右的尖括号作为开始和结束的表达式。以下表示了一些表达式类型。左侧为输入列表，右侧为输出的非终止类型。

1
2
3
4
5
6
assert nonterminals("<term> * <factor>") == ["<term>", "<factor>"]
assert nonterminals("<digit><integer>") == ["<digit>", "<integer>"]
assert nonterminals("1 < 3 > 2") == []
assert nonterminals("1 <3> 2") == ["<3>"]
assert nonterminals("1 + 2") == []
assert nonterminals(("<1>", {'option': 'value'})) == ["<1>"]

一个简单的grammer fuzzer

我是一只小懒虫，我把代码复制到这里，然后分析一下，✌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def simple_grammar_fuzzer(grammar: Grammar, 
                          start_symbol: str = START_SYMBOL,
                          max_nonterminals: int = 10,
                          max_expansion_trials: int = 100,
                          log: bool = False) -> str:
    """Produce a string from `grammar`.
       `start_symbol`: use a start symbol other than `<start>` (default).
       `max_nonterminals`: the maximum number of nonterminals 
         still left for expansion
       `max_expansion_trials`: maximum # of attempts to produce a string
       `log`: print expansion progress if True"""

    term = start_symbol
    expansion_trials = 0

    # 当术语中还有非终止符号的时候
    while len(nonterminals(term)) > 0:
        # 从术语中所有非终止符中挑选一个扩展。这里和之前讲的有顺序的扩展不太一样。
        symbol_to_expand = random.choice(nonterminals(term))
        # grammar是之前我们写的map类型的规则，作为参数传递进这个类，在这里引用，并找到这个key对应的expansion种类。
        expansions = grammar[symbol_to_expand]
        # 从这个key的所有expansion中随机找到一个
        expansion = random.choice(expansions)
        # In later chapters, we allow expansions to be tuples,
        # with the expansion being the first element
        if isinstance(expansion, tuple):
            expansion = expansion[0]
# 将随机选取的扩展替换之前的
        new_term = term.replace(symbol_to_expand, expansion, 1)
# 这里是防止非术语过多导致爆栈问题。设置了一个非术语数量上限。如果小于上线，就将术语替换成刚才换掉的，否则expansion_trials++，表示超出一次。如果超出多次，就直接停止计算。
        if len(nonterminals(new_term)) < max_nonterminals:
            term = new_term
            if log:
                print("%-40s" % (symbol_to_expand + " -> " + expansion), term)
            expansion_trials = 0
        else:
            expansion_trials += 1
            if expansion_trials >= max_expansion_trials:
                raise ExpansionError("Cannot expand " + repr(term))

    return term

用如下方式调用

1
simple_grammar_fuzzer(grammar=EXPR_GRAMMAR, max_nonterminals=3, log=True)

如下，可以生成很多很有意思的算式。但是更重要的是，这和基于变异的生成方式不同。这里给随机性加上了一定的规则，不能随机变成别的内容比如字母等。

1
2
3
4
5
6
7
8
9
10
7 / +48.5
-5.9 / 9 - 4 * +-(-+++((1 + (+7 - (-1 * (++-+7.7 - -+-4.0))))) * +--4 - -(6) + 64)
8.2 - 27 - -9 / +((+9 * --2 + --+-+-((-1 * +(8 - 5 - 6)) * (-((-+(((+(4))))) - ++4) / +(-+---((5.6 - --(3 * -1.8 * +(6 * +-(((-(-6) * ---+6)) / +--(+-+-7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6.37) + (1) / 482) / +++-+0)))) * -+5 + 7.513)))) - (+1 / ++((-84)))))))) * ++5 / +-(--2 - -++-9.0)))) / 5 * --++090
1 - -3 * 7 - 28 / 9
(+9) * +-5 * ++-926.2 - (+9.03 / -+(-(-6) / 2 * +(-+--(8) / -(+1.0) - 5 + 4)) * 3.5)
8 + -(9.6 - 3 - -+-4 * +77)
-(((((++((((+((++++-((+-37))))))))))))) / ++(-(+++(+6)) * -++-(+(++(---6 * (((7)) * (1) / (-7.6 * 535338) + +256) * 0) * 0))) - 4 + +1
5.43
(9 / -405 / -23 - +-((+-(2 * (13))))) + +6 - +8 - 934
-++2 - (--+715769550) / 8 / (1)

但是这样的缺点也有很多。比如说，可能包含很多字符串搜索、替换工作等。(或许考法一种面向语法的编译器可以解决问题?)

image-20220317230102013

更多语法例子

这里放一个比较有趣的吧。比如说下面的例子，可以用来生成书名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TITLE_GRAMMAR: Grammar = {
    "<start>": ["<title>"],
    "<title>": ["<topic>: <subtopic>"],
    "<topic>": ["Generating Software Tests", "<fuzzing-prefix>Fuzzing", "The Fuzzing Book"],
    "<fuzzing-prefix>": ["", "The Art of ", "The Joy of "],
    "<subtopic>": ["<subtopic-main>",
                   "<subtopic-prefix><subtopic-main>",
                   "<subtopic-main><subtopic-suffix>"],
    "<subtopic-main>": ["Breaking Software",
                        "Generating Software Tests",
                        "Principles, Techniques and Tools"],
    "<subtopic-prefix>": ["", "Tools and Techniques for "],
    "<subtopic-suffix>": [" for <reader-property> and <reader-property>",
                          " for <software-property> and <software-property>"],
    "<reader-property>": ["Fun", "Profit"],
    "<software-property>": ["Robustness", "Reliability", "Security"],
}

结果如下，解释方式其实上面计算器的例子已经很好的说明了。

1
2
3
4
5
6
7
8
9
10
{'Fuzzing: Generating Software Tests',
 'Fuzzing: Principles, Techniques and Tools',
 'Generating Software Tests: Breaking Software',
 'Generating Software Tests: Breaking Software for Robustness and Robustness',
 'Generating Software Tests: Principles, Techniques and Tools',
 'Generating Software Tests: Principles, Techniques and Tools for Profit and Fun',
 'Generating Software Tests: Tools and Techniques for Principles, Techniques and Tools',
 'The Fuzzing Book: Breaking Software',
 'The Fuzzing Book: Generating Software Tests for Profit and Profit',
 'The Fuzzing Book: Generating Software Tests for Robustness and Robustness'}

结合mutation和grammar

如果我们将变异和语法结合起来，语法上的生成数据能够生成有效的输入，而变异的数据能够提供一部分的无效输入，能够得到更好，更大的覆盖面。具体的使用方法也很简单，只需要把语法的生成结果作为种子输入到变异内部即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
number_of_seeds = 10
seeds = [
    simple_grammar_fuzzer(
        grammar=URL_GRAMMAR,
        max_nonterminals=10) for i in range(number_of_seeds)]
seeds
['ftps://user:password@www.google.com:80',
 'http://cispa.saarland/',
 'ftp://www.google.com:42/',
 'ftps://user:password@fuzzingbook.com:39?abc=abc',
 'https://www.google.com?x33=1&x06=1',
 'http://www.google.com:02/',
 'https://user:password@www.google.com/',
 'ftp://cispa.saarland:8080/?abc=abc&def=def&abc=5',
 'http://www.google.com:80/def?def=abc',
 'http://user:password@cispa.saarland/']
# 使用之前讲到的变异fuzzer
m = MutationFuzzer(seeds)
[m.fuzz() for i in range(20)]
['ftps://user:password@www.google.com:80',
 'http://cispa.saarland/',
 'ftp://www.google.com:42/',
 'ftps://user:password@fuzzingbook.com:39?abc=abc',
 'https://www.google.com?x33=1&x06=1',
 'http://www.google.com:02/',
 'https://user:password@www.google.com/',
 'ftp://cispa.saarland:8080/?abc=abc&def=def&abc=5',
 'http://www.google.com:80/def?def=abc',
 'http://user:password@cispa.saarland/',
 'Eh4tp:www.coogle.com:80/def?d%f=abc',
 'ftps://}ser:passwod@fuzzingbook.com:9?abc=abc',
 'uftp//cispa.sRaarland:808&0?abc=abc&def=defabc=5',
 'http://user:paswor9d@cispar.saarland/v',
 'ftp://Www.g\x7fogle.cAom:42/',
 'hht://userC:qassMword@cispy.csaarland/',
 'httx://ww.googlecom:80defde`f=ac',
 'htt://cispq.waarlnd/',
 'htFtp\t://cmspa./saarna(md/',
 'ft:/www.google.com:42\x0f']

grammar toolbox

语法构建程序

这里主要介绍了一些用来检验、生成(例如正则匹配中的+-？等)的方法。基于的还是python。这里介绍了一个例子BNF，我们需要将他扩充为EBNF，如下所示。实际上就是扩展了一下正则语法。替换了问号、加减等。

  1. An expression (content)op, where op is one of ?, +, *, becomes <new-symbol>op, with a new rule <new-symbol> ::= content.

  2. An expression <symbol>? becomes <new-symbol>, where <new-symbol> ::= <empty> | <symbol>.

  3. An expression <symbol>+ becomes <new-symbol>, where <new-symbol> ::= <symbol> | <symbol><new-symbol>.

  4. An expression <symbol>* becomes <new-symbol>, where <new-symbol> ::= <empty> | <symbol><new-symbol>

接下来讲的其实有点像是编译，大概是符号扩展。书本中提到了实现此方法的三个步骤。第一步是生成新symbol，第二步是将生成的symbol重新表示成我们之前提到的语法的形式。下面是一个例子

image-20220318092644508

处理完这个之后，我们再用正则匹配问号等，并根据上述规则或者加入新符号，或者替换原本的符号。核心代码如下

1
2
3
4
5
6
7
if operator == '?':
    grammar[new_sym] = ["", original_symbol]
elif operator == '*':
    grammar[new_sym] = ["", original_symbol + new_sym]
elif operator == '+':
     grammar[new_sym] = [
         original_symbol, original_symbol + new_sym]

上述三步完成之后，就可以根据正则语法写一些”语法”了。

image-20220318093039588

语法检查程序

这个有点过于复杂。牵涉到reachable和unreachable，并且检查语法合法性。这里后面有时间看的时候再进一步详细补充原理。总感觉相当于写了一个小编译器或者小解释器的感觉。

efficient grammar fuzzing

这一节介绍了一种用树结构表示变异的方法。用树结构的好处是：能够更清晰的看出变异过程，并且可以相应的控制变异什么时候开始和结束(通过监视变异树)

在上面提到的简单语法树中，其实存在不少问题。例如下面的输入。在给定max_nonterminals=3的条件下，存在无限父节点的问题。观察第四行。由于我们严格限定了非终止符号长度，因此第四行只能选择，于是产生了无限父类的错误。

1
2
3
4
5
6
7
8
9
10
11
{'<start>': ['<expr>'],
 '<expr>': ['<term> + <expr>', '<term> - <expr>', '<term>'],
 '<term>': ['<factor> * <term>', '<factor> / <term>', '<factor>'],
 '<factor>': ['<sign-1><factor>', '(<expr>)', '<integer><symbol-1>'],
 '<sign>': ['+', '-'],
 '<integer>': ['<digit-1>'],
 '<digit>': ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
 '<symbol>': ['.<integer>'],
 '<sign-1>': ['', '<sign>'],
 '<symbol-1>': ['', '<symbol>'],
 '<digit-1>': ['<digit>', '<digit><digit-1>']}

除了上述错误之外，这种语法结构也难以控制大小和监视变化。因此，我们通过引入树的结构就能够很好的解决这种问题(简单思考一下就能发现，解决上述问题只需要确保树没有循环指针就可以了)

语法树定义

每一次随机选定的终止符与非终止符作为叶节点(注意，类似加减乘除单独作为节点)之后将树展开。前序遍历得到的结果就是当前语法树的输出结果。如下图所示。

image-20220318234420004

这种结构如何表示呢?使用python

语法树的表示

我们用如下结构体表示一个节点

1
(SYMBOL_NAME, CHILDREN)

其中symbol_name如果是非终止符，就一定有叶节点，否则一定没有叶节点。下面是一个很简单的分叉树的表示

1
DerivationTree = Tuple[str, Optional[List[Any]]]
1
2
3
4
5
6
derivation_tree: DerivationTree = ("<start>",
                   [("<expr>",
                     [("<expr>", None),
                      (" + ", []),
                         ("<term>", None)]
                     )])

image-20220318234902745

注意如果是none，说明在未来还要扩展。否则一个空的list表示为终止符。

语法树的操作

有一些比较重要的操作，例如扩展结点。这一步需要首先选定要扩展的节点，其次使用扩展算法。以下方法能够计算在输入一个分叉树时，计算当前可能的扩展数量。

1
2
3
4
5
6
7
class GrammarFuzzer(GrammarFuzzer):
    def possible_expansions(self, node: DerivationTree) -> int:
        (symbol, children) = node
        if children is None:
            return 1

        return sum(self.possible_expansions(c) for c in children)

这里可以看到使用了递归来计算能够扩展多少。如果当前children是none，说明到达了结尾，可以返回1，表示这里有一个可以扩展的节点。

接下来当我们判定当前树存在可扩展的结点之后，就可以进行扩展。关键方法如下（expand_tree_once）。

下面代码的大致思路是：首先看当前node的子节点是不是none。如果是none就说明到达了可以扩展的节点，使用expand_node扩展当前节点。否则说明当前还在树枝节点上，那么需要以当前节点作为根节点，进一步往下选择任意一个后面可以扩展的节点，选择它并进行expand_tree_once。是一个典型的树操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class GrammarFuzzer(GrammarFuzzer):
    def choose_tree_expansion(self,
                              tree: DerivationTree,
                              children: List[DerivationTree]) -> int:
        """Return index of subtree in `children` to be selected for expansion.
           Defaults to random."""
        return random.randrange(0, len(children))

    def expand_tree_once(self, tree: DerivationTree) -> DerivationTree:
        """Choose an unexpanded symbol in tree; expand it.
           Can be overloaded in subclasses."""
        (symbol, children) = tree
        if children is None:
            # Expand this node
            return self.expand_node(tree)

        # Find all children with possible expansions
        expandable_children = [
            c for c in children if self.any_possible_expansions(c)]

        # `index_map` translates an index in `expandable_children`
        # back into the original index in `children`
        index_map = [i for (i, c) in enumerate(children)
                     if c in expandable_children]

        # Select a random child
        child_to_be_expanded = \
            self.choose_tree_expansion(tree, expandable_children)

        # Expand in place
        children[index_map[child_to_be_expanded]] = \
            self.expand_tree_once(expandable_children[child_to_be_expanded])

        return tree

可以用图的方法简明地看到效果。下面是第一次扩展的结果。

image-20220319142232107

下面是第二次扩展

image-20220319142256145

优化分叉

为了监视二叉树的行为，我们加上一些树在expand时候的控制。例如控制树扩展次数和广度。我们首先定义了一个cost用来计算树在扩展时产生的开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class GrammarFuzzer(GrammarFuzzer):
    def symbol_cost(self, symbol: str, seen: Set[str] = set()) \
    -> Union[int, float]:
        expansions = self.grammar[symbol]
        return min(self.expansion_cost(e, seen | {symbol}) for e in expansions)

    def expansion_cost(self, expansion: Expansion,
                       seen: Set[str] = set()) -> Union[int, float]:
        symbols = nonterminals(expansion)
        if len(symbols) == 0:
            return 1  # no symbol

        if any(s in seen for s in symbols):
            return float('inf')

        # the value of a expansion is the sum of all expandable variables
        # inside + 1
        return sum(self.symbol_cost(s, seen) for s in symbols) + 1

我们定义的规则是：如果当前扩展中含有自己，说明可能潜在的存在无限递归的可能性，设置此时权值为正无穷，否则权值+1。使用symbol_cost能够输出扩展的最小权值。下面是例子

image-20220319150332406

至此，我们可以有一种选择策略，每次扩展树时，选择cost最小的扩展，如果都相同，随机选择一个进行扩展

思考：这里就可以把很多图里面有关的算法引入了。有了权值之后我们可以定义最小生成树，或者计算路径等等。可以把每次扩展的权值和覆盖率的提升作比较。可以后面深入思考一下。

思考一下每次进行最小扩展具有的性质：cost表示的其实是能够最快达到演变结束的路径。也就是说每一次演变，我们朝着最快达到terminal的路径。

同样的，为了获得更多可以演变的节点，我们一样可以编写expand_node_max_cost，来让演变变得越来越庞大。那么每一次演变，我们都尽可能朝着能够扩展expr的路径。下图为一个例子

image-20220319160036395

由上述，我们有了三种扩展策略。

  1. Max cost expansion. Expand the tree using expansions with maximum cost until we have at least min_nonterminals nonterminals. This phase can be easily skipped by setting min_nonterminals to zero.
  2. Random expansion. Keep on expanding the tree randomly until we reach max_nonterminals nonterminals.
  3. Min cost expansion. Close the expansion with minimum cost.

我们用如下策略来扩展树

  1. 首先调用expand_node_max_cost来获得尽量多的node用来扩展。
  2. 接着expand_random
  3. 最后expand_min来企图快速达到收敛。

这样就能实现对于任何一种语法树，我们有了控制其发散和收敛的方法。也就不会出现本章一开始提出的问题了。

本文标题:fuzzing-6-grammer_fuzzing

文章作者:

发布时间:2022-03-17, 21:32:14

最后更新:2022-03-19, 16:08:38

原始链接:https://nicholas-wei.github.io/2022/03/17/fuzzing-6-grammer-fuzzing/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 输入的语法
    1. 1.1. 实例：数学表达式
    2. 1.2. 在python中编写语法
    3. 1.3. 一个简单的grammer fuzzer
  2. 2. 更多语法例子
  3. 3. 结合mutation和grammar
  4. 4. grammar toolbox
    1. 4.1. 语法构建程序
    2. 4.2. 语法检查程序
  5. 5. efficient grammar fuzzing
    1. 5.1. 语法树定义
    2. 5.2. 语法树的表示
    3. 5.3. 语法树的操作
    4. 5.4. 优化分叉
|