HTTPS SSH

Redux

Summary

Redux is a set of tools inspired by Delta to help applying the idea of delta debugging to Python programs. The main use case is reduction of test cases when reproducing bugs to assist reporting issues with the simplest steps to reproduce.

Status

This is an early version, which has some limitations:

  • Works only on 1 file at the moment
  • The refactoring options are limited, for example no re-structuring of classes and functions
  • There are known limitations in some of the filters, usually listed with a TODO tag
  • There are probably a lot of cases that redux doesn't handle, if you find issues, please open a ticket in the issue tracker with an example.

How does it work?

The reduction process happens in different steps

  1. The target code is run through a tracer to collect coverage data and identify the failure.
  2. A number of "safe" modifications are made to the code to simplify it with no change to its behaviour
  3. The code is analysed for hypotheses about things that are likely not related to the bug
  4. Each hypothese is tested individually by modifying the code, with 2 possible outcomes: - The failure is still present, the hypothese was right, the change to the code is kept - The failure disappeared, the hypothese was wrong as the change affected the failure, the change is discarded

Steps 3 and 4 are repeated until no more valid hypotheses can be found, at which point the resulting code is the minimal test case to reproduce the failure that redux can find.

Running the code

The target file is compiled to a Python abstract syntax tree (ast) then run with exec (See run in redux/utils.py). You can specify a function to be called when running the code as well, see below for examples. The ast of the ast is then used as the representation of the code through steps 2 to 4 as implementing modification to asts is easy.

Failure detection

A failure is assumed to be an exception raised by the code you're testing. As the hypotheses modify the code, they might introduce other failures than the one the code is trying to reproduce, so it's important to identify the right failure. You can specify a detector to compare exceptions raised during execution of the code to the one expected to be raised, to make sure the failure is still present.

At the moment 2 types of detectors are supported (see redux/detectors.py):

  • A detector that verifies the class of the raised exception. Use this one if the exception raised is specific enough so false positive are not likely.
  • A detector that matches the error message of raised exception, you can use it to have more control over what is matched if your exception is common

You can also explicitely raise a SentinelException (in redux/exc.py) if your failure isn't an exception, or if it's too common, for example AssertException.

Tracing

The tracer (See redux/tracer.py) is used to collect information about the code as it runs:

  • Line coverage
  • Return values of function calls

This information is then used to come up with hypotheses (See list_hypotheses in redux/__init__.py).

It is implemented by setting a tracing function using sys.settrace, like other code coverage tools.

Filters

Filters are subclasses of ast.NodeTransformer that can identify patterns of code and modify them. A BaseFilter is provided with to provide some helpers for subclasses, but any class compatible with NodeTransformer can be used. Hypotheses are implemented by filters. For example the hypothese "The function log_error doesn't affect the failure" will be tested by running a filter RemoveFunctionCall on each node calling log_error and verifying that the failure still exists.

Existing filters

The available filters are in redux/filters.py.

Some of them are safe to apply (they shouldn't affect the failure), for example:

  • RemoveUnusedDeclarations will remove class and function declaration that are not used.
  • RemoveUnusedLines will remove lines that are not used by the test, for example branches of if blocks or the body of unused functions.
  • SimplifyFormats will remove uninteresting parts of print statements

Some are more destructive

  • RemoveFunctionCall will remove a given function call completely.
  • RemoveAsserts will remove all assert statements

The first type of filters are general simplification/cleanup filters and are run during step 3 without re-running the code in between.

Adding new filters

Detecting a pattern

Each filter implements a method check which returns True if the given node is a candidate for modification. BaseFilter provides a simple check on the current node class against a white list.

Modifying the node

If a node passes the check, the apply method of the filter is called, and its return value will be used to modify the node or not. BaseFilter will run generic_visit on the children of the node before calling apply on the node itself, if you do not want that, re-implement visit in your filter.

Removing a node

Sometimes a node can't be removed directly, as its deletion could affect other filters being run.

For example

def fn1():
    pass

(a, b) = fn1(), fn1()

In that case fn1 is called twice. If we suspect that fn1 is irrelevant to the failure, we could run the following 2 filters:

  • RemoveFunctionCall("test.py", 4, "fn1", 0)
  • RemoveFunctionCall("test.py", 4, "fn1", 1)

to remove each call separately (0 and 1 are the index of list of calls to fn1 on line 4). If the first filter removed the node completely, the resulting code would become

def fn1():
    pass

(a, b) = (fn1(), )

and the second filter would be looking for the second call to fn1 on line 4 (index 1) but wouldn't find it as there is only one call now.

To avoid this issue, a new node type Deleted is introduced to maintain the structure of the code in a run of filters. It is then removed in step 3 by RemoveDeleted.

Examples

The reduxrun.py is a command line tool that runs the reduction steps on a given filename. You can specify how to detect the failure and if a function needs to be called in the script.

$ python reduxrun.py --help
Usage: reduxrun.py [options] file

Options:
  -h, --help            show this help message and exit
  -f FUNCTION, --function=FUNCTION
                        function to call to trigger the bug
  -e EXCEPTION, --exception=EXCEPTION
                        name of the exception raised by the bug
  -m MESSAGE, --message=MESSAGE
                        message of the exception raised by the bug

The examples below assume that all dependencies are installed properly (see requirements.txt). You can setup a virtualenv for that:

$ virtualenv venv
$ source venv/bin/activate
$ pip install -r requirements

Using a function call and exception match on message

$ python reduxrun.py --function "trigger" --message ".* zero" redux/test/data/source3.py
import sys
sys.path.insert(0, 'redux/test/data')

def fn2(x):
    return (x / 0)

def trigger():
    fn2(1)

Same but with exception match on name

$ python reduxrun.py --function "trigger" --exception ZeroDivisionError redux/test/data/source3.py
import sys
sys.path.insert(0, 'redux/test/data')

def fn2(x):
    return (x / 0)

def trigger():
    fn2(1)

Same script without function call

The failure in this example script only happens when calling the trigger function.

$ python reduxrun.py --exception ZeroDivisionError redux/test/data/source3.py
Error: The code didn't fail as expected
Error: Could not verify the failure, make sure the code raises SentinelException or uses the right failure detector

This doesn't work as the script didn't raise a ZeroDivisionError or a SentinelException

Example with SentinelException

$ python reduxrun.py --function redux_start redux/test/data/source1.py
import sys
sys.path.insert(0, 'redux/test/data')
from redux.exc import SentinelException
from source1module.a import function3

def buggy_func(a):
    raise NotImplementedError()

def redux_start():
    try:
        buggy_func(1)
    except NotImplementedError:
        raise SentinelException()

You can compare the output to the original code in redux/test/data/source1.py.

Testing

Most of the code is tested under redux/test. Most of the tests consist of running the filters against some code and checking the output for errors.

You can run all the tests with regular test runners, and you can also use make run_tests to run the tests with nose and see coverage stats.

Reading list and related tools

Articles

Tools