Look Ma No Hands! Testing Software Without Specifications

ANU, Sydney

Transcript

1. 1 Look Ma, No Hands! Testing Software Without Specifications Rahul Gopinath https://rahul.gopinath.org rahul@gopinath.org @rahul@gopinath.org
2. 2 Look Ma, No Hands! Testing Software Without Specifications Rahul Gopinath https://rahul.gopinath.org rahul@gopinath.org @rahul@gopinath.org
3. 3 We live in a world defined by software
4. Bugs 4
6. 6 Input Testing @app.route('/admin') def admin(): username = request.cookies.get("username") if not username: return {"Error": "Specify username in Cookie"} username = urllib.quote(os.path.basename(username)) url = "http://permissions:5000/permissions/{}".format(username) resp = requests.request(method="GET", url=url) # "superadmin\ud888" will be simpli fi ed to "superadmin" ret = ujson.loads(resp.text) if resp.status_code == 200: if "superadmin" in ret["roles"]: return {"OK": "Superadmin Access granted"} else: e = u"Access denied. User has following roles: {}".format(ret["roles"]) return {"Error": e}, 401 else:return {"Error": ret["Error"]}, 500 usernam e=adm in
7. 7 Input Testing @app.route('/admin') def admin(): username = request.cookies.get("username") if not username: return {"Error": "Specify username in Cookie"} username = urllib.quote(os.path.basename(username)) url = "http://permissions:5000/permissions/{}".format(username) resp = requests.request(method="GET", url=url) # "superadmin\ud888" will be simpli fi ed to "superadmin" ret = ujson.loads(resp.text) if resp.status_code == 200: if "superadmin" in ret["roles"]: return {"OK": "Superadmin Access granted"} else: e = u"Access denied. User has following roles: {}".format(ret["roles"]) return {"Error": e}, 401 else:return {"Error": ret["Error"]}, 500 username=guest
8. 8 Input Testing @app.route('/admin') def admin(): username = request.cookies.get("username") if not username: return {"Error": "Specify username in Cookie"} username = urllib.quote(os.path.basename(username)) url = "http://permissions:5000/permissions/{}".format(username) resp = requests.request(method="GET", url=url) # "superadmin\ud888" will be simpli fi ed to "superadmin" ret = ujson.loads(resp.text) if resp.status_code == 200: if "superadmin" in ret["roles"]: return {"OK": "Superadmin Access granted"} else: e = u"Access denied. User has following roles: {}".format(ret["roles"]) return {"Error": e}, 401 else:return {"Error": ret["Error"]}, 500 username=a;pass
9. 9 Testing Needs Automation @app.route('/admin') def admin(): username = request.cookies.get("username") if not username: return {"Error": "Specify username in Cookie"} username = urllib.quote(os.path.basename(username)) url = "http://permissions:5000/permissions/{}".format(username) resp = requests.request(method="GET", url=url) # "superadmin\ud888" will be simpli fi ed to "superadmin" ret = ujson.loads(resp.text) if resp.status_code == 200: if "superadmin" in ret["roles"]: return {"OK": "Superadmin Access granted"} else: e = u"Access denied. User has following roles: {}".format(ret["roles"]) return {"Error": e}, 401 else:return {"Error": ret["Error"]}, 500 Synopsis: Open Source Security and Risk Analysis Report 2024 •Average 500 external OSS components per software •50% of the OSS components were unmaintained •84% of code bases contained vulnerabilities
10. 10 Fuzzing Automating Testing @app.route('/admin') def admin(): username = request.cookies.get("username") if not username: return {"Error": "Specify username in Cookie"} username = urllib.quote(os.path.basename(username)) url = "http://permissions:5000/permissions/{}".format(username) resp = requests.request(method="GET", url=url) # "superadmin\ud888" will be simpli fi ed to "superadmin" ret = ujson.loads(resp.text) if resp.status_code == 200: if "superadmin" in ret["roles"]: return {"OK": "Superadmin Access granted"} else: e = u"Access denied. User has following roles: {}".format(ret["roles"]) return {"Error": e}, 401 else:return {"Error": ret["Error"]}, 500 import random def fuzzer(max_length=100,chars=[chr(i) for i in range(32, 64)]): return ''.join([random.choice(chars) for i in range(random.randint(0,max_length))]) $ fuzz.py | myprogram
11. Ko=*JK~;zMKV=9Nai:wxu{J&UV#HaU)*BiC<),`+t*gka<W =Z.%T5WGHZpI30D<Pq>&]BS6R&j?#tP7iaV}-}`\? [_[Z^LBMPG-FKj'\xwuZ1=Q`^`5,$N$Q@[!CuRzJ2D|vBy! ^ z k h d f 3 C 5 P A k R ? V ( ( - % > < h n | 3='i2Qx]D$qs4O`1@fevnG'2\11Vf3piU37@5:dfd45*(7^% 5ap\zIyl"'f,$ee,J4Gw:cgNKLie3nx9(`efSlg6#[K"@WjhZ} r[Scun&sBCS,T[/3]KAeEnQ7lU)3Pn,0)G/6N-wyzj/ MTd#A;r 11 Fuzzing @app.route('/admin') def admin(): username = request.cookies.get("username") if not username: return {"Error": "Specify username in Cookie"} username = urllib.quote(os.path.basename(username)) url = "http://permissions:5000/permissions/{}".format(username) resp = requests.request(method="GET", url=url) # "superadmin\ud888" will be simpli fi ed to "superadmin" ret = ujson.loads(resp.text) if resp.status_code == 200: if "superadmin" in ret["roles"]: return {"OK": "Superadmin Access granted"} else: e = u"Access denied. User has following roles: {}".format(ret["roles"]) return {"Error": e}, 401 else:return {"Error": ret["Error"]}, 500 [;x1-GPZ+wcckc];,N9J+?#6^6\e?]9lu2_%'4GX"0VUB[E/ r ~fApu6b8<{%siq8Zh.6{V,hr?;{Ti.r3PIxMMMv6{xS^+'Hq! AxB"YXRS@!Kd6;wtAMefFWM(`|J_<1~o}z3K(CCzRH JIIvHz>_*.\>JrlU32~eGP?lR=bF3+;y$3lodQ<B89! 5 " W 2 f K * v E 7 v { ' ) K C - i , c { < [ ~ m ! ] o ; { . ' } G j \ ( X } EtYetrpbY@aGZ1{P!AZU7x#4(Rtn!q4nCwqol^y6}0| JIIvHz>_*.\>JrlU32~eGP?lR=bF3+;y$3lodQ<B89! 5"W2fK*vE7v{')KC-i,c{<[~m!]o;{.'}Gj\(X} EtYetrpbY@aGZ1{P!AZU7x#4(Rtn!q4nCwqol^y6}0| Ko=*JK~;zMKV=9Nai:wxu{J&UV#HaU)*BiC<),`+t*gka<W =Z.%T5WGHZpI30D<Pq>&]BS6R&j?#tP7iaV}-}`\? [_[Z^LBMPG-FKj'\xwuZ1=Q`^`5,$N$Q@[!CuRzJ2D|vBy! ^zkhdf3C5PAkR?V((-%><hn| 3='i2Qx]D$qs4O`1@fevnG'2\11Vf3piU37@5:dfd45*(7^% 5ap\zIyl"'f,$ee,J4Gw:cgNKLie3nx9(`efSlg6#[K"@WjhZ} r[Scun&sBCS,T[/3]KAeEnQ7lU)3Pn,0)G/6N-wyzj/ MTd#A;r import random def fuzzer(max_length=100,chars=[chr(i) for i in range(32, 64)]): return ''.join([random.choice(chars) for i in range(random.randint(0,max_length))]) $ fuzz.py | myprogram zsh: exit 139 Segmentation Fault: 11
12. Ko=*JK~;zMKV=9Nai:wxu{J&UV#HaU)*BiC<),`+t*gka<W =Z.%T5WGHZpI30D<Pq>&]BS6R&j?#tP7iaV}-}`\? [_[Z^LBMPG-FKj'\xwuZ1=Q`^`5,$N$Q@[!CuRzJ2D|vBy! ^ z k h d f 3 C 5 P A k R ? V ( ( - % > < h n | 3='i2Qx]D$qs4O`1@fevnG'2\11Vf3piU37@5:dfd45*(7^% 5ap\zIyl"'f,$ee,J4Gw:cgNKLie3nx9(`efSlg6#[K"@WjhZ} r[Scun&sBCS,T[/3]KAeEnQ7lU)3Pn,0)G/6N-wyzj/ MTd#A;r 12 Fuzzing @app.route('/admin') def admin(): username = request.cookies.get("username") if not username: return {"Error": "Specify username in Cookie"} username = urllib.quote(os.path.basename(username)) url = "http://permissions:5000/permissions/{}".format(username) resp = requests.request(method="GET", url=url) # "superadmin\ud888" will be simpli fi ed to "superadmin" ret = ujson.loads(resp.text) if resp.status_code == 200: if "superadmin" in ret["roles"]: return {"OK": "Superadmin Access granted"} else: e = u"Access denied. User has following roles: {}".format(ret["roles"]) return {"Error": e}, 401 else:return {"Error": ret["Error"]}, 500 Syntax Error [;x1-GPZ+wcckc];,N9J+?#6^6\e?]9lu2_%'4GX"0VUB[E/ r Syntax Error Syntax Error Syntax Error Syntax Error Syntax Error Syntax Error Syntax Error ~fApu6b8<{%siq8Zh.6{V,hr?;{Ti.r3PIxMMMv6{xS^+'Hq! AxB"YXRS@!Kd6;wtAMefFWM(`|J_<1~o}z3K(CCzRH JIIvHz>_*.\>JrlU32~eGP?lR=bF3+;y$3lodQ<B89! 5 " W 2 f K * v E 7 v { ' ) K C - i , c { < [ ~ m ! ] o ; { . ' } G j \ ( X } EtYetrpbY@aGZ1{P!AZU7x#4(Rtn!q4nCwqol^y6}0| JIIvHz>_*.\>JrlU32~eGP?lR=bF3+;y$3lodQ<B89! 5"W2fK*vE7v{')KC-i,c{<[~m!]o;{.'}Gj\(X} EtYetrpbY@aGZ1{P!AZU7x#4(Rtn!q4nCwqol^y6}0| Ko=*JK~;zMKV=9Nai:wxu{J&UV#HaU)*BiC<),`+t*gka<W =Z.%T5WGHZpI30D<Pq>&]BS6R&j?#tP7iaV}-}`\? [_[Z^LBMPG-FKj'\xwuZ1=Q`^`5,$N$Q@[!CuRzJ2D|vBy! ^zkhdf3C5PAkR?V((-%><hn| 3='i2Qx]D$qs4O`1@fevnG'2\11Vf3piU37@5:dfd45*(7^% 5ap\zIyl"'f,$ee,J4Gw:cgNKLie3nx9(`efSlg6#[K"@WjhZ} r[Scun&sBCS,T[/3]KAeEnQ7lU)3Pn,0)G/6N-wyzj/ MTd#A;r import random def fuzzer(max_length=100,chars=[chr(i) for i in range(32, 64)]): return ''.join([random.choice(chars) for i in range(random.randint(0,max_length))]) $ fuzz.py | myprogram zsh: exit 1 Syntax Error
13. def process_input(input): try: val = parse(input) res = process(val) return res except SyntaxError: return Error def process_input(input): try: ✘val = parse(input) res = process(val) return res except SyntaxError: return Error SYNTAX ERROR 13 Parser
14. SYNTAX ERROR def process_input(input): try: ✘val = parse(input) res = process(val) return res except SyntaxError: return Error 14 The Core
15. 15 1. SQL Injection:
 SELECT * FROM users WHERE username = '" + username + "' AND password = '" + password + "';
 username=' OR 1=1--, 2. XML External Entity Injection
 <!DOCTYPE foo [ <!ENTITY xxe SYSTEM " fi le:///etc/passwd"> ]> 3. Server-Side Template Injection:
 {{ user.name }}
 user.name == "__import__('os').system('rm -rf /')" 4. XPath Injection:
 //user[username/text()='" + username + "' and password/text()='" + password + "']
 usrname = ' or '1'='1 5. PHP command Injection:
 exec("ls " . $userInput);
 userInput = '; rm -rf /' 6. HTML injection (XSS):
 <div>Welcome, <%= username %>!</div>
 username = '<script>...<script>' 7. Expression Language Injection (SpEL, OGNL)
 #{user.name}
 user.name = #{T(java.lang.System).exit(0)} 8. YAML injection
 yaml.load(user_input)
 user_input = '!!python/object/apply:os.system ["ls -l"]' 9. XInclude injection
 <xi:include href="http://attacker.com/malicious.xml"/> 10.CSS Injection
 <style>@import url("http://attacker.com/malicious.css");</style> 11.Javascript Injection
 [exploit()] How to overcome parsers?
16. 16 Overcoming Parsers
17. 17 def process_input(input): try: val = parse(input) res = process(val) return res except SyntaxError: return Error 17 <json> ::= <elt> <elt> ::= <string> | <list> | <object> | <number> | 'true' | 'false' | 'null' <object'> ::= '{' <items> '}' | '{' '}' <items> ::= <item> ',' <items> | <item> <item> ::= <string> ':' <elt> <list> ::= '[' <elts> ']' | '[' ']' <elts> ::= <elt> ',' <elts> | <elt> <string> ::= '"' <chars> '"' | '"' '"' <char> ::= <char> <chars> | <char> <number> ::= <digits> <digits> ::= <digit> <digits> | <digit> <digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0' Fix: Input Grammar
18. 18 def process_input(input): try: ✔val = parse(input) res = process(val) return res except SyntaxError: return Error 18 ✓ Fix: Input Grammar <json> ::= <elt> <elt> ::= <string> | <list> | <object> | <number> | 'true' | 'false' | 'null' <object'> ::= '{' <items> '}' | '{' '}' <items> ::= <item> ',' <items> | <item> <item> ::= <string> ':' <elt> <list> ::= '[' <elts> ']' | '[' ']' <elts> ::= <elt> ',' <elts> | <elt> <string> ::= '"' <chars> '"' | '"' '"' <char> ::= <char> <chars> | <char> <number> ::= <digits> <digits> ::= <digit> <digits> | <digit> <digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0'
19. 19 def process_input(input): try: ✔val = parse(input) res = process(val) return res except SyntaxError: return Error 19 Fix: Input Grammar <json> ::= <elt> <elt> ::= <string> | <list> | <object> | <number> | 'true' | 'false' | 'null' <object'> ::= '{' <items> '}' | '{' '}' <items> ::= <item> ',' <items> | <item> <item> ::= <string> ':' <elt> <list> ::= '[' <elts> ']' | '[' ']' <elts> ::= <elt> ',' <elts> | <elt> <string> ::= '"' <chars> '"' | '"' '"' <char> ::= <char> <chars> | <char> <number> ::= <digits> <digits> ::= <digit> <digits> | <digit> <digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0'
20. 20 ASIDE: A Simple Solution Let the parser tell you what it wants
21. 21 Let the parser tell you what it wants [ 3 5 ]
22. 22 Track input string accesses and comparisons [ 3 5 PARSE ERROR c ∉{']' ','} ]
23. 23 Track input string accesses and comparisons [ 3 , ]
24. 24 Track input string accesses and comparisons [ 3 , ] PARSE ERROR c ∉{'0'.., '[', '{'}
25. 25 Track input string accesses and comparisons [ 3 , 1
26. 26 Track input string accesses and comparisons [ 3 , 1 ]
27. 27 • Identify character comparisons or EOF Key Idea: Viable Pre fi xes 27 • Complete with one of the compared characters [ 3 , 1 ] Mathis, Gopinath, Mera, Kampmann, Höschele, and Zeller. Parser Directed Fuzzing. PLDI 2019. Mathis, Gopinath and Zeller Learning Input Tokens for Effective Fuzzing. ISSTA 2020.
28. 28 Viable Pre fi xes 28 Limitations [ x [ ; @ [ 3 _ [ 3 _ [ 3 $ _ [ 3 , _ [ 3 , x _ [ 3 , 1 _ [ 3 , 1 ; _ [ 3 , 1 ] • Performance • Lack of control
30. Where to Get the Input Grammar From? 30
31. 31 Formal Languages Language Descriptions: Grammars Regular Context Free Recursively Enumerable (Chomsky,1956) Argument Stack Return Stack 31
32. 32 Grammar <start> := <expr> <expr> := <expr> '+' <expr> | <expr> '-' <expr> | <expr> '/' <expr> | <expr> '*' <expr> | '(' <expr> ')' | <number> <number> := <integer> | <integer> '.' <integer> <integer>:= <digit> <integer> | <digit> <digit> := [0-9] Arithmetic expression grammar De f inition for <expr> <expr> key
33. 33 <start> := <expr> <expr> := <expr> '+' <expr> | <expr> '-' <expr> | <expr> '/' <expr> | <expr> '*' <expr> | '(' <expr> ')' | <number> <number> := <integer> | <integer> '.' <integer> <integer>:= <digit> <integer> | <digit> <digit> := [0-9] Grammar Arithmetic expression grammar Expansion Rule Terminal Symbol Nonterminal Symbol
34. 34 Grammars For Parsing (8 / 3) * 49 <start> := <expr> <expr> := <expr> '+' <expr> | <expr> '-' <expr> | <expr> '/' <expr> | <expr> '*' <expr> | '(' <expr> ')' | <number> <number> := <integer> | <integer> '.' <integer> <integer>:= <digit> <integer> | <digit> <digit> := [0-9]
35. 35 Grammars 8.2 - 27 - -9 / +((+9 * --2 + --+-+- ((-1 * +(8 - 5 - 6)) * (-(a-+(((+(4) )))) - ++4) / +(-+---((5.6 - --(3 * -1.8 * +(6 * +-(((-(-6) * ---+6)) / +--(+-+-7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6.37) + (1) / 482) / +++-+0)))) + 8.2 - 27 - -9 / +((+9 * --2 + --+-+-((-1 * + (8 - 5 - 6)) * (-(a-+(((+(4))))) - + +4) / +(-+---((5.6 - --(3 * -1.8 * + (6 * +-(((-(-6) * ---+6)) / +--(+-+- 7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6.37) + (1) / 482) / +++-+0)))) * -+5 + 7.513)))) - (+1 / ++((-84)))))))) * ++5 / +-(- -2 - -++-9.0)))) / 5 * --++090 + * - +5 + 7.513)))) - (+1 / ++((-84)))))) )) * 8.2 - 27 - -9 / +((+9 * --2 + - -+-+-((-1 * +(8 - 5 - 6)) * (-(a-+(( (+(4))))) - ++4) / +(-+---((5.6 - -- (3 * -1.8 * +(6 * +-(((-(-6) * ---+6 )) / +--(+-+-7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6 .37) + (1) / 482) / +++-+0)))) * -+5 + 7.513)))) - (+1 / ++((-84)))))))) * ++5 / +-(--2 - -++-9.0)))) / 5 * --++090 ++5 / +-(--2 - -++-9.0)))) / 5 * --++090 <start> := <expr> <expr> := <expr> '+' <expr> | <expr> '-' <expr> | <expr> '/' <expr> | <expr> '*' <expr> | '(' <expr> ')' | <number> <number> := <integer> | <integer> '.' <integer> <integer>:= <digit> <integer> | <digit> <digit> := [0-9] For Fuzzing (Hanford 1970) (Purdom 1972)
36. 36 Grammars As effective producers Interpreter Parser✔ 8.2 - 27 - -9 / +((+9 * --2 + --+-+- ((-1 * +(8 - 5 - 6)) * (-(a-+(((+(4) )))) - ++4) / +(-+---((5.6 - --(3 * -1.8 * +(6 * +-(((-(-6) * ---+6)) / +--(+-+-7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6.37) + (1) / 482) / +++-+0)))) + 8.2 - 27 - -9 / +((+9 * --2 + --+-+-((-1 * + (8 - 5 - 6)) * (-(a-+(((+(4))))) - + +4) / +(-+---((5.6 - --(3 * -1.8 * + (6 * +-(((-(-6) * ---+6)) / +--(+-+- 7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6.37) + (1) / 482) / +++-+0)))) * -+5 + 7.513)))) - (+1 / ++((-84)))))))) * ++5 / +-(- -2 - -++-9.0)))) / 5 * --++090 + * - +5 + 7.513)))) - (+1 / ++((-84)))))) )) * 8.2 - 27 - -9 / +((+9 * --2 + - -+-+-((-1 * +(8 - 5 - 6)) * (-(a-+(( (+(4))))) - ++4) / +(-+---((5.6 - -- (3 * -1.8 * +(6 * +-(((-(-6) * ---+6 )) / +--(+-+-7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6 .37) + (1) / 482) / +++-+0)))) * -+5 + 7.513)))) - (+1 / ++((-84)))))))) * ++5 / +-(--2 - -++-9.0)))) / 5 * --++090 ++5 / +-(--2 - -++-9.0)))) / 5 * --++090
37. 37 Grammars <start> := <expr> <expr> := <expr> '+' <expr> | <expr> '-' <expr> | <expr> '/' <expr> | <expr> '*' <expr> | '(' <expr> ')' | <number> <number> := <integer> | <integer> '.' <integer> <integer>:= <digit> <integer> | <digit> <digit> := [0-9] As efficient producers def start(): expr() def expr(): match (random() % 6): case 0: expr(); print('+'); expr() case 1: expr(); print('-'); expr() case 2: expr(); print('/'); expr() case 3: expr(); print('*'); expr() case 4: print('('); expr(); print(')') case 5: number() def number(): match (random() % 2): case 0: integer() case 1: integer(); print('.'); integer() def integer(): match (random() % 2): case 0: digit(); integer() case 1: digit() def digit(): match (random() % 10): case 0: print('0') case 1: print('1') case 2: print('2') case 3: print('3') case 4: print('4') case 5: print('5') case 6: print('6') case 7: print('7') Compiled Grammar (F1) Building Fast Fuzzers Gopinath and Zeller 2019 FormatFuzzer: Effective Fuzzing of Binary File Formats
 Dutra, Gopinath and Zeller 2024 ACM TOSEM {'<start>': [['<expr>']], '<expr>' :[['<expr>','+','<expr>'], ['<expr>','-','<expr>'], ['<expr>','/','<expr>'], ['<expr>','*','<expr>'], ['(','<expr>',')'], ['<number>']], '<number>':[['<integer>'], ['<integer>','.','<integer>']], '<integer>':[['<digit>','<integer>'], ['<digit>']], '<digit>' :[[i] for i in range(0,9)]}
38. Where to Get the Grammar From? 38
39. Almost Everyone Uses Handwritten Parsers https://notes.eatonphil.com/parser-generators-vs-handwritten-parsers-survey-2021.html 39
40. Where to Get the Grammar From? 40
41. 41 "Be liberal in what you accept, and conservative in what you send" Postel's Law 41
42. QUIRK_ALLOW_ASCII_CONTROL_CODES QUIRK_ALLOW_BACKSLASH_A QUIRK_ALLOW_BACKSLASH_CAPITAL_U QUIRK_ALLOW_BACKSLASH_E QUIRK_ALLOW_BACKSLASH_NEW_LINE QUIRK_ALLOW_BACKSLASH_QUESTION_MARK QUIRK_ALLOW_BACKSLASH_SINGLE_QUOTE QUIRK_ALLOW_BACKSLASH_V QUIRK_ALLOW_BACKSLASH_X_AS_BYTES QUIRK_ALLOW_BACKSLASH_X_AS_CODE_POINTS QUIRK_ALLOW_BACKSLASH_ZERO QUIRK_ALLOW_COMMENT_BLOCK QUIRK_ALLOW_COMMENT_LINE QUIRK_ALLOW_EXTRA_COMMA QUIRK_ALLOW_INF_NAN_NUMBERS QUIRK_ALLOW_LEADING_ASCII_RECORD_SEPARATOR QUIRK_ALLOW_LEADING_UNICODE_BYTE_ORDER_MARK QUIRK_ALLOW_TRAILING_FILLER QUIRK_EXPECT_TRAILING_NEW_LINE_OR_EOF QUIRK_JSON_POINTER_ALLOW_TILDE_N_TILDE_R_TILDE_T QUIRK_REPLACE_INVALID_UNICODE JSON common quirks from https://github.com/google/wuffs 42 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
43. "Be liberal in what you accept, and conservative in what you send" Postel's Law The Specification The Implementation Extra "Features" Where to Get the Grammar From? 43 Bugs
45. 45 Grammar Mining : Whitebox extraction of grammar
 Grammar Extraction Speci fi cation Mining
 Model Extraction Grammar Inference: Blackbox extraction of grammar
 Grammar Induction Language Learning Automata Learning
 Model Inference
46. 46 Where to Get the Grammar From? Handwritten parsers contain the parse structure key value key value scheme parse_scheme parse_hostpath parse_querystring parse_fragment domain TLD subdomain parse_host subdirectory parse_fslocation binary parse_binaryname parameters parse_parameters parse_url
47. 47 Where to Get the Grammar From? Mining Grammar from a hand-written parser https://www.example.com/forum/questions/cgi?tag=networking&order=newwest#top key value key value split scheme parse_scheme host path parse_hostpath query string parse_querystring fragment parse_fragment domain TLD subdomain parse_host subdirectory parse_fslocation binary parse_binaryname parameters parse_parameters With Dynamic Data Flow Analysis parseurl
48. 48 http://user:pass@www.google.com:80/?q=path#ref urlparse:url = 'http://user:pass@www.google.com:80/?q=path#ref' urlsplit:scheme = 'http' urlsplit:netloc = 'user:pass@www.google.com:80' urlsplit:fragment = 'ref' urlsplit:query = 'q=path' https://soft-eng.sydney.edu.au:80/ urlparse:url = 'https://soft-eng.sydney.edu.au:80/' urlsplit:scheme = 'https' urlsplit:netloc = 'soft-eng.sydney.edu.au:80' http://www.fuzzingbook.org/#News urlparse:url = 'http://www.fuzzingbook.org/#News' urlsplit:scheme = 'http' urlsplit:netloc = 'www.fuzzingbook.org' urlsplit:fragment = 'News' Mining with Dynamic Data Flow Analysis
49. 49 { '<urlparse:url>': [ ['<urlsplit:scheme>', '://', '<urlsplit:netloc>', '/?', '<urlsplit:query>', '#', '<urlsplit:fragment>'], ['<urlsplit:scheme>', '://', '<urlsplit:netloc>', '/#','<urlsplit:fragment>'], ['<urlsplit:scheme>', '://', '<urlsplit:netloc>', '/']], '<urlsplit:scheme>' : [ ['http'], ['http']], '<urlsplit:netloc>': [ ['user:pass@www.google.com:80'], ['www.fuzzingbook.org'], ['soft-eng.sydney.edu.au']], '<urlsplit:query>' : [ ['q=path']], '<urlsplit:fragment>' : [ ['ref'], ['News']],
 } http://user:pass@www.google.com:80/?q=path#ref urlparse:url = 'http://user:pass@www.google.com:80/?q=path#ref' urlsplit:scheme = 'http' urlsplit:netloc = 'user:pass@www.google.com:80' urlsplit:fragment = 'ref' urlsplit:query = 'q=path' https://soft-eng.sydney.edu.au:80/ urlparse:url = 'https://soft-eng.sydney.edu.au:80/' urlsplit:scheme = 'https' urlsplit:netloc = 'soft-eng.sydney.edu.au:80' http://www.fuzzingbook.org/#News urlparse:url = 'http://www.fuzzingbook.org/#News' urlsplit:scheme = 'http' urlsplit:netloc = 'www.fuzzingbook.org' urlsplit:fragment = 'News' Mining with Dynamic Data Flow Analysis
50. { '<urlparse:url>': [ ['<urlsplit:scheme>', '://', '<urlsplit:netloc>', '/?', '<urlsplit:query>', '#', '<urlsplit:fragment>'], ['<urlsplit:scheme>', '://', '<urlsplit:netloc>', '/#','<urlsplit:fragment>'], ['<urlsplit:scheme>', '://', '<urlsplit:netloc>', '/']], '<urlsplit:scheme>' : [ ['http'], ['http']], '<urlsplit:netloc>': [ ['user:pass@www.google.com:80'], ['www.fuzzingbook.org'], ['soft-eng.sydney.edu.au']], '<urlsplit:query>' : [ ['q=path']], '<urlsplit:fragment>' : [ ['ref'], ['News']],
 } Limitations • Poor accuracy in most handwritten parsers • Handwritten parsers are not often well formed • Control flow is ignored Mining with Dynamic Data Flow Analysis
51. <F> := <A> | <B> <F> := <A> <B> <C> <Fs> := <B> <Fs> | <empty> Structured Control Flow to Grammar Sequence A B C [F] Selection cond A B [F] F T Iteration cond B [F] 51 Function [F] <F> := ...
52. 52 1. Extract the input string accesses 2. Attach control fl ow information Hand-written parsers already encode the grammar Mining with Dynamic Control Flow Analysis
53. 53 • Inputs + control fl ow -> Dynamic Control Dependence Trees • DCD Trees -> Parse Tree Mining with Dynamic Control Flow Analysis
54. 54 Control Dependence Graph Statement B is control dependent on A if A determines whether B executes. def parse_csv(s,i): while s[i:]: if is_digit(s[i]): n,j = num(s[i:]) i = i+j else: comma(s[i]) i += 1 CDG for parse_csv while: determines whether if: executes
55. 55 def parse_csv(s,i): while s[i:]: if is_digit(s[i]): n,j = num(s[i:]) i = i+j else: comma(s[i]) i += 1 CDG for parse_csv Dynamic Control Dependence Tree Each statement execution is represented as a separate node DCD Tree for call parse_csv()
56. 56 def parse_csv(s,i): while s[i:]: if is_digit(s[i]): n,j = num(s[i:]) i = i+j else: comma(s[i]) i += 1 '1' '2' ',' DCD Tree ~ Parse Tree •No tracking beyond input bu ff er •Characters are attached to nodes where they are accessed last "12," "12,"
57. 57 def is_digit(i): return i in '0123456789' def parse_num(s,i): n = '' while s[i:] and is_digit(s[i]): n += s[i] i = i +1 return i,n def parse_paren(s, i): assert s[i] == '(' i, v = parse_expr(s, i+1) if s[i:] == '': raise Ex(s, i) assert s[i] == ')' return i+1, v def parse_expr(s, i = 0): expr, is_op = [], True while s[i:]: c = s[i] if isdigit(c): if not is_op: raise Ex(s,i) i,num = parse_num(s,i) expr.append(num) is_op = False elif c in ['+', '-', '*', '/']: if is_op: raise Ex(s,i) expr.append(c) is_op, i = True, i + 1 elif c == '(': if not is_op: raise Ex(s,i) i, cexpr = parse_paren(s, i) expr.append(cexpr) is_op = False elif c == ')': break else: raise Ex(s,i) if is_op: raise Ex(s,i) return i, expr 9+3/4 Parse tree for parse_expr('9+3/4')
58. 58 def is_digit(i): return i in '0123456789' def parse_num(s,i): n = '' while s[i:] and is_digit(s[i]): n += s[i] i = i +1 return i,n def parse_paren(s, i): assert s[i] == '(' i, v = parse_expr(s, i+1) if s[i:] == '': raise Ex(s, i) assert s[i] == ')' return i+1, v def parse_expr(s, i = 0): expr, is_op = [], True while s[i:]: c = s[i] if isdigit(c): if not is_op: raise Ex(s,i) i,num = parse_num(s,i) expr.append(num) is_op = False elif c in ['+', '-', '*', '/']: if is_op: raise Ex(s,i) expr.append(c) is_op, i = True, i + 1 elif c == '(': if not is_op: raise Ex(s,i) i, cexpr = parse_paren(s, i) expr.append(cexpr) is_op = False elif c == ')': break else: raise Ex(s,i) if is_op: raise Ex(s,i) return i, expr 9+3/4 Identifying Compatible Nodes Which nodes correspond to the same nonterminal
59. 59 (9 + 1) * 3 3 * (9 + 1)
60. 60 9 + 1 3 * (9 + 1)
61. 61 3 (9 + 1) * 3 * (9 + 1)
62. 62 3*(1) 1
63. 63 3*(1) 1 <parse_expr> := <while 1:1> <while 1:0> <while 1:1> <while 1:1> <parse_expr> :=
64. <parse_expr> := <while_s> <while_s> := <while_1:1> <while_1:0> <while_s> | <while_1:1> <parse_expr> := <while 1:1> <while 1:0> <while 1:1> | <while 1:1> <while 1:0> <while 1:1> <while 1:0> <while 1:1> <while 1:0> <while 1:1> | <while 1:1> <while 1:0> <while 1:1> <while 1:0> <while 1:1> | <while 1:1> <while 1:1> := <if 1:1> <if 1:1> := <parse_num> | <parse_paren> <parse_num> := <is_digit> <is_digit> := '3' | '1' <parse_paren>:= '(' <parse_expr> ')' <while 1:0> := <if 1:0> <if 1:0> := '*' 64
65. 65 def is_digit(i): return i in '0123456789' def parse_num(s,i): n = '' while s[i:] and is_digit(s[i]): n += s[i] i = i +1 return i,n def parse_paren(s, i): assert s[i] == '(' i, v = parse_expr(s, i+1) if s[i:] == '': raise Ex(s, i) assert s[i] == ')' return i+1, v def parse_expr(s, i = 0): expr, is_op = [], True while s[i:]: c = s[i] if isdigit(c): if not is_op: raise Ex(s,i) i,num = parse_num(s,i) expr.append(num) is_op = False elif c in ['+', '-', '*', '/']: if is_op: raise Ex(s,i) expr.append(c) is_op, i = True, i + 1 elif c == '(': if not is_op: raise Ex(s,i) i, cexpr = parse_paren(s, i) expr.append(cexpr) is_op = False elif c == ')': break else: raise Ex(s,i) if is_op: raise Ex(s,i) return i, expr <START> := <parse_expr.0-0-c> <parse_expr.0-0-c> := <parse_expr.0-1-s><parse_expr.0> | <parse_expr.0> <parse_expr.0-1-s> := <parse_expr.0><parse_expr.0-2> | <parse_expr.0><parse_expr.0-2><parse_expr.0-1-s> <parse_expr.0> := '(' <parse_expr.0-0-c> ')' | <parse_num.0-1-s> <parse_expr.0-2> := '*' | '+' | '-' | '/' <parse_num.0-1-s> := <is_digit.0-0-c> | <is_digit.0-0-c><parse_num.0-1-s> <is_digit.0-0-c> : [0-9] calc.py Recovered Arithmetic Grammar
66. 66 8.2 - 27 - -9 / +((+9 * --2 + --+-+- ((-1 * +(8 - 5 - 6)) * (-(a-+(((+(4) )))) - ++4) / +(-+---((5.6 - --(3 * -1.8 * +(6 * +-(((-(-6) * ---+6)) / +--(+-+-7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6.37) + (1) / 482) / +++-+0)))) + 8.2 - 27 - -9 / +((+9 * --2 + --+-+-((-1 * + (8 - 5 - 6)) * (-(a-+(((+(4))))) - + +4) / +(-+---((5.6 - --(3 * -1.8 * + (6 * +-(((-(-6) * ---+6)) / +--(+-+- 7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6.37) + (1) / 482) / +++-+0)))) * -+5 + 7.513)))) - (+1 / ++((-84)))))))) * ++5 / +-(- -2 - -++-9.0)))) / 5 * --++090 + * - +5 + 7.513)))) - (+1 / ++((-84)))))) )) * 8.2 - 27 - -9 / +((+9 * --2 + - -+-+-((-1 * +(8 - 5 - 6)) * (-(a-+(( (+(4))))) - ++4) / +(-+---((5.6 - -- (3 * -1.8 * +(6 * +-(((-(-6) * ---+6 )) / +--(+-+-7 * (-0 * (+(((((2)) + 8 - 3 - ++9.0 + ---(--+7 / (1 / +++6 .37) + (1) / 482) / +++-+0)))) * -+5 + 7.513)))) - (+1 / ++((-84)))))))) * ++5 / +-(--2 - -++-9.0)))) / 5 * --++090 ++5 / +-(--2 - -++-9.0)))) / 5 * --++090 <START> := <parse_expr.0-0-c> <parse_expr.0-0-c> := <parse_expr.0-1-s><parse_expr.0> | <parse_expr.0> <parse_expr.0-1-s> := <parse_expr.0><parse_expr.0-2> | <parse_expr.0><parse_expr.0-2><parse_expr.0-1-s> <parse_expr.0> := '(' <parse_expr.0-0-c> ')' | <parse_num.0-1-s> <parse_expr.0-2> := '*' | '+' | '-' | '/' <parse_num.0-1-s> := <is_digit.0-0-c> | <is_digit.0-0-c><parse_num.0-1-s> <is_digit.0-0-c> : [0-9]
67. 67 <START> ::= <json_raw> <json_raw> ::= '"' <json_string'> | '[' <json_list'> | '{' <json_dict'> | <json_number'> | 'true' | 'false' | 'null' <json_number'> ::= <json_number>+ | <json_number>+ 'e' <json_number>+ <json_number> ::= '+' | '-' | '.' | [0-9] | 'E' | 'e' <json_string'> ::= <json_string>* '"' <json_list'> ::= ']' | <json_raw> (','<json_raw>)* ']' | ( ',' <json_raw>)+ (',' <json_raw>)* ']' <json_dict'> ::= '}' | ( '"' <json_string'> ':' <json_raw> ',' )* '"'<json_string'> ':' <json_raw> '}' <json_string> ::= ' ' | '!' | '#' | '$' | '%' | '&' | ''' | '*' | '+' | '-' | ',' | '.' | '/' | ':' | ';' | '<' | '=' | '>' | '?' | '@' | '[' | ']' | '^' | '_', ''',| '{' | '|' | '}' | '~' | '[A-Za-z0-9]' | '\' <decode_escape> <decode_escape> ::= '"' | '/' | 'b' | 'f' | 'n' | 'r' | 't' stm.next() if expect_key: raise JSONError(E_DKEY, stm, stm.pos) if c == '}': return result expect_key = 1 continue # parse out a key/value pair elif c == '"': key = _from_json_string(stm) stm.skipspaces() c = stm.next() if c != ':': raise JSONError(E_COLON, stm, stm.pos) stm.skipspaces() val = _from_json_raw(stm) result[key] = val expect_key = 0 continue raise JSONError(E_MALF, stm, stm.pos) def _from_json_raw(stm): while True: stm.skipspaces() c = stm.peek() if c == '"': return _from_json_string(stm) elif c == '{': return _from_json_dict(stm) elif c == '[': return _from_json_list(stm) elif c == 't': return _from_json_fixed(stm, 'true', True, E_BOOL) elif c == 'f': return _from_json_fixed(stm, 'false', False, E_BOOL) elif c == 'n': return _from_json_fixed(stm, 'null', None, E_NULL) elif c in NUMSTART: return _from_json_number(stm) raise JSONError(E_MALF, stm, stm.pos) def from_json(data): stm = JSONStream(data) return _from_json_raw(stm) microjson.py Recovered JSON grammar
68. def json_raw(stm): while True: stm.skipspaces() c = stm.peek() if c == 't': return json_fixed(stm, 'true') elif c == 'f': return json_fixed(stm, 'false') elif c == 'n': return json_fixed(stm, 'null') elif c == '"': return json_string(stm) elif c == '{': return json_dict(stm) elif c == '[': return json_list(stm) elif c in NUMSTART: return json_number(stm) raise JSONError(E_MALF, stm, stm.pos) <json_raw>::= <json_object>
 | <json_list>
 | <json_string>
 | <json_number>
 | <json_fixed(true)> | <json_fixed(false)> | <json_fixed(null)> <json_string> ::= `"` <chars> `"` | `""` <chars> ::= <char><chars> | <char> <json_object> ::= `{`<items>`}` | `{}` <items> ::= <item>`,`<items> | <item> <item> ::= <string>`:`<elt> <json_list> ::= `[`<elts>`]` | `[]` <elts> ::= <elt>`,`<elts> | <elt> <json_number> ::= <digits> <digits> ::= <digit><digits> | <digit> https://github.com/phensley/microjson MicroJSON 68 68
69. def json_raw(stm): while True: stm.skipspaces() c = stm.peek() if c == 't': return json_fixed(stm, 'true') elif c == 'f': return json_fixed(stm, 'false') elif c == 'n': return json_fixed(stm, 'null') elif c == '"': return json_string(stm) elif c == '{': return json_dict(stm) elif c == '[': return json_list(stm) elif c in NUMSTART: return json_number(stm) raise JSONError(E_MALF, stm, stm.pos) <json_raw>::= <json_object>
 | <json_list>
 | <json_string>
 | <json_number>
 | <json_fixed(true)> | <json_fixed(false)> | <json_fixed(null)> <json_string> ::= `"` <chars> `"` | `""` <chars> ::= <char><chars> | <char> <json_object> ::= `{`<items>`}` | `{}` <items> ::= <item>`,`<items> | <item> <item> ::= <string>`:`<elt> <json_list> ::= `[`<elts>`]` | `[]` <elts> ::= <elt>`,`<elts> | <elt> <json_number> ::= <digits> <digits> ::= <digit><digits> | <digit> https://github.com/phensley/microjson MicroJSON 69 Gopinath, Mathis, and Zeller. Mining Input Grammars from Dynamic Control Flow. ESEC/FSE 2020.
70. 70 70 PART II
71. Service topology map of Uber showing hundreds of microservices (Source: Uber Engineering) Instrumentation ability or source code access is not always guaranteed
72. 72 Blackbox Grammar Inference
73. Grammar Inference Problem: Exponential Search Space 2n possibilities for n length string
74. Grammar Inference Problem: Exponential Search Space 2n possibilities for n length string
75. Grammar Inference for Fuzzing (SE) Assumption: Example Inputs are Available
76. Finding Good Examples Example corpus? (Blind spots) 76 INSERT INTO Students VALUES ('Robert'); DROP TABLE Students; --', 'XKCD')
77. 77 Blackbox Grammar Inference Without Examples L* Family
78. 78 Grammar Inference (L* Family) 2022 1987
79. 79 Grammar Inference (L* Family) Learner Teacher ab ac aaa aa aab
80. 80 Grammar Inference (L* Family) Assumption: Minimally Adequate Teacher
81. 81 Grammar Inference (L* Family) Equivalences Queries are not possible in software engineering scenarios
82. 82 L* Teacher with PAC Guarantees ab ✓ ✓ abb ✘ ✘ bb ✓ ✓ aaaa ✓ ✓ bbb ✓ ✘ Idea: Substitute equivalence queries with membership queries
83. 83 L* Teacher with PAC Guarantees ab ✓ ✓ abb ✘ ✘ bb ✓ ✓ aaaa ✓ ✓ bbb ✘ ✘ aaa ✘ ✘ abab ✘ ✘ Idea: Substitute equivalence queries with membership queries
84. 84 L* Teacher with PAC Guarantees Probably Approximately Correct (Valiant'84) Pr(L(A)≢X ≤ ϵ) ≥ 1−δ 1-∈: accuracy 1-δ: confidence Equivalence Query = Multiple Membership Checks Checks come from some sampling distribution D over A* We only get a PAC guarantee based on D qi = [1/ϵ (ln(1/δ) + i ln(2))] Checks made in place of ith equivalence query:
85. 85 Grammar Inference (PAC-L*) Random Sampler (D) Blackbox Hypothesis w ∈ D L(*) Substituting Equivalence Queries ab ✓ ✓ abb ✘ ✘ bb ✓ ✓ aaaa ✓ ✓ bbb ✓ ✘
86. 86 Grammar Inference (PAC-L*) Random Sampler (D) w ∈ D L(*) Substituting Equivalence Queries Search Space
87. 87 Solution: Leverage Error Feedback
88. 88 Key Idea: Leverage Error Feedback 88 Viable Prefix
89. 89 • Differentiate incomplete and incorrect inputs Key Idea: Viable Pre fi xes 89 • Solve one character at a time systematically
90. 90 Example Generator With Pre fi x Queries a [ 5 1 b , } 4 ] a ∉ [,],{,},",0,1,2,3,4,5,.,. b ∉ [,],0,1,2,3,4,5,6,7,8,9,, } ∉ [,],0,1,2,3,4,5,6,7,8,9,0,, [51,4] 90
91. 91 [51,4] a [ 5 1 b , } 4 ] a ∉ [,],{,},",0,1,2,3,4,5,.,. b ∉ [,],0,1,2,3,4,5,6,7,8,9,, } ∉ [,],0,1,2,3,4,5,6,7,8,9,0,, 91 [51,4] 👍 [51,4x 👎 [51,4 👎 [51,4- 👎 Example Generator With Pre fi x Queries
92. 92 Pre fi xQ AFL(black) INI 62.5 65 CSV 65.7 68.3 JSON 13.8 9.2 TinyC 86.8 47.9 MJS 28.0 19.0 Quality of Examples with Pre fi x Queries Branch Coverage Obtained C programs
93. 93 Pre fi xQ AFL(black) AFL(grey) INI 62.5 65 77.5 CSV 65.7 68.3 68.5 JSON 13.8 9.2 22.5 TinyC 86.8 47.9 81.6 MJS 28.0 19.0 29.9 Branch Coverage Obtained C programs Even compared with grey-box AFL, blackbox pre fi x queries are competitive Quality of Examples with Pre fi x Queries
94. 94 Crash: ]9xdy[zSf$\theta{f!;} ;i\nonfrenchspacing !$$\prec q;7O/, $\downbrace fi ll @Pz \mathstrut{}$^: aK[X|?$47$ ,`D f$)Cg8$* Quality of Examples with Pre fi x Queries
95. 95 a [ 5 1 95 Example Generator With Pre fi x Queries Not under PAC! ] 23] ,124] ] 23] ,124] $ ; } ) $ ; } )
96. 96 a [ 5 96 Example Generator With Pre fi x Queries Not under PAC! $ ; } ) 0,1,2,3,4,5,6,7,8,9,
97. 97 97 Example Generator With Pre fi x Queries Not under PAC! [ 5 1 [ 5 1 Check state by state equivalence with blackbox ] 23] ,124] ] 23] ,124] $ ; } ) $ ; } )
98. 98 Grammar Inference (PL*) Blackbox Hypothesis w ∈ B Yes/No Yes/No PL(*) w ∈ H Substituting Equivalence Queries
99. 99 Grammar Inference (PL*) Pr(L(A)≢X ≤ ϵ) ≥ 1−δ Relation between p,ϵ,δ and F1 score On Arithmetic (depth limited) L(*) Eq = Pre fi x Sampler Eq = Pre fi x Sampler) (p=0.05) (p=0.5) Eq = Pre fi x Sampler) (p=1.0) Red is good, Blue is bad PL(*) PL(*) PL(*) 1-δ: confidence 1-∈: accuracy
100. 100 Grammar Inference (PL*) Pr(L(A)≢X ≤ ϵ) ≥ 1−δ Relation between p,ϵ,δ and F1 score On JSON (depth limited) L(*) Eq = Pre fi x Sampler (p=0.05) Eq = Pre fi x Sampler) (p=0.5) Eq = Pre fi x Sampler) (p=1.0) Red is good, Blue is bad 1-δ: confidence 1-∈: accuracy PL(*) PL(*) PL(*)
102. 102 PART III Work in Progress
103. 103 Inferring Program Behaviour (Oracles) Assumption: • Programs have gone through some testing • Program behaviour can be considered partitions on some space Implications: • Programmers will find all big partitions • Programmers will find some small partitions • Programmers wont find all small partitions Idea: Learn the language of system behaviour • Identify partitions (and corresponding inputs), largest first
104. 104 Inferring Program Behaviour (Oracles) Whitebox Blackbox Blackbox Blackbox
105. 105 Inferring Program Behaviour (Oracles) (1) (2) (3) (4) No negative examples
106. 106 Isolating Program Behaviour 2023-06-10 09:00:00 INFO [FileWriterThread-1] com.example.FileWriter.writeToFile Writing data to fi le: /path/to/ fi le.txt 2023-06-10 09:01:30 INFO [NetworkConnectionManager] com.example.NetworkConnector.openConnection Opening network connection to 2023-06-10 09:02:15 INFO [DatabaseConnectionPool-1] com.example.DatabaseConnector.getConnection Acquired database connection fro 2023-06-10 09:05:45 INFO [DatabaseConnectionPool-1] com.example.DatabaseConnector.releaseConnection Released database connectio 2023-06-10 09:10:00 INFO [NetworkConnectionManager] com.example.NetworkConnector.closeConnection Closing network connection to 1 2023-06-10 09:15:30 INFO [FileWriterThread-2] com.example.FileWriter.writeToFile Writing data to fi le: /path/to/another_ fi le.txt 2023-06-10 09:20:00 INFO [UserAuthenticationService] com.example.auth.LoginHandler.handleLogin User 'john_doe' logged in successfully 2023-06-10 09:22:30 WARN [CacheManager] com.example.cache.CacheEvictionPolicy.evictEntries Cache size exceeded maximum limit. Evi 2023-06-10 09:25:15 ERROR [PaymentProcessingWorker-3] com.example.payments.PaymentProcessor.processPayment Payment processin 2023-06-10 09:30:45 INFO [EmailNoti fi cationService] com.example.noti fi cations.EmailSender.sendEmail Sent email noti fi cation to user@exam 2023-06-10 09:35:00 INFO [FileReaderThread-1] com.example. fi le.FileReader.readFromFile Reading data from fi le: /path/to/input.csv 2023-06-10 09:40:30 INFO [DatabaseBackupJob] com.example.db.DatabaseBackupService.performBackup Database backup completed su 2023-06-10 09:45:15 WARN [APIRequestHandler] com.example.api.RequestThrottler.handleRequest API request rate limit exceeded for clien 2023-06-10 09:50:45 INFO [FileUploadService] com.example.upload.FileUploadHandler.handleUpload File 'document.pdf' uploaded success 2023-06-10 09:55:00 ERROR [ImageProcessingWorker-2] com.example.image.ImageResizer.resizeImage Failed to resize image: image_001.jp 2023-06-10 10:00:30 INFO [JobScheduler] com.example.jobs.ScheduledJob.executeJob Executing scheduled job: Daily Sales Report Gener A typical log of events
107. 107 Fuzzer Blackbox GET... POST...A; POST...B;A POST..B Isolating Program Behaviour Grammar (G) - Generate inputs with the input grammar G - Look for a speci fi c event A in the event log - Collect the inputs that cause it A
108. 108 Fuzzer Blackbox Isolating Program Behaviour Grammar (G) - Generate inputs with the input grammar G - Look for a speci fi c event A in the event log - Collect the inputs that cause it A RA POST...AB POST...A; POST...B;A POST..A .*;.*
109. 109 Blackbox Ensuring Events Fuzzer G /\ RA A POST...A;ab POST...x;y POST...A;-- POST...B;A POST...A;vb$ .*;.*
110. 110 Blackbox Ensuring Events Fuzzer G /\ RB - Generate inputs with the input grammar G - Look for a speci fi c event A in the event log - Collect the inputs that cause it - Abstract all such inputs into a grammar RA - Any inputs from G /\ RA will cause the event A - Same for event B, event C etc. B POST...C$ab POST...x$ POST...$$ POST...$ POST...A$ .*$.*
111. 111 Blackbox Fuzzer G /\ (RA /\ RB) - Fuzzer using grammar G /\ (RA /\ RB)
 will produce events A and B consistently A+B Behaviour Algebra POST...C$a;b POST...;$ POST...A$B;C; POST...C;$x$ POST...$; .*(;|$).*
112. 112 Blackbox Behaviour Algebra Fuzzer G /\ (RA /\ RB\RC ) - Fuzzer using grammar G /\ (RA /\ RB)
 will produce events A and B consistently - Fuzzer using G /\ (RA /\ RB - RC)
 will produce events A and B consistently without C
 (if it is possible to produce such sequences) A+B \ C POST...;$ POST...$;
113. 113 Inferring Oracles Negative examples: Recipe - Abstract behaviour inducing inputs - Use input algebras to combine input patterns inducing atomic events - For checking the event sequence A.B.C fuzz with G (RA /\ RB /\ Rc ) - If A.B.C is not found, either A.B.C is impossible or it is rare Fuzzer G /\ (RA /\ RB /\ RC ) (B) (A) (C) Input pattern inducing event A Input pattern inducing event B Input pattern inducing event C
114. 114 Infer Input Grammar Oracle Induction Software Testing Without Speci fi cations Interpreter Parser✔
115. 115 Grammar Mining Grammar Inference Oracle Induction