Generating test cases to abuse a BNF grammar automagically

Question

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".

Answer 2

Not strictly a BNF fuzzing tool, but american fuzzy lop employs artificial intelligence methods and can walk around the lack of BNF knowledge quite well. It already found bugs in many open source parsers, so it might be the right tool for yours as well.