Automatic bug fixing: Difference between revisions

Revision as of 10:29, 15 October 2022

Revision as of 04:52, 25 December 2022

Line 40:

[[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 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 |lastlast1=Ye |firstfirst1=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:

* [[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 |lastlast1=Muntean |firstfirst1=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 |lastlast1=Etemadi Someoliayi |firstfirst1=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–11 |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 75:

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=12920–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 ==