Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Learning And Refining Input Grammars For Effect...

Learning And Refining Input Grammars For Effective Fuzzing

SBST 2022 Tutorial

Rahul Gopinath

May 10, 2022
Tweet

More Decks by Rahul Gopinath

Other Decks in Research

Transcript

  1. 8 Random Fuzzing $ ./fuzz [;x1-GPZ+wcckc];,N9J+?#6^6\e?]9lu
 2_%'4GX"0VUB[E/r ~fApu6b8<{%siq8Z
 h.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"W2fK*vE7v{'
 )KC-i,c{<[~m!]o;{.'}Gj\(X}EtYetrp
 bY@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^LBM
 PG-FKj'\xwuZ1=Q`^`5,$N$Q@[!CuRzJ2
 D|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[Sc
 un&sBCS,T[/3]KAeEnQ7lU)3Pn,0)G/6N
 -wyzj/MTd#A;r*(ds./df3r8Odaf?/<#r Program ✘
  2. $ ./fuzz -int | program 634111569742810193727424069509 
 741355925061499451162464719526 
 615957331924826555590537407605

    
 181400079803446874252046374716 
 740973770255348279425601333144 
 152724057932073828569041216191 
 099859446496509919024810271242 
 622974988671421938012464630138 
 735355134599327240920259675263 
 574528613057084231370741920902 
 794677842164654990353575580453 
 777282305855352378119038096476 
 699871306655084953377039862387 
 924957554389878352934547664240 
 082431556093837288597262675598 
 630851919061829885048834738832 
 677022429414980917053939970795 
 722006987916088650168665471731 yes 9 Feedback Driven Fuzzing def is_prime(n: int) -> bool: """Primality test using 6k+-1 optimization.""" if n <= 3: return n > 1 if n % 2 == 0 or n % 3 == 0: return False i = 5 while i ** 2 <= n: if n % i == 0 or n % (i + 2) == 0: return False i += 6 return True def main(): num = stdin.read() print(num, is_prime(num))
  3. 11 Fuzzing Parsers $ ./fuzz [;x1-GPZ+wcckc];,N9J+?#6^6\e?]9lu
 2_%'4GX"0VUB[E/r ~fApu6b8<{%siq8Z
 h.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"W2fK*vE7v{'
 )KC-i,c{<[~m!]o;{.'}Gj\(X}EtYetrp
 bY@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^LBM
 PG-FKj'\xwuZ1=Q`^`5,$N$Q@[!CuRzJ2
 D|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[Sc
 un&sBCS,T[/3]KAeEnQ7lU)3Pn,0)G/6N
 -wyzj/MTd#A;r*(ds./df3r8Odaf?/<#r Interpreter
  4. 11 Fuzzing Parsers $ ./fuzz [;x1-GPZ+wcckc];,N9J+?#6^6\e?]9lu
 2_%'4GX"0VUB[E/r ~fApu6b8<{%siq8Z
 h.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"W2fK*vE7v{'
 )KC-i,c{<[~m!]o;{.'}Gj\(X}EtYetrp
 bY@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^LBM
 PG-FKj'\xwuZ1=Q`^`5,$N$Q@[!CuRzJ2
 D|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[Sc
 un&sBCS,T[/3]KAeEnQ7lU)3Pn,0)G/6N
 -wyzj/MTd#A;r*(ds./df3r8Odaf?/<#r Parser Syntax Error Interpreter #
  5. 12 Sepcification Free Generators A ( 2 - B 9

    ) 4 ) A ∉ (,+,-,1,2,3,4,5,6,7,8,9,0 B ∉ +,-,1,2,3,4,5,6,7,8,9,0,) ) ∉ +,-,1,2,3,4,5,6,7,8,9,0
  6. 12 Sepcification Free Generators A ( 2 - B 9

    ) 4 ) A ∉ (,+,-,1,2,3,4,5,6,7,8,9,0 B ∉ +,-,1,2,3,4,5,6,7,8,9,0,) ) ∉ +,-,1,2,3,4,5,6,7,8,9,0
  7. 12 Sepcification Free Generators A ( 2 - B 9

    ) 4 ) A ∉ (,+,-,1,2,3,4,5,6,7,8,9,0 B ∉ +,-,1,2,3,4,5,6,7,8,9,0,) ) ∉ +,-,1,2,3,4,5,6,7,8,9,0 (2-94)
  8. 17 Formal Languages Formal Language Descriptions 3. Regular Context Free

    Recursively Enumerable (Chomsky,1956) Argument Stack Return Stack
  9. 17 Formal Languages Formal Language Descriptions 3. Regular Context Free

    Recursively Enumerable (Chomsky,1956) Easy to produce and parse Argument Stack Return Stack
  10. 18 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
  11. 18 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
  12. 18 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 <expr> key
  13. 18 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
  14. 19 <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
  15. 19 <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
  16. 19 <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
  17. 19 <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
  18. 19 <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
  19. 21 Grammars For Parsing <start> := <expr> <expr> := <expr>

    '+' <expr> | <expr> '-' <expr> | <expr> '/' <expr> | <expr> '*' <expr> | '(' <expr> ')' | <number> <number> := <integer> | <integer> '.' <integer> <integer>:= <digit> <integer> | <digit> <digit> := [0-9]
  20. 21 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]
  21. 21 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]
  22. 23 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] For Fuzzing (Hanford 1970) (Purdom 1972)
  23. 23 Grammars8.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)
  24. 24 Grammars As effective producers 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
  25. 24 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
  26. 25 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
  27. 25 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)
  28. 29 Where to Get the Grammar From? 1. Extract the

    input string accesses 2. Attach control fl ow information (context-managers) Hand-written parsers already encode the grammar
  29. 30 How to Extract This Grammar? • Inputs + control

    fl ow -> Dynamic Control Dependence Trees
  30. 30 How to Extract This Grammar? • Inputs + control

    fl ow -> Dynamic Control Dependence Trees • DCD Trees -> Parse Tree
  31. 31 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
  32. 31 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
  33. 31 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
  34. 32 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
  35. 32 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()
  36. 33 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 DCD Tree ~ Parse Tree •No tracking beyond input bu ff er •Characters are attached to nodes where they are accessed last "12," "12,"
  37. 33 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,"
  38. 34 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')
  39. 34 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')
  40. 35

  41. 40

  42. <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> := '*' 43
  43. <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> := '*' 43
  44. 44 def is_digit(i): return i in '0123456789' <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
  45. 45 <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]
  46. 45 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]
  47. 46 <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()
  48. 47

  49. 48

  50. Why Did My Program Crash? 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 50
  51. Why Did My Program Crash? 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 DD Minimized Input ((4)) 50
  52. Why Did My Program Crash? 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 DD Minimized Input ((4)) 00000 ? 50
  53. Why Did My Program Crash? 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 DD Minimized Input ((4)) 00000 ? ((5)) ? 50
  54. Why Did My Program Crash? 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 DD Minimized Input ((4)) 00000 ? ((5)) ? (++5) ? 50
  55. 51

  56. 52 Issue 386 from Rhino var A = class extends

    (class {}){}; Issue 2937 from Closure const [y,y] = []; var {baz:{} = baz => {}} = baz => {}; Issue 385 from Rhino {while ((l_0)){ if ((l_0)) {break;;var l_0; continue }0}} Issue 2842 from Closure
  57. 52 Issue 386 from Rhino var A = class extends

    (class {}){}; Issue 2937 from Closure const [y,y] = []; var {baz:{} = baz => {}} = baz => {}; Issue 385 from Rhino {while ((l_0)){ if ((l_0)) {break;;var l_0; continue }0}} Issue 2842 from Closure
  58. 52 Issue 386 from Rhino var A = class extends

    (class {}){}; Issue 2937 from Closure const [y,y] = []; var {baz:{} = baz => {}} = baz => {}; Issue 385 from Rhino {while ((l_0)){ if ((l_0)) {break;;var l_0; continue }0}} Issue 2842 from Closure
  59. 52 Issue 386 from Rhino var A = class extends

    (class {}){}; Issue 2937 from Closure const [y,y] = []; var {baz:{} = baz => {}} = baz => {}; Issue 385 from Rhino {while ((l_0)){ if ((l_0)) {break;;var l_0; continue }0}} Issue 2842 from Closure
  60. 52 Issue 386 from Rhino var A = class extends

    (class {}){}; Issue 2937 from Closure const [y,y] = []; var {baz:{} = baz => {}} = baz => {}; Issue 385 from Rhino {while ((l_0)){ if ((l_0)) {break;;var l_0; continue }0}} Issue 2842 from Closure Delta Minimization is useful but not su ff i cient
  61. ( ( 4 ) ) <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-9] 53
  62. ( ( 4 ) ) <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-9] 54
  63. ( ( 4 ) ) <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-9] 55
  64. ( ( 4 ) ) <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-9] ✓ Did not reproduce the failure 1 * (2 - 3) 55
  65. ( ( 4 ) ) <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-9] 56
  66. ( ( 4 ) ) <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-9] c 57
  67. ( ( 4 ) ) <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-9] c 58
  68. ( ( 4 ) ) <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-9] c ✓ Did not reproduce the failure 1 + 3 + 4 58
  69. ( ( 4 ) ) <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-9] c c 59
  70. 3 * 4 <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-9] c c 60
  71. 3 * 4 <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-9] c c ✓ Did not reproduce the failure 60
  72. ( ( 4 ) ) <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-9] c c c c c c c 61
  73. ( ( 1 - 2 ) ) <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-9] c c c c c c c ( ( 1 - 2 ) ) 62
  74. ( ( 1 - 2 ) ) <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-9] c c c c c c c ✘ reproduced the failure ( ( 1 - 2 ) ) 62
  75. ( ( 1 - 2 ) ) c c c

    c c c c ( ( 1 - 2 ) ) 63
  76. ( ( 1 - 2 ) ) c c c

    c c c c ✘ ( ( 1 - 2 ) ) 63
  77. ( ( 1 - 2 ) ) c c c

    c c c c ✘ ( ( 1 - 2 ) ) ( ( 2 * 3 + 4 ) ) 64
  78. ( ( 1 - 2 ) ) c c c

    c c c c ✘ ( ( 1 - 2 ) ) ✘ ( ( 2 * 3 + 4 ) ) 64
  79. ( ( 1 - 2 ) ) c c c

    c c c c ✘ ( ( 1 - 2 ) ) ✘ ( ( 2 * 3 + 4 ) ) ( ( - 2 / 1 ) ) 65
  80. ( ( 1 - 2 ) ) c c c

    c c c c ✘ ( ( 1 - 2 ) ) ✘ ( ( 2 * 3 + 4 ) ) ✘ ( ( - 2 / 1 ) ) 65
  81. ( ( 1 - 2 ) ) c c c

    c c c c ✘ ( ( 1 - 2 ) ) ✘ ( ( 2 * 3 + 4 ) ) ✘ ( ( - 2 / 1 ) ) ( ( 98 - 0 ) ) 66
  82. ( ( 1 - 2 ) ) c c c

    c c c c ✘ ( ( 1 - 2 ) ) ✘ ( ( 2 * 3 + 4 ) ) ✘ ( ( - 2 / 1 ) ) ✘ ( ( 98 - 0 ) ) 66
  83. <expr> ) ( ( ) ( ( ) 4 )

    ( ( 4 ) ) c c c c c c c A 67
  84. <expr> ) ( ( ) ( ( ) 4 )

    ( ( 4 ) ) c c c c c c c A 68
  85. ( ( 4 ) ) c c c c c

    c c A ( ( ) ) <expr> ( ( ) ) 4 Minimized Input Abstract Failure Inducing Input def check(parsed): if parsed.is_nested() and parsed.child.is_nested(): raise Exception() return input 69
  86. 70 <start F> := <expr F> <expr F> := <term

    F> ' + ' <expr> | <term> ' + ' <expr F> | <term F> ' - ' <expr> | <term> ' - ' <expr F> | <term F> <term F> := <factor F> ' * ' <term> | <factor> ' * ' <term F> | <factor F> ' / ' <term> | <factor> ' / ' <term F> | <factor F> <factor F> := '+' <factor F> | '-' <factor F> | '(' <expr F> ')' | '(' <expr F1> ')' <expr F1> := <term F2> <term F2> := <factor F3> <factor F3>:= '(' <expr> ')' Specialized Grammar <factor F> is ((<expr>))
  87. 70 <start F> := <expr F> <expr F> := <term

    F> ' + ' <expr> | <term> ' + ' <expr F> | <term F> ' - ' <expr> | <term> ' - ' <expr F> | <term F> <term F> := <factor F> ' * ' <term> | <factor> ' * ' <term F> | <factor F> ' / ' <term> | <factor> ' / ' <term F> | <factor F> <factor F> := '+' <factor F> | '-' <factor F> | '(' <expr F> ')' | '(' <expr F1> ')' <expr F1> := <term F2> <term F2> := <factor F3> <factor F3>:= '(' <expr> ')' ((1)) + 2 (23 * ((3)) - 34) (344- 4 + ((223))) (1) - 3 * 773 + (-22 + 1) 1798 - 889 / ((333-1)) * 2 / 3 + 1 34 + ((4)) -334 + (334 - (22) + 919 * 0 + 1 98435747+ 88 + (((0))) + (1) - 1 * 7 / 4 * 889 - 2 8 + ((8)) + --1 + 11223 / 344 - 39 + (1) - 456 + 134 / 45 437 + 8 - 1 * ((9 + ((1))) - 1 + 99111948 + 3 --1 + (112) - 2 + 445) + 0 74 + 334 + ((178 - 88 / (3393-1) * 1002 / 3 + 1+ 3439)) * 223 - 1233 + 334672 2 * ((9)) - (1798 - 889 / (333-1) * 2 / 3 + 100012 + 3434392 + 234 ----6 * 1798 - 889 / (33 778 - (((1) - 3 * 773 + (-22 + 1) * (4545) - 23 - ((2)) * 773 + (-22 + 1) / 3434 + ---1 + 1 / 34343 + 112 349 + (((1) - 3 * 3 + (-22 + 1) ((+ (-22 + 1) * (4545) - 23 - (2) * 773 + ((-22 + 1)) / 3434 + ---1 + 1 / 34343 + 1123 8 + ((8)) + --1 + / 1 - 39 + (1) - 456 + 134 / 45 ))(((1) - 2334 + ((((1)) - 3 * 773 + (-22 + 1) * (2) - 23 - (2) * 773 + (-22 + 1) / 3 74 + 3 + ((178 - 88 / (3393-1) * 1002 / 3 + 1+ 3439)) * - 1233 + 334672)) ((8 + ((8)) + --1 + / 344 - 39 + (1) - 456 + 134 / 45 ))(((1) - 3 * 773 1+ 33+ 24343433 +23343 - ((74 + 334 + ((178 - 88 / (3393-1) * 1002 / 3 + 1+ 3439)) * - 1233 + 334672)) ((8 + ((8)) + --1 + / 344 - 39 + (1) - 456 + 134 / 4 ✘ Specialized Grammar <factor F> is ((<expr>)) ✘
  88. 72

  89. def jsoncheck(json): if any_key_has_null_value(json): fail(’key value must not be null’)

    process(json) {"abc": null} ✘ <item N> is <string> : null 74
  90. {"abc": []} ✔ no <item N> is <string> : null

    def jsoncheck(json): if any_key_has_null_value(json): fail(’key value must not be null’) process(json) 75
  91. {"abc": 124} ✘ no <item E> is "" : <elt>

    def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) process(json) 76
  92. def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if

    any_key_has_null_value(json): fail(’key value must not be null’) process(json) 78
  93. def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if

    any_key_has_null_value(json): fail(’key value must not be null’) process(json) {"": 124} ✔ <item E> is "" : <elt> no <item N> is <string> : null & 79
  94. def jsoncheck(json): if any_key_has_null_value(json): fail(’key value must not be null’)

    process(json) {"abc": null} ✘ <item N> is <string> : null Start Symbol 80
  95. def jsoncheck(json): if any_key_has_null_value(json): fail(’key value must not be null’)

    process(json) {"abc": []} no <item N> is <string> : null ✔ Start Symbol 81
  96. <item E> is "" : <elt> no <item N> is

    <string> : null & def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if any_key_has_null_value(json): fail(’key value must not be null’) process(json) {"": 124} ✔ Start Symbol 83
  97. def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if

    any_key_has_null_value(json): fail(’key value must not be null’) process(json) Evogram 84
  98. def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if

    any_key_has_null_value(json): fail(’key value must not be null’) process(json) Evogram 84
  99. def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if

    any_key_has_null_value(json): fail(’key value must not be null’) process(json) Evogram Automatically Derived 84
  100. def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if

    any_key_has_null_value(json): fail(’key value must not be null’) process(json) 85
  101. def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if

    any_key_has_null_value(json): fail(’key value must not be null’) process(json) 85
  102. def jsoncheck(json): if no_key_is_empty_string(json): fail(’one key must be empty’) if

    any_key_has_null_value(json): fail(’key value must not be null’) process(json) Automatically Derived 85
  103. Supercharged Pattern Matchers <json E and not(N)> where <item E>

    is "": <elt> <item N> is <string>:null <calc not(D or F)> where <factor F> is ((<expr>)) <term D> is <factor> / 0 <ipv4addr O and H> where <quad O> is "0" <num> <quad H> is "0x" <num> <C not(F) not(EW or ED or F)> where <forCondition F> is ";;" <iterationStatement EW> is <WHILE> "()" <statement> <iterationStatement ED> is <DO> <statement> <WHILE> "()" <eos> Alternative to Regular Expressions 86
  104. 87