Minimal test case generator tool?

An interesting idea that Daniel Wagner, Vilhelm Sjöberg and I just came up with: a minimal test case generator. Here’s the idea: you have a program which exhibits error X, which you want to understand better; or perhaps you suspect it is a bug in the compiler, and you want to submit a test case along with your bug report. As input to the minimal test case generator, you give your program along with some sort of description of error X. It then tries to shrink your program as much as possible while still exhibiting error X. Of course, doing the shrinking would be nontrivial: you’d have to parse the program and do some sort of call graph analysis, and then only delete leaves in the call graph. But, of course, tools for analyzing call graphs already exist.

How difficult would this be to develop? Does anything like this already exist?

About these ads
This entry was posted in meta and tagged , , , , , , . Bookmark the permalink.

9 Responses to Minimal test case generator tool?

  1. dons00 says:

    Sounds like a special case of QuickCheck’s shrinking — where the random test data are “random” ASTs.

    http://hackage.haskell.org/packages/archive/QuickCheck/2.1.0.1/doc/html/Test-QuickCheck-Arbitrary.html#3

  2. Ganesh Sittampalam says:

    Not sure there’s anything that looks at call graphs, but see e.g. http://delta.tigris.org/ for more general stuff in this area.

  3. Jared says:

    Another interesting tool would be one that creates minimal test cases, but not necessarily trimming the code, but simplifying the test input. This would probably be harder than trimming the call graph since it would require domain knowledge of the test cases. Is it possible to have a test case generator (like QuickCheck) or use Generics to create test cases that can be automatically reduced?

  4. Max Bolingbroke says:

    LLVM has the bugpoint utility for reducing test cases that exhibit errors in IR transformations or code generation. It’s meant to be amazingly effective.

  5. This idea reminds me of SmallCheck (Runciman, Naylor, and Lindblad, Haskell 2008). But in your case, if it is easy to *check* whether any given program is a test case that exhibits the error, then perhaps it is practical to just try deleting each substring of the initial test case (which takes quadratic time) repeatedly (which takes cubic time)?

  6. Joe Schmoe says:

    Sounds like delta debugging, see http://www.st.cs.uni-saarland.de/dd/

  7. Steven Grady says:

    The original version of QuickCheck, for Erlang, was written by John Hughes. He founded QuviQ (http://quviq.com/) to sell the Erlang QuickCheck, which does simplification on the test input.

  8. Echo Nolan says:

    IIUC, QuickCheck-2 already does what Jared said. Look at the documentation for the Arbitrary class. There is a shrink function that returns a list of “smaller” versions of a value. It checks if any of the shrinks also fail the test and iterates to a fixed point.

    Of course, you don’t get this for free with generics, but Arbitrary instances are pretty easy to write.

  9. Jean-Marie Gaillourdet says:

    In the case of a single threaded programm, it should be possible to use coverage tools. If your program terminates abruptly at the error, but coverage information is still written, the the code coverage tells you exactly which code was executed and which not. Just a simple idea.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s