作者：時鐘@RainSec
本文為作者投稿，Seebug Paper 期待你的分享，凡經采用即有禮品相送！ 投稿郵箱：paper@seebug.org
Fuzzing input
Fuzzing的一大核心思想其實就是通過大量的Input去觸發程序的各個分支邏輯，因此Fuzzing的成功與否和Input的生成關系密切。Input的格式多種多樣，可以是文件，代碼，json數據等等。但是各種各樣的數據都有自己的格式，程序的輸入也是如此，那么在生成Input的過程中，格式化非常關鍵，程序無法接受的輸入對于Fuzzing來說是毫無意義的。
為了很好的描述一個程序的輸入，一個很有必要的事情是為輸入制定一些語法規范。比如編譯器的輸入：python解釋器規定了符合python語法的程序才能得以執行，gcc規定了符合C語言語法的程序才能被完成編譯進而生成二進制文件。Fuzzing也是如此，為了很好的達到Fuzzing的效果，為程序定義一種輸入的語法規范往往是一種不錯的選擇。
一般而言，對于Fuzzing簡單的程序來說，正則表達式往往是一個不錯的選擇，它所具備的有限狀態機屬性使得它易于推理進而獲得一個滿意的Input。但是如果面臨的Fuzzing目標需要非常復雜的輸入，那么它就會表現的捉襟見肘。
我曾見過為了更好的實現某些功能而專門設計一些語言，從計算機理論的角度這顯然是非常有用的，一些特殊功能在特殊語言的加持之下表現出超高的質量，但是對于Fuzzing而言這確實是成本過高了，Grammars其實就是正則表達式和專業語言之間的一個中間地帶。它易于理解，并且能很好的完成Fuzzing對它的期望--生成大量合法輸入，因為通過Grammars可以規定Inputs的大量屬性，完美的表達一個復雜輸入的語法結構。
Grammars初探
Grammar一般由符號和一組表達式組成，例如A = 10 | 9 | 0 |1，符號化使得遞歸成為可能，假設B = A | AB，這無疑就使得符號所代表的范圍倍增。根據這種思想我們可以制作一個算數表達式：
<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那么通過對<start>的內部的符號進行逐一擴展，并對過程進行隨機化處理，最終就可以得到大量的合法算數表達式。和大多數語法一樣，Grammar也應該有自己的Type，以便對其合法性進行校驗，以Python 為例子可以對上述的Grammar進行定義：
Option = Dict[str, Any]
Expansion = Union[str, Tuple[str, Option]]
Grammar = Dict[str, List[Expansion]]
EXPR_GRAMMAR: 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"]
}前三行代碼定義了一個Grammar應該如何在Python中構成。通過代碼中的EXPR_GRAMMAR["<digit>"]可以訪問當前Grammar的各個組成部分并對其進行操作。
Sample Grammar Fuzz
那么該如何對Grammar語法進行解析呢？一種最簡單的方式就是通過字符串替換，因為在Grammar中:的左右兩側本身就是一種映射關系，因此利用字符串替換不斷迭代是一種最為直觀的選擇。
實例代碼：
START_SYMBOL = "<start>"
# 一個簡單的gramar fuzzer
def simple_grammar_fuzzer(grammar: Grammar,
start_symbol: str = START_SYMBOL,
max_nonterminals: int = 10,
max_expansion_trials: int = 100,
log: bool = False) -> str:
"""Produce a string from `grammar`.
`start_symbol`: use a start symbol other than `<start>` (default).
`max_nonterminals`: the maximum number of nonterminals
still left for expansion
`max_expansion_trials`: maximum # of attempts to produce a string
`log`: print expansion progress if True"""
term = start_symbol
expansion_trials = 0
while len(nonterminals(term)) > 0: # 判斷字符串中是否存在<>，并返回所有被<>包裹的項，注意如果是<dsad<abc>>則返回<abc>
symbol_to_expand = random.choice(nonterminals(term))
expansions = grammar[symbol_to_expand]
expansion = random.choice(expansions)
# In later chapters, we allow expansions to be tuples,
# with the expansion being the first element
if isinstance(expansion, tuple):
expansion = expansion[0]
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利用上面的表達式Grammar可以制作一個簡單的grammar fuzz，Fuzz的編寫過程其實面臨著很多的取舍，便利和速度或者各種各樣的可行性之間的考慮，以上面的Grammar為例子，我們肯定不希望其陷入類似無限遞歸或者大量符號解析的情況，而是會限制對字段的提取次數和對符號的解析次數。
但是此類Grammar Fuzz都面臨幾個問題就是大量的字符串搜索和替換操作導致效率低下，而且可以看出存在Input生成失敗的情況（ExpansionError），而且這是一個典型的上下文無關的Fuzz。不過，依賴于上述功能，我們只要編寫Grammar就可以很好的對一些Inputs進行大量生成。
比如URL生成：
URL_GRAMMAR: Grammar = {
"<start>":
["<url>"],
"<url>":
["<scheme>://<authority><path><query>"],
"<scheme>":
["http", "https", "ftp", "ftps"],
"<authority>":
["<host>", "<host>:<port>", "<userinfo>@<host>", "<userinfo>@<host>:<port>"],
"<host>": # 大部分情況下其實可以指定一個URL
["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>"],
}或者類似HTTP協議的（但是這個不是為上述Fuzz準備的，只是拿來做個參考）：
{
"<A>": [["<START_LINE>", "\r\n", "<HEADERS>", "<BODY>", "\r\n\r\n"]],
"<START_LINE>": [["<METHOD>", " ", "<URI>", " ", "<VERSION>"]],
"<METHOD>": [["GET"], ["HEAD"], ["POST"], ["PUT"], ["DELETE"], ["CONNECT"], ["OPTIONS"], ["TRACE"], ["PATCH"], ["ACL"], ["BASELINE-CONTROL"], ["BIND"], ["CHECKIN"], ["CHECKOUT"], ["COPY"], ["LABEL"], ["LINK"], ["LOCK"], ["MERGE"], ["MKACTIVITY"], ["MKCALENDAR"], ["MKCOL"], ["MKREDIRECTREF"], ["MKWORKSPACE"], ["MOVE"], ["ORDERPATCH"], ["PRI"], ["PROPFIND"], ["PROPPATCH"], ["REBIND"], ["REPORT"], ["SEARCH"], ["UNBIND"], ["UNCHECKOUT"], ["UNLINK"], ["UNLOCK"], ["UPDATE"], ["UPDATEREDIRECTREF"], ["VERSION-CONTROL"]],
"<URI>": [["<SCHEME>" , ":", "<HIER>", "<QUERY>", "<FRAGMENT>"]],
"<SCHEME>": [["http"], ["https"], ["shttp"], ["dav"], ["about"], ["attachment"], ["cid"], ["data"], ["file"], ["ftp"], ["ssh"], ["sip"]],
"<HIER>": [["//", "<AUTHORITY>", "<PATH>"]],
"<AUTHORITY>": [["<USERINFO>", "<HOST>"]],
"<PATH>": [["/", "<DIR>"]],
"<DIR>": [[], ["<CHAR>", "/", "<DIR>"]],
"<USERINFO>": [[], ["<CHAR>", ":", "<CHAR>", "@"]],
"<HOST>": [["127.0.0.1:8080"]],
"<QUERY>": [[], ["?", "<CHAR>" , "=", "<CHAR>"]],
"<FRAGMENT>": [[], ["#", "<CHAR>"]],
"<VERSION>": [["HTTP/0.9"], ["HTTP/1.0"], ["HTTP/1.1"], ["HTTP/2.0"], ["HTTP/3.0"]],
"<HEADERS>": [[], ["<HEADER>", "\r\n", "<HEADERS>"]],
"<HEADER>": [["<HEADER_FIELD>", ": ", "<ANY>"]],
"<HEADER_FIELD>": [["A-IM"], ["Accept"], ["Accept-Charset"], ["Accept-Datetime"], ["Accept-Encoding"], ["Accept-Language"], ["Access-Control-Request-Method"], ["Access-Control-Request-Headers"], ["Authorization"], ["Cache-Control"], ["Connection"], ["Content-Encoding"], ["Content-Length"], ["Content-MD5"], ["Content-Type"], ["Cookie"], ["Date"], ["Expect"], ["Forwarded"], ["From"], ["Host"], ["HTTP2-Settings"], ["If-Match"], ["If-Modified-Since"], ["If-None-Match"], ["If-Range"], ["If-Unmodified-Since"], ["Max-Forwards"], ["Origin"], ["Pragma"], ["Proxy-Authorization"], ["Range"], ["Referer"], ["TE"], ["Trailer"], ["Transfer-Encoding"], ["User-Agent"], ["Upgrade"], ["Via"], ["Warning"]],
"<BODY>": [[], ["<CHAR>"]],
"<ANY>": [[], ["<DATE>"], ["<CHAR>"], ["<HOST>"], ["<URI>"]],
"<DATE>": [["Sat, 29 Oct 1994 19:43:31 GMT"]],
"<CHAR>": [["0"], ["1"], ["2"], ["3"], ["4"], ["5"], ["6"], ["7"], ["8"], ["9"], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"], ["m"], ["n"], ["o"], ["p"], ["q"], ["r"], ["s"], ["t"], ["u"], ["v"], ["w"], ["x"], ["y"], ["z"], ["A"], ["B"], ["C"], ["D"], ["E"], ["F"], ["G"], ["H"], ["I"], ["J"], ["K"], ["L"], ["M"], ["N"], ["O"], ["P"], ["Q"], ["R"], ["S"], ["T"], ["U"], ["V"], ["W"], ["X"], ["Y"], ["Z"]]
}到此，我們理解了Grammar對于Fuzzing的重要性，一個杰出的Grammar能夠有效的生成大量合法輸入，不過這只是從輸入組成（句法）來看，這畢竟是一個龐大的范圍，雖然有時候滿足程序的輸入格式，但是未必真的對Fuzzing起作用，這種情況非常常見。再一次以編譯器為例子，你的程序在滿足語言語法的同時更應該具備正確的語義。但是語義很難再以Grammar的形式表達。以URL生成Grammar為例，簡單通過Grammar很難定義端口的范圍。面對這樣的問題，最簡單的解決辦法其實就是在Fuzz里面而不是在Grammar里面進行限制。以URL Grammar為例，通過Grammar生成的URL在真正的被作為Input給予目標之前，應該在Fuzz系統里面經過URL“合法性”判斷，這里的判斷可以由作者根據自己的需求來進行限制。
Grammar Toolbox
在Fuzzing項目中對于Grammar的需求并不是一成不變的，因此Grammar的一大需求就是具備可擴展性。以一個簡單的Gramar為例：
simple_nonterminal_grammar: Grammar = {
"<start>": ["<nonterminal>"],
"<nonterminal>": ["<left-angle><identifier><right-angle>"],
"<left-angle>": ["<"],
"<right-angle>": [">"],
"<identifier>": ["id"] # for now
}有時候我們希望拓展其功能，但是不希望原來的Grammar受到影響（類比編程中的繼承）,就是一個很簡單的如下操作。
nonterminal_grammar = copy.deepcopy(simple_nonterminal_grammar)
nonterminal_grammar["<identifier>"] = ["<idchar>", "<identifier><idchar>"]
nonterminal_grammar["<idchar>"] = ['a', 'b', 'c', 'd'] # for now總結為一個函數如下，非常簡單就不多解釋：
def set_opts(grammar: Grammar, symbol: str, expansion: Expansion,
opts: Option = {}) -> None:
"""Set the options of the given expansion of grammar[symbol] to opts"""
expansions = grammar[symbol]
for i, exp in enumerate(expansions):
if exp_string(exp) != exp_string(expansion):
continue
new_opts = exp_opts(exp)
if opts == {} or new_opts == {}:
new_opts = opts
else:
for key in opts:
new_opts[key] = opts[key]
if new_opts == {}:
grammar[symbol][i] = exp_string(exp)
else:
grammar[symbol][i] = (exp_string(exp), new_opts)
return
raise KeyError(
"no expansion " +
repr(symbol) +
" -> " +
repr(
exp_string(expansion)))同時，在寫Fuzz的時候肯定不希望不斷地寫大量的符號和值的對應，因此我們需要一些語法來幫助，這里提供了ENBF的解析方法：
# 解析 ebnf 語法
def new_symbol(grammar: Grammar, symbol_name: str = "<symbol>") -> str:
"""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
# 提取表達式中符合EBNF語法的部分，? , * , + , ()
def parenthesized_expressions(expansion: Expansion) -> List[str]:
RE_PARENTHESIZED_EXPR = re.compile(r'\([^()]*\)[?+*]')
# 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)
# 對Grammar中的EBNF語法括號進行解析
def convert_ebnf_parentheses(ebnf_grammar: Grammar) -> 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]
if not isinstance(expansion, str):
expansion = expansion[0]
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)
exp = grammar[nonterminal][i]
opts = None
if isinstance(exp, tuple):
(exp, opts) = exp
assert isinstance(exp, str)
expansion = exp.replace(expr, new_sym + operator, 1)
if opts:
grammar[nonterminal][i] = (expansion, opts)
else:
grammar[nonterminal][i] = expansion
grammar[new_sym] = [contents]
return grammar
# ENBF符號擴展
def extended_nonterminals(expansion: Expansion) -> List[str]:
RE_EXTENDED_NONTERMINAL = re.compile(r'(<[^<> ]*>[?+*])')
# 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)
# ENBF符號擴展
def convert_ebnf_operators(ebnf_grammar: Grammar) -> 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]
assert original_symbol in ebnf_grammar, \
f"{original_symbol} is not defined in grammar"
new_sym = new_symbol(grammar, original_symbol)
exp = grammar[nonterminal][i]
opts = None
if isinstance(exp, tuple):
(exp, opts) = exp
assert isinstance(exp, str)
new_exp = exp.replace(extended_symbol, new_sym, 1)
if opts:
grammar[nonterminal][i] = (new_exp, opts)
else:
grammar[nonterminal][i] = new_exp
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
def convert_ebnf_grammar(ebnf_grammar: Grammar) -> Grammar:
return convert_ebnf_operators(convert_ebnf_parentheses(ebnf_grammar))對于Grammar來言，我們必須要確定它的一個合法性，不然在使用中必然會遇到各種錯誤問題，因此語法檢查是很必要的，就如同編譯器的語法檢查很重要一樣：
# 搜索Grammar中的定義的noterminal
def def_used_nonterminals(grammar: Grammar, start_symbol:
str = START_SYMBOL) -> Tuple[Optional[Set[str]],
Optional[Set[str]]]:
"""Return a pair (`defined_nonterminals`, `used_nonterminals`) in `grammar`.
In case of error, return (`None`, `None`)."""
defined_nonterminals = set()
used_nonterminals = {start_symbol}
for defined_nonterminal in grammar:
defined_nonterminals.add(defined_nonterminal)
expansions = grammar[defined_nonterminal]
if not isinstance(expansions, list):
print(repr(defined_nonterminal) + ": expansion is not a list",
file=sys.stderr)
return None, None
if len(expansions) == 0:
print(repr(defined_nonterminal) + ": expansion list empty",
file=sys.stderr)
return None, None
for expansion in expansions:
if isinstance(expansion, tuple):
expansion = expansion[0]
if not isinstance(expansion, str):
print(repr(defined_nonterminal) + ": "
+ repr(expansion) + ": not a string",
file=sys.stderr)
return None, None
for used_nonterminal in nonterminals(expansion):
used_nonterminals.add(used_nonterminal)
return defined_nonterminals, used_nonterminals
def reachable_nonterminals(grammar: Grammar,
start_symbol: str = START_SYMBOL) -> Set[str]:
reachable = set()
def _find_reachable_nonterminals(grammar, symbol):
nonlocal reachable
reachable.add(symbol)
for expansion in grammar.get(symbol, []):
for nonterminal in nonterminals(expansion):
if nonterminal not in reachable:
_find_reachable_nonterminals(grammar, nonterminal)
_find_reachable_nonterminals(grammar, start_symbol)
return reachable
def unreachable_nonterminals(grammar: Grammar,
start_symbol=START_SYMBOL) -> Set[str]:
return grammar.keys() - reachable_nonterminals(grammar, start_symbol)
def opts_used(grammar: Grammar) -> Set[str]:
used_opts = set()
for symbol in grammar:
for expansion in grammar[symbol]:
used_opts |= set(exp_opts(expansion).keys())
return used_opts
# Grammar的合法性判斷，類似于編譯器里面的語法檢查
def is_valid_grammar(grammar: Grammar,
start_symbol: str = START_SYMBOL,
supported_opts: Set[str] = set()) -> bool:
"""Check if the given `grammar` is valid.
`start_symbol`: optional start symbol (default: `<start>`)
`supported_opts`: options supported (default: none)"""
defined_nonterminals, used_nonterminals = \
def_used_nonterminals(grammar, start_symbol)
if defined_nonterminals is None or used_nonterminals is None:
return False
# Do not complain about '<start>' being not used,
# even if start_symbol is different
if START_SYMBOL in grammar:
used_nonterminals.add(START_SYMBOL)
for unused_nonterminal in defined_nonterminals - used_nonterminals:
print(repr(unused_nonterminal) + ": defined, but not used",
file=sys.stderr)
for undefined_nonterminal in used_nonterminals - defined_nonterminals:
print(repr(undefined_nonterminal) + ": used, but not defined",
file=sys.stderr)
# Symbols must be reachable either from <start> or given start symbol
unreachable = unreachable_nonterminals(grammar, start_symbol)
msg_start_symbol = start_symbol
if START_SYMBOL in grammar:
unreachable = unreachable - \
reachable_nonterminals(grammar, START_SYMBOL)
if start_symbol != START_SYMBOL:
msg_start_symbol += " or " + START_SYMBOL
for unreachable_nonterminal in unreachable:
print(repr(unreachable_nonterminal) + ": unreachable from " + msg_start_symbol,
file=sys.stderr)
used_but_not_supported_opts = set()
if len(supported_opts) > 0:
used_but_not_supported_opts = opts_used(
grammar).difference(supported_opts)
for opt in used_but_not_supported_opts:
print(
"warning: option " +
repr(opt) +
" is not supported",
file=sys.stderr)
return used_nonterminals == defined_nonterminals and len(unreachable) == 0以上列舉的是常用的Tools，在Fuzz的編寫過程中，要根據實際問題針對性的編寫各式各樣的工具。
高效Grammars Fuzz
前面提供的simple_grammar_fuzzer其實存在大量的問題，比如性能低下，對于符號的解析次數受限，容易引起報錯等，因此需要更加高明的算法。這里選擇的是派生樹，因為樹形結構易于追蹤而且易于添加和刪除其中分支。關于Fuzz的編寫其實就是不斷的對派生樹進行分析和對子節點的不斷擴展。
派生樹算法
從上述的簡單算法可以看出，整個的Grammar Fuzz的核心其實就是通過大量的符號擴展形成對應的數據結構，那么用來存儲或者拓展符號的數據結構其實尤為重要。派生樹的樹狀結構其實完美的符合了我們的要求，樹形結構自上而下的擴展正好和符號的擴展相對應。而且派生樹使得我們可以掌控整個擴展過程的狀態，比如那些節點已經被擴展，或者某個節點是否需要擴展等，同時，在擴展過程中增加新節點的速度遠超把一個符號替換為一個值的過程，因此使用這種數據結構也帶來了一定的性能增益。
讓我們以下面的Grammar為例子：
# URL Grammar
URL_GRAMMAR: Grammar = {
"<start>":
["<url>"],
"<url>":
["<scheme>://<authority><path><query>"],
"<scheme>":
["http", "https", "ftp", "ftps"],
"<authority>":
["<host>", "<host>:<port>", "<userinfo>@<host>", "<userinfo>@<host>:<port>"],
"<host>": # 大部分情況下其實可以指定一個URL
["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>"],
}以派生樹算法來看，首先以<start>為初始節點，然后在Grammar中發現其存在對應的表達，所以就會選擇<url>作為它的子節點，循環往復知道一個節點不再出現對應的子節點，然后整個的樹形結構完成解析，輸出對應的結構化數據。
對應的數據表示如下：
(SYMBOL_NAME, CHILDREN)
DerivationTree = Tuple[str, Optional[List[Any]]]
derivation_tree: DerivationTree = ("<start>",
[("<expr>",
[("<expr>", None),
(" + ", []),
("<term>", None)]
)])SYMBOL_NAME代表的就是符號，CHILDREN代表子節點，表示為具體的數據結構就是：DerivationTree = Tuple[str, Optional[List[Any]]]。其中CHILDREN主要有兩種表示：
- None代表當前節點可以繼續向下擴展，其含義就是現在節點存在可擴展的符號。
- []代表的就是沒有子節點了
整個算法都圍繞上面的基本原理展開
def g_rammar_fuzzer():
f = GrammarFuzzer(URL_GRAMMAR)
f.fuzz()ProbabilisticGrammarFuzzer
有時候完全隨機的進行表達式展開其實會白白浪費大量的時間和資源，因此可以對表達式附加概率值，這一塊涉及到大量的概率學問題，有部分數據來源于世界的統計規律，比如下面給出的leaddigit符號對應的概率，這些就不在深入分析。
PROBABILISTIC_EXPR_GRAMMAR: Grammar = {
"<start>":
["<expr>"],
"<expr>":
[("<term> + <expr>", opts(prob=0.1)),
("<term> - <expr>", opts(prob=0.2)),
"<term>"],
"<term>":
[("<factor> * <term>", opts(prob=0.1)),
("<factor> / <term>", opts(prob=0.1)),
"<factor>"
],
"<factor>":
["+<factor>", "-<factor>", "(<expr>)",
"<leadinteger>", "<leadinteger>.<integer>"],
"<leadinteger>":
["<leaddigit><integer>", "<leaddigit>"],
# Benford's law: frequency distribution of leading digits
"<leaddigit>":
[("1", opts(prob=0.301)),
("2", opts(prob=0.176)),
("3", opts(prob=0.125)),
("4", opts(prob=0.097)),
("5", opts(prob=0.079)),
("6", opts(prob=0.067)),
("7", opts(prob=0.058)),
("8", opts(prob=0.051)),
("9", opts(prob=0.046)),
],
# Remaining digits are equally distributed
"<integer>":
["<digit><integer>", "<digit>"],
"<digit>":
["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"],
}跟之前的Grammar有很大不同的地方在于，現在的Grammar可以通過增加注釋的方式為列表中的值添加隨機概率，使得作者可以通過逆向獲取其它渠道得到的信息可以在Fuzz中獲得利用。那現在問題就顯而易見了，如何確定概率？
當Fuzz的作者沒辦法直接給出一個符號對應的所有項具體的概率的時候，可以遵循的最直接的規則就是下面三個公式：
大致含義也很好理解，就是a代表的是已知概率的項，而u代表的未知概率的項目，已知概率自然可以通過opts的方法給對應項附加概率，未知概率的項則按照概率平分的原則來賦予概率。之后自然是要在Fuzz里面引入概率，使得在生成種子的時候可以對符號解析的選擇賦予權重，進而提高Fuzz效率。
就Fuzz的具體實現而言，其實相比于上述的Grammar Fuzz只是增加了一個對于opts注釋的訪問，以便在隨機解析的時候可以附加概率值權重。但是這樣帶來的優勢是很明顯的，甚至可以通過控制輸入Fuzz目標指定的Func等。但是還有一種情況，我第一次解析Grammar symbol的時候希望它的概率為0.3，但是我第二次解析Grammar symbol的時候希望其概率為0.5，為了實現這一點其實可以利用上下文，在不同的上下文中復制希望賦予其不同概率的symbol，以IP Grammar為例子：
IP_ADDRESS_GRAMMAR: Grammar = {
"<start>": ["<address>"],
"<address>": ["<octet>.<octet>.<octet>.<octet>"],
# ["0", "1", "2", ..., "255"]
"<octet>": decrange(0, 256) # 其實代表的就是0-256
}為了使得每次解析<octet>的時候都使用不同的概率，可以對其擴展，形成下面的語法：
IP_ADDRESS_GRAMMAR: Grammar = {
"<start>": ["<address>"],
"<address>": ["<octet-1>.<octet-2>.<octet-3>.<octet-4>"],
# ["0", "1", "2", ..., "255"]
"<octet-1>": decrange(0, 256) # 其實代表的就是0-256
"<octet-2>": decrange(0, 256) # 其實代表的就是0-256
"<octet-3>": decrange(0, 256) # 其實代表的就是0-256
"<octet-4>": decrange(0, 256) # 其實代表的就是0-256
}這樣在進行解析的時候就完全可以對每次解析附加不同的概率。下面是幫助實現的函數：
def _duplicate_context(grammar: Grammar,
orig_grammar: Grammar,
symbol: str,
expansion: Optional[Expansion],
depth: Union[float, int],
seen: Dict[str, str]) -> None:
"""Helper function for `duplicate_context()`"""
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: # Duplicated already
new_expansion += seen[s]
elif c == [] or depth == 0: # Terminal symbol or end of recursion
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
def duplicate_context(grammar: Grammar,
symbol: str,
expansion: Optional[Expansion] = None,
depth: Union[float, int] = 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]在完成上下文復制之后就可以通過類似下面的操作得到我們想要的結果：
set_prob(probabilistic_ip_address_grammar, "<octet-1>", "127", 1.0)
set_prob(probabilistic_ip_address_grammar, "<octet-2>", "0", 1.0)不過這就又引入一個問題，概率在賦予給symbol之后一成不變真的合適嗎？在真實世界的Fuzz中隨著我們對于目標的不斷了解，或者一些其它情況比如長時間未出現想要的結果等，及時改變策略也是非常必要的，但是如果Fuzz可以智能的自己調節調整不同symbol的概率值的話，會減輕很多的負擔并獲得更好的軟件測試效果。一個比較好的辦法是讓Fuzz通過最開始被給予Inputs種子來學習應該賦予某些symbol多大的一個概率值，這種方法在某些場景下非常有用：
- 測試常用功能，因為很多軟件測試更希望常用的功能確保安全，但是對于漏洞挖掘研究人員來說可能目標不在于此。
- 測試不常用功能，通過規避Inputs中解析到的symbol，Fuzz就會更偏向于測試一些不常用的功能。
- 專注于指定的Inputs，一些漏洞挖掘可能希望專注于已有的非常有價值的poc inputs，通過專注于這些inputs，Fuzz可以測試軟件的一些薄弱環節從而達到很好的效果。
理論已經存在，那么如何實現呢？第一步肯定是需要將已經存在的Inputs種子恢復成為派生樹，然后對派生樹種每個Symbol對應的值有多少來計算將來的概率值。
如上圖，假設我給與一個127.0.0.1的種子，那么被解析之后，0在<octet>中的概率值就會被限制為50%，127和1分別為25%，那么在Fuzz運行的時候相關的概率值就可以賦予給<octet>。那么如果測試一些不常用功能該怎么辦呢？其實就是通過原來測常用功能的Inputs得到相關概率，然后進行概率翻轉就行了，比如常用功能的Inputs概率如下：
[('http', {'prob': 0.2222222222222222}),
('https', {'prob': 0.6666666666666666}),
('ftp', {'prob': 0.0}),
('ftps', {'prob': 0.1111111111111111})]那么經過翻轉之后就是：
[('http', {'prob': 0.1111111111111111}),
('https', {'prob': 0.0}),
('ftp', {'prob': 0.6666666666666666}),
('ftps', {'prob': 0.2222222222222222})]上述就是之前講到的專注測試常用功能或者非常用功能的基本思路，從此處引出的另一個比較關鍵的是通過Inputs幫我們專注于目標的特定功能，它和測試常用功能的區別就是首先要找到一批特殊的Inputs，通過這些Inputs作為seeds就可以對語法解析的過程進行概率分析和限制，使得后續的變異可以一直有較高的目標命中率。
Generator With Pre or Post or order Func
在某些Inputs在生成的時候，Fuzz作者可能希望對他們進行一些限制調整，獲取其它的操作，這些都可以通過pre func完成。這類似于hook，那么對于func觸發的時機一般就分為兩種，在Inputs的生成之前或者是生成之后，在語法里面的表示就是：
CHARGE_GRAMMAR: Grammar = {
"<start>": ["Charge <amount> to my credit card <credit-card-number>"],
"<amount>": ["$<float>"],
"<float>": ["<integer>.<digit><digit>"],
"<integer>": ["<digit>", "<integer><digit>"],
"<digit>": crange('0', '9'),
"<credit-card-number>": ["<digits>"],
"<digits>": ["<digit-block><digit-block><digit-block><digit-block>"],
"<digit-block>": ["<digit><digit><digit><digit>"],
}
CHARGE_GRAMMAR.update({
"<float>": [("<integer>.<digit><digit>", opts(pre=high_charge))], # high_charge是函數名稱
})
CHARGE_GRAMMAR.update({
"<float>": [("<integer>.<digit><digit>",
opts(pre=lambda: random.randint(10000000, 90000000) / 100.0))] # 或者選擇使用lambda表達式
})另一種就是在Seeds的生成之后了：
CHARGE_GRAMMAR.update({
"<credit-card-number>": [("<digits>", opts(post=lambda digits: fix_credit_card(digits)))]
})比如生成的digits不能滿足Fuzz的需求，我們就可以通過這種方式來進行及時的修正，以提高Fuzz的效率。
Greybox Fuzzing with Grammars
除了Fuzzing性能類的問題之外的另一個問題就是變異的導向問題，在Grammars Fuzz生成Input的過程中對于Grammar的內部解析是隨機的，但是對于Fuzz目標來說，大量的Input可能會觸發相同的分支進而導致代碼覆蓋率難以達到理想的值。對于AFL類似的覆蓋引導型Fuzz來說，因為白盒Fuzz的源代碼插樁緣故可以統計代碼覆蓋率來進行不錯的引導，但是還存在很多情況，比如黑盒，甚至是以一種WebServer為目標的Fuzz，統計代碼覆蓋率并不是一件簡單的事情，這時候采取的措施應該是不斷的增加Inputs生成的多樣性，比如在上述的派生樹的子節點的擴展過程進行統計，使其在生成Input語料的時候偏向于還沒擴展過的節點。這時候就會面臨新的問題，如何快速提升代碼覆蓋率？
在進行Fuzz的時候，有時候一些輸入的部分會被識別為關鍵字，比如C語言里面的int等，如果告訴Fuzz這些關鍵字就可以在短時間內極大的提升代碼覆蓋率，但是就長遠來看整體的代碼覆蓋率還是要差于不使用關鍵字字典的情況。下面是使用關鍵字字典的變異Inputs生成器。
class DictMutator(Mutator):
"""Mutate strings using keywords from a dictionary"""
def __init__(self, dictionary: List[str]) -> None:
"""Constructor. `dictionary` is the list of keywords to use."""
super().__init__()
self.dictionary = dictionary
self.mutators.append(self.insert_from_dictionary)
def insert_from_dictionary(self, s: str) -> str:
"""Returns s with a keyword from the dictionary inserted"""
pos = random.randint(0, len(s))
random_keyword = random.choice(self.dictionary)
return s[:pos] + random_keyword + s[pos:]但是問題在于關鍵字通過字典隨機引入的方式很可能破壞了Input本來的正確輸入結構進而引發不必要的損耗。解決的方法其實也很簡單：Fuzzing with Input Fragments.
- 對原有的Input進行Parse，形成派生樹。
- 對派生樹進行節點互換或者節點替換等操作。
- 對派生樹進行還原，形成新的Input。
以上的所有操作都在派生樹上進行。為了更方便的進行編譯操作，可以建立一個派生樹的碎片池，每個碎片都由子樹組成，子樹包括符號和對應的Node節點和其子節點。不過對于派生樹的parse其實是非常耗時的，因此可以設置一些時間限制來防止速度過低。不過以Fragments為基礎的變異雖然可以很好的符合Inputs合法性的要求但是在代碼覆蓋率提升方面并不亮眼。而且以此為基礎的LangFuzz其實在Inputs生成的速度上也遠低于平常的結構化黑盒Fuzz。下面是兩組對比數據：
LangFuzz
From the 300 generated inputs, 152 (50.67%) can be parsed.In total, 91 statements are covered.
BlackFuzz
From the 300 generated inputs, 36 (12.00%) can be parsed.In total, 161 statements are covered.可以看出以Fragments為基礎的變異的優勢在于它可以很好的生成符合結構化語法的變異。那么現在的疑問就是如何在保證輸入語法正確性的前提下提升代碼覆蓋率？
一種方法是利用類似AFL的覆蓋引導方式，利用代碼覆蓋率不斷作為變異的反饋，以此來不斷的增添提高代碼覆蓋率的種子，同時提供structural mutations和32 byte-level mutations兩種變異方式，如下：
class GreyboxGrammarFuzzer(GreyboxFuzzer):
"""Greybox fuzzer using grammars."""
def __init__(self, seeds: List[str],
byte_mutator: Mutator, tree_mutator: FragmentMutator,
schedule: PowerSchedule) -> None:
"""Constructor.
`seeds` - set of inputs to mutate.
`byte_mutator` - a byte-level mutator.
`tree_mutator` = a tree-level mutator.
`schedule` - a power schedule.
"""
super().__init__(seeds, byte_mutator, schedule)
self.tree_mutator = tree_mutator
def create_candidate(self) -> str:
"""Returns an input generated by structural mutation
of a seed in the population"""
seed = cast(SeedWithStructure, self.schedule.choose(self.population))
# Structural mutation
trials = random.randint(0, 4)
for i in range(trials):
seed = self.tree_mutator.mutate(seed)
# Byte-level mutation
candidate = seed.data
if trials == 0 or not seed.has_structure or random.randint(0, 1) == 1:
dumb_trials = min(len(seed.data), 1 << random.randint(1, 5))
for i in range(dumb_trials):
candidate = self.mutator.mutate(candidate)
return candidate想通的種子和變異次數的條件下，測試結果如下：
From the 300 generated inputs, 1 (0.33%) can be parsed.
In total, 180 statements are covered.同時，在Inputs生成的速度方面極大提升，較高的代碼覆蓋率，但是在Inputs的合法性方面表現是最差的。那這個問題該如何解決呢？答案就是Fuzzing with Input Regions，這種Fuzz的變異方法不再使用派生樹節點拆分重組等方式，而是通過將合法種子的不同區域直接進行拆分重組的方式，這里的區域指的是可以和派生樹符號對應的連續的字節序列，這樣的好處其實在于它操作的對象可能比Fragments更大或者更小，以此種方式進行變異在和上述變異條件相同的情況下測試結構如下：
It took the structural greybox fuzzer with region mutator
11.35 seconds to generate and execute 300 inputs.
From the 300 generated inputs, 4 (1.33%) can be parsed.
In total, 168 statements are covered.
On average, 9.1% of a seed in the population can be successfully parsed.可以看到存在較高的代碼覆蓋率，在速度方面雖然優于Fragments Fuzz但是還是弱于普通的黑盒Fuzz，在代碼覆蓋率方面高于Fragments Fuzz并和GreyboxGrammarFuzzer維持在相差無幾的水平。不過核心原因還是在于，通過的合法Inputs其實占比很低。那么如何解決這個問題？首先要讓Fuzzer可以聚焦合法的Inputs。這一點其實前面已經討論過了，只需要利用schedule給合法Inputs的相關結構賦予更多的權重。測試結果如下：
It took AFLSmart 20.75 seconds to generate and execute 300 inputs.
From the 300 generated inputs, 46 (15.33%) can be parsed.
In total, 162 statements are covered.
On average, 23.7% of a seed in the population can be successfully parsed.可以看出在代碼覆蓋率保持較高水平的情況下，Inputs的合法性也得到了大幅度的提升，但是在Inputs的生成速度上來看，還是遠弱于普通的GrammarFuzz。
從上面可以看出，在選擇Fuzz的時候本身就是一個取舍的問題，通過二次開發或者針對不同場景的選擇才能更好的達到我們想要的結果。
Parser input
假設你在做一個模糊測試，無論是Grammar Fuzz 或者其他的Fuzz也好，如果沒有合適的種子那么通過不斷變異形成合適的Inputs是非常困難的，當然AFL的作者展示了通過簡單的輸入不斷向目標進化的可能性，但是這畢竟十分浪費時間和性能，效果在很多場景下估計也是不盡人意的。
因此在進行模糊測試的時候如果可以獲取一些poc，或者其它較好種子，比如在Fuzz js解釋器的一個比較經常的做法就是將一些公開的poc，如下：
var haystack = "foo";
var re_text = "^foo";
haystack += "x";
re_text += "(x)";
var re = new RegExp(re_text);
re.test(haystack);
RegExp.input = Number();
print(RegExp.$1);作為seeds進行變異，將生成的Inputs用來Fuzz解釋器。表現出來不錯的結果。
Tips:如何判斷對面的代碼覆蓋率，一般黑盒情況下可以試時間，如果一個Input在對面耗費了更多的時間來運行，那么可以猜測其走過了更多的代碼分支。
總結
在面對Fuzz的目標的時候最重要的是選擇合適的變異方式以及較好的初始種子，根據目標和測試目的不斷地進行取舍和針對性開發才能得到比較理想的結果。
參考鏈接
文中數據測試來源大多為Fuzzingbook，因為根據電腦不同，其實具體數值結果會有一定偏差，但是結論都是一樣的，因此就展示了書中的測試數據。
本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/1942/
暫無評論