Validity-Preserving Delta Debugging via Generator Trace Reduction

Luyao Ren, Xing Zhang, Ziyue Hua, Yanyan Jiang, Xiao He, Yingfei Xiong, Tao Xie

TL;DR

This paper introduces GReduce, a novel approach to delta debugging that preserves the validity of reduced test inputs by leveraging input generators. By reducing the generator's execution trace instead of the test input itself, GReduce significantly outperforms existing methods in effectiveness and efficiency across various domains.

What Problem Does This Paper Address?

Debugging complex software often involves dealing with lengthy and intricate test inputs. Delta debugging is a popular technique for simplifying these inputs to pinpoint the root cause of bugs. However, a significant challenge arises when test inputs must conform to specific specifications (beyond just syntax). Existing delta debugging methods often produce invalid inputs that fail these specifications, diminishing their effectiveness and efficiency. This is particularly problematic in generator-based testing, where inputs are automatically generated to meet complex criteria.

Methods

GReduce tackles the validity problem by shifting the focus from reducing the test input directly to reducing the execution trace of the input generator. The core idea is to leverage the generator's inherent understanding of the input specifications. The process involves three main components:

  1. Trace Instrumentation: The generator's execution is disassembled into a structured trace, representing a sequence of operations.
  2. Trace Reduction: This component identifies "reducible parts" within the trace (e.g., loop iterations, conditional branches influenced by random choices) and attempts to remove subparts of the trace to create a reduced trace. This step is inspired by patterns in generators and uses strategies similar to ddmin and HDD.
  3. Trace-Aligned Re-Execution: The generator is re-executed, guided by the reduced trace. The goal is to align the new execution trace with the reduced trace, effectively producing a smaller, valid test input. This step involves manipulating the generator's randomness to achieve this alignment. The paper also introduces strategies (halt, bypass, re-align) to handle "infeasible trace alignment" where direct alignment is not possible.

Datasets

The paper evaluates GReduce on five benchmarks across distinct domains:

  • Graphs: Using the JGraphT library and a generator for random graphs.
  • Deep Learning (DL) Models: Using the TVM compiler and the Isra generator for DL models.
  • JavaScript Programs: Using the Closure compiler and a JavaScript program generator from Zest.
  • SymPy Benchmark: An existing benchmark used in Hypothesis [28].
  • SmartCheck Benchmark: A set of five synthetic benchmarks from [28, 38].

The bug-inducing test inputs were collected by running generator-based testing on these software subjects.

Key Insights and Ideas

  • Generator-centric reduction: The most crucial insight is that input generators, by their nature, understand input specifications. Instead of trying to preserve validity by brute force on the output, GReduce leverages the generator's internal logic by reducing its execution trace.
  • Trace reduction for validity: Reducing the execution trace of a generator offers a more direct path to generating valid reduced inputs. By removing operations from the trace, the resulting generator execution naturally produces a smaller, valid output.
  • Handling non-determinism: Generators often rely on randomness. GReduce's "Trace-Aligned Re-Execution" component cleverly manipulates this randomness to align the reduced trace with a new execution, effectively guiding the generator to produce a smaller, valid output.
  • Tree-based trace reduction is superior: The evaluation shows that modeling reducible parts of the trace as a hierarchical tree structure (using HDD strategies) is more effective than a simple sequential approach.

Key Results

GReduce demonstrates significant improvements in both effectiveness and efficiency compared to state-of-the-art reducers like Perses, T-PDD, JSDelta, and Hypothesis.

  • Effectiveness (Size Reduction): GReduce consistently achieves the smallest reduced test inputs across all domains. For example, it reduces graph inputs by an average of 71.5% more than Perses and 86.1% more than T-PDD.
  • Efficiency (Reduction Time): GReduce is substantially faster. For DL models, it takes only 0.6% of the time Perses takes. On SymPy and SmartCheck benchmarks, it significantly outperforms Hypothesis in reduction time and property tests.
  • Validity Preservation: A key finding is that syntax-based reducers (Perses, T-PDD, ddmin) produce a low proportion of valid test inputs for complex domains like DL models (as low as 2.55%), whereas GReduce inherently preserves validity.

Limitations and Future Work

  • Supported Generators: The current implementation primarily supports generators written in Java and Python. Extending support to other languages and frameworks is a future direction.
  • Trace Reduction Completeness: The design of reducible patterns in Trace Reduction defines a manageable search space. While effective, a bounded-exhaustive enumeration could improve effectiveness at the cost of increased running time. Designing additional reducible patterns is also suggested.
  • Infeasible Trace Alignment: While strategies like halt, bypass, and re-align help, they are not always sufficient to completely resolve problems caused by complex data dependencies in generators.
  • Generator Properties: The approach relies on generator properties like monotonicity and locality. While preliminary studies suggest these are common, cases where they don't hold might require adjustments to reduction strategies.
  • Broader Applicability: The authors suggest further experiments with wider types of generators and test inputs to improve external validity. Exploring language design for generators that inherently support these properties is also a promising avenue.

Summary updated

BibTeX
@article{ren2025validity,
  author = {Luyao Ren and Xing Zhang and Ziyue Hua and Yanyan Jiang and Xiao He and Yingfei Xiong and Tao Xie},
  title = {{Validity-Preserving Delta Debugging via Generator Trace Reduction}},
  journal = {ACM Trans. Softw. Eng. Methodol.},
  year = {2025},
  doi = {10.1145/3705305},
}
Figure