姜佳君,陳俊潔,熊英飛

1(天津大學(xué) 智能與計算學(xué)部,天津 300350)

2(北京大學(xué) 信息科學(xué)技術(shù)學(xué)院 計算機科學(xué)技術(shù)系 軟件研究所,北京 100871)

3(高可信軟件技術(shù)教育部重點實驗室(北京大學(xué)),北京 100871)

軟件缺陷(software defects)在軟件的開發(fā)過程中是不可避免的,特別是隨著現(xiàn)代信息技術(shù)的迅速發(fā)展,軟件規(guī)模在不斷增加,軟件缺陷的數(shù)量也在隨之增加.軟件缺陷會破壞程序的正常執(zhí)行,使得程序在某種程度上不能滿足其既有的功能要求.嚴重的軟件缺陷不僅會造成企業(yè)的重大經(jīng)濟損失,甚至?xí)θ藗兊纳踩斐芍卮笸{.因此,及時修復(fù)程序中的缺陷十分重要,已經(jīng)成為軟件維護中的一項重要任務(wù).對Linux 開發(fā)者的一項調(diào)查研究表明,在程序的開發(fā)過程中大約一半時間是用在了缺陷修復(fù)上[1].然而,修復(fù)程序中的缺陷不僅耗時,且容易出錯.研究表明:開發(fā)者在修復(fù)軟件缺陷時,有可能會引入新的程序缺陷[2],使得軟件缺陷的修復(fù)變得更加困難.

軟件缺陷自動修復(fù)(automatic software repair)技術(shù)有希望將開發(fā)人員從繁重的修復(fù)任務(wù)中解脫出來.從2009年開始,軟件缺陷自動修復(fù)技術(shù)成為了一個熱門的研究方向,吸引了來自軟件工程(software engineering)、程序語言(programming language)、人工智能(artificial intelligence)、形式化驗證(formal verification)等多個社區(qū)的大量研究人員.已有研究提出了一系列的軟件自動修復(fù)技術(shù),綜合使用了軟件分析(software analysis)、啟發(fā)式搜索(heuristic search)、程序綜合(program synthesis)以及機器學(xué)習(xí)(machine learning)等多種技術(shù)手段.缺陷自動修復(fù)技術(shù)根據(jù)程序中的測試或者通過靜態(tài)分析技術(shù)等獲取程序的規(guī)約(specification)信息,并基于此定位程序中出錯的代碼位置,最后采用不同的技術(shù)手段嘗試生成修復(fù)代碼使程序滿足規(guī)約要求.

在過去的10 多年中,大量的缺陷自動修復(fù)技術(shù)被提出.為了對該研究問題的進展進行系統(tǒng)地歸納總結(jié)和分析比較,本文搜集了最近10 多年(2009~2020)發(fā)表的關(guān)于缺陷自動修復(fù)的相關(guān)論文并進行了梳理.我們采用谷歌學(xué)術(shù)搜索、ACM Digital Library、IEEE Explore、Springer、Elsevier 以及CNKI 等搜索引擎和數(shù)據(jù)庫,并且使用“program/software/fault/bug/defect repair/fix”“軟件修復(fù)”和“程序修復(fù)”等關(guān)鍵字進行檢索,并要求論文發(fā)表時間自2009年至今.同時,我們結(jié)合缺陷自動修復(fù)的共享主頁(http://program-repair.org)對搜索結(jié)果進行了補充.該主頁記錄了大部分與軟件缺陷自動修復(fù)技術(shù)相關(guān)的已發(fā)表論文,涉及新的修復(fù)技術(shù)以及相關(guān)的實證研究(empirical study)等.最后,對于每一篇論文,我們通過人工篩選過濾掉無關(guān)論文以及少于5 頁的短文.最終,我們一共搜集到了186 篇程序缺陷自動修復(fù)相關(guān)的論文.

圖1 展示了從2009年~2020年每年的論文發(fā)表數(shù)量統(tǒng)計,其中包括會議論文149 篇,期刊論文37 篇.從圖中數(shù)據(jù)可以發(fā)現(xiàn),該研究領(lǐng)域論文發(fā)表數(shù)量呈逐年增加的趨勢.僅在2018年,就有36 篇相關(guān)的論文發(fā)表.該數(shù)據(jù)表明,程序缺陷自動修復(fù)領(lǐng)域的研究熱度在不斷增加.我們又進一步對論文發(fā)表的會議和期刊進行了統(tǒng)計.圖2列出了在過去10年里,不同會議和期刊上所發(fā)表的相關(guān)論文數(shù)量,其中,“others”分類包含了所有僅包含一篇論文的會議和期刊,JoS 和SCIS 分別代表期刊《軟件學(xué)報》和英文版《計算機科學(xué)》.從圖中數(shù)據(jù)可以發(fā)現(xiàn):相關(guān)論文主要發(fā)表在軟件工程領(lǐng)域的高質(zhì)量會議和期刊上,如ICSE 和TSE 等.此外,在形式化驗證(如CAV)以及編程語言(如PLDI 和POPL)等高質(zhì)量會議上也有相關(guān)論文發(fā)表.

事實上,早在2016年,武漢大學(xué)的玄躋峰教授等人[3]就已經(jīng)對軟件自動修復(fù)方法的研究進展進行了分析和總結(jié).并在此之后,先后有多篇綜述論文發(fā)表[1,2,4?6].但由于上述論文發(fā)表時間比較早,它們主要針對2017年之前的相關(guān)研究進行了詳細介紹,且大部分論文發(fā)表于2016年及之前.根據(jù)圖1 中的統(tǒng)計數(shù)據(jù)分析可以發(fā)現(xiàn),大概一半的論文在2017年~2020年間發(fā)表.在此期間,研究人員提出了一些新的方法和思路.特別地,隨著最近幾年人工智能領(lǐng)域的迅速發(fā)展,一些智能化的新技術(shù)也被應(yīng)用到缺陷修復(fù)領(lǐng)域中[7?10].因此,本文旨在對目前已有的缺陷自動修復(fù)技術(shù)進行一個更加全面的總結(jié)和分析,并對已有技術(shù)進行系統(tǒng)性分類.此外,基于目前該領(lǐng)域的研究現(xiàn)狀,本文提出該領(lǐng)域研究的可行思路以及面臨的挑戰(zhàn),為未來的研究提供指導(dǎo).

Fig.1 Distribution of publications over years圖1 不同年份論文發(fā)表分布

Fig.2 Distribution of publications in venues圖2 不同會議或期刊論文發(fā)表分布

鑒于已有綜述論文對部分相關(guān)文獻已經(jīng)有了相關(guān)介紹,本文在介紹不同類型的缺陷修復(fù)技術(shù)時將更加側(cè)重對2016年之后發(fā)表論文的介紹.但是,由于個別類型的自動修復(fù)方法主要集中在早期所發(fā)表的工作中(2016年或之前),為了使得本文內(nèi)容更加完整,以及更好地反映相關(guān)研究的發(fā)展脈絡(luò),本文中所介紹論文與已有綜述論文可能會存在少部分重疊.最終,本論文選取了94 篇軟件缺陷自動修復(fù)相關(guān)論文進行詳細介紹,其中絕大多數(shù)論文是所涉及領(lǐng)域的高質(zhì)量會議和期刊,例如ICSE 會議(21 篇)、ESEC/FSE 會議(8 篇)、POPL 會議(1 篇)、CAV 會議(1 篇)、PLDI(1 篇)、OOPSLA 會議(1 篇)、ISSTA 會議(7 篇)、ASE 會議(8 篇)、TSE 期刊(10 篇)、TOSEM 期刊(1 篇)、《軟件學(xué)報》(3 篇).

綜上所述,本文的主要貢獻總結(jié)如下.

(1)對國內(nèi)外軟件缺陷自動修復(fù)技術(shù)的最新研究進展進行了系統(tǒng)的分析和介紹;

(2)提出了基于統(tǒng)計和分析的修復(fù)技術(shù)分類,對已有的技術(shù)分類進行了補充;

(3)對當(dāng)前自動修復(fù)技術(shù)所面臨的挑戰(zhàn)進行了系統(tǒng)的梳理,并總結(jié)了未來可能的研究方向;

(4)總結(jié)了該領(lǐng)域常用的缺陷數(shù)據(jù)集以及開源工具,促進未來的研究.

本文第1 節(jié)介紹缺陷修復(fù)的研究框架并概述缺陷修復(fù)的組成模塊、修復(fù)流程以及修復(fù)工具的評價指標(biāo).第2 節(jié)對已有的基于測試或靜態(tài)分析的缺陷修復(fù)技術(shù)進行詳細介紹,并梳理和分析自動修復(fù)方法的演進方向.第3 節(jié)根據(jù)研究現(xiàn)狀的介紹總結(jié)該領(lǐng)域研究所面臨的挑戰(zhàn)及對未來研究的啟示.第4 節(jié)對自動修復(fù)常用驗證數(shù)據(jù)集以及開源修復(fù)工具進行總結(jié).最后,第5 節(jié)對全文進行總結(jié).

1 研究框架

(1)缺陷修復(fù)過程

軟件缺陷自動修復(fù)技術(shù)根據(jù)其修復(fù)的過程大致可以分為3 個模塊:缺陷定位(fault localization)、補丁生成(patch generation)、補丁排序過濾以及驗證.圖3 是目前主流缺陷修復(fù)技術(shù)的一般流程.

Fig.3 Automatic software defect repair research framework圖3 軟件缺陷自動修復(fù)技術(shù)研究框架

當(dāng)給定一個缺陷程序,修復(fù)工具:(1)首先通過靜態(tài)分析、動態(tài)測試等技術(shù)手段確定程序中可能的缺陷代碼位置;(2)然后,每次選擇一個候選出錯位置,使用補丁生成技術(shù)嘗試生成修復(fù)補丁;(3)最后驗證生成的修復(fù)補丁的正確性.基于靜態(tài)分析檢測的修復(fù)方法由分析工具預(yù)定義的規(guī)則檢查補丁是否正確,而基于動態(tài)測試的修復(fù)方法要求修復(fù)補丁可以通過所有的測試.然而,修復(fù)工具可能產(chǎn)生多個補丁修復(fù)同一個缺陷,為了提升修復(fù)的效率和補丁的質(zhì)量,通常在驗證補丁之前或之后應(yīng)用啟發(fā)式規(guī)則或統(tǒng)計分析的方法對候選的補丁進行過濾和排序.修復(fù)工具針對候選出錯位置依次迭代上述修復(fù)過程,直到找到正確的修復(fù)補丁或者達到終止條件,如運行超時等.

在上述修復(fù)過程中,缺陷定位的準確率會影響缺陷自動修復(fù)工具的修復(fù)結(jié)果.Liu 等人[11]通過實驗表明:相比于使用自動化缺陷定位方法,提供準確的代碼出錯位置使得自動修復(fù)工具TBar 多修復(fù)了31 個程序缺陷(提升了72.1%).因此,提升缺陷定位的準確率可以有效提升已有修復(fù)工具正確修復(fù)缺陷的數(shù)量.有很多相關(guān)的研究致力于提升定位的準確率,提出了各種不同的缺陷定位技術(shù).目前,在缺陷自動修復(fù)領(lǐng)域使用比較多的缺陷定位技術(shù)存在兩類:基于動態(tài)測試執(zhí)行[12?15]以及靜態(tài)程序分析的方法[16?19].基于動態(tài)測試執(zhí)行的定位技術(shù)根據(jù)程序中的未通過測試以及通過測試的動態(tài)運行時特征對代碼候選出錯位置進行排序,比如基于程序頻譜的定位技術(shù).基于靜態(tài)分析的方法通過預(yù)定義的規(guī)則描述程序的規(guī)約,然后通過程序分析技術(shù)判斷程序是否滿足給定規(guī)約.缺陷定位是一個獨立的研究領(lǐng)域,本文對其不進行詳細介紹,更多關(guān)于定位的相關(guān)技術(shù)介紹請參考最新的相關(guān)綜述論文[20].

補丁生成模塊負責(zé)生成缺陷修復(fù)代碼,是自動修復(fù)方法的核心.根據(jù)上文的介紹,定位準確率會影響修復(fù)結(jié)果.事實上,缺陷定位對修復(fù)的整體影響依然十分有限,即使給定正確的代碼出錯位置,已有的自動修復(fù)方法也僅能正確修復(fù)小部分(<20%)程序缺陷[11].因此,目前的自動修復(fù)方法所面臨的核心挑戰(zhàn)依然是如何正確高效地生成修復(fù)補丁.最新的研究也是主要針對該模塊進行優(yōu)化和創(chuàng)新.因此,本文接下來的綜述部分將根據(jù)修復(fù)工具所使用的補丁生成策略進行分類.如圖3所示,本文將缺陷修復(fù)分為4 大類,具體內(nèi)容將在第2 節(jié)進行詳細介紹.

補丁過濾排序及驗證模塊是缺陷修復(fù)過程中的最后一步,也是保證補丁質(zhì)量的關(guān)鍵一步.由于修復(fù)中使用的程序規(guī)約通常是不完備的,例如非精確的靜態(tài)分析結(jié)果或不完備的測試集(弱測試集問題[21])等.因此,即使不正確的修復(fù)補丁也有可能會通過驗證(在第3 節(jié),我們會更詳細地討論補丁的質(zhì)量問題),對候選的修復(fù)補丁進行過濾[22,23]和排序[24],成為提升補丁質(zhì)量的一個有效手段.但由于目前修復(fù)工具主要面臨的挑戰(zhàn)是難以生成正確的修復(fù)補丁,所以過濾和排序策略僅是對自動修復(fù)方法效果的進一步優(yōu)化,并不能從根本上解決生成正確補丁難的問題.

綜上,本文主要針對軟件缺陷自動修復(fù)技術(shù)中的補丁生成模塊進行詳細的綜述,對于缺陷定位以及補丁過濾排序及驗證模塊不做展開討論(本文的局限性).讀者可以參考相關(guān)的綜述論文[1?6,20]了解更詳細的內(nèi)容.

(2)修復(fù)效果評價指標(biāo)

對于自動修復(fù)工具生成的修復(fù)補丁,我們將其分為以下3 種類型:錯誤補丁(incorrect patches)、似真補丁(plausible patches)和正確補丁(incorrect patches).其中:錯誤補丁指不能通過驗證模塊驗證的補丁;似真補丁可以通過驗證,但由于改變了程序的原始語義而并非正確;正確補丁即語義正確的修復(fù)補丁.在度量缺陷自動修復(fù)工具的修復(fù)效果時,目前廣泛使用的評價指標(biāo)是召回率(recall)和準確率(precision).其定義如下:

召回率越高,反映自動修復(fù)工具的補丁生成能力越強;準確率越高,反映修復(fù)工具生成補丁的質(zhì)量越好.在實際應(yīng)用中,上述兩個指標(biāo)在某種程度上相互制約.修復(fù)的數(shù)量增加,代表修復(fù)工具有能力生成更多種類的補丁,從而導(dǎo)致生成似真補丁的可能性增大而降低準確率.因此,自動修復(fù)技術(shù)通常需要在兩者中進行權(quán)衡.例如,已有的自動修復(fù)方法通過限定修復(fù)缺陷的類型[25],降低生成似真補丁的概率,提升修復(fù)準確率.這樣的修復(fù)技術(shù)在原理上就限制了其補丁生成能力.本文在第2 節(jié)中針對具體修復(fù)技術(shù)進行相關(guān)介紹.除上述兩個通用評價指標(biāo),一些論文中也會采用上述指標(biāo)的變體,比如針對語法等價的補丁的召回率和準確率(即要求正確補丁與目標(biāo)補丁語法等價)、Top-N(正確補丁排在候選補丁中的前N位置)召回率等.

2 程序缺陷自動修復(fù)技術(shù)綜述

本節(jié)基于第1 節(jié)中介紹的缺陷自動修復(fù)研究框架,根據(jù)補丁生成階段所采用的技術(shù),對已有的修復(fù)方法進行分類.本文將已有的自動修復(fù)技術(shù)分為以下4 大類:基于啟發(fā)式搜索(例如GenProg[26?28]和SimFix[29])、基于人工修復(fù)模板(例如PAR[30]和SketchFix[31])、基于語義約束(例如Nopol[32]和Angelix[33])以及基于統(tǒng)計分析(例如DeepFix[8]和SequenceR[9])的自動修復(fù)技術(shù).需要說明的是,單一的缺陷修復(fù)方法可能同時應(yīng)用多種技術(shù).比如,SimFix 在項目中搜索相似代碼的同時也利用了從歷史修復(fù)補丁中提取的常用修改操作對補丁進行過濾.在這種情況下,我們將根據(jù)方法的主要創(chuàng)新對其進行分類.

2.1 基于啟發(fā)式搜索

(1)利用變異算子

基于啟發(fā)式搜索的自動修復(fù)技術(shù)通過人工定義啟發(fā)式規(guī)則,指導(dǎo)修復(fù)補丁的生成過程.2009年被提出來的缺陷自動修復(fù)技術(shù)GenProg[26?28]是典型的基于啟發(fā)式搜索的技術(shù),其基本思想是代碼具有重復(fù)性,因此通過復(fù)用項目中的代碼,有希望產(chǎn)生正確的修復(fù)補丁.在搜索過程中,GenProg 采用遺傳算法,通過定義代碼片段的交叉和變異操作實現(xiàn)已有代碼片段的重新組合,增大補丁的搜索空間.該方法將生成補丁所通過的測試數(shù)量作為優(yōu)化目標(biāo),對候選補丁迭代應(yīng)用交叉和變異操作,直至產(chǎn)生可以通過所有測試的補丁.通過實驗證明,該方法可以修復(fù)程序中的缺陷.該工作使得自動修復(fù)技術(shù)進入了一個新的時期,吸引了大量的科研人員開始對自動修復(fù)技術(shù)進行探索.

Qi 等人[34]在2014年提出了RSRepair,該方法采用與GenProg 方法相同的修復(fù)框架,只是將其中的遺傳算法替換成了隨機搜索.實驗對比分析表明:GenProg 中的遺傳算法并沒有發(fā)揮較大的作用,使用隨機搜索算法不僅可以正確修復(fù)同樣的缺陷,且在23 個缺陷上,隨機搜索相比遺傳算法實現(xiàn)了更高的效率.

在此之后,先后有一系列針對GenProg 進一步優(yōu)化的方法被提出.

2018年,Oliveira 等人[35]提出了一種新的代碼修改表示方法來對遺傳算法進一步優(yōu)化.原始的GenProg 方法中所采用的代碼修改表示將代碼與修改作為兩個獨立的部分,互不干擾.GenProg 每次首先從所有定義的變異算子中選擇一個,例如交叉或變異,然后根據(jù)此再去選擇候選的修復(fù)補丁或代碼片段,最后應(yīng)用對應(yīng)的變異算子產(chǎn)生新的候選補丁.Oloveira 等人提出的代碼表示方法將變異算子和算子對應(yīng)的代碼元素編碼在同一條“染色體”上.該表示方法的好處在于,變異階段可以復(fù)用之前的代碼操作.此外,通過變異“染色體”上的變異算子部分,該方法可以實現(xiàn)對同一段代碼的不同變異操作.因此,相比于傳統(tǒng)的遺傳算法,其靈活性更強,可以提升修復(fù)工具的補丁生成能力.

2018年,Yuan 等人[36]提出了基于多目標(biāo)遺傳算法的自動修復(fù)方法ARJA,該方法同樣是對遺傳算法中的表示方法進行了優(yōu)化.ARJA 將代碼補丁表示為三元組〈b,u,v〉,分別用來編碼代碼上的修改位置、修改操作類型和復(fù)用的代碼元素.該方法由于記錄了代碼的修改過程,因此具有更強的表達能力,通過變異操作可以獲得更大的補丁空間.除此之外,ARJA 將補丁生成過程轉(zhuǎn)化為多目標(biāo)優(yōu)化問題,其兩個優(yōu)化目標(biāo)分別是補丁對代碼改動的大小以及應(yīng)用補丁后程序通過測試的數(shù)量.因此,該方法傾向于修改較小的修復(fù)補丁.最后,ARJA 在補丁驗證階段通過移除與當(dāng)前補丁無關(guān)的測試以及通過編譯器分析提前排除不合法的補丁等方式提升補丁驗證的效率.最終實驗結(jié)果表明,ARJA 正確修復(fù)缺陷的數(shù)量接近GenProg 的4 倍.

與ARJA 類似,2018年,Mehne 等人[37]同樣通過篩選程序中的測試樣例對修復(fù)的過程進行加速.其具體方法為:對于給定的修復(fù)補丁,如果一個測試在運行的過程中沒有覆蓋補丁所修改的代碼位置,那么該測試在驗證該補丁時可以被過濾,即節(jié)省了部分測試運行的時間開銷.除此之外,Mehne 等人還通過過濾候選出錯位置實現(xiàn)修復(fù)加速.在程序運行時,分別搜集通過測試和未通過測試在候選出錯位置處的變量取值情況:如果變量在未通過測試運行中的取值是其在通過測試運行中取值的子集,則對應(yīng)代碼位置出錯的概率會比較小,在修復(fù)的時候可以被過濾掉.其依據(jù)為,同樣的變量取值有很大的概率觸發(fā)相同的程序錯誤.

2018年,Sun 等人[38]通過對遺傳算法的種群初始化以及變異過程進行優(yōu)化來改善原有的GenProg 修復(fù)方法.GenProg 方法在初始化最初的種群時,根據(jù)缺陷定位的結(jié)果從高到低采用貪心策略逐一嘗試.然而,由于實際中缺陷定位的結(jié)果并不一定準確,真正出錯的代碼可能排在比較靠后的位置或者是候選位置相關(guān)的代碼.在真實的工業(yè)場景下,定位的不準確會導(dǎo)致修復(fù)工具生成更多不正確的修復(fù)補丁,從而降低修復(fù)工具的實用性.針對上述問題,Sun 等人提出弱化定位結(jié)果的影響,在初始化種群時,同時考慮多處候選出錯位置,并同時生成候選補丁,以此來緩解定位不準確帶來的影響.除此之外,為了更高效地探索補丁空間,該文中方法采用了兩種交叉操作,將候選補丁根據(jù)適應(yīng)度分數(shù)分為高、低適應(yīng)度兩個集合,然后對其分別進行交叉操作,在提升高質(zhì)量補丁收斂速度的同時,可以有效探索更大的補丁空間.類似方法還有Dantas 等人[39]在2019年提出的使用語言模型中的Doc2Vec 和LSTM 模型優(yōu)化GenProg 的適應(yīng)度函數(shù),以及2020年Villanueva 等人[40]提出的使用新穎性搜索(novelty search)算法對GenProg 的搜索進行優(yōu)化,以避免陷入局部最優(yōu)解.本文不再逐一詳細介紹.

上述方法主要針對GenProg 方法在算法上的一些優(yōu)化,實際上對其補丁生成空間影響不大,依然是復(fù)用項目中已有代碼片段.2019年,Yuan 等人[41,42]針對GenProg 的補丁空間進行了擴充,將GenProg 和PAR[30](基于人工模板的補丁生成方法,將在第2.2 節(jié)詳細介紹)方法結(jié)合提出了ARJA-e.根據(jù)上面的介紹我們知道,GenProg 是直接復(fù)用項目中已有的代碼來生成補丁.在此基礎(chǔ)之上,ARJA-e 借用PAR方法的修復(fù)補丁模板再額外產(chǎn)生一些新的代碼片段加入到遺傳算法的候選補丁集合中,與其原有的補丁一起進行變異和遺傳.除此之外,ARJA-e 對GenProg 的適應(yīng)度函數(shù)(fitness function)進行了優(yōu)化.根據(jù)上面的介紹,GenProg 將通過測試的個數(shù)作為補丁的適應(yīng)度值.然而實際上,單個測試函數(shù)中可能存在多條斷言(assertion),任何一條斷言的失敗都會導(dǎo)致整個測試函數(shù)的失敗.ARJA-e 針對該情況進行了細化處理,將以測試為單位修改為以斷言為單位,根據(jù)補丁通過斷言的數(shù)量評價補丁的適應(yīng)度.在Defects4J 數(shù)據(jù)集[43]上的實驗驗證表明:ARJA-e 相比GenProg 正確修復(fù)數(shù)量有了明顯提升,大概是后者的4 倍.

2019年,Ghanbari 等人[44]提出了基于JVM 字節(jié)碼(bytecode)的缺陷修復(fù)技術(shù)PraPR.在此之前的自動修復(fù)技術(shù)主要針對源代碼.上述所介紹的基于變異的技術(shù)均通過定義源碼上的變異算子生成修復(fù)補丁.與字節(jié)碼相比,源碼級別的修復(fù)存在結(jié)構(gòu)復(fù)雜、反復(fù)編譯耗時等缺點.字節(jié)碼級別的修復(fù)可以有效克服上述缺點.類似遺傳算法,PraPR 根據(jù)預(yù)先定義好的字節(jié)碼上的遺傳算子對缺陷代碼進行修改.由于字節(jié)碼中的結(jié)構(gòu)種類有限且簡單,因此變異算子所能覆蓋到的補丁空間會更大.但是由于對字節(jié)碼修改不需要二次編譯,可以直接在JVM 上運行,所以其效率會比較高.實際驗證效果也表明,該方法相比已有的技術(shù)具有更高的效率.該方法因為不涉及到源代碼的結(jié)構(gòu),也因此具有更強的通用性,可以修復(fù)任何中間代碼為JVM 字節(jié)碼的編程語言程序,例如Java,Kotlin,Scala 等.然而PraPR 也存在其固有的缺點,字節(jié)碼簡單的同時也伴隨著部分程序語義信息的丟失,例如變量名稱等,使得基于源碼字面語義的啟發(fā)式方法不適用于對PraPR 的進一步優(yōu)化.

(2)利用歷史修復(fù)補丁

與上述基于遺傳算法的缺陷修復(fù)不同,Le 等人[45]認為:在不同的應(yīng)用軟件中,軟件缺陷會重復(fù)出現(xiàn),之前的缺陷修復(fù)歷史可以為修復(fù)補丁提供有效的指導(dǎo).因此,引入了第三方數(shù)據(jù)源(即歷史修復(fù))對GenProg 進行優(yōu)化.基于該思想,作者在2016年提出一個新的缺陷修復(fù)技術(shù)HistoricalFix.該方法同樣采用了遺傳算法來生成修復(fù)補丁,不同的是,HistoricalFix 僅僅采用變異(mutation)而不使用交叉(crossover)操作.在每次變異之后,計算候選補丁所涉及的修改操作,根據(jù)其他項目歷史修復(fù)中常用的代碼修改對補丁進行篩選.該方法相比之前的遺傳算法引入了第三方的缺陷修復(fù)歷史數(shù)據(jù),對補丁的生成起到了更好的指導(dǎo)作用.最終的實驗證明,該方法相比原始的GenProg 方法有了非常大的效果提升.在Defects4J 數(shù)據(jù)集中的90 個缺陷上進行驗證,GenProg 只能正確修復(fù)1 個缺陷,而HistoricalFix 可以正確修復(fù)23 個.該實驗表明,歷史修復(fù)數(shù)據(jù)可以為補丁生成提供有效指導(dǎo).

與HistoricalFix 類似,2018年,Wen 等人[46]同樣應(yīng)用從歷史修復(fù)中挖掘的代碼修改操作指導(dǎo)補丁生成,其不同點在于考慮了代碼修改的上下文信息,從而可以提供更加準確的指導(dǎo),有效約束補丁的搜索空間.基于該方法,作者實現(xiàn)了一個自動修復(fù)工具CapGen.在歷史修復(fù)提取階段,Wen 等人通過記錄被修改代碼節(jié)點的父節(jié)點類型信息作為修改應(yīng)用的前置條件,例如:“insert EXPR_STMT under METH_DECL”表明,插入的“EXPR_STMT”應(yīng)該是“METH_DECL”的子節(jié)點.因此,根據(jù)該規(guī)則,CapGen 不能在循環(huán)語句“FOR_STMT”中插入“EXPR_STMT”.類似的代碼修改操作限定了特定修改操作的應(yīng)用范圍.除此之外,CapGen 在復(fù)用項目中已有代碼生成補丁時,會統(tǒng)計不同代碼表達式在項目中出現(xiàn)的頻繁程度并進行排序,被頻繁使用的表達式具有更高的優(yōu)先級.上述的補丁空間約束方法和代碼復(fù)用策略有效地提升了補丁的質(zhì)量.在Defects4J 數(shù)據(jù)集上的實驗表明,該方法可以達到84%的補丁準確率.但由于其對補丁空間的約束,導(dǎo)致其修復(fù)的數(shù)量并不多.

HistoricalFix 和CapGen 方法應(yīng)用歷史修改為補丁搜索提供指導(dǎo).2019年,Kim 等人[47]提出直接應(yīng)用歷史中人工修復(fù)的模板,并開發(fā)了自動修復(fù)工具ConFix.該工具從人工修復(fù)中直接提取代碼修改操作.ConFix 在代碼的抽象語法樹(abstract syntax tree)上,根據(jù)修改代碼的位置提取相關(guān)的上下文信息作為應(yīng)用對應(yīng)人工修復(fù)的條件,即僅當(dāng)出錯代碼正確匹配上下文才可以應(yīng)用對應(yīng)的代碼修改.ConFix 根據(jù)語法樹的結(jié)構(gòu)提取語法樹中被修改節(jié)點的相鄰節(jié)點作為上下文,例如父節(jié)點、左右鄰節(jié)點等.實驗結(jié)果表明,使用上下文信息平均可以減少48%的不必要代碼修改.

(3)利用相似代碼

上述技術(shù)主要針對補丁的搜索策略和代碼的修改進行優(yōu)化,還有一部分最新研究關(guān)注于優(yōu)化補丁生成過程中所使用的代碼元素.上述介紹的方法在復(fù)用項目中已有的代碼時,僅考慮代碼出現(xiàn)的頻繁程度(例如CapGen),甚至完全不考慮代碼的特征,并且均沒有考慮缺陷代碼與復(fù)用代碼之間的聯(lián)系.針對于此,2016年,Ji 等人[48]提出通過復(fù)用項目中與缺陷位置相似的代碼片段生成補丁,并實現(xiàn)了缺陷修復(fù)工具SCRepair.作者認為,與缺陷代碼過于相似的代碼可能存在同樣的錯誤.因此,SCRepair 在復(fù)用相似代碼作為修復(fù)參考時考慮了代碼之間需要具有差異性.SCRepair 通過對比缺陷代碼與參考代碼之間的語法樹結(jié)構(gòu)的一致性衡量代碼相似性,使用ChangeDistiller[49]提取缺陷代碼到參考代碼的修改操作衡量代碼之前的差異性.根據(jù)預(yù)設(shè)的相似性和差異性閾值對復(fù)用的參考代碼進行過濾.SCRepair 與RSRepair 相似,差別在于SCRepair 在復(fù)用代碼時考慮上述過濾條件,而RSRepair 采用無過濾的隨機搜索.

2017年,Wang 等人[50]同樣基于復(fù)用相似代碼的基本思想,提出了修復(fù)工具CRSearcher.與SCRepair 不同的是,CRSearcher 將代碼的搜索范圍擴展到了其他的項目,應(yīng)用基于標(biāo)識(token-based)的代碼相似度衡量方法,并且不要求相似代碼與缺陷代碼一定具有差異性.CRSearcher 并不算一個完整的自動修復(fù)工具,它不包含補丁驗證模塊,而是針對FindBugs 檢測出的缺陷為開發(fā)者推薦修復(fù),需要人工確認補丁的正確性.

與上述方法類似,Xin 等人[51]在2017年提出的修復(fù)方法ssFix 同樣從代碼庫中搜索與缺陷代碼相似的代碼作為修復(fù)補丁的原材料.ssFix 采用阿帕奇公司(Apache)的Lucene 作為代碼搜索引擎.在生成補丁階段,ssFix 并不是直接復(fù)用相似代碼,而是通過ChangeDistiller 提取缺陷代碼與相似代碼之間的差異,根據(jù)其中的不同點逐一應(yīng)用修改操作.相比上述復(fù)用技術(shù),ssFix 的代碼復(fù)用粒度更細,有效地提升了其補丁生成能力.在Defects4J 數(shù)據(jù)集上的實驗表明,ssFix 可以正確修復(fù)20 個缺陷.但是由于其細粒度的代碼修改、補丁空間增大導(dǎo)致補丁的準確率比較低,產(chǎn)生了兩倍數(shù)量的似真補丁.

Jiang 等人[29]認為,同一個項目中的代碼具有更好的參考價值.同一個項目中的代碼通常由同一個開發(fā)者或同一開發(fā)團隊所編寫,對于相似功能的代碼模塊,代碼風(fēng)格(例如程序結(jié)構(gòu)和變量名等)具有較高的相似性.基于該思想,在2018年,他們提出了自動修復(fù)工具SimFix,通過代碼結(jié)構(gòu)特征以及代碼語義特征(變量和函數(shù)命名)搜索項目中的相似代碼.在應(yīng)用相似代碼階段,SimFix 同樣采用基于差異的代碼修改策略,即通過對比缺陷代碼與相似代碼之間的差異提取細粒度的代碼修改操作.在復(fù)用代碼階段,會替換相似代碼中的變量使其在缺陷代碼位置語法正確.與ssFix 不同,SimFix 所提取出的代碼修改操作可以進行組合應(yīng)用,并且同時使用歷史修復(fù)中的常用修改操作對候選補丁進行過濾優(yōu)化.相似代碼和歷史修改對SimFix 的補丁空間提供了很好的約束,使其在最終的實驗驗證中不僅正確修復(fù)了更多數(shù)量的缺陷,其修復(fù)的準確率相比ssFix 也提升了將近一倍.

基于類似的思想,2019年,Hu 等人[52]提出了根據(jù)正確的代碼為學(xué)生提交的作業(yè)代碼推薦修復(fù)補丁,并實現(xiàn)了修復(fù)工具Refactory.該方法首先將學(xué)生提交的正確代碼作為代碼庫,通過預(yù)定義變換規(guī)則對其進行重構(gòu)使代碼結(jié)構(gòu)一致.當(dāng)學(xué)生提交的代碼不能通過測試驗證時,Refactory 通過將其與代碼庫中的正確代碼進行匹配定位缺陷代碼可能出錯位置,然后依賴測試在正確代碼上的運行結(jié)果推斷代碼規(guī)約,最后基于該規(guī)約為缺陷代碼生成修復(fù)代碼骨架(sketch),并通過枚舉所有的可能填充代碼骨架產(chǎn)生修復(fù)代碼.該方法與上述方法的不同在于其中包含了代碼重構(gòu)部分,使得語義相近的代碼盡可能在結(jié)構(gòu)上相似,方便之后的代碼匹配.但其應(yīng)用的場景是針對學(xué)生提交的作業(yè),要求相同功能的代碼存在不同的實現(xiàn).在工業(yè)開發(fā)環(huán)境中,相同功能代碼并不一定總是存在,使得其應(yīng)用范圍受到了一定限制.

(4)本節(jié)小結(jié)

基于啟發(fā)式搜索的自動修復(fù)方法是到目前為止研究最為廣泛的一類方法.該類方法的優(yōu)點是具有較強的通用性,適用于不同種類的程序缺陷.然而,其缺點是容易產(chǎn)生似真補丁而降低補丁的準確率.因此,其核心是如何定義合適的補丁搜索空間以提升補丁的質(zhì)量.如前所述,修復(fù)方法的召回率和準確率是兩個相互制約的指標(biāo),在保證準確率達到一定指標(biāo)要求的情況下提升自動方法的修復(fù)數(shù)量,是搜索空間定義的重大挑戰(zhàn).

2.2 基于人工修復(fù)模板

(1)利用模板生成補丁

基于人工模板的補丁生成,指根據(jù)開發(fā)者或研究人員的經(jīng)驗預(yù)定義一些補丁模板或者補丁生成策略用于指導(dǎo)修復(fù)的過程,2013年被提出來的PAR[30]是其中的代表性研究.通過分析人工修復(fù)補丁的特征,Kim 等人為PAR 人工定義了10 個修復(fù)模板,涵蓋6 大類的代碼修改,例如替換函數(shù)的參數(shù)、替換變量初始化等.PAR 中包含了每個修復(fù)模板的實現(xiàn)邏輯,當(dāng)給定一個缺陷代碼位置,PAR 按照一定的順序逐一實例化預(yù)定義的修復(fù)模板產(chǎn)生修復(fù)補丁.由于補丁生成的模板由人工定義和編寫,生成補丁的質(zhì)量相比隨機產(chǎn)生會有較大提升.對開發(fā)者的調(diào)查問卷表明,PAR 產(chǎn)生的補丁具有較好的可讀性.在此之后,2019年,Koyuncu 等人[53]將PAR 定義的修復(fù)模板用來修復(fù)缺陷報告中的缺陷,并提出了修復(fù)工具iFixR.然而,該方法的缺點也是比較明顯的.人工定義模板負擔(dān)重且難以覆蓋所有類型的程序缺陷,適合于分布較廣泛的特定類型缺陷.比如,2019年,Marginean 等人[54]提出的修復(fù)工具SapFix 主要針對面向?qū)ο笳Z言中的空指針缺陷等.

2017年,Tian 等人[55]提出了一種針對C 語言錯誤的自動修復(fù)方法ErrDoc,該方法主要針對靜態(tài)分析工具檢測出來的不正確條件檢查(error check)和資源釋放(resource release)以及值的錯誤傳播(error propagation)和輸出錯誤(error output)這4 種常見錯誤進行修復(fù).類似地,ErrDoc 針對每種特定的缺陷定義了對應(yīng)的修復(fù)模板.當(dāng)檢測到對應(yīng)的程序缺陷時,即應(yīng)用對應(yīng)的修復(fù)模板.例如,函數(shù)的返回值出錯的一種修復(fù)模板,是直接將返回值替換成為對應(yīng)的期望值.相比于PAR 以及SapFix,該方法的主要不同點在于:通過靜態(tài)分析在程序的控制流圖上檢測出錯路徑和未出錯路徑,通過對比差異為修復(fù)提供指導(dǎo).

類似ErrDoc,很多基于模板的自動修復(fù)技術(shù)主要是針對一些特定類型的缺陷.原因是缺陷的修復(fù)方式相對比較固定,數(shù)量有限,方便人工定義.比如:早在2016年,Gao 等人[56]通過定義3 種修復(fù)模板來修復(fù)緩沖區(qū)溢出(buffer overflow)缺陷,實現(xiàn)了修復(fù)工具BovInspector;Gao 等人[57]和Yan 等人[58]分別在2013年和2016年提出了LeakFix 和AutoFix,通過預(yù)定義的修復(fù)模板(插入free 語句),借助靜態(tài)分析技術(shù)修復(fù)內(nèi)存泄漏缺陷;再比如:2019年,Xu 等人[59]通過添加空指針檢查等模板,修復(fù)靜態(tài)分析技術(shù)檢測出來的空指針異常錯誤.

2018年,Liu 等人[60]首先使用代碼修改提取工具GumTree[61]從Stack Overflow 上的缺陷代碼修復(fù)中提取代碼修改操作,然后由人工總結(jié)成修復(fù)模板.該方法相比上述定義模板的好處在于:一些常用的變量或常量在問答網(wǎng)站上可能經(jīng)常出現(xiàn),這些數(shù)據(jù)可以包含到修復(fù)模板中,在生成修復(fù)補丁時可以起輔助作用.與此類似,Tan 等人[62]通過分析安卓(Android)應(yīng)用軟件崩潰的常見原因,總結(jié)了8 個修復(fù)模板并用于自動化修復(fù)安卓缺陷.

2018年,Hua 等人[31]提出了基于模板的自動修復(fù)技術(shù)SketchFix,該方法主要關(guān)注的是缺陷修復(fù)技術(shù)中的效率問題.根據(jù)之前的介紹,通常情況下補丁生成是一個不斷迭代過程,每次生成新的修復(fù)補丁都需要對程序進行重新編譯.因此,修復(fù)的一部分時間開銷在于重復(fù)編譯.SketchFix 使用輔助函數(shù)替換待修復(fù)的代碼,輔助函數(shù)內(nèi)部的具體實現(xiàn)根據(jù)預(yù)定義的補丁模板生成.這樣做的好處是:程序只需要編譯一次即可,修復(fù)過程每次只修改輔助函數(shù)內(nèi)的代碼,因此只有非常有限的代碼需要每次更新編譯,從而避免了由于編譯整個項目所帶來的時間開銷,可以有效提升修復(fù)的效率.與SketchFix 類似,2017年,Durieux 等人[63]提出了NPEfix,通過元編程避免不同補丁代碼的重復(fù)編譯.與此不同,2018年,Mechtaev 等人[64]從測試的角度出發(fā)來提升修復(fù)的效率,并實現(xiàn)了修復(fù)工具F1X.該工具同樣適用預(yù)定義模板生成修復(fù)補丁,其主要的貢獻在于:通過將修復(fù)補丁根據(jù)語義等價歸類來避免具有相同語義的修復(fù)補丁被重復(fù)驗證,最終實現(xiàn)提升修復(fù)效率的目的.

2019年,Saha 等人[65]將基于模板的補丁生成技術(shù)擴展到了多位置修復(fù),并實現(xiàn)了修復(fù)工具HERCULES.其基本思想是:具有相似特征(如代碼結(jié)構(gòu)、變量命名等)的代碼片段,以及在代碼的歷史修改中經(jīng)常同時演化的代碼片段有較大的概率需要協(xié)同的修復(fù).因此,HERCULES 通過分析當(dāng)前代碼中與候選出錯代碼相似的代碼片段以及與候選出錯代碼存在共同演化的代碼片段擴展缺陷修復(fù)的位置.在該過程中,HERCULES 根據(jù)可達定義分析(reaching-definition analysis)對不同代碼之間的關(guān)聯(lián)性進一步分析,從而過濾掉不相關(guān)的代碼.最后,在多個位置同時應(yīng)用預(yù)定義的修復(fù)模板生成補丁.該方法在一定程度上擴展了之前方法僅針對單個代碼位置的修復(fù),但由于其對修復(fù)的多處位置具有上述限制,因此其實際上并不能修復(fù)所有類型的多位置缺陷.

基于模板的修復(fù)技術(shù),由于其模板通常由人工定義,產(chǎn)生的補丁質(zhì)量相比隨機搜索的方法有所提升.但正因如此,該類方法的修復(fù)能力和應(yīng)用范圍由其定義的模板數(shù)量直接決定.2019年,Liu 等人[11]通過分析已有的基于模板的修復(fù)技術(shù),實現(xiàn)了一個新的修復(fù)工具TBar.TBar 集成了已有方法中大部分的補丁模板,在實驗驗證中實現(xiàn)了更多正確的修復(fù).然而,通過人工定義的方法畢竟受模板數(shù)量限制,難以大規(guī)模使用.因此,研究如何自動化地提取修復(fù)模板,是使自動修復(fù)技術(shù)走向?qū)嵱没囊粋€有效途徑.我們在第2.4 節(jié)將介紹相關(guān)研究.

(2)利用補丁模板優(yōu)化候選補丁

與PAR 相反,2016年,Tan 等人[66]通過分析修復(fù)工具GenProg 和SPR[67]所產(chǎn)生的修復(fù)補丁發(fā)現(xiàn),自動修復(fù)工具產(chǎn)生的大部分不正確補丁具有公共的特點:刪除了程序中的部分代碼語句.基于上述發(fā)現(xiàn),作者提出了反模式(anti-pattern)方法.該方法在已有的自動修復(fù)工具基礎(chǔ)之上定義了一系列規(guī)則對工具產(chǎn)生的補丁進行過濾,比如不能刪除返回語句(return)、不能刪除條件語句(if)等.作者基于GenProg 和SPR 自動修復(fù)工具實驗,對其增加了上述補丁過濾條件.實驗結(jié)果表明,上述過濾規(guī)則可以有效避免不正確的修復(fù)補丁.此外,該方法由于刪除了部分候選補丁,補丁驗證時間減少,修復(fù)的效率平均提升了1.4 倍.但相比原始方法,過濾規(guī)則并沒有使修復(fù)工具產(chǎn)生新的修復(fù)補丁,修復(fù)工具的召回率依然由其自身所決定,反模式只是在一定程度上提升了補丁的準確率.

2018年,Soto 等人[68]通過分析已有的修復(fù)補丁,提取比較常用的修復(fù)模板,然后將其與PAR 定義的模板一起用于優(yōu)化GenProg 方法的補丁生成過程.在GenProg 迭代生成候選補丁過程中,使用上述定義的修復(fù)模板對補丁進行排序.與上述的反模式類似,由于該方法中定義的補丁作為輔助而非直接用于生成補丁,因此最后實驗效果提升并不明顯.

(3)本節(jié)小結(jié)

基于人工修復(fù)模板的方法較大可能地應(yīng)用了開發(fā)者或研究者的領(lǐng)域知識.修復(fù)模板因具有較強的目標(biāo)性,即修復(fù)特定類型的缺陷,因此其優(yōu)點是生成的補丁質(zhì)量較高,不會產(chǎn)生晦澀難懂的代碼修改.然而,其缺點也很明顯.由于依賴人工定義修復(fù)模板,模板的種類受開發(fā)者經(jīng)驗限制,人工成本大.所以,該類方法主要針對一些比較常見的、特征比較明顯的缺陷類型,比如空指針缺陷等.

2.3 基于語義約束

(1)基于組件的補丁綜合

基于語義約束的自動修復(fù)方法通過某種手段推斷程序的正確規(guī)約,作為約束指導(dǎo)補丁的生成過程或?qū)ρa丁的正確性進行驗證.比較有代表性的研究工作是新加坡國立大學(xué)Roychoudhury 教授團隊在2013年和2015年先后提出來的自動修復(fù)工具SemFix[69]和DirectFix[70],這兩種方法均通過符號執(zhí)行技術(shù)在缺陷代碼位置搜集使測試通過的程序語義約束信息,然后使用基于組件(component-based)的程序合成方法生成修復(fù)補丁.該過程需要依賴約束求解器(SMT solver)求解.DirectFix 相比于前者對補丁生成過程進行了優(yōu)化:DirectFix 不嚴格按照定位的結(jié)果,而是優(yōu)先選擇比較簡單的候選語句進行修復(fù);其次,DirectFix 將補丁生成問題轉(zhuǎn)換為部分最大可滿足問題(partial MaxSAT),通過將補丁的復(fù)雜度(即對原始代碼的修改大小)作為軟約束(soft condition)來控制pMaxSMT 求解器,生成更簡單的修復(fù)補丁.

2016年,D’Antoni 等人[71]認為,已有方法僅僅通過代碼的語法變化來衡量補丁的復(fù)雜度來對補丁進行排序并不是有效的手段,進而提出一種基于代碼結(jié)構(gòu)和語義特征的補丁排序方法Qlose.與DirectFix 類似,在語法層面,Qlose 通過對比修改前后代碼的語法結(jié)構(gòu)差異作為補丁的語法復(fù)雜度,例如修改表達式的個數(shù)等.修改數(shù)量越少,表示補丁越簡單.在語義層面,Qlose 針對給定的測試集計算語義差異.其具體做法是:對比通過的測試在修復(fù)前后程序上執(zhí)行的路徑,并計算路徑的漢明距離(Hamming distance)來衡量補丁的復(fù)雜度.漢明距離越小,表示補丁越簡單.最后,將上述兩方面約束作為約束求解器的軟約束求解可行修復(fù)補丁.該方法在一定程度上提升了補丁的質(zhì)量.

Mechtaev 等人[33]在2016年提出了針對SemFix 和DirectFix 的優(yōu)化方法Angelix,該方法同樣采用基于組件的程序合成方法,通過使用受控的符號執(zhí)行技術(shù)使其具有更好的延展性(scalability),可以用于修復(fù)較大規(guī)模項目中的缺陷.此外,Angelix 采用增量的方式生成補丁,即首先根據(jù)部分測試生成修復(fù)補丁,然后做回歸測試,將不能通過的測試再添加到用于生成補丁的測試集中,如此遞歸生成補丁.這樣的方法可以有效簡化程序的約束,將約束求解器的部分負擔(dān)轉(zhuǎn)移到運行測試驗證,在一定程度上可以提升修復(fù)效率.Angelix 相比之前的工作可以修復(fù)程序中的多處錯誤.

2016年,Rothenberg 等人[72]針對符號執(zhí)行難以處理程序中的循環(huán)問題(搜索空間爆炸),提出了AllRepair 方法.該方法通過指定循環(huán)展開次數(shù)和遞歸深度將代碼轉(zhuǎn)換為無循環(huán)代碼,這樣可以將代碼轉(zhuǎn)換為靜態(tài)單賦值(static single assignment)形式,進而可以直接轉(zhuǎn)換為SMT 的約束.AllRepair 為了產(chǎn)生簡單的修復(fù)補丁,當(dāng)發(fā)現(xiàn)一個修改序列可以通過測試,會將其所有的超集排除.該方法相比之前的方法主要的貢獻是使用循環(huán)展開近似原程序,其優(yōu)點是可以處理循環(huán),缺點是得到的修復(fù)補丁并不能保證通過測試,需要執(zhí)行測試進一步驗證.

2016年,Xuan 等人[32]提出一種針對Java 程序中條件語句錯誤的修復(fù)技術(shù)Nopol,該技術(shù)針對出錯語句的類型定義了不同修復(fù)策略:如果定位出錯的代碼位置是條件語句,則Nopol 通常生成的修復(fù)補丁為修改原始的條件語句;如果定位出錯的代碼位置是非條件語句,則通過添加一個新的條件跳過當(dāng)前語句的執(zhí)行實現(xiàn)修復(fù).在針對特定類型的缺陷生成修復(fù)補丁時,Nopol 首先在出錯的代碼位置搜集所有變量的取值情況,然后根據(jù)期望的條件語句取值情況(true 或false),將程序語義編碼成為Z3[73]約束求解器的約束進行求解.在Nopol 方法中,除了程序中的變量可以用于生成修復(fù)補丁,同時編碼了一些常量(例如0,?1 等)以及常用函數(shù)調(diào)用(如size(?),length(?)等)用于支持補丁生成.該方法相比上述基于約束求解器的方法,由于僅針對條件語句(只有true 和false 兩種取值)錯誤,不需要依賴符號執(zhí)行搜集程序的約束信息,因此其在大項目上的可延展性會更好.缺點是只修復(fù)條件語句缺陷.

2017年,Chen 等人[74,75]提出一種基于程序契約(contract-based)的缺陷修復(fù)技術(shù)JAID.該方法基于程序狀態(tài)抽象技術(shù),通過監(jiān)視并記錄測試運行過程中不同程序位置的可使用表達式取值情況,同時結(jié)合測試執(zhí)行的結(jié)果定位程序中的可疑缺陷位置,最后通過預(yù)定義模板生成修復(fù)的補丁.在修復(fù)過程中,JAID 同時結(jié)合了函數(shù)的純度分析(purity analysis)等軟件分析技術(shù)指導(dǎo)補丁生成.該方法中的核心是,根據(jù)程序運行過程中的表達式取值來推斷程序的規(guī)約以確定出錯位置.因此,本文將其歸為基于語義約束的修復(fù)技術(shù).

實際上,上述介紹的使用約束求解器的方法輔助生成修復(fù)補丁的核心是搜集程序中的約束并轉(zhuǎn)化為約束求解問題.2017年,Nguyen 等人[76]將缺陷修復(fù)轉(zhuǎn)換為程序的可達性問題進行求解,其本質(zhì)和上述技術(shù)類似,只是將測試執(zhí)行的約束映射為程序中的未知條件語句,然后可以使用可達性問題的求解方法進行計算.該方法被證明得到的結(jié)果一定是正確的(sound),但不能保證完備性(completeness).

2017年,Le 等人[77]提出了缺陷自動修復(fù)技術(shù)S3,同時考慮程序的語法和語義特征指導(dǎo)補丁的生成過程.與之前介紹的基于約束求解的方法類似,S3 通過符號執(zhí)行搜集測試的約束信息作為約束求解器的輸入;不同的是,S3 為不同的代碼修改操作預(yù)定義了優(yōu)先次序,在約束求解的過程中,會根據(jù)該排序優(yōu)化補丁的生成過程.類似地,最后,S3 通過對比修改之后的代碼與修改之前代碼的語法以及語義的相似程度對補丁進行排序,例如代碼修改的大小、修改前后同一表達式的取值情況等,相似程度高的補丁排序優(yōu)先.

2018年,Mechtaev 等人[78]在Angelix 的基礎(chǔ)之上進一步優(yōu)化并提出了SemGraft 修復(fù)工具.SemGraft 在以下兩方面進行了優(yōu)化:首先,Angelix 依賴測試驗證生成補丁的正確性容易產(chǎn)生似真補丁,SemGraft 借助于相似功能的正確代碼作為引用來推導(dǎo)缺陷程序的規(guī)約,輔助補丁的驗證,提升補丁的質(zhì)量;其次,SemGraft 結(jié)合了基于反例的程序綜合技術(shù),當(dāng)程序綜合器生成的修復(fù)補丁不能滿足約束時,將反例返回給綜合器用于優(yōu)化下一次的搜索.該方法通過上述兩方面優(yōu)化可以有效提升補丁的質(zhì)量,但由于其依賴于存在相同功能的其他代碼實現(xiàn)作為參考,其應(yīng)用場景受到較大的制約.

2018年,Lee 等人[79]提出了MemFix,修復(fù)C 語言中的內(nèi)存釋放錯誤.MemFix 通過類型狀態(tài)靜態(tài)分析(typestate static analysis)技術(shù)獲取程序中每個位置處所有可以被訪問的內(nèi)存對象的狀態(tài),該狀態(tài)可以通過〈o,must,mustNot,patch,patchNot〉來表示,其中,o表示特定內(nèi)存對象的編號或內(nèi)存地址,must指在當(dāng)前位置一定指向內(nèi)存位置o的指針集合,mustNot指在當(dāng)前位置一定不指向內(nèi)存位置o的指針集合,patch指在當(dāng)前位置的安全修復(fù)集合,而patchNot指在當(dāng)前位置不一定安全的修復(fù)集合.patch和patchNot中的每個修復(fù)是一個二元組(n,e),表示在第n行插入free(e)語句.根據(jù)程序的執(zhí)行流,動態(tài)更新程序的每個位置狀態(tài)信息.最后,在程序的出口處可以得到所有的內(nèi)存狀態(tài)信息,將其轉(zhuǎn)化為覆蓋問題,即:尋找一個最小覆蓋,通過插入free(?)語句,使得所有內(nèi)存狀態(tài)最終均得以被釋放,且不存在重復(fù)釋放(double-free).該求解過程屬于優(yōu)化問題,依賴于約束求解器進行求解.

(2)基于語義的代碼搜索和復(fù)用

上述介紹的補丁生成方法通過重新組合項目中的已有代碼片段生成修復(fù)補丁.近期的一些研究通過編碼程序的語義信息,搜索可以直接復(fù)用的代碼片段用于生成補丁代碼.與MemFix 類似,2018年,van Tonder 和Le Goues[80]提出了FootPatch,針對Java 語言的資源泄漏、內(nèi)存溢出和空指針引用等缺陷.在該方法中,FootPatch將程序的語義約束信息用分離邏輯(saparation logic)描述作為程序的規(guī)約.在最后的補丁生成階段,FootPatch 在項目中搜索滿足上述規(guī)約的代碼段,直接復(fù)用其作為正確修復(fù)補丁.

2017年,Ke 等人[81]提出了基于代碼語義搜索的修復(fù)技術(shù)SearchRepair,該方法首先建立了一個代碼片段數(shù)據(jù)庫.與之前方法類似,對于缺陷代碼,SearchRepair 首先使用符號執(zhí)行技術(shù)搜集滿足程序測試的規(guī)約,然后在代碼庫中搜索滿足對應(yīng)程序規(guī)約的代碼段.在搜索的過程中,SearchRepair 利用約束求解器求解代碼段中變量與出錯代碼中的變量映射關(guān)系.當(dāng)找到滿足要求的代碼段,則可以根據(jù)約束求解結(jié)果,使用缺陷代碼中的變量替換搜索得到代碼段中的變量,然后直接替換缺陷位置代碼即可.上述方法一方面涉及到符號執(zhí)行在大項目上延展性差的問題,另一方面,搜索代碼庫過程需要頻繁的約束求解導(dǎo)致其效率比較低.目前,SearchRepair 將代碼段的粒度規(guī)定為1~5 行代碼.如果降低代碼段的粒度,例如表達式級別,其修復(fù)效率將難以接受.

2019年,Afzal 等人[82]針對SearchRepair 存在的表達力與效率等問題,提出了改進方法SOSRepair.該方法采用了一種新的代碼編碼方式來存儲代碼,以加速在修復(fù)過程中代碼的搜索過程.SOSRepair 在代碼庫的建立階段記錄每個代碼段中使用的變量名和變量類型信息,同時通過符號執(zhí)行搜索程序所有的可能執(zhí)行路徑并編碼成為約束.在代碼搜索階段,可以根據(jù)變量類型以及代碼段的約束驗證其是否滿足所有測試的輸入輸出約束.除此之外,SOSRepair 對復(fù)雜的代碼結(jié)構(gòu)有了更強的兼容性,例如結(jié)構(gòu)體、循環(huán)以及庫函數(shù)等.不僅如此,為了提升代碼搜索效率,SOSRepair 會根據(jù)不同變量位置指導(dǎo)變量的映射過程(輸入變量映射輸入變量),避免約束求解枚舉所有可能的映射關(guān)系.最后,SOSRepair 通過使用反例制導(dǎo)的程序規(guī)約推斷方法降低了對測試的要求,即使只有未通過測試覆蓋修復(fù)代碼,該方法也可以根據(jù)未通過測試推導(dǎo)程序的規(guī)約,并在驗證補丁失敗時動態(tài)更新規(guī)約指導(dǎo)之后的補丁搜索過程.

(3)本節(jié)小結(jié)

基于語義約束的修復(fù)技術(shù)通過將補丁生成過程轉(zhuǎn)換成約束求解問題,可以充分利用已有的優(yōu)化求解算法,避免反復(fù)執(zhí)行測試來驗證候選補丁的正確性.但是該類方法由于依賴于符號執(zhí)行和約束求解技術(shù),在比較復(fù)雜的大規(guī)模程序上難以適用.此外,基于組件的補丁綜合方法容易產(chǎn)生過擬合以及可閱讀性差的代碼片段,從而降低代碼可維護性.雖然最新的研究通過復(fù)用已有代碼可以在一定程度上提升補丁的可讀性,但大量的求解過程會導(dǎo)致修復(fù)過程的低效,限制了可復(fù)用代碼片段的粒度,進而約束了修復(fù)方法所能修復(fù)的缺陷數(shù)量.

2.4 基于統(tǒng)計分析

(1)補丁排序模型

基于統(tǒng)計分析的缺陷修復(fù)技術(shù)指利用統(tǒng)計的方法或?qū)W習(xí)的技術(shù)指導(dǎo)補丁生成的過程或?qū)蜻x補丁進行優(yōu)化.比較早的相關(guān)工作是2016年由Long 和Rinard[24]提出來的修復(fù)方法Prophet,該方法是在SPR[67]基礎(chǔ)之上的進一步優(yōu)化.SPR 也是Long 等人在2015年提出來的基于人工定義模板的C 語言條件語句修復(fù)技術(shù).Prophet 根據(jù)修復(fù)前后的代碼特征訓(xùn)練了一個排序模型對SPR 生成的修復(fù)補丁進行排序.Prophet 搜集程序的兩類特征信息:首先是操作,即修復(fù)補丁所使用的代碼修改有哪些,例如插入語句或替換語句等;另一類特征是程序的靜態(tài)特征,例如包含循環(huán)語句或檢查某個變量的取值等.通過實驗表明,該方法可以有效過濾不正確的修復(fù)補丁.雖然Prophet 使用SPR 同樣的補丁生成技術(shù),卻可以多修復(fù)一個缺陷.但該結(jié)果也表明,單純通過補丁排序技術(shù)難以實現(xiàn)較大的效果提升.

2017年,Saha 等人[83]采用類似Prophet 的方法,通過預(yù)定義補丁模板指導(dǎo)修復(fù)過程;同時,應(yīng)用機器學(xué)習(xí)模型對候選的修復(fù)補丁進行排序.基于該方法實現(xiàn)了自動修復(fù)工具ELIXIR.該作者通過實證研究分析實際項目中的歷史修復(fù)發(fā)現(xiàn),面向?qū)ο笳Z言(Java)程序中存在很多函數(shù)調(diào)用相關(guān)的缺陷,例如替換函數(shù)參數(shù)、替換同名函數(shù)調(diào)用等.基于上述分析結(jié)果,作者人工定義了一組補丁生成模板(文中稱為Repair-Expressions),通過搜集缺陷代碼位置可用的程序元素實例化補丁模板生成修復(fù)補丁.在此之后,ELIXIR 根據(jù)程序的上下文特征,例如使用的程序元素在上下文中出現(xiàn)的頻率、缺陷報告中出現(xiàn)的關(guān)鍵詞等,訓(xùn)練一個補丁排序模型,對上述得到的候選補丁進行排序.該方法的思想與Prophet 基本保持一致,差別在于ELIXIR 所定義的補丁模板和排序模型以及針對的編程語言不同.

2019年,White 等人[84]提出使用神經(jīng)網(wǎng)絡(luò)模型對項目中的相似代碼進行排序,以供復(fù)用生成補丁.基于此,實現(xiàn)了自動修復(fù)工具DeepRepair.該修復(fù)工具預(yù)定義了兩種修復(fù)模板用于指導(dǎo)生成補丁,分別是插入新語句和替換已有語句.新插入的語句或替換語句來自項目自身代碼.DeepRepair 通過預(yù)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)模型對候選語句進行排序.在補丁生成階段,DeepRepair 會使用相似的局部變量替換復(fù)用代碼中的未定義變量避免編譯錯誤.然而,實驗對比傳統(tǒng)的基于遺傳算法的自動修復(fù)技術(shù)GenProg 表明,DeepRepair 并不能產(chǎn)生更多正確修復(fù)補丁.其中的一個重要原因是:DeepRepair 采用的代碼修改模板過于簡單,不能很好地覆蓋不同的缺陷類型,而神經(jīng)網(wǎng)絡(luò)模型并不能增強其補丁生成能力.

(2)提取補丁模板用于修復(fù)

2017年,Xiong 等人[25]針對Java 語言中的條件語句修復(fù),提出了高精度的條件語句綜合技術(shù)ACS.該技術(shù)應(yīng)用了3 種技術(shù)手段優(yōu)化生成補丁的質(zhì)量:首先,ACS 利用代碼的局部性原理,根據(jù)變量之間的依賴拓撲關(guān)系對修復(fù)條件中的變量選取進行排序,在拓撲圖中,距離代碼修改位置比較近的變量優(yōu)先使用;此外,ACS 通過分析代碼中的自然語言注釋內(nèi)容,挖掘程序特征來補充測試所定義的不完整程序規(guī)約;最后,ACS 通過統(tǒng)計分析相似項目中常用的條件謂詞,用來對修復(fù)補丁所使用的表達式類型進行篩選和排序.通過分析其他項目中的頻繁謂詞可以獲得領(lǐng)域特定知識,例如變量“hour”通常與常量12 進行比較等,從而有效提升補丁的質(zhì)量.實驗結(jié)果表明:該方法相比之前方法,實現(xiàn)了大概兩倍的修復(fù)準確率.

2017年,Long 等人[85]針對Java 語言的空指針(NPE)、數(shù)組越界(OOB)以及類型強轉(zhuǎn)(CC)缺陷,設(shè)計并實現(xiàn)了自動修復(fù)技術(shù)Genesis.該技術(shù)針對每類缺陷分別準備數(shù)據(jù)集,然后應(yīng)用整數(shù)線性規(guī)劃(ILP)算法為不同的缺陷類型分別推斷代碼修改模板,并采用二元組〈t1,t2〉的形式表示,其中t1 表示代碼修改之前的語法樹,t2 表示修改之后的語法樹.在學(xué)習(xí)模板的過程中,Genesis 隨機地從同類型的代碼修改訓(xùn)練集中選取樣本進行抽象,然后將抽象之后的模板應(yīng)用到訓(xùn)練集上.在盡可能保證修復(fù)數(shù)量最大化的情況下,控制抽象掉的屬性最少(整數(shù)規(guī)劃問題).在修復(fù)階段,首先將缺陷代碼與模板中的t1 進行匹配,如果匹配成功,可以得到表達式的映射關(guān)系,然后根據(jù)t2 生成修復(fù)之后的代碼.在49 個缺陷上的實驗表明,Genesis 可以正確修復(fù)22 個缺陷.

2017年,Rolim 等人[86]提出的Refazer 從代碼修改樣例中學(xué)習(xí)修改模板.為了方便描述代碼的修改操作,作者提出了一個領(lǐng)域特定語言.基于該語言,代碼修改被描述為抽象語法樹上的一系列代碼重寫規(guī)則.每一條規(guī)則匹配部分語法子樹,輸出修改之后的語法子樹.比如替換一個變量為函數(shù)調(diào)用,其輸入是變量對應(yīng)的子樹(根節(jié)點是葉子節(jié)點),輸出則是函數(shù)調(diào)用對應(yīng)的子樹(根節(jié)點是內(nèi)部節(jié)點).Refazer 在提取模板時(重寫規(guī)則序列),采用了基于演繹的程序綜合方法(deductive program systhesis)生成重寫規(guī)則.最后,基于人工定義的啟發(fā)式規(guī)則對其生成的模板進行排序.其基本思想是傾向于盡可能復(fù)用已有的代碼,且被修改的代碼不要包含過多的上下文信息,目的是使得到的模板具有更強的魯棒性.文中通過修復(fù)學(xué)生作業(yè)程序驗證Refazer 的修復(fù)效果,實驗結(jié)果表明,Refazer 可以幫助87%的學(xué)生修復(fù)缺陷代碼.

2018年,Zhong 和Mei[87]提出了一個針對異常(exception)相關(guān)缺陷的修復(fù)技術(shù)MiMo.與之前介紹的自動修復(fù)方法不同的是,MiMo 針對給定的程序缺陷推薦對應(yīng)的修改操作(repair shape).本文的主要出發(fā)點是之前的實證研究關(guān)注于挖掘通用類型的代碼修改操作,期望為自動化的修復(fù)工具提供指導(dǎo).論文作者認為:當(dāng)劃定缺陷的范圍,代碼修改推薦效果將有希望進一步提升.為此,作者首先開發(fā)了一個根據(jù)程序的異常信息對缺陷類型進行自動分類的工具ExFi,并構(gòu)建了一個數(shù)據(jù)集.其中,數(shù)據(jù)集里的每個修復(fù)都被標(biāo)記為特定類型的缺陷.MiMo 應(yīng)用ChangeDistiller,在該數(shù)據(jù)集中提取缺陷修復(fù)的修改操作.對于新的缺陷,MiMo 通過搜索缺陷報告或相關(guān)的Issue報告中的異常信息來匹配需要使用的代碼修改操作.該方法目前只能針對異常相關(guān)的缺陷推薦代碼修改操作,尚不能直接生成修復(fù)補丁.但該論文為以后的研究提供了一個新的思路,即:通過將缺陷分類提取補丁模板,有希望提升現(xiàn)有自動修復(fù)方法的準確率.

2018年,Gulwani 等人[88]提出了Clara,用于修復(fù)學(xué)生的作業(yè)程序.與Refazer 不同的是,Clara 不依賴歷史修復(fù)樣例,而是直接聚類相同功能的正確代碼.在該過程中,Clara 根據(jù)程序的控制流以及變量的使用情況映射功能相同的兩段代碼.此外,Clara 會考慮程序執(zhí)行過程中變量的取值情況映射不同變量.最后,被歸為一類的代碼隨機選擇一個作為該類的代表.在修復(fù)階段,通過匹配缺陷程序與正確程序中的變量和結(jié)構(gòu)生成對應(yīng)的修改.

2019年,Bader 等人[7]提出了自動修復(fù)技術(shù)GetaFix.其基本方法與Genesis 類似,在代碼的語法樹級別提取代碼修改操作以及代碼修改所涉及到的上下文信息.在應(yīng)用其修復(fù)新的缺陷時,首先將缺陷代碼與模板進行匹配,匹配成功,則可以應(yīng)用對應(yīng)的修改操作生成補丁.由于不同的代碼修改操作涉及的上下文特征不同,為了保證提取到的模板具有一定的通用性(在相似但不相同的上下文中可以應(yīng)用),GetaFix 使用層次聚類(hierarchical clustering)算法對提取的模板進行歸類合并,其目的是抽象掉同一類別模板中的不相同特征,例如使用不同的變量名等.但是,如果對模板中的代碼特征過度抽象,會導(dǎo)致模板不能準確地描述其所修改代碼的特征,模板的準確性將降低.為了平衡模板的通用性與準確性,GetaFix 在聚類過程中使用Anti-Unification 算法避免過度抽象.由于該方法依賴相似的代碼修改作代碼抽象,因此對缺陷的重復(fù)性有一定要求,目前僅針對比較常見的一些靜態(tài)工具檢測出的缺陷類型,如空指針異常(NullPointerException)、缺少指定編碼(DefaultCharSet)等.

類似的,2019年,Bavishi 等人[89]同樣針對靜態(tài)分析工具檢測出的缺陷進行修復(fù),并實現(xiàn)了修復(fù)推薦工具Phoenix.它同樣依賴于聚類算法對從歷史中提取的補丁模板進行抽象.為此,作者提出了一個領(lǐng)域特定語言(DSL),用來描述代碼的修改模板.Phoenix 同樣在代碼的抽象語法樹上提取修改模板.具體講,根據(jù)靜態(tài)分析工具報告的缺陷代碼位置,Phoenix 從對應(yīng)的語法樹節(jié)點出發(fā),使用DSL 描述代碼修改的上下文信息,實際上可以表示為有限狀態(tài)自動機(finite state automata),自動機中的每個節(jié)點對應(yīng)語法樹中的節(jié)點,節(jié)點間的連邊代表節(jié)點之間的關(guān)系,比如變量聲明(decl).在模板的聚類階段,Phoenix 采用貪心策略將所有兼容(compatible)的模板進行合并,在合并的過程中,會匹配不同模板所對應(yīng)的自動機并求交集.此處的兼容性根據(jù)修改模板中所包含的字符串和涉及到的節(jié)點類型等因素決定,最終的目標(biāo)是聚類之后的模板之間彼此不兼容.在應(yīng)用其修復(fù)缺陷階段,首先是匹配模板的上下文信息,匹配成功即可應(yīng)用對應(yīng)修改.

2020年,Koyuncu 等人[90]提出了FixMiner,通過迭代式聚類算法,從相似的代碼修改中挖掘可以復(fù)用的代碼修改模板.本文定義了抽象語法樹上的代碼編輯腳本語言,用來描述代碼修改操作.在迭代式聚類過程中,FixMiner 將編輯腳本拆分成3 個子部分進行索引,分別是代碼結(jié)構(gòu)(shape)、代碼修改(action)以及代碼文本(token).通過上述拆分,可以實現(xiàn)對代碼修改聚類的有效加速.在實驗驗證部分,作者將FixMiner 挖掘的修復(fù)模板用于修復(fù)工具PAR 中,結(jié)果表明,其挖掘得到的模板可以用于修復(fù)真實缺陷.與此類似,Liu 等人[91]提出的修復(fù)工具AVATAR 從靜態(tài)分析工具報告的缺陷及其對應(yīng)的修復(fù)中學(xué)習(xí)修復(fù)補丁模板,用于生成修復(fù)補丁.在Defects4J數(shù)據(jù)集上的驗證表明,該方法可以修復(fù)之前方法不能修復(fù)的缺陷.

上述介紹的方法主要依賴于從重復(fù)的代碼修改中提取可復(fù)用補丁模板.而研究表明[92],實際程序修復(fù)中只有不到20%的缺陷存在重復(fù),大部分類型缺陷無法通過聚類提取補丁模板.針對此,2019年,Jiang 等人[93]提出了基于單個歷史修復(fù)的補丁模板提取技術(shù)GenPat.該技術(shù)將代碼映射成代碼圖表示形式,通過分析海量的開源代碼,為補丁模板的抽象提供指導(dǎo).具體講,GenPat 所使用的代碼圖表示模型中,每個節(jié)點包含不同的屬性信息,通過分析對應(yīng)屬性在代碼庫中出現(xiàn)的頻繁程度,決定其通用性.頻繁出現(xiàn)的代碼屬性具有較強的通用性,在模板抽象時被保留,否則被抽象掉.該技術(shù)通過將代碼屬性的抽象過程與代碼修改分離,克服了對重復(fù)修改的依賴,因此可以依據(jù)單個修改提取補丁模板.該方法在Defects4J 數(shù)據(jù)集上驗證有效性,結(jié)果表明:GenPat 可以從單個歷史修復(fù)中學(xué)習(xí)通用的補丁模板,用于修復(fù)真實缺陷.但其依然面臨補丁的準確率低的難題.

(3)端到端補丁生成模型

2017年,Gupta 等人[8]使用序列到序列(sequence-to-sequence)神經(jīng)網(wǎng)絡(luò)(neural network)模型自動修復(fù)C 語言中的編譯錯誤,并基于此實現(xiàn)了自動修復(fù)工具DeepFix.相比已有的自動修復(fù)技術(shù),DeepFix 不依賴外部的缺陷定位過程,通過神經(jīng)網(wǎng)絡(luò)直接預(yù)測程序中的缺陷代碼并產(chǎn)生修復(fù)補丁推薦.具體講,DeepFix 采用了一個多層的(multi-layered)編解碼(encoder-decoder)模型,其編碼器和解碼器均為基于GRU 的循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)模型.此外,DeepFix 在模型的解碼器端結(jié)合了注意力機制(attention mechanism)來提升預(yù)測的準確性.在編碼程序階段,DeepFix 將程序轉(zhuǎn)換為符號序列(token sequence)“(l1,s1),…,(lk,sk),〈eos〉”作為網(wǎng)絡(luò)輸入,其中,(li,si)表示位置li的字符編碼是si,而〈eos〉代表輸入結(jié)束.網(wǎng)絡(luò)預(yù)測輸出是“(li,si′)”,表示用編碼為si′的符號替換位置li的原有符號.為了使得預(yù)測得到的結(jié)果可以還原成源代碼,模型中只抽象掉了字符串常量和整數(shù)常量,分別用STR 和NUM 替代.DeepFix 依賴編譯器驗證其修復(fù)之后的程序是否編譯正確.由于其每次預(yù)測的輸出僅修復(fù)單處錯誤,對于多處位置缺陷,DeepFix 采用迭代式修復(fù)策略.最后,實驗針對常見的4 種簡單編譯錯誤進行修復(fù),例如缺少分隔符、括號錯誤等.實驗結(jié)果表明:DeepFix 可以正確定位78.7%的錯誤代碼位置,正確修復(fù)27.0%的缺陷,且修復(fù)時間僅需要幾十毫秒.該方法模型簡單,針對簡單缺陷比較有效,對于復(fù)雜的缺陷效果如何仍需進一步驗證.

2018年,Bhatia 等人[94]針對學(xué)生作業(yè)Python 程序提出了自動修復(fù)技術(shù).與DeepFix 不同的是,該工作不僅修復(fù)程序的語法錯誤,同時修復(fù)程序的語義錯誤.其具體方法是:首先,使用神經(jīng)網(wǎng)絡(luò)模型修復(fù)缺陷代碼的語法錯誤得到語法正確程序;然后,借助基于語義約束的程序修復(fù)技術(shù),使程序滿足語義規(guī)約.在語法修復(fù)階段,作者使用了RNN 模型,其輸入是語法錯誤程序的符號序列,輸出為修改之后的符號序列,即預(yù)測輸出為程序而非修改.在語義修復(fù)階段,作者通過定義代碼重寫規(guī)則替換程序中的部分變量或者符號,然后將程序的語義轉(zhuǎn)換成邏輯約束,通過參考正確代碼的語義,使用約束求解器求解代碼可能的修復(fù).該方法針對學(xué)生作業(yè)進行修復(fù),存在大量重復(fù)的相同功能代碼,且程序功能相對簡單.實驗結(jié)果表明,該方法平均可以修復(fù)59.8%的語法錯誤和23.8%的語義錯誤.

2019年,Vasic 等人[10]提出使用聯(lián)合預(yù)測(joint prediction)模型修復(fù)程序中的變量使用錯誤,即應(yīng)該使用其他變量替換程序中的某些變量使用.論文的基本思想是,代碼中出錯的變量通常應(yīng)該使用上下文中存在的某個變量進行替換.因此,作者提出使用多頭指針網(wǎng)絡(luò)模型(multi-head pointer network)對程序代碼是否存在缺陷、缺陷的位置以及對應(yīng)的修復(fù)進行聯(lián)合預(yù)測.為此,該方法首先使用LSTM(long-short term memory)模型對程序進行編碼,模型的輸出作為指針模型的輸入.在該方法中,指針模型包含兩個指針,其中一個指針指向錯誤使用的變量p的位置,另一個指針指向期望的正確變量q的位置.其對應(yīng)的修復(fù)即使用變量q替換變量p.特殊地,當(dāng)程序中不存在變量錯誤使用缺陷時,模型的第一個指針將指向一個預(yù)定義的特殊位置.當(dāng)給定一個數(shù)據(jù)集,首先對程序中的所有出錯位置以及待替換的變量進行標(biāo)記.在模型訓(xùn)練階段,分別根據(jù)出錯位置預(yù)測正確數(shù)以及修復(fù)變量預(yù)測正確數(shù)建立損失函數(shù)(loss function),最后的聯(lián)合預(yù)測則取兩者損失函數(shù)的求和作為最終的優(yōu)化目標(biāo).最終實驗在開源網(wǎng)站上的15 萬條Python 源代碼上進行測試,測試結(jié)果表明:基于上述預(yù)測模型,出錯位置預(yù)測準確率為71.0%,同時,修復(fù)的預(yù)測準確率為65.7%.相比之前介紹的基于神經(jīng)網(wǎng)絡(luò)模型的修復(fù)技術(shù),本方法被應(yīng)用到大型的項目代碼中,具有更好的延展性;但其缺點是僅針對變量使用錯誤,應(yīng)用范圍受限.

2019年,Tufano 等人[95]探索了使用自然語言處理中的NMT(neural maching translation)技術(shù)為程序缺陷預(yù)測修復(fù)補丁的效果.在該論文中,作者采用了編碼器-解碼器模型,模型的輸入和輸出分別是出錯的代碼片段和正確的代碼片段.需要注意的是:為了降低變量名稱和常量值等帶來的干擾,模型輸入的代碼首先需要抽象處理,為每個變量和常量等設(shè)定唯一的標(biāo)識符,例如變量a為VAR_1,常量0 為INT_1 等.特殊地,為了反映程序的語義特征,在抽象的過程中,作者預(yù)定義了一些常用的慣用詞(idioms),例如size,min 等,在抽象過程中被保留.由于上述已經(jīng)介紹過編碼器-解碼器模型,基本思路相同,此處不再贅述.為了提升最終預(yù)測結(jié)果的準確率,作者采用了束搜索(beam search)算法對修復(fù)的預(yù)測進行調(diào)優(yōu).最終輸出的代碼通過還原標(biāo)識符對應(yīng)的原始值可得.實驗結(jié)果表明,使用NMT 模型對修復(fù)補丁的預(yù)測準確率在12.0%左右.相比之前的工作,準確率比較低,其中一個主要原因是其針對的缺陷類型更廣、復(fù)雜度更高.

2019年,Chen 等人[9]在Tufano 等人工作之后提出了針對Java 語言代碼缺陷自動修復(fù)技術(shù)SequenceR,同樣采用編碼器-解碼器模型.相比之前的工作,其主要的不同在于:SequenceR 采用了復(fù)制機制(copy mechanism)[96],簡單描述為,可以將模型的輸入端數(shù)據(jù)直接復(fù)制到輸出端.這樣做的好處是可以實現(xiàn)部分代碼的直接復(fù)用,緩解模型不準帶來的巨大誤差.實驗證明,SequenceR 的預(yù)測準確率高于上述Tufano 等人提出的NMT 模型.此外,將SequenceR 用于修復(fù)Defects4J 數(shù)據(jù)集中的75 個單行代碼缺陷,正確修復(fù)了14 個.該實驗結(jié)果表明:盡管相比已有基于搜索的修復(fù)方法效果還有差距,但使用機器學(xué)習(xí)的方法有希望正確修復(fù)大型項目中的真實程序缺陷.其優(yōu)點是不依賴任何人工定義模板以及啟發(fā)式規(guī)則.

(4)本節(jié)小結(jié)

基于統(tǒng)計分析的修復(fù)技術(shù)在最近幾年發(fā)展迅速,其優(yōu)點是可以利用海量的開源代碼數(shù)據(jù)指導(dǎo)修復(fù)過程,處理各種不同類型的缺陷,具有較強的通用性,并且不依賴人工精心設(shè)計啟發(fā)式搜索方法以及人工定義修復(fù)模板,有希望成為未來的實用化修復(fù)方法.然而,該類方法依賴于訓(xùn)練數(shù)據(jù)的質(zhì)量.如何從海量的開源數(shù)據(jù)中準確提取代碼特征,是提升其修復(fù)能力的關(guān)鍵.盡管已有方法已經(jīng)取得了初步成效(如GetaFix 和GenPat 等),但依然具有很大的提升空間.特別是對于端到端的補丁生成模型,已有方法主要適用于分類任務(wù)或自然語言處理的應(yīng)用場景,在自動修復(fù)場景中表現(xiàn)并不理想.研究針對代碼生成任務(wù)的高效方法,依然需要更多探索.基于統(tǒng)計分析的修復(fù)技術(shù)存在一個固有的能力約束:依賴于代碼或代碼修改的重復(fù)性.而開發(fā)者的開發(fā)以及修復(fù)過程常常伴隨較高的創(chuàng)新性.目前的方法從數(shù)據(jù)中所學(xué)習(xí)到的領(lǐng)域知識依然十分有限,在缺陷修復(fù)中主要起輔助作用,距離實用化尚存較大鴻溝.

3 自動修復(fù)技術(shù)面臨挑戰(zhàn)與啟示

根據(jù)第2 節(jié)最新相關(guān)研究的介紹,目前的自動修復(fù)工具所能修復(fù)的缺陷依然占所有缺陷的小部分.根據(jù)我們對已有缺陷修復(fù)工具在通用缺陷數(shù)據(jù)集Defects4J 上的修復(fù)結(jié)果統(tǒng)計,所有修復(fù)工具可以正確修復(fù)的缺陷總數(shù)僅有101 個,還不到完整數(shù)據(jù)集的30%(v1.2.0 版本包含395 個缺陷).不僅如此,自動修復(fù)工具所產(chǎn)生的修復(fù)補丁準確率依然難以達到工業(yè)應(yīng)用的要求.因此,自動化的修復(fù)技術(shù)目前依然面臨巨大挑戰(zhàn).本節(jié)根據(jù)之前相關(guān)研究的介紹,對目前面臨的問題和挑戰(zhàn),以及未來可能研究方向進行總結(jié).

?低召回率問題

Motwani 等人[97]通過對早期7 種自動修復(fù)工具所修復(fù)的缺陷進行分析發(fā)現(xiàn),正確修復(fù)的缺陷通常比較簡單,例如空指針異常、修改變量等,不涉及大段代碼或多文件修改,更不涉及生成復(fù)雜的代碼結(jié)構(gòu)(例如循環(huán)等).影響召回率的因素是多方面的,其中比較重要的原因可以歸結(jié)為以下兩點.

(1)缺陷定位準確率低.有研究表明[11,98,99],定位的準確率會直接影響缺陷修復(fù)的數(shù)量,通過提升定位的準確率可以有效提升修復(fù)召回率;

(2)補丁空間受限.已有的自動修復(fù)技術(shù)主要依賴于人工定義的修復(fù)模板或啟發(fā)式規(guī)則約束補丁的空間,導(dǎo)致目前僅僅針對比較常見的簡單缺陷進行修復(fù),如NPEfix 僅修復(fù)空指針缺陷.

?低準確率問題

基于測試的缺陷自動修復(fù)技術(shù)依賴于測試提供程序規(guī)約過濾候選修復(fù)補丁.但實際中,測試通常比較弱[22],不能提供完整的程序規(guī)約,從而導(dǎo)致即使修復(fù)補丁通過測試也可能是不正確的(似真補丁),即修復(fù)工具會產(chǎn)生過擬合補丁[100,101].李斌等人[5]已經(jīng)針對該問題進行了詳細的分析和討論,本文不再贅述.

針對缺陷自動修復(fù)存在的上述兩點問題,本文將其所面臨的的挑戰(zhàn)及對未來研究的展望總結(jié)如下.

(1)定位提供的信息.目前的缺陷定位技術(shù)在缺陷自動修復(fù)框架中所起的作用是返回代碼中的疑似語句,指導(dǎo)補丁生成過程,兩個過程相對獨立而缺少交互.但是在實際開發(fā)者人工修復(fù)的過程中,并不是嚴格遵循上述的過程,而是兩者相互作用[102]:定位的過程可以為修復(fù)提供出錯的“原因”指導(dǎo)生成補丁;反過來,修復(fù)可以進一步優(yōu)化定位的結(jié)果.DirectFix 通過優(yōu)先選取簡單的語句進行修復(fù),在一定程度上打破了上述的修復(fù)范式.但實際上,定位所提供的信息依然有限.最新的研究[103]嘗試應(yīng)用自動修復(fù)產(chǎn)生的補丁優(yōu)化缺陷定位的準確率,但其實驗效果相比最新的定位技術(shù)并無明顯提升.在缺陷定位研究領(lǐng)域,最新的一些研究工作通過概率模型推導(dǎo)程序出錯原因.如何將類似信息反饋給補丁生成過程作為有效指導(dǎo),目前依然缺少探索;

(2)啟發(fā)式規(guī)則.大部分已有的自動修復(fù)技術(shù)依賴人工定義的啟發(fā)式規(guī)則作為生成補丁的指導(dǎo),然而已有的啟發(fā)式規(guī)則僅依賴單一數(shù)據(jù)特征,如代碼的語法特征(DirectFix 將補丁修改的大小作為啟發(fā)式規(guī)則)或代碼語義特征(GenProg 將補丁通過測試的數(shù)量作為啟發(fā)式規(guī)則).單一的約束會導(dǎo)致補丁搜索陷入局部最優(yōu),例如GenProg 產(chǎn)生很多通過測試的似真補丁.因此,結(jié)合代碼的多維度特征提出合適的啟發(fā)式規(guī)則用于引導(dǎo)補丁的生成,是提升補丁質(zhì)量的重要途徑;

(3)補丁模板數(shù)量.基于補丁模板的修復(fù)方法通常依賴于人工定義好修復(fù)的模板,在補丁生成階段,根據(jù)條件逐一嘗試.這種修復(fù)模式適用于修復(fù)比較常見的、開發(fā)者比較熟悉且容易定義的缺陷類型,例如插入一個條件語句、替換一個變量等.對于存在復(fù)雜邏輯約束的缺陷類型而言并不容易定義,因此在理論上,已有方法只能修復(fù)一些比較簡單的缺陷.Noda 等人[104]將ELIXIR 應(yīng)用于實際的工業(yè)場景發(fā)現(xiàn),其有限的模板是限制其修復(fù)數(shù)量的一個重要原因.雖然最新提出的修復(fù)方法嘗試自動從歷史修復(fù)中學(xué)習(xí)模板(例如Genesis,GetaFix 等),但由于該類方法依賴大量重復(fù)的訓(xùn)練數(shù)據(jù),其應(yīng)用范圍受到限制,也是僅僅針對個別類型的缺陷.GenPat 通過從單個代碼修改提取補丁模板,可以有效克服上述問題,但目前也僅有少數(shù)缺陷可以通過該方式修復(fù).其中的一個關(guān)鍵原因是,自動提取的模板質(zhì)量低于人工定義模板.所以,研究從少量數(shù)據(jù)自動學(xué)習(xí)高質(zhì)量補丁模板并應(yīng)用于修復(fù)真實缺陷,依然面臨重大挑戰(zhàn);

(4)代碼修改大小.已有的自動修復(fù)工具只針對修改比較小的缺陷類型,比如單行代碼修改或單個函數(shù)代碼修改等.實際中的代碼缺陷可能涉及多函數(shù)甚至多文件修改,或者涉及復(fù)雜的代碼結(jié)構(gòu)(例如循環(huán)).盡管最新的工作已經(jīng)開始探索程序多點修改,如HERCULES,但其修復(fù)能力依然非常有限,僅修復(fù)多點代碼修改類似或相同的缺陷.如果被修改的多處代碼需要完全不同的修改甚至存在相互依賴關(guān)系,上述方法將無能為力.例如在程序A點添加一個標(biāo)記變量,在程序B點對標(biāo)記變量進行檢查.除此之外,已有的缺陷修復(fù)工具通常將代碼修改的范圍限定在有限的代碼區(qū)間內(nèi)(<5 行),這也是限制已有方法召回率的重要原因.但擴大代碼修改范圍會導(dǎo)致補丁搜索難度增加,降低補丁的準確率.因此,在擴大代碼修改范圍時,如何根據(jù)修改之間的依賴關(guān)系約束補丁空間,是其中的重要挑戰(zhàn);

(5)代碼復(fù)用粒度.從早期的GenProg 修復(fù)方法開始,利用代碼的重復(fù)性修復(fù)缺陷被證明是有效的.最新的研究通過細粒度的代碼復(fù)用實現(xiàn)了較大的效果提升,例如ssFix,SimFix 等.然而,上述修復(fù)技術(shù)依然依賴于較大段的重復(fù)代碼(5 行~10 行).在實際的項目中,這樣的重復(fù)代碼并不總是存在.因此,如何在更細粒度搜索并復(fù)用已有的代碼用于合成新代碼,是擴展現(xiàn)有補丁空間的有效手段.雖然基于組件的合成方法(例如SemFix)在理論上可以實現(xiàn)上述目標(biāo),但由于約束求解器并非針對該特定問題所設(shè)計,實際求解得到的代碼質(zhì)量低、可讀性差.所以,探索通過代碼復(fù)用合成高質(zhì)量的修復(fù)補丁,是提升修復(fù)召回率的有效手段;

(6)依賴未通過測試.目前,軟件缺陷自動修復(fù)方法主要集中于基于測試的修復(fù)方法,即,根據(jù)程序中未通過的測試定位程序中的錯誤.然而在真實的開發(fā)場景中,未通過的測試并不總是存在的.在缺陷修復(fù)領(lǐng)域中常用的驗證數(shù)據(jù)集Defects4J(v1.2.0)中,96%(=381/395)的程序缺陷在被修復(fù)之前無對應(yīng)的未通過測試[48].該問題會嚴重影響目前的自動修復(fù)技術(shù)在真實工業(yè)開發(fā)場景中的實用性.最新的一些自動修復(fù)方法嘗試分析缺陷報告[53]、應(yīng)用軟件靜態(tài)分析[57,59]等技術(shù)定位程序中的缺陷或驗證補丁正確性,從而不依賴于未通過測試.但其修復(fù)效果相比基于測試的修復(fù)技術(shù)依然存在較大的差距.而且該類方法主要針對一些特定類型的缺陷,如空指針錯誤[59]、內(nèi)存溢出[57]等.因此,非基于測試的自動修復(fù)技術(shù)在未來的研究中依然需要更多的探索;

(7)不完整規(guī)約.測試為缺陷修復(fù)工具提供規(guī)約,測試不完備是導(dǎo)致似真補丁的一個重要原因.已有研究的實驗[105]表明,測試的覆蓋率與補丁的質(zhì)量成正相關(guān).因此,提升測試的覆蓋率是提升補丁質(zhì)量和修復(fù)準確率的重要手段.最新的一些研究[22,23,106]通過生成新的測試對候選補丁進行過濾,可以在一定程度上提升補丁質(zhì)量.然而,由于測試生成依賴測試斷言(oracle),導(dǎo)致自動生成的測試對補丁過濾有限.挖掘程序的其他特征對程序規(guī)約進行補全,是提升補丁質(zhì)量的有效途徑.已有工作嘗試使用類似特征指導(dǎo)補丁生成(例如ACS),但目前挖掘到的程序規(guī)約信息依然比較有限.可以考慮結(jié)合更多的數(shù)據(jù)源,比如項目的演化歷史和缺陷報告等,對程序規(guī)約進行補全;

(8)語義理解.程序自動修復(fù)技術(shù)實際上涉及程序理解的過程.然而,自動修復(fù)方法通過啟發(fā)式搜索或代碼復(fù)用的方式雖然在一定程度上可以修復(fù)程序中的部分代碼,但實際上針對其修復(fù)結(jié)果并不能給出合理的解釋,即并沒有真正理解程序的語義.因此,補丁的生成過程在一定程度上具有隨機性和盲目性.這也是導(dǎo)致對于開發(fā)者非常容易修復(fù)的一些缺陷,自動修復(fù)工具卻難以修復(fù)的一個重要原因.但程序理解本身就是一件具有重大挑戰(zhàn)的研究.隨著近年來人工智能的發(fā)展,使用智能化的算法(例如深度神經(jīng)網(wǎng)絡(luò))實現(xiàn)程序語義的部分理解,是可探索的方向.

自動修復(fù)技術(shù)的上述挑戰(zhàn)是目前研究被廣泛關(guān)注的重點問題,也是在未來的研究中亟待解決的難點.部分挑戰(zhàn)在之前的綜述論文中[1,3]也有被提出過,比如不完整規(guī)約導(dǎo)致的補丁過擬合等,此處結(jié)合最新研究對其進一步歸納和總結(jié).除此之外,已有綜述論文中同時提出了自動修復(fù)技術(shù)所面臨的關(guān)于實用性的重要挑戰(zhàn),接下來本文對其進一步總結(jié).

?修復(fù)效率問題

目前,研究比較廣泛的基于測試的自動修復(fù)方法大部分遵循“生成-驗證”的模型[25?28,93],即首先生成修復(fù)補丁,然后通過運行測試驗證補丁的正確性.該模型由于依賴測試的反復(fù)執(zhí)行,會導(dǎo)致修復(fù)效率比較低,一般需要幾十分鐘到幾個小時去修復(fù)一個程序缺陷,使得已有的自動修復(fù)方法只能離線使用,不能為開發(fā)者提供實時的反饋.已有研究從不同角度提升修復(fù)效率,如早期的自動修復(fù)方法AE[107],通過分析補丁的等價性來避免重復(fù)補丁的驗證過程.此外,Prophet[24]通過補丁排序方法使得正確的修復(fù)補丁盡可能得到提前驗證,在一定程度上可以提升修復(fù)的效率.但上述方法依然不能避免驗證大量候選補丁所帶來的巨大時間開銷.最新的研究中,通過補丁隔離[44]和字節(jié)碼修復(fù)[31]避免了補丁驗證過程中的代碼反復(fù)編譯開銷,大幅度提升了修復(fù)的效率.然而,盡管如此,自動修復(fù)方法依然難以滿足在線與開發(fā)者交互的實效要求.因此,修復(fù)效率依然是目前自動修復(fù)方法所面臨的實用性挑戰(zhàn)之一.

?代碼可維護性問題

由于自動生成的補丁一般通過組合復(fù)用已有的代碼片段產(chǎn)生,在缺少領(lǐng)域知識進行有效指導(dǎo)的情況下,補丁代碼具有一定的隨機性,比如產(chǎn)生類似“if(a!=a)”和“if(1<3)”等死代碼(dead code),甚至?xí)a(chǎn)生重復(fù)代碼[29]以及晦澀難懂的補丁代碼[69]等,嚴重影響代碼的可讀性和可維護性.最新的研究通過啟發(fā)式方法或統(tǒng)計分析嘗試從已有代碼或補丁數(shù)據(jù)中學(xué)習(xí)類似的領(lǐng)域知識,在一定程度上降低了補丁的隨機性,但補丁質(zhì)量依然難以保證.目前,依然缺少關(guān)于該問題的針對性研究.

?工業(yè)場景中的實用性問題

根據(jù)之前的介紹,現(xiàn)有的通用自動修復(fù)方法主要是基于測試的方法.然而在真實的工業(yè)生產(chǎn)環(huán)境中,依賴的未通過測試用例并不能保證存在.另一方面,由于自動修復(fù)方法生成補丁的正確率和質(zhì)量(可讀性和可維護性)依然難以保證,其補丁最終依賴于人工驗證.相比于人工修復(fù),使用自動化的修復(fù)方法是否會更高效,目前缺少系統(tǒng)性的對比研究.此外,已有的研究主要在實驗環(huán)境下、少數(shù)的數(shù)據(jù)集上驗證方法的有效性.已有研究[104]將自動修復(fù)工具應(yīng)用到工業(yè)場景中,實驗結(jié)果與實驗環(huán)境相差較大.因此,更加全面地驗證自動修復(fù)方法的有效性,是評估其實用性的重要方面.近幾年,盡管更多豐富的實驗數(shù)據(jù)集被提出(參考第4.1 節(jié)),但被使用的頻率相對較低.其中的一個主要原因是不同的數(shù)據(jù)集所依賴環(huán)境不兼容,適配對應(yīng)的方法會引入較大的時間開銷.因此,設(shè)計和開發(fā)統(tǒng)一的、易于擴展的、模擬真實工業(yè)生產(chǎn)環(huán)境的通用缺陷修復(fù)平臺,有利于驗證和對比不同自動修復(fù)方法的有效性,促進修復(fù)技術(shù)的實用化研究進程.

4 缺陷修復(fù)數(shù)據(jù)集和開源修復(fù)工具總結(jié)

本節(jié)總結(jié)缺陷自動修復(fù)研究領(lǐng)域常用的基準數(shù)據(jù)集(benchmark)以及重要的開源缺陷自動修復(fù)工具.

4.1 常用缺陷數(shù)據(jù)集

表1 中列出了自動修復(fù)領(lǐng)域常用的缺陷數(shù)據(jù)集,表中給出了每個數(shù)據(jù)集所對應(yīng)的參考文獻、發(fā)表時間、缺陷程序涉及語言、數(shù)據(jù)來源以及下載地址鏈接,方便之后的研究人員下載使用.

Table 1 Benchmarks for automatic program repair表1 缺陷修復(fù)驗證數(shù)據(jù)集

目前,使用最為廣泛的是2014年Just 等人[43]提出的Defects4J 數(shù)據(jù)集.該數(shù)據(jù)集早期版本(v0.1.0)包含來自5 個開源項目的357 個真實程序缺陷,該部分缺陷也是目前被廣泛使用驗證缺陷修復(fù)工具效果的對象.該數(shù)據(jù)集中的每個程序缺陷包含至少一個未通過的測試可以觸發(fā)程序中的缺陷,其中部分未通過測試來自于原始的程序缺陷報告,部分未通過測試是開發(fā)者在修復(fù)對應(yīng)缺陷時新添加的(詳見第3 節(jié)中的討論).近幾年,該數(shù)據(jù)集在不斷地擴充,最新的v2.0.0 版本已經(jīng)擴展到17 個項目共835 個缺陷.

ManyBugs 數(shù)據(jù)集是由LeGoues 等人[108]提出來的C/C++語言程序缺陷,該數(shù)據(jù)集中共包含來自7 個開源項目的185 個真實程序缺陷.其中,每個缺陷程序都有至少一個未通過的測試觸發(fā)程序中的缺陷,且未通過測試均由項目的開發(fā)者編寫.相比表1 中其他C/C++語言缺陷數(shù)據(jù)集,ManyBugs 中的項目規(guī)模最大.與此不同,LeGoues等人同時提出的IntroClass 數(shù)據(jù)集來自于本科生的課程編程任務(wù),共包含998 個學(xué)生提交的缺陷程序,涉及6 個編程任務(wù).此外,程序代碼的規(guī)模比較小,一般僅有5 行~20 行代碼.類似地,IntroClass 中的每個任務(wù)通過多個“輸入-輸出”樣例來描述程序的規(guī)約.每個缺陷程序被至少一個測試樣例所觸發(fā).

IntroClassJava 是IntroClass 數(shù)據(jù)集的Java 語言版本,由Durieux 和Monperrus[109]通過人工定義轉(zhuǎn)換規(guī)則,使用腳本自動化將C/C++語言程序轉(zhuǎn)換為Java 程序.此外,他們將IntroClass 中的“輸入-輸出”樣例轉(zhuǎn)換成了可執(zhí)行的Junit 單元測試.在轉(zhuǎn)換的過程中,由于刪除了其中的部分重復(fù)程序以及未能正確轉(zhuǎn)換的程序,最終數(shù)據(jù)集中包含297 個缺陷程序.

與IntroClass 類似,CodeFlaws 數(shù)據(jù)集來自于在線編程競賽平臺Codeforces.該數(shù)據(jù)集中共包含3 902 個程序缺陷,其中每個缺陷都存在對應(yīng)的未通過測試.與其他數(shù)據(jù)集不同,CodeFlaws 根據(jù)程序的代碼修改將所有的程序缺陷劃分為了39 個缺陷類型,可以用來研究不同修復(fù)工具對特定類型缺陷的修復(fù)效果.

DroixBench 數(shù)據(jù)集包含來自15 個開源Android 軟件的24 個可復(fù)現(xiàn)的運行崩潰缺陷,特別地,該數(shù)據(jù)集中的程序缺陷均涉及用戶界面(UI).

QuixBugs 數(shù)據(jù)集包含Python 和Java 兩種語言的缺陷程序,其中40 個Python 缺陷程序來自于Quixey 公司測試題目,程序代碼為幾行到幾十行不等,且每個代碼缺陷只涉及一行代碼修改.其中的Java 缺陷程序由人工編寫,與上述Python 缺陷程序一一對應(yīng).與IntroClass 類似,該數(shù)據(jù)集同樣是采用“輸入-輸出”樣例的形式描述程序的規(guī)約.

Bugs.jar 是繼Defects4J 之后的一個更大的Java 語言程序缺陷數(shù)據(jù)集,該數(shù)據(jù)集包含8 個Apache 開源項目中的1 158 個程序缺陷.為了提升缺陷程序的多樣性,不同的項目涉及不同的應(yīng)用場景,如數(shù)據(jù)庫、常用庫、Web框架等.此外,除了包含觸發(fā)程序缺陷的測試,Bugs.jar 中還包含對應(yīng)缺陷的問題編號(issue id)以及缺陷報告(bug report),可以用來追溯對應(yīng)缺陷在項目問題追蹤系統(tǒng)(issue tracking system)中的記錄.

Bears 是由Madeiral 等人[113]提出來的Java 缺陷程序數(shù)據(jù)集.相比于上述的數(shù)據(jù)集,其特點是易于擴展.它通過檢測GitHub 上開源項目的持續(xù)集成(continuous integration)構(gòu)建結(jié)果,自動識別不能通過測試的缺陷代碼版本.因此,用戶可以根據(jù)需要擴展數(shù)據(jù)集.其初始版本(v1.0)包含72 個項目中的251 個程序缺陷.

與Bears 類似,BugSwarm 采用同樣的策略不斷擴展數(shù)據(jù)集的大小.截止其論文發(fā)表,BugSwarm 已經(jīng)搜集了3 091 個Java 和Python 程序缺陷,并執(zhí)行周期性檢測,不斷擴展其數(shù)據(jù)集大小.

根據(jù)上面的介紹可以發(fā)現(xiàn),缺陷程序的數(shù)據(jù)集在向著多語言、多種類、大規(guī)模演化.然而,目前使用較廣泛的數(shù)據(jù)集依然比較集中(Defects4J 居多).其原因可能包含以下兩點:(1)使用相同的數(shù)據(jù)集方便不同方法對比驗證;(2)數(shù)據(jù)集的易用性.然而,單一的數(shù)據(jù)集可能會導(dǎo)致自動修復(fù)方法面臨過擬合問題,而影響其效果的客觀評價.因此在未來的研究中,不同的數(shù)據(jù)集應(yīng)該被利用起來,同時需要考慮實用化的工業(yè)生產(chǎn)環(huán)境.

4.2 開源缺陷修復(fù)工具

工具是驗證算法有效性的重要支撐,可以為其他研究人員學(xué)習(xí)其方法以及對比新技術(shù)提供方便.自動修復(fù)工具代碼開源為后來研究者搭建了好的平臺,可以促進該領(lǐng)域的發(fā)展.表2 列出了2016年至今的一些開源缺陷修復(fù)項目,包含自動修復(fù)工具的名稱、對應(yīng)發(fā)表論文、發(fā)表時間、針對的編程語言、所屬的修復(fù)技術(shù)分類以及下載鏈接.在該表格中,我們使用HS(heuristic search)、MT(manual template)、SC(semantic constraint)和SA(statistical analysis)分別代表基于啟發(fā)式搜索、人工修復(fù)模板、語義約束和統(tǒng)計分析的自動修復(fù)技術(shù).特殊地,DiffTGen 通過生成測試對候選的修復(fù)補丁進行過濾,該方法本身不能自動生成修復(fù)補丁,因此無分類項.此外,一些開源項目(如Astor)集成了多個自動修復(fù)工具,此時,其分類為所有工具分類的并集.根據(jù)表中的引用可以檢索對應(yīng)修復(fù)工具的具體算法描述,下載地址可以方便閱讀者檢索和下載.

5 總結(jié)

缺陷自動修復(fù)由于有希望將開發(fā)者從繁重的程序調(diào)試過程中解脫出來而受到越來越多的關(guān)注,眾多的缺陷修復(fù)技術(shù)被先后提出.本文針對缺陷自動修復(fù)相關(guān)的文獻進行了系統(tǒng)的整理.對最近10年間論文的發(fā)表情況進行了詳細的分析.特殊地,本文針對2016年至今基于測試的缺陷自動修復(fù)技術(shù)進行了詳細的分析和總結(jié).根據(jù)缺陷修復(fù)技術(shù)在補丁生成階段所使用的不同方法,本文將自動修復(fù)技術(shù)系統(tǒng)性地分為4 類.相比已有的綜述論文,本文首次提出了基于統(tǒng)計分析的缺陷修復(fù)技術(shù)類別,對已有的技術(shù)分類進行了補充.此外,本文對目前該領(lǐng)域研究所面臨的挑戰(zhàn)做了分析和總結(jié),對未來的研究具有指導(dǎo)意義.最后,本文對缺陷修復(fù)領(lǐng)域常用的數(shù)據(jù)集和開源修復(fù)工具進行了整理和歸納,方便讀者引用.

Table 2 Automatic program repair tools表2 缺陷自動修復(fù)工具