Arya

Grammar Coverage(二)
0x01 深度覆盖从上面的例子我们可以看出如何为单个规则选择扩展,但是我们之前写过了很多规则及其代码,我们可以尝试...
扫描右侧二维码阅读全文
20
2019/02

Grammar Coverage(二)

0x01 深度覆盖

从上面的例子我们可以看出如何为单个规则选择扩展,但是我们之前写过了很多规则及其代码,我们可以尝试对其他的语法规则进行覆盖。

比如我们对CGI语法规则进行扩展,首先我们查看CGI_GRAMMAR

print(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>': ['0', '1', '2', '3', '4', '5', 'a', 'b', 'c', 'd', 'e', '-', '_']}

CGI_GRAMMAR进行简单的fuzz

f =SimpleGrammarCoverageFuzzer(CGI_GRAMMAR)
for i in range(10):
    print(f.fuzz())

打印输出fuzz之后的结果

c
+%a6++
+-
+
++
%18%b7
+e
_
d2+%e3
%d0

我们可以检查没有被覆盖到的语句

f.missing_expansion_coverage()
{'<hexdigit> -> 2',
 '<hexdigit> -> 4',
 '<hexdigit> -> 5',
 '<hexdigit> -> 9',
 '<hexdigit> -> c',
 '<hexdigit> -> f',
 '<other> -> 0',
 '<other> -> 1',
 '<other> -> 3',
 '<other> -> 4',
 '<other> -> 5',
 '<other> -> a',
 '<other> -> b'}

可以看出的是,在10次迭代之后,仍然有很多语句未被覆盖。那么问题出在哪里呢?简单说来,在CGI的语法中,我们需要覆盖的最大变量就是<hexdigit>,因此,我们需要达到它的最大扩展。
假设,我们需要扩展符号<letter>,我们可以选择以下三个扩展

print(CGI_GRAMMAR["<letter>"])

['<plus>', '<percent>', '<other>']
如果上面的三个扩展都被覆盖了,接下来我们可以调用函数choose_node_expansion()随机选择一个扩展,当然,如果此时我们选择了扩展<percent>,那么接下来需要覆盖的工作量就巨大了。

因此我们需要选择一个最好的策略来覆盖<percent>一方面是避免工作量过大,一方面是为了尽可能的覆盖到全部子节点。

为了解决这个问题,我们定义一个新的继承类SimpleGrammarCoverageFuzzer的类GrammarCoverageFuzzer。首先我们需要计算特定符号可以达到的最大扩展集合,类似于我们已有的方法max_expansion_coverage()。我们希望能够计算出这个集合和已经覆盖的集合的交集,这样我们就可以获得一个非空的交集,即已展开的符号的集合。

第一步,先计算一个符号可以达到的最大扩展集,当然之前已经实现了

f =SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR)
f.max_expansion_coverage('<integer>')

打印输出<integer>最大扩展
{'<digit> -> 0','<digit> -> 1','<digit> -> 2','<digit> -> 3','<digit> -> 4','<digit> -> 5','<digit> -> 6','<digit> -> 7','<digit> -> 8','<digit> -> 9',<integer> -> <digit>','<integer> -> <digit><integer>'}

f.max_expansion_coverage('<digit>')

打印输出<digit>的最大扩展
{'<digit> -> 0',<digit> -> 1','<digit> -> 2','<digit> -> 3','<digit> -> 4','<digit> -> 5','<digit> -> 6','<digit> -> 7','<digit> -> 8','<digit> -> 9'}

接下来我们可以开始实现类GrammarcOverageFuzzer,通过调用方法max_expansion_coverage()获得所有未被覆盖的子节点。

class GrammarCoverageFuzzer(SimpleGrammarCoverageFuzzer):
    def _new_child_coverage(self, children, max_depth):
        new_cov = set()
        for (c_symbol, _) in children:
            if c_symbol in self.grammar:
                new_cov |= self.max_expansion_coverage(
                    c_symbol, max_depth)
        return new_cov

    def new_child_coverage(self, symbol, children, max_depth=float('inf')):
        """Return new coverage that would be obtained by expanding (symbol, children)"""
        new_cov = self._new_child_coverage(children, max_depth)
        new_cov.add(expansion_key(symbol, children))
        new_cov -= self.expansion_coverage()   # -= is set subtraction
        return new_cov

为了演示新的方法new_child_coverage(),我们先随机选择一个节点覆盖

f = GrammarCoverageFuzzer(EXPR_GRAMMAR, start_symbol="<digit>", log=True)
print(f.fuzz())

打印输出

Tree: <digit>
Expanding <digit> randomly
Now covered: <digit> -> 2
Tree: 2
'2'

'2'

查看当前的覆盖

print(f.expansion_coverage())

{'<digit> -> 2'}
通过调用方法new_child_coverage(),查看所有节点的覆盖情况

for expansion in EXPR_GRAMMAR["<digit>"]:
    children = f.expansion_to_children(expansion)
    print(expansion, f.new_child_coverage("<digit>", children))

打印输出

0 {'<digit> -> 0'}
1 {'<digit> -> 1'}
2 set()
3 {'<digit> -> 3'}
4 {'<digit> -> 4'}
5 {'<digit> -> 5'}
6 {'<digit> -> 6'}
7 {'<digit> -> 7'}
8 {'<digit> -> 8'}
9 {'<digit> -> 9'}

可以看出除了刚才我们已经覆盖的节点之外,其他节点都给出了可以覆盖的范围,这也意味着,我们可以利用new_child_coverage()方法选择接下来需要进行的扩展。

0x02 整体覆盖率

当我们随机选择一个子节点时,我们没法获得整个语法规则的最大整体覆盖率,所以我们制定一个这样的策略,先采取广度优先扩展,首先覆盖到给定深度的所有扩展,然后再进行深度扩展,最后确定最大覆盖率。这种策略的核心方法是new_coverages():从最大深度(max_depth)为零开始,然后不断增加深度,直到找最后的一个扩展项为止

class GrammarCoverageFuzzer(GrammarCoverageFuzzer):
    def new_coverages(self, node, possible_children):
        """Return coverage to be obtained for each child at minimum depth"""
        (symbol, children) = node
        for max_depth in range(len(self.grammar)):
            new_coverages = [
                self.new_child_coverage(
                    symbol, c, max_depth) for c in possible_children]
            max_new_coverage = max(len(new_coverage)
                                   for new_coverage in new_coverages)
            if max_new_coverage > 0:
                # Uncovered node found
                return new_coverages

        # All covered
        return None

我们现在定义choose_node_expansion()利用上面的策略,首先我们

class GrammarCoverageFuzzer(GrammarCoverageFuzzer):
    def choose_node_expansion(self, node, possible_children):
        (symbol, children) = node
        new_coverages = self.new_coverages(node, possible_children)

        if new_coverages is None:
            # All expansions covered - use superclass method
            return self.choose_covered_node_expansion(node, possible_children)

        max_new_coverage = max(len(cov) for cov in new_coverages)

        children_with_max_new_coverage = [c for (i, c) in enumerate(possible_children)
                                          if len(new_coverages[i]) == max_new_coverage]
        index_map = [i for (i, c) in enumerate(possible_children)
                     if len(new_coverages[i]) == max_new_coverage]

        # Select a random expansion
        new_children_index = self.choose_uncovered_node_expansion(
            node, children_with_max_new_coverage)
        new_children = children_with_max_new_coverage[new_children_index]

        # Save the expansion as covered
        key = expansion_key(symbol, new_children)

        if self.log:
            print("Now covered:", key)
        self.covered_expansions.add(key)

        return index_map[new_children_index]

现在我们快速地可以对所有符号进行覆盖,

f = GrammarCoverageFuzzer(EXPR_GRAMMAR, min_nonterminals=3)
print(f.fuzz())

'-4.02 / (1) * +3 + 5.9 / 7 * 8 - 6'
查看一下是否还有位被覆盖的

f.max_expansion_coverage() - f.expansion_coverage()

set()
可以看到已经没有未被覆盖的语法符号

接下来计算执行时的平均扩展字符

average_length_until_full_coverage(GrammarCoverageFuzzer(EXPR_GRAMMAR))

在CGI语法中,只需要几次迭代就可以覆盖所有字母和数字

f = GrammarCoverageFuzzer(CGI_GRAMMAR, min_nonterminals=5)while len(f.max_expansion_coverage() - f.expansion_coverage()) > 0:
    print(f.fuzz())

%18%d03
%c3%94%7f+cd
%a6%b5%e2%5e%4c-54e01a2
%5eb%7cb_ec%a0+

我们可以将改进后的算法的效率通之前的几种fuzz方式的效率进行比较

average_length_until_full_coverage(TrackingGrammarCoverageFuzzer(CGI_GRAMMAR))

211.34

average_length_until_full_coverage(SimpleGrammarCoverageFuzzer(CGI_GRAMMAR))

68.64

average_length_until_full_coverage(GrammarCoverageFuzzer(CGI_GRAMMAR))

40.38

其实可以看出,新的策略要更加优于原有的策略。

因为我们在写语法的时候,很多非终结符并不会只出现在一个地方,往往会用于递归或者组成新的语法规则中,例如<integer>不仅可以用于表示整数,也可以用来表示小数

EXPR_GRAMMAR["<factor>"]

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

之前我们已经写了可以覆盖到每一个子节点的代码,所以我们可以确保我们覆盖到<digit>的每一个扩展,即0~9。但是,单个数字将分布在语法中所分布的各个<integer>中,所以不一定能产生我们需要的所有数字。如果我们能够产生诸如1234.567890,我们就可以完全覆盖所有数字的扩展。但是在上面对<factor>的拓展中,<integer>.<integer><integer>只能够分别覆盖数字的一小部分。所以我们希望能够用所有数字去测试这里的功能,并且还希望能用每个数字测试浮点数的整数部分和小数部分。

如果我们接下来使用的所有符号都是上下文无关语法的方式(我们刚才使用的<integer><digit><factor>中的用法),那么我们可以忽略使用符号的上下文。如果在我们的语法中没有给出这个符号,我们可以手动创建这样的符号,该符号是旧符号的副本,来实现上面提到的功能,接下来手动操作。

0x03 为上下文覆盖手动扩展的语法

根据上面的分析得到,在上下文中实现覆盖的一个简单的方法是复制符号以及他们引用的规则。例如,我们可以将<integer>替换为<integer-1>,integer-2.,并赋予与原始的<integer>相同的定义,这意味着接下来我们不仅要副高<integer>的所有扩展,还要覆盖<integer-1><integer-2>的·所有扩展

给出代码

dup_expr_grammar = extend_grammar(EXPR_GRAMMAR,
                                  {
                                      "<factor>": ["+<factor>", "-<factor>", "(<expr>)", "<integer-1>.<integer-2>", "<integer>"],
                                      "<integer-1>": ["<digit-1><integer-1>", "<digit-1>"],
                                      "<integer-2>": ["<digit-2><integer-2>", "<digit-2>"],
                                      "<digit-1>":
                                      ["0", "1", "2", "3", "4",
                                          "5", "6", "7", "8", "9"],
                                      "<digit-2>":
                                      ["0", "1", "2", "3", "4",
                                          "5", "6", "7", "8", "9"]
                                  }
                                  )

检测代码的语法合规性

assert is_valid_grammar(dup_expr_grammar)

正确无误,接下来,我们使用这个扩展语法运行基于coverage的fuzzer,我们将覆盖所有数字,包括规则整数以及浮点数

f = GrammarCoverageFuzzer(dup_expr_grammar, start_symbol="<factor>")
for i in range(10):
    print(f.fuzz())

`-(43.76 / 8.0 5.5 / 6.9 6 / 4 + +03)
(90.1 - 1 7.3 9 + 5 / 8 / 7)
2.8
1.2
10.4
2
4386
7
0
08929.4302`

0x04 用编程的方式覆盖上下文无关语法

如果我们想在上下文中增强覆盖率,通过手动的方式调整语法一定不是最佳选择。因为我们对语法的任何一点修改,都必须在所有副本进行同样的修改复制。因此我们引入一个函数来完成复制。我们使用函数duplicate ate_context()接受语法、语法中的符号和该符号的扩展(None或者符号的所扩展),并更改扩展以应用所有最初引用的规则的副本。其思想如下,

dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
duplicate_context(dup_expr_grammar, "<factor>", "<integer>.<integer>") #将原本与法中的所有<factor>中的<integer>.<integer>进行替换

我们通过调用这个函数后,得到与手动更改类似的结果。

代码如下:

from Grammars import new_symbol, unreachable_nonterminals
from GrammarFuzzer import expansion_to_children

def duplicate_context(grammar, symbol, expansion=None, depth=float('inf')):
    """Duplicate an expansion within a grammar.

    In the given grammar, take the given expansion of the given symbol
    (if expansion is omitted: all symbols), and replace it with a
    new expansion referring to a duplicate of all originally referenced rules.

    If depth is given, limit duplication to `depth` references (default: unlimited)
    """
    orig_grammar = extend_grammar(grammar)
    _duplicate_context(grammar, orig_grammar, symbol,
                       expansion, depth, seen={})

    # After duplication, we may have unreachable rules; delete them
    for nonterminal in unreachable_nonterminals(grammar):
        del grammar[nonterminal]

上面带八中的大部分工作都是在助手函数,即missing_expansion_coverage()函数中完成地。通过附加参数seen跟踪已经展开地符号,并避免无限递归.

下面是函数_duplicate_context()的具体实现

import copy

def _duplicate_context(grammar, orig_grammar, symbol, expansion, depth, seen):
    for i in range(len(grammar[symbol])):
        if expansion is None or grammar[symbol][i] == expansion:
            new_expansion = ""
            for (s, c) in expansion_to_children(grammar[symbol][i]):
                if s in seen:                 # 已经复制过了
                    new_expansion += seen[s]
                elif c == [] or depth == 0:   # c为终端符号或者地柜结束
                    new_expansion += s
                else:                         # Nonterminal symbol - duplicate
                    # Add new symbol with copy of rule
                    new_s = new_symbol(grammar, s)
                    grammar[new_s] = copy.deepcopy(orig_grammar[s])

                    # Duplicate its expansions recursively
                    # {**seen, **{s: new_s}} is seen + {s: new_s}
                    _duplicate_context(grammar, orig_grammar, new_s, expansion=None,
                                       depth=depth - 1, seen={**seen, **{s: new_s}})
                    new_expansion += new_s

            grammar[symbol][i] = new_expansion

上面展示了函数的工作过程,那么,实际操作一下。我们使用函数复制表达式语法的<integer>.<integer>扩展,并获得一个具有新的语法的<integer-1>.<integer-2>扩展(其中<integer-1><integer-2>均符合原有规则)

dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
duplicate_context(dup_expr_grammar, "<factor>", "<integer>.<integer>")
dup_expr_grammar

运行结果为

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

这样我们就完成了扩展和复制工作,打印fuzz结果

f = GrammarCoverageFuzzer(dup_expr_grammar, start_symbol="<factor>")
for i in range(10):
    print(f.fuzz())

返回结果

(57.5)
2
+-(1 / 3 + 6 / 0 - 7 * 59 * 3 + 8 * 4)
374.88
5.709
0.93
01.1
892.27
219.50
6.636

我们可以通过控制depth参数来控制复制的深度,也即递归的深度

dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
duplicate_context(dup_expr_grammar, "<factor>", "<integer>.<integer>", depth=1)
print(dup_expr_grammar)

返回结果,此时值复制了下一条规则

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

在默认情况下,深度设置为,表示无限的重复,当然真正的无线重复会导致递归语法出问题,因此duplicate_context()函数被设置为一旦复制过符号就不再重复复制符号,尽管如此,假设我们应用该函数来福之所有的扩展,我们依然会得到一个不少于296条规则的语法

dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
duplicate_context(dup_expr_grammar, "<expr>")

assert is_valid_grammar(dup_expr_grammar)
print(len(dup_expr_grammar))

292

假设我们使用这种规则,那么我们就要覆盖将近2000个扩展

f = GrammarCoverageFuzzer(dup_expr_grammar)
len(f.max_expansion_coverage())

1981

我们可以重复复制一次,然后不断地增加语法和覆盖率要求

dup_expr_grammar = extend_grammar(EXPR_GRAMMAR)
duplicate_context(dup_expr_grammar, "<expr>")
duplicate_context(dup_expr_grammar, "<expr-1>")
len(dup_expr_grammar)

594

f = GrammarCoverageFuzzer(dup_expr_grammar)
print(len(f.max_expansion_coverage()))

3994

我们可以通过这种方式实现上下文无语法的单独覆盖

print(dup_expr_grammar["<expr>"])

['<term-1> + <expr-4>', '<term-5> - <expr-8>', '<term-9>']

print(dup_expr_grammar["<term-1-1>"])

['<factor-1-1> * <term-1-1>', '<factor-2-1> / <term-1-1>', '<factor-3-1>']

print(dup_expr_grammar["<factor-1-1>"])

['+<factor-1-1>',
 '-<factor-1-1>',
 '(<expr-1-1>)',
 '<integer-1-1>.<integer-2-1>',
 '<integer-3-1>']

上面代码生成的语法可能不会用在我们正常的代码中,但使如果真的需要覆盖生成的所有语法规则,同样适用类GrammarCoverageFuzzer()即可

0x05通过覆盖语法来覆盖代码

通过系统的覆盖所有输入元素,我们可以获得极大的输入多样性,但是我们能否将这种覆盖转化为一种更广泛的程序行为呢?同时在覆盖的程序行为中,我们也想覆盖一些意外的行为。在语法中,有直接对应与程序特性的元素。程序处理算术表达式具有由单个元素直接触发的功能,例如,由+符号触发的加法功能,由-符号出发的减法功能,以及由输入中的浮点数的出现出发的浮点运算功能。输入结构和功能之间的这种连接导致语法覆盖和代码覆盖之间的强相关性,换句话说:如果我们能够实现高语法覆盖率,同样也能提高代码覆盖率。

我们利用CGI语法探索这种关系,假设我们需要计算一个映射coverages,其中coverages = {y_1, y_2, ...},x为第n次运算获得的语法覆盖率,y_n为第n次运行获得的代码覆盖率。

首先我们来计算最大覆盖率

from Coverage import Coverage, cgi_decode

with Coverage() as cov_max:
    cgi_decode('+')
    cgi_decode('%20')
    cgi_decode('abc')
    try:
        cgi_decode('%?a')
    except:
        pass

f = GrammarCoverageFuzzer(CGI_GRAMMAR, max_nonterminals=2)
coverages = {}

trials = 100
for trial in range(trials):
    f.reset_coverage()
    overall_cov = set()
    max_cov = 30

    for i in range(10):
        s = f.fuzz()
        with Coverage() as cov:
            cgi_decode(s)
        overall_cov |= cov.coverage()

        x = len(f.expansion_coverage()) * 100 / len(f.max_expansion_coverage())
        y = len(overall_cov) * 100 / len(cov_max.coverage())
        if x not in coverages:
            coverages[x] = []
        coverages[x].append(y)

接下来我们计算y的值

xs = list(coverages.keys())
ys = [sum(coverages[x]) / len(coverages[x]) for x in coverages]

绘制对应的变化图像

import matplotlib.pyplot as plt
import matplotlib.ticker as mtick

ax = plt.axes(label="coverage")
ax.yaxis.set_major_formatter(mtick.PercentFormatter())
ax.xaxis.set_major_formatter(mtick.PercentFormatter())

plt.xlim(0, max(xs))
plt.ylim(0, max(ys))

plt.title('Coverage of cgi_decode() vs. grammar coverage')
plt.xlabel('grammar coverage (expansions)')
plt.ylabel('code coverage (lines)')
plt.scatter(xs, ys);

我们可以看到随之语法覆盖率的提高,代码覆盖率也在提高

G-1.png

Last modification:February 20th, 2019 at 10:58 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment