Technical Summary: DRReduce

Problem Statement

Program reduction is essential for simplifying large, failure-inducing programs into minimal reproducible test cases. While language-specific tools (e.g., CReduce) achieve high effectiveness by leveraging deep semantic knowledge, they are tightly coupled to specific language families, requiring substantial engineering effort to port. Conversely, language-agnostic reducers (e.g., Perses, WDD) apply syntax-guided search across any grammar but suffer from a fundamental limitation: semantic coherence breakage.

When these syntax-guided tools delete a node or subtree in isolation, they often break semantic dependencies (e.g., removing a function declaration while leaving its call sites, or deleting a parameter while retaining its arguments). This results in intermediate programs that fail to compile. The property checker rejects these deletions not because the reduction logic is flawed, but because the program state is incoherent. Consequently, the reducer must backtrack, leading to excessive query invocations, reduced efficiency, and an inability to remove elements involved in mutual dependency cycles, ultimately limiting the final reduction size.

Methodology: DRReduce

The authors propose DRReduce, a framework that bridges the gap between language-agnostic syntactic reduction and semantic validity by augmenting the process with a lightweight semantic layer: dependency reconstruction.

Core Workflow

DRReduce operates in three stages:

1. Semantic Dependency Graph Construction: The system constructs a graph representing semantic dependencies (definition-use relationships, type constraints, and call-site consistency) from the input program. For source code, this involves parsing into an Abstract Syntax Tree (AST) and performing static analysis. For Intermediate Representations (IRs) like LLVM bitcode, the graph is constructed directly from existing dependency data.
2. Semantic Reduction with Dependency Reconstruction: This is the core contribution. DRReduce iteratively deletes semantic nodes using a Delta Debugging (DDMin) strategy. Crucially, after a deletion, it performs dependency reconstruction to repair broken references before querying the property checker. This ensures intermediate programs remain compilable.
   • Node Classification: Nodes are classified as Providers (defining entities), Users (referencing entities), or Conditioners (modifying validity, e.g., modifiers). Only Providers and Users are primary reduction candidates.
   • Reconstruction Strategies:
     • Default Value Replacement: If a Provider is deleted but Users remain, the Users are replaced with a type-compatible default value (e.g., 0 for pointers, null for objects, 1 for integers).
     • Associated Semantic Structure Deletion: If nodes form a circular dependency (e.g., a parameter and its corresponding argument), the entire cycle is deleted atomically to prevent signature mismatches.
3. Syntactic Minimization: The semantically reduced program is passed to a standard syntax-guided reducer (Perses in the implementation) for further minimization. Because the input is already semantically coherent, this stage converges faster.

Implementation

DRReduce was implemented for C and Java source code. It leverages JetBrains' Program Structure Interface (PSI) for semantic analysis, type resolution, and refactoring. The framework is designed to be language-agnostic; extending it to new languages requires only a parser, a mapping of language constructs to semantic roles, and default values for primitive types, without needing language-specific transformation rules.

Key Contributions

1. Formalization of Semantic Coherence Breakage: The paper identifies and formalizes the inefficiency caused by the mismatch between syntactic structure and semantic validity in language-agnostic reduction, introducing the concepts of semantic dependency and dependency reconstruction.
2. DRReduce Framework: A novel reduction framework that integrates dependency reconstruction with syntax-guided reduction, enabling the removal of semantically dependent elements that purely syntactic approaches cannot handle.
3. Language-Agnostic Design: The system achieves results comparable to language-specific tools without requiring hand-crafted, language-specific transformation rules, relying instead on a uniform dependency reconstruction strategy.
4. Empirical Validation: Implementation and evaluation on real-world bug-triggering programs for C and Java.

Experimental Results

The authors evaluated DRReduce on 28 real-world bug-triggering programs (16 C, 12 Java) against state-of-the-art baselines.

Comparison with Syntax-Guided Reducers (Perses, WDD, CDD)

• Effectiveness: DRReduce produced significantly smaller test cases. On average, it achieved further size reductions of 51.9% over Perses, 14.9% over WDD, and 19.8% over CDD.
• Efficiency: DRReduce completed reductions faster on the majority of Java programs and many C programs. While it incurred overhead for semantic analysis on large C programs, the reduction in query invocations (due to fewer compilation failures) often offset this, particularly in Java where baselines frequently generated invalid intermediates.

Comparison with Language-Specific Reducers (CReduce, Latra)

• Effectiveness: DRReduce achieved results comparable to CReduce and Latra (which use thousands of lines of hand-crafted rules) without using any language-specific rules. It produced the smallest output in 5 out of 16 C bugs and the second smallest in 7 others.
• Efficiency: DRReduce was significantly more efficient, completing reductions 3.3× faster than CReduce and 1.2× faster than Latra on average, with a 5.4× reduction in query invocations compared to CReduce.

Ablation Study

An ablation study isolating the dependency reconstruction component confirmed its critical role:

• Query Invocations: Reduced by 80.2%.
• Reduction Time: Reduced by 58.7%.
• Final Token Count: Reduced by 55.1%.

Significance and Claims

The paper claims that DRReduce addresses a fundamental bottleneck in language-agnostic program reduction: the inability to handle semantic dependencies without breaking compilability. By proactively repairing broken dependencies, DRReduce unlocks reduction opportunities that purely syntactic search cannot achieve.

The authors emphasize that DRReduce offers a "best of both worlds" approach: it retains the generality of language-agnostic tools while recovering much of the effectiveness of language-specific tools, all without the engineering burden of writing language-specific transformation rules. The work suggests that semantic coherence is a primary source of inefficiency in current reducers and that dependency reconstruction is a highly effective mechanism to resolve it.

Limitations Acknowledged:

• The default-value reconstruction strategy may fail for bugs sensitive to specific runtime values or type annotations (e.g., the cf-691 case where a specific type annotation was required to trigger a bug).
• The current implementation is limited to C and Java, though the design is argued to be generalizable.
• The evaluation uses token count as the primary metric, which the authors acknowledge may not perfectly correlate with human readability or debugging effort.