Arya

Grammar Coverage(一)
[+] 昨天摸鱼摸了一天,感觉自己的良心备受谴责[+] 樱花师傅就是我的欧尔麦特(哈哈哈哈[+] 我也是一个偶尔有...
扫描右侧二维码阅读全文
27
2019/01

Grammar Coverage(一)

[+] 昨天摸鱼摸了一天,感觉自己的良心备受谴责
[+] 樱花师傅就是我的欧尔麦特(哈哈哈哈
[+] 我也是一个偶尔有着伟大梦想的人啊~

0x01 语法覆盖率

上一章最后说到了输入测试值有限的问题,那么这一章就来展开讨论语法覆盖率的问题,探究如何在测试中能够系统地涵盖语法中的所有元素,且不反复重复相同的扩展。

首先测试生成的目的是为了涵盖程序的所有功能,这里的所有当然也包括执行失败的功能。当然,触发程序的所有功能就需要有能够出发这些功能的不同输入。

举个例子,如果想测试语法表达式的功能,那么就要考虑到所有扩展的可能性,那么我们的输入的测试值在运行时必须涵盖所有可能的扩展。

本章中的一些常量选取依然是上一章已经定义的

from Grammars import EXPR_GRAMMAR, CGI_GRAMMAR, URL_GRAMMAR, START_SYMBOL
from Grammars import is_valid_grammar, extend_grammar
print(EXPR_GRAMMAR["<factor>"])

打印出输出结果为
['+<factor>', '-<factor>', '(<expr>)', '<integer>.<integer>', '<integer>']

我们可以从结果中看出,如果扩展<factor>那么一共有5种方式,假设我们在对<factor>的地一次扩展中先选择了<integer>作为扩展方式,那么在下一次扩展式,我们将<integer>标记为coverd,并且从剩下的4种方式中选择一种,比如选择+<factor>或者是<integer>.<integer>,直到覆盖到全部5种扩展方式为止

我们可以引入一个类GrammarCoverageFuzzer跟踪当前的实现的语法覆盖

class TrackingGrammarCoverageFuzzer(GrammarFuzzer):
    def __init__(self, *args, **kwargs):
        # invoke superclass __init__(), passing all arguments
        super().__init__(*args, **kwargs)
        self.reset_coverage()

    def reset_coverage(self):
        self.covered_expansions = set()

    def expansion_coverage(self):
        return self.covered_expansions

covered_expansions集合中,我们将单个扩展作为一堆(symbol,expansion)存储,使用函数expansion_key()生成一个字符串来表示

def expansion_key(symbol, expansion):
    """Convert (symbol, children) into a key.  `children` can be an expansion string or a derivation tree."""
    if isinstance(expansion, tuple):
        expansion = expansion[0]#如果expansion是元组,则选择元组的第一个
    if not isinstance(expansion, str):
        children = expansion
        expansion = all_terminals((symbol, children))#利用all_terminals返回书中所有叶子节点的字符串表现形式
    return symbol + " -> " + expansion
print(expansion_key(START_SYMBOL, EXPR_GRAMMAR[START_SYMBOL][0]))#这里的START_SYMBOL在前一章定义为<start>

打印输出
'<start> -> <expr>'
我们也可以将一个列表作为参数传递进入函数中,然后将这些子元素自动转为字符串

children = [("<expr>", None), (" + ", []), ("<term>", None)]
print(expansion_key("<expr>", children))

输出

'<expr> -> <expr> + <term>'

我们可以通过枚举所有扩展来计算语法中可能
的扩展集。max_expansion_coverage()函数从给定符号(默认为语法开始符号,例如在START_SYMBOL中开始语法为<start>)开始递归遍历语法,并在累计集合expansions中所有扩展,我们可以利用参数max_depth(默认值为∞)来控制语法探索深度

class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    def _max_expansion_coverage(self, symbol, max_depth):
        if max_depth <= 0:
            return set()

        self._symbols_seen.add(symbol)#每次将递归得到的nonterminal作为新的symbol加入_symbols_seen.add,用于表示这个symbol已经被访问了

        expansions = set()
        for expansion in self.grammar[symbol]:
            expansions.add(expansion_key(symbol, expansion))#将新的键值对加入expansions中
            for nonterminal in nonterminals(expansion):#对expansion中的非终端符号进行匹配之后,对所获得的expansion中所有非终端符号遍历
                if nonterminal not in self._symbols_seen:#如果存在未遍历过的非终端符号
                    expansions |= self._max_expansion_coverage(
                        nonterminal, max_depth - 1)#将这个新的非终端符号作为参数进入递归,并将返回值赋值给expansions

        return expansions

    def max_expansion_coverage(self, symbol=None, max_depth=float('inf')):
        """Return set of all expansions in a grammar starting with `symbol`"""
        if symbol is None:
            symbol = self.start_symbol

        self._symbols_seen = set()
        cov = self._max_expansion_coverage(symbol, max_depth)

        if symbol == START_SYMBOL:
            assert len(self._symbols_seen) == len(self.grammar)

        return cov

讲道理,多年以后的我再看到我的这段话,说不定会嘲笑现在的我是个沙雕,但是我还是想说,我真的花了好长时间来读懂这个老哥的这段代码,T_T

输出

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

在扩展过程中,我们可以保持对扩展的跟踪,为此我们可以使用函数choose_node_expansion(),展开单个节点

class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    def add_coverage(self, symbol, new_children):
        key = expansion_key(symbol, new_children)

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

    def choose_node_expansion(self, node, possible_children):
        (symbol, children) = node
        index = super().choose_node_expansion(node, possible_children)
        self.add_coverage(symbol, possible_children[index])
        return index

我们可以通过方法missing_expansion_coverage()可以跟踪所看到的扩展,返回仍然需要扩展的值

class TrackingGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    def missing_expansion_coverage(self):
        return self.max_expansion_coverage() - self.expansion_coverage()

我们查看这个如何跟踪程序运行的

digit_fuzzer = TrackingGrammarCoverageFuzzer(
    EXPR_GRAMMAR, start_symbol="<digit>", log=True)
print(digit_fuzzer.fuzz())

得出结果

Tree: <digit>
Expanding <digit> randomly
Now covered: <digit> -> 9
Tree: 9
'9'
digit_fuzzer.fuzz()
Tree: <digit>
Expanding <digit> randomly
Now covered: <digit> -> 0
Tree: 0
'0'

'0'

查看扩展列表

digit_fuzzer.expansion_coverage()

{'<digit> -> 0', '<digit> -> 5', '<digit> -> 9'}

这是所有扩展组成的集合

digit_fuzzer.max_expansion_coverage()
{'<digit> -> 0',
 '<digit> -> 1',
 '<digit> -> 2',
 '<digit> -> 3',
 '<digit> -> 4',
 '<digit> -> 5',
 '<digit> -> 6',
 '<digit> -> 7',
 '<digit> -> 8',
 '<digit> -> 9'}

这里是刚才我们未访问的语句

digit_fuzzer.missing_expansion_coverage()
{'<digit> -> 1',
 '<digit> -> 2',
 '<digit> -> 3',
 '<digit> -> 4',
 '<digit> -> 6',
 '<digit> -> 7',
 '<digit> -> 8'}

我们可以测试一下如果展开所有非终端符号扩展,平均需要多少字符

def average_length_until_full_coverage(fuzzer):
    trials = 50

    sum = 0
    for trial in range(trials):
        # print(trial, end=" ")
        fuzzer.reset_coverage()
        while len(fuzzer.missing_expansion_coverage()) > 0:
            s = fuzzer.fuzz()
            sum += len(s)

    return sum / trials

我们可以查看最大程度上完全展开<digit>平均生成多少个字符

digit_fuzzer.log = False
average_length_until_full_coverage(digit_fuzzer)

28.4
EXPR_GRAMMAR中的符号最大程度上完全展开,则每次平均生成更多的的字符

expr_fuzzer = TrackingGrammarCoverageFuzzer(EXPR_GRAMMAR)
average_length_until_full_coverage(expr_fuzzer)

138.12

0x02 覆盖语法扩展

接下来我们不仅需要跟踪展开的范围,同时我们也要实际的覆盖每一条扩展的语句,那么具体怎么高效的覆盖呢?思路如下

  1. 我们先确定uncovered_children中尚未访问(或覆盖)的子节点
  2. 如果所有子节点均未被覆盖,那么我们返回原来的方法(即,随机选择一个扩展方式)
  3. 否则,我们从尚未被覆盖的子节点中点则一个子节点并进行标记已覆盖

首先,我们创建一个新的fuzzer——类SimpleGrammarCoverageFuzzer继承于类TrackingGrammarCoverageFuzzer并引入方法choose_node_expansion()实现上面的思路

class SimpleGrammarCoverageFuzzer(TrackingGrammarCoverageFuzzer):
    def choose_node_expansion(self, node, possible_children):
        # Prefer uncovered expansions
        (symbol, children) = node
        uncovered_children = [c for (i, c) in enumerate(possible_children)
                              if expansion_key(symbol, c) not in self.covered_expansions]#返回为被访问的节点,此处digit返回[('0', [])]等,其中[]表示该子节点不可以再进行扩展
        index_map = [i for (i, c) in enumerate(possible_children)
                     if c in uncovered_children]

        if len(uncovered_children) == 0:
            # All expansions covered - use superclass method
            return self.choose_covered_node_expansion(node, possible_children) #当所有节点全部被覆盖时调用函数

        # Select from uncovered nodes
        index = self.choose_uncovered_node_expansion(node, uncovered_children) #当存在未被覆盖的节点时调用函数choose_uncovered_node_expansion

        return index_map[index]

choose_covered_node_expansion()choose_uncovered_node_expansion()为子类提供了两种方法,前者在无未被覆盖的子节点时调用,后者在存在未被访问节点时调用

class SimpleGrammarCoverageFuzzer(SimpleGrammarCoverageFuzzer):
    def choose_uncovered_node_expansion(self, node, possible_children):
        return TrackingGrammarCoverageFuzzer.choose_node_expansion(
            self, node, possible_children)

    def choose_covered_node_expansion(self, node, possible_children):
        return TrackingGrammarCoverageFuzzer.choose_node_expansion(
            self, node, possible_children)

最终返回目前已被覆盖的扩展集合,我们可以多次调用fuzzer,不断增加语法覆盖率,使用EXPR_GRAMMAR生成数字

f = SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR, start_symbol="<digit>")
f.fuzz()

5

f.fuzz()

2

f.fuzz()

1
通过调用expansion_coverage方法查看已覆盖的扩展

f.expansion_coverage()

{'<digit> -> 1', '<digit> -> 2', '<digit> -> 5'}
我们也可以自动的进行fuzzer

for i in range(7):
    print(f.fuzz(), end=" ")

0 9 7 4 8 3 6
通过调用函数missing_expansion_coverage()查看尚未被覆盖的节点

f.missing_expansion_coverage()

此时均被访问,故返回
set()

我们可以将这种fuzz方式用于更加复杂的语法中,经过及迭代,来覆盖每个数字、运算法和展开式

f = SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR)
for i in range(10):
    print(f.fuzz())
+(0.31 / (5) / 9 + 4 * 6 / 3 - 8 - 7) * -2
+++2 / 87360
((4) * 0 - 1) / -9.6 + 7 / 6 + 1 * 8 + 7 * 8
++++26 / -64.45
(8 / 1 / 6 + 9 + 7 + 8) * 1.1 / 0 * 1
7.7
++(3.5 / 3) - (-4 + 3) / (8 / 0) / -4 * 2 / 1
+(90 / --(28 * 8 / 5 + 5 / (5 / 8))) - +9.36 / 2.5 * (5 * (7 * 6 * 5) / 8)
9.11 / 7.28
1 / (9 - 5 * 6) / 6 / 7 / 7 + 1 + 1 - 7 * -3

同样的所有扩展均被访问

f.missing_expansion_coverage()

set()
可以看护我们的策略比单纯的随机访问要更加高效

average_length_until_full_coverage(SimpleGrammarCoverageFuzzer(EXPR_GRAMMAR))

52.28
此时我们覆盖所有表达式扩展,比最开始少生成了50%的字符

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

Leave a Comment