Generating test cases to abuse a BNF grammar automagically.

Question

Hi,

I am wondering if there is a tool or technique which, given a BNF grammar, adjusts it randomly(but intelligently) and generates a stream of output for use in detecting cases that slip past the BNF (but shouldn't).

edit: Fuzz testing a parser, in other words.

Thanks

Answer 1

Spending some tender time with Google, I found that automated grammar-based fuzz testing is hard, and a subject of current research. In particular, P. Godefroid at Microsoft Research is working on a piece of software called SAGE.

I dug up a research paper by him.

Automated Whitebox Fuzz Testing (joint work with Michael Y. Levin and David Molnar) Proceedings of NDSS'2008 (Network and Distributed Systems Security), pages 151-166, San Diego, February 2008.

I also found the XML-based Peach software, but it is unclear to me on a casual reading how I might leverage it in an afternoon of work for a non-security application.

So my conclusion is: "It's a subject of current (Apr '10) research and there's no quick-use tool out there".