Automatic bug fixing: Difference between revisions

Revision as of 15:44, 5 February 2016

Revision as of 18:26, 10 February 2016

Line 4:

{{nofootnotes|date=February 2016}}

}}

'''Automatic bug fixing''' automates the process of

[[Patch (computing)|fixing]] or repairing

[[Software bug|software bugs]]

<ref>Patching program errors (CACM 2008)

http://dx.doi.org/doi:10.1145/1409360.1409381</ref><ref>Automated Patching Techniques: The Fix Is In (CACM 2010)

http://dx.doi.org/doi:10.1145/1735223.1735248</ref>. It is also known as automatic bug repair or automatic patch generation.

'''Automatic bug-fixing''' is the automatic [[Patch (computing)|repair]] of [[Software bug|software bugs]] without the intervention of a human programmer

Several techniques<ref>[http://www.monperrus.net/martin/survey-automatic-repair.pdf Automatic Software Repair: a Bibliography], Technical Report, University of Lille 2015

<ref>Patching program errors (CACM 2008) http://dx.doi.org/doi:10.1145/1409360.1409381</ref>

</ref> have been proposed to automatically fix bugs, such as [[Genetic Programming]]. Automatic bug fixing is one of the application fields of [[genetic improvement]].

<ref>Automated Patching Techniques: The Fix Is In (CACM 2010) http://dx.doi.org/doi:10.1145/1735223.1735248</ref>.

http://dx.doi.org/doi:10.1145/1735223.1735248</ref>. It is also knowncommonly referred to as ''automatic bug repair'' or ''automatic patch generation''.

Techniques for automatic bug-fixing are still in their infancy, but are broadly divided into two camps depending on the way the proposed repair is evaluated: those based on formal analysis, and those that use a generate-and-validate approach. The former utilises formal methods to prove properties of a repair, whilst the latter relies on the availability of a high-quality test suite or similar artifact to validate the outcome of the repair process.

Current automatic repair systems are able to repair real bugs in C, C++. and Java<ref>

Automatic program repair with evolutionary computation

==Techniques using Formal Verification==

http://dx.doi.org/doi:10.1145/1735223.1735249</ref>.

Verification-based program repair combines techniques from formal verification, program synthesis, and fault-localisation. Industrial application of these techniques is limited due to the computation cost involved; it is not clear how potentially scalable such methods are. To reduce the number of possible repairs and hence the computational cost, often only a small pre-defined class of bugs is considered. Examples of bug classes include off-by-one errors and memory leaks

<ref>Automatic Software Repair: a Bibliography http://www.monperrus.net/martin/www.monperrus.net/martin/survey-automatic-repair.pdf</ref>.

==Test-and-Validate Techniques==

In Test-and-Validate approaches, program repair is performed with respect to an oracle, encompassing the desired functionality of the program, which is used for validation of the generated fix. A simple example is a test-suite - the input/output pairs specify the functionality of the program, possibly captured in assertions. This oracle can in fact be divided between the ''bug oracle'' that detects faulty behaviour, and the ''regression oracle'', which encapsulates the functionality any program repair method must preserve.

A variety of tools are employed to generate a candidate repair, typically either deterministic approaches using solvers for [[Satisfiability Modulo Theories]] (SMT)

<ref>Automatic Repair of Buggy If Conditions and Missing Preconditions with SMT http://arxiv.org/abs/1404.3186</ref>,

or stochastic algorithms such as [[Genetic Programming]]. Research on the application of Genetic Programming to repair bugs is part of a subfield known as [[Genetic Improvement]]. Current automatic repair systems using Genetic Improvement are able to repair real bugs in C, C++, and Java

<ref>Automatic program repair with evolutionary computation Automatic program repair with evolutionary computation</ref>

.

==Repair Operators==

Repair operators manipulate the original program, potentially via its [[abstract syntax tree]] representation, or a more coarse-grained representation such as operating at the line or block-level.

Typically, Genetic Improvement approaches operate at the line level and carry out simple delete/replace operations similar to those found in standard software patches. Verification-based methods are more likely to rely on template-based operators that match known patterns and have well-understood affects on program semantics.

==Example Tools==

Arguably the most well-known Genetic Improvement software repair tool is GenProg

<ref>GenProg: Evolutionary Program Repair http://dijkstra.cs.virginia.edu/genprog/</ref>.

Examples of verification-based repair are Semfix

<ref>SemFix: Program Repair via Semantic Analysis https://www.comp.nus.edu.sg/~abhik/pdf/ICSE13-SEMFIX.pdf</ref>

, which relies on symbolic execution, and Gopinath et al.'s work that relies on Alloy specifications

<ref>http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.4390</ref>.

==Limitations of Automatic Repair==

State-of-the-art approaches can currently repair only a very small proportion of bugs

<ref>Automatic program repair with evolutionary computation http://dx.doi.org/doi:10.1145/1735223.1735249.</ref>.

Whilst Genetic Improvement methods have arguably been shown to scale best, they are limited by the lack of correctness guarantees.

==Limitations of automatic repair==