Program Repair

This is the most common paradigm, where a repair system generates candidate patches and then validates them against a test suite or formal specification. The process involves:

• Search Space Definition: Defining the space of possible code modifications (e.g., statement replacement, insertion, deletion).
• Candidate Generation: Using heuristics, templates, or mutations to produce patch candidates.
• Validation: Running the patched program against a test suite; a candidate passes if it fixes failing tests without breaking passing ones.
• Ranking: Selecting the "best" valid patch, often by minimality or syntactic similarity.

Example: A tool mutates an incorrect conditional if (x > y) to if (x >= y) and tests it. If all tests pass, the patch is accepted.

This approach uses formal methods and program semantics to reason about correctness, going beyond test execution. Key techniques include:

• Symbolic Execution: Executing the program with symbolic inputs to derive path conditions and identify failing constraints.
• Constraint Solving: Using Satisfiability Modulo Theories (SMT) solvers (e.g., Z3) to find patch expressions that satisfy correctness conditions.
• Specification Mining: Inferring intended behavior from code comments, invariants, or similar correct code.

Example: For a buggy expression e, symbolic execution identifies a failing constraint C. The solver finds a new expression e' such that the constraint C[e'/e] is satisfied, yielding a semantically correct patch.

This method applies pre-defined patch templates (or patterns) derived from common bug fixes in historical data. The process is:

• Template Library: A curated set of fix patterns (e.g., "change operator", "add null check", "fix off-by-one").
• Fault Localization: Identifying suspicious code locations likely to contain the bug.
• Template Instantiation: Applying relevant templates to the suspicious locations, generating concrete patch candidates.
• Validation: Testing instantiated candidates.

Example: The system identifies a potential null pointer dereference at obj.value. It instantiates the "add null check" template, generating if (obj != null) return obj.value; as a candidate patch.

This approach uses machine learning models, trained on large corpora of bug-fix pairs, to predict patches. Common models include:

• Sequence-to-Sequence Models: Treat buggy code as a source sequence and the fixed code as a target sequence.
• Graph Neural Networks (GNNs): Operating on Abstract Syntax Trees (ASTs) to capture code structure.
• Large Language Models (LLMs): Using models like Codex or Code Llama, prompted with the buggy context, to generate fixes.

Strengths: Can suggest complex, non-obvious fixes. Limitations: May generate syntactically invalid or semantically incorrect code; requires extensive training data.

This technique frames program repair as an optimization problem and uses metaheuristic search algorithms to explore the patch space. Key methods include:

• Genetic Programming: Evolving a population of program variants (patches) using crossover and mutation, with fitness defined by test suite performance.
• Hill Climbing: Making local modifications to improve fitness iteratively.
• Simulated Annealing: Allowing occasional moves to worse states to escape local optima.

The fitness function typically maximizes the number of passing tests. This approach is powerful for complex, multi-line fixes but can be computationally expensive.

These approaches involve external guidance to improve patch quality and relevance.

• Oracle-Guided Synthesis: Uses an oracle (e.g., a formal specification, a simulator, or a human) to answer queries about desired behavior, refining the search.
• Interactive Program Repair: Engages the developer in the loop. The system may:
  • Present multiple candidate patches for human selection.
  • Ask clarifying questions about intended behavior.
  • Accept natural language feedback to refine its search.

This paradigm is crucial for integrating developer intent and ensuring patches are not just technically correct but also align with software design and maintainability goals.

The overarching field of automatically generating executable code from high-level specifications. Program repair is a specialized subfield focused on modifying existing code to meet a corrected specification, whereas general synthesis often creates programs from scratch. Key approaches include:

• Programming by Example (PBE): Using input-output pairs.
• Syntax-Guided Synthesis (SyGuS): Using a grammar and logical constraints.
• Sketch-Based Synthesis: Filling holes in a partial program template.

The use of mathematical logic and automated theorem proving to prove that a program satisfies its formal specification. In program repair, verification is critical for validating candidate patches. Techniques like model checking and SMT solving are used to ensure a repair does not introduce new violations. The Counterexample-Guided Inductive Synthesis (CEGIS) loop is a canonical architecture that tightly couples synthesis with verification.

The prerequisite step to program repair that identifies the specific lines of code likely responsible for a bug. Repair systems rely on its output to constrain the search space. Common techniques include:

• Spectrum-Based Fault Localization: Analyzing which statements are most correlated with test failures.
• Statistical Debugging: Using predicate statistics from passing and failing runs.
• Slice-Based Analysis: Computing program slices relevant to the erroneous output.

A software testing technique that evaluates test suite quality by introducing small faults (mutants) into the program and checking if tests detect them. It shares a core mechanism with generate-and-validate program repair, where repair tools often generate variants (mutations) of the original code and test them against a specification. The mutation operators (e.g., changing an arithmetic operator) are frequently reused in repair patch generation.

The general category of tools that automatically modify source code while preserving or enhancing certain properties. Program repair is a goal-directed transformation for correctness. Other forms include:

• Refactoring: Improving code structure without changing behavior.
• Performance Optimization: Transforming code for efficiency.
• Code Translation (Transpilation): Converting code between languages.
• Decompilation: Recovering source code from binaries.

A dominant paradigm in automated program repair where the specification is a test suite. The goal is to generate a patch that makes all tests pass. This approach is pragmatic but has the overfitting problem, where a patch passes the given tests but fails on unseen cases. Advanced systems use test amplification or specification inference to mitigate this. The Defects4J benchmark is a standard dataset for evaluating such tools.