Using Delta Debugging
A short tutorial

Lehrstuhl für Softwaretechnik (Prof. Zeller)
Universität des Saarlandes – Informatik
Informatik Campus des Saarlandes
Campus E9 1 (CISPA)
66123 Saarbrücken
E-mail: zeller @ cs.uni-saarland.de
Telefon: +49 681 302-70970

Deutschsprachige Startseite Page d'acceuil en franšais English home page
   This tutorial explains how to put Delta Debugging to work. As ongoing example, we use the case study "GCC gets a Fatal Signal" from the paper Simplifying and Isolating Failure-Inducing Input.

Roadmap

The general pattern to put Delta Debugging to work is:
  1. Identify the test case(s)
  2. Identify the deltas.
  3. Set up a Delta Debugging framework.
  4. Write a testing function.
  5. Invoke Delta Debugging.

Step 1: Identify the test case(s)

The first prerequisite to apply Delta Debugging is actually two prerequisites:

You need two test cases - one where the program fails and one where the failure does not occur.

It is helpful if the two test cases are similar - Delta Debugging will run faster and produce better results. However, the passing test case is often some trivial test case - e.g. the empty input.

In the GCC case study, the failing test case is this program named "bug.c". If we compile bug.c using GCC 2.95.2 on Linux with optimization enabled, GCC crashes:

    $ (ulimit -H -s 256; gcc -c -O bug.c)
    gcc: Internal compiler error: program cc1 got fatal signal 11
    $ _
We also know that GCC has no trouble compiling an empty program, say, "empty.c":
    $ cat < /dev/null > empty.c)
    $ (ulimit -H -s 256; gcc -c -O empty.c)
    $ _
That's all we need: we have a failing test case ("bug.c") and a passing test case ("empty.c").

Step 2: Identify the deltas

The next prerequisite is to find a set of deltas:

You must identify the difference between the passing and the failing test case and to decompose this difference into individual deltas.

In general, identifying the difference can require special tools, depending on the application. If you want to determine a difference between text files, for instance, you will need a diff-like algorithm; if you plan to compare tree structures or graph structures, even more sophisticated algorithms may be required. diff and related tools already produce a set of deltas - a number of commands that can be applied to the passing test run (i.e. its input) to produce the failing test run.

That's for the general setting. If the passing test case is the empty input (as in our example), the difference becomes the failing input itself. That is, instead of decomposing the difference into deltas, you can easily decompose the failing input into deltas.

It is helpful if the decomposition follows the structure of the input (e.g. if the input is composed of, say, statements, decompose it into statements). In this tutorial, though, we'll be lazy: We simply decompose the input into characters. That is, we end up in 755 deltas, one for each character in "bug.c".

Step 3: Set up a delta debugging framework

Here's a prerequisite that's rather obvious:

You need the Delta Debugging algorithm.

The MyDD module provides a good starting point. MyDD is written in the Python programming language. But don't worry - typically, it will take you far less time to program in Python than implementing the Delta Debugging algorithm yourself. (Please take a few minutes to browse the Python documentation for a tutorial.)

Besides the MyDD module, you also need the DD module. Download both modules in some directory and change into that directory. If all works well, you should be able to invoke the MyDD module as follows:

    $ python MyDD.py
    Isolating the failure-inducing difference...
    dd: done
    The 1-minimal failure-inducing difference is [1]
    [] passes, [1] fails
    $ _
If something else happens, verify your setup and your python installation.

Step 4: Write a testing function

Now comes the actual programming.

You need a testing function that fails when all deltas are applied and passes when no deltas are applied.

Load the "MyDD.py" file into your favourite text editor and rename it appropriately. Locate a method called "_test": This is the method you have to adapt to your specific needs.

In general, "_test" takes a list of deltas, runs the test with the given deltas and returns

  • self.PASS if the test passes,
  • self.FAIL if it fails, and
  • self.UNRESOLVED, otherwise.

In our case, the deltas are the characters of the GCC input. So, all we have to do is to assemble the passed characters into a file, run GCC on it and check the outcome.

Unfortunately, it's not that easy: The DD.py module sorts the deltas to allow for caching of test results. So, we make each delta a pair (index, character), where index is the position of character in the file. Since characters will now be sorted by index, the characters will always remain ordered.

Finally, we use the getstatusoutput function of the commands module to invoke GCC and the find function of the string module to check the GCC output. The additional coerce method produces the list of deltas in a user-readable form. All this code can be downloaded as the GCCDD.py module,

# New modules
import commands
import string

class MyDD ...
        
    def _test(self, deltas):
        # Build input
        input = ""
        for (index, character) in deltas:
            input = input + character

        # Write input to `input.c'
        out = open('input.c', 'w')
        out.write(input)
        out.close()

        print self.coerce(deltas)

        # Invoke GCC
        (status, output) = commands.getstatusoutput(
            "(ulimit -H -s 256; gcc -c -O input.c) 2>&1")

        print output
        print "Exit code", status

        # Determine outcome
        if status == 0:
            return self.PASS
        elif string.find(output, "fatal signal 11") >= 0:
            return self.FAIL
        return self.UNRESOLVED

    def coerce(self, deltas):
        # Pretty-print the configuration
        input = ""
        for (index, character) in deltas:
            input = input + character
        return input
Here's the full GCCDD.py program.

Step 5: Invoke Delta Debugging

Now comes the final step.

Invoke Delta Debugging to isolate the failure cause.

In our case, we still must load the deltas (from "bug.c") ...
    # Load deltas from `bug.c'
    deltas = []
    index = 1
    for character in open('bug.c').read():
        deltas.append((index, character))
        index = index + 1
... and then invoke Delta Debugging - either "ddmin" for simplifying test cases or "dd" for isolating a failure-inducing difference. Both variants are included in GCCDD.py; we choose the simplifying variant here.
    mydd = MyDD()
    
    print "Simplifying failure-inducing input..."
    c = mydd.ddmin(deltas)              # Invoke DDMIN
    print "The 1-minimal failure-inducing input is", mydd.coerce(c)
    print "Removing any element will make the failure go away."
You can now invoke Delta Debugging - and if all went well, you'll see the following output...
    $ python GCCDD.py
    Simplifying failure-inducing input...
    (Lots of output deleted)
    The 1-minimal failure-inducing input is t(double z[],int n){int i,j;for(;j<n;){i=i+j+1;z[i]=z[i]*(z[0]+0);}}
    Removing any element will make the failure go away.
    $ _
... that is, the minimal input that makes GCC fail. You see that only a fraction of the original input is relevant for producing the failure.

If you need further programming challenges,

  • try to isolate a failure-inducing difference using the dd method (simple - this code is commented out in "GCCDD.py")
  • have delta debugging run on lines instead of characters (much faster; moderate)
  • make delta debugging run on lines first, on characters later (faster + more precise; harder)
  • overload the _split method to influence the splitting and grouping of deltas - for instance, use C syntax rules and split the input after a semicolon (much faster; hard)
  • integrate the whole into your testing environment (moderate)

The DD.py module contains lots of additional material:

  • DD class variables like debug_test to set for debugging and logging,
  • DD methods to overload such as _split to influence the splitting and grouping of deltas, or
  • Older DD variants like old_dd - the first delta debugging algorithm.
That's all, folks - I hope you can now adapt Delta Debugging to your own needs. Have fun exploring, and let me know if you need anything,

Andreas Zeller

<webmaster@st.cs.uni-saarland.de> · http://www.st.cs.uni-saarland.de/dd/ddusage.php3 · Stand: 2017-01-03 21:09