Abstract
Delta debugging is essential for simplifying complex bug-triggering test cases. However, traditional methods often produce invalid inputs that fail to satisfy system specifications, hindering the debugging process. This paper introduces GReduce, a novel tool that ensures validity by reducing the execution trace of an input generator rather than the test input itself. By manipulating the "recipe" of generation, GReduce achieves superior reduction efficiency and effectiveness across diverse domains.
The Validity Problem in Delta Debugging
When software developers encounter a bug through fuzzing, the resulting test input is typically massive and difficult to analyze. Delta debugging (e.g., the ddmin algorithm) aims to find a minimal version of this input that still triggers the bug.
Traditional delta debugging tools work by speculatively deleting chunks of text or nodes in a syntax tree. However, many inputs must adhere to complex semantic rules, such as checksums or "use-before-definition" requirements. Blindly deleting parts often results in invalid test inputs that fail early in the program's logic, preventing the reducer from finding a truly minimal, bug-triggering case.
While domain-specific reducers exist, they require significant manual effort to develop for every new format.
The GReduce Approach
GReduce addresses the validity problem by leveraging the generators used to create complex test inputs. Instead of modifying the final output, GReduce modifies the process of generation.
The GReduce workflow consists of three primary phases:
- Trace Instrumentation: GReduce records the generator's execution (the "trace"), capturing all random choices and control flow decisions.
- Trace Reduction: It identifies reducible patterns in the trace (e.g., loop iterations) and applies delta debugging logic to the trace itself.
- Trace-Aligned Re-Execution: GReduce re-runs the generator, forcing it to follow the modified trace. If the generator's state drifts, GReduce employs strategies like bypass or re-align to maintain execution consistency.
By operating on the generator's logic, GReduce "inherits" the generator's inherent knowledge of the input specification, ensuring the resulting output remains valid.
Evaluation and Results
The authors evaluated GReduce across five domains: Graphs (JGraphT), Deep Learning Models (TVM), JavaScript (Closure), Symbolic Algebra (SymPy), and synthetic Haskell benchmarks (SmartCheck).
GReduce consistently outperformed state-of-the-art tools like Perses (syntax-based) and T-PDD (probabilistic):
- Effectiveness: On DL models, GReduce's outputs were only 8.8% the size of those from T-PDD. For graphs, it achieved 71.5% better reduction than Perses.
- Efficiency: GReduce is significantly faster; in the DL domain, it required only 0.6% of the time taken by Perses.
- Versatility: It outperformed Hypothesis on SymPy and SmartCheck benchmarks, demonstrating robustness even with highly optimized generators.
Key Insights and Limitations
The core philosophy of GReduce is that the generator is the specification. Reducing the "recipe" (the trace) is inherently safer than reducing the "cake" (the input). A key innovation is the re-align strategy, which allows the generator to "drift" from the original trace and make new valid choices, often leading to smaller inputs than strict deletion.
However, GReduce relies on certain generator properties like monotonicity and locality. Generators that use global state or complex hashes to determine many subsequent actions may be harder to align. Currently, GReduce supports Java and Python, with future work focused on expanding language support and handling more complex dependencies in generators like CSmith.
Summary updated