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


  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

Preempting Flaky Tests via Non-Idempotent-Outcome Tests @ICSE '22

Nonidiomatic test are one of Flaky tests category. In the previous TACAS work, the relation between polluters(modify the shared state) and victims(read from the shared state) are found but there exists a lot false positive for it to have Order dependent variables inside, from our previous tests on these testcases. Also for the latent polluters/victims that potentially read/write the variables. e.g.

//shared variables x,y,z are initialized into 0
void t1(){ assert x==0; } // victim
void t2(){ x = 0; } // polluter
void t3(){ assert y==0; } // latent-victim
void t4(){ z=1; } // latent-polluter
void t5(){ assert w=0;w=1;}

The NIO tests means passes in the first run but fails in the second when run twice consecutively.

The NIO will self pollutes the state that its own assertions depend on

  • NIO $\in$ latent-polluter ^ latent-victim $\in$ latent-writer


Real Examples

Static Inference Meets Deep Learning: A Hybrid Type Inference Approach for Python @ICSE '22

The type inference in dynamic function in python.

Compared with static inference like Pyre.

Static+DL Approach

先 Type dependency graph,在路径constraint上做验证正确性,最后再验证正确性。其实非动态语言rust的类型推导💥问题也可以这样解决。至少DL给了一个搜索路径。


重点就是Backward Type Rejection的语义。

看了下,比如subscript的刻画还是很准确的,但是symbolic value的rejection rule还是会比sound 大一些。

Counter case