PaperlayerView exact revision on arXiv

Source-linked AI summary

KNOD: Domain Knowledge Distilled Tree Decoder for Automated Program Repair

Nan Jiang, Thibaud Lutellier, Yiling Lou, Lin Tan, Dan Goldwasser, Xiangyu Zhang

arXiv:2302.01857v3cs.SEcs.AI

TL;DR

DL models generate a large portion of uncompilable and incorrect patches –,; inference-only parsing or type checking still leaves as high as 91% uncompilable and incorrect,. KNOD directly generates patched-code ASTs with a three-stage decoder and uses logic rules to refine teacher-student distributions during training and inference. KNOD fixes 72 bugs on Defects4J v1.2, outperforming existing APR tools, and fixes the most bugs on QuixBugs (25) and Defects4J v2.0 (50).

  • Problem

    DL models generate a large portion of uncompilable and incorrect patches –,; inference-only parsing or type checking still leaves as high as 91% uncompilable and incorrect,.

    Source: §I · p. 1

  • Method

    KNOD directly generates patched-code ASTs with a three-stage decoder and uses logic rules to refine teacher-student distributions during training and inference.

    Source: §I · pp. 1–2

  • Results

    KNOD fixes 72 bugs on Defects4J v1.2, outperforming existing APR tools, and fixes the most bugs on QuixBugs (25) and Defects4J v2.0 (50).

    Source: §I · p. 2

  • Takeaways & Limitations

    Across three benchmarks, KNOD fixes 147 bugs with perfect fault localization, and ablations support contributions from both proposed components.

    Source: §VII · p. 11

    KNOD does not handle multi-hunk bugs well and depends on fault-localization accuracy.

    Source: §V · p. 11

Abstract

from arXiv · show

Automated Program Repair (APR) improves software reliability by generating patches for a buggy program automatically. Recent APR techniques leverage deep learning (DL) to build models to learn to generate patches from existing patches and code corpora. While promising, DL-based APR techniques suffer from the abundant syntactically or semantically incorrect patches in the patch space. These patches often disobey the syntactic and semantic domain knowledge of source code and thus cannot be the correct patches to fix a bug. We propose a DL-based APR approach KNOD, which incorporates domain knowledge to guide patch generation in a direct and comprehensive way. KNOD has two major novelties, including (1) a novel three-stage tree decoder, which directly generates Abstract Syntax Trees of patched code according to the inherent tree structure, and (2) a novel domain-rule distillation, which leverages syntactic and semantic rules and teacher-student distributions to explicitly inject the domain knowledge into the decoding procedure during both the training and inference phases. We evaluate KNOD on three widely-used benchmarks. KNOD fixes 72 bugs on the Defects4J v1.2, 25 bugs on the QuixBugs, and 50 bugs on the additional Defects4J v2.0 benchmarks, outperforming all existing APR tools.

I. INTRODUCTION

KNOD addresses invalid patches in deep-learning program repair by directly generating patch ASTs and distilling syntax and semantic rules into decoding. It evaluates the approach on three benchmarks.

I. INTRODUCTION

  • Invalid patches dominate DL-based APR [5],,,, and inference-only parsing or type checking still leaves up to 91% of patches uncompilable or incorrect,.The paper argues that syntactic and semantic rules should also be enforced during training.Source: §I · p. 1
  • 72 bugs on Defects4J v1.2—8 more than the strongest DL-based and 19 more than non-DL-based APR techniques; KNOD also fixes the most bugs: 25 on QuixBugs and 50 on Defects4J v2.0.The evaluation covers three widely used benchmarks.Source: §I · p. 2

A. Overview

  • For a buggy function and location, KNOD normalizes identifiers, builds an ASG, decodes a normalized patch AST, then reconstructs concrete patched code.The decoded AST is converted to a patch in normal form before abstract tokens are replaced with concrete identifiers.Source: A. Overview · p. 2
  • KNOD’s parent, edge, and node decoders generate patched-code ASTs incrementally from root to children, explicitly representing tree structure.The decoder emits one edge and node at a time, allowing fine-grained control over generated trees.Source: §I · p. 1, A. Overview · p. 2
  • First-order-logic syntax and semantic rules refine teacher-student distributions, adding a loss during training and distilling invalid generations during inference.The training loss penalizes ASTs that violate grammar or type rules.Source: §I · p. 2, A. Overview · p. 3

B. Data Preprocessing and Extraction

KNOD normalizes identifiers before representing code as an Abstract Syntax Graph, which adds sibling connections to AST edges and labels those edges with their meanings.

B. Data Preprocessing and Extraction

  • KNOD replaces identifiers with normalized representations and records mappings so abstract identifiers can later be reconstructed as concrete code identifiers.Identifiers occurring only in the patch are mapped to special unknown-identifier placeholders.Source: B. Data Preprocessing and Extraction · p. 3
  • An Abstract Syntax Graph retains AST nodes and edges while adding edges between sibling nodes to bring them closer for learning.These additional sibling edges help the encoder but are not generated by the decoder because they can be added to a generated AST.Source: B. Data Preprocessing and Extraction · pp. 3–4
  • KNOD labels AST edges explicitly to distinguish relations such as type and declarators, providing information beyond node labels.The passage gives the example that a type edge can help the decoder focus on type nodes rather than an invalid function token.Source: B. Data Preprocessing and Extraction · p. 4

C. Encoder

KNOD encodes normalized buggy functions with graph-transformer attention over node and graph structure, then generates patches as ASTs through iterative parent, edge, and node decisions.

C. Encoder

  • The encoder represents the input ASG with a pre-order node sequence, an adjacency matrix carrying edge labels, and a buggy-location sequence marking buggy versus non-buggy nodes.It embeds node, edge, and location information along with positional embeddings, then applies sequence and ASG self-attention.Source: C. Encoder · pp. 4–5

D. Novelty 1: Three-Stage Tree Decoder

  • The three-stage decoder iteratively selects a parent, generates an edge and its label, then generates a child node, directly constructing an AST.This design addresses the difficulty of decoding labeled ASTs for modern languages such as Java.Source: D. Novelty 1: Three-Stage Tree Decoder · p. 5

1) Parent Decoder:

  • At each decoding step, the parent decoder uses encoder outputs and the partially generated AST to select an existing node as the parent for a new child.Its attention includes dependencies between patch-AST nodes and between patch and input buggy-AST nodes.Source: 1) Parent Decoder · p. 5

2) Edge Decoder:

The edge decoder conditions on the selected parent to predict the label of the edge connecting that parent to the child being generated.

2) Edge Decoder:

  • The edge decoder combines each node’s hidden state with the hidden state of its predicted parent through a parent-state fusion layer.The fusion layer uses a trainable parameter.Source: 2) Edge Decoder · p. 5
  • The edge decoder processes fused states through attention modules and an edge generator that assigns probabilities to possible edge labels.The attention modules include sequence self-attention, ASG self-attention, and encoder-decoder attention.Source: 2) Edge Decoder · p. 5
  • The label with the highest predicted probability is selected for the edge connecting the located parent to the child node to be generated.The predicted label depends on the parent because different parent-node types call for different edge labels.Source: 2) Edge Decoder · p. 5

3) Node Decoder:

The node decoder uses the preceding edge-decoder output, predicted parent, and edge label to generate a child node; syntax-rule categories specify edge multiplicities for decoding parents and edges.

3) Node Decoder:

  • The node decoder uses the edge-decoder hidden states, predicted parent, and predicted edge label to generate a child node.Its architecture includes a parent-edge state fusion layer, attention modules, and a node generator.Source: 3) Node Decoder · pp. 5–6
  • The syntax-rule table distinguishes required, required+, optional, and optional* edges by whether each label occurs exactly once, at least once, at most once, or any number of times.The table presents javalang syntax rules used to design first-order logic rules for decoding parents and edges.Source: Table I · p. 6
  • The node generator assigns probabilities to possible node labels and generates the node with the highest probability.The generator maps hidden states to a distribution over possible nodes.Source: 3) Node Decoder · p. 6

E. Novelty 2: Domain-Rule Distillation

KNOD distills syntactic and semantic domain rules into teacher–student distributions that guide AST decoding during training and inference. These rules shape parent, edge, and node probabilities, while an added loss trains the decoder against the rule-informed distributions.

E. Novelty 2: Domain-Rule Distillation

  • Domain-rule distillation represents syntax and semantics as logic rules, uses them to create teacher–student distributions, and adds a loss to guide valid AST generation during training and inference.The rules shape the decoding procedure, rather than being applied only to filter generated patches.Source: E. Novelty 2: Domain-Rule Distillation · p. 6
  • Syntactic rules classify possible parents and edges so required edges are generated, optional ones remain possible, and completed nodes cannot generate more edges.For example, Rule 1 requires a node with a missing required edge to be selected as parent and that edge to be generated.Source: E. Novelty 2: Domain-Rule Distillation · p. 6
  • Semantic rules use types of accessible identifiers across the buggy program to restrict generated nodes to those compatible with the expected type.For function arguments, compatibility includes matching types and subtypes.Source: E. Novelty 2: Domain-Rule Distillation · p. 7
  • Rule-informed teacher distributions raise required choices, preserve optional choices, and zero invalid ones before renormalization.For MemberRef, the example raises the required member edge to 0.77 after renormalization while retaining the optional qualifier edge at 0.23.Source: E. Novelty 2: Domain-Rule Distillation · p. 7
  • The training objective combines ground-truth cross-entropy with an added loss aligning student distributions to teacher distributions.Minimizing the objective is intended to help models generate syntactically and semantically correct ASTs.Source: E. Novelty 2: Domain-Rule Distillation · pp. 7–8

F. Training and Inference

KNOD trains multiple models on buggy-function ASGs and patched-code ASTs, then uses their generated patches during inference. It selects models by validation loss and ranks their candidate ASTs using ranks and average probabilities.

F. Training and Inference

  • Training maps normalized buggy-function ASGs to normalized patched-code ASTs using paired examples.KNOD selects the top-k models by validation loss from models trained with randomly chosen hyperparameters.Source: F. Training and Inference · p. 8
  • KNOD uses ensemble learning to train multiple models with varied randomly chosen hyperparameters, increasing the diversity of learned fix patterns.Examples of varied hyperparameters include encoder and decoder block counts and hidden-state dimensions.Source: F. Training and Inference · p. 8
  • At inference, each selected model generates normalized patched-code ASTs, which KNOD ranks using their ranks and average probabilities.Source: F. Training and Inference · p. 8

G. Patch Generation and Validation

KNOD reconstructs generated ASTs as concrete patches by restoring normalized tokens and resolving unknown tokens through type analysis. It validates patches against tests and stops when a patch meets either stated plausibility criterion.

G. Patch Generation and Validation

  • KNOD converts generated ASTs to normalized source code and replaces normalized tokens with their recorded concrete identifiers to form patches.For example, VAR3 and FUNC13 are reconstructed as rhsContext and getContextForNoInOperator.Source: G. Patch Generation and Validation · p. 8
  • For an unknown token, KNOD analyzes its parent and sibling AST nodes, then substitutes all concrete identifiers that satisfy inferred constraints such as data type.Source: G. Patch Generation and Validation · p. 8
  • Validation stops when a patch passes all tests, or passes all originally passed tests and at least one originally failed test.Source: G. Patch Generation and Validation · p. 8

III. EXPERIMENT SETUP

The evaluation compares KNOD with existing APR techniques, studies its components, and examines correct-patch ranking. It uses three Java bug benchmarks and training data mined from open-source projects.

III. EXPERIMENT SETUP

  • The evaluation asks how KNOD compares with existing APR techniques, what each component contributes, and how it ranks correct patches.Source: §III · p. 8

A. Datasets

  • Training data comprises 576,002 buggy-program and developer-patch pairs, split into 90% training and 10% validation sets.The data is mined from open-source GitHub Java projects, excluding projects in or cloned from Defects4J.Source: A. Datasets · p. 8
  • The benchmarks are Defects4J v1.2 with 393 bugs, Defects4J v2.0 with 444 additional bugs, and QuixBugs with 40 Java bugs.Source: A. Datasets · p. 8

B. Evaluated Techniques

  • Comparisons include heuristic- and template-based SimFix and TBar, six DL-based APR tools, and KNOD variants that remove or replace decoder and distillation components.The variants replace the tree decoder with a sequential decoder or omit distillation during training or inference.Source: B. Evaluated Techniques · p. 8

C. Experimental Procedure

With perfect fault localization, KNOD fixes more bugs than compared tools across three benchmarks; with spectrum-based localization, it leads on two and ranks second on Defects4J v1.2. The evaluation also reports manual correctness checks and validity boundaries involving benchmark coverage and fault localization.

C. Experimental Procedure

  • The evaluation manually checks plausible patches for semantic equivalence to developer patches, with two participants reaching 92.1% agreement before resolving disagreements through discussion.Fault localization is tested under perfect and Ochiai spectrum-based settings; the evaluation uses a five-hour validation limit.Source: C. Experimental Procedure · pp. 8–9

D. Threats to Validity

  • The authors identify external-validity limits from the evaluated benchmarks, which cannot guarantee generalizability to other benchmarks; evaluation on more benchmarks and languages remains future work.The study covers three widely used benchmarks with up to 877 real-world Java bugs.Source: D. Threats to Validity · p. 9

A. RQ1: Effectiveness and Generalizability

  • With perfect fault localization, KNOD fixes 72 bugs on Defects4J v1.2, 50 on Defects4J v2.0, and 25 on QuixBugs, outperforming all compared techniques.On Defects4J v1.2, it fixes 8 and 19 more bugs than the best DL-based and non-DL-based approaches, respectively.Source: Table III · p. 9, A. RQ1: Effectiveness and… · p. 9
  • With spectrum-based localization, KNOD fixes the most bugs on Defects4J v2.0 and QuixBugs, and the second most on Defects4J v1.2, ahead of RewardRepair.The reported counts are 24 and 23 on Defects4J v2.0 and QuixBugs, and 38 on Defects4J v1.2 versus RewardRepair’s 29.Source: Table IV · p. 9, A. RQ1: Effectiveness and… · pp. 9–10
  • KNOD uniquely fixes 12 bugs alongside TBar, CURE, and Recoder on Defects4J v1.2, and 21 versus RewardRepair and 35 versus CURE on Defects4J v2.0.The authors describe KNOD as complementary to existing APR tools.Source: Figure 4 · p. 9, A. RQ1: Effectiveness and… · p. 10
  • KNOD averages 12.8 seconds to generate one thousand candidate patches for a bug on one NVIDIA RTX 2080 TI GPU.Source: A. RQ1: Effectiveness and… · p. 10

B. RQ2: Ablation Study

KNOD’s correct fixes rank ahead of CURE and RewardRepair across candidate budgets, while ablations report gains from its tree decoder and domain-rule distillation. The study also reports effects on patch compilation and distinguishes training-phase from inference-only distillation.

B. RQ2: Ablation Study

  • The sequential KNOD-decoder produces many more uncompilable patches, while domain-rule distillation during training and inference improves compilation rates.The authors attribute the sequential decoder’s compilation result to its failure to learn code syntax and semantics well.Source: B. RQ2: Ablation Study · p. 10
  • KNOD-distInf’s superiority to KNOD-distTrain supports training-phase domain-rule distillation as more effective than considering domain knowledge only at inference.Source: B. RQ2: Ablation Study · p. 10
  • On Defects4J v1.2, KNOD fixes 16 more bugs than KNOD-decoder, 10 more than KNOD-distTrain, and 3 more than KNOD-distInf.Source: Table V · p. 10, B. RQ2: Ablation Study · p. 10

C. RQ3: Ranking

  • Across top-10 to top-2000, KNOD generates more correct fixes than CURE and RewardRepair; on Defects4J v2.0, top-200 yields 37 versus 19 for Recoder.The authors report that KNOD fixes the most bugs across candidate-validation budget settings.Source: Figure 6 · p. 10, C. RQ3: Ranking · p. 11

V. LIMITATION

KNOD is limited on multi-hunk bugs and depends on fault-localization accuracy. The paper positions its explicit tree decoder and domain-rule distillation among DL-based repair and code-generation approaches, and reports results across three benchmarks.

V. LIMITATION

  • KNOD does not fix multi-hunk bugs well, although it handles some relatively simple cases, and its performance depends on fault-localization accuracy.The authors identify fault localization as an orthogonal bottleneck for multi-hunk repair and note that these limitations are shared by most DL-based APR techniques.Source: §V · p. 11

A. DL-based APR

  • Unlike approaches generating ASTs or edits from production rules, KNOD directly generates patch ASTs with an explicit tree structure and combines this with domain-rule distillation.The paper describes the tree structure as forcing the model to capture code structure.Source: A. DL-based APR · p. 11

B. DL-based Code Generation

VII. CONCLUSION

  • With perfect fault localization, KNOD fixes 147 bugs across three benchmarks, and the ablation study supports contributions from both novelties.Source: §VII · p. 11
Loading 2302.01857v3…