Growing A Test Corpus with Bonsai Fuzzing @ICSE'21

For generating synthesization automatically based on the ChocoPy dialect which I'm in great need of, the author of ChocoPy published their tricky counterpart to C-smith/ Fuzzy Grammer Generator called Bonsal Fuzzing.

Problems and Pair Review

Instead of Fuzz-then-reduce method, the corpus bottom up generation is already concise. enough and can touch much of the corner test cases.

  1. Bounded Exhaustive Testing: input of bounded size are generated systematically but not enumerated exhaustively
  2. So enumerate the k-path with the grammar.
  3. JPF-SE explores the space of program paths, for bounding the size of a comprehensive test suite that covers a diverse set of program paths
  4. different kind of strategies of fuzzing: Coverage-Guided Fuzzing, Specialized Compiler Fuzing, Grammar-based, Semantic Fuzzing(Zest)
  5. Test-Case Reduction by Hieachical delta debugging

Implementation

  1. Bounded Grammar Fuzzers: Bound iteration by idens, items, depths number.

  2. Coverage-Guided Bounded Grammar Fuzzing


    The lattice of coverage-guided size-bounded grammar-based fuzzers $F_{m,n,d}$, ordered by three size bounds on the syntax of the test cases they produce: number of unique identifiers m, maximum sequence length n, and maximum nesting depth d.

Test cases flow along directed edges: the inputs generated by each fuzzer are used as the seed inputs to its successors. The result of bonsai fuzzing is the corpus produced by the top-most element.

  1. Bonsai fuzzing with extended lattice