Arya

Fuzzing with Grammars(二)
[+] 眼睛依然很疼,大概率是上火,可能我的身体知道最近要过年,上火都舍不得让我牙龈疼~[+] 偶尔学习学的也会很...
扫描右侧二维码阅读全文
23
2019/01

Fuzzing with Grammars(二)

[+] 眼睛依然很疼,大概率是上火,可能我的身体知道最近要过年,上火都舍不得让我牙龈疼~
[+] 偶尔学习学的也会很累啊,考研结束到现在还没有真正的玩过一整天(委屈

0x01 一些语法

昨天下午因为没能弹出图片折腾的我整个人都想跳过这一小节,后来又仔细看了一下接下来的代码,还是决定认认真真的写笔记,图片弹不出来也不妨碍我阅读代码,不是嘛

接下来作者为我们展现了CGI语法的铁路图形式,首先定义CGI

CGI_GRAMMAR = {
    "<start>":
        ["<string>"],

    "<string>":
        ["<letter>", "<letter><string>"],

    "<letter>":
        ["<plus>", "<percent>", "<other>"],

    "<plus>":
        ["+"],

    "<percent>":
        ["%<hexdigit><hexdigit>"],

    "<hexdigit>":
        ["0", "1", "2", "3", "4", "5", "6", "7",
            "8", "9", "a", "b", "c", "d", "e", "f"],

    "<other>":  # Actually, could be _all_ letters
        ["0", "1", "2", "3", "4", "5", "a", "b", "c", "d", "e", "-", "_"],}

显示铁路图

syntax_diagram(CGI_GRAMMAR)

铁路图如下
Image8-1.png
Image8-2.png

我们也可以生成简单的语法组合

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

生成随机的结果

+%9a
+++%ce+
+_
+%c6c
++
+%cd+5
1%ee
%b9%d5
%96
%57d%42

之前我们除了学了写cgi_decode fuzzer还写过url fuzzer,我们也可以通过适用语法生成大量的url

先定义url语法的一些现相关内容

URL_GRAMMAR = {
    "<start>":
        ["<url>"],
    "<url>":
        ["<scheme>://<authority><path><query>"],
    "<scheme>":
        ["http", "https", "ftp", "ftps"],
    "<authority>":
        ["<host>", "<host>:<port>", "<userinfo>@<host>", "<userinfo>@<host>:<port>"],
    "<host>":  # Just a few
        ["cispa.saarland", "www.google.com", "fuzzingbook.com"],
    "<port>":
        ["80", "8080", "<nat>"],
    "<nat>":
        ["<digit>", "<digit><digit>"],
    "<digit>":
        ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"],
    "<userinfo>":  # Just one
        ["user:password"],
    "<path>":  # Just a few
        ["", "/", "/<id>"],
    "<id>":  # Just a few
        ["abc", "def", "x<digit><digit>"],
    "<query>":
        ["", "?<params>"],
    "<params>":
        ["<param>", "<param>&<params>"],
    "<param>":  # Just a few
        ["<id>=<id>", "<id>=<nat>"],}

也可以画出相应的铁路图,这里我就不展示了,基本都是大同小异

直接生成较为复杂的url输入

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

输出结果

https://user:password@cispa.saarland:80/
http://fuzzingbook.com?def=56&x89=3&x46=48&def=def
ftp://cispa.saarland/?x71=5&x35=90&def=abc
https://cispa.saarland:80/def?def=7&x23=abc
https://fuzzingbook.com:80/
https://fuzzingbook.com:80/abc?def=abc&abc=x14&def=abc&abc=2&def=38
ftps://fuzzingbook.com/x87
https://user:password@fuzzingbook.com:6?def=54&x44=abc
http://fuzzingbook.com:80?x33=25&def=8
http://fuzzingbook.com:8080/def

成功生成了一些符合规则的url

0x03 语法的突变应用

语法的一个非常有用的特性就是可以产生的大部分的有效输入。从句法的角都来看,输入总是有效的,毕竟最后的结果都是符合语法结构的。但是有一些语义属性,例如,对于一个url,端口范围应该在1024~2048之间,那么这就很难用语法来实现,我们不太可能去写一个过长的列表进行随机选择,如果仅是一个还好,一个字典里都是很长的列表,那么使用语法使过程简洁高效的意义也就不存在了

那么解决这个问题的一种方式是添加一种约束附加到语法上,还有一种方法是将基于语法的fuzzer与基于突变的fuzzer的优势结合起来,使用语法生成的输入作为进一步基于突变的fuzzer的种子,换句话说就是先用语法生成合法的输入,再用突变进行模糊生成大量输入。这样我们不仅可以学到有效输入,还可以检查有效和无效输入的边界,也会产生一些有趣的错误(我现在也不知道是什么,那么接着往下看好了

为了将我们生成的输入作为输入数据使用,我们可以直接输入到前面我们写过的突变fuzzer中,这里我们将输入放在一个列表里

from MutationFuzzer import MutationFuzzer

number_of_seeds = 10seeds = [
    simple_grammar_fuzzer(
        grammar=URL_GRAMMAR,
        max_nonterminals=10) for i in range(number_of_seeds)]
print(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/']

将输入作为种子,进行突变fuzzing

m = MutationFuzzer(seeds)
[m.fuzz() for i in range(20)]

生成了一些随机输入

['https://cispa.saarland/', 'ftps://user:password@fuzzingbook.com:80/?abc=06', 'ftps://cispa.saarland/?abc=x13&abc=abc', 'ftp://fuzzingbook.com/?x83=abc&def=abc', 'http://www.google.com:8080?x11=x18', 'ftp://www.google.com?abc=4&x87=def&x42=4', 'http://user:password@www.google.com/x60', 'http://fuzzingbook.com/?abc=12', 'ftps://cispa.saarland:80', 'http://user:password@cispa.saarland/def?def=24', 'f\\tBps://cispa.saQarland/?abc=x13&abc=ab', 'http:?user:4pa9ssword@ccpa.saalanddef?def=2b', 'ftps:.cispa:saarlnl/abx=x13&abc=abc', 'ftps://user:password@fuzzinebook.com:80/?ab=06f', "https:/'cispansaarland/", 'Ftpsz//cnspjansaarland/\x7fabc=x3&abc=ac', 'ftps//user:password@fuzzingbook.com:0/n?abc=H06', 'ftps://cispa.saarlan(d/abc=x13&abc=abc', 'http://www.google>com:8080?x811=px183', 'ftps:/ci9spa.saarl!nWd/?ab=x13&aba=jabc']

我们可以利用这种突变的方式生成更多不同的符合结构的url,基于此,我们也可以在学完这一章,尝试自己写符合结构的url生成器。

0x04 语法工具箱

接下来介绍一些编写语法的小技巧

在我们学的语法中,使用<>来分割非终止符号,假设我们想利用代码,随机生成一些类似<symbol>的非终端符号,那么我们要如何实际的表达<>呢?
那么没有什么是语法解决不了的,如果有,那就语法来表达语法(哈哈哈哈哈

我们定义一个列表simple_nonterminal_grammar,在定义键值对<left-angle><right-angle><>,我们可以在这两个符号之间随意的生成自己想要的非终止符号的字符串

simple_nonterminal_grammar = {
    "<start>": ["<nonterminal>"],
    "<nonterminal>": ["<left-angle><identifier><right-angle>"],
    "<left-angle>": ["<"],
    "<right-angle>": [">"],
    "<identifier>": ["id"]  # for now}

我们可以随意定义<identifier>的值,生成我们想要的非终止符号,这也是我们现在使用的语法规则

接下来我们就可以自己利用现有的语法规则G,创建新的语法G'。我们先将G复制到G',再使用新的方法扩展现有规则,或者是添加一些新的符号,

import copy

nonterminal_grammar = copy.deepcopy(simple_nonterminal_grammar)
nonterminal_grammar["<identifier>"] = ["<idchar>", "<identifier><idchar>"]
nonterminal_grammar["<idchar>"] = ['a', 'b', 'c', 'd']  # for now

这样我们在原来语法规则的基础上,又重新生成了新的语法规则,打印输出
{'<start>': ['<nonterminal>'], '<nonterminal>': ['<left-angle><identifier><right-angle>'], '<left-angle>': ['<'],'<right-angle>': ['>'],'<identifier>': ['<idchar>', '<identifier><idchar>'],'<idchar>': ['a', 'b', 'c', 'd']}

我们可以利用这种思路来不断创造新的非终端符号,本着简洁的思想,定义一个函数extend_grammar()来完成这些操作

def extend_grammar(grammar, extension={}):    
     new_grammar = copy.deepcopy(grammar)
     new_grammar.update(extension)
return new_grammar

接下来我们可以直接调用函数来给非终端符号增加新的定义

nonterminal_grammar = extend_grammar(simple_nonterminal_grammar,
                                     {
                                         "<identifier>": ["<idchar>", "<identifier><idchar>"],
                                         # for now
                                         "<idchar>": ['a', 'b', 'c', 'd']
                                     }
                                     )

初步简化就完成了。

那么在nonterminal_grammar中,我们只枚举前几个字母,实际上,我们是不可能手动列举所有的字母,比如写成<idchar> ::= 'a' | 'b' | 'c' ...,那也实在是太多了不是?然而,语法是程序的一部分,我们也可以用编程的方式构造。
我们可以定义一个函数sragne()来构造一个字符串中的字符列表

import string
def srange(characters):
    """Construct a list with all characters in the string"""
    return [c for c in characters]#以列表形式获取所需要的字符

我们可以将一个包含着所有字母的ascii码的常量`
string.ascii_letters`传给这个函数,

>>>string.ascii_letters
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

获取前10个字符

print(srange(string.ascii_letters)[:10])
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

我们也可以通过常量string.digits获取数字0~9

>>>string.digits
'0123456789’

接下来我们可以在语法中使用这种方法来快速定义标识符


nonterminal_grammar = extend_grammar(nonterminal_grammar,
                                     {
                                         "<idchar>": srange(string.ascii_letters) + srange(string.digits) + srange("-_")#<idchar>对应为a~z,A~Z,0~9,-_组成的一个列表
                                     }
                                     )

<identifier>fuzzing后输入前10位

print([simple_grammar_fuzzer(nonterminal_grammar, "<identifier>") 
for i in range(10)])

['b', 'd', 'V9', 'x4c', 'YdiEWj', 'c', 'xd', '7', 'vIU', 'QhKD']

当然我们也可以定义一个函数crange(start,end),通过编码ascii码,返回你想要的字符

def crange(character_start, character_end):
    return [chr(i)
            for i in range(ord(character_start), ord(character_end) + 1)]

假设我们只需要数字

crange('0', '9')

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

0x05 一些简便的写法

上面介绍的nonterminal_grammar和其他的语法一样,内部都存在着递归的语法规则,如

nonterminal_grammar["<identifier>"]

['<idchar>', '<identifier><idchar>']
这种情况下,如果我们选择的是<identifier><idchar>赋值给<iderntifier>,则需要递归<identifier>

那么我们要怎么实现这种递归的方式呢?
当然,我也不会(哈哈哈哈

那么先把这个难题放在一遍,我们先研究一个比较简单的问题,根据上面的式子,我们可以获得的信息是,我们的非终端符号应该是一个非空的字符序列,比如

<identifier> = <idchar>+

我知道这句话有点难懂,但是作者给出的就是这种解释,我换句话解释一下就好懂很多

因为<ideneifier>无论是否进入递归循环,最后一定是一个字符或者是一堆字符组成的字符串,而这些字符则是从<idchar>中随机获得的,所以说我们的非终端符号应该是一个非空的字符序列

你说那个+号吗?哈,你还记得正则表达式吗?
没错,接下来作者想利用类似于正则表达式的方式代替原本的循环。我们应当还记得正则表达式中的+*的意思,作者这里也希望通过这些符号表示某些字符重复出现或者是一次都不出现的情况。

这种引入+运算符简化表达的方式,从形式上被称为Backus-Naur form,我们就简称为BNF,我们接下来的任务就是将BNF扩展(extend),简称为EBNF

那么现在作者提出了一种方法

  • <symbol>?表示<symbol>出现1次或者是0次
  • <symbol>+表示<symbol>出现1次或者是多次
  • <symbol>*表示<symbol>出现0次或者是多次

既然都已经模拟出了一套类似正则的表达方式,那么我们也可以顺便套用正则表达式中()的用处,我们用(<sakura><Li>)?用来表示我们可以选择<sakura>或者是<Li>

那么,既然有了这种方式,我们可以先把这种方法定义出来,举个例子,比如我们将与原本对<identifier>的定义给换一下,就用上述的思想

nonterminal_ebnf_grammar = extend_grammar(nonterminal_grammar,
                                          {
                                              "<identifier>": ["<idchar>+"]
                                          }
                                          )

那么接下来,我们就可以简单的把所有的表示方式都给替换了

EXPR_EBNF_GRAMMAR = {
    "<start>":
        ["<expr>"],

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

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

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

    "<sign>":
        ["+", "-"],

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

    "<digit>":
        srange(string.digits)}

这里我们将原本就在符号前用来表示正负号的+ -定义为<sign>
成功替换

接下来我们还要考虑一个新的问题,既然我们已经有了EBNF,也就是扩展后的BNF,那么,为了之后可以直接用扩展后的语法式,我们要给这些语法式映射回我们原来想表达的意思中,即完成EBNF-->BNF的转化

转化需要以下的规则

  • 将形如(content)op的表达式变为<new-symbol>op,其中op+ ? *中的一个)
  • 将形如<symbol>的表达式变为<new-symbol>,其中<new-symbol> ::= <empty> | <symbol>

    • 将形如<symbol>+的表达式变为<new-symbol>,其中`
      <new-symbol> ::= <symbol> | <symbol><new-symbol>`
  • 将形如<symbol>*的表达式变成为`
    <new-symbol> ::= <empty> | <symbol><new-symbol>`

此处的<empty>展开为空字符串

将这些规则运用到我们刚才的代码中,则

  • <idchar>+转化为<idchar><new-symbol>,其中<new-symbol> ::= <idchar> | <idchar><new-symbol>
  • <integer>(.<integer>)?转化为<integer><new-symbol>,其中<new-symbol> ::= <empty> | .<integer>.

那么接下来,我们需要一步步的实现这些

0x06 转化代码实现

首先,我们需要一种机制来创建一些新的符号

def new_symbol(grammar, symbol_name="<symbol>"):
    """Return a new symbol for `grammar` based on `symbol_name`"""
    if symbol_name not in grammar:
        return symbol_name

    count = 1
    while True:
        tentative_symbol_name = symbol_name[:-1] + "-" + repr(count) + ">"
        if tentative_symbol_name not in grammar:
            return tentative_symbol_name
        count += 1 #简单的将原有符号修改成新的符号

利用断言方式检测一下以上代码

assert new_symbol(EXPR_EBNF_GRAMMAR, '<expr>') == '<expr-1>'

ok,正确无误

接下来,我们需要从以上的表达式中提取出(),之前我们说了,利用()来表示内部符号可选
利用正则匹配

RE_PARENTHESIZED_EXPR = re.compile(r'\([^()]*\)[?+*]') #这里也匹配了'()'外部存在的'+ * ?'符号
def parenthesized_expressions(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_PARENTHESIZED_EXPR, expansion)

检测转化是否成功

assert parenthesized_expressions("(<foo>)* (<foo><bar>)+ (+<foo>)? <integer>(.<integer>)?") == [
    '(<foo>)*', '(<foo><bar>)+', '(+<foo>)?', '(.<integer>)?']

最后一步,我们需要将()去掉,将原本含有()的表达式变回只含有<>的表达式

def convert_ebnf_parentheses(ebnf_grammar):
    """Convert a grammar in extended BNF to BNF"""
    grammar = extend_grammar(ebnf_grammar)
    for nonterminal in ebnf_grammar:
        expansions = ebnf_grammar[nonterminal]

        for i in range(len(expansions)): #将表达式式中的每个圆括号,一个一个替换
            expansion = expansions[i]

            while True:#将每个部分中的含有圆括号的表达式匹配出来
                parenthesized_exprs = parenthesized_expressions(expansion)
                if len(parenthesized_exprs) == 0:
                    break

                for expr in parenthesized_exprs:
                    operator = expr[-1:] #提取出括号外的符号'+'、'*'、'?'
                    contents = expr[1:-2]#去除括号中的字符

                    new_sym = new_symbol(grammar) #创建一个新的<symbol>
                    expansion = grammar[nonterminal][i].replace(
                        expr, new_sym + operator, 1)
                    grammar[nonterminal][i] = expansion
                    grammar[new_sym] = [contents]

    return grammar
print(convert_ebnf_parentheses({"<number>": ["<integer>(.<integer>)?"]}))

输出
{'<number>': ['<integer><symbol>?'], '<symbol>': ['.<integer>']}

print(convert_ebnf_parentheses({"<foo>": ["((<foo>)?)+"]}))

输出
{'<foo>': ['<symbol-1>+'], '<symbol>': ['<foo>'], '<symbol-1>': ['<symbol>?']}

括号运算符我们已经可以成功解决了
那么现在问题来了,我们只是脱了一层壳,并没有把+*?的表达式给表示出来,那么接下来,我们要做的是,把这些符号提取出来,并转化成原来的形式

首先,如法炮制上面的步骤,把这些符号都给正则匹配出来

RE_EXTENDED_NONTERMINAL = re.compile(r'(<[^<> ]*>[?+*])')
def extended_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_EXTENDED_NONTERMINAL, expansion)

检测一下

assert extended_nonterminals(
    "<foo>* <bar>+ <elem>? <none>") == ['<foo>*', '<bar>+', '<elem>?']

正确无误

接下来,我们要把每个符号表示的意思给写出来


def convert_ebnf_operators(ebnf_grammar):
    """Convert a grammar in extended BNF to BNF"""
    grammar = extend_grammar(ebnf_grammar)
    for nonterminal in ebnf_grammar:
        expansions = ebnf_grammar[nonterminal]

        for i in range(len(expansions)):
            expansion = expansions[i]
            extended_symbols = extended_nonterminals(expansion)

            for extended_symbol in extended_symbols:
                operator = extended_symbol[-1:]#提取出操作符
                original_symbol = extended_symbol[:-1]

                new_sym = new_symbol(grammar, original_symbol)
                grammar[nonterminal][i] = grammar[nonterminal][i].replace(
                    extended_symbol, new_sym, 1)

                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]

    return grammar

检测一下是否可以正确输出

convert_ebnf_operators({"<integer>": ["<digit>+"]})

{'<integer>': ['<digit>'], '<digit>': ['<digit>', '<digit><digit>']}

OK,这样我们就完成了全过程

0x07 写法汇总

我们在上面已经成功的把所有表达式完成了成功的转化,现在,我们可以将方法集成在一个函数中,进行测试,先是去括号,然后去符号

def convert_ebnf_grammar(ebnf_grammar):
    return convert_ebnf_operators(convert_ebnf_parentheses(ebnf_grammar))

测试并打印输出

print(convert_ebnf_grammar({"<authority>": ["(<userinfo>@)?<host>(:<port>)?"]}))

{'<authority>': ['<symbol-2><host><symbol-1-1>'],
'<symbol>': ['<userinfo>@'],
'<symbol-1>': [':<port>'],
'<symbol-2>': ['', '<symbol>'],
'<symbol-1-1>': ['', '<symbol-1>']}

那么,我们可以将最开始的表达式EXPR_EBNF_GRAMMAR测试输出

expr_grammar = print(convert_ebnf_grammar(EXPR_EBNF_GRAMMAR)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>']}

终于完成了全部的转化

[+] 终于把本章给结束了,算是学到现在感觉陌生知识最多的一章,显示铁路图,然后是语法的表示
[+] 算是慢慢了解一些计算机语言的思想,收货还是很多的

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

Leave a Comment