[an error occurred while processing this directive]

Automated Debugging and Testing: Exercises

Andreas Zeller, Bertrand Meyer, summer semester 2007

General info: Back to main course page | Exercise 1 | Exercise 2

Exercise 1: Simplifying Input

In this project, you write a simple tool that simplifies failure-inducing input.
  • Submission date: 22.06.2007
Please submit your solution via email to andreas-abgabe@inf.ethz.ch. Questions can be answered by email (andreas-uebung@inf.ethz.ch), directly in/before/after the course or you just drop by my office (RZ J4).

The failure

XMLProc is a small XML parser written in Python. It has a small defect. To exhibit the defect, follow these steps:
  1. Download the XMLProc parser. It should unpack into a directory called xmlproc.
  2. In the xmlproc dictionary, the file xpcmd.py is a command-line interface to the XML parser. To have the parser parse the XML file demo/nstest1.xml, type
    $ cd xmlproc
    $ python xpcmd.py demo/nstest1.xml
    xmlproc version 0.70
    Parsing 'demo/nstest1.xml'
    Parse complete, 0 error(s) and 0 warning(s)
    $ _
  3. The input file demo/urls.xml causes the parser to fail:
    $ python xpcmd.py demo/urls.xml
    xmlproc version 0.70
    Traceback (most recent call last):
      File "xpcmd.py", line 112, in ?
        p.parse_resource(sysid) [...]
      File "xmlproc/xml/parsers/xmlproc/xmlproc.py", line 401, in parse_charref
        if digs==None: return
    UnboundLocalError: local variable 'digs' referenced before assignment
    $ _

Your task

Use Delta Debugging to simplify the failure-inducing input. Proceed in the following steps:

Step 1: Download ddmin

Download DD.zip, which contains a simple implementation of ddmin. Unzip the package to a directory of your choice and have a look at the various files.

Step 2: Write a testing function.

To invoke the parser, you have two options:
  • Invoke the parser as a separate program. Use Python's os module to execute the parser. You can use fork(), execv(), and wait() functions; however, for this particular task, system() or popen() are far easier to use. Python's built-in File Objects are useful in communicating with the parser via files.
  • Invoke the parser directly from Python. Take a look at the xpcmd.py source to see how this works. The essential lines are
    from xml.parsers.xmlproc import xmlproc
    app = xmlproc.Application()
    p = xmlproc.XMLProcessor()
    In order to catch the exception thrown by the parser, be sure to read and understand exception handling in Python.
Take care to differentiate three outcomes:
  • The parser completely parses the file (PASS), without errors or warnings;
  • The parser fails as in the original failure (FAIL)
  • The parser has another outcome, in particular syntax errors (UNRESOLVED)

Step 3: Write a splitting function.

Adapt the file split.py (contained in DD.zip) to fit your needs.

Step 4: Choose a representation.

How do you represent the configuration that is to be minimized?
  • If you want to simplify input, each delta might be a single character—thus, the string "defect" becomes the list ['d', 'e', 'f', 'e', 'c', 't']. However, this will cause trouble as you cannot distinguish between the same character at different locations. For instance, listminus(['d', 'e', 'f', 'e', 'c', 't'], ['e']) = ['d', 'f', 'c', 't']—which is not what you want.
  • A better solution is to store characters with their indices, as in [('d', 1), ('e', 2), ('f', 3), ('e', 4), ('c', 5), ('t', 6)]—this way, each circumstance can be uniquely identified.
  • For a more general solution, you may wish to set up Circumstance or Delta classes and to store lists of these objects.

Step 5: Run it.

What is the simplified failure-inducing input in demo/urls.xml? Record the number of tests that Delta Debugging takes.

Exercise 2: Cause-Effect Chains

In this project, you write a tool that isolates failure-inducing program states.
  • Submission date: 01.09.2007 05.09.2007
Please submit your solution via email to ilinca-abgabe@inf.ethz.ch. Questions can be answered by email (ilinca-uebung@inf.ethz.ch), directly in/before/after the course or you just drop by my office (RZ J4).

Your Task

Extract and compare program states to isolate failure causes. Proceed in five steps:

Step 1: Obtain states.

In Python, you can access the program state from within a program run using a trace function. The Python method sys.settrace(func) sets the global trace function to func; it is invoked whenever a new function is entered. func can return a local trace function which is then invoked for every line of the current function. Here's a full description of sys.settrace().

From within a trace function, you can access all variables of the current frame; you can also access the frames of the calling functions. See internal types for a discussion of frame objects.

  1. Start by extending an existing program (such as middle) with a tracing function. Have your tracing function first report the called functions; then extend it to report the local and global variables. See the lecture slides on isolating cause-effect chains for an example.
  2. Set up the tracing function such that it operates only at given locations (say, a list of function names).
  3. Create a State class in which you create a copy of the current state. (You may also want to create your own Backtrace and Frame classes, such that each State contains a Backtrace as a list of Frame objects.)

    Copying state is tricky. Here are some hints:

    • You need to care about aliasing. If variables a and b reference the same object, this should also be reflected in your State object. (If needed, you can use the Python built-in id() function to access the "identity" of an object.)
    • An important limitation of Python is that you cannot make "deep" copies of the entire state, since modules cannot be copied. Also, you cannot access the internal state of modules, so if there is any difference in here, you won't be able to detect or isolate it.
    • The Python copy.copy() method handles all of this nicely. It creates a shallow copy—that is, it copies the top-level structure (that is, the mapping of global and local variables), while preserving aliases at the deeper levels.
    • A good solution is to copy as much as you can—that is:
      • to copy recursively the entire state,
      • if an exception occurs, catch that exception, and share the object rather than copying it.
  4. Allow the state to be output in human-readable form (for debugging).

Step 2: Compare states.

For simplicity, we shall only compare state per base variables—that is, we do not (yet) examine the contents of data structures.
  1. Create a class StateDelta that holds the difference between two program states, expressed as a set of Delta objects.
  2. Each Delta object represents a difference of two values of one single (named) variable. Essentially, a Delta will consist of
    • The name of the variable
    • Its stack depth (frames of different functions can have different variables with the same name)
    • Its value (as a copy of the original value)
  3. When designing your Delta class, note that in Python, the set of local variables at a frame may be different, even though the backtrace is the same. For instance, in the Python code
    if debug:
       x = 1
    the variable x is defined only if debug is set. Comparing two runs with different settings of debug results in different sets of local variables.
  4. If two values reference the same object (such as a module), you need not look further for any differences. Use the Python built-in id() function to access the "identity" of an object.
  5. Set up a constructor for StateDelta that takes two State objects and creates appropriate deltas—one for each differing base variable. (Hint: to compare variables, use the Python built-in cmp() function.)
  6. Allow state differences to be output in human-readable form (for debugging).
  7. For each of the two test programs (see below), determine and output state differences between runs.

Step 3: Apply and isolate differences.

In this step, we use delta debugging to isolate failure-inducing state:
  1. Extend the Delta class by an apply(frame) method that applies a delta to the stack of frames starting with frame. This is essentially done by finding the stack frame at the depth as specified in the delta, and to assign the variable the value as stored in the delta.
  2. If you change a variable on the stack, only changes to the top-level frame are actually copied back to the Python interpreter. Therefore, you may need to defer application of deltas until the respective frame is top-level again.
  3. Check that transferring state works. For each of the two test programs (see below), the challenge is to apply an entire StateDelta such that you effectively transform one test run into another.

    This is the trickiest part of the project. If you are stuck somewhere during this process, drop me a note and we will try to resolve the problem together.

  4. Apply delta debugging on state deltas, thus isolating failure-inducing program states at given locations. Use the dd() algorithm to isolate individual states—for instance, by extending your module from Project 1.

    Once you are able to apply all deltas such that the failure occurs, using delta debugging is pretty straight-forward.

Step 4: Generalize.

Finally, we clean up the code and generalize it:
  1. Generalize your approach to a stand-alone function (say, debug()) that takes as arguments
    • a unit test which fails (see the unittest framework for details)
    • a unit test which passes
    • a list of locations covered by both unit cases at which to isolate failure-inducing states.
  2. Be sure to have docstrings for every function which describe its purpose. Have a README file (or other appropriate help) that describes how to invoke the isolation tool.

Step 5 (optional): Implement an advanced method.

Implement one of the following extensions to isolating cause-effect chains:
  1. Make your deltas more fine-grained. Do not compare data structures and mappings as a whole, but identify single elements that can be added, deleted, or changed. In particular, think of
    • tuples such as (1, 2, 3)
    • lists such as [1, 2, 3]
    • mappings such as {1: 'one', 2: 'two', 3: 'three'}
    • objects such as State with their attributes
    This also calls for a more elaborated Delta class—rather than changing the value of a base variable, applying a Delta now means to change individual values in a data structure. Consider introducing Delta subclasses such as ListDelta, TupleDelta, etc., that handle specific data types. (To simplify things, you do not need to care about aliasing of elements.)
    • To check the type of a value, use the Python isinstance() function.
    • To access individual attributes, use the Python built-in dir() and getattr() functions.
  2. Implement automatic identification of cause transitions—that is, moments in time at which the set of relevant variables change. For a full description of the algorithm, see the paper of Cleve and Zeller: Locating Causes of Program Failures (ICSE 2005). It suffices to narrow down a cause transition to a specific function which occurs in both traces; there is no need to isolate single statements.

Test cases

Demonstrate your techniques on two programs:
  • The middle program and its test runs as described in the book. You need to create appropriate unit tests for this example.
  • The XMLProc parser from Project 1. The XMLdata archive contains a number of passing and failing test inputs. For each of the three failing test inputs, isolate a cause-effect chain that lead to the error or warning message. You need to set up unit test that check the messages issued by the XMLProc parser.