arXiv CSopen access

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

softwarearchitecture softwareengineering testing

software engineering, software architecture, testing

arXiv:2605.19412v1 [cs.SE] 19 May 2026

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction QIONG FENG, Nanjing University of Science and Technology, China XIAOTIAN MA, Nanjing University of Science and Technology, China YONGQIANG TIAN, Monash University, Australia WEI SONG, Nanjing University of Science and Technology, China PENG LIANG, School of Computer Science, Wuhan University, China Program reduction is a critical technique for simplifying large, failure-inducing programs into minimal reproducible test cases. Language-specific tools such as CReduce achieve strong performance by leveraging deep semantic knowledge of C/C++, but are tightly coupled to a single language family. Language-agnostic reducers such as Perses address this by applying syntax-guided search across any grammar, yet share a fundamental limitation: deleting a node or subtree in isolation often breaks semantic coherence — such as leaving unresolved references or inconsistent signatures — causing the property checker to reject the deletion and forcing the reducer to backtrack, limiting overall reduction effectiveness and efficiency. In this paper, we propose DRReduce, a framework that bridges this gap by augmenting language-agnostic syntactic reduction with a lightweight semantic layer: dependency reconstruction, which repairs program dependencies broken by a deletion in order to preserve the semantic validity of intermediate programs and increase the acceptance rate of the property checker. DRReduce constructs a semantic dependency graph from the input program, performs semantically coherent deletions with dependency reconstruction, and delegates further minimization to a syntax-guided reducer. We implement DRReduce for C and Java and evaluate it on real-world bug-triggering programs. Compared to state-of-the-art syntax-guided reducers, DRReduce achieves average size reductions of 51.9%, 14.9%, and 19.8% over Perses, WDD, and CDD respectively, while completing reduction faster on the majority of programs. Compared to language-specific tools, DRReduce achieves results comparable to CReduce and Latra without any language-specific transformation rules, at 3.3× and 1.2× higher efficiency than CReduce and Latra on average, respectively. An ablation study confirms that dependency reconstruction reduces query invocations by 80.2%, reduction time by 58.7%, and final token count by over 55.1%. CCS Concepts: • Software and its engineering → Software testing and debugging. Additional Key Words and Phrases: Program Reduction, Semantic Dependency, Dependency Reconstruction

Introduction

Program reduction is a critical debugging technique that simplifies large, failure-inducing programs into minimal reproducible test cases [8, 16, 24]. A minimal test case is easier to inspect, faster to replay, and more likely to isolate the root cause of a bug. As software systems grow in complexity and automated testing generates increasingly large failure-inducing inputs, the ability to reduce programs quickly and effectively has become essential to the debugging workflow of compiler developers and language implementors [10, 13, 20, 21, 25–28]. For instance, both GCC and LLVM explicitly require bug-triggering test cases to be minimized to reduce the workload of developers and increase the bug fix probabilities [2, 9]. Reduction with language-specific transformations. The most effective program reducers leverage deep knowledge of a single target language. For example, CReduce [13] targets C/C++ programs and achieves remarkably small outputs by applying a rich set of semantics-aware transformations — Authors’ Contact Information: Qiong Feng, Nanjing University of Science and Technology, Nanjing, China, qiongfeng@njust. edu.cn; Xiaotian Ma, Nanjing University of Science and Technology, Nanjing, China, [email protected]; Yongqiang Tian, Monash University, Melbourne, Australia, [email protected]; Wei Song, Nanjing University of Science and Technology, Nanjing, China, [email protected]; Peng Liang, School of Computer Science, Wuhan University, Wuhan, China, [email protected].

Feng et al.

inlining functions, simplifying types, removing unused declarations — that are carefully engineered to preserve compilability and bug-triggering behavior. Similar tools exist for specific domains: llvm-reduce for LLVM IR [12]. More recently, Latra [23] has reduced the engineering burden of building such reducers by allowing users to express transformations as match-rewrite template pairs in a domain-specific language; for C, Latra implements 27 such rules and achieves results statistically comparable to CReduce. These tools work well precisely because they encode deep knowledge of a single language’s semantics. However, this strength is also their limitation: the transformations are tightly coupled to the target language, and building a similar tool for another language requires substantial engineering effort. Language-agnostic reduction. To address this, language-agnostic reducers such as Perses [17], WDD [30] and ProbDD [18] apply syntax-guided search across any context-free grammar. Given a grammar and a property checker, these tools systematically attempt to delete or replace subtrees while preserving the property of interest. Because of operating on parse trees rather than semantic models, they require no language-specific knowledge and generalize immediately to any language with a formal grammar. In practice, they achieve competitive reduction ratios across a wide range of languages, making them the default choice when no dedicated reducer exists. The semantic coherence problem. Despite their generality, syntax-only reducers share a fundamental limitation rooted in the mismatch between syntactic structure and semantic validity. Deleting a node or subtree in isolation frequently breaks semantic coherence: a removed function declaration leaves call sites with unresolved references, a deleted parameter creates a signature mismatch at every call site, and a removed type definition invalidates all variables of that type. The resulting intermediate program fails to compile, and the property checker rejects the deletion — not because the reduction was semantically wrong, but because the surrounding program was left in an incoherent state. This forces the reducer to backtrack and try smaller subsets, multiplying query invocations and reducing overall efficiency. In effect, syntax-guided reducers pay the full search cost but cannot exploit semantic structure to recover rejected deletions. Our approach. In this paper, we propose DRReduce, a framework that bridges this gap by augmenting language-agnostic syntactic reduction with a lightweight semantic layer. The key insight is that most semantic coherence failures following a deletion are local and repairable. When a node is deleted, other nodes that depended on it can be reconstructed — replaced with a default value of the appropriate type. This reconstruction restores compilability without affecting whether the bug-triggering property is preserved. We formalize this operation as dependency reconstruction and integrate this operation into a three-stage reduction pipeline: DRReduce first constructs a semantic dependency graph from the input programs, then applies dependency reconstruction to perform semantically coherent deletions, and finally delegates further minimization to a syntax-guided reducer such as Perses. Critically, DRReduce achieves this without language-specific transformation rules. The dependency graph is constructed from definition-use relationships that can be extracted from any language with a type system, and dependency reconstruction applies a uniform default-value replacement strategy that requires only type information. This makes DRReduce applicable to any language for which a parser and basic semantic analysis are available. To validate this generality and quantify the benefits of dependency reconstruction, we implement DRReduce for C and Java and evaluate it on 28 real-world bug-triggering programs. Compared to state-of-the-art syntax-guided reducers (Perses, WDD, and CDD), DRReduce reduces programs to 51.9%, 14.9%, and 19.8% smaller sizes on average, while completing reduction faster on the majority of programs. Compared to reducers that incorporate language-specific transformations (CReduce and Latra), DRReduce closely matches their effectiveness without using any language-specific transformation rules, at 3.3× and 1.2× higher efficiency on average, respectively. An ablation study

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

confirms that dependency reconstruction reduces query invocations by 80.2%, reduction time by 58.7%, and final token count by over 55.1%. This paper makes the following contributions: • We identify semantic coherence breakage as a key source of inefficiency in languageagnostic program reduction, and formalize it through the notions of semantic dependency and dependency reconstruction (Section 3.1 and Section 3.2). • We present DRReduce, a language-agnostic reduction framework that integrates dependency reconstruction with syntax-guided reduction (Section 3). • We implement DRReduce for two targets — C and Java source code — demonstrating its applicability across different source languages (Section 3.3). • We evaluate DRReduce on real-world bug-triggering programs and show that it consistently outperforms state-of-the-art syntax-guided reducers in both effectiveness and efficiency (Section 5.1), while achieving results comparable to language-specific, semantictransformation-based tools at substantially higher efficiency (Section 5.2). The remainder of the paper is organized as follows: Section 2 presents a motivating example to illustrate the semantic coherence challenges that DRReduce addresses. Section 3 presents how DRReduce is implemented. Section 4 and Section 5 detail the experimental setup and evaluation. Section 6 discusses the limitations and future potential of DRReduce, and Section 7 addresses threats to validity. Section 8 surveys related work, and Section 9 concludes the paper. 2

A Motivating Example

01 0 0 0 0 0 02 0000 01234 03 00000000 04 0000 0 0 !"0 0 05 0000 0 06 00000000 0 #0$0 07 00000000 0 %0$0 08 00000000 0 # 0$0 #0&0 % 09 00000000'()(* ) # 1 0000 0 0* ) 0 + 0 11 0000 0,- )0.) /0, 12 00000000 13 0000 14 (a) Before reduction. Arrows indicate direct semantic dependencies.

01 0 0 0 0 0 02 0000 01234 03 00000000 04 0000 0 0 !"0 0 05 0000 0 06 00000000 0 #0$0 07 00000000 0 # 0$0 #00000000000 08 00000000%&'&( ' # 09 0000 0 0( ' 0 ) 0 1 0000 0*+ '0,' -.* 11 00000000 12 0000 13 (b) Reduction result generated by WDD.

Fig. 1. A Java program and its reduction result by WDD.

Program reduction takes as input a bug-triggering program 𝑃 and a property checker 𝜓 that determines whether a given program preserves the property of interest, and produces a smaller program 𝑃 ′ satisfying 𝜓 (𝑃 ′ ) = 𝜓 (𝑃). Figure 1a shows a Java program prior to reduction, where the property of interest is producing the “Hello World” output. Figure 1b presents the successfully reduced program produced by Weighted Delta Debugging (WDD) [30], which still prints “Hello World”. Built on Perses [17] - which leverages ANTLR grammars to transform programs into syntax trees — WDD is among the most advanced language-agnostic reduction techniques. It improves upon prior delta debugging approaches by assigning weights to syntactic elements (e.g., based on token count) and performing weight-aware partitioning, prioritizing the removal of smaller elements that are more likely to be irrelevant. Although WDD achieves state-of-the-art (SOTA)

Feng et al.

Reduced Size (tokens)

(0, 71) (6, 71)

(31, 71) (32, 69)

(49, 69) (50, 62)

(81, 62)

(7, 57) (15, 57) (16, 54) (18, 54)

55 50 45

Invocations, Reduced Size) (19, 37) (26, 37) (X, Y) = (Number of Query WDD

DRReducer

Number of Query Invocations

Fig. 2. The overall reduction result of WDD and DRReduce.

effectiveness and efficiency compared to other language-agnostic methods, it still exhibits two key limitations on this example. Limitation 1: WDD generates invalid intermediate results, which limits efficiency. During node deletion, operations must often follow a strict order: removing elements out of sequence can violate syntactic or semantic dependencies. For example, in Figure 1a, the method uselessFunc is invoked within main. Deleting its declaration before removing its call sites results in a compilation error. Thus, the statement uselessB = uselessFunc(); must be eliminated before uselessFunc can be safely removed. To handle such ordering constraints, Perses employs a fixpoint iteration strategy: it repeatedly applies reduction passes until no further nodes can be deleted, ensuring that interdependent elements are eventually processed. In this example, Perses first attempts (and fails) to remove uselessFunc , then successfully deletes uselessB = uselessFunc(); , and continues iterating until reaching a 1-minimal state. WDD further improves this process by using weights to guide deletion order. However, as shown in Figure 2, even for this simple program, WDD requires 81 iterations, whereas our approach completes the reduction in only 26 iterations. A closer inspection reveals that WDD frequently produces invalid intermediate states. In the first 31 iterations, all attempts fail the query script—for example, it removes uselessA without eliminating its occurrences in uselessA + uselessB . Only at iteration 32 does it successfully simplify the expression by removing + uselessB , reducing the token count to 69. Between iterations 33 and 49, despite two fixpoint cycles, no function-level elements are removed. The 50th iteration finally succeeds in deleting the statement int uselessB=uselessFunc(); , after which further iterations again yield no progress. The root cause is that WDD does not explicitly enforce the semantic ordering of deletions. Valid intermediate states must respect the topological order induced by dependency relationships among syntax nodes. Ignoring this constraint leads to numerous failed attempts and significantly degrades efficiency, particularly for larger programs. Limitation 2: WDD fails to handle mutually dependent elements, which limits effectiveness. Some syntax nodes form mutual semantic dependencies that prevent fixpoint reduction from making progress. We define a node that provides a dependency as a provider node and one that consumes

Change Ed

01223453657

to k lic C

(a) Deleting an argument causes a compilation error (iteration 39.

hange E

F-

01 0 0 0 0 0 02 0000 01234 03 00000000 04 0000 0 0 !"0 0 05 0000 0 06 00000000 0 #0$0 07 00000000 0 %0$0 08 00000000 0 # 0$0 #00000000000 09 00000000&'(') ( # 1 0000 0 0) (00000000000000000 11 0000 0*+ (0,( -.* 12 00000000 13 0000 223453657 1401 or

01 0 0 0 0 0 02 0000 01234 03 00000000 04 0000 0 0 !"0 0 05 0000 0 06 00000000 0 #0$0 07 00000000 0 %0$0 08 00000000 0 # 0$0 #00000000000 09 00000000&'(') (0000000000 1 0000 0 0) ( 0 * 0 11 0000 0+, (0-( ./+ 12 00000000 13 0000 14

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

d f- x

chang

(b) Deleting a parameter causes a compilation error (iteration 42.

15ÿ122

Fig. 3. Two invalid intermediate results produced by WDD for Fig. 1a.

15ÿ122 ÿ ' , . 3 6 ;

88ÿ

ÿÿ ÿÿÿÿÿÿÿ !"#$%ÿ"#&ÿ ' ÿÿÿÿÿÿÿÿÿ(()ÿ*ÿ + , ÿÿÿÿÿÿÿÿÿ((-ÿ*ÿ + . ÿÿÿÿÿÿÿÿÿ(()"#ÿ*ÿ(()ÿ/ÿ((-+ ÿÿÿÿÿÿÿÿ!0(11" 2( (()"#&&+ ÿÿÿÿÿÿÿÿ!0(11" 2( &&+ 3 ÿÿÿÿ4 ÿÿÿÿÿ!"#ÿ2( ÿ((5"&ÿ ÿÿÿÿÿ!"#ÿ2( &ÿ 6 ÿÿÿÿÿÿÿÿ"("ÿ78(ÿ9":7+ ; ÿÿÿÿ4 4

(a) A valid intermediate program at iteration 16 (54 tokens), in which DRReduce atomically removes a parameter and its corresponding argument together.

89ÿ

ÿÿ ÿÿÿÿÿÿÿ ÿ ÿÿÿÿÿÿÿÿÿ !"# ÿÿÿÿ$ % ÿÿÿÿ&'ÿÿ()*ÿ+,-./ÿ-ÿ ÿÿÿÿÿÿÿÿÿ0ÿ1ÿ# ÿÿÿÿÿÿÿÿÿ2ÿ1ÿ# ÿÿÿÿÿÿÿÿÿ0-ÿ1ÿ0ÿ3ÿ2# ÿÿÿÿÿÿÿÿ,4+5)5&6)0-# ÿÿÿÿÿÿÿÿ,4+5)5&6)# 7 " ÿÿÿÿ$ ÿÿÿÿÿ,-ÿ6)ÿ8+ÿ ÿÿÿÿÿ,-ÿ6)ÿ 9 ÿÿÿÿÿÿÿÿÿ:;)ÿ<)*=:# ! > ÿÿÿÿ$ " ? $ (b) Final reduction result of Fig. 1a produced by DRReduce.

Fig. 4. Intermediate and final reduction results produced by DRReduce on the motivating example in Fig. 1a. Yellow shading indicates the lines that were present in the previous valid intermediate but have been deleted in this step.

it as a user node. While deleting a provider node typically breaks its user nodes, in some cases deleting the user node also causes errors. Figure 1a illustrates such a scenario: uselessParam and uselessArg are mutually dependent, since function arguments and parameters must remain consistent for successful compilation. Removing either one isolately results in a compilation error, as illustrated in Figures 3a and 3b, which show two failed attempts by WDD at iterations 39 and 42. Consequently, nodes involved in such cycles cannot be deleted individually, and fixpoint iteration alone cannot break the impasse, leaving WDD stuck at a larger reduced size than is theoretically achievable.

Feng et al.

Summary and our approach. The two limitations above share a common root cause: existing syntax-guided reducers treat syntax nodes as independent units and lack any awareness of the semantic dependencies between them. As a result, they generate invalid intermediate programs which fail to compile and also cannot remove elements involved in dependency cycles. To address both limitations, we propose DRReduce: Augmenting Syntax-Guided Program Reduction with Dependency Reconstruction. Given an input program, DRReduce first identifies its semantic nodes (i.e., syntax nodes that participate in semantic dependencies, such as declarations, references, and parameters) and their dependencies. It then iteratively deletes these semantic nodes using DDMin [25], and after each deletion, it applies dependency reconstruction to proactively repair any broken references introduced by the removal. Dependency reconstruction takes two forms: when a deleted node is referenced by surviving users, DRReduce substitutes a placeholder of the appropriate type at each reference site (the type remains visible and is sufficient to synthesize a placeholder in the program text even when the value does not); when a deleted node participates in a circular dependency, DRReduce deletes the entire cycle. Concretely, when deleting uselessFunc , its call sites on Lines 6 and 7 in Figure 1a are replaced with the constant expression 1, as shown on Lines 3 and 4 in Figure 4a. In another scenario, when deleting uselessParam , the corresponding argument uselessArg is deleted simultaneously to break the circular dependency. By keeping intermediate programs compilable in both scenarios, DRReduce substantially increases the rate at which the oracle accepts deletions, addressing both efficiency and effectiveness limitations of prior syntax-guided reducers. As shown in Figure 2, DRReduce reduces the example program from 71 to 37 tokens in 26 iterations, while WDD only reaches 62 tokens after 81 iterations; the final reduction result produced by DRReduce is shown in Figure 4b. We describe the design of DRReduce in detail in Section 3. 3

DRReduce

The overall workflow of DRReduce is shown in Figure 5. Given a set of programs and a property of interest, DRReduce proceeds in three stages. In Stage 1, DRReduce constructs a semantic dependency graph, a language-agnostic representation that can model dependencies across programs in different forms. The graph construction strategy differs depending on whether semantic dependency information is explicitly available in the input. For intermediate representations (IRs) that already encode dependency information — such as IRs used for compiler testing [1, 3] or compilation IRs such as LLVM bitcode — DRReduce constructs the graph directly without additional analysis. For source code or other program forms without explicit dependencies, DRReduce first parses each program into an Abstract Syntax Tree (AST), then performs static analysis to extract semantic relationships such as definition-use chains, function call dependencies, and type constraints. In both cases, the resulting graph has the same structure and the subsequent reduction process is identical. In Stage 2, semantic reduction with dependency reconstruction, performs the actual semantic reduction and consists of three steps. (1) DRReduce classifies semantic nodes that carry semantic significance. (2) DRReduce deletes semantic nodes using DDMin [25]. (3) DRReduce traverses the semantic dependency graph and reconstructs broken dependencies by rewiring them to valid replacements. By directly manipulating the program’s dependency structure, this stage produces a semantically valid reduced program that preserves the property of interest while remaining compilable and executable. In Stage 3, DRReduce passes the semantically reduced program to a syntactic reducer — Perses in our implementation — which performs further minimization by systematically attempting to delete or replace subtrees guided by the language grammar. Because Stage 2 has already produced

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

Fig. 5. DRReduce’s overall workflow

a clean, semantically coherent core, Stage 3 encounters far fewer query invocations and converges faster than it would on the original input. The two stages are complementary, but the majority of DRReduce’s effectiveness gain over prior reducers comes from Stage 2’s dependency reconstruction— the core contribution of this work — which performs reductions that no purely syntactic search can achieve, as illustrated in our motivating example (Section 2) and further confirmed in our ablation study (Section 5.3). Algorithm 1 presents the full procedure of Stage 2: semantic reduction with dependency reconstruction. Given a set of programs P, a property checker 𝜓 , and the semantic dependency graph generated in Stage 1, this procedure proceeds as a single loop driven by the DDMin search [25], via the routines InitDDMin, NextCandidate, and UpdateDDMin. The search maintains internal state that determines the next deletion candidate RC𝑑𝑒𝑙 based on the accepted and rejected attempts, rather than enumerating subsets in a fixed order. Each iteration (Lines 7–13) applies one such candidate to a working copy of the program, performs dependency reconstruction, and queries the oracle 𝜓 . When a deletion is accepted, all nodes in RC𝑑𝑒𝑙 are removed from 𝐺, along with every edge incident to them. Second, the edges that previously connected those nodes to remaining user nodes are rewired to the placeholder expressions introduced by reconstruction. After this update, semanticnode classification is re-run on the modified graph to provide any new reduction opportunities exposed by the deletion. DRReduce continues until the ddmin search exhausts its candidates. The remainder of this section describes the two core steps of Algorithm 1 in detail: classifying semantic nodes (Section 3.1) and reconstructing dependencies (Section 3.2). 3.1

Classifying Semantic Nodes

Effective dependency reconstruction requires identifying which syntax nodes participate in semantic relationships in the first place. Not all syntax nodes are equally relevant to semantics. To focus reduction on semantically meaningful nodes, DRReduce classifies nodes into three categories based on their semantic role: • Provider: the node defines a semantic entity that other nodes depend on (e.g., a function declaration, a variable declaration, a parameter declaration). • User: the node references a semantic entity defined by other nodes (e.g., a function call, a variable reference, an argument at a call site).

Feng et al.

Algorithm 1 Semantic Reduction with Dependency Reconstruction Require: 𝐺, Set of programs P = {𝑃 1, 𝑃2, . . . , 𝑃𝑛 }, property 𝜓 Ensure: Reduced programs P ′ = {𝑃1′ , 𝑃2′ , . . . , 𝑃𝑛′ } each satisfying 𝜓 1: RC𝑠𝑒𝑚 ← ClassifySemanticNodes(𝐺) 2: P ′ ← P 3: state ← InitDDMin(RC𝑠𝑒𝑚 ) 4: while state has unexplored candidates do 5: RC𝑑𝑒𝑙 ← NextCandidate(state) 6: P𝑡𝑒𝑠𝑡 ← Copy(P ′ ) 7: Delete all nodes in RC𝑑𝑒𝑙 from 𝑃𝑡𝑒𝑠𝑡 8: ReconstructDependencies(P𝑡𝑒𝑠𝑡 , 𝐺, RC𝑑𝑒𝑙 ) 9: if 𝑃𝑡𝑒𝑠𝑡 |= 𝜓 then 10: P ′ ← P𝑡𝑒𝑠𝑡 11: 𝐺 ← UpdateGraph(𝐺, RC𝑑𝑒𝑙 ) ⊲ Remove deleted nodes; rewire edges to reconstructed placeholders 12: RC𝑠𝑒𝑚 ← ClassifySemanticNodes(𝐺) 13: state ← UpdateDDMin(state, RC𝑠𝑒𝑚 , accept) 14: else 15: state ← UpdateDDMin(state, RC𝑠𝑒𝑚 , reject) 16: end if 17: end while 18: return P ′

• Conditioner: the node neither defines nor references a semantic entity directly, but conditions whether other dependencies remain valid (e.g., a public modifier, whose removal can invalidate references to the enclosing entity from other packages). This classification extends classical def-use analysis and generalizes its notion. Providers and users naturally capture def-use relationships, but they also capture other forms of semantic dependency that def-use analysis does not, such as the positional correspondence between formal parameters and their actual arguments at call sites, even though no variable is being defined or referenced. The conditioner category has no def-use relations and captures syntactic structures whose removal would invalidate many provider-user relationships. Consider the nodes of a Java method declaration: annotation nodes, modifier nodes, and parameter nodes. Annotation nodes reference a class declaration and therefore act purely as users. Modifier nodes (e.g., public, static) determine whether the method can be referenced externally, making them conditioners. Parameter nodes are both users and providers: they have bidirectional dependencies with argument expressions at call sites, and also define entities consumed by nodes within the method body. DRReduce models semantic relations between Provider and User nodes as directed edges (𝑢, 𝑝) ∈ 𝐸, where 𝑢 ∈ 𝑁𝑠𝑒𝑚 is a user that directly requires 𝑝 ∈ 𝑁𝑠𝑒𝑚 , a provider, for its semantic validity. The resulting dependency graph 𝐺 = (𝑁𝑠𝑒𝑚 , 𝐸) captures all such edges over the selected semantic nodes. The deletion behavior of nodes follows naturally: removing 𝑝 renders 𝑢 semantically invalid, while removing 𝑢 eliminates the dependency on 𝑝, making 𝑝 a candidate for removal if no other user depends on it. For example, the method hello directly requires the parameter int uselessParam it corresponds to, yielding the edge ( hello , int uselessParam ). In C, a call site is a user of the function declaration it references, and a function’s forward declaration is a user of its definition.

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

DRReduce selects only provider and user nodes as reduction candidates, since their semantic roles are well-defined and can be precisely captured by semantic dependencies. conditioner nodes, whose semantic effects are more complex and context-dependent, are delegated to the syntax-guided reducer in Stage 3. For instance, in C, a function’s return type node is treated as a conditioner and excluded from DRReduce’s reduction candidates; though it remains a candidate for the syntaxguided reducer. 3.2

Reconstructing Dependencies

When a provider node in a reduction candidate is deleted atomically through DDMin, any user nodes that depend on the deleted provide node will produce compilation errors. To prevent this, DRReduce applies dependency reconstruction before committing any deletion: for each provider 𝑝 scheduled for deletion, every user 𝑢 such that (𝑢, 𝑝) ∈ 𝐸 that has not itself been deleted is modified to remove its dependency on 𝑝, keeping the intermediate program compilable. Dependency reconstruction takes two forms. • Default value replacement substitutes the user node with the default value of its expected type. In Figure 1a, after scheduling uselessFunc for deletion, DRReduce reconstructs the dependency at Lines 6 and 7 by replacing uselessFunc with 1. The modified intermediate program compiles successfully, allowing the deletion to proceed without error, as shown in Figure 4a. This Default value replacement operation modifies program semantics but preserves their semantics to the extent possible. • Associated semantic structure deletion removes groups of nodes that share a mutual semantic relationship and cannot be deleted independently without breaking compilation. One example is the relationship between a formal parameter in a function declaration and its corresponding actual argument at every call site: deleting one without the other produces a signature mismatch. As illustrated in Figure 4b, this Associated semantic structure deletion operation enables DRReduce to remove both uselessParam and uselessArg together. The choice between the two forms is determined by the dependency structure: DRReduce applies default-value replacement when the deleted node has surviving users that reference its value, and associated structure deletion when the deleted node participates in a circular dependency where no individual node can be removed without breaking another, such as parameter-argument pairs. Semantic validity guarantees. Dependency reconstruction guarantees the compilability of every intermediate program but not behavioral equivalence to the original. By substituting type-compatible default values for broken references or deleting cyclic dependencies, the modified program may compute different values than the original, but it always compiles. This weaker guarantee does not compromise the soundness of DRReduce: every intermediate is independently checked against the property 𝜓 , and modifications that violate 𝜓 are rejected exactly as any other failed reduction would be. The role of reconstruction is to ensure that 𝜓 can be evaluated — the program compiles — not to ensure that it is satisfied. This decouples compilability from property preservation, which syntax-guided reducers conflate: prior tools treat compilation failures as evidence of failed reduction even though such failures reveal nothing about 𝜓 . In practice, most bug-triggering properties (compiler crashes, miscompilations of structural patterns, type-checker false positives and false negatives) depend on syntactic or type-level features rather than concrete runtime values, so default-value reconstruction preserves 𝜓 in the vast majority of cases. When it does not, the oracle rejects the modification and DRReduce backtracks. Our evaluation (Section 5.1) identifies one such case (cf-691), where the bug-triggering property is sensitive to a specific type annotation that default-value substitution destroys; this is the only

Feng et al.

program in our 28-program benchmark on which DRReduce underperforms a syntax-guided baseline. 3.3

Language-Specific Implementation

While Algorithm 1 describes a general semantics-guided reduction process, its full realization requires semantic analysis and dependency reconstruction capabilities that vary across languages and program forms. DRReduce currently supports two targets: C and Java source code. We choose these two languages for two reasons. First, both are widely used in compiler testing and have well-established benchmarks and baselines for program reduction, enabling direct comparison with prior work. Second, JetBrains’ Program Structure Interface (PSI) [5] provides unified APIs for dependency analysis, type resolution, and refactoring operations across both languages, which we leverage as the foundational infrastructure for semantic analysis and transformation in DRReduce. Table 1 summarizes the semantic nodes for each language, and Table 2 details the dependency reconstruction strategies. Extending DRReduce to other languages. Adding support for a new language requires three pieces of language-specific information: (1) a parser and AST representation, (2) a mapping from language constructs to the provider, user, and conditioner roles in Table 1, and (3) default values for each primitive type. The mapping is small (our C and Java implementations each define fewer than ten node categories) and follows directly from the language’s type system; default values are trivially available in any typed language. Notably, no language-specific transformation rules are required, since the reduction logic itself remains unchanged across languages. Languages already integrated with PSI (e.g., Kotlin, Python, Rust, Go) can reuse the existing front-end with no new analysis infrastructure. Table 1. Semantic node categories identified by DRReduce for C and Java.

Semantic Nodes C

Files, Declarations, Statements, Function declaration and its definition, parameter declaration and its corresponding arguments

Java

Files, Statements, Named Nodes, Parameters, Parameter declaration and its corresponding arguments

3.3.1 C Source Code. For C programs, DRReduce performs semantic analysis using JetBrains’ Program Structure Interface (PSI) [5], a language-aware API provided by IntelliJ CLion that represents source code as a structured tree of typed nodes, each carrying syntactic and semantic information such as type bindings, reference resolution, and scope. DRReduce leverages PSI to identify semantic dependencies between nodes without requiring a custom parser or type checker. The selected semantic nodes are Files, Declarations, and Statements. Declarations cover struct declarations, function declarations, variable declarations, struct members, and parameter declarations. Expression nodes are excluded because dependency reconstruction for expressions requires non-trivial type inference, which we leave for future work. Two kinds of node pairs are grouped together: (1) a function’s forward declaration and its definition — since deleting either alone leaves an unresolved symbol — and (2) a parameter declaration and its corresponding argument expressions at all call sites — since function signatures and call sites must remain consistent. The reconstruction strategies are summarized in Table 2. For example, if a deleted function foo returns int, then

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

Table 2. Dependency Reconstruction Strategies for C and Java

Target

Provider

User

Reconstruction Strategy

Type / Struct

Type reference Expression Call expression

Replace with void*** Replace with (func_type) 0 Replace with (return_type) defaulta Replace with defaulta

Function C Variable / Parameter Goto label Parameter / Argument Class Java

Expression

Goto statement Delete User node Argument / Pa- Delete User node rameter Type reference Expression Call expression

Replace with Object Replace with (func_type) nullb Method Replace with (return_type) defaultc Variable / Param- Expression Replace with (expected_type) eter defaultc Parameter / Argu- Argument / Pa- Delete User node ment rameter

a For C, the default value is determined by the expected or return type: 1 for integer types,

0 for pointer types. b Java does not have first-class function types; method references are typically typed as

functional interface types. c For Java, the default value is 0 for primitive types and null for reference types.

a remaining call foo() is replaced with (int) 1, according to the reconstruction rule between Function and Call expressions in Table 2. 3.3.2 Java Source Code. For Java programs, DRReduce performs semantic analysis using PSI provided by JetBrains’ IntelliJ IDEA [5], which offers Java-specific capabilities such as type hierarchy resolution, method override detection, and reference tracking across class boundaries. The selected semantic nodes are Files, Statements, Named Nodes, and Parameters. Named Nodes are elements referenceable by name, including classes, methods, and fields. Unlike C, Java does not require forward declarations, so no declaration-definition pairs exist. Parameter declarations and their corresponding argument expressions at all call sites are grouped together, since method signatures and call sites must remain consistent. Java’s inheritance structure introduces additional semantic complexity. When a superclass is deleted, its subclasses must be updated to inherit from the grandparent, and overriding methods that reference the deleted superclass must be removed or redirected. Correctly propagating such changes across the full class hierarchy at the source-code level is beyond our current capabilities and is left for future work. The reconstruction strategies currently supported are summarized in Table 2. For example, suppose a class MyClass is deleted while the program still contains a method that uses MyClass as a parameter type, such as void foo(MyClass arg) { ... }. According to the rules in Table 2, MyClass is replaced with its supertype Object, yielding the reconstructed method signature void foo(Object arg) { ... }.

Feng et al.

Experiment Setup

4.1

Dataset

Table 3 summarizes the dataset used to evaluate DRReduce, covering bug-triggering programs in C and Java languages across multiple compilers and data sources. For C, the dataset contains 16 bug-triggering programs sourced from the Perses dataset [17], covering 10 GCC bugs and 6 Clang bugs. For Java, the dataset contains 12 programs covering 12 bugs across three compilers: 4 programs target Checker Framework bugs from Specimin [11]; 2 programs target Eclipse Java Compiler and 2 target JDK bugs, both from Perses; and an additional 4 programs target JDK bugs from newly collected data. Note that Checker Framework is a type-checking plugin for Java compilers. Several programs were excluded from the original datasets for the following reasons, as detailed in the footnotes of Table 3. First, manual inspection revealed that for 3 Clang bugs and 1 GCC bug, the reduced programs from the original reports trigger a different bug than the one reported. Second, 1 Eclipse Java Compiler bug was excluded because the compiler version required to reproduce the bug is no longer publicly archived. Third, 1 Null Away bug was excluded because it is a false negative tied to a specific location; a user query script cannot be accurately written in this case, and automatic reduction is not meaningful since such location-specific false negatives can already be reduced manually. Table 3. The bug-triggering program dataset used to evaluate DRReduce.

Program Type

Compiler

Java

#Programs

#Bugs

Data Source

GCC Clang

10 6

Perses [17]

Checker Framework

Specimin [11]

Eclipse Java Compiler JDK

2 2

Perses [17]

JDK

Newly Collected

† 3 Clang bugs and 1 GCC bug from the Perses dataset were removed upon manual inspection, which

revealed that the reduced programs from the original reports trigger a different bug than the one reported. ‡ 1 Eclipse Java Compiler bug from the Perses dataset was removed because the compiler version required to reproduce the bug is no longer publicly archived. § 1 Null Away bug from the Specimin dataset was removed because it is a location-sensitive false negative for which no general-purpose query script can be written, making automated reduction ill-defined.

4.2

Experiment Configuration

All experiments were conducted on a machine running Ubuntu 24.04.3 LTS (64-bit) with Linux kernel 6.14.0-37-generic, powered by an AMD Ryzen 9 9950X 16-core processor (32 threads) and 64 GiB of RAM. Each bug-triggering program was reduced using a single thread to ensure fair and reproducible comparisons across all tools. In our implementation of DRReduce, we adopt Perses [17] as the syntactic reducer in Stage 3. We make this choice because Perses is the foundational syntax-guided reducer upon which the other syntax-guided baselines in our evaluation (WDD [30] and CDD [28]) are built. Using the

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

same backend across all tools allows us to fairly compare the impact of DRReduce’s dependency reconstruction against the improvements that WDD and CDD make on top of Perses [17]. 4.3

Research Questions

Using the above dataset, we evaluate whether DRReduce’s effectiveness and efficiency compare with those of state-of-the-art (SOTA) program reduction approaches. Accordingly, we formulate the following three Research Questions (RQs): RQ1. How does DRReduce compare to state-of-the-art syntax-guided reduction tools in terms of reduction effectiveness and efficiency? Specifically, does DRReduce produce smaller reduced programs and require less reduction time than existing tools? Existing syntax-guided reduction tools treat syntax nodes as independent units, ignoring the semantic dependencies between them. This design choice leads to two main issues: (1) tools fail to reduce elements with mutual semantic dependencies, limiting how small the output can become; and (2) without respecting dependency ordering, tools frequently generate invalid intermediate programs, triggering unnecessary query invocations and increasing reduction time. This RQ evaluates whether DRReduce can address these shortcomings, producing smaller outputs in less time on C and Java bug-triggering programs. RQ2. How does DRReduce compare to state-of-the-art reducers that incorporate language-specific transformations in terms of reduction effectiveness and efficiency? Tools that incorporate language-specific transformations, such as CReduce and Latra, achieve exceptionally compact outputs by applying extensive, hand-crafted, semantics-aware transformations tailored to a specific language. In contrast, DRReduce relies solely on a language-agnostic strategy of dependency reconstruction, with no language-specific rules. This RQ explores whether DRReduce’s general approach incurs a measurable cost: does its simpler, uniform design yield comparable reduction quality or speed to that of highly engineered, special-purpose tools? RQ3 (Ablation). Is dependency reconstruction a necessary component of DRReduce, and what is its overall impact on effectiveness and efficiency? Dependency reconstruction ensures the compilability of intermediate results by substituting references to deleted nodes with default values. While this prevents unnecessary query invocations due to compilation failures, it also introduces additional code changes that may affect both the final program size and the time required to reach a fixpoint. This RQ isolates the contribution of dependency reconstruction by measuring its impact on both effectiveness and efficiency, and assesses whether its benefits consistently outweigh its overhead. 5 5.1

Results RQ1: Comparison between DRReduce and SOTA syntax-guided reduction tools

We compare DRReduce against three state-of-the-art syntax-guided reducers: Perses [17], WDD [30], and CDD [28]. These baselines span two generations of syntax-guided reduction: Perses (2018) establishes the grammar-based hierarchical reduction paradigm and remains the most widely adopted baseline, while WDD and CDD (2025) represent the latest advances, each improving upon the underlying delta debugging algorithms that Perses relies on. We adopt WProbDD — WDD’s stronger variant according to the original paper — in our evaluation. Detailed descriptions of each baseline are provided in Section 8 (Related Work). In our implementation of DRReduce, we adopt Perses as the syntactic reducer in Stage 3, ensuring that any improvement of DRReduce over these baselines can be cleanly attributed to the semantic dependency reconstruction in Stages 1 and 2. Table 4 presents the reduction results on C and Java bug-triggering programs. For each tool, we report the number of query script invocations (Q),

Feng et al.

Table 4. Reduction results on C and Java bug-triggering programs compared with syntax-guided reduction 𝑅 −𝑅Baseline tools. Q = number of query invocations, T = time (seconds), R = reduced size (tokens). 𝐶 = DRReduce × 𝑅Baseline 100% (negative values indicate DRReduce produces smaller outputs than the baseline). Best reduced size per bug is highlighted in green . Best time per bug is highlighted in blue .

Bug ID

Original

DRReducePerses

Perses [17]

WDD [30]

CDD [28]

C(%) w.r.t.

Perses

WDD

CDD

clang-22382 clang-22704 clang-23353 clang-25900 clang-26760 clang-27747

21068 93032 30196 78960 32958 19915

3459 2888 3763 3266 2612 2344

118 223 236 279 151 108

95 63 72 107 50 115

1445 1413 1881 1851 1805 1430

91 204 192 240 152 114

256 215 283 318 239 269

1991 1904 2569 2659 2161 2214

130 324 327 311 176 152

113 99 72 148 64 141

1998 1866 2639 2702 2227 2211

135 316 330 325 187 152

113 97 72 146 94 141

-62.9% -70.7% -74.6% -66.4% -79.1% -57.2%

-15.9% -36.4% 0.0% -27.7% -21.9% -18.4%

-15.9% -35.1% 0.0% -26.7% -46.8% -18.4%

gcc-59903 gcc-60116 gcc-61383 gcc-61917 gcc-64990 gcc-65383 gcc-66186 gcc-70127 gcc-70586 gcc-71626

57581 75224 32449 85359 16623 43942 47481 12358 14626 6133

7127 10944 7777 8307 4530 12945 5782 4228 10675 262

540 1765 2503 1698 2042 3098 2347 4186 6145 12

328 433 258 127 163 122 236 107 346 46

3139 3572 2728 2720 2683 2045 2253 1817 3568 120

747 469 2172 291 1808 4112 1090 525 1768 8

609 793 508 454 519 384 488 370 904 49

5422 5062 4185 3841 3503 2721 3097 2715 6014 249

817 651 3293 576 2022 5232 1422 941 3008 16

394 393 303 147 244 144 310 311 402 46

5208 5040 5032 3848 3516 2663 2722 2757 6422 721

832 671 3361 507 2119 4960 4999 956 3390 35

394 393 323 147 181 156 153 311 380 46

-46.1% -45.4% -49.2% -72.0% -68.6% -68.2% -51.6% -71.1% -61.7% -6.1%

-16.8% 10.2% -14.9% -13.6% -33.2% -15.3% -23.9% -65.6% -13.9% 0.0%

-16.8% 10.2% -20.1% -13.6% -9.9% -21.8% 54.2% -65.6% -8.9% 0.0%

cf-577 cf-689 cf-691 cf-4614 ecj-352665 ecj-404146 JDK-8068399 JDK-8145466 JDK-8271954 JDK-8272562 JDK-8293941 JDK-8331717

382 2328 25477 394 1142 348 447 462 1617 1537 1837 1497

782 324 209 1863 408 104 2458 936 454 118 113 67 112 48 44 193 64 75 246 25 63 111 14 40 1253 1218 199 1060 4741 124 541 1453 123 1325 5755 136

548 351 306 231 174 209 5782 4736 601 258 236 74 295 126 143 435 165 155 208 27 69 197 29 49 736 653 217 522 2357 134 363 642 144 855 2776 212

532 347 306 393 292 146 7700 4773 95 217 188 74 457 199 102 379 145 155 229 23 69 173 22 49 741 512 235 513 2688 140 486 3078 167 871 1801 212

536 356 386 290 6535 4131 235 207 444 192 382 145 228 23 172 22 770 533 498 2840 382 694 874 1840

306 146 601 74 102 155 69 49 235 140 152 212

-31.7% -50.2% -24.5% -9.5% -69.2% -51.6% -8.7% -18.4% -8.3% -7.5% -14.6% -35.8%

-31.7% -28.8% 377.9% -9.5% -56.9% -51.6% -8.7% -18.4% -15.3% -11.4% -26.3% -35.8%

-31.7% -28.8% -24.5% -9.5% -56.9% -51.6% -8.7% -18.4% -15.3% -11.4% -19.1% -35.8%

Median Mean

15625 25192

2535 3606

1438 1604

2076 2250

2105 2251

150 192

-54.8% -51.9%

-19.0% -20.7% -14.9% -19.8%

474 1448

119 154

321 938

263 320

430 1195

147 181

432 1234

reduction time in seconds (T), and the reduced program size in tokens (R). Each query script invocation validates whether the current reduced program still triggers the target compiler bug. We also report the percentage of tokens produced by DRReduce relative to those produced by the baselines (C(%) w.r.t.). Effectiveness. DRReduce consistently outperforms all three syntax-guided baselines in reduction effectiveness. Compared to Perses, DRReduce achieves a smaller reduced size on 28 out of 28 bug-triggering programs, with a mean further reduction of 51.9% (154 versus 320 tokens). Compared to WDD and CDD, DRReduce achieves a smaller reduced size on 24 out of 28 bug-triggering programs, with mean further reduction of 14.9% and 19.8% respectively. The gains are most pronounced on complex GCC bugs: gcc-65383 is reduced to 122 tokens by DRReduce, versus 384, 144, and 156 tokens by Perses, WDD, and CDD respectively (up to 3.1× smaller). DRReduce also achieves the smallest reduced size on 11 out of 12 Java bug-triggering programs. The one notable exception is cf-691, where WDD achieves 95 tokens while DRReduce produces 454. We manually inspected this case and attributed this to DRReduce’s default-value reconstruction strategy: replacing deleted references with default values likely destroys the type annotations that trigger this Checker Framework bug, leaving DRReduce at a larger local minimum. This case suggests that default-value

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

reconstruction can be counterproductive when the bug-triggering property is sensitive to the exact values or types of reconstructed expressions, motivating the same-semantics replacement strategy discussed in Section 6. Efficiency. The efficiency results are more nuanced. DRReduce is slower than Perses on most C bug-triggering programs (mean 1,448 versus 938 seconds, 54.4% overhead), due to the upfront cost of semantic analysis and dependency graph construction. However, this trend reverses on Java bug-triggering programs, where DRReduce is faster on 7 out of 12 bugs. Although DRReduce invokes the query script more frequently than the baselines in many cases, its reduction time is nonetheless lower on these programs. We attributed this to the fact that DRReduce’s semantic reduction produces smaller intermediate programs earlier in the process — by deleting large semantic nodes in early rounds, the remaining programs are cheaper to compile and evaluate. As a result, each individual query invocation takes less wall-clock time, compensating for the higher query count. Compared to WDD and CDD, DRReduce achieves faster reduction on 17 and 18 out of 28 bug-triggering programs respectively, with consistent efficiency advantages on Java programs where semantic dependencies cause the baselines to generate large numbers of invalid intermediate programs that are rejected without making progress. Summary. DRReduce achieves mean size reductions of 51.9%, 14.9%, and 19.8% over Perses, WDD, and CDD respectively, at a moderate efficiency cost on large C programs that is substantially offset on Java bug-triggering programs. These results confirm that semantic dependency reconstruction provides reduction opportunities that purely syntax-guided approaches cannot exploit. 5.2

RQ2: Comparison between DRReduce and SOTA reducers that incorporate language-specific transformations

We compared DRReduce against two state-of-the-art reducers that incorporate language-specific transformations, CReduce [13] and Latra [23]. Both incorporate hand-crafted, language-specific transformation rules that syntax-guided reducers cannot express, and represent the strongest available points of comparison for C. We restricted this comparison to C because no comparable language-specific reducer exists for Java. Detailed descriptions of each baseline are provided in Section 8. Table 5 presents the reduction results on the 16 C bug-triggering programs. Effectiveness. Despite having no language-specific transformation rules, DRReduce achieves the best reduced size on 5 bug-triggering programs (clang-22382, clang-23353, clang-26760, gcc-59903, and gcc-70127) and the second-best on 7 bug-triggering programs (clang-22704, clang-25900, gcc61917, gcc-64990, gcc-65383, gcc-66186, and gcc-70586), placing first or second on 12 out of 16 bugtriggering programs overall. The mean reduced size of DRReduce is 167 tokens, situated between CReduce (195 tokens) and Latra (157 tokens) — a 14.4% improvement over CReduce and statistically comparable to Latra. This is a notable result given that CReduce relies on more than 5,685 lines of hand-crafted C transformation code and Latra on 27 manually written rules, while DRReduce requires neither: its advantage derives entirely from language-agnostic semantic dependency reconstruction, which enables deletions that syntax-guided and template-based approaches cannot perform due to unresolved semantic dependencies. Efficiency. DRReduce achieves the best reduction time on 12 out of 16 bug-triggering programs, completing in a mean of 1,591 seconds — 3.0× faster than CReduce (4,720 seconds) and 1.1× faster than Latra (1,694 seconds). The efficiency advantage over CReduce is particularly pronounced: CReduce’s exhaustive semantic transformations require an average of 30,716 query invocations versus 5,682 for DRReduce (an 5.4× reduction), and on individual bug-triggering programs the

Feng et al.

Table 5. Reduction results on C bug-triggering programs compared with reducers that incorporate languagespecific transformations tools. Q = number of query invocations, T = time (seconds), R = reduced size (tokens). 𝑅 −𝑅Baseline 𝐶 = DRReduce × 100% (negative values indicate DRReduce produces smaller outputs than the baseline). 𝑅 Baseline

Best reduced size per bug is highlighted in green . Second best reduced size is highlighted in light green . Best time per bug is highlighted in blue .

Bug ID

Original

DRReducePerses

CReduce [13]

Latra [23]

C(%) w.r.t.

Creduce

Latra

clang-22382 clang-22704 clang-23353 clang-25900 clang-26760 clang-27747

21068 93032 30196 78960 32958 19915

3459 2888 3763 3266 2612 2344

118 223 236 279 151 108

95 63 72 107 50 115

13857 10277 9297 16775 15965 16656

1017 1111 982 1566 1274 1198

110 59 73 88 65 106

1957 1917 4932 4512 2642 2690

126 273 427 462 217 181

109 59 135 148 59 107

-13.6% 6.8% -1.4% 21.6% -23.1% 8.5%

-12.8% 6.8% -46.7% -27.7% -15.3% 7.5%

gcc-59903 gcc-60116 gcc-61383 gcc-61917 gcc-64990 gcc-65383 gcc-66186 gcc-70127 gcc-70586 gcc-71626

57581 75224 32449 85359 16623 43942 47481 12358 14626 6133

7127 10944 7777 8307 4530 12945 5782 4228 10675 262

540 1765 2503 1698 2042 3098 2347 4186 6145 12

328 433 258 127 163 122 236 107 346 46

41732 58335 34140 46557 41382 41382 36294 36482 70493 1832

3892 5248 2951 7853 6587 20184 5430 7578 8477 174

329 394 161 329 243 142 280 277 417 45

11377 11656 7717 3837 3814 2542 4526 4567 13004 167

1150 1713 4595 390 2313 4796 1816 2466 6166 13

398 366 228 87 64 116 177 109 301 42

-0.3% 9.9% 60.2% -61.4% -32.9% -14.1% -15.7% -61.4% -17.0% 2.2%

-17.6% 18.3% 13.2% 46.0% 154.7% 5.2% 33.3% -1.8% 15.0% 9.5%

Median Mean

15625 25192

4379 5682

1119 1591

119 167

35217 30716

3422 4720

152 195

4175 5116

806 1694

113 157

-21.7% -14.4%

5.3% 6.4%

wall-clock gap can be dramatic — on clang-22382, DRReduce completes in 118 seconds while CReduce requires 1,017 seconds. Summary. DRReduce matches or exceeds the effectiveness of CReduce and Latra on the majority of bug-triggering programs while substantially reducing reduction time and query invocations. These results suggest that, on programs where semantic coherence is the primary bottleneck, language-agnostic dependency reconstruction can replace much of the hand-crafted rules in reducers that incorporate language-specific transformations without sacrificing reduction quality. 5.3

RQ3: Ablation Study of Dependency Reconstruction

As dependency reconstruction in Stage 2 is the core module of DRReduce, we conducted an ablation study to evaluate its contribution to overall reduction performance. Specifically, we measured program reduction effectiveness and efficiency with and without dependency reconstruction, using only Stages 1 and 2 and excluding the syntax-guided backend of Stage 3. The reason for this choice is that isolating Stages 1 and 2 allows us to directly attribute any observed difference in effectiveness and efficiency to dependency reconstruction alone. If Stage 3 were included, its syntactic reduction would mask the individual contribution of dependency reconstruction, as improvements could be attributed to the interaction between the semantic and syntactic stages rather than to dependency reconstruction itself. Figure 6 reports results on 25 of our 28 bug-triggering programs. We exclude clang-22704 because, in the without reconstruction configuration, the reduction did not converge before our machine exhausted memory. gcc-70217 and cf-691 are omitted from the figure as their reduction times in the without reconstruction configuration (8,985 and 28,602 seconds respectively) deviate substantially from the rest of the dataset and would distort the visualization.

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

w/o

0 w/o w

10000 20000 30000 Mean

Median

STD

12936 2558

13314 1317

13237 2717

(a) Number of query invocations

0 2000 4000 6000 8000 w/o w

Mean

Median

STD

2682 1107

1100 1052

5610 1396

(b) Reduction time (seconds)

0 w/o w

2500

5000

7500

Mean

Median

STD

2206 990

1335 595

2323 1076

Fig. 6. Ablation study of dependency reconstruction across all 28 bug-triggering programs (w: with dependency reconstruction; w/o: without reconstruction).

Efficiency. Without reconstruction, reduction requires on average 12,936 query invocations (median 13,314) and 2,682 seconds (median 1,100). With reconstruction, query invocations drop to an average of 2,558 (median 1,317) and reduction time decreases to an average of 1,107 seconds (median 1,052) — representing a 80.2% reduction in query invocations and a 58.7% reduction in time. A Mann–Whitney U test confirms that the difference is statistically significant for query invocations (𝑈 = 232.00, 𝑝 = 0.011) and marginally significant for reduction time (𝑈 = 286.00, 𝑝 = 0.087). These gains confirm that dependency reconstruction substantially improves efficiency by producing semantically valid intermediate programs that the oracle accepts, thereby avoiding the large numbers of unnecessary query invocations caused by semantically broken intermediates that syntax-guided reduction alone would generate. Effectiveness. Dependency reconstruction also yields a substantial improvement in final reduced size, with the mean token count decreasing from 2,206 to 990 tokens (55.1% reduction) and the median from 1,335 to 595 tokens (55.4% reduction). A Mann–Whitney U test confirms that this difference is marginally significant (𝑈 = 272.00, 𝑝 = 0.055). This confirms that dependency reconstruction not only prevents wasted query invocations, but also unlocks reduction opportunities. Summary. Dependency reconstruction reduces query invocations by 80.2%, reduction time by 58.7%, and final token count by 55.1% on average, confirming that it is a central and highly effective component of DRReduce. The consistent gain across both efficiency and effectiveness indicates that semantic coherence breakage is a fundamental bottleneck in language-agnostic program reduction — one that cannot be addressed by refining syntax-guided search alone. 6

Discussion

Applying DRReduce to Intermediate Representations (IRs). We believe that DRReduce may be especially promising for IRs such as LLVM bitcode. In several bugs, such as clang-22382, we observed that developers provided reduced LLVM IR programs rather than reduced C source code, suggesting that IR-level reduction is already a practical option when source-level reduction is insufficient. We hypothesize that applying DRReduce to LLVM IR could yield significantly higher efficiency than to source code for two reasons. First, IRs are typically designed with explicit

Feng et al.

representations of semantic dependencies (e.g., LLVM’s use-def chains and basic-block structure are part of the IR specification itself), so Stage 1 of DRReduce can be replaced with a direct translation from IR to dependency graph rather than requiring static analysis. Second, the dependency reconstruction rules required for an IR are typically smaller in number than for a source language, since IRs use a smaller set of constructs and a more regular type system. This is particularly relevant for reduction of bug-triggering inputs produced by fuzzers, which often emit programs in IR form directly. A full evaluation of DRReduce on IRs is left for future work. Aligning Semantics-aware Reduction with Required Program Properties. We believe that when introducing semantics-aware reduction, it is essential to consider the connection between the program properties that need to be preserved and the program semantics. For instance, the reduction methods required for programs that trigger compiler crashes differ significantly from those that cause miscompilations. The former does not require the intermediate reduced programs to be executable, whereas the latter necessitates a certain degree of executability. Note that we do not claim full executability here, as miscompilations can manifest in two ways: a correctly compiled program encountering a runtime error or incorrect output upon completion; both scenarios require specific analysis. Designing reconstruction operators tailored to the semantics of each property could yield more effective reduction than the uniform default-value strategy used by DRReduce, and is a promising direction for future work. Evaluating Reduction Effectiveness Beyond Token Count. Following prior work [17, 28, 30], we evaluate reduction effectiveness using token count, which is the standard metric in the program reduction literature. However, we have found that programs with a similar number of tokens can still exhibit significant differences in semantic complexity or readability. In some cases, a program with fewer tokens may actually be more complex than one with more tokens. For example, consider a continuous nested call foo(bar(foo())) versus a sequence of calls introducing temporary variables, such as int f = foo(); int b = bar(f); foo(b);. Although the former has fewer tokens than the latter, its readability is arguably lower. This concern has been discussed in recent work [20], which proposes structure-form conversion as one approach to producing more readable reduced programs. Developing reduction metrics that better reflect human debugging effort is an open problem in the field, and one to which we believe DRReduce could contribute, since its dependency-graph-based design enables structurally-aware manipulation of the reduced program rather than only size-based optimization. 7

Threats to Validity

The primary threats to the validity of our findings are discussed in this section in accordance with established guidelines for empirical software engineering research [19]. Internal validity. To ensure fair comparison with baselines, all tools (DRReduce, Perses, WDD, CDD, CReduce, and Latra) are run from their publicly released implementations on the same machine, under single-thread execution. We acknowledge that further tuning of the baselines’ configurations could potentially improve their performance, but we do not perform such tuning to keep the comparison neutral. External validity. DRReduce currently supports C and Java; while we argue in Section 3.3 that the design generalizes to any programming language with a static type system, we have not empirically evaluated this claim. Evaluating DRReduce on additional languages and intermediate representations remains future work. Construct validity. We use token count as our primary metric for reduction effectiveness, following prior work [17, 28, 30], but token count is an imperfect indicator of human debugging effort, as discussed in Section 6. Our efficiency metric, wall-clock time, is sensitive to system load

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

and concurrent processes; we mitigate this threat by running all experiments on our machine with single-thread execution. 8

Related Work

We discuss language-agnostic reducers, reduction with language-specific transformations, and approaches for avoiding or repairing invalid intermediate programs, and highlight how our work differs from these existing approaches. 8.1

Language-agnostic Reduction

Delta Debugging (DDMin) [25] reduces failure-inducing programs by iteratively deleting code fragments while preserving the failure-triggering behavior. However, text-based DDMin often generates many invalid intermediate programs when applied to structured inputs such as source code. Hierarchical Delta Debugging (HDD) [10] addresses this issue by performing reductions over Abstract Syntax Trees (ASTs) rather than raw text, ensuring that intermediate candidates remain syntactically valid. Perses [17] further extends this idea by integrating grammars with delta debugging and applying grammar-preserving transformations to systematically minimize programs without violating syntactic constraints. Building on Perses, Vulcan [22] goes beyond 1-minimality through three additional operations: smaller-structure replacement, identifier replacement, and subtree replacement. T-Rec [21] complements tree-level reductions with fine-grained lexical reduction that exploits sub-token reduction opportunities. PPR [29] extends program reduction to a pairwise setting by simultaneously minimizing both a bug-triggering program and a passing variant while minimizing their differences, thereby highlighting the bug-inducing change. Another line of work focuses on improving the underlying delta debugging algorithm. ProbDD [18] replaces the traditional delta debugging strategy with a probabilistic model that estimates the likelihood of each element being failure-relevant and selects deletion subsets that maximize the expected number of removable elements per attempt. CDD [28] simplifies ProbDD by showing that its probabilities can be analytically precomputed as counters, achieving comparable performance with substantially lower complexity. WDD [30] augments Perses by assigning weights to syntax elements based on token count, prioritizing the deletion of smaller and more likely irrelevant elements. 8.2

Reduction with Language-specific Transformations

C-Reduce [13] is a language-specific reducer for C programs that applies more than 30 compilerlike source-to-source transformations, including simultaneously removing function parameters and their corresponding call-site arguments, inlining function bodies, and other semantics-aware simplifications. ReduKtor [15] adopts a hybrid approach for Kotlin compiler testing by combining program slicing, hierarchical delta debugging, and language-specific transformations. However, its reliance on manually engineered Kotlin-specific transformations limits portability to other languages, reflecting the trade-off between effectiveness and generality that DRReduce aims to address. More recent work has explored ways to reduce the engineering burden of language-specific reducers. LPR [27] combines the language generality of reducers such as Perses with languagespecific semantics inferred by Large Language Models (LLMs), demonstrating effectiveness on C, Rust, and JavaScript programs. Latra [23] bridges the gap between language-agnostic and languagespecific reducers by augmenting a language-agnostic reducer with user-defined transformations expressed as match-rewrite template pairs in a domain-specific language. For C programs, Latra

Feng et al.

implements 27 transformation rules and achieves results statistically comparable to C-Reduce while requiring up to 34× fewer lines of code. 8.3

Avoiding Invalid Intermediate Programs

Several studies address the same fundamental challenge targeted by DRReduce: avoiding invalid intermediate programs that significantly increase reduction cost. J-Reduce [6, 7] uses propositional logic to specify dependencies and formulates Java bytecode reduction as a logical satisfiability problem, ensuring that intermediate programs remain semantically sound. However, J-Reduce derives dependencies from Java bytecode semantics and is therefore tightly coupled to a specific language, whereas DRReduce employs a language-agnostic dependency model. In addition, DRReduce proactively reconstructs broken dependencies during reduction, while J-Reduce primarily prevents invalid reductions through dependency constraints. Gharachorlu and Sumner [4] train a machine learning model on syntactic features to predict which deletion candidates are likely to remain semantically valid. GReduce [14] takes a different direction: instead of reducing the generated program itself, it minimizes the execution trace of the generator that produces the program, thereby ensuring program validity inherently. Specimin [11], the source of the Checker Framework benchmarks used in our evaluation, performs static program reduction by exploiting the modularity of type rules to compute a slice that preserves the typechecker’s behavior, without running the typechecker on each candidate. Specimin is more suitable for bugs where the error messages are more explicit, while DRReduce is a dynamic reducer that targets any property a query script can express, including compiler crashes and miscompilations. 8.4 Conclusive Summary DRReduce strikes a balance between fully language-agnostic approaches and reduction techniques based on language-specific transformations. While remaining language-agnostic, it introduces a lightweight semantic layer that repairs broken dependencies during reduction. This enables DRReduce to recover much of the semantic coherence achieved by language-specific reducers without requiring extensive per-language engineering. In addition, DRReduce complements existing approaches that aim to predict or prevent invalid intermediate programs by instead proactively repairing invalid intermediates through dependency reconstruction. 9

Conclusions

This paper presents DRReduce, a novel program reduction approach that enhances syntax-guided program reduction with dependency reconstruction. By repairing broken dependencies through default-value reconstruction, DRReduce preserves the semantic validity of intermediate programs and unlocks reduction opportunities that purely syntax-guided approaches cannot exploit. Our evaluation on real-world bug-triggering C and Java programs shows that (1) DRReduce produces significantly smaller reduced programs than state-of-the-art syntax-guided reducers with competitive efficiency, and (2) DRReduce achieves results comparable to reducers that incorporate language-specific transformations without using any such transformations itself, with improved efficiency overall. An ablation study further confirms that dependency reconstruction is the key contributor to DRReduce’s performance, reducing query invocations by 80.2% and final token count by over 55.1% on average. In the next step, we plan to extend DRReduce along two directions. First, we will broaden its applicability by supporting additional languages and intermediate representations such as LLVM IR, where semantic dependencies are already explicit and reduction may be more efficient. Second, we will explore more sophisticated dependency reconstruction strategies, including same-semantics

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

replacement that preserves program behavior, to address the limitation observed on bugs sensitive to specific values or types. Data Availability Our data is publicly available at https://github.com/XYZboom/DRReduceData, which includes all bug-triggering programs, the programs reduced using different baselines, and the results of ablation experiments. Acknowledgments This work has been partially supported by the National Natural Science Foundation of China (NSFC) with Grant No. 92582203. References [1] Stefanos Chaliasos, Thodoris Sotiropoulos, Diomidis Spinellis, Arthur Gervais, Benjamin Livshits, and Dimitris Mitropoulos. 2022. Finding typing compiler bugs. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI). ACM, 183–198. [2] GNU Compiler Collection Contributors. 2026. Reporting Bugs. https://gcc.gnu.org/bugs/. [3] Qiong Feng, Xiaotian Ma, Ziyuan Feng, Marat Akhin, Wei Song, and Peng Liang. 2025. Finding Compiler Bugs through Cross-Language Code Generator and Differential Testing. Proceedings of the ACM on Programming Languages 9, OOPSLA2 (2025), 2843–2869. [4] Golnaz Gharachorlu and Nick Sumner. 2021. Leveraging models to reduce test cases in software repositories. In Proceedings of the 18th IEEE/ACM International Conference on Mining Software Repositories (MSR). IEEE, 230–241. [5] JetBrains. 2024. Program Structure Interface. https://plugins.jetbrains.com/docs/intellij/psi.html [6] Christian Gram Kalhauge and Jens Palsberg. 2019. Binary reduction of dependency graphs. In Proceedings of the 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE). ACM, 556–566. [7] Christian Gram Kalhauge and Jens Palsberg. 2021. Logical bytecode reduction. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI). ACM, 1003–1016. [8] Christopher Lidbury, Andrei Lascu, Nathan Chong, and Alastair F Donaldson. 2015. Many-core compiler fuzzing. ACM SIGPLAN Notices 50, 6 (2015), 65–76. [9] LLVM Project. 2026. How to Submit a Bug Report. https://llvm.org/docs/HowToSubmitABug.html. [10] Ghassan Misherghi and Zhendong Su. 2006. HDD: Hierarchical delta debugging. In Proceedings of the 28th International Conference on Software Engineering (ICSE). ACM, 142–151. [11] Loi Ngo Duc Nguyen, Tahiatul Islam, Theron Wang, Sam Lenz, and Martin Kellogg. 2025. Static Program Reduction via Type-Directed Slicing. Proceedings of the ACM on Software Engineering 2, ISSTA (2025), 2068–2090. [12] Diego Trevi no Ferrer. 2019. LLVM-Reduce for testcase reduction. https://llvm.org/devmtg/2019-10/talk-abstracts. html#tech22. [13] John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. 2012. Test-case reduction for C compiler bugs. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM, 335–346. [14] Luyao Ren, Xing Zhang, Ziyue Hua, Yanyan Jiang, Xiao He, Yingfei Xiong, and Tao Xie. 2025. Validity-Preserving Delta Debugging via Generator Trace Reduction. ACM Transactions on Software Engineering and Methodology 34, 3 (2025), 1–33. [15] Daniil Stepanov, Marat Akhin, and Mikhail Belyaev. 2019. ReduKtor: How We Stopped Worrying About Bugs in Kotlin Compiler. In Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 317–326. [16] Chengnian Sun, Vu Le, and Zhendong Su. 2016. Finding compiler bugs via live code mutation. In Proceedings of the 31st ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). ACM, 849–863. [17] Chengnian Sun, Yuanbo Li, Qirun Zhang, Tianxiao Gu, and Zhendong Su. 2018. Perses: Syntax-guided program reduction. In Proceedings of the 40th International Conference on Software Engineering (ICSE). ACM, 361–371. [18] Guancheng Wang, Ruobing Shen, Junjie Chen, Yingfei Xiong, and Lu Zhang. 2021. Probabilistic Delta Debugging. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE). ACM, 881–892.

Feng et al.

[19] Claes Wohlin, Per Runeson, Martin Höst, Magnus C. Ohlsson, Björn Regnell, and Anders Wesslén. 2012. Experimentation in Software Engineering. Springer. [20] Zhenyang Xu, Yongqiang Tian, Mengxiao Zhang, and Chengnian Sun. 2025. Boosting Program Reduction with the Missing Piece of Syntax-Guided Transformation. Proceedings of the ACM on Programming Languages 9, OOPSLA2 (2025), 86–112. [21] Zhenyang Xu, Yongqiang Tian, Mengxiao Zhang, Jiarui Zhang, Puzhuo Liu, Yu Jiang, and Chengnian Sun. 2025. T-rec: Fine-grained language-agnostic program reduction guided by lexical syntax. ACM Transactions on Software Engineering and Methodology 34, 2 (2025), 1–31. [22] Zhenyang Xu, Yongqiang Tian, Mengxiao Zhang, Gaosen Zhao, Yu Jiang, and Chengnian Sun. 2023. Pushing the limit of 1-minimality of language-agnostic program reduction. Proceedings of the ACM on Programming Languages 7, OOPSLA1 (2023), 636–664. [23] Zhenyang Xu, Yiran Wang, Yongqiang Tian, Mengxiao Zhang, and Chengnian Sun. 2025. Latra: A Template-Based Language-Agnostic Transformation Framework for Effective Program Reduction. In Proceedings of the 40th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2274–2285. [24] Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and understanding bugs in C compilers. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM, 283–294. [25] Andreas Zeller and Ralf Hildebrandt. 2002. Simplifying and isolating failure-inducing input. IEEE Transactions on Software Engineering 28, 2 (2002), 183–200. [26] Jiang Zhang, Shuai Wang, Manuel Rigger, Pinjia He, and Zhendong Su. 2021. SANRAZOR: Reducing Redundant Sanitizer Checks in C/C++ Programs. In Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI). USENIX Association, 479–494. [27] Mengxiao Zhang, Yongqiang Tian, Zhenyang Xu, Yiwen Dong, Shin Hwei Tan, and Chengnian Sun. 2024. LPR: Large language models-aided program reduction. In Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA). ACM, 261–273. [28] Mengxiao Zhang, Zhenyang Xu, Yongqiang Tian, Xinru Cheng, and Chengnian Sun. 2025. Toward a Better Understanding of Probabilistic Delta Debugging. In Proceedings of the 47th International Conference on Software Engineering (ICSE). ACM, 2024–2035. [29] Mengxiao Zhang, Zhenyang Xu, Yongqiang Tian, Yu Jiang, and Chengnian Sun. 2023. PPR: Pairwise Program Reduction. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE). ACM, 338–349. [30] Xintong Zhou, Zhenyang Xu, Mengxiao Zhang, Yongqiang Tian, and Chengnian Sun. 2025. WDD: Weighted Delta Debugging. In Proceedings of the 47th IEEE/ACM International Conference on Software Engineering (ICSE). IEEE, 1592– 1603.

DRReduce: Enhancing Syntax-Guided Program Reduction with Dependency Reconstruction

Related documents