Content deleted Content added
cleaning up extensive COI / selfcite |
Jnestorius (talk | contribs) |
||
| (24 intermediate revisions by 16 users not shown) | |||
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><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> It is also commonly referred to as ''automatic patch generation'', ''automatic bug repair'', or ''automatic program repair''.<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
== Specification ==
Automatic bug fixing is made according to a specification of the expected behavior which can be for instance a [[formal specification]] or a [[test suite]].<ref name="genprog2009">{{Cite book |last1=Weimer |first1=Westley |title=Proceedings of the 31st International Conference on Software Engineering |last2=Nguyen |first2=ThanhVu |last3=Le Goues |first3=Claire|author3-link=Claire Le Goues |last4=Forrest |first4=Stephanie |date=2009 |publisher=IEEE |isbn=978-1-4244-3453-4 |pages=364–374 |chapter=Automatically finding patches using genetic programming |citeseerx=10.1.1.147.8995 |doi=10.1109/ICSE.2009.5070536 |s2cid=1706697}}</ref>
A test-suite – the input/output pairs specify the functionality of the program, possibly captured in [[Assertion (software development)|assertions]] can be used as a [[test oracle]] to drive the search. This oracle can in fact be divided between the ''bug oracle'' that exposes the faulty behavior, and the ''regression oracle'', which encapsulates the functionality any program repair method must preserve. Note that a test suite is typically incomplete and does not cover all possible cases. Therefore, it is often possible for a validated patch to produce expected outputs for all inputs in the test suite but incorrect outputs for other inputs.<ref name="kali">{{Cite book |last1=Qi |first1=Zichao |title=Proceedings of the 2015 International Symposium on Software Testing and Analysis |last2=Long |first2=Fan |last3=Achour |first3=Sara |last4=Rinard |first4=Martin |date=2015 |publisher=ACM |isbn=978-1-4503-3620-8 |chapter=An
Another way to specify the expected behavior is to use [[formal specification]]s<ref name="autofixe">{{Cite journal |last1=Pei |first1=Yu |last2=Furia |first2=Carlo A. |last3=Nordio |first3=Martin |last4=Wei |first4=Yi |last5=Meyer |first5=Bertrand |last6=Zeller |first6=Andreas |date=May 2014 |title=Automated Fixing of Programs with Contracts |journal=IEEE Transactions on Software Engineering |volume=40 |issue=5 |pages=427–449 |arxiv=1403.1117 |bibcode=2014arXiv1403.1117P |doi=10.1109/TSE.2014.2312918 |s2cid=53302638}}</ref><ref>{{Cite journal |title=Contract-based Data Structure Repair Using Alloy |citeseerx=10.1.1.182.4390}}</ref> Verification against full specifications that specify the whole program behavior including functionalities is less common because such specifications are typically not available in practice and the computation cost of such [[formal verification|verification]] is prohibitive. For specific classes of errors, however, implicit partial specifications are often available. For example, there are targeted bug-fixing techniques validating that the patched program can no longer trigger overflow errors in the same execution path.<ref name="codephage" />
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
<!-- 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|author1-link=Claire Le Goues |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
<!-- fix templates -->
Line 28:
<!-- repair and synthesis -->
Under certain assumptions, it is possible to state the repair problem as a synthesis problem.
SemFix<ref name="semfix
Dynamoth 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 |author4-link=Claire Le Goues|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 |author3-link=Claire Le Goues|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.
=== Data-driven ===
Line 37:
[[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" />
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 |arxiv=1902.06111 }}</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.
=== Template-based repair ===
Line 61:
== 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|author3-link=Claire Le Goues |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: 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. 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
Alternatively, Tian et al. propose heuristic approaches to assess patch correctness.<ref>{{cite news |last1=Tian |first1=Haoye |last2=Liu |first2=Kui |last3=Kaboré |first3=Abdoul Kader |last4=Koyuncu |first4=Anil |last5=Li |first5=Li |last6=Klein |first6=Jacques |last7=Bissyandé |first7=Tegawendé F. |title=Evaluating representation learning of code changes for predicting patch correctness in program repair |url=https://dl.acm.org/doi/abs/10.1145/3324884.3416532 |work=Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering |publisher=Association for Computing Machinery |date=27 January 2021 |pages=981–992 |doi=10.1145/3324884.3416532|isbn=9781450367684 }}</ref><ref>{{cite book |last1=Tian |first1=Haoye |last2=Tang |first2=Xunzhu |last3=Habib |first3=Andrew |last4=Wang |first4=Shangwen |last5=Liu |first5=Kui |last6=Xia |first6=Xin |last7=Klein |first7=Jacques |last8=BissyandÉ |first8=TegawendÉ F. |title=Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering |chapter=Is this Change the Answer to that Problem?: Correlating Descriptions of Bug and Code Changes for Evaluating Patch Correctness |date=5 January 2023 |pages=1–13 |doi=10.1145/3551349.3556914 |chapter-url=https://dl.acm.org/doi/abs/10.1145/3551349.3556914 |publisher=Association for Computing Machinery|s2cid=251403079 |arxiv=2208.04125 |isbn=9781450394758 }}</ref>
== Limitations of automatic bug-fixing ==
Line 78 ⟶ 79:
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 (programming language)|Java]], the main benchmark is Defects4J now extensively used in most research papers on program repair for Java.<ref name="capgen">{{Cite
== Example tools ==
Line 92 ⟶ 93:
* LeakFix:<ref name=leakfix /> A tool that automatically fixes memory leaks in C programs.
* Prophet:<ref name=prophet /> The first generate-and-validate tool that uses machine learning techniques to learn useful knowledge from past human patches to recognize correct patches. It is evaluated on the same benchmark as GenProg and generate correct patches (i.e., equivalent to human patches) for 18 out of 69 cases.<ref name=prophet />
* SearchRepair:<ref name=searchrepair /> A tool for replacing buggy code using snippets of code from elsewhere. It is evaluated on the IntroClass benchmark<ref name="introclassmanybugs">{{Cite journal |last1=Le Goues |first1=Claire|author1-link=Claire Le Goues |last2=Holtschulte |first2=Neal |last3=Smith |first3=Edward |last4=Brun |first4=Yuriy |last5=Devanbu |first5=Premkumar |last6=Forrest |first6=Stephanie |last7=Weimer |first7=Westley |date=2015 |title=The Many ''Bugs'' and Intro ''Class'' Benchmarks for Automated Repair of C Programs |journal=IEEE Transactions on Software Engineering |volume=41 |issue=12 |pages=1236–1256 |doi=10.1109/TSE.2015.2454513 |doi-access=free}}</ref> and generates much higher quality patches on that benchmark than GenProg, RSRepair, and AE.
* Angelix:<ref name=angelix /> An improved solver-based bug-fixing tool. It is evaluated on the GenProg benchmark. For 10 out of the 69 cases, it generate patches that is equivalent to human patches.
* Learn2Fix:<ref name=learn2fix /> The first human-in-the-loop semi-automatic repair tool. Extends GenProg to learn the condition under which a semantic bug is observed by systematic queries to the user who is reporting the bug. Only works for programs that take and produce integers.
Line 98 ⟶ 99:
=== Java ===
* PAR:<ref name=par /> A generate-and-validate tool that uses a set of manually defined fix templates.
* 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.
* 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.
Line 112 ⟶ 113:
* DeepCode integrates public and private [[GitHub]], [[GitLab]] and [[Bitbucket]] [[Software repository|repositories]] to identify code-fixes and improve software.<ref>{{Cite web |title=AI is coming for your coding job |url=https://sifted.eu/articles/ai-is-coming-for-your-coding-job/ |access-date=2019-04-15 |website=Sifted |date=13 March 2019 |language=en-US}}</ref>
* [[Kodezi, Inc.|Kodezi]] utilizes opensource data from [[GitHub]] [[Software repository|repositories]], [[Stack Overflow]], and private trained models to analyze code, provide solutions, and descriptions about the coding bugs instantly.<ref>{{Cite web |title=Ishraq Khan, Revolutionizing the Programming Scene in 2021 |url=https://www.techtimes.com/articles/265325/20210913/ishraq-khan-revolutionizing-the-programming-scene-in-2021.htm |access-date=2022-10-15 |website=TechTimes|date=13 September 2019 |language=en-US}}</ref>
== References ==
Line 119 ⟶ 120:
== External links ==
* {{URL|
[[Category:Debugging]]
| |||