Reducing Failure-Inducing Inputs
Overview
This blog discusses the “Reducing Failure-Inducing Inputs” chapter of The Fuzzing Book. Fuzzers can generate complex inputs that reveal problems in a program, but determining exactly what caused a failure can be difficult. Input reduction helps by removing unnecessary portions of a failing input while keeping the failure reproducible. We will look at why reduction matters, how it can be performed manually, and how grammar-based techniques simplify structured inputs. We will also discuss delta debugging, compare reduction approaches, and introduce a tool that demonstrates these ideas.
Why Reduce Failure-Inducing Inputs?
Finding a bug is only the beginning of the debugging process. A fuzzer may produce a long string containing many characters or operations, even though only a small portion is responsible for the failure. When developers inspect the entire input, the unrelated parts make it harder to identify the cause.
Input reduction is the process of simplifying a failure-inducing input while checking that the reduced input still triggers the failure being investigated. The goal is to produce a smaller and more understandable example that can be used to explain, reproduce, and eventually fix the bug.
For example, the chapter shows a Python expression that raises a division-by-zero error:
x = 1 + 2 * 3 / 0The expression contains several operations, but it can be reduced to:
3 / 0Both examples trigger a ZeroDivisionError. The reduced expression makes the cause of the problem much easier to recognize.
Manual Input Reduction
One way to reduce a failure-inducing input is to remove portions of it by hand and test whether the same failure still occurs. If deleting a section does not remove the failure, that section was not necessary for reproducing the problem. The process can be repeated to make the input progressively smaller.
Consider a hypothetical program that fails whenever ( appears before ) in its input. The program receives the following failing string:
abc123()xyz789A developer might try removing different sections and testing the result:
abc123()xyz789 FAIL
123()xyz FAIL
()xyz FAIL
() FAILIn this example, the final input is enough to reproduce the failure. However, reducing inputs manually becomes time-consuming when there are many possible deletions to test. It is also possible to remove too much and accidentally eliminate the original failure. This motivates automated reduction techniques.
Delta Debugging
Delta debugging automates the trial-and-error process of manual reduction. It divides the input into sections, removes one section at a time, and tests the remaining complement. If the complement still causes the failure, the removed section was not necessary and the reducer keeps the smaller input. If none of the complements fails, the input is divided into more sections and the process continues.
The following pseudocode illustrates the central idea:
def delta_debug(inp):
granularity = 2
while len(inp) >= 2:
chunk_size = max(1, len(inp) // granularity)
reduced = False
for start in range(0, len(inp), chunk_size):
complement = inp[:start] + inp[start + chunk_size:]
if causes_failure(complement):
inp = complement
granularity = max(granularity - 1, 2)
reduced = True
break
if not reduced:
if granularity >= len(inp):
break
granularity = min(granularity * 2, len(inp))
return inpFor example, a reducer might test the following candidates:
abc123()xyz789 FAIL
()xyz789 FAIL
() FAILThe final candidate is smaller but preserves the failure. In practice, a reducer should also distinguish a real failure from a passing input and from an input that is invalid or cannot be executed. Caching previously tested candidates can reduce the number of repeated program executions.
Delta debugging is useful because it does not require knowledge of the input format. Its main limitation is that removing arbitrary sections can create many invalid inputs. Those candidates may be unable to reach the original bug, which can increase the number of tests needed.
Grammar-Based Input Reduction
Delta debugging can remove pieces of an input without knowing how that input is structured. This works well for many strings, but it can become less useful when a program expects a specific syntax. For example, removing a character from a valid arithmetic expression might make the expression invalid before the program reaches the behavior we want to test. Consider the following valid expression: Deleting arbitrary characters could produce: The new expression is syntactically invalid. If the program rejects it for a syntax error, that result might tell us nothing about the original bug. Grammar-based input reduction attempts to avoid this by making changes that follow the rules of the input language. A grammar defines rules for building valid inputs, while a derivation tree represents how a specific input was constructed using those rules. Instead of treating an input as a sequence of unrelated characters, grammar-based reduction works with the tree’s structure. For example, the expression Why Syntax Matters
1 + (2 * 3)1 + (2 *Derivation Trees
2 * 3 can be viewed as a multiplication operation with two number operands. A grammar-based reducer can use the expression’s tree to identify complete components that could be replaced or simplified, rather than deleting individual symbols without regard for their roles.
Simplifying Structured Inputs
Grammar-based reduction simplifies an input by working with its derivation tree rather than removing individual characters. The chapter introduces two approaches: replacing subtrees and using alternative grammar expansions. Both approaches aim to produce smaller inputs that still follow the grammar’s rules. One approach is to replace a larger subtree with a smaller subtree that represents the same grammar symbol. This allows the reducer to remove unnecessary parts of an expression without making it syntactically invalid. For example, the chapter begins with the expression The reducer can simplify the original expression by replacing its larger Another approach discussed in the chapter is simplifying an input using alternative grammar expansions. Instead of replacing a subtree with an existing smaller subtree, the reducer can use another expansion allowed by the grammar to produce a simpler expression. For example, the expression In both approaches, the reduced input must still be tested to determine whether it causes the same failure as the original input. A smaller and syntactically valid input is only useful for debugging if it continues to reproduce the failure being investigated. Why can derivation trees be helpful when reducing structured inputs? Derivation trees describe the grammatical structure of an input. By simplifying complete subtrees or replacing them with valid expansions, a reducer can avoid many malformed candidates that result from deleting arbitrary characters. This helps it focus more of its tests on inputs that the program can actually process.Simplifying by Replacing Subtrees
1 + (2 * 3). The following derivation tree shows how the original expression is organized into grammar symbols such as <expr>, <term>, and <factor>.
1 + (2 * 3). Source: The Fuzzing Book.<expr> subtree with the smaller <expr> subtree representing (2 * 3). This removes the 1 + portion while keeping the expression valid according to the grammar.
(2 * 3). Source: The Fuzzing Book.Simplifying by Alternative Expansions
(2 * 3) could be simplified to (3) by replacing the multiplication with a simpler expression.Click to Expand for the Answer
Comparing Reduction Techniques
The main reduction techniques differ in how much they know about the input:
| Technique | How it works | Advantages | Limitations |
|---|---|---|---|
| Manual reduction | A developer removes sections and reruns the test | Easy to start and inspect | Slow and difficult to repeat for large inputs |
| Delta debugging | Automatically removes chunks and tests their complements | Works without a grammar and applies to many formats | May generate many invalid candidates |
| Grammar-based reduction | Simplifies derivation trees and grammar expansions | Preserves syntactic structure and produces meaningful inputs | Requires a grammar and parser |
Delta debugging is a good general-purpose choice when the input format is unknown or unstructured. Grammar-based reduction is usually better for source code, queries, configuration files, and other structured inputs where syntax is necessary to reach the failure. In either case, the reducer should verify that the final result still reproduces the original failure before it is used as a regression test. The chapter demonstrates this trade-off by generating a long arithmetic expression with a grammar fuzzer and reducing the same input with both strategies: The grammar-based reducer works with the expression’s derivation tree. In the demonstration, it needs only a small number of tests to find a reduced, failure-inducing expression: The text-based delta debugger does not have access to the expression’s structure. It tries many more character-level complements before reaching a failure-inducing result: In the chapter’s example, grammar-based reduction takes about 10 tests, while delta debugging takes about 900. The exact counts depend on the generated input and the runner, but the result illustrates the central trade-off: grammar-aware reduction is more efficient for syntactically complex inputs, while delta debugging requires less setup and applies to inputs without a known grammar.Comparing Strategies on a Long Expression
long_expr_input = GrammarFuzzer(
EXPR_GRAMMAR, min_nonterminals=100
).fuzz()grammar_reducer = GrammarReducer(
eval_mystery, EarleyParser(EXPR_GRAMMAR)
)
grammar_reducer.reduce(long_expr_input)
grammar_reducer.testsdd_reducer = DeltaDebuggingReducer(eval_mystery)
dd_reducer.reduce(long_expr_input)
dd_reducer.tests
Lessons Learned
- Reducing a failing input can make it easier to identify the behavior responsible for a bug.
- A reduction is useful only if the relevant failure can still be reproduced.
- Manual reduction is possible, but repeated testing can make it slow for large inputs.
- Grammar-based reduction uses the structure of inputs to avoid many syntactically invalid candidates.
- Different reduction techniques have different strengths, so the right approach depends on the input and the program being tested.