Arya

Fuzzing with Grammars(一)
[+] 眼睛实在太疼了,可能是因为没休息好导致的上火,也可能是看屏幕时间太长了(委屈[+] 不能吃橘子了,改吃苹果...
扫描右侧二维码阅读全文
22
2019/01

Fuzzing with Grammars(一)

[+] 眼睛实在太疼了,可能是因为没休息好导致的上火,也可能是看屏幕时间太长了(委屈
[+] 不能吃橘子了,改吃苹果吧

在前一章学的是“基于突变的模糊化”,学会了如何在有输入条件限制的情况下,生成满足条件的输入,所以本章将进一步的深入这个话题,创建一个满足特殊条件的合法输入程序。

0x01 输入的语言

一个程序的所有可能产生的行为都是由其输入触发的,input的可能来源的范围很广,但是这些数据决定了一个程序的行为方式,包括程序执行失败。因此在测试的时候,考虑可能的输入源,如何控制这些输入的范围以及如何系统测试这些输入都非常重要。

同样为了简单起见,我们假设程序只有一个输入源。一个程序的有效输入集合叫做语言语言范围很大,由简单到复杂,比如CSV语言表示一组由逗号分隔的有效输入数据,而Python语言表示一组有效的Python程序。我们通常将数据语言与程序语言分开讨论,尽管任何程序也可以被视为输入数据(比如对编译器来说,程序也是输入数据)

为了能够正式地描述语言,形式语言(formal language)领域设计了许多描述语言的语言规范。正则表达式是一种对简单字符串进行操作的逻辑公式,例如正则表达式中[a-z]*表示小写字母的序列(可能为空)。自动机理论这些语言与接受这些输入的自动机连接起来,例如我们可以使用有限状态机来指定正则表达式的语言。

正则表达式可以很好地生成一些不太复杂的输入形式,并且关联的有限状态机具有许多特性,可以使它们非常适合进行一些推理。但是如果指定的输入很复杂,有限状态机很快就会遇到限制,所以我们需要一种策略来自动的来解决这个问题。

0x02 语法的规则和拓展

语言的语法是能够帮我们识别一种程序语言最直接的工具,每一种语言的语法都各不相同。语法可以表示输入语言的各种属性,也可以很好的表达输入的语法结构(如嵌套或者递归输入)。我们大多数时候使用的语法都是上下文无关语法,这也是一种最常用的语法形式。

语法由一个表示开始符号和一组扩展规则(或简单规则)组成,这些规则制定了如何扩展开始符号(或其他符号),例如,下面的语法,表示两位数字的序列

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

(不要紧,我也看不懂这个语法,继续往下看

上面这种语法是以下形式的变形

<A>::=<B>

表达式<A>::=<B>表示字符串<A>可以替换为字符串<B>

所以读懂这样的语法,首先从左边<start>开始,在上面第一句的中<start>被替换为<digit><digit>,在第二句中<digit>也被替换为右边的字符串,而特殊运算符|表示的意思,表示你可以选择其中任何一个数字,所以每一个<digit>被拓展成一个给定的数字,最后将产生一个00~99之间的数字。

语法的有趣之处在于他们是可以递归recursive的,因此我们进行扩展时可以利用前面的扩展符号然后再次扩展,例如

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

这里的<integer>要么表示的是<digit>是0~9之间的一个数字,要么表示的是<digit><integer>一个数字后面跟着一个整数。(这是作者的解释,不是很容易一下读懂)

接下来我简单利用python代码做的做一些小解释,原文中没有
我们可以把第二句看作是一个递归语句

def integer(number):
     if number=='<digit>' :
          return (random.randint(0,10))
     elif number=='<digit><integer>'
         print(random.randint(0,10))
         return integer(number) #此处的number值依然是随机的二者之一,依次递归直到number为<digit>为止

例如1234表示的是1后面跟着整数234,而同样234表示的是2后面跟着整数343之后跟着的是4,而4就是最内层循环的<digit>代表的那个数,而在1234中前三次选择的均为<digit><integer>,最后一次选择的是<digit>递归执行了4次之后输出结果。

此时我们可以看出,我们可以使用一个表达式表示一个整数,因此如果我们想表示一个有符号整数,我们也可以在表达式前面添加+或者-,语法格式如下

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

以上我们可以看出,这些语法规则正式地定义了语言:任何从表示开始的符号派生出来的部分都是语言的部分,任何不是从开始的符号派生出来的部分都不是语言的部分

0x03 算数表达式

刚才已经简单的说了表达式的写法,现在我们可以拓展我们的语法,来写一个涵盖完成算数表达式的语法,这也是一个典型的语法例子

<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

我们可以看见表达式<expr>要么表示和,要么表示差,要么表示<term>,而表达式<term>要么表示乘积,要么表示除法,要么表示<factor>,与此同时表达式<factor>要么表示一个的数字,要么是一个带着圆括号的表达式,几乎所有的规则都是可以递归的,因此我们可以表达例如(1 + 2) * (3.4 / 5.6 - 789)的复杂算数表达式。

在以上的语法规则中,我们从<start>开始,然后一个接着一个的展开不同的符号,并且随机选择代替项,生成不同的算数表达式。

基于这种语法fuzzing方法,我们可以快速高效的的产生复杂的输入,接下来就是实现这种输入的方式。

0x04 利用python表示语法

我们构建语法的fuzzer第一步是要找到合适的语法格式,为了简单起见,我们选择使用python语法中的映射规则来表示符号名与拓展之间的映射关系,我们可以列表来表示这种方式。

import fuzzingbook_utils
DIGIT_GRAMMAR = {
    "<start>":
        ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]}

表达方式类似于这种形式

EXPR_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"]}

打印输出<digit1>

print(EXPR_GRAMMAR["<digit>"])

['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

我们也可以检测某个符号是否存在这个语法中

print("<identifier>" in EXPR_GRAMMAR)

False

值得注意的是我们总是假设在规则的左侧(类似于映射中的键)总是一个单独的符号,这也是上下文无关语法的属性,这里我也贴出一篇文章,从英语角度出发,很好的解释了上下文无关语法的意思(不管怎么说人类的语言还是比较好懂的~( ̄▽ ̄~)~

0x05 一些定义

我们假设规则的开始符号是<start>

START_SYMBOL = "<start>"

我们定义一个函数nonterminals()从扩展中提取非终止符号的列表,即<>之间出空格以外的内容

import re

RE_NONTERMINAL = re.compile(r'(<[^<> ]*>)')#匹配除了'<','>',' '以外的字符

def nonterminals(expansion):
    # In later chapters, we allow expansions to be tuples,
    # with the expansion being the first element
    if isinstance(expansion, tuple):
        expansion = expansion[0]

    return re.findall(RE_NONTERMINAL, expansion)#匹配所有符合正则表达式的字符,并返回一个列表

接下来可以测试一下

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>"]

我们也可以使用is_nonterminal()检测符号是否为非终止符号

def is_nonterminal(s):
    return re.match(RE_NONTERMINAL, s)
assert is_nonterminal("<abc>")
assert is_nonterminal("<symbol-1>")
assert not is_nonterminal("+")

0x06 一个简单的语法fuzzer

我们可以使用上面的方法构建一个简单的语法fuzzer,先从<start>符号开始,再逐一进行扩展,为了避免扩展到无限输入的状态,我们设置一个最大值(max_nonterminals来限制非终止符号的数量,此外,为了避免程序无限的运行,我们也要限制扩展步骤的总数

import random

class ExpansionError(Exception):
    pass
def simple_grammar_fuzzer(grammar, start_symbol=START_SYMBOL,
                          max_nonterminals=10, max_expansion_trials=100,
                          log=False):
    term = start_symbol #赋初始值<start>
    expansion_trials = 0

    while len(nonterminals(term)) > 0: #如果term表示的字符为非终止符号
        symbol_to_expand = random.choice(nonterminals(term))#从生成的非终止符号中任选一符号
        expansions = grammar[symbol_to_expand]#从grammar中寻找该符号匹配的字符串列表
        expansion = random.choice(expansions)#从匹配的字符串列表中任选一个
        new_term = term.replace(symbol_to_expand, expansion, 1)#使用expansion代替symbol_to_expand赋值给new_term

        if len(nonterminals(new_term)) < max_nonterminals: #new_term中非终止符号长度如果小于最大非终止符号长度,赋值并输出
            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: #如果expansion_trial值大于等于可拓展的最大值,则报错并输出
                raise ExpansionError("Cannot expand " + repr(term))

    return term
simple_grammar_fuzzer(grammar=EXPR_GRAMMAR, max_nonterminals=3, log=True)

输出fuzzer之后的结果


<start> -> <expr>                        <expr>
<expr> -> <term> + <expr>                <term> + <expr>
<term> -> <factor>                       <factor> + <expr>
<factor> -> <integer>                    <integer> + <expr>
<integer> -> <digit>                     <digit> + <expr>
<digit> -> 6                             6 + <expr>
<expr> -> <term> - <expr>                6 + <term> - <expr>
<expr> -> <term>                         6 + <term> - <term>
<term> -> <factor>                       6 + <factor> - <term>
<factor> -> -<factor>                    6 + -<factor> - <term>
<term> -> <factor>                       6 + -<factor> - <factor>
<factor> -> (<expr>)                     6 + -(<expr>) - <factor>
<factor> -> (<expr>)                     6 + -(<expr>) - (<expr>)
<expr> -> <term>                         6 + -(<term>) - (<expr>)
<expr> -> <term>                         6 + -(<term>) - (<term>)
<term> -> <factor>                       6 + -(<factor>) - (<term>)
<factor> -> +<factor>                    6 + -(+<factor>) - (<term>)
<factor> -> +<factor>                    6 + -(++<factor>) - (<term>)
<term> -> <factor>                       6 + -(++<factor>) - (<factor>)
<factor> -> (<expr>)                     6 + -(++(<expr>)) - (<factor>)
<factor> -> <integer>                    6 + -(++(<expr>)) - (<integer>)
<expr> -> <term>                         6 + -(++(<term>)) - (<integer>)
<integer> -> <digit>                     6 + -(++(<term>)) - (<digit>)
<digit> -> 9                             6 + -(++(<term>)) - (9)
<term> -> <factor> * <term>              6 + -(++(<factor> * <term>)) - (9)
<term> -> <factor>                       6 + -(++(<factor> * <factor>)) - (9)
<factor> -> <integer>                    6 + -(++(<integer> * <factor>)) - (9)
<integer> -> <digit>                     6 + -(++(<digit> * <factor>)) - (9)
<digit> -> 2                             6 + -(++(2 * <factor>)) - (9)
<factor> -> +<factor>                    6 + -(++(2 * +<factor>)) - (9)
<factor> -> -<factor>                    6 + -(++(2 * +-<factor>)) - (9)
<factor> -> -<factor>                    6 + -(++(2 * +--<factor>)) - (9)
<factor> -> -<factor>                    6 + -(++(2 * +---<factor>)) - (9)
<factor> -> -<factor>                    6 + -(++(2 * +----<factor>)) - (9)
<factor> -> <integer>.<integer>          6 + -(++(2 * +----<integer>.<integer>)) - (9)
<integer> -> <digit>                     6 + -(++(2 * +----<digit>.<integer>)) - (9)
<integer> -> <digit>                     6 + -(++(2 * +----<digit>.<digit>)) - (9)
<digit> -> 1                             6 + -(++(2 * +----1.<digit>)) - (9)
<digit> -> 7                             6 + -(++(2 * +----1.7)) - (9)

'6 + -(++(2 * +----1.7)) - (9)'

我们也可以提高最大值限制,获得更多更长的语法规则

for i in range(10):
    print(simple_grammar_fuzzer(grammar=EXPR_GRAMMAR, max_nonterminals=5))

生成字符

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)

0x07 将语法可视化为铁路图(Railroad Diagrams)

我们可以使用语法表示一些算数表达式,如果在linux系统中我们可以直接将表达式发给bc计算机或者别的一些接受算数表达式的程序。

在此之家,我们在引入一个新的概念,将这些抽象的表达式可视化为一个视图——铁路图

Railroad diagrams,铁路图,也叫语法图,是一种表示形式语法的方式,也是上下文无关语法的图形表示。读图时按照可能的轨道从左往右读取;在轨道上遇上的符号序列定义了语言。

接下来,作者引入了他自己写的一个外部的可视化库RailroadDiagram

from RailroadDiagrams import NonTerminal, Terminal, Choice, HorizontalChoice, Sequence, Diagram, show_diagram
from IPython.display import SVG, display

接下来创建函数syntax_diagram_symbol()将符号可视化,我们使用椭圆形表示终端符号,非终端符号(如:<term>)表示为矩形

def syntax_diagram_symbol(symbol):
    if is_nonterminal(symbol):
        return NonTerminal(symbol[1:-1])
    else:
        return Terminal(symbol)

显示<term>的图像

SVG(show_diagram(syntax_diagram_symbol('<term>')))

显示图像
Image7-1.png

当然接下来还有很多代码,我都不打算继续贴出来了,一来这个代码掌握并不是最重要的,二来我并没能弹出图片,但是并不是说学到这里就结束了

我们要能读好铁路图,所以接下来我不会贴出作者写的代码,而是贴出每句话对应的铁路图

EXPR_GRAMMAR['<term>'][0]的值为<factor>*<term> 

铁路图
Image7-2.png

可以看出非终止符号<factor><term>用矩形表示,而终止符号*用椭圆表示

EXPR_GRAMMAR['<digit>'] 的值为["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]

铁路图
Image7-3.png

因为<digit>中没有非终止符号,所以均为中是符号,使用椭圆表示10个数字,读图时任选一条路一直走下去,经过上面的解释都不难懂,简单贴两张
Image7-4.png

掌握了所有规则之后就变得很简单了后面的图也都不成问题

Last modification:January 23rd, 2019 at 09:16 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment