程序缺陷自動修復(fù)研究進展及關(guān)鍵問題

曹鶴玲，劉 昱，趙晨陽，王玉華

1(河南工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，鄭州 450001) 2(河南工業(yè)大學(xué) 糧食信息處理與控制教育部重點實驗室，鄭州 450001)

1 引 言

在軟件開發(fā)過程中，不可避免地會產(chǎn)生缺陷，且隨著軟件規(guī)模和復(fù)雜度的不斷增長，缺陷的數(shù)量也逐年增加[1]，有相當(dāng)一部分人力和物力資源用于缺陷的定位與修復(fù)[2，3].如何能夠有效降低軟件維護成本，減少軟件維護時間已經(jīng)成為了一個亟待解決的問題.程序缺陷自動修復(fù)方法應(yīng)運而生，其能節(jié)省大量的時間、人力和物力，具有極高的科研價值.該方法首先定位到可能含有缺陷的程序語句，并依據(jù)存在缺陷可能性的大小對可疑程序語句進行排序；然后利用各種補丁生成方式自動地生成對應(yīng)的補丁；最后使用某種策略對補丁進行驗證，并輸出正確的補丁.通過該方法產(chǎn)生的補丁既可以自動添加到程序中，也可以為人工改進代碼提供有用的指導(dǎo)[4].

早期的程序缺陷主要通過手工修復(fù)，然而程序缺陷數(shù)量的激增使得這項工作日漸繁重，手工修復(fù)的能力已逐漸不能滿足需求.近年來，程序缺陷自動修復(fù)獲得了廣泛的關(guān)注，其已成為軟件工程領(lǐng)域的研究熱點，學(xué)術(shù)界也涌現(xiàn)出了大批的研究成果，產(chǎn)生了許多頗具影響力的貢獻.盡管如此，程序缺陷自動修復(fù)仍處于初級階段，只能修復(fù)部分缺陷，并且在工業(yè)界成功應(yīng)用的案例少之又少，其進一步的發(fā)展還面臨著許多的問題和挑戰(zhàn).

目前已有一些文獻對程序缺陷自動修復(fù)問題進行了調(diào)研.在早期的工作中，Le Goues等人[5]對其團隊核心研究工作的創(chuàng)新和不足之處以及當(dāng)時程序缺陷自動修復(fù)方法面臨的挑戰(zhàn)進行了剖析，為以后的研究工作打下了良好的基礎(chǔ).玄躋峰等人[4]將基于測試集的程序缺陷自動修復(fù)方法劃分為基于搜索、基于代碼窮舉以及基于約束求解的方法，并對上述3類方法進行了詳細的論述.Monperrus[6]主要整理和總結(jié)了行為型修復(fù)(behavioral repair)方法和狀態(tài)型修復(fù)(state repair)方法的重要研究成果.王贊等人[7]總結(jié)了缺陷定位階段、補丁生成階段和補丁驗證階段的研究進展，并梳理了程序缺陷自動修復(fù)領(lǐng)域的缺陷庫和研究團隊.李斌[8]等人從程序規(guī)約的角度對程序缺陷自動修復(fù)問題與技術(shù)進行了梳理和分析.Gazzola等人[9]結(jié)合108篇相關(guān)文獻對程序缺陷自動修復(fù)領(lǐng)域的研究成果進行了回顧，對自動修復(fù)方法的能力進行了批判性的分析，并從3個方面分析了當(dāng)時程序缺陷自動修復(fù)方法面臨的關(guān)鍵挑戰(zhàn).此外，還有一些相關(guān)的研究工作，但經(jīng)調(diào)研發(fā)現(xiàn)他們僅對以往傳統(tǒng)的程序缺陷自動修復(fù)方法進行了詳細綜述，針對最新涌現(xiàn)出的如基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法等未有全面的研究綜述.

基于此，為了便于研究者在現(xiàn)有研究工作的基礎(chǔ)上取得更好的進展，非常有必要對目前程序缺陷自動修復(fù)方法的最新研究成果進行全面分析和總結(jié).因此，我們首先在谷歌學(xué)術(shù)、IEEE、Web of Science、Springer、ACM和DBLP等搜索引擎和文獻數(shù)據(jù)庫中對2001年～2021年的相關(guān)文獻進行檢索，檢索時采用的主要關(guān)鍵詞包括“bug/defect/program/software/fault repair/fix”、“缺陷修復(fù)”、“程序修復(fù)”和“缺陷庫”等，隨后我們進一步篩選了檢索出的論文，最終確定了與本文綜述問題直接相關(guān)的高質(zhì)量論文共79篇，其中包含發(fā)表于權(quán)威期刊(TSE(7篇)、TOSEM(3篇)、軟件學(xué)報(4篇)、計算機學(xué)報(1篇))的論文共15篇，以及發(fā)表于權(quán)威會議(ICSE(15篇)、ICSME(1篇)、PLDI(1篇)、POPL(1篇)、ESEC/FSE(1篇)、ASE(5篇)、ISSTA(4篇)、AAAI(1篇))的論文共29篇.本文不僅吸納了關(guān)于基于搜索和基于語義的程序缺陷自動修復(fù)方法的最新研究成果，還首次系統(tǒng)總結(jié)了基于機器學(xué)習(xí)的和基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法.除此之外，將程序缺陷自動修復(fù)領(lǐng)域常用的缺陷庫劃分為了C/C++、Java和多種語言的缺陷庫，并進行了系統(tǒng)地總結(jié)，特別梳理了缺陷庫的適用場景以及對程序缺陷自動修復(fù)工作的貢獻.最后，分析了程序缺陷自動修復(fù)在工業(yè)界的應(yīng)用現(xiàn)狀并總結(jié)了該領(lǐng)域面臨的關(guān)鍵問題及未來研究的方向.

2 研究框架

程序缺陷自動修復(fù)方法針對各種不同的缺陷修復(fù)場景，將整個修復(fù)過程自動化[8]，實質(zhì)上就是自動地定位程序缺陷、生成程序補丁并進行補丁驗證.圖1給出了程序缺陷自動修復(fù)的研究框架.

如圖1所示，定位階段通過缺陷定位策略找出可能導(dǎo)致程序錯誤的可疑位置，缺陷定位結(jié)果的精度直接關(guān)系到補丁的生成效率.缺陷定位方法可分為動態(tài)缺陷定位方法與靜態(tài)缺陷定位方法[10].動態(tài)缺陷定位方法通過對測試用例的執(zhí)行行為與運行結(jié)果進行分析，并基于特定模型來定位缺陷語句的可能位置，具有較高的定位準(zhǔn)確性，當(dāng)前此類方法中的主流是基于頻譜的缺陷定位方法[7]，其通過執(zhí)行測試用例獲取程序頻譜，而后分析頻譜來定位程序缺陷[11].靜態(tài)缺陷定位方法通過分析缺陷報告和程序模塊的文本內(nèi)容并提取特征，基于特定模型確定可疑的程序語句，其不需要執(zhí)行測試用例，不會受到程序規(guī)模和編程語言等因素的影響，基于信息檢索的缺陷定位(Information Retrieval-Based Bug Localization，IRBL)是目前靜態(tài)缺陷定位研究中的熱點[12]，其廣泛應(yīng)用于基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法中.補丁生成階段按照一定的修復(fù)規(guī)則逐個對可疑缺陷代碼進行相應(yīng)的處理，生成缺陷代碼的補丁.本文根據(jù)補丁生成方式的不同，將程序缺陷自動修復(fù)方法劃分為4類，分別為基于搜索的、基于語義的、基于機器學(xué)習(xí)的和基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法.補丁排序及驗證階段對補丁生成階段產(chǎn)生的候選補丁進行排序和正確性驗證.在驗證時，一方面要檢驗補丁是否成功修復(fù)原有的缺陷，另一方面要檢驗原有的程序功能是否被破壞.對補丁進行驗證的開銷往往較大，利用候選補丁排序技術(shù)有助于提高修復(fù)效率和縮減驗證成本.

圖1 程序缺陷自動修復(fù)研究框架Fig.1 Research framework of automatic program repair

3 基于搜索的程序缺陷自動修復(fù)方法

基于搜索的程序缺陷自動修復(fù)方法利用了基于搜索的軟件工程[13-15](Search Based Software Engineering，SBSE)中的蟻群算法、粒子群優(yōu)化、遺傳算法以及模擬退火等算法.其核心思想是將修復(fù)問題看成是組合優(yōu)化問題，為了修復(fù)程序，將程序中若干位置的代碼更新(修改、刪除、添加代碼)視為個體，即把更新的內(nèi)容當(dāng)作潛在的程序補丁，并把所有通過更新得到的程序補丁作為一個龐大的搜索空間，在這個補丁搜索空間中尋找最優(yōu)可行解，搜索空間的大小取決于代碼修改操作的大小.圖2展示了基于搜索的程序缺陷自動修復(fù)方法的總體流程，可以看出尋找正確補丁的過程是一個迭代的過程.

圖2 基于搜索的程序缺陷自動修復(fù)方法流程Fig.2 Flow of search-based automatic program repair methods

3.1 基于搜索的程序缺陷自動修復(fù)方法研究進展

最早在2008年，Arcuri等人[16]提出了一種協(xié)同進化的方法ABF(Automatic Bug Fixing)來自動修復(fù)程序中的缺陷.該方法將缺陷程序與測試用例進行協(xié)同進化，在多次進化后，篩選出檢測缺陷能力較強的測試用例以及正確性較高的程序補丁.該方法對于缺陷的類型沒有限制，可以輕易修復(fù)難以識別的微小缺陷，但是該方法存在搜索空間過大的問題.

Weimer和Le Goues等人[17-20]于2009年提出了開創(chuàng)性的基于搜索的程序缺陷自動修復(fù)方法GenProg.該方法工作在抽象語法樹(Abstract Syntax Tree，AST)級別，其將源程序轉(zhuǎn)化為AST，通過更新(刪除，插入，替換)AST的節(jié)點獲得新的AST，最后將AST轉(zhuǎn)化為程序補丁.相比于ABF[16]，該方法設(shè)計了限制搜索空間的策略.在2012年，Le Goues等人[21]對GenProg進行了如下優(yōu)化：對GenProg提出新的算法改進，使其能夠擴展到大型程序并且能夠修復(fù)更多的缺陷；利用GenProg固有的并行性，使用云計算資源提供可靠的成本估算.在2013年，Weimer等人[22]提出了程序缺陷自動修復(fù)方法AE，AE利用近似語義等價關(guān)系識別出語義等價的候選補丁，可顯著減少補丁評估數(shù).在2015年，Le Goues等人[23]為程序缺陷自動修復(fù)領(lǐng)域貢獻了兩個經(jīng)典的缺陷庫MangBugs和IntroClass.

在2010年，Debroy等人[24]提出了一種通過使用變異測試中的變異算子來生成程序補丁的缺陷自動修復(fù)方法.該方法按照包含缺陷可能性的大小對程序語句進行排序，并以相同的順序?qū)Τ绦蛘Z句進行變異，以為含有缺陷的程序提供盡可能的修復(fù).Fast等人[25]則在2010年對進化算法進行了優(yōu)化，研究了兩種增強程序修復(fù)適應(yīng)度函數(shù)的方法：對測試集進行選擇來提高效率；形式化規(guī)范以提高精度.Schulte等人[26]在同年嘗試了利用進化算法在匯編代碼級別的修復(fù)，其修復(fù)效率與在源代碼級別的修復(fù)方法不相上下.

在大型程序中通過修改源代碼來自動修復(fù)缺陷通常是一個非常耗時的過程，重新編譯和重新安裝打過補丁的程序需要大量的時間.于是，Qi等人[27，28]在2012年提出了一種弱重新編譯技術(shù).在弱重新編譯技術(shù)中，假設(shè)一個程序是由多個組件構(gòu)成的，對于每個候選補丁，僅將一個組件中更改的代碼片段重新編譯為共享庫.弱重新編譯的優(yōu)點是可以大幅降低重新編譯和重新安裝的成本.他們還構(gòu)建了WAutoRepair，這是一個具有可伸縮性的系統(tǒng)，可以高效地修復(fù)大型C程序中的缺陷.在2013年，Qi等人[29]將回歸測試優(yōu)先級排序應(yīng)用于程序缺陷自動修復(fù)領(lǐng)域，并提出了一種新的優(yōu)先級排序技術(shù)FRTP，可以減少測試用例的執(zhí)行次數(shù).他們還開發(fā)了一個名為TrpAutoRepair的工具來實現(xiàn)FRTP技術(shù).同年，Kim等人[30]從開發(fā)人員手工編寫的修復(fù)程序中總結(jié)出了10種常用的代碼修改模板，由此提出了程序缺陷自動修復(fù)方法PAR(Pattern-based Automatic program Repair).該方法解決了GenProg[17-20]因突變操作的隨機性而產(chǎn)生無效補丁的問題.在2014年，Qi等人[31]提出了一種基于隨機搜索的程序缺陷自動修復(fù)方法RSRepair，并實現(xiàn)了其原型工具.相比于GenProg[17-20]，RSRepair需要的測試用例更少且補丁搜索空間更小，這也證明了隨機搜索相對于遺傳編程具有更強的優(yōu)勢.

Long等人[32]于2016年提出了Prophet，Prophet從現(xiàn)有的補丁數(shù)據(jù)庫中學(xué)習(xí)一個用于補丁排序的最大似然概率模型.對于一個新的缺陷，Prophet會生成一個包含許多候選補丁的搜索空間，然后應(yīng)用所學(xué)習(xí)的模型計算每個補丁可能是正確補丁的概率，接著根據(jù)概率進行補丁排序，最后使用給定的測試套件對候選補丁進行驗證.實驗結(jié)果顯示，在一組含有69個真實缺陷的集合中，Prophet成功修復(fù)了其中的15個，具有一定的準(zhǔn)確度.同年，Le等人[33]提出了一種可以利用軟件開發(fā)歷史中大量的修復(fù)程序來有效地指導(dǎo)和推動程序缺陷修復(fù)的方法.他們認為重復(fù)出現(xiàn)的錯誤修復(fù)在現(xiàn)實程序中很常見，以前出現(xiàn)的修復(fù)模式可以為自動修復(fù)方法提供有用的指導(dǎo).基于此，該方法首先從許多項目的提交歷史中挖掘錯誤修復(fù)模式，然后再使用變異操作符來為含有缺陷的程序生成候選補丁.

在實際項目中，測試套件通常是不夠全面的，因此通過測試套件的補丁并不一定是正確的補丁，該問題即過擬合問題.Xiong等人[34]于2017年提出了一種新穎的程序修復(fù)方法ACS，ACS可產(chǎn)生精確的補丁和緩解過擬合問題.相比于同時期的其他方法，ACS在修復(fù)數(shù)量和精確度上都處于領(lǐng)先地位.同年，Saha等人[35]提出了ELIXIR用于自動修復(fù)C++程序中的缺陷，尤其是修復(fù)表達式與函數(shù)調(diào)用錯誤.ELIXIR使用方法調(diào)用來構(gòu)建更有表現(xiàn)力的修復(fù)表達式以合成程序補丁.Qi等人[36]也于2017年提出了一種程序缺陷自動修復(fù)方法ssFix.該方法假設(shè)用于合成補丁的代碼可以在現(xiàn)有的代碼庫中找到，因此其利用現(xiàn)有代碼來生成修補程序的補丁.

基于搜索的程序缺陷自動修復(fù)方法由于搜索空間可能不包含正確補丁和搜索空間巨大這兩個問題，其性能受到了限制.于是，Wen等人[37]于2018年提出了一種上下文感知的程序缺陷自動修復(fù)方法CapGen.CapGen增加了搜索空間中正確補丁的數(shù)量，同時也解決了由于使用更精細的粒度而導(dǎo)致進一步擴大搜索空間，增加搜索難度的問題.在Defects4J[38]上的實驗結(jié)果顯示，CapGen達到了84%的精度，并且可在絕大多數(shù)不正確的補丁之前優(yōu)先處理正確補丁，其修復(fù)能力優(yōu)于同時期的其它方法.常見的修復(fù)方法是迭代生成可疑程序的候選補丁，然后利用給定的測試用例對其進行驗證，直到找到通過所有測試用例的候選補丁為止.盡管此類方法在概念上較為簡單，但是由于可能需要生成、編譯和測試大量的候選補丁，其修復(fù)效率相對較低，尤其是對于細粒度的缺陷而言.因此，Hua等人[39]在2018年提出了SketchFix，該方法可在測試執(zhí)行期間按需生成候選補丁.在Defects4J[38]上對SketchFix的實驗結(jié)果表明，與其他程序修復(fù)方法相比，SketchFix在AST節(jié)點級粒度下通過表達式操作修復(fù)錯誤的效果更好.同年，Yuan等人[40]提出了一種基于遺傳編程的Java程序自動修復(fù)方法ARJA.ARJA使用一種低粒度的補丁表示，它可以適當(dāng)?shù)亟怦羁赡苡衎ug的位置、操作類型和潛在修復(fù)成分的搜索子空間，使其能夠更有效地探索搜索空間.基于這種低粒度的表示，該方法將程序缺陷自動修復(fù)表述為一個多目標(biāo)搜索問題，引入了一個測試過濾過程來減小計算工作量和搜索空間，并且還提出了一種類型匹配策略，通過利用現(xiàn)有語句的語法模式來創(chuàng)建新的潛在的修復(fù)成分.在對ARJA大規(guī)模的實證研究中，實驗結(jié)果充分顯示了多目標(biāo)搜索和類型匹配策略的有效性，ARJA修復(fù)了比jGenProg[41]和Nopol[42]更多的缺陷，其中包含幾個公認的難以修復(fù)的多位置缺陷.隨后，為擴充補丁生成空間，Yuan等人[43，44]結(jié)合GenProg[17-20]和PAR[30]提出了ARJA-e.ARJA-e利用冗余假設(shè)和修復(fù)模板來創(chuàng)建候選補丁的搜索空間.ARJA-e 還使用了更細粒度的適應(yīng)度函數(shù)，可以充分利用測試套件中包含的語義信息，有望更好地指導(dǎo)整個搜索過程.除此之外，ARJA-e 還包含一個后期處理工具，可以用于過擬合檢測和補丁排序.在Defects4J[38]上的實驗研究表明，相比于GenProg，ARJA-e生成的正確補丁數(shù)量有了明顯的增加，實現(xiàn)了實質(zhì)性的性能提升.

在2019年，Hu等人[45]提出了一種全自動的程序修復(fù)方法用以根據(jù)正確的程序來修復(fù)學(xué)生提交的作業(yè)程序，并實現(xiàn)了修復(fù)工具Refactory.該方法首先通過將所有可能的正確程序根據(jù)給定的變換規(guī)則重構(gòu)為具有新控制流結(jié)構(gòu)且語義等價的程序，然后根據(jù)控制流結(jié)構(gòu)，將學(xué)生提交的不正確的程序與正確的重構(gòu)程序進行匹配，進而根據(jù)執(zhí)行這些正確程序基本塊(basic blocks)的運行結(jié)果來推斷出錯誤程序基本塊的輸入/輸出規(guī)范，最后根據(jù)這些規(guī)范產(chǎn)生修復(fù)代碼.同年，Ghanbari等人[46]提出了首個實用的字節(jié)碼級程序缺陷自動修復(fù)方法PraPR，并首次對基于字節(jié)碼突變的修復(fù)方法進行了實證研究.與源代碼級別的修復(fù)方法相比，由于字節(jié)碼具有結(jié)構(gòu)簡單且種類有限的特點，因此PraPR具有更高的修復(fù)效率.在Defects4J[38]上的實驗結(jié)果顯示，其修復(fù)效果顯著優(yōu)于當(dāng)時最先進的程序缺陷自動修復(fù)方法.

Villanueva等人[47]于2020年將新穎性搜索(Novelty Search，NS)算法應(yīng)用于GenProg[17-20]中，提出了程序缺陷自動修復(fù)方法NS-GenProg，這是NS在程序缺陷自動修復(fù)領(lǐng)域的首次應(yīng)用.NS-GenProg使用NS適應(yīng)度函數(shù)替代了GenProg中的適應(yīng)度函數(shù)，NS-GenProg解決了GenProg陷入局部最優(yōu)解的問題.經(jīng)實驗研究表明，NS-GenProg在修復(fù)了與GenProg相似數(shù)量缺陷的同時，還修復(fù)了GenProg無法修復(fù)的缺陷.

3.2 小 結(jié)

目前，基于搜索的程序缺陷自動修復(fù)方法還存在如下尚需解決的關(guān)鍵問題：

1)基于搜索的程序缺陷自動修復(fù)是一個在搜索空間內(nèi)尋找補丁并進行正確性驗證的過程.但是，若搜索空間設(shè)置得過大，會致使效率低下，且會產(chǎn)生大量疑似正確的補丁.若搜索空間設(shè)置得過小，可能會導(dǎo)致搜索空間中不存在正確的補丁.因此，如何設(shè)置合適的搜索空間是基于搜索的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

2)生成的補丁有可能能夠通過全部測試用例但是它違背了程序語義，如何剔除這類補丁是基于搜索的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

3)測試用例在缺陷定位和補丁評價階段都起到了關(guān)鍵的作用，測試用例的質(zhì)量決定了定位缺陷的準(zhǔn)確性以及驗證補丁的準(zhǔn)確性.因此，如何生成高質(zhì)量的測試用例也是基于搜索的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

4 基于語義的程序缺陷自動修復(fù)方法

基于語義的程序缺陷自動修復(fù)方法的正確性通常高于基于搜索的程序缺陷自動修復(fù)方法.該類方法首先定位到可疑的缺陷實體，并對可疑的缺陷實體進行排序；其次生成含有缺陷的實體的輸入以及輸出預(yù)期值；然后收集程序運行時的信息，提取補丁需要滿足的約束；最后將修復(fù)約束作為合成補丁的規(guī)約，并用約束求解器生成補丁[7].該類方法將測試用例作為輸入，且轉(zhuǎn)化為解輸出.與基于搜索的修復(fù)方法相比，其生成的補丁基本都能通過驗證.圖3展示了基于語義的程序缺陷自動修復(fù)方法的總體流程.

圖3 基于語義的程序缺陷自動修復(fù)方法流程Fig.3 Flow of semantic-based automatic program repair methods

4.1 基于語義的程序缺陷自動修復(fù)方法研究進展

Nguyen等人[48]于2013年提出了一種基于符號執(zhí)行、約束求解和程序綜合的缺陷自動修復(fù)方法SemFix.SemFix從測試用例中得出修復(fù)約束，并求解該修復(fù)約束以生成有效的補丁，其優(yōu)勢是可以在不存在修復(fù)材料的情況下合成修復(fù)程序，且在特定類型的缺陷修復(fù)上，SemFix相比于基于搜索的程序缺陷自動修復(fù)方法具有更高的修復(fù)效率與修復(fù)成功率.

Mechtaev等人[49]著眼于最大限度地保留缺陷程序的程序結(jié)構(gòu)，于2015年提出了DirectFix.DirectFix將故障定位和補丁生成融合到一個步驟中，利用部分Max SAT約束求解和基于組件的程序合成來實現(xiàn).相比于SemFix[48]，DirectFix實現(xiàn)缺陷修復(fù)的難度更低.由于DirectFix和SemFix都是測試驅(qū)動的修復(fù)工具，它們都會進行回歸測試，與SemFix相比，DirectFix引入的回歸錯誤要少得多.同在2015年，Marcote等人[50]針對無限循環(huán)的缺陷提出了一種自動修復(fù)方法Infinitel.該方法首先檢測到無限循環(huán)缺陷發(fā)生的位置，然后收集有關(guān)其預(yù)期行為的執(zhí)行信息，最后通過基于程序合成的方法生成新的循環(huán)條件.

基于語義的程序缺陷自動修復(fù)方法最大的挑戰(zhàn)在于如何提高方法的可伸縮性.為此，Mechtaev 等人[51]于2016年提出了Angelix，它可以擴展到與GenProg[17-20]等基于搜索的修復(fù)方法處理的大小相似的程序.Angelix比基于語義的其他修復(fù)方法如SemFix[48]和DirectFix[49]更具伸縮性，而且該方法可以修復(fù)相互依賴的多個位置的缺陷.在2018年，Mechtaev等人[52]在Angelix的基礎(chǔ)之上提出了修復(fù)工具SemGraft.針對由于Angelix依賴于測試用例作為補丁正確性標(biāo)準(zhǔn)而產(chǎn)生的過擬合問題，SemGraft將程序的規(guī)約作為補丁正確性判斷的輔助標(biāo)準(zhǔn)，在一定程度上緩解了過擬合問題，提升了生成的補丁質(zhì)量.

Xuan等人[42]于2017年提出了Nopol，其早期版本[53]于2014年提出，Nopol是一種自動修復(fù)條件語句缺陷(即錯誤的IF條件和缺失的前提條件)的方法.該方法利用天使修復(fù)定位(Angelic Fix Localization)來確定缺陷位置，然后利用基于組件的程序合成方法合成條件補丁.雖然該方法存在一定的局限性，但是由于該方法是針對有缺陷的條件語句設(shè)計的，所以具有成本低、空間小和可以應(yīng)用于大規(guī)模的程序修復(fù)等優(yōu)勢.

針對程序缺陷自動修復(fù)方法經(jīng)常產(chǎn)生低質(zhì)量補丁且引入新缺陷的問題，Afzal等人[54]于2019年提出了一種基于語義代碼搜索的程序缺陷自動修復(fù)方法SOSRepair.該方法用人工編寫的語義相似但不相同的代碼替換可疑位置的代碼.除此之外，該方法采用了一種新穎、高效、通用的機制，用于編碼程序修復(fù)的語義搜索查詢，這種編碼方式可以有效地將候選修復(fù)代碼映射到有缺陷的上下文中，顯著加快了代碼的搜索過程.

GAO等人[55]于2021年提出了一種基于約束驅(qū)動的程序缺陷自動修復(fù)方法并實現(xiàn)了修復(fù)工具ExtractFix.為應(yīng)對高質(zhì)量的測試用例并不總是存在的問題，ExtractFix使用了一種基于約束/依賴的定位技術(shù)而不是廣泛應(yīng)用的統(tǒng)計故障定位技術(shù).針對程序崩潰位置可能與修復(fù)位置不同的問題，ExtractFix可對提取的約束進行傳播和轉(zhuǎn)換，以指導(dǎo)在修復(fù)位置生成補丁.此外，ExtractFix還擴展了現(xiàn)有的二階程序合成方法以生成具有最小句法/語義變化的補丁.經(jīng)在MangBugs[23]等數(shù)據(jù)集上的實驗研究表明，ExtractFix產(chǎn)生的正確補丁數(shù)多于同時期較為先進的程序缺陷自動修復(fù)工具.

4.2 小 結(jié)

基于語義的程序缺陷自動修復(fù)方法目前還存在如下尚需解決的關(guān)鍵問題：

1)基于語義的程序缺陷自動修復(fù)方法通過約束生成補丁，生成正確補丁的概率往往更高.但是此類方法需要更多的程序信息，且面臨算法執(zhí)行時間較長、部署和實施困難的問題.

2)基于語義的程序缺陷自動修復(fù)方法建立在“若補丁通過全部的測試用例，則為正確補丁”的假設(shè)之上，因此不可避免地會產(chǎn)生過擬合問題.如何更好的緩解過擬合問題是基于語義的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

3)基于語義的程序缺陷自動修復(fù)方法在小規(guī)模的程序上展現(xiàn)出了良好的修復(fù)效果，然而由于此類方法大多使用了符號執(zhí)行以及約束求解等技術(shù)，使得其難以應(yīng)用在較為復(fù)雜的程序上.如何解決上述局限性是基于語義的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

5 基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法

目前，以GenProg[17-20]為代表的基于搜索的程序自動修復(fù)方法和以SemFix[48]為代表的基于語義的程序自動修復(fù)方法已展現(xiàn)出良好的修復(fù)效果.但是這些方法都有自身的局限性，將機器學(xué)習(xí)應(yīng)用于程序缺陷自動修復(fù)可以有效解決這些局限.基于機器學(xué)習(xí)的缺陷自動修復(fù)主要步驟為：首先，獲取數(shù)據(jù)集，進行數(shù)據(jù)預(yù)處理并將數(shù)據(jù)送與修復(fù)模型；其次，結(jié)合機器學(xué)習(xí)的技術(shù)對修復(fù)模型進行訓(xùn)練；然后，用訓(xùn)練好的模型為待修復(fù)程序生成候選補?。蛔詈?，對候選補丁進行排序和正確性驗證.圖4展示了基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法的總體流程.

5.1 基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法研究進展

最早在2009年，Jeffrey等人[56]提出了一種稱為BugFix的程序缺陷自動修復(fù)方法.BugFix會在程序語句中自動分析調(diào)試情況，并得出相關(guān)缺陷的修復(fù)程序排序列表以指導(dǎo)開發(fā)人員對該缺陷進行適當(dāng)?shù)男迯?fù).BugFix融合了機器學(xué)習(xí)的思想，可以不斷地自動學(xué)習(xí)新的調(diào)試情況和缺陷修復(fù).當(dāng)遇到新的缺陷時，可以有效的預(yù)測最準(zhǔn)確的缺陷修復(fù)程序.

圖4 基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法流程Fig.4 Flow of machine learning-based automatic program repair methods

對于執(zhí)行復(fù)雜操作的代碼，修復(fù)其中的錯誤仍然是昂貴且困難的.于是在2016年，Gopinath等人[57]提出了MLR用以修復(fù)復(fù)雜代碼中的錯誤，他們認為基于機器學(xué)習(xí)和系統(tǒng)路徑探索的集成方法可以提供有效的修復(fù).MLR首先挖掘執(zhí)行條件分支成功和執(zhí)行失敗的數(shù)據(jù)以生成程序頻譜，然后生成補丁搜索空間，最后生成在現(xiàn)有測試套件之下的補丁.Gopinath等人[57]將MLR應(yīng)用于修復(fù)小型但數(shù)據(jù)結(jié)構(gòu)復(fù)雜的程序中的缺陷以證明其修復(fù)效果.實驗結(jié)果表明，與2016年同時期的其它修復(fù)工具相比，MLR能更有效地修復(fù)此類缺陷.

由于一些程序員缺乏編程的經(jīng)驗以及對細節(jié)的關(guān)注，會產(chǎn)生許多錯誤，通常稱這些錯誤為編程錯誤.編譯器會檢測到此類錯誤，但編譯器提供的錯誤報告通常不準(zhǔn)確.針對此類錯誤，在2017年，Gupta等人[58]提出了一種稱為DeepFix的程序缺陷自動修復(fù)方法，其核心是一個序列到序列神經(jīng)網(wǎng)絡(luò)，該神經(jīng)網(wǎng)絡(luò)具有多層次的結(jié)構(gòu).在訓(xùn)練后DeepFix可以預(yù)測缺陷位置以及正確的修復(fù)語句.在一組由學(xué)生編寫的6971個含有錯誤的C程序集合中，DeepFix完整修復(fù)的程序數(shù)量達到了1881(27%)個，部分修復(fù)的程序數(shù)量達到了1338(19%)個.

在2019年，Vasic等人[59]提出了一種聯(lián)合學(xué)習(xí)定位和修復(fù)的方法，該方法主要針對變量濫用而引起的程序缺陷.方法中設(shè)計了一個基于程序標(biāo)記序列順序編碼的多頭指針網(wǎng)絡(luò)模型，每個頭指針網(wǎng)絡(luò)模型用于定位和修復(fù)一個錯誤，該模型的性能明顯優(yōu)于使用枚舉方法的模型.在將來，他們還將探索使用其他模型(如圖模型、指針和圖模型的組合)的聯(lián)合定位和修復(fù)，并將考慮使用更多的程序語義信息.White等人[60]于2019年提出了一種通過深度學(xué)習(xí)來推理代碼相似性的程序缺陷自動修復(fù)方法DeepRepair.該方法可以根據(jù)與可疑元素(即包含可疑語句的代碼元素)的相似性來對代碼片段進行排序，并且可以通過將范圍外的標(biāo)識符映射到范圍內(nèi)的相似標(biāo)識符來轉(zhuǎn)換語句.該方法的特點是找到了當(dāng)時基于冗余的修復(fù)方法無法找到的補丁.Tufano等人[61]于2019年對使用神經(jīng)機器翻譯(NMT)技術(shù)進行程序修復(fù)的可行性進行了廣泛的實證研究，其設(shè)計并詳細闡述了挖掘、提取以及抽象缺陷程序和修復(fù)程序的過程.在此基礎(chǔ)之上建立了基于循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)的NMT模型用于將缺陷程序轉(zhuǎn)換為修復(fù)程序.Tufano等人[61]提出的NMT模型作為較為先進的修復(fù)工具，其能修復(fù)多種類型的缺陷，且能在9%-50%的情況下預(yù)測補丁程序.該NMT模型中解碼器輸出的是方法級別的補丁程序，但由于NMT模型難以處理過長的方法序列，使得其修復(fù)范圍僅限于中小型方法中.Chen[62]等人于2019年提出了一種使用序列到序列模型進行端到端程序修復(fù)的方法SEQUENCER.該方法通過構(gòu)建抽象的上下文來模擬開發(fā)人員分析和推理bug的過程，通過復(fù)制機制克服大代碼中出現(xiàn)的詞匯量巨大的問題.相比于Tufano等人[61]提出的方法，SEQUENCER沒有修復(fù)方法大小的限制，且其考慮的上下文范圍由方法擴展到了類，使模型在修復(fù)缺陷時可以訪問更多的程序信息.

“生成—驗證(G&V)”的程序缺陷自動修復(fù)方法常依賴于硬編碼規(guī)則，發(fā)現(xiàn)這些規(guī)則需要大量的人工努力，而且難以使這些規(guī)則適應(yīng)于不同的程序語言，因此只能按照特定的修復(fù)模式修復(fù)缺陷.為了解決這些問題，在2020年，Lutellier等人[63]提出了一種G&V方法CoCoNuT.CoCoNuT利用卷積神經(jīng)網(wǎng)絡(luò)(CNN)和神經(jīng)機器翻譯技術(shù)來自動修復(fù)多種程序語言的缺陷.Lutellier等人[63]在4種編程語言(Java，C，Python，JavaScript)的6個缺陷庫上測試了CoCoNuT的修復(fù)效果.實驗結(jié)果表明，在其中的4個缺陷庫上，CoCoNuT修復(fù)了數(shù)量最多的缺陷，也是唯一一個修復(fù)Python和JavaScript缺陷的方法.Li等人[64]于2020年提出了一個兩層的深度學(xué)習(xí)模型DLFix用于自動修復(fù)程序缺陷.DLFix的第1層是基于樹的RNN模型，用于學(xué)習(xí)缺陷修復(fù)的上下文，第2層用于學(xué)習(xí)缺陷程序到修復(fù)程序的轉(zhuǎn)換.

近些年，神經(jīng)機器翻譯技術(shù)(NMT)被廣泛用于自動修復(fù)程序缺陷.該類方法展現(xiàn)出了良好的發(fā)展前景，但是目前存在著兩個主要的局限性：該類方法的搜索空間中包含的正確補丁較少；其搜索策略忽略了如代碼語法等軟件知識.針對上述局限性，Jiang等人[65]于2021年提出了一種新的基于NMT的程序缺陷自動修復(fù)方法CURE.CURE 在大型軟件代碼庫上預(yù)訓(xùn)練編程語言(PL)模型，以在自動修復(fù)程序之前預(yù)先對源代碼進行學(xué)習(xí).CURE 還設(shè)計了一種新的代碼感知搜索策略，該策略側(cè)重于關(guān)注可編譯的補丁和與錯誤代碼長度相近的補丁以找到更多正確的修復(fù).此外，CURE 使用了子詞標(biāo)記化技術(shù)來生成包含更多正確修復(fù)的較小搜索空間.PL模型、代碼感知搜索策略和子詞標(biāo)記化技術(shù)的使用使得CURE的修復(fù)效率及效果優(yōu)于同時期的程序缺陷自動修復(fù)方法.

5.2 小 結(jié)

目前，基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法還存在如下尚需解決的關(guān)鍵問題：

1)源代碼不同于自然語言，其原始數(shù)據(jù)相當(dāng)嘈雜，會對訓(xùn)練產(chǎn)生極大程度的噪音.因此，如何過濾原始數(shù)據(jù)是基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

2)在自然語言中，類似于標(biāo)點符號的錯誤是可以接受的，且依賴關(guān)系通常在同一個句子中或者幾個句子中.但在編程語言中，標(biāo)識符、數(shù)字等的誤用會導(dǎo)致編譯器產(chǎn)生錯誤的結(jié)果，依賴關(guān)系的范圍也更長(可以使用一個在幾十行前已經(jīng)聲明的變量).因此，如何使通過機器學(xué)習(xí)產(chǎn)生的修復(fù)程序的精度達到標(biāo)識符、數(shù)字級別和處理好長依賴關(guān)系是基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法面臨的關(guān)鍵問題.

3)使用機器學(xué)習(xí)自動修復(fù)程序缺陷時，需要處理的詞匯數(shù)量巨大，這是由于變量、常量等定義的任意性，且字母的大小寫在編程語言中代表著不同的含義.因此，如何減小需要處理的詞匯數(shù)量是基于機器學(xué)習(xí)的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

6 基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法

目前程序缺陷自動修復(fù)主要集中在基于測試集的修復(fù)方法，其中錯誤定位和補丁生成由明確定義的測試套件驅(qū)動.但是在大多數(shù)實際情況中，有關(guān)測試用例的通用假設(shè)并不存在，即許多的錯誤并不能通過測試套件挖掘到.基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法可以應(yīng)對上述問題，因為錯誤報告中含有豐富的關(guān)于程序執(zhí)行以及用戶反饋的錯誤信息.

6.1 基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法研究進展

2011年，Jin等人[66]提出了AFIX，該方法用于自動修復(fù)單變量原子性違背的并發(fā)錯誤.其使用現(xiàn)有的錯誤檢驗工具得到錯誤報告，通過靜態(tài)分析和靜態(tài)代碼轉(zhuǎn)換來自動設(shè)計和生成程序補丁.它還利用交叉測試技術(shù)來引導(dǎo)其修復(fù)過程.此外，AFIX進一步結(jié)合了運行時動態(tài)代碼監(jiān)測，以幫助開發(fā)人員驗證和評估它生成的每個補丁.

2013年，Liu等人[67]提出了一種基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法R2Fix，該方法可以通過無格式要求的錯誤報告生成補丁.收到錯誤報告后，R2Fix會先分析該錯誤報告，然后確定錯誤類型，最后生成候選補丁來修復(fù)該錯誤.具體的，R2Fix包含3個步驟：1)錯誤分類器(簡稱為分類器)分類，分類器對錯誤報告進行分析和歸類，并且僅保留歸類為目標(biāo)錯誤類型的錯誤報告(候選錯誤報告)用于接下來的兩個步驟;2)模式參數(shù)提取器(簡稱模式提取器)從源代碼和候選錯誤報告中提取緩沖區(qū)長度、指針名稱等模式參數(shù);3)補丁生成器(或簡稱生成器)使用目標(biāo)錯誤類型的修復(fù)模式、模式參數(shù)以及源代碼存儲庫來自動生成補丁.研究人員在3個大型的項目(即Linux內(nèi)核，Mozilla和Apache)上評估了R2Fix對3類重要錯誤(緩沖區(qū)溢出，空指針錯誤和內(nèi)存泄漏)的修復(fù)效果.實驗結(jié)果表明，R2Fix可以生成60個正確補丁，其中5個是針對尚未被開發(fā)人員修復(fù)的錯誤的新補丁，且5個中的4個補丁被開發(fā)人員認可接受.R2Fix生成的60個正確的補丁程序可以節(jié)省68天的錯誤診斷和補丁程序生成時間.

在2019年，Koyuncu等人[68]提出了一種基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法iFixR，這是一種程序自動修復(fù)的管道變體，適用于測試用例不可用的情況.該方法的修復(fù)流程為：將錯誤報告和錯誤程序送到基于IR的定位器，定位器會定位到可疑代碼的位置；篩選出合適的修復(fù)模式，由修復(fù)模式生成補?。煌ㄟ^回歸測試進行補丁驗證.在重組的Defects4J上的實驗結(jié)果表明，iFixR可以針對各種錯誤報告生成更合理的補丁，且其修復(fù)性能與Defects4J上絕大多數(shù)基于測試集的程序缺陷自動修復(fù)方法不相上下.

6.2 小 結(jié)

在修復(fù)實際項目中的錯誤時，測試用例的假設(shè)通常是無法成立的.相比于基于測試集的程序缺陷自動修復(fù)方法，基于錯誤報告驅(qū)動的修復(fù)方法最大的優(yōu)勢是不需要對測試用例進行任何的假設(shè)，這也在一定程度上增加了此類方法的實際可用性.目前，基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法還存在如下尚需解決的關(guān)鍵問題：

1)基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法修復(fù)錯誤的第一階段是對錯誤報告進行解析、篩選和分類，然而錯誤報告的數(shù)量通常較多，需要耗費大量的資源.因此，設(shè)計更加合理高效的解析、篩選和分類算法是基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

2)為了從錯誤報告中自動生成補丁，需要從錯誤報告中提取關(guān)于錯誤的詳細信息，然而現(xiàn)有的許多錯誤報告提取技術(shù)只能從錯誤報告中獲取到簡單的錯誤描述.因此，如何改進現(xiàn)有的技術(shù)以獲取全面的錯誤描述進而得到錯誤產(chǎn)生的根本原因是基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.

7 缺陷庫

程序缺陷自動修復(fù)方法及工具修復(fù)效果的檢驗離不開高質(zhì)量的缺陷庫.高質(zhì)量的缺陷庫需要具有完備的測試集，且要求缺陷的來源必須是真實的項目.本節(jié)總結(jié)了目前程序缺陷自動修復(fù)領(lǐng)域常用的C/C++、Java和多種語言的缺陷庫，特別梳理了缺陷庫的適用場景以及對程序缺陷自動修復(fù)工作的貢獻.表1給出了每個缺陷庫對應(yīng)的編程語言、缺陷總數(shù)、參考文獻、缺陷來源、適用場景和下載地址.

表1 程序缺陷自動修復(fù)評測缺陷庫Table 1 Defect libraries for automatic program repair evaluation

7.1 C/C++缺陷庫

Le Goues等人[23]于2015年提出了兩個缺陷庫ManyBugs和IntroClass.ManyBugs由9個大型開源項目的185個缺陷組成，共含有代碼590萬行和測試用例1萬多個.IntroClass由本科生編寫的程序中的共998個缺陷組成.ManyBugs和IntroClass包含黑盒測試和白盒測試，黑盒測試由人工方式依據(jù)等價類劃分執(zhí)行，白盒測試實現(xiàn)測試預(yù)言的分支覆蓋.Tan等人[69]于2017年提出了缺陷庫Codeflaws，Codeflaws缺陷庫來自于Codeforces在線數(shù)據(jù)庫中的7436個程序.它是3902個缺陷的集合，共有39種缺陷類別.Codeflaws用于研究不同修復(fù)工具可修復(fù)的缺陷類別.B?hme等人[70]基于CoREBench(CoREBench是4個開源項目(coreutils，findutils，grep和make)中70個實際回歸錯誤的集合)于2017年發(fā)布了DBGBENCH論文，提出了DBGBENCH缺陷庫.

7.2 Java缺陷庫

Just等人[38]于2014年提出了Defects4J，這是一個可擴展的缺陷庫，提供了真實項目中的缺陷.Defects4J的初始版本包含5個真實的開源項目中的357個程序缺陷，每個缺陷都附帶一個全面的測試套件.Defects4J是可擴展的，將Defects4J配置好之后，可以輕松地將新的缺陷添加到缺陷庫中.Defects4J具有一個框架，該框架提供了高級界面，可訪問錯誤程序和修復(fù)程序以及相應(yīng)的測試套件.Saha等人[71]于2018年提出了Bugs.jar，這是一個大規(guī)模的缺陷庫，用于研究Java語言的程序缺陷自動修復(fù)方法.Bugs.jar由1，158個錯誤和補丁組成，這些錯誤和補丁來自8個大型流行的開源Java項目.Bugs.jar比Defects4J[38]大一個數(shù)量級.Madeiral等人[72]于2019年提出了缺陷庫Bears，Bears是用于程序缺陷自動修復(fù)研究的可擴展Java缺陷庫.Madeiral等人[72]提供了Bears的1.0版本，Bears1.0版本中包含從72個項目中收集的251個可復(fù)制的缺陷.

7.3 多種語言的缺陷庫

Lin等人[73]于2017年提出了QuixBugs缺陷庫.QuixBugs中的40個Python缺陷程序來自于Quixey公司測試題目，這些程序均由人工轉(zhuǎn)換為Java程序，每個程序都包含一個單行缺陷，以及通過和失敗測試用例.Quixbugs旨在用于檢驗修復(fù)方法跨語言的修復(fù)性能.Tomassi等人[74]于2019年提出了BugSwarm.BugSwarm是同類中最大的缺陷庫，其有成千上萬個可復(fù)制的錯誤程序及相應(yīng)的修復(fù)程序?qū)?，具有很強的可擴展性.目前，BugSwarm已經(jīng)收集了3，091個Java和Python的錯誤程序及相應(yīng)的修復(fù)程序?qū)?

7.4 缺陷庫對程序缺陷自動修復(fù)工作的貢獻

程序缺陷自動修復(fù)工作與缺陷庫密不可分，本小節(jié)將系統(tǒng)地分析和總結(jié)缺陷庫對于程序缺陷自動修復(fù)工作的主要貢獻.

1)程序缺陷自動修復(fù)方法能夠降低維護軟件可靠性和保證軟件質(zhì)量所需的成本.為了使程序缺陷自動修復(fù)方法走向?qū)嶋H運用，需要建立高質(zhì)量的缺陷庫以對其修復(fù)能力進行測試評估.高質(zhì)量的缺陷庫需要具有一定的規(guī)模、復(fù)雜度和多樣性，除此之外還要求缺陷來自于真實項目.近些年，不斷有高質(zhì)量的缺陷庫被設(shè)計與運用，如用于評估C/C++程序缺陷自動修復(fù)方法的ManyBugs[23]、IntroClass[23]和DBGBENCH[70]等，用于評估Java程序缺陷自動修復(fù)方法的Defects4J[38]、Bugs.jar[71]和Bears[72]等，這些缺陷庫為推進程序缺陷自動修復(fù)方法的工業(yè)應(yīng)用作出了重要貢獻.

2)通常情況下，一種程序缺陷自動修復(fù)方法可以修復(fù)多種類型的缺陷.但在修復(fù)某種特定類型的缺陷時，為取得良好的修復(fù)效果，需針對性地選擇修復(fù)性能最佳的方法.為此，近些年來研究者們設(shè)計和建立了如Codeflaws[69]等缺陷庫，這類缺陷庫為研究不同的程序缺陷自動修復(fù)方法對某種特定類型缺陷的修復(fù)效果作出了較為重要的貢獻.

3)近年來，程序缺陷自動修復(fù)領(lǐng)域涌現(xiàn)出了許多研究成果.雖然以前的工作只關(guān)注某一種語言的缺陷修復(fù)，但是由于最近語言轉(zhuǎn)換工作的不斷進展，當(dāng)下在該領(lǐng)域也提出了許多可以修復(fù)多種語言缺陷的程序自動修復(fù)方法.為了對這類方法進行實證研究，一些多語言并行的缺陷庫被設(shè)計和建立，如Lin等人[73]建立的QuixBugs和Tomassi等人[74]建立的BugSwarm等，這些缺陷庫為評估程序自動修復(fù)方法跨語言修復(fù)缺陷的能力作出了重要貢獻.

8 總結(jié)與展望

隨著軟件規(guī)模和復(fù)雜度的提高，程序缺陷自動修復(fù)近幾年來獲得了持續(xù)且廣泛的關(guān)注.雖然程序缺陷自動修復(fù)研究時間較短，但取得了大量的研究成果.尤其在國內(nèi)，隨著研究的深入，產(chǎn)生了許多具有影響力的貢獻.本文根據(jù)補丁生成方式的不同，將程序缺陷自動修復(fù)方法劃分為4類，分別為基于搜索的、基于語義的、基于機器學(xué)習(xí)的和基于錯誤報告驅(qū)動的程序缺陷自動修復(fù)方法，并對每類方法進行了詳細闡述.其次，總結(jié)了檢驗程序缺陷自動修復(fù)方法及工具修復(fù)效果所用到的缺陷庫，特別梳理了缺陷庫的適用場景以及對程序缺陷自動修復(fù)工作的貢獻.

雖然目前程序缺陷自動修復(fù)領(lǐng)域開發(fā)出了數(shù)以百計的自動修復(fù)工具，且在由開源項目組成的真實缺陷庫上展現(xiàn)出了一定的修復(fù)效果，但程序缺陷自動修復(fù)研究成功應(yīng)用于工業(yè)軟件的案例少之又少.目前成功應(yīng)用的案例是Facebook[75]，兩個程序缺陷自動修復(fù)工具SapFix[76]和Getafix[77]被集成到他們的開發(fā)工作流中，其修復(fù)了超過40%～50%的與空值相關(guān)的缺陷和警告.如ELIXIR[35]、Nopol[42]和Astor[78]等常用的程序缺陷自動修復(fù)工具的工業(yè)應(yīng)用并未取得顯著的效果.Noda[75]等人將較為先進的程序缺陷自動修復(fù)工具ELIXIR[35]應(yīng)用于大型工業(yè)軟件中，在20個真實的單語句缺陷的修復(fù)中，僅取得了10%的成功率.Naitou等人[79]對Nopol[42]和Astor[78]進行了工業(yè)應(yīng)用的研究，在9個待修復(fù)的缺陷中，它們僅正確修復(fù)了其中的一個.鑒于此，我們分析總結(jié)了該領(lǐng)域面臨的關(guān)鍵問題及未來研究的方向：

1)許多程序缺陷自動修復(fù)工具在如 Defects4J[38]等缺陷庫上展現(xiàn)出了良好的修復(fù)效果，然而在工業(yè)軟件上的實際性能卻相當(dāng)?shù)?，這表明修復(fù)工具過度擬合缺陷庫，這是程序缺陷自動修復(fù)應(yīng)用于工業(yè)界尚需解決的一個關(guān)鍵問題.

2)許多程序缺陷自動修復(fù)方法都是建立在缺陷只存在于單條語句之上的，修復(fù)的缺陷類型較為簡單.然而在現(xiàn)實中，程序中的缺陷很可能在多條語句之上.因此，如何修復(fù)存在于多條語句之上的缺陷是程序自動修復(fù)方法面臨的一個關(guān)鍵問題.

3)缺陷定位方法發(fā)展相對較早，且取得了較多的研究成果.但是，很多缺陷定位方法是用來輔助開發(fā)人員進行人工的缺陷修復(fù)的，其精度往往達不到程序缺陷自動修復(fù)的要求.因此，開發(fā)精度更高的缺陷定位方法是一個值得深入研究的方向.

4)基于生成-驗證的程序缺陷自動修復(fù)方法在缺陷定位和補丁評估階段需要消耗相當(dāng)長一段時間來多次運行測試用例.企業(yè)級應(yīng)用程序的測試時間往往更長，如果執(zhí)行整個測試用例，則很容易超過時間預(yù)算，這是由于企業(yè)級應(yīng)用程序經(jīng)常需要與數(shù)據(jù)庫等外部環(huán)境進行交互，訪問數(shù)據(jù)庫等外部環(huán)境的時間開銷十分沉重，過長的時間開銷阻礙了程序缺陷自動修復(fù)方法的工業(yè)應(yīng)用.因此，如何選擇檢測能力較強的測試用例子集并確定其執(zhí)行順序以減少時間開銷是一個值得進一步研究的問題.

5)在實際應(yīng)用中，通過程序自動修復(fù)方法產(chǎn)生的補丁不僅需要能夠修復(fù)缺陷，還要具有安全性、清晰的結(jié)構(gòu)和較高的效率等特性，但是這些特性通常難以通過測試套件評估.因此，如何產(chǎn)生和篩選出正確且具有安全性、清晰的結(jié)構(gòu)和較高效率的補丁是程序缺陷自動修復(fù)方法面臨的一個關(guān)鍵問題.