• Home
  • Blog
  • Schedule
  • Syllabus

Contents

  • Overview
  • Why Reduce Failure-Inducing Inputs?
  • Manual Input Reduction
  • Delta Debugging
  • Grammar-Based Input Reduction
    • Why Syntax Matters
    • Derivation Trees
  • Simplifying Structured Inputs
    • Simplifying by Replacing Subtrees
  • Comparing Reduction Techniques
    • Comparing Strategies on a Long Expression
  • Lessons Learned

Reducing Failure-Inducing Inputs

post
software engineering
fuzzing book
How can reducing failure-inducing inputs make debugging easier?
Authors

Kathryn Boidock

Ritesh Ojha

Gregory M. Kapfhammer

Published

November 18, 2026

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 / 0

The expression contains several operations, but it can be reduced to:

3 / 0

Both 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()xyz789

A developer might try removing different sections and testing the result:

abc123()xyz789   FAIL
123()xyz         FAIL
()xyz            FAIL
()               FAIL

In 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 inp

For example, a reducer might test the following candidates:

abc123()xyz789   FAIL
()xyz789         FAIL
()               FAIL

The 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.

Why Syntax Matters

Consider the following valid expression:

1 + (2 * 3)

Deleting arbitrary characters could produce:

1 + (2 *

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.

Derivation Trees

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 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.

Simplifying by Replacing Subtrees

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 1 + (2 * 3). The following derivation tree shows how the original expression is organized into grammar symbols such as <expr>, <term>, and <factor>.

Original derivation tree for 1 + (2 * 3). Source: The Fuzzing Book.

The reducer can simplify the original expression by replacing its larger <expr> subtree with the smaller <expr> subtree representing (2 * 3). This removes the 1 + portion while keeping the expression valid according to the grammar.

Reduced derivation tree for (2 * 3). Source: The Fuzzing Book.

Simplifying by Alternative Expansions

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 (2 * 3) could be simplified to (3) by replacing the multiplication with a simpler 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?

Click to Expand for the Answer

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.

Comparing Reduction Techniques

The main reduction techniques differ in how much they know about the input:

TechniqueHow it worksAdvantagesLimitations
Manual reductionA developer removes sections and reruns the testEasy to start and inspectSlow and difficult to repeat for large inputs
Delta debuggingAutomatically removes chunks and tests their complementsWorks without a grammar and applies to many formatsMay generate many invalid candidates
Grammar-based reductionSimplifies derivation trees and grammar expansionsPreserves syntactic structure and produces meaningful inputsRequires 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.

Comparing Strategies on a Long Expression

The chapter demonstrates this trade-off by generating a long arithmetic expression with a grammar fuzzer and reducing the same input with both strategies:

long_expr_input = GrammarFuzzer(
    EXPR_GRAMMAR, min_nonterminals=100
).fuzz()

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:

grammar_reducer = GrammarReducer(
    eval_mystery, EarleyParser(EXPR_GRAMMAR)
)
grammar_reducer.reduce(long_expr_input)
grammar_reducer.tests

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:

dd_reducer = DeltaDebuggingReducer(eval_mystery)
dd_reducer.reduce(long_expr_input)
dd_reducer.tests

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.

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.
NoteOpen-Source Tool for Software Engineers

Our tool is text-reducer, a small educational command-line tool that minimizes a text file while keeping a user-provided checker failing. It demonstrates the delta debugging technique from this chapter. You should check out the text-reducer on GitHub!

NoteReference

Unless otherwise noted, the source code segments in this article are excerpted directly from the Fuzzing Book. The authors of this online book licensed the source code and its written content under the BY-NC-SA 4.0 Creative Commons License. More details about the license for the Fuzzing Book are available in the The Fuzzing Book License.

Return to Blog Post Listing

DevDev

Top