Using Delta Debugging - Lehrstuhl für Softwaretechnik (Prof. Zeller) (original) (raw)

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

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 thecommands module to invoke GCC and the find function of the string module to check the GCC output. The additionalcoerce 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,

The DD.py module contains lots of additional material:

Andreas Zeller

Impressum ● Datenschutzerklärung

<webmaster@st.cs.uni-saarland.de> · http://www.st.cs.uni-saarland.de//dd/ddusage.php3 · Stand: 2018-04-05 13:40