Delta: the coolest tool you’ve never heard of

One of the challenges that any developer faces is finding a small test case that reproduces a defect reported by users. That’s often easier said than done: when the defect originally shows up during parsing of a makefile consisting of 20,000 lines of nested calls to $(eval), separating the interesting lines from the irrelevant lines can seem like an exercise in futility. Thankfully, you don’t have to do it alone. Some clever guys at UC Berkeley wrote a tool called delta to assist with just this problem. In this post I’ll show you how you can use delta to distill useful test cases out of otherwise intractable inputs. The example involves makefiles of course, but the tool and the techniques are useful to developers and QA engineers in all fields.

What does delta do?

Delta isolates the interesting portions of an input file by iteratively partitioning the input, then testing each partition to see if it produces the behavior you want. If any partition does, the other partitions can be discarded. After numerous rounds of this, the uninteresting chaff is eliminated and you are left with an input file containing only those parts of the original that are really necessary. Conceptually it’s like doing a binary search on the input, although it’s more clever than that because it handles the case where the interesting lines are not strictly contiguous in the input.

Using delta to minimize test cases

Let me walk you through a small example. This makefile (right-click, “Save As…” — although it has a .doc extension it’s really just plain text) exhibits different behavior when run with gmake 3.80 and 3.81. I would like to know specifically what parts of the makefile are relevant to demonstrating the difference. Sure, I could do this by hand, but I’m a busy guy, and I really believe that anything the computer can do for me, it should do for me. The first step is to characterize the difference. The output with gmake 3.80 looks like this:

Compare that to the output when using gmake 3.81:

I’ve highlighted the difference to make it easier to see: the flags used to build the target have changed.

The next step is to write a shell script that will tell delta if a given permutation of the makefile produces the behavior we want or not. Technically you could use any kind of program you want here as long as it adheres to delta’s convention of returning zero if the input is “interesting” and non-zero otherwise; shell scripts are just an easy way to do it. Here’s the script I wrote for this example:

The script runs gmake 3.80 and gmake 3.81, checking the output of each to verify that the flags are printed and that they have the expected values. I named the script check.sh and made it executable with chmod, then ran it once to ensure it does in fact return zero as expected:

If you haven’t already, download delta (.tar.gz) and unpack it. Delta itself is a Perl script, so make sure you have Perl installed. Now we’re ready to go.

Delta will modify the input file in place, so make sure to save a backup copy first, and then run delta, telling it the name of the check script and the input file to minimize:

This will produce a boatload of output like this:

Generally you can ignore this output, but it’s worth looking at once just to get a better understanding of what delta is doing. The output log tells you the partitions that delta tries, expressed as ranges of lines from the original input. The first test is on the full input, [0,1851]; next delta splits the file in two and tries each half, [0,925] and [925,1851]. You can see sometimes these partitions result in a completely broken makefile — syntax errors, missing rules, etc. Delta doesn’t care — all it needs to know is whether or not the partition is “interesting” according to our check.sh script. Looking further on in the output, you can see how the test makefile gets smaller and smaller as delta discovers ranges of the original input that are relevant. Eventually it ends up with trials like [3,7][93,96][198,202][533,540][1549,1557][1760,1767][1843,1847], indicating that it has constructed a makefile from lines 3-7, 93-96, 198-202, etc, of the original input. Finally delta hits a point where it cannot reduce the input any further — if it removes anything more, the resulting makefile is no longer interesting:

On my laptop, delta takes all of about two seconds to trim the original makefile, consisting of nearly 2,000 lines of text, to a trivial 15 line makefile. Not too shabby.

Depending on your situation, you may find that delta stops too soon. It’s strength is also its weakness: it is not at all domain aware. It doesn’t understand the syntax of makefiles or whatever else you might throw at it, so sometimes it hits a dead end. You may be able to help it along a bit by applying your own domain knowledge to the problem at that point. That is, once delta has had a first crack at the input, take a look at it yourself and see if there are ways you can simplify the input manually. When dealing with makefiles, that could mean doing things like inlining makefile includes, or flattening nested variable definitions. After you tweak the input manually, you can feed it back into delta again for another round.

Delta delta delta, it can help ya help ya help ya

I’ve used delta myself on several occasions to help pull simple test cases out of seemingly intractable makefiles. It’s not perfect, but it’s earned a place in my toolbox. Hopefully you’ll find room for it in yours.

UPDATE: changed URL of the sample Makefile.

Follow me

Eric Melski

Eric Melski was part of the team that founded Electric Cloud and is now Chief Architect. Before Electric Cloud, he was a Software Engineer at Scriptics, Inc. and Interwoven. He holds a BS in Computer Science from the University of Wisconsin. Eric also writes about software development at http://blog.melski.net/.
Follow me

Share this:

2 responses to “Delta: the coolest tool you’ve never heard of”

  1. iresha says:

    This is a pretty awesome tool. Now to try it out :)

  2. WinWin says:

    hola
    i’m so happy that i found this website. that topic was so insightful. thanks again i added the rss on this site.
    are you planning to write similar posts?

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe

Subscribe via RSS
Click here to subscribe to the Electric Cloud Blog via RSS

Subscribe to Blog via Email
Enter your email address to subscribe to this blog and receive notifications of new posts by email.