Learn more

• About the Book
• About the Author
• Contents
• Reviews

Project 3: Cause-Effect Chains

Your Task

Step 1: Obtain states.

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.

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.

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.

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.

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

• 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 and Project 2. 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.

References

• Chapter 14 in the book
• Zeller, Isolating Cause-Effect Chains from Computer Programs (FSE 2002)
• Cleve and Zeller, Locating Causes of Program Failures (ICSE 2005)

Get the book at Amazon.com · Amazon.de
Comments? Write to Andreas Zeller <zeller@whyprogramsfail.com>.