Automatic bug fixing: Difference between revisions

Revision as of 18:25, 6 January 2023

Revision as of 19:49, 27 January 2023

Line 1:

{{short description|Automatic repair of software bugs}}

'''Automatic bug-fixing''' is the automatic [[Patch (computing)|repair]] of [[software bug]]s without the intervention of a human programmer.<ref>{{Cite journal |last=Rinard |first=Martin C. |year=2008 |title=Technical perspective ''Patching'' program errors |journal=Communications of the ACM |volume=51 |issue=12 |pages=86 |doi=10.1145/1409360.1409381 |s2cid=28629846}}</ref><ref>{{Cite journal |last=Harman |first=Mark |year=2010 |title=Automated patching techniques |journal=Communications of the ACM |volume=53 |issue=5 |pages=108 |doi=10.1145/1735223.1735248 |s2cid=9729944}}</ref> It is also commonly referred to as ''automatic patch generation'', ''automatic bug repair'', or ''automatic program repair''.<ref name="Monperrus2018">{{Cite journal |last=Monperrus |first=Martin |year=2018 |title=Automatic Software Repair: A Bibliography |journal=ACM Computing Surveys |volume=51 |issue=1 |pages=1–24 |arxiv=1807.00515 |doi=10.1145/3105906 |s2cid=216145256}}</ref><ref name="Gazzola2019">{{Cite journal |last1=Gazzola |first1=Luca |last2=Micucci |first2=Daniela |last3=Mariani |first3=Leonardo |year=2019 |title=Automatic Software Repair: A Survey |url=https://boa.unimib.it/bitstream/10281/184798/2/08089448_final.pdf |journal=IEEE Transactions on Software Engineering |volume=45 |issue=1 |pages=34–67 |doi=10.1109/TSE.2017.2755013 |hdl=10281/184798 |s2cid=57764123|doi-access=free }}</ref> The typical goal of such techniques is to automatically generate correct [[Patch (computing)|patches]] to eliminate [[software bug|bugs]] in [[software program]]s without causing [[software regression]].<ref>{{Cite book |last1=Tan |first1=Shin Hwei |title=2015 IEEE/ACM 37th IEEE International Conference on Software Engineering |last2=Roychoudhury |first2=Abhik |date=2015 |publisher=IEEE |isbn=978-1-4799-1934-5 |pages=471–482 |chapter=relifix: Automated repair of software regressions |doi=10.1109/ICSE.2015.65 |s2cid=17125466}}</ref>

== Specification ==

Line 14:

=== Generate-and-validate ===

Generate-and-validate approaches compile and test each candidate patch to collect all validated patches that produce expected outputs for all inputs in the test suite.<ref name="genprog2009" /><ref name="kali" /> Such a technique typically starts with a test suite of the program, i.e., a set of [[test cases]], at least one of which exposes the bug.<ref name="genprog2009" /><ref name="prophet" /><ref name="rsrepair">{{Cite book |last1=Qi |first1=Yuhua |title=Proceedings of the 36th International Conference on Software Engineering |last2=Mao |first2=Xiaoguang |last3=Lei |first3=Yan |last4=Dai |first4=Ziying |last5=Wang |first5=Chengsong |date=2014 |publisher=ACM |isbn=978-1-4503-2756-5 |series=ICSE 2014 |___location=Austin, Texas |pages=254–265 |chapter=The Strength of Random Search on Automated Program Repair |doi=10.1145/2568225.2568254 |s2cid=14976851}}</ref><ref name="spr">{{Cite book |last1=Long |first1=Fan |title=Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering |last2=Rinard |first2=Martin |date=2015 |publisher=ACM |isbn=978-1-4503-3675-8 |series=ESEC/FSE 2015 |___location=Bergamo, Italy |pages=166–178 |chapter=Staged Program Repair with Condition Synthesis |citeseerx=10.1.1.696.9059 |doi=10.1145/2786805.2786811 |s2cid=5987616}}</ref> An early generate-and-validate bug-fixing systems is GenProg.<ref name="genprog2009" /> The effectiveness of generate-and-validate techniques remains controversial, because they typically do not provide [[#Limitations of automatic bug-fixing|patch correctness guarantees]].<ref name="kali" /><ref name="criticalreview">{{Cite book |last=Monperrus |first=Martin |title=Proceedings of the 36th International Conference on Software Engineering |date=2014 |publisher=ACM |isbn=978-1-4503-2756-5 |series=ICSE 2014 |___location=New York, New York |pages=234–242 |chapter=A Critical Review of "Automatic Patch Generation Learned from Human-written Patches": Essay on the Problem Statement and the Evaluation of Automatic Software Repair |arxiv=1408.2103 |doi=10.1145/2568225.2568324 |s2cid=13355761}}</ref> Nevertheless, the reported results of recent state-of-the-art techniques are generally promising. For example, on systematically collected 69 real world bugs in eight large C software programs, the state-of-the-art bug-fixing system Prophet generates correct patches for 18 out of the 69 bugs.<ref name="prophet" />

<!-- mutation based repair -->

One way to generate candidate patches is to apply [[program mutation|mutation operators]] on the original program. Mutation operators manipulate the original program, potentially via its [[abstract syntax tree]] representation, or a more coarse-grained representation such as operating at the [[Statement (programming)|statement]]-level or [[Block (programming)|block]]-level. Earlier [[Genetic improvement (computer science)|genetic improvement]] approaches operate at the statement level and carry out simple delete/replace operations such as deleting an existing statement or replacing an existing statement with another statement in the same source file.<ref name=genprog2009 /><ref name="genprog2012">{{Cite book |last1=Le Goues |first1=Claire |title=2012 34th International Conference on Software Engineering (ICSE) |last2=Dewey-Vogt |first2=Michael |last3=Forrest |first3=Stephanie |last4=Weimer |first4=Westley |date=2012 |publisher=IEEE |isbn=978-1-4673-1067-3 |pages=3–13 |chapter=A Systematic Study of Automated Program Repair: Fixing 55 out of 105 Bugs for $8 Each |citeseerx=10.1.1.661.9690 |doi=10.1109/ICSE.2012.6227211 |s2cid=10987936}}</ref> Recent approaches use more fine-grained operators at the [[abstract syntax tree]] level to generate more diverse set of candidate patches.<ref name=spr /> Notably, the statement deletion mutation operator, and more generally removing code, is a reasonable repair strategy, or at least a good fault localization strategy.<ref>{{Cite journal |last1=Qi |first1=Zichao |last2=Long |first2=Fan |last3=Achour |first3=Sara |last4=Rinard |first4=Martin |date=2015-07-13 |title=An analysis of patch plausibility and correctness for generate-and-validate patch generation systems |url=http://dx.doi.org/10.1145/2771783.2771791 |journal=Proceedings of the 2015 International Symposium on Software Testing and Analysis |pages=24–36 |___location=New York, NY, USA |publisher=ACM |doi=10.1145/2771783.2771791|hdl=1721.1/101586 |isbn=9781450336208 |s2cid=6845282 }}</ref><ref>{{Cite journal |last1=Ginelli |first1=Davide |last2=Martinez |first2=Matias |last3=Mariani |first3=Leonardo |last4=Monperrus |first4=Martin |date=2022 |title=A comprehensive study of code-removal patches in automated program repair |url=https://link.springer.com/10.1007/s10664-021-10100-7 |journal=Empirical Software Engineering |language=en |volume=27 |issue=4 |pages=97 |doi=10.1007/s10664-021-10100-7 |s2cid=228376263 |issn=1382-3256}}</ref>

<!-- fix templates -->

Another way to generate candidate patches consists of using fix templates. Fix templates are typically predefined changes for fixing specific classes of bugs.<ref name=par /> Examples of fix templates include inserting a [[Conditional (computer programming)|conditional statement]] to check whether the value of a variable is null to fix null pointer exception, or changing an integer constant by one to fix off-by-one errors.<ref name="par" /> It is also possible to automatically mine fix templates for generate-and-validate approaches.<ref>{{Citation |last1=Martinez |first1=Matias |title=Ultra-Large Repair Search Space with Automatically Mined Templates: The Cardumen Mode of Astor |date=2018 |work=Search-Based Software Engineering |pages=65–86 |publisher=Springer International Publishing |language=en |arxiv=1712.03854 |doi=10.1007/978-3-319-99241-9_3 |isbn=9783319992402 |last2=Monperrus |first2=Martin |s2cid=49651730}}</ref><ref>{{Cite journal |last1=Koyuncu |first1=Anil |last2=Liu |first2=Kui |last3=Bissyandé |first3=Tegawendé F. |last4=Kim |first4=Dongsun |last5=Klein |first5=Jacques |last6=Monperrus |first6=Martin |last7=Le Traon |first7=Yves |date=2020 |title=FixMiner: Mining relevant fix patterns for automated program repair |journal=Empirical Software Engineering |language=en |volume=25 |issue=3 |pages=1980–2024 |arxiv=1810.01791 |doi=10.1007/s10664-019-09780-z |s2cid=52915728}}</ref>

<!-- redundancy insight -->

Many generate-and-validate techniques rely on the redundancy insight: the code of the patch can be found elsewhere in the application. This idea was introduced in the Genprog system, where two operators, addition and replacement of AST nodes, were based on code taken from elsewhere (i.e. adding an existing AST node). This idea has been validated empirically, with two independent studies that have shown that a significant proportion of commits (3%-17%) are composed of existing code.<ref>{{Cite book |last1=Martinez |first1=Matias |title=Proceedings of the 36th International Conference on Software Engineering |last2=Weimer |first2=Westley |last3=Monperrus |first3=Martin |year=2014 |isbn=9781450327688 |pages=492–495 |chapter=Do the fix ingredients already exist? An empirical inquiry into the redundancy assumptions of program repair approaches |arxiv=1403.6322 |doi=10.1145/2591062.2591114 |chapter-url=https://hal.archives-ouvertes.fr/hal-00965410/document |s2cid=9533437}}</ref><ref>{{Cite book |last1=Barr |first1=Earl T. |title=Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering - FSE 2014 |last2=Brun |first2=Yuriy |last3=Devanbu |first3=Premkumar |last4=Harman |first4=Mark |last5=Sarro |first5=Federica |year=2014 |isbn=9781450330565 |pages=306–317 |chapter=The plastic surgery hypothesis |citeseerx=10.1.1.646.9678 |doi=10.1145/2635868.2635898 |s2cid=14002308}}</ref> Beyond the fact that the code to reuse exists somewhere else, it has also been shown that the context of the potential repair ingredients is useful: often, the donor context is similar to the recipient context.<ref>{{Cite book |last1=White |first1=Martin |title=2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER) |last2=Tufano |first2=Michele |last3=Martinez |first3=Matias |last4=Monperrus |first4=Martin |last5=Poshyvanyk |first5=Denys |year=2019 |isbn=978-1-7281-0591-8 |pages=479–490 |chapter=Sorting and Transforming Program Repair Ingredients via Deep Learning Code Similarities |arxiv=1707.04742 |doi=10.1109/SANER.2019.8668043 |s2cid=13578285}}</ref><ref name="capgen" />

=== Synthesis-based ===

Line 32 ⟶ 29:

Under certain assumptions, it is possible to state the repair problem as a synthesis problem.

SemFix<ref name="semfix" /> and Nopol<ref name="nopol" /> uses component-based synthesis.<ref>{{Cite book |last1=Jha |first1=Susmit |url=http://techreports.lib.berkeley.edu/accessPages/EECS-2010-15.html |title=Oracle-guided component-based program synthesis |last2=Gulwani |first2=Sumit |last3=Seshia |first3=Sanjit A. |last4=Tiwari |first4=Ashish |date=2010-05-01 |publisher=ACM |isbn=9781605587196 |pages=215–224 |doi=10.1145/1806799.1806833 |s2cid=6344783}}</ref>

Dynamoth<ref>{{Cite book |last1=Durieux |first1=Thomas |url=https://hal.archives-ouvertes.fr/hal-01279233/file/main.pdf |title=DynaMoth: dynamic code synthesis for automatic program repair |last2=Monperrus |first2=Martin |date=2016-05-14 |isbn=9781450341516 |pages=85–91 |chapter=DynaMoth |doi=10.1145/2896921.2896931 |chapter-url=https://hal.archives-ouvertes.fr/hal-01279233/document |s2cid=16025812}}</ref> uses dynamic synthesis.<ref>{{Cite book |last1=Galenson |first1=Joel |title=CodeHint: dynamic and interactive synthesis of code snippets |last2=Reames |first2=Philip |last3=Bodik |first3=Rastislav |last4=Hartmann |first4=Björn |last5=Sen |first5=Koushik |date=2014-05-31 |publisher=ACM |isbn=9781450327565 |pages=653–663 |doi=10.1145/2568225.2568250 |s2cid=10656182}}</ref>

S3<ref>{{Cite book |last1=Le |first1=Xuan-Bach D. |url=https://ink.library.smu.edu.sg/sis_research/3917 |title=Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering - ESEC/FSE 2017 |last2=Chu |first2=Duc-Hiep |last3=Lo |first3=David |last4=Le Goues |first4=Claire |last5=Visser |first5=Willem |date=2017-08-21 |publisher=ACM |isbn=9781450351058 |pages=593–604 |doi=10.1145/3106237.3106309 |s2cid=1503790}}</ref> is based on syntax-guided synthesis.<ref>{{Cite book |last1=Alur |first1=Rajeev |title=2013 Formal Methods in Computer-Aided Design |last2=Bodik |first2=Rastislav |last3=Juniwal |first3=Garvit |last4=Martin |first4=Milo M. K. |last5=Raghothaman |first5=Mukund |last6=Seshia |first6=Sanjit A. |last7=Singh |first7=Rishabh |last8=Solar-Lezama |first8=Armando |last9=Torlak |first9=Emina |author9-link=Emina Torlak|year=2013 |isbn=9780983567837 |pages=1–8 |chapter=Syntax-guided synthesis |citeseerx=10.1.1.377.2829 |doi=10.1109/fmcad.2013.6679385 |last10=Udupa |first10=Abhishek}}</ref>

SearchRepair<ref name="searchrepair">{{Cite book |last1=Ke |first1=Yalin |title=Proceedings of the 2015 30th IEEE/ACM International Conference on Automated Software Engineering |last2=Stolee |first2=Kathryn |last3=Le Goues |first3=Claire |last4=Brun |first4=Yuriy |date=2015 |publisher=ACM |isbn=978-1-5090-0025-8 |series=ASE 2015 |___location=Lincoln, Nebraska |pages=295–306 |chapter=Repairing Programs with Semantic Code Search |doi=10.1109/ASE.2015.60 |s2cid=16361458}}</ref> converts potential patches into an SMT formula and queries candidate patches that allow the patched program to pass all supplied test cases.

Line 38 ⟶ 35:

=== Data-driven ===

[[Machine learning]] techniques can improve the effectiveness of automatic bug-fixing systems.<ref name="prophet" /> One example of such techniques learns from past successful patches from human developers collected from [[open-source software|open source]] [[software repository|repositories]] in [[GitHub]] and [[SourceForge]].<ref name="prophet" /> It then use the learned information to recognize and prioritize potentially correct patches among all generated candidate patches.<ref name="prophet" /> Alternatively, patches can be directly mined from existing sources. Example approaches include mining patches from donor applications<ref name="codephage" /> or from QA web sites.<ref name="QAFix" /> Learning can be done online, aka continual learning, with the known precedent of online learning of patches from the stream of open source build results from continuous integration.<ref>{{Cite journal|last1=Baudry|first1=Benoit|last2=Chen|first2=Zimin|last3=Etemadi|first3=Khashayar|last4=Fu|first4=Han|last5=Ginelli|first5=Davide|last6=Kommrusch|first6=Steve|last7=Martinez|first7=Matias|last8=Monperrus|first8=Martin|last9=Ron Arteaga|first9=Javier|last10=Ye|first10=He|last11=Yu|first11=Zhongxing|date=2021|title=A Software-Repair Robot Based on Continual Learning|url=https://arxiv.org/abs/2012.06824|journal=IEEE Software|volume=38|issue=4|pages=28–35|doi=10.1109/MS.2021.3070743|issn=0740-7459|arxiv=2012.06824|s2cid=229156186}}</ref>

SequenceR uses [[Neural machine translation|sequence-to-sequence learning]] on source code in order to generate one-line patches.<ref>{{Cite journal |last1=Chen |first1=Zimin |last2=Kommrusch |first2=Steve James |last3=Tufano |first3=Michele |last4=Pouchet |first4=Louis-Noel |last5=Poshyvanyk |first5=Denys |last6=Monperrus |first6=Martin |date=2019 |title=SEQUENCER: Sequence-to-Sequence Learning for End-to-End Program Repair |journal=IEEE Transactions on Software Engineering |pages=1 |arxiv=1901.01808 |doi=10.1109/TSE.2019.2940179 |issn=0098-5589 |s2cid=57573711}}</ref> It defines a neural network architecture that works well with source code, with the copy mechanism that allows to produce patches with tokens that are not in the learned vocabulary. Those tokens are taken from the code of the Java class under repair. Different kinds of loss functions can be used for optimizing the sequence-to-sequence neural network: the most common ones are purely static, typically a token-based cross entropy loss, and advanced ones also include dynamic information, e.g. through loss amplification.<ref>{{Cite journal |last1=Ye |first1=He |last2=Martinez |first2=Matias |last3=Monperrus |first3=Martin |date=2022-05-21 |title=Neural program repair with execution-based backpropagation |url=https://arxiv.org/abs/2105.04123 |journal=Proceedings of the 44th International Conference on Software Engineering |language=en |___location=Pittsburgh Pennsylvania |publisher=ACM |pages=1506–1518 |doi=10.1145/3510003.3510222 |arxiv=2105.04123 |isbn=978-1-4503-9221-1|s2cid=234340063 }}</ref>

Getafix<ref name=":0">{{Cite journal |last1=Bader |first1=Johannes |last2=Scott |first2=Andrew |last3=Pradel |first3=Michael |last4=Chandra |first4=Satish |date=2019-10-10 |title=Getafix: learning to fix bugs automatically |journal=Proceedings of the ACM on Programming Languages |volume=3 |issue=OOPSLA |pages=159:1–159:27 |doi=10.1145/3360585|doi-access=free }}</ref> is a language-agnostic approach developed and used in production at [[Facebook, Inc.|Facebook]]. Given a sample of [[Commit (version control)|code commits]] where engineers fixed a certain kind of bug, it learns human-like fix patterns that apply to future bugs of the same kind. Besides using Facebook's own [[Repository (version control)|code repositories]] as training data, Getafix learnt some fixes from [[open source]] Java repositories. When new bugs get detected, Getafix applies its previously learnt patterns to produce candidate fixes and ranks them within seconds. It presents only the top-ranked fix for final validation by tools or an engineer, in order to save resources and ideally be so fast that no human time was spent on fixing the same bug, yet.

Line 48 ⟶ 43:

* [[null pointer exception]] repair<ref name="rcv">{{Cite book |last1=Long |first1=Fan |title=Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation |last2=Sidiroglou-Douskos |first2=Stelios |last3=Rinard |first3=Martin |date=2014 |publisher=ACM |isbn=978-1-4503-2784-8 |series=PLDI '14' |___location=New York, New York |pages=227–238 |chapter=Automatic Runtime Error Repair and Containment via Recovery Shepherding |doi=10.1145/2594291.2594337 |s2cid=6252501}}</ref><ref name="nullfix">{{Cite book |last1=Dobolyi |first1=Kinga |title=2008 19th International Symposium on Software Reliability Engineering (ISSRE) |last2=Weimer |first2=Westley |year=2008 |pages=47–56 |chapter=Changing Java's Semantics for Handling Null Pointer Exceptions |citeseerx=10.1.1.147.6158 |doi=10.1109/ISSRE.2008.59 |s2cid=1454939}}</ref><ref name="par">{{Cite book |last1=Kim |first1=Dongsun |title=Proceedings of the 2013 International Conference on Software Engineering |last2=Nam |first2=Jaechang |last3=Song |first3=Jaewoo |last4=Kim |first4=Sunghun |date=2013 |publisher=IEEE Press |isbn=978-1-4673-3076-3 |series=ICSE '13' |pages=802–811 |chapter=Automatic Patch Generation Learned from Human-written Patches}}</ref> with insertion of a [[Conditional (computer programming)|conditional statement]] to check whether the value of a variable is null.

* [[integer overflow]] repair<ref name="codephage">{{Cite book |last1=Sidiroglou |first1=Stelios |title=Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation |last2=Lahtinen |first2=Eric |last3=Long |first3=Fan |last4=Rinard |first4=Martin |date=2015 |chapter=Automatic Error Elimination by Multi-Application Code Transfer}}</ref><ref>{{Cite journal |last1=Muntean |first1=Paul |last2=Monperrus |first2=Martin |last3=Sun |first3=Hao |last4=Grossklags |first4=Jens |last5=Eckert |first5=Claudia |date=2021-10-01 |title=IntRepair: Informed Repairing of Integer Overflows |url=http://dx.doi.org/10.1109/tse.2019.2946148 |journal=IEEE Transactions on Software Engineering |volume=47 |issue=10 |pages=2225–2241 |doi=10.1109/tse.2019.2946148 |arxiv=1807.05092 |s2cid=51627444 |issn=0098-5589}}</ref>

* [[buffer overflow]] repair<ref name="codephage" />

* [[memory leak]] repair,<ref name="leakfix">{{Cite book |last1=Gao |first1=Qing |title=Proceedings of the 37th International Conference on Software Engineering – Volume 1 |last2=Xiong |first2=Yingfei |last3=Mi |first3=Yaqing |last4=Zhang |first4=Lu |last5=Yang |first5=Weikun |last6=Zhou |first6=Zhaoping |last7=Xie |first7=Bing |last8=Mei |first8=Hong |date=2015 |publisher=IEEE Press |isbn=978-1-4799-1934-5 |series=ICSE '15' |___location=Piscataway, New Jersey |pages=459–470 |chapter=Safe Memory-leak Fixing for C Programs}}</ref> with automated insertion of missing memory deallocation statements.

* [[static analysis]] warning repair<ref>{{Cite journal |last1=Etemadi Someoliayi |first1=Khashayar |last2=Harrand |first2=Nicolas Yves Maurice |last3=Larsen |first3=Simon |last4=Adzemovic |first4=Haris |last5=Luong Phu |first5=Henry |last6=Verma |first6=Ashutosh |last7=Madeiral |first7=Fernanda |last8=Wikstrom |first8=Douglas |last9=Monperrus |first9=Martin |date=2022 |title=Sorald: Automatic Patch Suggestions for SonarQube Static Analysis Violations |url=https://ieeexplore.ieee.org/document/9756950 |journal=IEEE Transactions on Dependable and Secure Computing |pages=1 |doi=10.1109/TDSC.2022.3167316 |s2cid=232307680 |issn=1545-5971}}</ref>

Comparing to generate-and-validate techniques, template-based techniques tend to have better bug-fixing accuracy but a much narrowed scope.<ref name="kali" /><ref name="leakfix" />

Line 59 ⟶ 53:

There are multiple uses of automatic bug fixing:

* In a development environment: When encountering a bug the developer activates a feature to search for a patch (for instance by clicking on a button). This search can also happen in the background, when the IDE proactively searches for solutions to potential problems, without waiting for explicit action from the developer.<ref>{{Cite journal |last1=Muşlu |first1=Kıvanç |last2=Brun |first2=Yuriy |last3=Holmes |first3=Reid |last4=Ernst |first4=Michael D. |last5=Notkin |first5=David |last6=Muşlu |first6=Kıvanç |last7=Brun |first7=Yuriy |last8=Holmes |first8=Reid |last9=Ernst |first9=Michael D. |last10=Notkin |first10=David |date=19 October 2012 |title=Speculative analysis of integrated development environment recommendations, Speculative analysis of integrated development environment recommendations |journal=ACM SIGPLAN Notices |volume=47 |issue=10 |pages=669, 669–682, 682 |citeseerx=10.1.1.259.6341 |doi=10.1145/2384616.2384665 |issn=0362-1340 |s2cid=5795141}}</ref>

* At runtime: When a failure happens at runtime, a binary patch can be searched for and [[Self-modifying code|applied online]]. An example of such a repair system is ClearView,<ref name="clearview">{{Cite book |last=Perkins |first=Jeff H. |title=Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles |date=2009 |publisher=ACM |isbn=978-1-60558-752-3 |pages=87–102 |chapter=Automatically patching errors in deployed software |citeseerx=10.1.1.157.5877 |doi=10.1145/1629575.1629585 |display-authors=etal |s2cid=7597529}}</ref> which does repair on x86 code, with x86 binary patches.

* In a continuous integration server: When a build fails during continuous integration, a patch search can be attempted as soon as the build has failed. If the search is successful, the patch is provided to the developer.<ref>{{Cite book |last1=Urli |first1=Simon |title=How to design a program repair bot?: insights from the repairnator project |last2=Yu |first2=Zhongxing |last3=Seinturier |first3=Lionel |last4=Monperrus |first4=Martin |date=27 May 2018 |isbn=9781450356596 |pages=95–104 |chapter=How to design a program repair bot? |arxiv=1811.09852 |doi=10.1145/3183519.3183540 |chapter-url=https://hal.archives-ouvertes.fr/hal-01691496/document |s2cid=49237449}}</ref> When a synthesized patch is suggested to the developers as pull-request, an explanation has to be provided in addition to the code changes (e.g. a pull request title and description).<ref>{{Cite book |last=Monperrus |first=Martin |title=2019 IEEE/ACM 1st International Workshop on Bots in Software Engineering (BotSE) |year=2019 |isbn=978-1-7281-2262-5 |pages=12–15 |chapter=Explainable Software Bot Contributions: Case Study of Automated Bug Fixes |arxiv=1905.02597 |bibcode=2019arXiv190502597M |doi=10.1109/BotSE.2019.00010 |s2cid=146808763}}</ref> An experiment has shown that generated patches can be accepted by open-source developers and merged in the code repository.<ref>{{Cite journal |last1=Monperrus |first1=Martin |last2=Urli |first2=Simon |last3=Durieux |first3=Thomas |last4=Martinez |first4=Matias |last5=Baudry |first5=Benoit |last6=Seinturier |first6=Lionel |date=2019 |title=Repairnator patches programs automatically |url=https://hal.archives-ouvertes.fr/hal-02267512/document |journal=Ubiquity |volume=2019 |issue=July |pages=1–12 |arxiv=1910.06247 |bibcode=2019arXiv191006247M |doi=10.1145/3349589 |s2cid=198986312}}</ref>

* At runtime: When a failure happens at runtime, a binary patch can be searched for and [[Self-modifying code|applied online]]. An example of such a repair system is ClearView,<ref name="clearview">{{Cite book |last=Perkins |first=Jeff H. |title=Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles |date=2009 |publisher=ACM |isbn=978-1-60558-752-3 |pages=87–102 |chapter=Automatically patching errors in deployed software |citeseerx=10.1.1.157.5877 |doi=10.1145/1629575.1629585 |display-authors=etal |s2cid=7597529}}</ref> which does repair on x86 code, with x86 binary patches. The Itzal system<ref>{{Cite book |last1=Durieux |first1=Thomas |title=2017 IEEE/ACM 39th International Conference on Software Engineering: New Ideas and Emerging Technologies Results Track (ICSE-NIER) |last2=Hamadi |first2=Youssef |last3=Monperrus |first3=Martin |year=2017 |isbn=978-1-5386-2675-7 |pages=23–26 |chapter=Production-driven patch generation |arxiv=1812.04475 |doi=10.1109/icse-nier.2017.8 |chapter-url=https://hal.archives-ouvertes.fr/hal-01463689/document |s2cid=7737476}}</ref> is different from Clearview: while the repair search happens at runtime, in production, the produced patches are at the source code level. The BikiniProxy system does online repair of JavaScript errors happening in the browser.<ref>{{Cite book |last1=Durieux |first1=Thomas |title=2018 IEEE 29th International Symposium on Software Reliability Engineering (ISSRE) |last2=Hamadi |first2=Youssef |last3=Monperrus |first3=Martin |year=2018 |isbn=978-1-5386-8321-7 |pages=1–12 |chapter=Fully Automated HTML and Javascript Rewriting for Constructing a Self-Healing Web Proxy |arxiv=1803.08725 |bibcode=2018arXiv180308725D |doi=10.1109/ISSRE.2018.00012 |s2cid=4268784}}</ref>

* In response to security disclosures: when vulnerabilities are discovered and registered as CVEs, one can ask a repair system to generate a security patch.<ref>{{Cite journal |last1=Chen |first1=Zimin |last2=Kommrusch |first2=Steve James |last3=Monperrus |first3=Martin |date=2022 |title=Neural Transfer Learning for Repairing Security Vulnerabilities in C Code |url=https://ieeexplore.ieee.org/document/9699412 |journal=IEEE Transactions on Software Engineering |pages=1 |doi=10.1109/TSE.2022.3147265 |s2cid=233296471 |issn=0098-5589}}</ref>

== Search space ==

In essence, automatic bug fixing is a search activity, whether deductive-based or heuristic-based. The search space of automatic bug fixing is composed of all edits that can be possibly made to a program. There have been studies to understand the structure of this search space. Qi et al.<ref>{{Cite book |last1=Qi |first1=Yuhua |title=The strength of random search on automated program repair |last2=Mao |first2=Xiaoguang |last3=Lei |first3=Yan |last4=Dai |first4=Ziying |last5=Wang |first5=Chengsong |date=2014-05-31 |publisher=ACM |isbn=9781450327565 |pages=254–265 |doi=10.1145/2568225.2568254 |s2cid=14976851}}</ref> showed that the original fitness function of Genprog is not better than random search to drive the search. Martinez et al.<ref>{{Cite journal |last1=Martinez |first1=Matias |last2=Monperrus |first2=Martin |date=2013-11-28 |title=Mining software repair models for reasoning on the search space of automated program fixing |url=https://hal.archives-ouvertes.fr/hal-00903808/document |journal=Empirical Software Engineering |language=en |volume=20 |issue=1 |pages=176–205 |arxiv=1311.3414 |bibcode=2013arXiv1311.3414M |doi=10.1007/s10664-013-9282-8 |issn=1382-3256 |s2cid=1676168}}</ref> explored the imbalance between possible repair actions, showing its significant impact on the search. Long et al.'s<ref name="spaceanalysis" /> study indicated that correct patches can be considered as sparse in the search space and that incorrect overfitting patches are vastly more abundant (see also discussion about overfitting below).

If one explicitly enumerates all possible variants in a repair algorithm, this defines a design space for program repair.<ref name="Martinez2019">{{Cite journal |last1=Martinez |first1=Matias |last2=Monperrus |first2=Martin |date=2019 |title=Astor: Exploring the design space of generate-and-validate program repair beyond GenProg |journal=Journal of Systems and Software |volume=151 |pages=65–80 |arxiv=1802.03365 |doi=10.1016/j.jss.2019.01.069 |s2cid=3619320}}</ref> Each variant selects an algorithm involved at some point in the repair process (e.g. the fault localization algorithm), or selects a specific heuristic which yields different patches. For instance, in the design space of generate-and-validate program repair, there is one variation point about the granularity of the program elements to be modified: an expression, a statement, a block, etc.<ref name="Martinez2019" />

It is also possible to analyze whether known search spaces encompass existing commits.<ref>{{Cite journal|last1=Etemadi|first1=Khashayar|last2=Tarighat|first2=Niloofar|last3=Yadav|first3=Siddharth|last4=Martinez|first4=Matias|last5=Monperrus|first5=Martin|date=2022|title=Estimating the potential of program repair search spaces with commit analysis|url=https://linkinghub.elsevier.com/retrieve/pii/S0164121222000309|journal=Journal of Systems and Software|language=en|volume=188|pages=111263|doi=10.1016/j.jss.2022.111263|s2cid=246485882 }}</ref> Such a search space analysis means [[Mining software repositories|mining a software repository]], this results in an approximation of the applicability and usefulness of a given repair algorithm.

== Overfitting ==

Sometimes, in test-suite based program repair, tools generate patches that pass the test suite, yet are actually incorrect, this is known as the "overfitting" problem.<ref name="overfitting">{{Cite book |last1=Smith |first1=Edward K. |title=Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering |last2=Barr |first2=Earl T. |last3=Le Goues |first3=Claire |last4=Brun |first4=Yuriy |date=2015 |publisher=ACM |isbn=978-1-4503-3675-8 |series=ESEC/FSE 2015 |___location=New York, New York |pages=532–543 |chapter=Is the Cure Worse Than the Disease? Overfitting in Automated Program Repair |doi=10.1145/2786805.2786825 |s2cid=6300790}}</ref> "Overfitting" in this context refers to the fact that the patch overfits to the test inputs. There are different kinds of overfitting:<ref name="Yu2018">{{Cite journal |last1=Yu |first1=Zhongxing |last2=Martinez |first2=Matias |last3=Danglot |first3=Benjamin |last4=Durieux |first4=Thomas |last5=Monperrus |first5=Martin |year=2018 |title=Alleviating patch overfitting with automatic test generation: a study of feasibility and effectiveness for the Nopol repair system |journal=Empirical Software Engineering |volume=24 |pages=33–67 |arxiv=1810.10614 |bibcode=2018arXiv181010614Y |doi=10.1007/s10664-018-9619-4 |issn=1382-3256 |s2cid=21659819}}</ref> incomplete fixing means that only some buggy inputs are fixed, regression introduction means some previously working features are broken after the patch (because they were poorly tested). Early prototypes for automatic repair suffered a lot from overfitting: on the Manybugs C benchmark, Qi et al.<ref name="kali" /> reported that 104/110 of plausible GenProg patches were overfitting; on the Defects4J Java benchmark, Martinez et al.<ref name="martinezdefects4j">{{Cite journal |last1=Martinez |first1=Matias |last2=Durieux |first2=Thomas |last3=Sommerard |first3=Romain |last4=Xuan |first4=Jifeng |last5=Monperrus |first5=Martin |date=2016-10-25 |title=Automatic repair of real bugs in java: a large-scale experiment on the defects4j dataset |url=https://hal.archives-ouvertes.fr/hal-01387556/document |journal=Empirical Software Engineering |language=en |volume=22 |issue=4 |pages=1936–1964 |arxiv=1811.02429 |doi=10.1007/s10664-016-9470-4 |issn=1382-3256 |s2cid=24538587}}</ref> reported that 73/84 plausible patches as overfitting. In the context of synthesis-based repair, Le et al.<ref>{{Cite journal |last1=Le |first1=Xuan Bach D. |last2=Thung |first2=Ferdian |last3=Lo |first3=David |last4=Goues |first4=Claire Le |date=2018-03-02 |title=Overfitting in semantics-based automated program repair |url=https://ink.library.smu.edu.sg/sis_research/3986 |journal=Empirical Software Engineering |language=en |volume=23 |issue=5 |pages=3007–3033 |doi=10.1007/s10664-017-9577-2 |issn=1382-3256 |s2cid=3635768}}</ref> obtained more than 80% of overfitting patches.

One way to avoid overfitting is to filter out the generated patches. This can be done based on dynamic analysis,.<ref>{{Cite journal|last1=Xin|first1=Qi|last2=Reiss|first2=Steven P.|date=2017-07-10|title=Identifying test-suite-overfitted patches through test case generation|url=http://dx.doi.org/10.1145/3092703.3092718|journal=Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis|pages=226–236|___location=New York, NY, USA|publisher=ACM|doi=10.1145/3092703.3092718|isbn=978-1-4503-5076-1|s2cid=20562134}}</ref> or static code analysis of the generated patches.<ref>{{Cite journal|last1=Ye|first1=He|last2=Gu|first2=Jian|last3=Martinez|first3=Matias|last4=Durieux|first4=Thomas|last5=Monperrus|first5=Martin|date=2021|title=Automated Classification of Overfitting Patches with Statically Extracted Code Features|url=https://arxiv.org/abs/1910.12057|journal=IEEE Transactions on Software Engineering|volume=48 |issue=8 |pages=2920–2938|doi=10.1109/tse.2021.3071750|issn=0098-5589|arxiv=1910.12057|s2cid=204954907}}</ref> When a reference patch is available, a state of the art technique is to generate tests based on the patched version, such that the generated tests capture the expected behavior. While the sampling of the input ___domain by test generation is incomplete by construction, it has been shown to be effective at detecting overfitting patches, and even at finding human errors done during manual classification of patches.<ref>{{Cite journal|last1=Ye|first1=He|last2=Martinez|first2=Matias|last3=Monperrus|first3=Martin|date=2021|title=Automated patch assessment for program repair at scale|url=https://arxiv.org/abs/1909.13694|journal=Empirical Software Engineering|language=en|volume=26|issue=2|pages=20|doi=10.1007/s10664-020-09920-w|issn=1382-3256|arxiv=1909.13694|s2cid=203594006}}</ref>

== Limitations of automatic bug-fixing ==

Line 90 ⟶ 78:

In C, the Manybugs benchmark collected by GenProg authors contains 69 real world defects and it is widely used to evaluate many other bug-fixing tools for C.<ref name=genprog2012 /><ref name=prophet /><ref name=spr /><ref name=angelix />

In Java, the main benchmark is Defects4J, initially explored by Martinez et al.,<ref name="martinezdefects4j" /> and now extensively used in most research papers on program repair for Java.<ref name="capgen">{{Cite journal |last1=Wen |first1=Ming |last2=Chen |first2=Junjie |last3=Wu |first3=Rongxin |last4=Hao |first4=Dan |last5=Cheung |first5=Shing-Chi |date=2018 |title=Context-aware patch generation for better automated program repair |journal=Proceedings of the 40th International Conference on Software Engineering - ICSE '18 |___location=New York, New York, USA |publisher=ACM Press |pages=1–11 |doi=10.1145/3180155.3180233 |isbn=9781450356381 |s2cid=3374770|url=http://repository.ust.hk/ir/Record/1783.1-92186 }}</ref><ref>{{Cite journal |last1=Hua |first1=Jinru |last2=Zhang |first2=Mengshi |last3=Wang |first3=Kaiyuan |last4=Khurshid |first4=Sarfraz |date=2018 |title=Towards practical program repair with on-demand candidate generation |journal=Proceedings of the 40th International Conference on Software Engineering - ICSE '18 |___location=New York, New York, USA |publisher=ACM Press |pages=12–23 |doi=10.1145/3180155.3180245 |isbn=9781450356381 |s2cid=49666327|doi-access=free }}</ref> Alternative benchmarks exist, such as the Quixbugs benchmark,<ref>{{Cite journal |last1=Lin |first1=Derrick |last2=Koppel |first2=James |last3=Chen |first3=Angela |last4=Solar-Lezama |first4=Armando |date=2017 |title=QuixBugs: a multi-lingual program repair benchmark set based on the quixey challenge |journal=Proceedings Companion of the 2017 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity - SPLASH Companion 2017 |___location=New York, New York, USA |publisher=ACM Press |pages=55–56 |doi=10.1145/3135932.3135941 |isbn=9781450355148 |doi-access=free}}</ref> which contains original bugs for program repair.<ref>{{Cite journal |last1=Ye |first1=He |last2=Martinez |first2=Matias |last3=Durieux |first3=Thomas |last4=Monperrus |first4=Martin |date=2021 |title=A comprehensive study of automatic program repair on the QuixBugs benchmark |url=https://arxiv.org/pdf/1805.03454 |journal=Journal of Systems and Software |language=en |volume=171 |pages=110825 |arxiv=1805.03454 |doi=10.1016/j.jss.2020.110825|issn=0164-1212 |s2cid=221978135 }}</ref> Other benchmarks of Java bugs include Bugs.jar,<ref>{{Cite journal |last1=Saha |first1=Ripon K. |last2=Lyu |first2=Yingjun |last3=Lam |first3=Wing |last4=Yoshida |first4=Hiroaki |last5=Prasad |first5=Mukul R. |date=2018 |title=Bugs.jar: a large-scale, diverse dataset of real-world Java bugs |url=http://dl.acm.org/citation.cfm?doid=3196398.3196473 |journal=Proceedings of the 15th International Conference on Mining Software Repositories |series=MSR '18 |language=en |pages=10–13 |doi=10.1145/3196398.3196473 |isbn=9781450357166 |s2cid=50770093}}</ref> based on past commits, and BEARS<ref>{{Cite book |last1=Madeiral |first1=Fernanda |title=2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER) |last2=Urli |first2=Simon |last3=Maia |first3=Marcelo |last4=Monperrus |first4=Martin |year=2019 |isbn=978-1-7281-0591-8 |pages=468–478 |chapter=BEARS: An Extensible Java Bug Benchmark for Automatic Program Repair Studies |arxiv=1901.06024 |doi=10.1109/SANER.2019.8667991 |s2cid=58028949}}</ref> which is a benchmark of continuous integration build failures.

== Example tools ==

Line 111 ⟶ 99:

* PAR:<ref name=par /> A generate-and-validate tool that uses a set of manually defined fix templates. A later study raised concerns about the generalizability of the fix templates in PAR.<ref name=criticalreview />

* NOPOL:<ref name="nopol">{{Cite journal |last1=Xuan |first1=Jifeng |last2=Martinez |first2=Matias |last3=DeMarco |first3=Favio |last4=Clément |first4=Maxime |last5=Lamelas |first5=Sebastian |last6=Durieux |first6=Thomas |last7=Le Berre |first7=Daniel |last8=Monperrus |first8=Martin |date=2016 |title=Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs |url=https://hal.archives-ouvertes.fr/hal-01285008/document |journal=IEEE Transactions on Software Engineering |volume=43 |pages=34–55 |arxiv=1811.04211 |doi=10.1109/TSE.2016.2560811 |s2cid=15132155}}</ref> A solver-based tool focusing on modifying condition statements.

* QACrashFix:<ref name="QAFix">{{Cite book |last1=Gao |first1=Qing |title=2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE) |last2=Zhang |first2=Hansheng |last3=Wang |first3=Jie |last4=Xiong |first4=Yingfei |last5=Zhang |first5=Lu |last6=Mei |first6=Hong |date=2015 |publisher=IEEE |isbn=978-1-5090-0025-8 |pages=307–318 |chapter=Fixing Recurring Crash Bugs via Analyzing Q&A Sites |doi=10.1109/ASE.2015.81 |s2cid=2513924}}</ref> A tool that fixes Java crash bugs by mining fixes from Q&A web site.

* Astor:<ref name="astor">{{Cite book |last1=Martinez |first1=Matias |title=Proceedings of ISSTA, Demonstration Track |last2=Monperrus |first2=Martin |date=2016 |isbn=978-1-4503-4390-9 |pages=441–444 |chapter=ASTOR: A Program Repair Library for Java |doi=10.1145/2931037.2948705 |chapter-url=https://hal.archives-ouvertes.fr/hal-01321615/file/astor.pdf |s2cid=7322935}}</ref> An automatic repair library for Java, containing jGenProg, a Java implementation of GenProg.

* ARJA:<ref name="arja">{{Cite journal |last1=Yuan |first1=Yuan |last2=Banzhaf |first2=Wolfgang |date=2020 |title=ARJA: Automated Repair of Java Programs via Multi-Objective Genetic Programming |url=https://doi.org/10.1109/TSE.2018.2874648 |journal=IEEE Transactions on Software Engineering |volume=46 |issue=10 |pages=1040–1067 |arxiv=1712.07804 |doi=10.1109/TSE.2018.2874648|s2cid=25222219 }}</ref> A repair tool for Java based on multi-objective genetic programming.

* NpeFix:<ref name="npefix">{{Cite book |last=Durieux |first=Thomas |title=2017 IEEE 24th International Conference on Software Analysis, Evolution and Reengineering (SANER) |date=2017 |isbn=978-1-5090-5501-2 |pages=349–358 |chapter=Dynamic Patch Generation for Null Pointer Exceptions Using Metaprogramming |arxiv=1812.00409 |doi=10.1109/SANER.2017.7884635 |s2cid=2736203}}</ref> An automatic repair tool for NullPointerException in Java, available [https://github.com/Spirals-Team/npefix on Github].