PaperlayerView exact revision on arXiv

Source-linked AI summary

Automatic Software Repair: a Bibliography

Martin Monperrus

arXiv:1807.00515v1cs.SEcs.CRcs.PL

TL;DR

Automatic software repair addresses the difficult problem of finding bug fixes without human intervention. This paper surveys the field across behavioral and state repair, organizing work by repair type, oracle, and contributing research community. It concludes that repair techniques must still scale to today’s software stacks, so the field remains at an early stage.

  • Problem

    Automatic software repair addresses the difficult task of fixing software bugs without human intervention, against a background of widespread bugs in software systems.

  • Method

    The paper presents an annotated bibliography spanning behavioral and state repair across software engineering, dependability, operating systems, programming languages, and software security.

  • Results

    The survey provides a structured overview of automatic repair literature by repair type, oracle, and empirical knowledge about repair techniques and patches.

  • Takeaways & Limitations

    Repair techniques must scale to the size and complexity of today’s software stacks, and the paper characterizes the field as only at its beginning.

  • Takeaways & Limitations

    The paper excludes automatic repair and tolerance against hardware bugs from its scope, and notes that comprehensive bug-class taxonomy remains incomplete.

Abstract

from arXiv · show

This article presents a survey on automatic software repair. Automatic software repair consists of automatically finding a solution to software bugs without human intervention. This article considers all kinds of repairs. First, it discusses behavioral repair where test suites, contracts, models, and crashing inputs are taken as oracle. Second, it discusses state repair, also known as runtime repair or runtime recovery, with techniques such as checkpoint and restart, reconfiguration, and invariant restoration. The uniqueness of this article is that it spans the research communities that contribute to this body of knowledge: software engineering, dependability, operating systems, programming languages, and security. It provides a novel and structured overview of the diversity of bug oracles and repair operators used in the literature.

1. INTRODUCTION

The paper surveys automatic software repair as a challenging response to widespread software bugs, bringing together behavioral and state repair across multiple research communities. It organizes the literature by repair type and oracle while emphasizing empirical relevance.

  • Motivation: Automatic software repair aims to find solutions to software bugs without human intervention, a challenging task because difficult bugs can require extensive human effort.The paper frames repair as potentially valuable because software is pervasive and bugs remain widespread.
  • Scope: The survey brings together behavioral repair, which modifies program code, and state repair, which modifies execution state at runtime.These are presented as the field’s two main families of techniques.
  • Selection criteria: The survey emphasizes techniques that apply to industry programs and bugs occurring in practice.Included works are qualified using venue visibility, reputation, or idea novelty.
  • Scope: It spans software engineering, dependability, operating systems, programming languages, and software security, while abstracting over related terminology.The survey uses this cross-community and terminology-spanning perspective to draw the field’s big picture.
  • Organization: The literature is analyzed according to the type of repair performed and the oracle considered.The paper’s structure covers behavioral repair, state repair, empirical foundations, and closely connected work.

2. CORE CONCEPTS FOR AUTOMATIC REPAIR

This section establishes the core vocabulary of automatic repair, distinguishing bugs, specifications, oracles, and bug classes. It defines repair as transforming unacceptable program behavior into acceptable behavior according to a specification, while noting that bug-class taxonomy remains incomplete.

  • Bug concepts: A bug is discussed through related notions of failure, error, and fault, although the literature does not consistently adhere to these distinctions.A failure is observed unacceptable behavior, an error is a propagating incorrect state, and a fault is its root cause.
  • Repair definition: Automatic repair transforms unacceptable behavior during program execution into acceptable behavior according to a specification.The relevant observer may be a human user or a specification expressed through documents, logic, tests, or implicit expectations.
  • Specifications and oracles: A specification describes expected behavior and related constraints, whereas an oracle determines whether an execution result is correct.A test suite is a specification whose assertions act as oracles for expected outputs.
  • Specifications and oracles: Repair uses bug oracles to detect unexpected behavior and regression oracles to check that repair has not introduced new bugs.The distinction reflects that the original program already satisfies the regression oracles before repair.
  • Bug classes: A bug class groups bugs sharing symptoms, root causes, or solutions, but many classes lack clear definitions or names.The paper states that a comprehensive bug-class taxonomy will require years of research.

3. BEHAVIORAL REPAIR

Behavioral repair changes program code to alter behavior, offline or online, and organizes techniques by their repair operators and bug oracles. The literature includes test-suite, synthesis, mutation, template, and contract-based approaches.

  • Behavioral repair: Behavioral repair changes source or binary code to modify program behavior, either offline or online at runtime.Runtime behavioral repair involves dynamic software updating.
  • Repair operators: Repair operators are code modifications, sometimes parameterized by templates targeting specific bug classes.A repair model is a set of repair operators.
  • Test-suite oracles: Test-suite based repair uses a failing test as the bug oracle and passing tests as the regression oracle.The repair goal is a patch that makes the whole test suite pass.
  • Test-suite oracles: 55 out of 105 bugs were claimed fixed by Genprog, whose AST operators delete, add, or replace nodes under the redundancy assumption.The reported results were later questioned in the paper’s empirical discussion.
  • Other behavioral approaches: Behavioral repair also includes symbolic-execution synthesis, mutation-based systems, staged search, historical-learning systems, and contract-based templates.Examples include Semfix, Angelix, PAR, SPR, Prophet, and AutoFix-E.

3.2. Static Analysis

Static-analysis-based repair uses errors or warnings reported by static analysis as the correctness oracle. Approaches target fault classes including off-by-one errors, arithmetic overflow, memory leaks, compiler errors, and buffer overflows.

  • Static-analysis oracle: Static analysis can provide the correctness oracle for automatically repairing detected errors and warnings.The analysis is used to identify repair targets and verify repairs.
  • Fault-specific repairs: Static-analysis repair operations are specialized to fault classes, including adding preconditions and changing array-allocation sizes.The static analysis is rerun to verify the repair.
  • Fault-specific repairs: Integer arithmetic overflow can be addressed by statically detecting it and reordering arithmetic operations.The stated fix ensures that the overflow cannot happen anymore.
  • Fault-specific repairs: Memory leaks in C can be repaired by statically inserting deallocation statements.The evaluation considered 242 allocations across 14 programs.
  • Fault-specific repairs: DeepFix uses a deep-learning language model to suggest fixes for compiler errors in student programs.Compiler errors serve as a static oracle.
  • Fault-specific repairs: Buffer-overflow repair uses parameterized templates whose variables are selected with SMT.The buffer overflows are first detected statically.

3.3. Crashing inputs

Crashing-input repair responds to field failures such as exceptions, segmentation faults, and buffer overflows after identifying and possibly minimizing the crashing input. These systems use mined edits, binary rewriting, source transformation, or dynamically derived conditions.

  • Crashing inputs: Crashing-input repair begins after a field failure is identified and possibly minimized, using the crashing input as the repair oracle.A failing test case can also be viewed as a crashing input, but test suites additionally provide passing regression tests.
  • Repair approaches: QACrashFix mines buggy–fixed code pairs from Stack Overflow and tries extracted edit scripts sequentially to suppress crashing exceptions.The system is designed for crashing exceptions.
  • Repair approaches: Runtime-detected buffer-overflow vulnerabilities can be repaired through source recovery, TXL transformations, and manually provided regression test suites.The vulnerabilities are detected in production.
  • Repair approaches: Array overflows can be repaired by adding modulo operations for out-of-bound reads and truncating data for out-of-bound writes.The patch is generated from a working exploit that triggers the overflow.
  • Repair approaches: Integer-overflow repair operators force an error branch before or after overflow, or stop the program.The generated conditions are path conditions obtained from dynamic symbolic execution.

3.4. Other Oracles

Other behavioral-repair oracles include concurrency constraints, output validity, bug reports, proof failures, reference implementations, and metamorphic relations. These approaches vary from constraint solving and tracing to templates, proofs, and program synthesis.

  • Specialized oracles: Concurrency-bug repair can insert instructions into critical regions or introduce locks using satisfiability-based encodings.Dfixer instead repairs concurrency bugs without introducing new locks.
  • Specialized oracles: Malformed HTML output can serve as an oracle for repairing PHP applications through string constraints or runtime tracing.The malformed-output condition concerns inconsistent opening and closing tags.
  • Specialized oracles: Manually written bug reports can provide template parameters, such as the variable used by a not-null checker.The approach extracts concrete parameter values from the report.
  • Specialized oracles: Proof failures and their counterexamples can drive template-based repairs for ML programs verified with Isabelle.Repairs include replacing method calls or adding code.
  • Reference implementations: A reference implementation can act as both bug and regression oracle, with Sketch-based systems evaluating repairs on Python programs and large sets of student submissions.Qlose additionally minimizes the number of inputs whose behavior changes.
  • Metamorphic relations: Metamorphic relations have been used as repair oracles, but their usefulness for large real programs remains unproven because one evaluation used limited experimental subjects.The cited work evaluated the approach on the Introclass benchmark of student programs.

3.5. Domain Specific Repair

Domain-specific repair applies automatic repair to specialized computational artifacts, including constraint programs, databases, ontologies, models, policies, architectures, and test scripts.

  • Automatic repair has been applied to specialized artifacts such as constraint programs, database statements, OWL ontologies, boolean programs, access-control policies, and structured documents.
  • Other approaches repair architectural dependencies, UML and MOF models, software product-line configurations, or GUI and Selenium test scripts.

3.6. Fault Classes and Repair

Fault-class repair targets known families of bugs with transformations designed to suppress or correct their characteristic failures. These approaches include semantic-preserving and semantic-modifying transformations across arithmetic, memory safety, security, and exception handling.

  • Known fault classes can be addressed with code transformations that suppress all instances, such as replacing fixed-width integers with unlimited-precision arithmetic to avoid overflows.
  • Failure-oblivious computing handles out-of-bounds reads by returning a selected non-null or modulo-indexed element, while related methods store out-of-bounds writes for later access.
  • Security-oriented transformations modify PHP abstract syntax trees to inject prepared SQL statements.
  • Tools such as Error Prone, Coccinelle, and Trans declaratively specify bug patterns and corresponding repairs or formal transformations.
  • Buffer-overflow and integer-bug repairs replace unsafe calls or types, detect overflows, or deny inputs; reported buffer-overflow transformations scale to large programs without breaking tests or slowing execution.
  • Catch stretching analyzes test executions and generalizes exception types so unexpected exceptions are caught proactively.

4. STATE REPAIR

State repair changes program execution state at runtime, using production-available incorrectness oracles and operators such as restart, rollback, reconfiguration, input modification, execution perturbation, and invariant restoration.

  • 4. STATE REPAIR: State repair changes inputs, heap, stack, or environment at runtime, unlike behavioral repair, which changes program code.
  • 4. STATE REPAIR: State repair relies on runtime oracles including non-functional contracts, production-verifiable functional contracts, and inferred contracts based on regularities in program states.
  • 4.1. Reinitialization & Restart: Restart is the simplest state-repair action, while microreboot hierarchically restarts the smallest failed component first and can significantly improve system availability.
  • 4.2. Checkpoint & Rollback: Checkpoint and rollback periodically snapshot execution state and later restore a snapshot, with state boundaries and checkpoint timing as central challenges.
  • Runtime state repair also uses alternative implementations, component reconfiguration, input denial or rectification, environment changes, memory padding, added locks, and other execution perturbations.
  • 4.7. Forward Recovery: Forward recovery transforms the current state into a correct one, including restoring violated invariants with minimal changes when possible.
  • Runtime data-structure repair can use a specification language or an invariant encoded as a Java repOK method.

5. EMPIRICAL KNOWLEDGE ON REPAIR

Empirical research examines repair knowledge, patch quality, comparative system performance, and benchmark needs. Findings show that repositories contain reusable repair information, while synthesized patches can be incorrect or less maintainable than human patches.

  • Software repositories provide repair knowledge: analysis of 89,993 commits mined repair actions, and studies found many fixes rearrange existing code or modify configuration files.
  • Machine-generated patches were slightly less maintainable than human-written patches, and a GenProg analysis found most generated patches incorrect because they overfit test suites.
  • Comparative evaluation of GenProg, RSRepair, and AE on 119 seeded and 34 real Siemens bugs showed that repair techniques do not perform equally.
  • Accepted, well-defined, publicly available benchmarks are needed to consolidate repair knowledge; one C benchmark contains 1,183 bugs from open-source projects and student code.

6. RELATED TECHNIQUES

Related techniques either omit full automation or actual repair of real programs, or support repair through design principles, frameworks, systematic editing, and developer suggestions. The section also identifies work under strong assumptions where practical programs may not exist.

  • Design principles: Related techniques include forward engineering for repair, which implements robustness and resilience principles as first-class framework or library concepts.Examples include immune-system principles and crash-only software characteristics such as timeouts and leased resources.
  • Repair frameworks: Repair-support frameworks address runtime recovery, interoperability, program-variation search, and operating-system driver errors.Examples include Flora for local restart, runtime-selected adaptors, embedded DSLs, and annotations for Linux driver recovery.
  • Systematic editing: Systematic editing applies a unique generic patch to multiple locations affected by the same kind of bug.The patch may be inferred from a concrete instance or written abstractly, with tools supporting patch application.
  • Repair suggestions: Repair suggestions assist developers without full automation, using error-message histories, association rules, variable correlations, expected outputs, or distance metrics.These approaches cover compiler errors, runtime exceptions, suspicious statements, assignment updates, formulas, data structures, and issue reports.
  • Strong assumptions: Some automatic-repair studies rely on strong assumptions under which no practical program exists, and the area lacks a dedicated survey.The cited work includes repairing programs expressed in linear temporal logics.

7. CONCLUSION

The bibliography presents automatic software repair as a field with roots in older fault-tolerance work and newer behavioral-repair research. It concludes that techniques must scale to modern software stacks, a challenge the field has not yet solved.

  • Field history: Automatic software repair has roots in fault-tolerance research from the 1970s and 1980s.The conclusion cites a 1973 paper on software recovery in the JPL-STAR computer.
  • Field history: Behavioral repair, understood as automatically changing program code, has been explored since the end of the 2000s.The conclusion contrasts this newer research direction with the field’s older fault-tolerance roots.
  • Open challenge: Automatic-repair techniques have not yet scaled to the size and complexity of today’s software stacks.The article characterizes the field as being at an early stage and identifies scaling as an ongoing challenge.
Loading 1807.00515v1…