Arya

Efficient Grammar Fuzzing(一)
[+] 昨天梦见了一个漂亮的小姐姐,顺便梦回了一次高中,哈哈哈[+] 我不喜欢过年0x01 高效的语法fuzzin...
扫描右侧二维码阅读全文
24
2019/01

Efficient Grammar Fuzzing(一)

[+] 昨天梦见了一个漂亮的小姐姐,顺便梦回了一次高中,哈哈哈
[+] 我不喜欢过年

0x01 高效的语法fuzzing

所以看题目也知道,今天学的还是和语法相关的fuzzing,那么继续开始吧╮(╯▽╰)╭

上一章的中,我们学到了如何使用于法进行非常有效的测试,所以在本章中,我们将对前面居于字符串的算法改为基于树的算法。基于树的算法在运算速度上很快,并且允许对模糊输入的产生进行更多的控制。

本章的算法也为之后进一步学习奠定了基础,本章作为本书中的一个“集线器”存在

在之前一章,我们写过一个simple_grammar_fuzzer()函数用来接受语法并自动生成一个语法有效的字符串,当然之前之所以命名为simple也是因为确实是一个简单的fuzzer,接下来我们要回到上一章创建的EXPR_GRAMMAR_BNF语法中

import fuzzingbook_utils
from fuzzingbook_utils import unicode_escape
from Grammars import EXPR_EBNF_GRAMMAR, convert_ebnf_grammar, simple_grammar_fuzzer, is_valid_grammar, exp_string, exp_opts
expr_grammar = convert_ebnf_grammar(EXPR_EBNF_GRAMMAR)
print(expr_grammar)

输出生成的符合规则的语法

{'<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>']}

expr_grammar有一个有趣的属性,当我们将它放入simple_grammar_fuzzer()中时,一定会陷入一个无限的扩展中,可以来测试一下

from ExpectError import ExpectTimeout

with ExpectTimeout(1):
     simple_grammar_fuzzer(grammar=expr_grammar, max_nonterminals=3)

果然触发了超时报错机制
`
Traceback (most recent call last):
File "<ipython-input-6-fbcda5f486bb>", line 2, in <module>

simple_grammar_fuzzer(grammar=expr_grammar, max_nonterminals=3)

File "<string>", line 10, in simple_grammar_fuzzer
File "/Users/rahul.gopinath/anaconda3/lib/python3.6/random.py", line 258, in choice

i = self._randbelow(len(seq))

File "/Users/rahul.gopinath/anaconda3/lib/python3.6/random.py", line 258, in choice

i = self._randbelow(len(seq))

File "<string>", line 16, in check_time
TimeoutError (expected)`

那么为什么会这样呢,其实问题出在了这个语句中

print(expr_grammar['<factor>'])

['<sign-1><factor>', '(<expr>)', '<integer><symbol-1>']

(不过比较丢人的是我突然忘了simple_grammar_fuzzer()是用来做什么的,又重新回去翻了一下笔记,哈哈哈

因为simple_grammar_fuzzer()会对每一个非终端符号进行扩展,除了类似于(expr)不用进行扩展以外,对于任何一个<expr>形式的终端符号都要进行扩展。所以在<factor>中对每个非终端符号都要进行相对应的扩展,而且每个都不一样,并且<factor>还要自己进行递归,所以基本上我们是陷入了一个不断扩展的递归循环中。并且如果我们对扩展进行限制的话,我们只能展开(<expr>),这又导致了无数()的增加。

当然无限扩展仅仅只是simple_grammar_fuzzer()的问题之一,但是上面的分析中还有别的问题,第一,这种扩展会引起无限的迭代,相当的低效;第二,即使我们控制了符号的数量,这种扩展也会无限的字符串。

那么接下来通过绘制时间图,简单的观察一下另一个字符串消耗的时间

from Grammars import simple_grammar_fuzzer
from Grammars import START_SYMBOL, EXPR_GRAMMAR, URL_GRAMMAR, CGI_GRAMMAR
from Grammars import RE_NONTERMINAL, nonterminals, is_nonterminal
from Timer import Timer
trials = 50
xs = []
ys = []
for i in range(trials):
    with Timer() as t:
        s = simple_grammar_fuzzer(EXPR_GRAMMAR, max_nonterminals=15)
    xs.append(len(s))
    ys.append(t.elapsed_time())
    print(i, end=" ")
print()

0 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 42 43 44 45 46 47 48 49
循环了50次

我们可以计算一下平均消耗的时间

average_time = sum(ys) / trials
print("Average time:", average_time)

Average time: 0.1715061183006037
接下来绘制耗时的图谱
Image9-1.png

import matplotlib.pyplot as plt
plt.scatter(xs, ys)
plt.title('Time required for generating an output')
plt.show()

我们可以看到随着时间的推移,工作量是呈4次方在增长,同时我们也可以看到我们可以在1s内生成数以万计的字符的增长。

为了解决这些问题,我们需要一个更加高效的算法,既可以更好的控制可见的无限扩展,也能够产生一个新的方法来抑制潜在的扩展可能性

0x02 派生树(derivation tree)

为了获得更有效地算法,并且能够很好地控制扩展,我们需要对语法生成的字符串使用特殊的方法来表示。一般的做法是使用一个可以被扩展的树的结构——派生树。这种表示方式可以让我们跟踪代码的扩展状态,可以通过回答一些问题的方式,比如有哪些元素已经扩展到其他元素中了,哪些符号仍然需要扩展之类的问题对字符串的扩展进行控制,而且想书中添加新元素,也比一次一次的替换字符串要高效的多。

派生树和其他的树差不多,派生树的别名又叫
parse tree或者是concrete syntax tree。

接下来将说明带有派生树的语法扩展过程,我们从一个节点开始,我们使用<start>表示开始符号,作为树的根

tree

<start>
接下来我们从树根开始,遍历拓展这棵树,对于<start>来说,它只有一个扩展

#此处为源代码中的对应关系
"<start>":    ["<expr>"],

因此树变为

tree

Image9-2.png

接下来继续遍历树,从<expr>开始,寻找它的子节点

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

这里我们找到的是<expr> + <term>,那么现在的树扩展成
Image9-3.png
增加了三个孩子

那么继续重复便利的过程,直到遍历结束
Image9-4.png
此时获得了一棵完整的树,并且我们最终获得了2+2
的字符串表示形式

但是与之前单独使用字符串的替换不同的是,派生树完整记录了生成字符串的全过程,它还允许一些简单的比较和操作——比如讲一个子树替换成另一个子树。

在python中,我们也有表示派生出的方式,使用的是以下的格式

(SYMBOL_NAME, CHILDREN)

在这里SYMBOL_NAME表示的是节点的字符串(如<start>或者是+),CHILDREN表示的是子节点的列表

CHILDREN可以被赋一些特殊的值,

  • None作为将来扩展的占位符,表示这个节点是应该进行进一步扩展的非终端符号
  • []表示没有子节点,意味着这个节点是一个不能再展开的终端符号

接下来我们用一个比较简单的派生说来表示<expr> + <term>的中间步骤

derivation_tree = ("<start>",
                   [("<expr>",
                     [("<expr>", None),
                      (" + ", []),
                         ("<term>", None)]
                     )])

为了能够跟好的理解这棵树,我们可以通过定义一个函数来将这个树打印输出。我们使用graphvi包中的dot来绘制图像,遍历上面的结构。

首先我们来……打住吧
作者给的fuzzingbook_utils包里根本没有unicode_escape函数,所以最后的结果就是我找了一小时未果,遂放弃

0x03 扩展节点

没法做图是一件挺可惜的事情,不过好在接下来也不太需要必须做图,那么就接着往下看。

在刚才我们简单的介绍了一下派生树的概念,以及一些节点的细节问题。那么现在我们想通过代码生成这棵树,并且扩展这棵树的节点。我们创建一个Fuzzer的子类GrammerFuzzerGrammerFuzzer必要的参数是一个语法和一个开始符号,其他的参数则用于稍后的调试中。

from Fuzzer import Fuzzer
class GrammarFuzzer(Fuzzer):
    def __init__(self, grammar, start_symbol=START_SYMBOL,
                 min_nonterminals=0, max_nonterminals=10, disp=False, log=False):
        self.grammar = grammar
        self.start_symbol = start_symbol
        self.min_nonterminals = min_nonterminals
        self.max_nonterminals = max_nonterminals
        self.disp = disp
        self.log = log
        self.check_grammar()

和之前一样,我们来给类GrammarFuzzer添加新的方法,这个方法和之前我们给类MutationFuzzer添加方法的结构一样

class GrammarFuzzer(GrammarFuzzer):
    def new_method(self, args):
        pass

我们使用这种方式添加方法check_grammar()用来检查一下给定的语法是否符合原有的语法结构

class GrammarFuzzer(GrammarFuzzer):
    def check_grammar(self):
        assert self.start_symbol in self.grammar
        assert is_valid_grammar(
            self.grammar,
            start_symbol=self.start_symbol,
            supported_opts=self.supported_opts())

    def supported_opts(self):
        return set()

现在我们定义一个方法init_tree(),这个符号只负责创建开始符号

class GrammarFuzzer(GrammarFuzzer):
    def init_tree(self):
        return (self.start_symbol, None)

执行并打印

f = GrammarFuzzer(EXPR_GRAMMAR)
print(f.init_tree())

作者给出了打印的图,但我这边没打印出来,我直接输出了
('<start>', None)
这个结果也表明了<start>还可以扩展节点

接下来我们创建一个函数expansion_to_children()用来扩展字符串并且将这个字符串分解成派生树列表,每个符号(相当于是树中的节点)对应一个派生树,再使用re.split()将字符串拆分为子节点列表

def expansion_to_children(expansion):
    # print("Converting " + repr(expansion))
    # strings contains all substrings -- both terminals and nonterminals such
    # that ''.join(strings) == expansion

    expansion = exp_string(expansion)
    assert isinstance(expansion, str)

    if expansion == "":  # Special case: epsilon expansion
        return [("", [])] #表示该节点后无子节点,即为终端节点

    strings = re.split(RE_NONTERMINAL, expansion)
    return [(s, None) if is_nonterminal(s) else (s, [])
            for s in strings if len(s) > 0]#遍历string,如果s非空且是非终端符号,则输出(s, None),若非空且为终端符号,则输出(s, [])

打印输出

print(expansion_to_children("<term> + <expr>"))

[('<term>', None), (' + ', []), ('<expr>', None)]
我们也可以来测试一下空字符

print(expansion_to_children(""))

[('', [])]

我们也可以惊醒进一步的测试,传入一个元组,观察是否可以正确的过滤额外的数据

print(expansion_to_children(("+<term>", ["extra_data"])))

[('+', []), ('<term>', None)]正确输出

我们将这个方法添加至类GrammerFuzzer

class GrammarFuzzer(GrammarFuzzer):
    def expansion_to_children(self, expansion):
        return expansion_to_children(expansion)

我们可以使用expand_node_randomly()方法在树中提取一些未展开的节点,选择一个随机扩展,并返回新的树。expand_node_randomly()可以使用方法choose_node_expansion()从子数组中随机选取一个未展开的节点(使用index定义)。

import random

class GrammarFuzzer(GrammarFuzzer):
    def choose_node_expansion(self, node, possible_children):
        """Return index of expansion in `possible_children` to be selected.  Defaults to random."""
        return random.randrange(0, len(possible_children)) #随机选择一个节点

    def expand_node_randomly(self, node):
        (symbol, children) = node
        assert children is None

        if self.log:
            print("Expanding", all_terminals(node), "randomly")

        # Fetch the possible expansions from grammar...
        expansions = self.grammar[symbol]
        possible_children = [self.expansion_to_children(
            expansion) for expansion in expansions]

        # ... and select a random expansion
        index = self.choose_node_expansion(node, possible_children)
        chosen_children = possible_children[index]

        # Process children (for subclasses)
        chosen_children = self.process_chosen_children(chosen_children,
                                                       expansions[index])

        # Return with new children
        return (symbol, chosen_children)

接下来我们先定义expand_node()方法用于稍后选择不同的扩展策略,在此之前,我们先用它来调用函数expand_node_randomly()

class GrammarFuzzer(GrammarFuzzer):
    def expand_node(self, node):
        return self.expand_node_randomly(node)

在定义一个辅助函数process_chosen_children()等稍后使用

class GrammarFuzzer(GrammarFuzzer):
    def process_chosen_children(self, chosen_children, expansion):
        """Process children after selection.  By default, does nothing."""
        return chosen_children

接下来我们可以观察expand_node_randomly()的运行方式

f = GrammarFuzzer(EXPR_GRAMMAR, log=True)

print("Before:")tree = ("<integer>", None)
display_tree(tree)

print("After:")tree = f.expand_node_randomly(tree)
display_tree(tree)

同样,我没打出来图,换为print打印输出
Before:
('<integer>', None)
After:
('<integer>', [('<digit>', None), ('<integer>', None)])

即可获得展开的节点

0x04 扩展一棵树

接下来我们可以将这种方法应用于扩展一棵树的节点,因此,首先我们需要在树中搜索未展开的节点

定义函数possible_expansions()来计算有多少棵未展开的树

class GrammarFuzzer(GrammarFuzzer):
    def possible_expansions(self, node):
        (symbol, children) = node
        if children is None:
            return 1

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

打印输出

f = GrammarFuzzer(EXPR_GRAMMAR)
print(f.possible_expansions(derivation_tree))

结果为
2
接下来我们定义方法any_possible_expansions(),当树中还存在未展开的子节点时,则方法返回True

class GrammarFuzzer(GrammarFuzzer):
    def any_possible_expansions(self, node):
        (symbol, children) = node
        if children is None:
            return True

        return any(self.any_possible_expansions(c) for c in children)

打印输出结果

f = GrammarFuzzer(EXPR_GRAMMAR)
f.any_possible_expansions(derivation_tree)

True

Last modification:January 24th, 2019 at 11:22 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment