文章目录
0. 前言
基于文法的模糊测试，我安排两天来完成的。但是，沉迷于看《神盾局特工》，安排的时间，被减半。
比较匆忙，代码一行行看明白了，没有手敲。关于python生成文法的“铁路图”代码，没有看。
Railroad Diagrams --fuzzing book | Railroad-Diagram Generator – github
This is a small library for generating railroad diagrams (like what JSON.org uses) using SVG, with both JS and Python ports.
Railroad diagrams are a way of visually representing a grammar in a form that is more readable than using regular expressions or BNF. They can easily represent any context-free grammar, and some more powerful grammars. There are several railroad-diagram generators out there, but none of them had the visual appeal I wanted, so I wrote my own.
因为，我本科学过《编译原理简明教程（第二版）》-- 冯秀芳，所以概念理解上没啥难度。
寒假在家，我翻出当时的课本。课本的首页上，我写着“知其然，不知其所以然”。当年听的也是懵得很。。
本文涉及的编译原理内容，可以参考：EBNF – wiki | 什么是图灵完备？-- 知乎 – 我不知道
建议阅读原文，我这里仅仅整理下思路。我敲的相关代码见：fuzzing仓库
1. 摘要
程序的有效输入集合称为语言。语言的范围从简单到复杂。之前，我们随机输入的字符串（语言），很容易用正则表达式生成。为了形式化的描述语言，这里我们使用文法。通过文法，生成语句(言)，作为模糊测试的输入。
本文使用python，实现一个BNF的算数表达式文法。并使用该文法生成测试用例。
本文不包含（但Fuzzing with Grammars 大部分包含）：文法的铁路图生成、EBNF、将EBNF转换成BNF（通过增加新的非终结符，先去括号，再去运算符）、给每个表达式添加参数、文法的合法性检查（开始符号不能出现在规则的右边、每个非终结符都能推导出终结符、每个非终结符都能出现在某个句型中、没有特殊规则、没有空规则、没有直接左递归？不晓得这点了）
2. 表达式的BNF文法
使用树形结构来看该文法。
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"]
}
这里存在一个问题：文法的构造过程中，我们将’<’、’>‘用以限定非终结符。如果输入中真真包含’<’、’>’,可能会导致误判。
BNF 为自身使用了符号 (<, >, |, ::=)。当它们出现在要定义的语言中的时候，BNF 不得不加以修改或解释的使用）
3. 使用表达式文法
使用上面文法，生成测试的输入。由于是按照文法生成，该输入合法，可以作为突变模糊测试的种子。
import re
import random
RE_NONTERMINAL = re.compile(r'(<[^<> ]*>)')
def nonterminals(expansion):
"""返回表达式中第一个元素中的所有非终结符号"""
if isinstance(expansion,tuple):
expansion = expansion[0]
return re.findall(RE_NONTERMINAL,expansion)
def is_nonterminal(s):
"""判断一个符号是否为非终结符"""
return re.match(RE_NONTERMINAL, s)
def simple_grammar_fuzzer(grammar, start_symbol="<start>",
max_nonterminals=10, max_expansion_trials=100,
log=False):
"""简单的文法生成输入"""
term = start_symbol
expansion_trials = 0
while len(nonterminals(term)) > 0 :
symbol_to_expand = random.choice(nonterminals(term))
expansions = grammar[symbol_to_expand]
expansion = random.choice(expansions)
new_term = term.replace(symbol_to_expand,expansion,1)
if len(nonterminals(new_term)) < max_nonterminals :
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:
raise ExpansionError("Cannot expand " + repr(term))
return term
4. 运行结果
simple_grammar_fuzzer(grammar=EXPR_GRAMMAR, max_nonterminals=3, log=True)
<start> -> <expr> <expr>
<expr> -> <term> - <expr> <term> - <expr>
<term> -> <factor> <factor> - <expr>
<factor> -> <integer> <integer> - <expr>
<expr> -> <term> <integer> - <term>
<integer> -> <digit> <digit> - <term>
<digit> -> 2 2 - <term>
<term> -> <factor> / <term> 2 - <factor> / <term>
<factor> -> <integer> 2 - <integer> / <term>
<integer> -> <digit> 2 - <digit> / <term>
<digit> -> 5 2 - 5 / <term>
<term> -> <factor> 2 - 5 / <factor>
<factor> -> (<expr>) 2 - 5 / (<expr>)
<expr> -> <term> 2 - 5 / (<term>)
<term> -> <factor> / <term> 2 - 5 / (<factor> / <term>)
<factor> -> -<factor> 2 - 5 / (-<factor> / <term>)
<factor> -> (<expr>) 2 - 5 / (-(<expr>) / <term>)
<term> -> <factor> 2 - 5 / (-(<expr>) / <factor>)
<factor> -> -<factor> 2 - 5 / (-(<expr>) / -<factor>)
<factor> -> -<factor> 2 - 5 / (-(<expr>) / --<factor>)
<factor> -> +<factor> 2 - 5 / (-(<expr>) / --+<factor>)
<factor> -> <integer> 2 - 5 / (-(<expr>) / --+<integer>)
<integer> -> <digit> 2 - 5 / (-(<expr>) / --+<digit>)
<digit> -> 0 2 - 5 / (-(<expr>) / --+0)
<expr> -> <term> - <expr> 2 - 5 / (-(<term> - <expr>) / --+0)
<expr> -> <term> 2 - 5 / (-(<term> - <term>) / --+0)
<term> -> <factor> 2 - 5 / (-(<factor> - <term>) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((<expr>) - <term>) / --+0)
<expr> -> <term> 2 - 5 / (-((<term>) - <term>) / --+0)
<term> -> <factor> 2 - 5 / (-((<factor>) - <term>) / --+0)
<factor> -> -<factor> 2 - 5 / (-((-<factor>) - <term>) / --+0)
<factor> -> <integer> 2 - 5 / (-((-<integer>) - <term>) / --+0)
<integer> -> <digit> 2 - 5 / (-((-<digit>) - <term>) / --+0)
<digit> -> 7 2 - 5 / (-((-7) - <term>) / --+0)
<term> -> <factor> * <term> 2 - 5 / (-((-7) - <factor> * <term>) / --+0)
<factor> -> -<factor> 2 - 5 / (-((-7) - -<factor> * <term>) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((-7) - -(<expr>) * <term>) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(<expr>) * <factor>) / --+0)
<expr> -> <term> 2 - 5 / (-((-7) - -(<term>) * <factor>) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(<factor>) * <factor>) / --+0)
<factor> -> -<factor> 2 - 5 / (-((-7) - -(-<factor>) * <factor>) / --+0)
<factor> -> -<factor> 2 - 5 / (-((-7) - -(--<factor>) * <factor>) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((-7) - -(--(<expr>)) * <factor>) / --+0)
<expr> -> <term> 2 - 5 / (-((-7) - -(--(<term>)) * <factor>) / --+0)
<factor> -> +<factor> 2 - 5 / (-((-7) - -(--(<term>)) * +<factor>) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(--(<factor>)) * +<factor>) / --+0)
<factor> -> +<factor> 2 - 5 / (-((-7) - -(--(+<factor>)) * +<factor>) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((-7) - -(--(+(<expr>))) * +<factor>) / --+0)
<expr> -> <term> 2 - 5 / (-((-7) - -(--(+(<term>))) * +<factor>) / --+0)
<factor> -> <integer> 2 - 5 / (-((-7) - -(--(+(<term>))) * +<integer>) / --+0)
<integer> -> <digit> 2 - 5 / (-((-7) - -(--(+(<term>))) * +<digit>) / --+0)
<digit> -> 9 2 - 5 / (-((-7) - -(--(+(<term>))) * +9) / --+0)
<term> -> <factor> * <term> 2 - 5 / (-((-7) - -(--(+(<factor> * <term>))) * +9) / --+0)
<factor> -> +<factor> 2 - 5 / (-((-7) - -(--(+(+<factor> * <term>))) * +9) / --+0)
<factor> -> -<factor> 2 - 5 / (-((-7) - -(--(+(+-<factor> * <term>))) * +9) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(--(+(+-<factor> * <factor>))) * +9) / --+0)
<factor> -> -<factor> 2 - 5 / (-((-7) - -(--(+(+--<factor> * <factor>))) * +9) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((-7) - -(--(+(+--(<expr>) * <factor>))) * +9) / --+0)
<expr> -> <term> 2 - 5 / (-((-7) - -(--(+(+--(<term>) * <factor>))) * +9) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(--(+(+--(<factor>) * <factor>))) * +9) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((-7) - -(--(+(+--((<expr>)) * <factor>))) * +9) / --+0)
<factor> -> +<factor> 2 - 5 / (-((-7) - -(--(+(+--((<expr>)) * +<factor>))) * +9) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((-7) - -(--(+(+--((<expr>)) * +(<expr>)))) * +9) / --+0)
<expr> -> <term> 2 - 5 / (-((-7) - -(--(+(+--((<term>)) * +(<expr>)))) * +9) / --+0)
<expr> -> <term> 2 - 5 / (-((-7) - -(--(+(+--((<term>)) * +(<term>)))) * +9) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(--(+(+--((<factor>)) * +(<term>)))) * +9) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(--(+(+--((<factor>)) * +(<factor>)))) * +9) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((-7) - -(--(+(+--(((<expr>))) * +(<factor>)))) * +9) / --+0)
<factor> -> <integer> 2 - 5 / (-((-7) - -(--(+(+--(((<expr>))) * +(<integer>)))) * +9) / --+0)
<expr> -> <term> 2 - 5 / (-((-7) - -(--(+(+--(((<term>))) * +(<integer>)))) * +9) / --+0)
<integer> -> <digit> 2 - 5 / (-((-7) - -(--(+(+--(((<term>))) * +(<digit>)))) * +9) / --+0)
<digit> -> 3 2 - 5 / (-((-7) - -(--(+(+--(((<term>))) * +(3)))) * +9) / --+0)
<term> -> <factor> * <term> 2 - 5 / (-((-7) - -(--(+(+--(((<factor> * <term>))) * +(3)))) * +9) / --+0)
<factor> -> (<expr>) 2 - 5 / (-((-7) - -(--(+(+--((((<expr>) * <term>))) * +(3)))) * +9) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(--(+(+--((((<expr>) * <factor>))) * +(3)))) * +9) / --+0)
<factor> -> <integer> 2 - 5 / (-((-7) - -(--(+(+--((((<expr>) * <integer>))) * +(3)))) * +9) / --+0)
<integer> -> <digit> 2 - 5 / (-((-7) - -(--(+(+--((((<expr>) * <digit>))) * +(3)))) * +9) / --+0)
<digit> -> 1 2 - 5 / (-((-7) - -(--(+(+--((((<expr>) * 1))) * +(3)))) * +9) / --+0)
<expr> -> <term> 2 - 5 / (-((-7) - -(--(+(+--((((<term>) * 1))) * +(3)))) * +9) / --+0)
<term> -> <factor> * <term> 2 - 5 / (-((-7) - -(--(+(+--((((<factor> * <term>) * 1))) * +(3)))) * +9) / --+0)
<term> -> <factor> 2 - 5 / (-((-7) - -(--(+(+--((((<factor> * <factor>) * 1))) * +(3)))) * +9) / --+0)
<factor> -> <integer> 2 - 5 / (-((-7) - -(--(+(+--((((<integer> * <factor>) * 1))) * +(3)))) * +9) / --+0)
<factor> -> +<factor> 2 - 5 / (-((-7) - -(--(+(+--((((<integer> * +<factor>) * 1))) * +(3)))) * +9) / --+0)
<factor> -> +<factor> 2 - 5 / (-((-7) - -(--(+(+--((((<integer> * ++<factor>) * 1))) * +(3)))) * +9) / --+0)
<integer> -> <digit> 2 - 5 / (-((-7) - -(--(+(+--((((<digit> * ++<factor>) * 1))) * +(3)))) * +9) / --+0)
<digit> -> 5 2 - 5 / (-((-7) - -(--(+(+--((((5 * ++<factor>) * 1))) * +(3)))) * +9) / --+0)
<factor> -> <integer>.<integer> 2 - 5 / (-((-7) - -(--(+(+--((((5 * ++<integer>.<integer>) * 1))) * +(3)))) * +9) / --+0)
<integer> -> <digit> 2 - 5 / (-((-7) - -(--(+(+--((((5 * ++<digit>.<integer>) * 1))) * +(3)))) * +9) / --+0)
<digit> -> 9 2 - 5 / (-((-7) - -(--(+(+--((((5 * ++9.<integer>) * 1))) * +(3)))) * +9) / --+0)
<integer> -> <digit> 2 - 5 / (-((-7) - -(--(+(+--((((5 * ++9.<digit>) * 1))) * +(3)))) * +9) / --+0)
<digit> -> 4 2 - 5 / (-((-7) - -(--(+(+--((((5 * ++9.4) * 1))) * +(3)))) * +9) / --+0)
'2 - 5 / (-((-7) - -(--(+(+--((((5 * ++9.4) * 1))) * +(3)))) * +9) / --+0)'