Generalizing Failure Circumstances¶

One central question in debugging is: Does this bug occur in other situations, too? In this chapter, we present a technique that is set to generalize the circumstances under which a failure occurs. The DDSET algorithm takes a failure-inducing input, breaks it into individual elements. For each element, it tries to find whether it can be replaced by others in the same category, and if so, it generalizes the concrete element to the very category. The result is a pattern that characterizes the failure condition: "The failure occurs for all inputs of the form (<expr> * <expr>)".

Prerequisites

• You should have read the chapter on delta debugging.

A Failing Program¶

As with previous chapters, we use remove_html_markup() as our ongoing example. This function is set to remove HTML markup tags (like <em>) from a given string s, returning the plain text only. We use the version from the chapter on asssertions, using an assertion as postcondition checker.

For the most inputs, remove_html_markup() works just as expected:

There are inputs, however, for which it fails:

In contrast to the other chapters, our aim now is not to immediately go and debug remove_html_markup(). Instead, we focus on another important question:

Under which conditions precisely does remove_html_markup() fail?

This question can be generalized to

What is the set of inputs for which remove_html_markup() fails?

Our plan for this is to generalize concrete inputs (such as BAD_INPUTS) into an abstract failure-inducing inputs. These are patterns formed from a concrete input, but in which specific placeholders indicate sets of inputs that are permitted. In the abstract failure-inducing input

<opening-tag>"bar<closing-tag>

for instance, <opening-tag> and <closing-tag> are placeholders for opening and closing HTML tags, respectively. The pattern indicates that any opening HTML tag and closing HTML tag can be present in the input, as long as the enclosed text reads "bar.

Given a concrete failure-inducing input, our aim is to generalize it as much as possible to such an abstract failure-inducing input. The resulting pattern should then

• capture the circumstances under which the program fails;
• allow for test generation by instantiating the placeholders;
• help ensuring our fix is as general as possible.

Grammars¶

To determine abstract failure-inducing inputs, we need means to determine and characterize sets of inputs – known in computer science as languages. To formally describe languages, the field of formal languages has devised a number of language specifications that describe a language. Regular expressions represent the simplest class of these languages to denote sets of strings: The regular expression [a-z]*, for instance, denotes a (possibly empty) sequence of lowercase letters. Automata theory connects these languages to automata that accept these inputs; finite state machines, for instance, can be used to specify the language of regular expressions.

Regular expressions are great for not-too-complex input formats, and the associated finite state machines have many properties that make them great for reasoning. To specify more complex inputs, though, they quickly encounter limitations. At the other end of the language spectrum, we have universal grammars that denote the language accepted by Turing machines. A Turing machine can compute anything that can be computed; and with Python being Turing-complete, this means that we can also use a Python program $p$ to specify or even enumerate legal inputs. But then, computer science theory also tells us that each such program has to be written specifically for the input to be considered, which is not the level of automation we want.

The middle ground between regular expressions and Turing machines is covered by grammars. Grammars are among the most popular (and best understood) formalisms to formally specify input languages. Using a grammar, one can express a wide range of the properties of an input language. Grammars are particularly great for expressing the syntactical structure of an input, and are the formalism of choice to express nested or recursive inputs. The grammars we use are so-called context-free grammars, one of the easiest and most popular grammar formalisms.

A grammar is defined as a mapping of nonterminal symbols (denoted in <angle brackets>) to lists of alternative expansions, which are strings containing terminal symbols and possibly more nonterminal symbols. To make the writing of grammars as simple as possible, we adopt the fuzzingbook format that is based on strings and lists.

Fuzzingbook grammars take the format of a mapping between symbol names and expansions, where expansions are lists of alternatives.

A one-rule grammar for digits thus takes the form

which means that the <start> symbol can be expanded into any of the digits listed.

A full grammar for arithmetic expressions looks like this:

From such a grammar, one can easily generate inputs that conform to the grammar.

Nonterminals as found in the grammar make natural placeholders in abstract failure-inducing inputs. If we know, for instance, that it is not just the concrete failure-inducing input

(2 * 3)

but the abstract failure-inducing input

(<expr> * <expr>)

that causes the failure, we immediately see that the error is due to the multiplication operator rather than its operands.

Coming back to our remove_html_markup() example, let us create a simple grammar for HTML expressions. A <html> element is either plain text or tagged text.

Plain text is a simple (possibly empty) sequence of letter, digits, punctuation, and whitespace. (Note how <plain-text> is either empty or some character followed by more plain text.) The characters < and > are not allowed, though.

Tagged text is a bit more complicated. We have opening tags <foo>, followed by some more HTML material, and then closed by a closing tag </foo>. (We do not insist that the two tags match.) A self-closing tag has the form <br/>. For compatibility reasons, we also allow just opening tags without closing tags, as in <img>.

Since the characters < and > are already reserved for denoting nonterminal symbols, we use the special nonterminal symbols <lt> and <gt> that expand into < and >, respectively,

Finally, HTML tags can have attributes, which are enclosed in quotes.

Again, we can generate inputs from the grammar.

Such inputs, of course, are great for systematic testing. Our sister book, the fuzzing book, covers these and more.

Derivation Trees¶

To produce inputs from a grammar, the fuzzingbook GrammarFuzzer makes use of a structure called a derivation tree (also known as syntax tree). A derivation tree encodes the individual expansion steps undertaken while producing the output.

Let us illustrate derivation trees by example, using the last HTML output we produced.

The GrammarFuzzer attribute derivation_tree holds the last tree used to produce this input. We can visualize the tree as follows:

From top to bottom, we see that the input was constructed from a <start> symbol, which then expanded into html, which then expanded into HTML text, and so on. Multiple children in a tree stand for a concatenation of individual symbols.

Internally, these trees come as pairs (symbol, children), where symbol is the name of a node (say, <html>), and children is a (possibly empty) list of subtrees. Here are the topmost nodes of the above tree:

To produce abstract failure-inducing patterns, we will work on this very structure. The idea is to

1. systematically replace subtrees by other, generated, compatible subtrees (e.g. replace one <html> subtree in the concrete input by some other generated <html> subtree);
2. see whether these subtrees also result in failures; and
3. if they do, use the nonterminal (<html>) as a placeholder in the pattern.

This will involve some subtree manipulation, construction, and finally testing. First, though, we need to be able to turn an existing input into a derivation tree.

Parsing¶

The activity of creating a structure out of an unstructured input is called parsing. Generally speaking, a parser uses a grammar to create a derivation tree (also called parse tree in parsing contexts) from a string input.

Again, there's a whole body of theory (and practice!) around constructing parsers. We make our life simple by using an existing parser (again, from the fuzzing book), which does just what we want. The EarleyParser is instantiated with a grammar such as SIMPLE_HTML_GRAMMAR:

Its method parse() returns an iterator over multiple possible derivation trees. (There can be multiple trees because the grammar could be ambiguous). We are only interested in the first such tree. Let us parse BAD_INPUT and inspect the resulting ~parse tree~ ~syntax tree~ derivation tree:

This derivation tree has the same structure as the one created from our GrammarFuzzer above. We see how the <tagged-text> is composed of three elements:

1. an<opening-tag> (<foo>);
2. a <html> element which becomes <plain-text> ("bar); and
3. a <closing-tag> (</foo>).

We can easily turn the tree back into a string. The method tree_to_string() traverses the tree left-to-right and joins all nonterminal symbols.

With this, we can now

• parse an input into a tree structure;
• (re-)create parts of the tree structure; and
• turn the tree back into an input string.

Mutating the Tree¶

We introduce a class TreeMutator that is set to mutate a tree. Its constructor takes a grammar and a tree.

Referencing Subtrees¶

To reference individual elements in the tree, we introduce the concept of a path. A path is a list of numbers indicating the children (starting with 0) we should follow. A path [0, 0, 0, ..., 0] stands for the leftmost child in a tree.

The method get_subtree() returns the subtree for a given path.

Here's get_subtree() in action. We instantiate a TreeMutator on the BAD_INPUT tree as shown above and return the element at the path [0, 0, 1, 0] – i.e. follow the leftmost edge twice, than the second-to-leftmost edge, then the leftmost edge again. This gives us the <plain-text> subtree representing the string "bar:

Creating new Subtrees¶

The method new_tree() creates a new subtree for the given <start_symbol> according to the rules of the grammar. It invokes expand_tree() on the given GrammarFuzzer – a method that takes an initial (empty) tree and expands it until no more expansions are left.

Here is an example of new_tree():

Mutating the Tree¶

With us now being able to

• access a particular path in the tree (get_subtree()) and
• create a new subtree (new_tree()),

we can mutate the tree at a given path. This is the task of mutate().

Here is an example of mutate() in action. We mutate bad_input_tree at the path [0, 0, 1, 0] – that is, <plain-text>:

We see that the <plain-text> subtree is now different, which also becomes evident in the string representation.

Generalizing Trees¶

Now for the main part – finding out which parts of a tree can be generalized. Our idea is to test a finite number of mutations to a subtree (say, 10). If all of these tests fail as well, then we assume we can generalize the subtree to a placeholder.

We introduce a class TreeGeneralizer for this purpose. On top of grammar and tree already used for the TreeMutator constructor, the TreeGeneralizer also takes a test function.

The test function is used in test_tree(), returning False if the test fails (raising an exception), and True if the test passes (no exception).

Testing for Generalization¶

The can_generalize() method brings the above methods together. It creates a number of tree mutations at the given path, and returns True if all of them produce a failure. (Note that this is not as sophisticated as our delta debugger implementation, which also checks that the same error occurs.)

Let us put TreeGeneralizer into action. We can directly use remove_html_markup() as test function.

On our BAD_INPUT (and its tree), can we generalize the root <html> node? In other words, does the failure occur for all possible <html> inputs?

The answer is no. The first alternative passes the test; hence no generalization.

How about the middle <plain_text> part? Can we generalize this?

The answer is no – just as above.

How about the closing tag? Can we generalize this one?

Yes, we can! All alternate instantiations of <closing-tag> result in a failure.

Note that the above does not hold for <opening-tag>. If the attribute value contains a quote character, it will extend to the end of the input. This is another error, but not caught by our assertion; hence, the input will be flagged as passing:

The effect of this is that there are patterns for <opening-tag> which do not cause the failure to occur; hence, <opening-tag> is not a fully valid generalization.

This, however, becomes apparent only if one of our generated tests includes a quote character in the attribute value. Since quote characters are as likely (or as unlikely) to appear as other characters, this effect may not become apparent in our default 10 tests:

It will become apparent, however, as we increase the number of tests:

We see that our approach may overgeneralize – producing a generalization that may be too lenient. In practice, this is not too much of a problem, as we would be interested in characterizing cases that trigger the failure, rather than characterizing a small subset that does not trigger the failure.

Generalizable Paths¶

Using can_generalize(), we can devise a method generalizable_paths() that returns all paths in the tree that can be generalized.

Here is generalizable_paths() in action. We obtain all (paths to) subtrees that can be generalized:

To convert these subtrees into abstract failure-inducing patterns, the method generalize_path() returns a copy of the tree with the subtree replaced by a nonterminal without children:

The function all_terminals() expands these placeholders:

Finally, the method generalize() obtains a tree in which all generalizable paths actually are generalized:

This gives us the final generalization of BAD_INPUT. In the abstract failure-inducing input, all generalizable elements are generalized.

We see that to obtain the failure, it suffices to have an <opening-tag>, followed by a quote and (any) <plain-text> and (any) <closing-tag>. Clearly, all that it takes to produce the failure is to have a double quote in the plain text.

Also note how this diagnosis was reached through experiments only – just as with delta debugging, we could treat the program under test as a black box. In contrast to delta debugging, however, we obtain an abstraction that generalizes the circumstances under which a given failure occurs.

Fuzzing with Patterns¶

One neat side effect of abstract failure-inducing patterns is that they can be easily instantiated into further test cases, all set to reproduce the failure in question. This gives us a test suite we can later test our fix against.

The method fuzz_tree() takes a tree representing an abstract failure-inducing input and instantiates all missing subtrees.

We can take these inputs and see whether they reproduce the failure in question:

We get an overall failure rate of ~98%, which is not bad at all.

In our case, it is overgeneralization (as discussed above) that is responsible for not reaching a 100% rate. (In all generality, we are trying to approximate the behavior of a Turing machine with a context free grammar, which is, well, always an approximation.) However, even a lower rate would still be useful, as any additional test case that reproduces a failure helps in ensuring the final fix is complete.

Putting it all Together¶

Let us now put together all this in a more convenient package that does not require the user to parse and unparse derivation trees.

Our DDSetDebugger is modeled after the DeltaDebugger from the chapter on delta debugging. It is to be used as

with DDSetDebugger(grammar) as dd:
    some_failing_function(...)

After that, evaluating dd yields a generalized abstract failure-inducing input as a string.

Since DDSetDebugger accepts only one grammar, the function to be debugged should have exactly one string argument (besides other arguments); this string must fit the grammar.

Constructor¶

The constructor puts together the various components. It allows for customization by subclassing.

Generalizing Arguments¶

The method generalize() is the main entry point. For all string arguments collected in the first function call, it generalizes the arguments and returns an abstract failure-inducing string.

Here is an example of how DDSetDebugger would be used on our BAD_INPUT example. Simply evaluating the debugger yields a call with a generalized input.

Fuzzing¶

The fuzz() method produces instantiations of the abstract failure-inducing pattern.

Here are some axamples of fuzz() in action:

These can be fed into eval(), set to produce more failing calls.

More Examples¶

Let us apply DDSetDebugger on more examples.

Square Root¶

Our first example is the square_root() function from the chapter on assertions.

The square_root() function fails on a value of -1:

We define a grammar for its arguments:

The test function takes a string and converts it into an integer:

With this, we can go and see whether we can generalize a failing input:

Success! Using DDSetDebugger, we have nicely generalized the failure-inducing input to a pattern -<positive-int> that translates into "any negative number".

Middle¶

The middle() function from the chapter on statistical debugging returns the middle of three numerical values x, y, and z.

We set up a test function that evaluates a string – a tuple of three arguments – and then tests middle():

The grammar for the three numbers simply puts three integers together:

Here is an example of middle() failing:

What happens if we debug this with DDSetDebugger? We see that there is no abstraction at the syntax level that could characterize this failure:

So, while there are failures that can be nicely characterized using abstractions of input elements, middle() is not one of them. Which is good, because this means that all our other techniques such as statistical debugging and dynamic invariants still have a use case :-)

Lessons Learned¶

• Generalizing failure-inducing inputs can yield important information for which inputs and under which circumstances a failure occurs.
• Generalizing failure-inducing inputs is most useful if the input can be split into multiple elements, of which only a part are relevant for producing the error.
• As they help in parsing and producing input, grammars can play an important role in testing and debugging.

Next Steps¶

Our next chapter introduces automated repair of programs, building on the fault localization and generalization mechanisms introduced so far.

Background¶

Our DDSetDebugger class implements the DDSET algorithm as introduced by Gopinath et al. in [Gopinath et al, 2020]. A full-fledged implementation of DDSET with plenty of details and experiments is available as a Jupyter Notebook. Our implementation follows the simplified implementation of DDSET, as described by Gopinath.

The potential for determining how input features relate to bugs is not nearly explored yet. The ALHAZEN work by Kampmann et al. [Kampmann et al, 2020] generalizes over DDSET differently, by investigating semantic features of input elements such as their numeric interpretation or length and their correlation with failures. Like DDSET, ALHAZEN also uses a feedback loop to strengthen or refute its hypotheses.

In recent work [Gopinath et al, 2021], Gopinath has extended the concept of DDSET further. His work on evocative expressions introduces a pattern language in which arbitrary DDSET-like patterns can be combined into Boolean formula that even more precisely capture and produce failure circumstances. In particular, evocative expressions can specialize grammars towards Boolean pattern combinations, thus allowing for great flexibility in testing and debugging.

Exercises¶

Exercise 1: Generalization and Specialization¶

Consider the abstract failure-inducing input for BAD_INPUT we determined:

1. How does it change if you increase the number of test runs, using max_tries_for_generalization?
2. What is the success rate of the new pattern?