Quality Evaluation Method of Automatic Software Repair Using Syntax Distance Metrics

Yukun Dong, Daolong Tang, Xiaotong Cheng, Yufei YangSymmetry 2022 · DOI

TL;DR

This paper introduces a novel method for evaluating the quality of automatically generated software patches by measuring their "syntax distance" from the original buggy code. This approach helps developers prioritize correct patches from the many plausible but incorrect ones produced by current repair tools, significantly improving efficiency.

What Problem Does This Paper Address?

Automatic Program Repair (APR) tools aim to fix software bugs automatically, saving developers time and effort. However, a major challenge is that existing APR tools often generate numerous "plausible" patches that pass all available test cases but still contain semantic or syntactic defects. Developers then face the arduous task of manually sifting through these plausible patches to find the truly correct ones, which can be more time-consuming than fixing the bug themselves. This paper addresses the critical need for a reliable way to evaluate and rank these generated patches, reducing the burden on human developers.

Methods

The core of this paper is a patch quality evaluation method based on syntax distance metrics. This method quantifies the difference between a buggy program and a patched program using four key features:

  • Variable Similarity: Measures how similar the variables and constants are between the buggy and repaired code segments.
  • Expression Similarity: Assesses the similarity of expressions, aiming to find repair ingredients that are functionally equivalent to those in the original code. This is done using longest common subsequence (LCS) on tokenized expressions.
  • Structure Similarity: Compares the control flow structures (loops, conditionals, returns) of the buggy and repaired statements.
  • Repair Location: Considers the position of the patch within the program's error propagation chain, assuming earlier patches in the chain are more likely to be correct.

These four features are combined to calculate a syntax distance score. The paper then defines different formulas for combining these scores based on the type of patch operation (modification, insertion, deletion). For modifications, all four features are used. For insertions, variable similarity is omitted. For deletions, expression and structure similarity are omitted. A higher syntax distance generally indicates a higher quality patch.

Datasets

The evaluation was performed on 368 patches generated by multiple well-known automatic program repair tools, including jKali, Nopol, SimFix, DynaMoth, and CapGen. The benchmark used was Defects4J, a widely recognized collection of real-world Java bugs.

Key Insights and Ideas

  • Syntax Distance as a Proxy for Quality: The paper posits that a greater "syntax distance" between the original buggy code and the patched code, when measured across specific features, is a strong indicator of a correct patch. This is counter-intuitive to some extent, as one might expect minimal changes, but the authors argue it reflects a more fundamental fix rather than superficial alterations.
  • Four Features are Key: The combination of variable, expression, structure, and repair location provides a robust way to distinguish correct from incorrect patches, outperforming individual features.
  • Limitations of Test Cases: The paper strongly emphasizes that test cases alone are insufficient to guarantee patch correctness, as they often fail to cover all program paths and can lead to "overfitting" where patches pass tests but are semantically flawed.
  • Semantic vs. Syntactic Focus: While many APR tools focus on semantic correctness, this work highlights the importance of syntactic similarity and distance as a practical and effective evaluation metric.

Key Results

  • The proposed method successfully ranked 95% of correct patches in the top one position among plausible patches for each defect.
  • When comparing their method (PPSD) against CapGen and SSDM on 43 defects, PPSD ranked the correct patches first for 41 defects, outperforming CapGen (36) and SSDM (36).
  • The method demonstrated a higher average space reduction (95.3%) compared to CapGen (85.0%) and SSDM (87.7%), meaning it more effectively narrowed down the search space for correct patches.
  • The perfect repair rate (percentage of defects where the correct patch was ranked first) was also superior for PPSD (95.3%) compared to CapGen (83.7%) and SSDM (83.7%).

Limitations and Future Work

  • Statement Dependence: The current method evaluates patches at a fine-grained level (expressions, variables, structures) but does not explicitly consider the dependence between statements. This limits its effectiveness for evaluating patches that fix defects involving multiple statements.
  • Fault Localization Assumption: The study assumes that the fault localization step correctly identifies the faulty statement. This assumption might not always hold true in practice.
  • External Validity: The evaluation was primarily conducted on the Defects4J benchmark. While the authors explored using IntroClassJava to test generalizability, further validation on diverse datasets is needed.

The authors suggest combining their method with dynamic test methods and further exploring the impact of statement dependencies in future work. They also propose integrating their method into continuous integration pipelines for automated code quality verification.

Summary updated

BibTeX
@article{dong2022quality,
  author = {Yukun Dong and Daolong Tang and Xiaotong Cheng and Yufei Yang},
  title = {{Quality Evaluation Method of Automatic Software Repair Using Syntax Distance Metrics}},
  journal = {Symmetry},
  year = {2022},
  doi = {10.3390/sym14081751},
}
Figure