Using Delta Debugging
A short tutorial

Roadmap

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)

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
    $ _

    $ cat < /dev/null > empty.c)
    $ (ulimit -H -s 256; gcc -c -O empty.c)
    $ _

Step 2: Identify the 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

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
    $ _

Step 4: Write a testing function

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

Step 5: Invoke Delta Debugging

Invoke Delta Debugging to isolate the failure cause.

    # Load deltas from `bug.c'
    deltas = []
    index = 1
    for character in open('bug.c').read():
        deltas.append((index, character))
        index = index + 1

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

    $ 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.
    $ _

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.

Impressum ● Datenschutzerklärung