李 斌,賀也平,3,馬恒太

1(中國科學(xué)院大學(xué),北京 100049)

2(基礎(chǔ)軟件國家工程研究中心(中國科學(xué)院 軟件研究所),北京 100190)

3(計算機科學(xué)國家重點實驗室(中國科學(xué)院 軟件研究所),北京 100190)

由于現(xiàn)代程序規(guī)模和復(fù)雜度(scale and complexity)的上升,程序錯誤(program error)不可避免地存在且數(shù)量逐年上升.傳統(tǒng)維護(hù)面臨成本和維護(hù)能力不足、不可控條件下無法維護(hù)等諸多問題,這使得程序錯誤修復(fù)這一問題上升到新的高度,程序自動修復(fù)技術(shù)(automatic program repair)應(yīng)運而生并成為研究熱點.

(1)傳統(tǒng)維護(hù)面臨成本和維護(hù)能力不足問題

統(tǒng)計表明,軟件維護(hù)占用了軟件開發(fā)成本的 50%～75%[1],其中,成本消耗最大的就是程序錯誤定位和修復(fù).2006年,Mozilla公司的維護(hù)人員發(fā)現(xiàn):每天有大約300個軟件錯誤發(fā)生,其規(guī)模遠(yuǎn)遠(yuǎn)大于Mozilla公司的處理能力[2].現(xiàn)在軟件發(fā)布越來越快,軟件維護(hù)周期越來越短.面對越來越多的軟件錯誤,許多公司開始尋求外部開發(fā)者的幫助,甚至通過懸賞的方式尋求緩解日益增長的軟件錯誤問題.例如,著名IT公司Mozilla[3]、谷歌[4]為較高安全等級的軟件錯誤修復(fù)設(shè)立了專門的獎勵基金,微軟也建立了賞金計劃[5].

(2)不可控條件下無法維護(hù)問題

由于軟件邏輯設(shè)計復(fù)雜性和運行環(huán)境的限制,當(dāng)軟件發(fā)生錯誤時,維護(hù)人員可能無法遠(yuǎn)程修復(fù)該類錯誤.在航天領(lǐng)域中應(yīng)用的軟件系統(tǒng),當(dāng)衛(wèi)星、航天飛船等空間飛行器與地面的通信聯(lián)絡(luò)中斷時存在不可控的情況.例如,2005年,NASA發(fā)射的“深度撞擊”號探測器由于重置探測器計算機遇到一個軟件通訊的小故障,使得該探測器處于失控狀態(tài).地面控制人員無法發(fā)送指令修復(fù)程序錯誤,最終,美國航天局宣布探測器電池耗盡已經(jīng)死亡[6].

程序自動修復(fù)是一個飛速發(fā)展的研究領(lǐng)域,為了方便研究人員進(jìn)入該領(lǐng)域并充分了解研究現(xiàn)狀,國內(nèi)外學(xué)者已形成多篇研究綜述.其中,在 2016年,已有國內(nèi)學(xué)者玄躋峰等人對程序自動修復(fù)方法及實證研究基礎(chǔ)進(jìn)行了總結(jié)[7],但是該綜述文章將研究對象限制在基于測試集的程序自動修復(fù)方法范疇,僅僅分析和梳理了2015年8月之前基于測試集的程序自動修復(fù)方法和修復(fù)的實證基礎(chǔ)研究進(jìn)展.2017年,國內(nèi)學(xué)者王贊等人[8]在綜述性文獻(xiàn)[7]的基礎(chǔ)上進(jìn)一步對修復(fù)方法進(jìn)行分類總結(jié),新增的 38篇研究文獻(xiàn)主要集中在 2016年底之前的研究成果.該綜述梳理了缺陷定位、補丁生成和補丁評價這 3個階段的程序自動修復(fù)研究成果,同時總結(jié)了該領(lǐng)域已有的benchmark缺陷庫、修復(fù)工具和活躍的研究團(tuán)隊.國外學(xué)者Claire等人[9]早在2013年就發(fā)表了回顧型論文(review),主要分析了該團(tuán)隊的核心研究工作GenProg方法的創(chuàng)新和不足,以及當(dāng)時程序自動修復(fù)研究領(lǐng)域面臨的挑戰(zhàn).2018年,國外學(xué)者M(jìn)artin等人[10]主要對2016年底之前(除了1篇AAAI 2017對編譯錯誤進(jìn)行修復(fù)的研究文獻(xiàn))程序自動修復(fù)和程序動態(tài)容錯兩個領(lǐng)域的研究成果進(jìn)行梳理和總結(jié),將研究對象上升到軟件自動修復(fù)(automatic software repair)的范疇.

與該領(lǐng)域國內(nèi)[7,8]、國外[9,10]已有的研究綜述相比,我們的工作有如下不同.

首先,我們從一個新的角度對程序自動修復(fù)技術(shù)領(lǐng)域進(jìn)行了分析,以問題為導(dǎo)向,分析技術(shù)邏輯關(guān)系更加自然.現(xiàn)有的綜述更傾向于對已有的程序自動修復(fù)技術(shù)在方法層面進(jìn)行梳理和分類總結(jié),闡述的是具體方法和具體問題以及相互的異同.比如,玄躋峰等人[7]將基于測試集的程序自動修復(fù)方法劃分為基于搜索、基于代碼窮舉和基于約束求解這3個方面進(jìn)行闡述,王贊等人[8]將補丁生成階段劃分為基于搜索、基于語義和其他這3類對應(yīng)方法進(jìn)行闡述.以上綜述有利于理清具體問題的差異和每種技術(shù)體系下各類方法的發(fā)展趨勢,但不利于對程序自動修復(fù)領(lǐng)域各類具體問題之間的聯(lián)系和技術(shù)體系中邏輯關(guān)系的理解.例如,基于搜索和基于語義的修復(fù)方法其實面向的是同一類不完全規(guī)約的修復(fù)問題,即具有共同的潛在假設(shè),認(rèn)為補丁通過全部測試用例則是正確的[11].我們的工作嘗試抽象出該領(lǐng)域面對的幾類問題和不同的前提假設(shè),然后以抽象問題作為脈絡(luò),分析各類技術(shù)體系和典型的方法.

其次,在上述綜述之后,又有一些新的典型問題和方法出現(xiàn),我們增加了新的有代表性的工作.例如,Le等人[11]發(fā)現(xiàn),基于語義的修復(fù)方法也同樣存在過擬合問題,但某些情況下,過擬合現(xiàn)象和基于搜索的方法所表現(xiàn)的形式不同,這是對不完全規(guī)約修復(fù)問題中過擬合問題的重要說明.例如,Mechtaev等人[12]引入了參考程序的思想緩解過擬合問題.該方法完全不依賴測試集,從而區(qū)別開了已有基于測試集的修復(fù)方法和補丁擇優(yōu)的方法,為不完全規(guī)約修復(fù)問題中緩解過擬合這一關(guān)鍵問題提供了新的思路.我們的梳理工作也吸收了上述典型問題及其代表性研究成果,總體上新增前文綜述未覆蓋的研究文獻(xiàn)22篇.

我們將視角擴(kuò)展到整個程序自動修復(fù)的范疇,為了方便分析和說明規(guī)約刻畫對程序自動修復(fù)的重要性,提出了一種基于規(guī)約的程序自動修復(fù)描述.基于該描述所面對的不同修復(fù)問題,將現(xiàn)有修復(fù)技術(shù)所面向的修復(fù)對象抽象為完全規(guī)約、不完全規(guī)約和半完全規(guī)約這 3大類問題.以上述問題分類為線索,并結(jié)合基于規(guī)約的程序自動修復(fù)描述,梳理了各類技術(shù)體系的發(fā)展現(xiàn)狀和需要研究的核心問題.本文的主要工作內(nèi)容如下.

(1)提出了一種基于規(guī)約的程序自動修復(fù)描述,說明了程序規(guī)約的刻畫在修復(fù)過程中的重要性.從一個新的角度對程序自動修復(fù)技術(shù)領(lǐng)域進(jìn)行分析,根據(jù)描述中對待修復(fù)程序刻畫的程序規(guī)約S(specification)是否完整,將現(xiàn)有修復(fù)技術(shù)面向的問題抽象為完全規(guī)約、不完全規(guī)約和半完全規(guī)約這 3大類.由于能否完整地描述和刻畫待修復(fù)對象的程序規(guī)約的不同,各類程序自動修復(fù)技術(shù)的應(yīng)用場景、方法關(guān)注點和困難點存在很大區(qū)別.

(2)在梳理了不完全規(guī)約修復(fù)問題和方法,即基于測試集的程序自動修復(fù)方法最新進(jìn)展的基礎(chǔ)上,重點分析了該類方法面臨的高精度補丁生成、補丁判定中的規(guī)約補全和補丁擇優(yōu)等核心問題和已有的解決方案.

(3)梳理了完全規(guī)約和半完全規(guī)約的修復(fù)問題和方法,對其中完全規(guī)約的程序自動修復(fù)熱點問題(內(nèi)存泄漏、并發(fā)錯誤中的數(shù)據(jù)競爭、原子性違背、順序違背和死鎖、資源泄露、配置錯誤)以及特定性能錯誤等具體問題類型和研究進(jìn)展進(jìn)行了梳理.

本文第 1節(jié)給出一種基于規(guī)約的程序自動修復(fù)描述,并基于描述給出問題分類.第 2節(jié)介紹不完全規(guī)約的程序自動修復(fù)問題及方法.第 3節(jié)介紹完全規(guī)約的程序自動修復(fù)問題及方法.第 4節(jié)介紹半完全規(guī)約的程序自動修復(fù)問題及方法.最后在第5節(jié)進(jìn)行總結(jié)和展望.

1 程序自動修復(fù)描述

1.1 相關(guān)概念

程序自動修復(fù)技術(shù)針對各類不同的錯誤(error)修復(fù)場景,將整個修復(fù)過程自動化.一個程序錯誤(program error)是指程序的預(yù)期行為和實際執(zhí)行時所發(fā)生情況之間存在的一種偏差(deviation)[13].該定義引入了一個概念:預(yù)期行為,其實,一系列預(yù)期行為的集合就是程序規(guī)約(program specification),程序規(guī)約可以是自然語言書寫的文本、形式化的邏輯公式,或者測試集(test suite)等.有些文獻(xiàn)中提到一個和程序規(guī)約非常相近的概念:測試預(yù)言(test oracle),測試預(yù)言可以確定一個程序執(zhí)行結(jié)果是否正確,通過測試用例的預(yù)期結(jié)果與實際執(zhí)行結(jié)果的對比機制來判斷測試用例的結(jié)果是否通過[14].但測試預(yù)言和程序規(guī)約之間存在一定的區(qū)別:測試預(yù)言只與程序的輸出相關(guān),而程序規(guī)約還包括程序的輸入?yún)^(qū)間、程序的內(nèi)部邏輯要求和非功能屬性等規(guī)范.因此,測試預(yù)言是程序規(guī)約的一個子集.例如,一個程序規(guī)約要求遍歷一個輸入的字符串中是否包含字符A.若該程序的某個程序變體(program variant)不是遍歷輸入的字符串,而是直接判斷該字符串的某一位(例如第1位)是否為A.如果給定的輸入集字符串恰好都是以A開頭,則該程序變體和原程序在給定的輸入集對應(yīng)的測試預(yù)言相同,實則兩者邏輯語義截然不同.

1.2 程序規(guī)約與程序自動修復(fù)

程序自動修復(fù)是一種將不符合程序規(guī)約的錯誤語義自動轉(zhuǎn)換為符合程序規(guī)約的技術(shù).一般的程序自動修復(fù)方法包括錯誤定位、補丁生成和補丁判定等步驟.例如,輸入一個帶有bug的程序(buggy program)和測試用例集(至少1個測試用例執(zhí)行不通過,執(zhí)行未通過的用例檢測出了待修復(fù)的bug,這里將測試集作為程序規(guī)約),程序自動修復(fù)工具通過錯誤定位技術(shù)確定可能的出錯位置,然后利用補丁生成技術(shù)產(chǎn)生一系列候選補丁,最后利用程序規(guī)約構(gòu)造判定條件輸出0個、1個或多個正確補丁,最終輸出的補丁使得整個修復(fù)后的程序執(zhí)行行為符合規(guī)約.

根據(jù)我們的了解,目前的相關(guān)研究文獻(xiàn)針對程序自動修復(fù)大多是具體問題的步驟描述和示例說明,并沒有給出統(tǒng)一的描述和刻畫.為了說明程序規(guī)約的刻畫在自動修復(fù)過程中的重要性,以及更加方便地說明程序自動修復(fù)中出現(xiàn)的各類問題及方法特點,下面我們給出一種基于規(guī)約的程序自動修復(fù)描述.假設(shè)最簡單的一種情況,待修復(fù)的程序BP(buggy program)只包含1個錯誤,且修復(fù)該錯誤所需的補丁只有1條語句.修復(fù)之前程序BP不滿足程序規(guī)約S,修復(fù)過程中產(chǎn)生的補丁語句集合表示為P=patch(L,OP,C),其中L(location)表示bug程序BP的出錯位置,也是修復(fù)時打補丁的位置;OP(operater)表示補丁生成的操作符,包括增加、刪除和修改某條語句等變換的操作,也可以理解為修復(fù)模板;C(content)表示補丁語句所包含的內(nèi)容,是操作符OP的操作對象,也可以理解為修復(fù)模板的參數(shù).則程序自動修復(fù)可描述為:

1)假設(shè)給定程序BP和對應(yīng)的程序規(guī)約S,且BP不滿足S(即已經(jīng)發(fā)現(xiàn)程序BP包含一個錯誤).

2)修復(fù)過程是求解函數(shù)P=patch(L,OP,C),即通過錯誤自動定位、程序分析等技術(shù)計算出錯位置L,利用程序規(guī)約S或歸納方法總結(jié)適合的修復(fù)操作或修復(fù)模板OP,基于規(guī)約S指導(dǎo)的程序分析技術(shù)或其他方法獲取修復(fù)模板的參數(shù)或者補丁內(nèi)容C,然后求解補丁生成函數(shù)產(chǎn)生候選補丁集合P.

3)使得程序BP應(yīng)用上述補丁集合P中的特定補丁后滿足程序規(guī)約S,即判定打補丁后的程序語義和程序規(guī)約S等價,并輸出該符合判定條件的補丁.

通過以上描述可以看出,修復(fù)的前提假設(shè)需要根據(jù)程序規(guī)約S判定程序存在錯誤.需要特別指明的是,上述步驟2)的補丁求解在很多情況下其實是隱含程序規(guī)約指導(dǎo)的,最后也是通過程序規(guī)約S判定補丁的質(zhì)量.下面以內(nèi)存泄露錯誤的修復(fù)[15]為例,使用如圖1所示的示例程序BP進(jìn)行說明.

Fig.1 An example of memory leaks圖1 一個內(nèi)存泄露錯誤的示例

1)給定程序BP,通過先驗知識,我們可以完全明確地描述,不發(fā)生內(nèi)存泄露錯誤的正確程序規(guī)約是“對于任意執(zhí)行路徑和任意插入的釋放語句(free),要保證釋放前已分配、無雙重釋放、無釋放后使用這三者同時滿足”,則程序BP的完全規(guī)約S描述為和原程序語義等價并不發(fā)生內(nèi)存泄露.

BP程序中,第4行申請了內(nèi)存空間;緊接著,第5行的條件語句之后第1個分支對該空間進(jìn)行了釋放,而第2條分支對該空間使用后并未釋放.從而確定BP程序包含一個內(nèi)存泄露錯誤(具體可用測試技術(shù)或程序分析技術(shù)發(fā)現(xiàn)該錯誤),即已知前提是BP不滿足規(guī)約S.

2)修復(fù)過程中,對函數(shù)P=patch(L,OP,C)進(jìn)行求解.首先確定出錯位置L,這里,根據(jù)規(guī)約S指導(dǎo)反復(fù)使用數(shù)據(jù)流分析技術(shù)獲得.具體通過過程間分析技術(shù),使用前向數(shù)據(jù)流分析檢查釋放前已分配,后向數(shù)據(jù)流分析檢查釋放后未使用,前后向數(shù)據(jù)流分析檢查無雙重釋放的位置,求解出錯位置L為第 9行之后和第 11行之前的區(qū)間.根據(jù)規(guī)約S確定修復(fù)該類錯誤主要是在合適的位置插入內(nèi)存釋放語句,即修復(fù)模板OP為free(C).在數(shù)據(jù)流分析過程中,通過處理各種復(fù)雜的計算(如循環(huán)、全局變量、多重分配、空指針判斷等問題)求解補丁內(nèi)容C是指針b,即修復(fù)模板的參數(shù)為指針b.求解函數(shù)P=patch(L,OP,C)獲得候選補丁集合P,即“在第9行之后和第11行之前的區(qū)間插入語句free(b);”.

3)基于在安全插入?yún)^(qū)間盡早釋放內(nèi)存的原則,最終判定補丁“在第10行之前插入語句free(b);”符合程序規(guī)約S,修復(fù)完畢.事實上,由于該類內(nèi)存泄露錯誤的程序規(guī)約是完全規(guī)約,因此采用比較精確的分析技術(shù)和完全規(guī)約能夠求解出高精度補丁,另外一個候選補丁“在第10行之后插入語句free(b);”同樣符合程序規(guī)約S.

針對補丁包含多條語句的情況,可以在單條補丁語句表示patch(L,OP,C)的基礎(chǔ)上進(jìn)行擴(kuò)展.在多個單條補丁語句之間增加先后順序描述,從而組合出一個包含多語句的補丁程序塊.

綜上所述,程序自動修復(fù)中,對程序規(guī)約S的刻畫是非常重要的問題,直接影響到程序自動修復(fù)關(guān)注的核心過程:錯誤定位、補丁生成和補丁判定這3個方面.錯誤自動定位技術(shù)作為一個獨立的研究領(lǐng)域已經(jīng)有30多年的研究歷史,Wong等人、虞凱等人、陳翔等人[16-18]給出了研究綜述,很多程序自動修復(fù)方法使用基于程序頻譜的錯誤定位技術(shù)[19]獲得可能出錯位置排序,這里不再贅述.我們從程序規(guī)約的角度對程序自動修復(fù)研究內(nèi)容進(jìn)行梳理,具有問題和技術(shù)邏輯關(guān)系清晰的優(yōu)勢.本文梳理文獻(xiàn)范圍涵蓋軟件領(lǐng)域的頂級會議(OSDI、POPL、ICSE、FSE、ASE、PLDI、ISSTA、CAV、AAAI等)和頂級期刊(IEEE Trans.on Software Engineering,簡稱 TSE)等,以該領(lǐng)域的問題為導(dǎo)向,從程序規(guī)約的角度重點梳理了補丁自動生成和補丁判定技術(shù)典型的相關(guān)研究成果和存在的核心問題.

1.3 程序自動修復(fù)問題分類

程序自動修復(fù)的目的是對軟件開發(fā)和維護(hù)過程中出現(xiàn)的程序錯誤,在源代碼級別進(jìn)行自動修復(fù),圖2給出了問題分類框架.

Fig.2 Framework of automatic program repair diagram圖2 程序自動修復(fù)框架示意圖

由于在實際場景下針對待修復(fù)程序能夠獲取到的程序規(guī)約各不相同,從而程序自動修復(fù)技術(shù)面向的研究問題、大的前提假設(shè)、具體方法關(guān)注點和困難點也有很大區(qū)別.鑒于程序規(guī)約S對自動修復(fù)的至關(guān)重要性,本文根據(jù)是否能夠完整地刻畫待修復(fù)程序的規(guī)約S,將程序自動修復(fù)技術(shù)面向的問題分為不完全規(guī)約、完全規(guī)約和半完全規(guī)約的程序修復(fù)問題3大類.

(1)不完全規(guī)約的程序自動修復(fù)問題是目前研究成果最多的一類問題.

該類問題就是基于測試集的修復(fù)技術(shù)面向的問題,其將測試集或者通過測試集提取的條件約束作為最終判定自動生成補丁質(zhì)量的程序規(guī)約S.一方面,現(xiàn)實世界中不易獲取充足的測試用例;另一方面,更關(guān)鍵的問題是測試集并不能完整地表示程序規(guī)約[20,21].基于測試集的修復(fù)技術(shù)可進(jìn)一步分為基于搜索和基于語義的修復(fù)技術(shù)兩種類型,兩者具有共同的潛在假設(shè),即如果生成的補丁通過全部測試用例,則都認(rèn)為該補丁正確[11].

不完全規(guī)約的修復(fù)問題中,基于搜索的經(jīng)典修復(fù)技術(shù)直接將測試集作為程序規(guī)約S構(gòu)造搜索算法來判定候選補丁搜索空間中的補丁質(zhì)量,目標(biāo)是輸出通過全部測試用例的程序補丁,其標(biāo)準(zhǔn)結(jié)構(gòu)符合生成-檢測類型(generate-and-validate).該類修復(fù)技術(shù)要求輸入一個帶有bug的程序及其測試用例集,包含至少1個測試用例因為待修復(fù)的bug而無法通過測試,輸出0個、1個或多個通過測試集的補丁.打過補丁的程序通過整個測試用例集中原來未通過的用例表示修復(fù)了該 bug,同時,通過剩余的原來已經(jīng)通過測試的用例表示該補丁未引入新的錯誤.輸出0個補丁表示未能成功修復(fù);1個表示該修復(fù)方法可生成唯一針對待修復(fù)bug的補丁;輸出多個補丁表示針對當(dāng)前用例集存在多種修復(fù)補丁的情況.由于測試集本質(zhì)上不能表示完整的規(guī)約,通過全部測試用例的補丁往往包含疑似正確補丁(plausible patch)[22],即候選補丁通過給定的測試集并不能保證測試集之外的功能也符合原程序期望的語義.因此,該類修復(fù)技術(shù)目前的主要問題是輸出的補丁正確率較低,存在過擬合問題(overfitting problem)[23],即生成的疑似正確補丁只是擬合了測試用例集而并非完整的原程序期望語義.

不完全規(guī)約的修復(fù)問題中,基于語義的修復(fù)技術(shù)通過符號執(zhí)行技術(shù)和測試集提取條件約束,然后轉(zhuǎn)化為約束求解問題,并結(jié)合程序合成(program synthesis)技術(shù)生成補丁.該類修復(fù)技術(shù)將基于測試用例提取的全部語義約束作為程序規(guī)約S,對比基于搜索的修復(fù)技術(shù)需要處理龐大的候選補丁搜索空間,其更有針對性地提取約束條件并采用比較精確的分析技術(shù)生成補丁.由于基于搜索和基于語義的修復(fù)技術(shù)具有共同的潛在假設(shè),基于語義的修復(fù)技術(shù)也不可幸免地存在過擬合問題[11].

不完全規(guī)約的修復(fù)問題特性,使得不斷提高輸出補丁的精度成為基于測試集的修復(fù)技術(shù)面臨的核心問題.在補丁生成階段,已有很多細(xì)粒度的補丁生成方法致力于提高生成補丁的精度.在補丁判定階段,存在疑似正確補丁的現(xiàn)象[22]被描述為過擬合問題[23],是該階段需要克服的主要困難.即在生成的多個補丁均通過全部測試用例或者基于測試用例提取的全部約束條件的情況下,人工分析后發(fā)現(xiàn)依然包含錯誤的補丁.本質(zhì)上是測試用例集或者約束條件刻畫的程序規(guī)約S的區(qū)分度不夠,無法進(jìn)一步區(qū)分輸出的潛在錯誤補丁.

緩解過擬合問題可以分為規(guī)約補全問題和補丁擇優(yōu)問題兩類.兩類問題的研究目的都是為了提高輸出補丁的正確率.規(guī)約補全問題是研究程序規(guī)約本身,如何通過額外的程序期望語義信息直接加強規(guī)約本身來增強基于已有測試集構(gòu)造的補丁判定條件.補丁擇優(yōu)的研究內(nèi)容與增強規(guī)約本身無關(guān),在已刻畫的程序規(guī)約S無法識別潛在錯誤補丁的情況下,如何通過其他規(guī)約之外的信息進(jìn)一步識別潛在錯誤補丁,同時盡可能地減少對正確補丁的誤報,從而進(jìn)一步提高輸出補丁的正確率是其研究的核心內(nèi)容.目前,解決補丁擇優(yōu)問題的主要技術(shù)包括補丁最小化、利用啟發(fā)式規(guī)則、基于概率模型的分類和排序思想等.文獻(xiàn)[24]指出,選擇最小化的補丁作為最終采用的補丁,其基本假設(shè)為最小化的補丁引入新錯誤的可能性最小;文獻(xiàn)[25]指出,選擇和原程序相似度最高的補丁作為最終采用的補丁,其基本假設(shè)為原BUG程序和修復(fù)后的正確程序之間語義高度相似等.

(2)完全規(guī)約的程序自動修復(fù)問題.

該類問題的特點是能夠完全明確地描述待修復(fù)程序的完整規(guī)約,即刻畫的程序規(guī)約S和原程序語義等價且修復(fù)后不引入原程序語義變化.針對該類問題,主要枚舉了幾種明確的特定錯誤類型,能夠完整地刻畫程序規(guī)約,其規(guī)約S和原程序語義等價且修復(fù)特定錯誤不引入原程序語義變化,其中,不發(fā)生特定錯誤能夠進(jìn)行明確和完整的描述.該類問題的前提假設(shè)是開發(fā)人員事先已經(jīng)確定錯誤類型,由于面向具體問題的不同而方法各不相同,具體方法修復(fù)能力只針對特定錯誤類型有效.目前已有的完全規(guī)約程序自動修復(fù)問題包括內(nèi)存泄漏、并發(fā)錯誤中的數(shù)據(jù)競爭、原子性違背、順序違背和死鎖、資源泄露、配置錯誤以及特定性能錯誤的修復(fù)問題.例如,針對內(nèi)存泄露[15]的特定類型錯誤,其完整的程序規(guī)約S和原程序語義等價并且修復(fù)內(nèi)存泄露錯誤不引入原程序語義變化,無內(nèi)存泄露的完整描述前文已述.若修復(fù)后的程序滿足以上規(guī)約,則不存在內(nèi)存泄露的同時滿足原程序的功能要求.針對并發(fā)錯誤中常見的子類型,包括死鎖、數(shù)據(jù)競爭、原子性違反和順序違背這4類錯誤[26],不發(fā)生以上4類錯誤的原因也有明確的定義并可以完整地刻畫程序規(guī)約,其程序規(guī)約S和原程序串行語義等價并且不發(fā)生以上并發(fā)錯誤.

(3)半完全規(guī)約的程序自動修復(fù)問題.

除了明確的不完全規(guī)約和完全規(guī)約的程序自動修復(fù)問題以外,剩余的問題都屬于半完全規(guī)約的程序自動修復(fù)問題,即修復(fù)中刻畫的程序規(guī)約S是否完整不確定.針對該類問題的修復(fù),往往先假設(shè)具有完整的程序規(guī)約S,通過判定的修復(fù)補丁還需要事后進(jìn)一步的人工確認(rèn)或者正確性證明.一些文獻(xiàn)中基于契約(contract)[27]進(jìn)行程序自動修復(fù),假設(shè)這些契約是完整的程序規(guī)約,則用于判定修復(fù)的正確性之后,再人工地確認(rèn)或進(jìn)行正確性證明.契約是指編程元素(例如類或者函數(shù))之間存在的某種固有約定,具體表示形式為前置條件(precondition)、后置條件(postcondition)和類不變式(class invariant)等程序局部要保持的性質(zhì),其完整性不確定.還有一些文獻(xiàn)需要使用特定語言手工編寫程序規(guī)約,其手工編寫的完整性不確定.甚至有一些文獻(xiàn)中使用的規(guī)約來自于神經(jīng)網(wǎng)絡(luò)模型,神經(jīng)網(wǎng)絡(luò)模型通過計算機能夠理解的特征來刻畫程序的語義特征,這種學(xué)習(xí)模型的質(zhì)量取決于特征向量的選擇和訓(xùn)練集的質(zhì)量,該模型表示的程序規(guī)約S的完整性不確定.

2 不完全規(guī)約的程序修復(fù)問題及方法

正如第 1.3節(jié)所述,不完全規(guī)約的修復(fù)問題主要是基于測試集的程序自動修復(fù)技術(shù)面向的問題.基于測試集的程序自動修復(fù)技術(shù)包括基于搜索和基于語義兩類修復(fù)方法,其具有共同的潛在假設(shè),將通過全部測試用例的補丁認(rèn)為是正確的[11].由于測試用例集表示的不完整規(guī)約導(dǎo)致最終產(chǎn)生疑似正確補丁,這些補丁只滿足了測試集而不能保證同時滿足測試集之外的程序期望語義,該問題被稱為過擬合問題[22].

2.1 過擬合問題分析

2015年,Qi等人[22]發(fā)現(xiàn),基于測試集的修復(fù)技術(shù)中基于搜索的修復(fù)方法修復(fù)正確率并不高,通過測試集中全部測試用例的補丁并不是必然正確,通過全部測試用例卻依然錯誤的補丁被稱為疑似正確補丁.疑似正確補丁雖然通過了選定的測試用例集,但并不能保證符合測試集之外的其他程序規(guī)約.產(chǎn)生大量的疑似正確補丁不但不能達(dá)到程序自動修復(fù)的目的,反而增加了大量人工確認(rèn)輸出補丁正確性的工作量.自此之后形成了一個明顯的轉(zhuǎn)折點,如何提高該類修復(fù)方法輸出補丁的精度成為研究的關(guān)鍵問題.Smith等人[23]進(jìn)一步分析認(rèn)為,補丁的質(zhì)量和修復(fù)中所使用的測試用例集的覆蓋率成正比.

2016年,Long等人[28]解釋了基于搜索的自動修復(fù)方法產(chǎn)生的補丁質(zhì)量較低的原因.在整個候選補丁搜索空間中,正確的補丁是稀疏的,而疑似正確的補丁相對來說更加豐富.在他們的實驗中,針對同一個錯誤經(jīng)常有成百上千個疑似正確補丁,其中只有一兩個是正確的補丁.因此,一方面,修復(fù)工具很難從大量的搜索空間中找出正確的補丁;另一方面,雖然更大和更豐富的搜索空間包含更多的絕對數(shù)量正確補丁,但被準(zhǔn)確識別出的正確補丁卻更少.因為更多的候選補丁增加了判定時間,占比更多的疑似正確補丁的驗證阻礙了正確補丁的發(fā)現(xiàn).

2018年,Le等人[11]發(fā)現(xiàn),基于語義的修復(fù)方法也同樣存在過擬合問題,但某些情況下過擬合現(xiàn)象和基于搜索的方法的表現(xiàn)形式不同.他們對比了基于搜索的修復(fù)方法中存在的過擬合問題,通過 IntroClass[29]和Codeflaws[30]兩個benchmarks,以及2016年 Mechtaev等人[31]提出的基于語義修復(fù)方法Angelix分析過擬合問題.他們假設(shè)測試集中測試用例的總量和來源、未執(zhí)行通過的測試用例數(shù)量、基于語義的修復(fù)方法設(shè)計方式等和對應(yīng)的過擬合問題相關(guān).實驗結(jié)果表明:一些情況下,基于搜索和基于語義的修復(fù)方法過擬合結(jié)果一致;另一些情況下,兩者過擬合結(jié)果不同.他們發(fā)現(xiàn),使用多種程序合成引擎(program synthesis engine)是基于語義的修復(fù)方法提高修復(fù)能力的一種可能措施.這一結(jié)論與2017年Le等人[32]得出的結(jié)論一致.他們通過分析多個過擬合的實例和實驗現(xiàn)象進(jìn)一步指出,基于語義的修復(fù)方法存在過擬合問題的一種可能原因是底層程序合成引擎采用過于保守的策略,其生成補丁時直接使用第1種求解合成的方案,而沒有其他可替代的備用方案.

2.2 基于測試集的程序修復(fù)新進(jìn)展

下面分別從補丁生成和補丁判定兩個階段介紹不完全規(guī)約程序修復(fù)問題的研究進(jìn)展.由于不完全規(guī)約的修復(fù)問題特性使得修復(fù)產(chǎn)生的補丁精度不高,在補丁生成階段,如何生成高精度補丁是核心問題;在補丁判定階段,規(guī)約補全和補丁擇優(yōu)則是需要研究的關(guān)鍵問題.

2.2.1 補丁生成

1)基于搜索的補丁生成方法

2016年,Le等人[33]從人工修復(fù)的歷史信息中挖掘模板來指導(dǎo)高質(zhì)量候選補丁的生成,通過計算挖掘模板的頻度,賦予修復(fù)模板對應(yīng)的權(quán)重.權(quán)重信息高效地指導(dǎo)候選補丁生成,同時也有助于對輸出補丁排序,從而提升修復(fù)能力和修復(fù)效率.具體使用AST級別的commit比較獲取修復(fù)歷史的變化情況,同時將挖掘?qū)ο笙拗圃趩未a行的改變,這有利于過濾掉 bug修復(fù)操作中包含增加新特性或功能等代碼塊的影響.利用突變測試技術(shù)(mutation testing)生成候選補丁,并根據(jù)匹配挖掘的 5類規(guī)則的頻度信息對輸出補丁質(zhì)量進(jìn)行排序.基于第 1.2節(jié)我們提出的補丁語句表示patch(L,OP,C),之前代表性的方法GenProg[24]相當(dāng)于將OP模板和C補丁語句所包含的內(nèi)容在語句級別通過變異和交叉操作進(jìn)行粗粒度的考慮,而 PAR[34]方法將OP模板單獨提出并細(xì)化為 10種類型,該方法在前文基礎(chǔ)上進(jìn)一步賦予OP模板權(quán)重.因此,該方法最終獲得比GenProg和PAR兩種工具更好的修復(fù)效果.

2017年,Suzuki等人[35]提出了REFAZER,從正確修復(fù)的實例程序(example)中學(xué)習(xí)細(xì)粒度的修復(fù)模板(稱作程序轉(zhuǎn)換(program transformation))來指導(dǎo)包含同類錯誤問題程序的修復(fù).例如,接口誤用問題在修復(fù)時需要在多處調(diào)用位置使用新接口替換.該類問題具有相同的修復(fù)方式(替換接口),但在不同程序?qū)崿F(xiàn)中具體使用的函數(shù)名稱、變量名稱或表達(dá)式不同.REFAZER具體利用領(lǐng)域?qū)Ｓ谜Z言(domain-specific language,簡稱DSL)描述程序語法轉(zhuǎn)換,形成一系列在AST級別的變換序列,事實上,相當(dāng)于刻畫補丁語句表示patch(L,OP,C)中的修復(fù)模板OP.為了減少漏報(修復(fù)模板太抽象)和誤報(修復(fù)模板太具體),在抽取修復(fù)模板時需要在具體和抽象中間取得一個平衡,REFAZER借鑒了歸納編程(inductive programming,簡稱 IP)和樣例編程(programming-by-example,簡稱PBE)的思想.REFAZER利用720個學(xué)生參加的4個編程任務(wù)所產(chǎn)生的數(shù)據(jù)集進(jìn)行實驗,可以幫助學(xué)生修復(fù)87%的同類錯誤.

2017年,熊英飛等人[36]針對不完全規(guī)約程序修復(fù)問題,聚焦在條件錯誤,提出了 ACS,以專門解決高精度補丁生成和緩解程序修復(fù)過擬合問題.鑒于前述Prophet、Qlose和Angelix等方法利用候選補丁正確率排序的粒度過大問題,他們將修復(fù)對象聚焦在單變量條件類錯誤問題,利用啟發(fā)式方法合成待修復(fù)條件語句,并按正確性排序.具體基于變量使用的局部性原理,利用變量間的依賴關(guān)系排序確定條件表達(dá)式中應(yīng)該使用的候選變量,并利用文本分析技術(shù)對相關(guān)的 API文檔信息分析進(jìn)一步過濾候選變量.利用挖掘技術(shù)對其他項目中相似上下文代碼片段所使用的謂詞按頻率排序確定候選謂詞,最后,通過正反測試用例獲取測試預(yù)言(test oracle),合成待修復(fù)的條件語句.結(jié)合補丁語句表示patch(L,OP,C)來說明,出錯位置L利用傳統(tǒng)程序頻譜的方法[19]并結(jié)合已有的基于謂詞切換的錯誤定位技術(shù)[37],兼顧程序規(guī)模和定位精度,高效地對條件類錯誤進(jìn)行定位.條件類錯誤的修復(fù)模板OP是相對固定的.該方法對合成條件補丁的素材C,包括變量(或表達(dá)式)、謂詞等進(jìn)行了更細(xì)粒度的重點研究,因此獲得了更高的修復(fù)準(zhǔn)確率.在Defects4J benchmark上的實驗結(jié)果顯示其修復(fù)準(zhǔn)確率在78.3%,顯著高于前述方法(一般修復(fù)準(zhǔn)確率低于40%).

2017年,Ripon等人[38]提出了專門修復(fù)面向?qū)ο蟪绦蝈e誤的自動修復(fù)方法ELIXIR,其主要關(guān)注函數(shù)調(diào)用和表達(dá)式錯誤.ELIXIR利用基于頻譜的定位技術(shù)Ochiai確定可能的出錯位置L,通過收集到的對象和變量等基礎(chǔ)素材C,具體使用8種修復(fù)模板OP進(jìn)行變換產(chǎn)生候選補丁(具體修復(fù)模板包括改變變量類型、改變表達(dá)式返回值狀態(tài)、空指針檢查等).該方法的主要貢獻(xiàn)是利用機器學(xué)習(xí)模型對候選補丁進(jìn)行排序,從而提高用于補丁判定的候選補丁質(zhì)量.特征向量的選擇主要關(guān)注出錯語句的上下文,包括標(biāo)識符在上下文中的使用頻率、標(biāo)識符最近使用位置和出錯語句位置之間的距離、修復(fù)補丁中是否包含與上下文命名相似的元素、修復(fù)使用的標(biāo)識符是否在錯誤報告中引用這4種特征.在Defects4J benchmark上的實驗結(jié)果顯示其修復(fù)準(zhǔn)確率在85%,在自己提供的Bugs.jar實驗數(shù)據(jù)集上正確修復(fù)率在57%.

2017年,Chen等人[39]提出從JAVA代碼中自動提取細(xì)粒度狀態(tài)抽象信息(類似于Eiffel語言中手工編寫的契約信息),從而指導(dǎo)生成高質(zhì)量候選補丁,形成的方法 JAID屬于基于搜索的修復(fù)方法.該方法通過函數(shù)純度分析(purity analysis)等靜態(tài)分析方法提取狀態(tài)抽象的斷言信息,基于狀態(tài)抽象信息形成的斷言和測試確定出錯的可疑位置L.補丁生成主要是基于狀態(tài)抽象斷言信息對出錯區(qū)域做變換,設(shè)計了5個修復(fù)模板OP,具體類似增加一個布爾條件對action語句和已有舊語句進(jìn)行if-else代碼塊組合.補丁內(nèi)容C在該方法中其實是action語句,action語句的求解通過對已有語句進(jìn)行語法和語義的修改,使其符合相應(yīng)狀態(tài)抽象斷言,具體修改操作包括修改狀態(tài)、修改表達(dá)式、修改一條語句和修改控制流這4種.JAID在Defects4J benchmark上進(jìn)行實驗,產(chǎn)生通過測試集的修復(fù)補丁對應(yīng)31個bug,并基于啟發(fā)式規(guī)則和出錯定位可疑值信息對輸出補丁進(jìn)行排序,通過人工進(jìn)一步確認(rèn)排名靠前的輸出補丁,其中25個修復(fù)補丁是正確的.

2017年,Qi等人[40]提出利用已有代碼(與錯誤代碼語法相關(guān)的數(shù)據(jù)庫代碼數(shù)據(jù))生成補丁的方法ssFix.針對如何生成高質(zhì)量補丁的核心問題,一些研究假設(shè)生成補丁所需的正確語句或者表達(dá)式可以在出錯項目本地代碼找到[24]或者在其他項目的代碼中找到[41],這些正確語句或者表達(dá)式可以直接用于構(gòu)造補丁.另一些研究指出,通過語義搜索獲得修復(fù)出錯語句相關(guān)的正確語義代碼片段,利用這些語義片段提高生成補丁的質(zhì)量.CodePhage[42]和 SearchRepair[43]屬于該類型的研究工作.鑒于上述基于語義的搜索方法開銷太大且不能處理規(guī)模較大的程序,ssFix通過搜索和出錯語句上下文語法相關(guān)的代碼片段,形成一種輕量級的利用語法相關(guān)的代碼片段提高生成補丁質(zhì)量的修復(fù)方法.具體ssFix使用GZoltar確定疑似出錯位置L,通過結(jié)構(gòu)相似性和概念相似性搜索與出錯語句上下文語法相關(guān)的代碼片段,具體設(shè)定替換、插入和刪除這3種修復(fù)模板OP,對語法相關(guān)的程序片段中的元素進(jìn)行變換生成補丁.ssFix在Defects4J benchmark上進(jìn)行實驗,能夠產(chǎn)生通過測試集的修復(fù)補丁20個,并且輸出每個補丁平均需要11min.

2018年,Ming等人[44]提出了CapGen形成上下文感知的補丁自動生成技術(shù).基于搜索的程序自動修復(fù)技術(shù)不能高效地生成正確補丁,主要原因一方面是候選補丁搜索空間可能本身就不包含正確補丁;另一方面是搜索空間太大,使得在限定的時間閾值未找到正確補丁.該方法有效利用了更細(xì)粒度的 AST上下文信息(context)生成補丁,提出了 3種模型獲取更細(xì)粒度的補丁修復(fù)素材,同時利用上下文感知信息對變異操作進(jìn)行排序,從而限制搜索空間.結(jié)合補丁語句表示patch(L,OP,C)來說明,出錯位置L利用傳統(tǒng)程序頻譜的方法進(jìn)行定位[19].該方法的創(chuàng)新是修復(fù)模板OP由上下文信息指導(dǎo)選擇變異操作,C補丁語句所包含的內(nèi)容相當(dāng)于在表達(dá)式級別(與語句級別相比更細(xì)粒度)獲取更細(xì)粒度內(nèi)容,主要是有效利用AST上下文信息形成3種模型選擇細(xì)粒度內(nèi)容合成補丁.給出的實驗結(jié)果CapGen可達(dá)到84%的精度,同時過濾掉98.78%疑似正確的補丁.

2018年,Hua等人[45]針對基于搜索的修復(fù)方法中龐大的候選補丁搜索空間在遍歷時需要迭代的對候選程序重復(fù)編譯和重復(fù)執(zhí)行的低效率問題,提出了在測試執(zhí)行時按需生成補丁的方法 SketchFix.和迭代地重復(fù)編譯和重復(fù)執(zhí)行每個完整候選程序的方法不同,SketchFix在抽象語法樹級別將程序錯誤的修復(fù)部分轉(zhuǎn)換成若干類似組件方式的概要(sketch),每個類似組件方式的概要獨立編譯,并和原程序正確的部分以“拉抽屜”的形式按需組合出新的候選程序.該方法集成的考慮補丁生成和補丁判定階段精簡搜索空間,同時使用細(xì)粒度的抽象語法樹級別轉(zhuǎn)換技術(shù)生成語義更接近原程序的高質(zhì)量候選補丁.在 Defects4J benchmark數(shù)據(jù)集上,SketchFix在23min內(nèi)成功修復(fù)了357個錯誤中的19個,在整個搜索空間中找到第1個通過判定的補丁平均使用1.6%的重復(fù)編譯和3.0%的重復(fù)執(zhí)行次數(shù).

2)基于語義的補丁生成方法

2015年,Mechtaev等人針對如何生成高精度補丁的核心問題,提出了生成更簡化補丁的自動修復(fù)方法DirectFix[46].其基本假設(shè)是:相比復(fù)雜的修復(fù)操作,更簡化的補丁對原程序正確語義修改得更少,簡單的補丁引入新錯誤的可能性更小.DirectFix不再考慮為每個可疑出錯位置枚舉候選補丁,而是更高效地將錯誤定位和補丁生成合并在一起,作為部分最大可滿足性問題進(jìn)行求解,直接選擇滿足約束的最簡化補丁作為輸出.DirectFix在 SIR(software-artifact infrastructure repository)數(shù)據(jù)集[47]和 Coreutils數(shù)據(jù)集[48]上實驗,能夠成功產(chǎn)生 59%的bug補丁,其中56%是正確的補丁;同時,DirectFix輸出的正確補丁大多數(shù)比SemFix[49]更簡單.

2016年,Mechtaev等人[31]提出了輕量級符號執(zhí)行技術(shù)處理規(guī)模更大的程序中錯誤修復(fù)的方法 Angelix.具體利用測試用例集驅(qū)動可控的符號執(zhí)行技術(shù)(controlled symbolic execution)收集路徑條件,將通過測試用例的可疑出錯語句期望輸出約束稱為天使森林(angelic forest),把基于測試集獲取的修復(fù)約束(repair constraint)作為程序規(guī)約S.與之前的同類修復(fù)技術(shù)SemFix[49]和DirectFix[46]相比,該方法的符號執(zhí)行更加輕量級,只對可疑出錯的表達(dá)式進(jìn)行符號化而不是對程序輸入符號化來獲取整個程序的語義信息.輕量的修復(fù)技術(shù)在提高效率的同時,更重要的是能夠處理大規(guī)模的程序修復(fù)問題.結(jié)合補丁語句表示patch(L,OP,C)來說明,事實上,該方法中可疑出錯語句的位置L是作為算法輸入手工給定,OP和C通過符號執(zhí)行的路徑語義信息和約束求解獲取,程序規(guī)約S由修復(fù)約束(repair constraint)表示,但其規(guī)約的完整性依賴于提供的測試用例集.同時,在約束求解過程中使用近似值也可能增加修復(fù)的不完整性.開發(fā)的 Angelix修復(fù)工具能夠進(jìn)行多點程序修復(fù)(multiple buggy locations,即 bug存在于多條語句之中),同時能夠自動修復(fù)著名的心臟滴血漏洞(heartbleed vulnerability),在GenProg Benchmark[50]上的實驗顯示其修復(fù)準(zhǔn)確率為35.7%.

2017年,玄躋峰等人[51]針對不完全規(guī)約程序修復(fù)問題,聚焦在條件錯誤,提出了基于語義的修復(fù)方法Nopol.該問題的研究和 Nopol方法的更早版本在2014年由DeMarco等人[52]提出.結(jié)合補丁語句表示patch(L,OP,C)來說明,其修復(fù)對象的程序規(guī)約S是基于測試集提取的條件約束.該方法通過天使修復(fù)定位(angelic fix localization)來確定修復(fù)位置L.修復(fù)模板OP是對已有的條件語句進(jìn)行修改,或者在已有語句塊之前添加衛(wèi)士前置條件(guard precondition).通過測試用例執(zhí)行時收集的預(yù)期條件約束轉(zhuǎn)化為約束求解問題獲取補丁內(nèi)容C,基于組件的方法合成條件補丁.在給定的數(shù)據(jù)集上修復(fù)精度表現(xiàn)良好,可以正確修復(fù)17個條件錯誤中的13個.

2.2.2 補丁判定

補丁判定階段,基于搜索和基于語義的修復(fù)方法都存在過擬合問題[11,22],緩解過擬合問題可以進(jìn)一步分為規(guī)約補全問題和補丁擇優(yōu)問題兩類.兩類問題的研究目的都是為了提高輸出補丁的正確率.兩類問題的區(qū)別在第1.3節(jié)已經(jīng)介紹.

1)規(guī)約補全問題和方法

2017年,Qi等人[53]提出了DiffTGen,利用測試用例增強方法緩解修復(fù)的過擬合問題.首先,通過生成測試輸入識別過擬合的補丁,這些測試輸入未覆蓋原 BUG 程序和打過候選補丁的程序之間的語義差別;然后,測試打過候選補丁的程序中存在語義差別的部分,并生成新的測試用例,其基本假設(shè)是增加新的測試用例對基于測試集的自動修復(fù)技術(shù)輸出高精度補丁有益,將這些新測試用例加入測試集中直接加強了用于最終補丁判定的程序規(guī)約S.

直接增加測試用例并不必然對輸出高精度補丁有益,增加更多數(shù)量的已通過測試用例會使得修復(fù)方法產(chǎn)生正確補丁更困難[22],而增加合適數(shù)量的執(zhí)行失敗測試用例在一些情況下反而更有益[54].測試集如何影響修復(fù)過程已有一些研究成果,測試集包含測試用例的數(shù)量嚴(yán)重影響修復(fù)方法輸出的補丁質(zhì)量:測試用例數(shù)量太少,會導(dǎo)致輸出的補丁刪除測試集未覆蓋的功能[22,28];測試用例數(shù)量太多,會使整個修復(fù)過程變慢[9,54,55].合適數(shù)量的測試用例盡可能多地覆蓋程序語義并減少冗余,對成功地進(jìn)行錯誤修復(fù)非常重要[55,56].測試集的覆蓋率也可能影響輸出補丁的質(zhì)量.文獻(xiàn)[23]認(rèn)為,高覆蓋率的測試集對基于搜索的修復(fù)方法輸出高質(zhì)量補丁有益.文獻(xiàn)[57]的研究結(jié)果指出,更高的條件覆蓋率比語句覆蓋率在防止輸出錯誤的補丁方面更有效.

2018年,Mechtaev等人[12]針對過擬合問題提出了SemGraft方法,引入了測試用例集之外的參考實現(xiàn)程序作為程序規(guī)約S,即參考實現(xiàn)程序表示功能和buggy程序相同但實現(xiàn)算法不同的程序.該方法將補丁好壞的判斷轉(zhuǎn)化為語義等價檢測問題,利用反例制導(dǎo)的符號執(zhí)行技術(shù)求解生成補丁,若修復(fù)后的程序和對應(yīng)的參考實現(xiàn)程序之間語義等價,則產(chǎn)生的補丁正確.例如,加法程序和乘法程序功能語義等價但實現(xiàn)算法不同,若加法程序出錯,產(chǎn)生的補丁修復(fù)加法程序后和乘法程序語義等價,則判定為該補丁正確.該方法相當(dāng)于將抽取的參考程序語義符號摘要作為最后補丁判定的程序規(guī)約S,其假設(shè)基于參考程序刻畫的程序規(guī)約比測試集表示的程序規(guī)約更傾向于完整.在給定的Busybox和Coreutils兩個項目的實驗數(shù)據(jù)集中,SemGraft(修復(fù)了12個錯誤)比基于測試用例集提取符號約束進(jìn)行補丁判定的 Angelix方法(僅修復(fù) 4個錯誤)更有效,因此也說明參考程序語義代表的規(guī)約比給定的測試用例集表示的規(guī)約更完備.

2)補丁擇優(yōu)問題和方法

2016年,針對過擬合這一關(guān)鍵問題,Tan等人[58]從自動生成的候選補丁中學(xué)習(xí)一般的和領(lǐng)域無關(guān)的反模式(anti-pattern),利用這些反模式排除包含非法修改的候選補丁.相當(dāng)于在待驗證的程序規(guī)約S中枚舉了一系列反例,利用過濾反例附加條件來提升修復(fù)質(zhì)量和性能.Antoni等人[25]引入程序距離(program distance)的概念來解決過擬合問題.當(dāng)測試用例集無法進(jìn)一步區(qū)分已通過測試的多個補丁正確與否時,該方法假設(shè)修復(fù)后的程序和原程序相似度越高,則補丁越趨向于正確.將識別補丁的好壞問題轉(zhuǎn)化為補丁質(zhì)量排序問題,計算各個打補丁程序和原程序的距離進(jìn)行排序(距離越小,則相似度越高),相當(dāng)于在測試集代表的程序規(guī)約S無法進(jìn)一步區(qū)分已通過測試的補丁好壞時,根據(jù)相似度計算的排序結(jié)果進(jìn)一步補丁擇優(yōu).具體開發(fā)了 Qlose修復(fù)工具,利用形式化方法刻畫原程序(bug程序)和候選補丁程序的2種語法距離和3種語義距離,找出通過全部測試用例同時語法和語義距離更接近原BUG程序的候選補丁作為最終輸出的補丁.Fan等人[59]利用學(xué)習(xí)人工修復(fù)的正確補丁獲得應(yīng)用獨立的概率模型,利用該模型對候選補丁進(jìn)行排序,從而確定補丁質(zhì)量.假設(shè)補丁的正確性包括補丁本身和上下文交互兩部分,該方法通過這兩個部分特征學(xué)習(xí)獲得最大似然估計的概率模型,相當(dāng)于在測試集代表的程序規(guī)約S無法進(jìn)一步區(qū)分已通過測試的補丁好壞時,根據(jù)該模型對輸出補丁排序進(jìn)一步擇優(yōu).開發(fā)的Prophet修復(fù)工具能夠面向真實的大規(guī)模程序(成百上千萬行代碼體量)進(jìn)行自動錯誤修復(fù).在GenProg Benchmark[50]上的實驗顯示,其修復(fù)準(zhǔn)確率為38.5%.

2018年,熊英飛等人[60]提出一種全新的基于測試用例執(zhí)行行為相似度進(jìn)行補丁擇優(yōu)的方法.基于測試用例的補丁質(zhì)量判定方法只關(guān)注給定測試的輸入、對應(yīng)的實際輸出結(jié)果,并與預(yù)期結(jié)果比對,卻對測試用例的執(zhí)行過程關(guān)注不夠.該團(tuán)隊將補丁擇優(yōu)問題轉(zhuǎn)化為分類問題,通過測試用例執(zhí)行行為的相似度,抽象出一個模型進(jìn)行分類.

· 首先觀察到兩個準(zhǔn)則.

1)若兩個測試用例具有相似的執(zhí)行行為,則兩者趨向于相同的執(zhí)行結(jié)果(例如觸發(fā)相同的錯誤或者均是正確執(zhí)行行為).

2)未打補丁前執(zhí)行通過的測試用例,在打補丁前后執(zhí)行行為趨向于相似;未打補丁前執(zhí)行失敗的測試用例,在打補丁前后執(zhí)行行為趨向于不同.

· 然后,一方面通過生成可達(dá)修復(fù)區(qū)域的定向輸入,結(jié)合準(zhǔn)則 1)獲得測試預(yù)言(test oracle)形成新的測試用例,從而加強了原來的測試用例集表示的程序規(guī)約S;另一方面,利用準(zhǔn)則 2)并確定合適的相似度閾值構(gòu)建分類模型,對通過全部測試用例的多個補丁進(jìn)一步分類和補丁擇優(yōu).

該方法相當(dāng)于在原測試集代表的程序規(guī)約基礎(chǔ)上,一方面通過新生成的測試用例直接加強測試集表示的程序規(guī)約S;另一方面,通過分類模型增加附加條件進(jìn)行補丁擇優(yōu).利用 jGenProg、Nopol、Kali和 ACS等程序自動修復(fù)工具產(chǎn)生的130個補丁數(shù)據(jù)集上進(jìn)行有效性驗證.該方法可識別出56.3%的錯誤補丁,并且不會產(chǎn)生誤報,即不會將數(shù)據(jù)集中任何正確的補丁識別為錯誤的.

2.3 小 結(jié)

針對基于測試用例集的程序自動修復(fù)方法,一方面由于其修復(fù)對象是一類通用問題(如該類方法可修復(fù)多種多樣的程序錯誤類型),生成正確率更高的候選補丁受到面向問題的限制很大,往往搜索空間中正確的補丁是稀疏的且大體量的搜索空間嚴(yán)重影響搜索效率;另一方面,測試用例集直接作為程序規(guī)約S用于判定自動修復(fù)工具最終輸出補丁的正確性,其表示的不完整程序規(guī)約必然嚴(yán)重影響輸出補丁質(zhì)量.

針對以上關(guān)鍵問題,一方面從補丁生成的角度,基于第1.2節(jié)提出的補丁語句表示patch(L,OP,C)進(jìn)行說明.現(xiàn)有學(xué)者首先對修復(fù)模板OP進(jìn)行深入研究,利用被修復(fù)程序代碼自身的信息和領(lǐng)域知識作為輔助規(guī)約對輸出的補丁質(zhì)量進(jìn)行排序,從而提高修復(fù)的正確率.包括從修復(fù)的歷史信息中挖掘模板,從而對修復(fù)模板賦予不同的權(quán)重來更有效地指導(dǎo)候選補丁的生成;通過實例程序(example)學(xué)習(xí)細(xì)粒度的修復(fù)模板,并用領(lǐng)域?qū)Ｓ谜Z言(domain-specific language,簡稱 DSL)來刻畫這種細(xì)粒度的模板用于補丁生成.還有一些學(xué)者對合成補丁所需的素材C進(jìn)行深入研究,包括Angelix利用輕量的符號執(zhí)行和約束求解技術(shù)獲取補丁合成素材;ACS對條件類錯誤修復(fù)所需要的補丁內(nèi)容C進(jìn)行細(xì)粒度研究,利用變量使用的局部性原理和謂詞頻率挖掘等技術(shù)獲取合成條件類補丁的素材;CapGen利用抽象語法樹AST的上下文感知信息,提出3種模型來獲取更細(xì)粒度的補丁修復(fù)素材C.以上一系列技術(shù)的研究,大幅度提高了候選補丁空間中所包含補丁的正確率.

另一方面,從補丁判定的角度,研究如何加強補丁質(zhì)量判定條件來緩解過擬合問題.

第 1類規(guī)約補全問題研究規(guī)約本身,通過直接加強程序規(guī)約S,達(dá)到增強補丁質(zhì)量判定條件的目的.例如,DiffTGen通過增量生成新的測試用例來加強原有的測試集,新測試用例覆蓋原 buggy程序和打過候選補丁的程序之間存在語義差別的區(qū)域.其前提假設(shè)是,測試集的覆蓋率更高,對輸出高精度補丁有益.SemGraft引入?yún)⒖汲绦虻乃枷?將提取的參考程序語義替代測試集來表示待修復(fù)程序更完整的程序規(guī)約S.

第2類補丁擇優(yōu)問題研究在已有規(guī)約S無法進(jìn)一步區(qū)分輸出補丁好壞的情況下,利用啟發(fā)式規(guī)則或者概率模型來進(jìn)一步識別錯誤的補丁.例如,從自動生成的候選補丁中學(xué)習(xí)一般的和領(lǐng)域無關(guān)的反模式(anti-pattern)的方法,過濾掉錯誤的補丁.利用測試集信息之外的信息建立概率模型來進(jìn)一步識別錯誤補丁,包括:Qlose利用語法和語義相似度計算程序距離構(gòu)建排序模型;Prophet利用補丁本身正確性和上下文交互正確性兩部分特征學(xué)習(xí)人工補丁獲得最大似然估計的概率模型;利用測試用例執(zhí)行行為相似度構(gòu)建分類模型.

3 完全規(guī)約的程序修復(fù)問題及方法

如前所述,針對某些特定類型錯誤的自動修復(fù)方法具有完整的程序規(guī)約刻畫,即刻畫的程序規(guī)約S和原程序語義等價,且修復(fù)后不引入原程序語義改變.在長期的開發(fā)實踐中,一些特定類型錯誤的發(fā)生原因已被開發(fā)者分析清楚并能夠完整地描述其程序規(guī)約.例如內(nèi)存泄露、資源泄露、特定性能錯誤、配置錯誤、并發(fā)錯誤的一些子類型包括死鎖、數(shù)據(jù)競爭、原子性違反和順序違背等特定類型都各有錯誤特點.結(jié)合第1.2節(jié)提出的補丁語句表示patch(L,OP,C)來說明該類問題的修復(fù),一般程序出錯位置L由調(diào)用?；蛘咭?guī)約指導(dǎo)的精確分析技術(shù)進(jìn)行推測;修復(fù)模板OP針對不同錯誤類型不盡相同,但對特定類型錯誤一般具有相對固定的修復(fù)模式,即結(jié)合先驗知識可以確定相對固定的修復(fù)模板OP;而補丁所包含的內(nèi)容C是該類方法研究的重點之一,因為具有明確的規(guī)約和修復(fù)模式,補丁內(nèi)容可以通過規(guī)約指導(dǎo)的精確分析方法求解獲得.最終判定補丁質(zhì)量時,由于程序規(guī)約是明確和完全的,因此修復(fù)過程產(chǎn)生的補丁準(zhǔn)確性較高.每一種特定類型錯誤都可以代表一類修復(fù)場景,需要針對不同問題的特點進(jìn)行細(xì)致研究,對應(yīng)問題的刻畫、程序規(guī)約描述和因果分析、方法設(shè)計及有效性驗證.

3.1 并發(fā)錯誤修復(fù)

并發(fā)錯誤(concurrency bug)是由于指令在不符合預(yù)期的時機對共享變量進(jìn)行訪問造成的,其完整的程序規(guī)約與原程序串行語義等價,且不發(fā)生特定并發(fā)錯誤.因此,自動修復(fù)的目標(biāo)是消除并發(fā)錯誤且不引入新的錯誤,修復(fù)后的程序和原程序邏輯語義等價,同時具有較好的并發(fā)性能.并發(fā)錯誤中,目前研究最多的包括數(shù)據(jù)競爭、原子性違背、順序違背和死鎖[26],并發(fā)錯誤并不僅僅包括這幾種類型,更多的錯誤類型隨著人類知識的積累會被不斷地識別出來.該部分并發(fā)錯誤的修復(fù)方法在綜述文獻(xiàn)[8]中已經(jīng)進(jìn)行了梳理,但沒有指出該類修復(fù)屬于完全規(guī)約程序修復(fù)問題,我們的工作中簡單梳理并說明問題.

1)原子性違背

原子性違背是指對某一為保證正確性必須原子性執(zhí)行的指令序列,存在一個執(zhí)行交錯,其執(zhí)行效果不與任何該指令序列原子性執(zhí)行時的執(zhí)行交錯的執(zhí)行效果相同[26].該類錯誤程序的完全規(guī)約S和原程序串行語義等價,且不發(fā)生原子性違背問題.

2011年,Jin等人[61]提出了 Afix,能夠自動修復(fù)一類常見的單變量原子性違反(single-variable atomicity violation)并發(fā)錯誤.該錯誤的程序規(guī)約S是可以完全確定的.AFix首次提出該問題,并通過對錯誤檢測報告(特定并發(fā)錯誤檢測工具 CTrigger)進(jìn)行靜態(tài)分析,在合適的位置插入新鎖來保證不發(fā)生原子性違反操作,并在運行時進(jìn)行補丁正確性驗證.然而,AFix只針對1類同步原語(互斥鎖),針對特定的檢測報告只解決原子性違背這1種類型的并發(fā)錯誤,當(dāng)錯誤檢測器不能給出錯誤根本原因(root cause)時,則無法修復(fù)該類錯誤.

2012年,Jin等人[62]提出了更強大的并發(fā)錯誤修復(fù)方法CFix.該方法可適配更多類型的并發(fā)錯誤檢測器(一種集成的檢測和修復(fù)工具).其中,CFix使用 CTrigger[63]作為原子性違背錯誤檢測前端時,通過添加新鎖對檢測到的原子性違背區(qū)域進(jìn)行保護(hù).

2012年,Liu等人[64]提出了Axis方法,能夠進(jìn)行原子性違背并發(fā)錯誤自動修復(fù),其將原子性違反問題看作約束求解問題,利用Petri網(wǎng)(Petri net)模型進(jìn)行修復(fù),其修復(fù)后,程序的安全性和性能比AFix更好.換句話說,其修復(fù)后的程序不會引人新的死鎖,同時并發(fā)性能也相對較好.

2014年,Liu等人[65]針對前述方法AFix[61]和Axis[64]修復(fù)原子性違背可能會引入死鎖的問題,提出Grail更嚴(yán)格的修復(fù)原子性違背問題,同時保證安全性,即不會引入新的死鎖.主要是利用Petri網(wǎng)進(jìn)行分析從而消除引人新的死鎖.該方法只適用于消除2個線程的死鎖問題.

2016年,Liu等人[66]提出了HFix,首先對收集的77個并發(fā)錯誤人工修復(fù)補丁進(jìn)行實證研究,得出人工補丁的 3類修復(fù)策略:通過增加和刪除同步(synchronization)原語來改變執(zhí)行時序、旁過(bypass)一些錯誤指令或容錯(tolerance)處理、共享變量私有化(data private)技術(shù).HFix針對原子性違背修復(fù)策略不同于CFix,利用程序中原有的同步而不是引入新的同步.該方法由于前期的實證研究基礎(chǔ),能夠針對原子性違背錯誤產(chǎn)生類似于人工編寫的高質(zhì)量補丁.

2)數(shù)據(jù)競爭

數(shù)據(jù)競爭是指對某一共享內(nèi)存單元,存在來自不同線程的2個并發(fā)訪問,且至少1個為寫訪問[26].該類錯誤程序的完全規(guī)約S和原程序串行語義等價,且不發(fā)生數(shù)據(jù)競爭問題.

2012年,Jin等人[62]提出了集成并發(fā)錯誤修復(fù)方法 CFix.該方法針對數(shù)據(jù)競爭問題首先確定順序和互斥關(guān)系的組合,然后用靜態(tài)分析和測試方法來確定插入同步操作的位置L,修復(fù)模板OP是順序化或者添加新的互斥鎖.

3)死鎖

死鎖是在某線程集合中的每一個線程都在等待另一個線程占有的互斥性資源,由此造成的循環(huán)等待即為死鎖[26].死鎖包括資源死鎖和通信死鎖[67].死鎖錯誤程序的完全規(guī)約S和原程序串行語義等價,且不發(fā)生線程的循環(huán)等待問題.

2016年,蔡彥等人[68]針對資源死鎖問題提出了自動修復(fù)方法DFixer.由于早期的一些并發(fā)錯誤修復(fù)技術(shù)通過動態(tài)插入新鎖對共享資源進(jìn)行加鎖,該類方案可能會引入新的死鎖.而通過靜態(tài)強制序列化地執(zhí)行可能引發(fā)死鎖的線程來避免死鎖,會導(dǎo)致大量的性能損失問題.DFixer選擇一個線程進(jìn)行修復(fù),通過控制流分析提前獲取鎖而不引入新鎖,消除持有等待必要條件(hold-and-wait necessary condition),并引入喚醒條件保護(hù)(contextaware condition)來消除死鎖.

4)順序違背

順序違背是指某一指令(組)沒有按照設(shè)計預(yù)期,總是在另一指令(組)之前或者之后執(zhí)行的問題[26].順序違背錯誤程序的完全規(guī)約S和原程序串行語義等價,且不存在違反預(yù)期設(shè)計順序執(zhí)行的指令.

2012年,Jin等人[62]提出了集成并發(fā)錯誤修復(fù)方法CFix,其中使用ConMem[69]作為順序違背錯誤檢測前端時,CFix給出的修復(fù)方案是增加線程鄰接(thread-join operation)而不是簡單地增加信號量和等待.該方法由于前期的實證研究基礎(chǔ),針對順序違背錯誤產(chǎn)生的補丁更接近人工編寫的質(zhì)量.

3.2 內(nèi)存泄露和資源泄露修復(fù)

2015年,高慶等人[15]提出了安全的針對C語言的內(nèi)存泄漏錯誤修復(fù)方法.該方法人工給定了針對內(nèi)存泄漏的安全修復(fù)正確規(guī)約,即不發(fā)生內(nèi)存泄露的正確程序規(guī)約是“對于任意執(zhí)行路徑和任意插入的釋放語句(free),要保證釋放前已分配、無雙重釋放、無釋放后使用這三者同時滿足”,則待修復(fù)程序的完整規(guī)約S和原程序語義等價,并不發(fā)生內(nèi)存泄露.該錯誤修復(fù)模板OP是free(C),補丁生成過程是求解free語句的安全插入位置和釋放空間大小(即修復(fù)模板的參數(shù)C)的過程.具體反復(fù)使用使用數(shù)據(jù)流分析和過程間分析技術(shù),通過前向數(shù)據(jù)流分析檢查釋放前分配,后向數(shù)據(jù)流分析檢查釋放后使用,前后向數(shù)據(jù)流分析檢查雙重釋放.分析過程中需要解決一系列復(fù)雜問題,包括對循環(huán)、全局變量、多重分配、空指針判斷等問題的分析和處理.在一定程度上,用數(shù)據(jù)流分析的效率達(dá)到了路徑敏感分析的效果.開發(fā)的leakFix修復(fù)工具在SPEC 2000數(shù)據(jù)集進(jìn)行實驗,對15個項目中檢測到的25個內(nèi)存泄露自動生成了41個正確修復(fù)補丁,平均1個內(nèi)存泄露錯誤生成1.6個補丁.

2018年,Rijnard等人[70]提出用靜態(tài)方法檢測和修復(fù)指針安全屬性違反問題,使用分離邏輯(separation logic)生成補丁,并對輸出補丁進(jìn)行形式驗證.形成的 FootPatch方法可以修復(fù)多種錯誤類型,包括資源泄露、內(nèi)存泄露和空指針解引用這3種.其中,資源泄露、內(nèi)存泄露這兩種錯誤修復(fù)問題屬于完全規(guī)約修復(fù)問題.修復(fù)后,程序規(guī)約S和原程序語義等價,同時不存在資源泄露和內(nèi)存泄露問題.而空指針解引用問題不屬于完全規(guī)約修復(fù)問題,具體在第 4.2節(jié)手工編寫程序規(guī)約中介紹.該方法使用分離邏輯生成補丁并防止補丁過擬合,其假設(shè)修復(fù)代碼存在于原程序中,通過靜態(tài)分析原程序中相關(guān)代碼片段的語義構(gòu)造修復(fù)補丁.該方法不依賴測試集,程序規(guī)約S目前需要使用分離邏輯針對錯誤類型手工編寫.其修復(fù)模板OP和補丁內(nèi)容C都是從原程序中靜態(tài)分析獲取,例如,使用sw_free和swHashMap_node_free(hmap,root)等釋放語句從待修復(fù)程序中已經(jīng)封裝好的語句構(gòu)造補丁,更符合原程序的編碼規(guī)范和實現(xiàn)風(fēng)格.

3.3 性能錯誤和配置錯誤修復(fù)

2015年,針對特定性能錯誤,Adrian等人[71]提出了 CARAMEL自動檢測和修復(fù)特定性能錯誤.針對循環(huán)中當(dāng)某個條件成立時,剩余的執(zhí)行都是在浪費計算資源的目標(biāo)研究問題,提出了針對性的修復(fù)方法.通過識別“循環(huán)+條件”并分析滿足給定的性能錯誤判定規(guī)則,然后在適當(dāng)?shù)奈恢貌迦腩愃啤皸l件+break”的修復(fù)模板OP來規(guī)避性能問題,同時不影響程序原有功能.程序的完全規(guī)約S和原程序語義等價,并消除了上述性能問題.該論文獲得了ICSE 2015年的最佳論文獎.

2017年,Weiss等人[72]針對服務(wù)器配置漂移(configuration drift)問題提出了交互式修復(fù)方法Tortoise.配置漂移是指隨著時間推移,管理員對一組服務(wù)器或者服務(wù)做出的配置引起的實際狀態(tài),偏離了管理員所期望的配置狀態(tài)改變.該類問題的完全規(guī)約S和上述特定類型錯誤有所不同,配置漂移的完全規(guī)約S是由管理員選擇的,選擇后修復(fù)的實際配置狀態(tài)和管理員的預(yù)期狀態(tài)等價并且消除了配置漂移錯誤(如配置狀態(tài)不一致等問題).在變更服務(wù)器狀態(tài)時,管理員會輸入一組配置命令序列,Tortoise同時在后臺利用ptrace記錄由管理員的配置命令引發(fā)的服務(wù)器中系統(tǒng)調(diào)用和文件系統(tǒng)變化信息.然后將配置狀態(tài)構(gòu)造成一個模型,其中新的狀態(tài)變更刻畫為硬約束,原來已有的狀態(tài)配置刻畫為軟約束.Tortoise接著將模型表示轉(zhuǎn)化為邏輯公式,利用SMT求解器轉(zhuǎn)化為約束求解問題計算狀態(tài)不一致性并生成修復(fù)補丁,利用啟發(fā)式規(guī)約對補丁排序并推薦給管理員選擇.在給定的42個配置場景中,Tortoise推薦出的第1個修復(fù)補丁76%被管理員采納.其實,在2015年,熊英飛等人[73]提出了Range Fixes的概念(即允許配置項的取值在一定范圍內(nèi)變化)交互式的修復(fù)軟件配置錯誤.軟件配置錯誤問題的完全規(guī)約S也是由用戶選擇,選擇后修復(fù)的實際軟件配置狀態(tài)和用戶的預(yù)期狀態(tài)等價并且消除了配置錯誤.

3.4 小 結(jié)

完全規(guī)約的程序自動修復(fù)問題面向一些特定錯誤類型.目前出現(xiàn)的該類問題已經(jīng)枚舉了并發(fā)錯誤中的數(shù)據(jù)競爭、順序違背、原子性違背和死鎖、內(nèi)存泄露、資源泄露、特定性能問題和配置錯誤等.以上特定錯誤都可以進(jìn)行明確的問題刻畫并且完整地描述待修復(fù)程序規(guī)約S,因此更多地使用精確分析技術(shù)以保證較高的修復(fù)精度.相對于不完全規(guī)約程序的修復(fù)問題,該類問題的修復(fù)技術(shù)不依賴于測試集和龐大的修復(fù)空間,能夠有效地避免過擬合問題.

雖然完全規(guī)約的程序修復(fù)問題對應(yīng)的方法修復(fù)精度和產(chǎn)生的補丁質(zhì)量較高,但定向修復(fù)的固有特性使其修復(fù)能力受限,只對特定類型錯誤有效而不能同時修復(fù)多種類型的錯誤.從以上分析可以看出,該類修復(fù)技術(shù)到目前已枚舉了部分特定錯誤類型,更多的錯誤類型和相關(guān)修復(fù)技術(shù)有待研究,更多錯誤類型的實證研究有必要深入挖掘.

4 半完全規(guī)約的程序修復(fù)問題及方法

如前所述,半完全規(guī)約的程序修復(fù)問題涵蓋了多種類型的程序規(guī)約S,包括契約、手工編寫的程序規(guī)約和神經(jīng)網(wǎng)絡(luò)模型等.結(jié)合第1.2節(jié)提出的補丁語句表示patch(L,OP,C)和程序規(guī)約S來說明該類問題的修復(fù),該類問題的主要特征是修復(fù)中刻畫的程序規(guī)約S是否完整不確定,求解補丁函數(shù)patch(L,OP,C)的過程和不完全規(guī)約的程序修復(fù)問題對應(yīng)的方法在一定程度上有類似之處.但由于先隱含假設(shè)所面向修復(fù)問題的程序規(guī)約S是完整的,修復(fù)后輸出的補丁還需要進(jìn)一步手工檢查或者證明.

4.1 契約作為程序規(guī)約

契約作為程序規(guī)約,具體表示為前置條件(precondition)、后置條件(postcondition)、類不變式(class invariant)等程序局部要保持的性質(zhì).在 Eiffel語言中具有該類規(guī)約,可以類似理解為 Java語言中 JML(Java modeling language)對其設(shè)計規(guī)約的描述.該類修復(fù)技術(shù)中常假設(shè)程序中存在契約,并將其作為指導(dǎo)補丁生成和判定補丁正確性的依據(jù),而契約代表的程序規(guī)約S是否完整并不確定.

2010年,Wei等人[27]首次提出了AutoFix-E,利用契約進(jìn)行程序自動修復(fù).AutoFix-E將Eiffel語言編寫的程序中提供的契約作為判斷程序正確性的標(biāo)準(zhǔn),要求在最終修復(fù)的程序中,函數(shù)在執(zhí)行前的狀態(tài)滿足前置條件和類不變式,函數(shù)執(zhí)行后的狀態(tài)滿足后置條件和類不變式,且執(zhí)行過程中還需要滿足過程內(nèi)部斷言(intermediate assertion).這些斷言和不變式規(guī)范了程序的正確行為,一定程度上可以理解為基于模型的程序自動修復(fù)方法.AutoFix-E在給定的實驗數(shù)據(jù)集上進(jìn)行實驗,可以成功地修復(fù)42個錯誤中的16個.

2011年,裴玉等人[74]提出了AutoFix-E2,在AutoFix-E基于模型的修復(fù)方法基礎(chǔ)上,進(jìn)一步挖掘程序本身包含的信息來指導(dǎo)修復(fù).他們將其稱為基于證據(jù)的修復(fù)方法,將隨機測試、錯誤定位、動靜態(tài)分析收集的結(jié)果作為證據(jù).具體通過靜態(tài)分析(表達(dá)式依賴和控制依賴)和運行通過/未通過兩種測試用例的動態(tài)分析,當(dāng)檢測到待修復(fù)表達(dá)式接受一個可疑值時將其轉(zhuǎn)換為合法的值,從而保持契約的成立.

2014年,裴玉等人[75]提出了 AutoFix的最新實現(xiàn)和實驗,其部分思想在文獻(xiàn)[27,74]中已經(jīng)介紹.AutoFix使用 AutoTest基于契約和隨機測試框架自動產(chǎn)生測試用例,由失敗的測試用例驅(qū)動動態(tài)分析進(jìn)行錯誤定位,基于契約指導(dǎo)生成補丁并進(jìn)行判定,最終利用相關(guān)性對判定通過的補丁進(jìn)行排序.在給定的 204個錯誤修復(fù)實驗中,AutoFix的正確率為42%.由于AutoFix生成補丁的正確性判斷依據(jù)是給定的契約(如果給定的契約表示了不完整的程序規(guī)約,則可能引入誤報),在AutoFix給出的正確補丁中進(jìn)行人工檢查,其完全正確的補丁占有率為59%.

2015年,裴玉等人[76]提出了在IDE中進(jìn)行程序自動修復(fù)的思想,將AutoFix集成到EiffelStudio集成開發(fā)環(huán)境中.AutoFix作為一個推薦系統(tǒng)在IDE后臺自動地檢測源碼錯誤并給出建議的修復(fù)補丁,這將為開發(fā)人員提供強大的自動化功能.

4.2 手工編寫程序規(guī)約

如下修復(fù)問題中刻畫的程序規(guī)約S使用線性時序邏輯(linear-temporal logic)、分離邏輯(separation logic)等手工編寫,其針對不同程序和修復(fù)問題手工編寫,該程序規(guī)約S是否完整不確定.

2005年,Jobstmann等人[77]將程序修復(fù)問題刻畫為一種游戲,獲得一組對程序修改的策略,使得修改后的程序符合程序規(guī)約,則認(rèn)為獲得一次勝利.程序規(guī)約S由線性時序邏輯(linear-temporal logic)給出.該方法假設(shè)程序出錯范圍僅在程序表達(dá)式語句或賦值語句的左值,也就是說,其修復(fù)能力僅包含程序表達(dá)式錯誤或賦值語句錯誤的修復(fù).

2013年,Essen等人[78]使用線性時序邏輯(linear-temporal logic)給出形式化程序規(guī)約S,提出一種新的修復(fù)方法,要求修復(fù)后的程序符合該給定的程序規(guī)約,同時和原 BUG 程序語義保持相似.該方法最大的特點是在修復(fù)過程中強制保持一個原BUG程序執(zhí)行軌跡的子集,從而自動將程序正確部分本身的語義保持下來而不被修改.也就是說,原 BUG程序符合程序規(guī)約的正確部分需要持續(xù)保持,同時只需要小范圍地修改出錯部分的語義,使得整個修復(fù)后的程序在保持原正確部分的同時,滿足線性時序邏輯刻畫的規(guī)約S.

2015年,Kneuss等人[79]提出一種修復(fù)遞歸函數(shù)數(shù)據(jù)類型錯誤(樹、鏈表、整形)的方法.該方法需要開發(fā)人員使用特定的語言編寫程序和對應(yīng)的程序規(guī)約S,其假設(shè)待修復(fù)的錯誤程序是有限狀態(tài)的(infinite-state)并且程序規(guī)約是完整正確的,最終的修復(fù)程序經(jīng)過Leon系統(tǒng)進(jìn)行形式化驗證.

2018年,Rijnard等人[70]提出用靜態(tài)方法檢測和修復(fù)指針安全屬性違反問題,其中,針對空指針解引用問題屬于半完全規(guī)約的程序修復(fù)問題.形成的 FootPatch方法是一個集成的工具,其中,解決空指針解引用問題的程序規(guī)約S使用分離邏輯手工編寫且是否完整不確定;同時,修復(fù)空指針解引用問題后是否改變原程序語義也不確定.該方法對空指針解引用的處理具體包括指針為空添加前置條件檢查、空指針引用報告異常處理等方式,暫未考慮實例化一個新的指針進(jìn)行引用等多樣化方式.以上多種修改方案都可能會改變原程序語義,但是因為FootPatch采用靜態(tài)方法進(jìn)行修復(fù),不會過擬合類似動態(tài)測試用例提供的期望語義.在給定的實驗中,成功地修復(fù)了24個空指針解引用錯誤.

4.3 其他程序規(guī)約

1)測試用例的修復(fù)

2010年,Daniel等人[80]提出了ReAssert自動修復(fù)發(fā)生錯誤的測試用例.當(dāng)一個測試用例執(zhí)行失敗時,可能的情況是被測程序出錯或者測試用例出錯.ReAssert對執(zhí)行出錯的變量值和控制流進(jìn)行動態(tài)分析,進(jìn)而修改錯誤賦值和斷言,并盡可能地保持原測試用例的邏輯功能.ReAssert利用以上策略對執(zhí)行失敗的測試用例進(jìn)行修改,使得原執(zhí)行失敗的測試用例能夠執(zhí)行成功.其潛在假設(shè)是程序行為正確,測試用例執(zhí)行成功則符合程序規(guī)約S.因此,ReAssert無法判定測試用例出錯情況以及測試用例正確的執(zhí)行邏輯.修復(fù)后的測試用例以建議的方式給出,其正確性還需要人工進(jìn)行確認(rèn).

2016年,Gao等人[81]提出了SITAR自動修復(fù)GUI測試腳本.在回歸測試中,由于原GUI程序圖形組件的變化,使得原測試用例的事件或操作序列等輸入不再適應(yīng)當(dāng)前的測試腳本,期望測試的 GUI對象對應(yīng)的斷言和檢查點等測試預(yù)言(test oracle)也需要適應(yīng)性地更新.SITAR通過逆向工程生成的事件流圖和用戶輸入修復(fù)原有測試腳本,使其在新的GUI程序中可用.

2)崩潰錯誤和資源競爭

2015年,高慶等人[82]提出了基于問答系統(tǒng)的特定修復(fù)方法,利用Q&A問答系統(tǒng)中的知識修復(fù)崩潰錯誤.發(fā)生崩潰錯誤的原因很多,崩潰時程序行為如何不確定,目前不能確定地給出完整的程序規(guī)約S.該方法具體通過抽取崩潰路徑信息(crash trace)包含的行號作為候選出錯位置,提煉崩潰報的錯信息構(gòu)造一組查詢,檢索 Stack Overflow問答系統(tǒng)獲得和崩潰相關(guān)的問題和回答頁面列表.然后,通過模糊程序分析技術(shù)(fuzzy program analysis technique)形成修復(fù)的樣例,并利用結(jié)構(gòu)相似度和文本相似度進(jìn)一步過濾噪聲樣例.利用編輯腳本將樣例轉(zhuǎn)化為最終的修復(fù)補丁.實驗中,通過手工確認(rèn),表明可以修復(fù)實際的崩潰錯誤.具體在收集了 24個可復(fù)發(fā)崩潰錯誤數(shù)據(jù)集上,該方法能夠修復(fù)其中的10個崩潰錯誤,其中8個修復(fù)結(jié)果正確.

2016年,Wang等人[83]提出了ARROW,針對現(xiàn)代瀏覽器軟件的并發(fā)執(zhí)行引起的 Web應(yīng)用程序資源競爭問題進(jìn)行自動修復(fù).例如,客戶端Web頁面包含各種類型腳本(HTML、JS和樣式表等),在并發(fā)渲染和異步加載時,這些異步事件和用戶輸入事件相互競爭資源并以非確定性的順序執(zhí)行,可能引起網(wǎng)絡(luò)延遲、執(zhí)行異常等問題.Web頁面異步加載和用戶請求資源競爭問題存在很多執(zhí)行交錯,也不能完全串行,刻畫的程序規(guī)約S是否完全符合預(yù)期行為不確定.ARROW以瀏覽器渲染各頁面元素的前后依賴關(guān)系,將Web頁面靜態(tài)建模為因果圖,通過Web頁面源碼獲取開發(fā)人員預(yù)期的各元素依賴關(guān)系.最后,利用求解器對構(gòu)造的約束進(jìn)行求解,使得兩者不會出現(xiàn)不一致的情況.

3)緩沖區(qū)溢出和整形錯誤

2016年,Gao等人[84]提出了BovInspector,能夠自動檢測和修復(fù)緩沖區(qū)溢出漏洞.為了過濾誤報,對靜態(tài)分析的錯誤檢測結(jié)果進(jìn)行可達(dá)性分析,并在可達(dá)性指導(dǎo)下進(jìn)行符號執(zhí)行收集路徑約束條件和指定的溢出約束條件,通過比對兩者確定真正的緩沖區(qū)溢出漏洞.對確認(rèn)的緩沖區(qū)溢出漏洞采用3種修復(fù)模板OP:添加邊界檢查、替換為更安全的API和擴(kuò)展緩沖區(qū)空間.以上修復(fù)操作都可能改變原程序語義,程序規(guī)約S完整性不確定,修復(fù)結(jié)果需要人工檢查.在給定的實驗中,BovInspector能夠以平均 74.9%的準(zhǔn)確率檢測該類漏洞,并全部產(chǎn)生正確的修復(fù)補丁.

2017年,Cheng等人[85]通過推測合適的變量和表達(dá)式數(shù)據(jù)類型,自動生成整形錯誤的補丁,提出交互式的修復(fù)方法 IntPTI.該方法通過靜態(tài)值分析近似表達(dá)式的值,并收集其可能的正確類型約束,然后轉(zhuǎn)化為約束求解問題,推測可能的正確數(shù)據(jù)類型來生成補丁,最后,通過 Web界面展示供開發(fā)人員交互式選擇和確認(rèn)正確的補丁.具體來說,整形錯誤的程序規(guī)約S由靜態(tài)分析收集約束并求解獲得,其規(guī)約完整性不確定;同時,修復(fù)后是否引起原程序語義變化也不確定.該方法設(shè)計了 3種修復(fù)模板OP:完整性檢查(sanity check)、顯式類型轉(zhuǎn)換(explicit type casting)和改變申明類型(declared type changing).補丁內(nèi)容C即推斷出的正確數(shù)據(jù)類型通過約束求解獲得.IntPTI在收集的7個實際項目數(shù)據(jù)集上實驗,能夠成功地使25個錯誤中的23個補丁被用戶確認(rèn)和采納.其實,2個誤報是由于采用流不敏感的靜態(tài)分析技術(shù)進(jìn)行正確的數(shù)據(jù)類型推斷所引起的.

4)語法錯誤修復(fù)

2017年,Gupta等人[86]首次提出了Deepfix,利用深度學(xué)習(xí)技術(shù)直接生成補丁.這種方法的修復(fù)對象是語法錯誤,將程序抽象為以語句為粒度的序列,利用多層次的神經(jīng)網(wǎng)絡(luò)模型來預(yù)測出錯位置和正確的語句,其修復(fù)精度取決于從訓(xùn)練集中學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò).而神經(jīng)網(wǎng)絡(luò)模型的質(zhì)量取決于特征向量的選擇和訓(xùn)練集的質(zhì)量.該模型表示的程序規(guī)約S的完整性不確定.該方法相當(dāng)于將學(xué)習(xí)獲得的神經(jīng)網(wǎng)絡(luò)模型作為程序規(guī)約S,對學(xué)生的句法錯誤修復(fù)實驗顯示,其完全修復(fù)的準(zhǔn)確率在27%,在其他更復(fù)雜的缺陷上的表現(xiàn)尚不清楚.

5)搜索語句修復(fù)

2014年,Gopinath等人[87]提出一種利用面向數(shù)據(jù)的語言ABAP修復(fù)SELECT語句錯誤的方法.具體利用數(shù)據(jù)分布中所隱含的信息,使用半監(jiān)督的學(xué)習(xí)方法識別正確行為,修復(fù)SELECT語句中WHERE子句附帶的條件錯誤.該方法學(xué)習(xí)獲得的程序規(guī)約S完整性不確定,需要人工確認(rèn)修復(fù)結(jié)果.

6)用戶體驗

2018年,Sonal等人[88]提出了MFix方法自動修復(fù)手機中網(wǎng)頁的友好顯示問題.由于很多網(wǎng)站不是專門為手機設(shè)備設(shè)計和開發(fā)的,這會導(dǎo)致在手機上顯示文本不可讀、導(dǎo)航混亂、內(nèi)容溢出手機設(shè)備顯示窗體等問題,手機上網(wǎng)頁友好顯示的問題規(guī)約S由用戶手工確認(rèn).MFix方法主要關(guān)注字體大小、點擊目標(biāo)間距、內(nèi)容縮放調(diào)整等問題,通過自動生成層疊樣式表(cascading style sheet,簡稱CSS)補丁來優(yōu)化上述問題的友好顯示.MFix首先建立基于圖的網(wǎng)頁布局模型;然后對這些圖進(jìn)行強制編碼以增強顯示友好性,同時最小化布局的損壞,從而生成CSS補丁.該方法使用訪問頻度靠前的38個網(wǎng)站主頁進(jìn)行評估實驗,能夠成功解決占比95%的網(wǎng)站在手機上友好顯示的問題.

4.4 小 結(jié)

半完全規(guī)約的程序修復(fù)問題對應(yīng)的方法擴(kuò)展了程序規(guī)約S的刻畫方式和使用范疇,所使用的契約、形式規(guī)約和學(xué)習(xí)的行為模型等程序規(guī)約有效補充了測試用例不足的問題.該類方法存在的主要問題是:輸出的補丁后期需要人工確認(rèn)或者正確性證明,用于大規(guī)模程序錯誤的修復(fù)非常困難.同時,現(xiàn)實世界中自帶契約、形式規(guī)約等程序規(guī)約的待修復(fù)問題非常少,很多問題的形式規(guī)約需要手工構(gòu)造.

5 總結(jié)和展望

根據(jù)上述文獻(xiàn)研究結(jié)果可以得出:程序自動修復(fù)技術(shù)雖然研究歷史較短,但得到了學(xué)術(shù)界持續(xù)的高熱度關(guān)注,并取得了大量的研究成果.雖然目前暫時還沒有工業(yè)界的應(yīng)用,但一系列的研究成果表明,程序自動修復(fù)技術(shù)已經(jīng)在一定程度上具備自動修復(fù)實際應(yīng)用中簡單錯誤的能力.雖然國內(nèi)對該問題的研究起步較晚,但近年來國內(nèi)的研究情況令人欣慰,包括北京大學(xué)、國防科技大學(xué)、南京大學(xué)、武漢大學(xué)、上海交通大學(xué)和中國科學(xué)院軟件研究所等單位的研究非?；钴S,在頂級期刊發(fā)表的一系列研究成果得到了國外同行的認(rèn)可.本文提出一種基于規(guī)約的程序自動修復(fù)描述,并從程序規(guī)約的角度將問題進(jìn)行分類梳理,程序規(guī)約S的刻畫方式直接影響著補丁生成函數(shù)P=patch(L,OP,C)的求解過程和補丁判定條件的構(gòu)造.從程序自動修復(fù)對象是否具有完整的程序規(guī)約S這個關(guān)鍵問題進(jìn)行分類,對錯誤修復(fù)的不同場景和技術(shù)體系進(jìn)行分類闡述.梳理了各類修復(fù)方法的研究進(jìn)展,闡述了各類研究問題和方法的異同、研究重點和可能存在的問題.

程序自動修復(fù)的研究領(lǐng)域中機遇和挑戰(zhàn)并存,有待更多的研究者們?nèi)〉脛?chuàng)新和突破.我們認(rèn)為,該領(lǐng)域還存在如下值得進(jìn)一步研究的問題.

(1)程序自動修復(fù)技術(shù)給傳統(tǒng)的錯誤定位提供了新的應(yīng)用場景,傳統(tǒng)的錯誤自動定位目的是輔助人工進(jìn)行錯誤修復(fù).輔助人工和輔助機器進(jìn)行錯誤修復(fù)是不同的問題,他們要求的精度不同.例如,人工修復(fù)更傾向于定位到函數(shù)級,而機器自動修復(fù)更需要語句級甚至表達(dá)式級別的精確位置.傳統(tǒng)的錯誤定位更多的研究關(guān)注于錯誤語句的位置排序和可能出錯位置的最小集,而對出錯語句可疑值本身的精確性和語句內(nèi)部可疑錯誤位置研究不足.輔助人和軟件進(jìn)行錯誤自動修復(fù)所需的錯誤位置精度不同,到目前為止,還沒有出現(xiàn)專門針對程序自動修復(fù)技術(shù)而設(shè)計的錯誤高精度自動定位方法.針對程序自動修復(fù)場景,設(shè)計更細(xì)粒度和更高精度的錯誤定位技術(shù)值得深入研究.

(2)針對不完全規(guī)約的程序自動修復(fù)問題,即直接或間接地(基于測試集提取的條件約束)使用測試集作為待修復(fù)程序規(guī)約S,高精度修復(fù)技術(shù)還有待進(jìn)一步研究.一般的程序錯誤中,條件錯誤和函數(shù)調(diào)用錯誤占比更高,因此,對表達(dá)式條件或更復(fù)雜的條件錯誤、接口錯誤的修復(fù)值得深入研究.由于弱測試用例問題依然存在,如何利用更細(xì)粒度的源代碼靜態(tài)信息、代碼執(zhí)行的動態(tài)信息以及其他測試用例之外的信息加強程序規(guī)約,從而加強對輸出補丁的正確性判定條件和增強的規(guī)約指導(dǎo)補丁生成都是重要的研究問題.研究更多的程序規(guī)約刻畫方法用于補丁質(zhì)量判定,例如借鑒傳統(tǒng)的程序驗證和證明技術(shù),結(jié)合具體程序修復(fù)場景進(jìn)一步判定測試用例集無法區(qū)分的補丁正確性問題.多行錯誤、互有依賴的多個錯誤以及跨項目錯誤的程序自動修復(fù)是更復(fù)雜的問題,是同樣值得研究和探討的困難問題.

(3)針對完全規(guī)約的程序自動修復(fù)問題,即待修復(fù)程序規(guī)約S能夠完整刻畫的修復(fù)問題,需要更多實例基礎(chǔ),更多類型特定錯誤的發(fā)生原因和人工修復(fù)方法有待充分的實證研究.基于充分的實證研究基礎(chǔ),更多具有完全規(guī)約的程序自動修復(fù)問題尚待進(jìn)一步發(fā)掘,由于修復(fù)錯誤而引入的程序語義變化的合理性需要充分討論.在提高修復(fù)精度的同時,修復(fù)的補丁質(zhì)量(例如補丁可讀性和人工修復(fù)的補丁質(zhì)量近似等)也是重要的研究問題.另外,將多種特定類型錯誤修復(fù)技術(shù)結(jié)合,例如與缺陷自動分類技術(shù)結(jié)合來提升特定錯誤修復(fù)技術(shù)的可擴(kuò)展性和修復(fù)能力.

(4)對于半完全規(guī)約的程序自動修復(fù)問題,其待修復(fù)程序規(guī)約S是否能夠完整刻畫不確定.在程序自動修復(fù)場景中先假設(shè)有完全規(guī)約,最終生成的補丁程序正確性校驗是核心問題.尤其面對程序規(guī)模較大的情況下,如何結(jié)合程序驗證和證明技術(shù)自動進(jìn)行正確性判定是困難問題.當(dāng)然,對于完全規(guī)約和半完全規(guī)約程序修復(fù)問題本身也值得進(jìn)一步研究,充分討論其內(nèi)涵和外延有助于進(jìn)一步擴(kuò)展程序自動修復(fù)技術(shù)所面向的問題.

統(tǒng)一的程序自動修復(fù)技術(shù)評價標(biāo)準(zhǔn),測試用例和 banchmark不足依然是面臨的客觀問題.測試用例自動生成和測試用例修復(fù)相關(guān)技術(shù)為程序自動修復(fù)提供有效支撐,更大和更符合錯誤自然分布的banchmark有待進(jìn)一步建立.各修復(fù)技術(shù)的橫向?qū)Ρ确治龊徒y(tǒng)一的評價標(biāo)準(zhǔn)有待豐富,從而促進(jìn)修復(fù)技術(shù)的持續(xù)發(fā)展和應(yīng)用.

總體來講,程序自動修復(fù)技術(shù)最終要解決的核心問題是修復(fù)真實 bug,針對實際問題的任何改進(jìn)都值得深入研究.例如,待修復(fù)程序的規(guī)模,即如何修復(fù)規(guī)模盡可能大的程序中包含的真實bug;修復(fù)能力,即如何修復(fù)盡可能多的真實 bug和涵蓋更廣泛的錯誤類型;補丁質(zhì)量,即在保證生成補丁正確性的前提下,如何使工具自動生成的補丁和人工修復(fù)補丁更接近,從而更容易被開發(fā)者接受.針對該熱點研究,未來的機遇和挑戰(zhàn)并存、榮耀和艱辛同在.