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

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

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

3(計(jì)算機(jī)科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院 軟件研究所),北京 100190)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 相關(guān)概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 程序自動(dòng)修復(fù)問(wèn)題分類

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

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

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

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

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

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

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

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

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

(2)完全規(guī)約的程序自動(dòng)修復(fù)問(wèn)題.

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

(3)半完全規(guī)約的程序自動(dòng)修復(fù)問(wèn)題.

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

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

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

2.1 過(guò)擬合問(wèn)題分析

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

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

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

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

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

2.2.1 補(bǔ)丁生成

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

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

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

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

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

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

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

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

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

2)基于語(yǔ)義的補(bǔ)丁生成方法

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

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

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

2.2.2 補(bǔ)丁判定

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

1)規(guī)約補(bǔ)全問(wèn)題和方法

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

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

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

2)補(bǔ)丁擇優(yōu)問(wèn)題和方法

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

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

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

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

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

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

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

2.3 小 結(jié)

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

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

另一方面,從補(bǔ)丁判定的角度,研究如何加強(qiáng)補(bǔ)丁質(zhì)量判定條件來(lái)緩解過(guò)擬合問(wèn)題.

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

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

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

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

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

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

1)原子性違背

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

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

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

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

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

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

2)數(shù)據(jù)競(jìng)爭(zhēng)

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

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

3)死鎖

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

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

4)順序違背

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

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

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

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

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

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

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

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

3.4 小 結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 其他程序規(guī)約

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

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

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

2)崩潰錯(cuò)誤和資源競(jìng)爭(zhēng)

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

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

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

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

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

4)語(yǔ)法錯(cuò)誤修復(fù)

2017年,Gupta等人[86]首次提出了Deepfix,利用深度學(xué)習(xí)技術(shù)直接生成補(bǔ)丁.這種方法的修復(fù)對(duì)象是語(yǔ)法錯(cuò)誤,將程序抽象為以語(yǔ)句為粒度的序列,利用多層次的神經(jīng)網(wǎng)絡(luò)模型來(lái)預(yù)測(cè)出錯(cuò)位置和正確的語(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,對(duì)學(xué)生的句法錯(cuò)誤修復(fù)實(shí)驗(yàn)顯示,其完全修復(fù)的準(zhǔn)確率在27%,在其他更復(fù)雜的缺陷上的表現(xiàn)尚不清楚.

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

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

6)用戶體驗(yàn)

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

4.4 小 結(jié)

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

5 總結(jié)和展望

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

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

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

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

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

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

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

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