程序自動修復:關鍵問題及技術?

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

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

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

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

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

(1)傳統維護面臨成本和維護能力不足問題

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

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

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

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

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

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

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

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

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

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

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

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

1 程序自動修復描述

1.1 相關概念

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

1.2 程序規約與程序自動修復

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

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

1)假設給定程序BP和對應的程序規約S,且BP不滿足S(即已經發現程序BP包含一個錯誤).

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

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

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

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

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

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

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

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

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

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

1.3 程序自動修復問題分類

程序自動修復的目的是對軟件開發和維護過程中出現的程序錯誤,在源代碼級別進行自動修復,圖2給出了問題分類框架.

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

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

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

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

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

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

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

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

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

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

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

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

2 不完全規約的程序修復問題及方法

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

2.1 過擬合問題分析

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

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

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

2.2 基于測試集的程序修復新進展

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

2.2.1 補丁生成

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 補丁判定

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

1)規約補全問題和方法

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

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

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

2)補丁擇優問題和方法

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

2018年,熊英飛等人[60]提出一種全新的基于測試用例執行行為相似度進行補丁擇優的方法.基于測試用例的補丁質量判定方法只關注給定測試的輸入、對應的實際輸出結果,并與預期結果比對,卻對測試用例的執行過程關注不夠.該團隊將補丁擇優問題轉化為分類問題,通過測試用例執行行為的相似度,抽象出一個模型進行分類.

· 首先觀察到兩個準則.

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

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

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

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

2.3 小 結

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

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

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

第 1類規約補全問題研究規約本身,通過直接加強程序規約S,達到增強補丁質量判定條件的目的.例如,DiffTGen通過增量生成新的測試用例來加強原有的測試集,新測試用例覆蓋原 buggy程序和打過候選補丁的程序之間存在語義差別的區域.其前提假設是,測試集的覆蓋率更高,對輸出高精度補丁有益.SemGraft引入參考程序的思想,將提取的參考程序語義替代測試集來表示待修復程序更完整的程序規約S.

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

3 完全規約的程序修復問題及方法

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

3.1 并發錯誤修復

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

1)原子性違背

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

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

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

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

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

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

2)數據競爭

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

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

3)死鎖

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

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

4)順序違背

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

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

3.2 內存泄露和資源泄露修復

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

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

3.3 性能錯誤和配置錯誤修復

2015年,針對特定性能錯誤,Adrian等人[71]提出了 CARAMEL自動檢測和修復特定性能錯誤.針對循環中當某個條件成立時,剩余的執行都是在浪費計算資源的目標研究問題,提出了針對性的修復方法.通過識別“循環+條件”并分析滿足給定的性能錯誤判定規則,然后在適當的位置插入類似“條件+break”的修復模板OP來規避性能問題,同時不影響程序原有功能.程序的完全規約S和原程序語義等價,并消除了上述性能問題.該論文獲得了ICSE 2015年的最佳論文獎.

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

3.4 小 結

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

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

4 半完全規約的程序修復問題及方法

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

4.1 契約作為程序規約

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

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

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

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

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

4.2 手工編寫程序規約

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

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

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

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

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

4.3 其他程序規約

1)測試用例的修復

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

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

2)崩潰錯誤和資源競爭

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

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

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

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

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

4)語法錯誤修復

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

5)搜索語句修復

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

6)用戶體驗

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

4.4 小 結

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

5 總結和展望

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

程序自動修復的研究領域中機遇和挑戰并存,有待更多的研究者們取得創新和突破.我們認為,該領域還存在如下值得進一步研究的問題.

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

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

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

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

統一的程序自動修復技術評價標準,測試用例和 banchmark不足依然是面臨的客觀問題.測試用例自動生成和測試用例修復相關技術為程序自動修復提供有效支撐,更大和更符合錯誤自然分布的banchmark有待進一步建立.各修復技術的橫向對比分析和統一的評價標準有待豐富,從而促進修復技術的持續發展和應用.

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