Invalidator: Automated Patch Correctness Assessment Via Semantic and Syntactic Reasoning

Thanh Le-Cong, Duc-Minh Luong, Xuan-Bach Dinh Le, David Lo, Nhat-Hoa Tran, Bui Quang Huy, Quyet-Thang Huynh

Introduction

Automated Program Repair (APR) has emerged as a transformative technology in software engineering, acting as an "auto-correct" for complex codebases. However, the field faces a significant bottleneck known as test overfitting.

An APR tool may generate a patch that passes all existing test cases but fails to truly fix the underlying bug. These "plausible but incorrect" patches often cheat by hard-coding specific results or breaking features not covered by the current test suite. Traditionally, identifying these failures requires manual human inspection or the generation of massive, computationally expensive new test suites. INVALIDATOR addresses this by automating the assessment of patch correctness through a novel hybrid approach.

The INVALIDATOR Framework

INVALIDATOR is a hybrid tool designed to determine if a machine-generated patch is correct or merely overfitting. It operates by combining two distinct forms of analysis: semantic (behavioral) and syntactic (structural) reasoning. This dual-layered approach allows the tool to catch errors that single-method classifiers often miss.

The INVALIDATOR hybrid architecture, illustrating the flow from machine-generated patches through semantic and syntactic classifiers to a final correctness prediction.

Semantic Reasoning: Behavioral Analysis

The first stage of the pipeline focuses on program behavior. INVALIDATOR utilizes Daikon, a tool for dynamic invariant detection, to infer "likely invariants"—mathematical properties (such as x > 0) that consistently hold true during execution.

The detailed workflow of the semantic-based classifier, showing how invariants from correct, buggy, and patched programs are compared to identify violations.

As shown in the semantic workflow, the system compares invariants across three versions of the code: the buggy program, the developer's "ground truth" fix, and the APR-generated patch. The classification follows two primary rules:

  1. Violation of Correct Specifications: If the patch violates a property known to be part of the correct program's specification, it is flagged as overfitting.
  2. Persistence of Buggy Behavior: If the patch maintains an invariant that only exists in the buggy version of the code, it is likewise flagged as incorrect.

Syntactic Reasoning: Structural Analysis

When semantic analysis is inconclusive, INVALIDATOR employs a machine learning-based syntactic check. This stage leverages CodeBERT, a pre-trained deep learning model for programming languages, to transform code fragments into high-dimensional vector embeddings.

By calculating the "distance" between the patched code, the buggy code, and the ground truth, the model can determine if a patch is structurally too similar to the bug or too distant from a known-correct fix. This provides a powerful "soft" proxy for correctness when formal semantic logic cannot reach a definitive conclusion.

Experimental Evaluation

The researchers evaluated INVALIDATOR using a dataset of 885 patches derived from real-world Java programs in the Defects4J benchmark. This dataset consisted of 508 overfitting patches and 377 correct ones, sourced from previous high-profile studies to ensure a rigorous comparison against existing state-of-the-art tools like ODS and RGT.

Key Results

  • Superior Performance: INVALIDATOR correctly identified 79% of overfitting patches, outperforming top existing tools by 14% in Accuracy and 19% in F-Measure.
  • High Precision: The tool achieved a precision of 97%. This high reliability is critical for developer adoption, as it ensures that patches flagged as overfitting are almost certainly incorrect.
  • Efficiency: The assessment process takes approximately 7 minutes per patch on average, making it a viable candidate for integration into modern Continuous Integration/Continuous Deployment (CI/CD) pipelines.

Insights and Future Directions

The study's most significant finding is the complementarity of semantic and syntactic reasoning. The hybrid approach detected 35% more overfitting patches than using invariants alone. While raw test cases only validate specific inputs, invariants capture the broader intent of the code, allowing INVALIDATOR to generalize beyond the existing test suite.

Currently, INVALIDATOR requires a "ground truth" patch for comparison, which limits its immediate application to regression testing or research environments. Future work aims to reduce the computational overhead of invariant mining and explore using INVALIDATOR to guide APR tools during the generation phase, preventing the creation of overfitting patches before they are even proposed.

Summary updated

BibTeX
@article{lecong2023invalidator,
  author = {Thanh Le-Cong and Duc-Minh Luong and Xuan-Bach Dinh Le and David Lo and Nhat-Hoa Tran and Bui Quang Huy and Quyet-Thang Huynh},
  title = {{Invalidator: Automated Patch Correctness Assessment Via Semantic and Syntactic Reasoning}},
  journal = {IEEE Trans. Software Eng.},
  year = {2023},
  doi = {10.1109/tse.2023.3255177},
}
Figure