韓俊璇， 孫偉峰， 趙瑞蓮， 王微微

(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100029)

0 引言

程序自動(dòng)修復(fù)旨在利用程序相關(guān)信息，對(duì)含有缺陷的程序進(jìn)行自動(dòng)修復(fù)。修復(fù)生成-驗(yàn)證技術(shù)是近年來提出的一種通用程序自動(dòng)修復(fù)方法，它首先對(duì)程序源代碼進(jìn)行修改，生成一組補(bǔ)丁，然后通過執(zhí)行測(cè)試用例，驗(yàn)證補(bǔ)丁的正確性。GenProg[1]是最早提出的生成-驗(yàn)證工具，它使用變異來修改源程序以生成補(bǔ)丁，結(jié)合遺傳規(guī)劃算法中的適應(yīng)度函數(shù)選取更優(yōu)的補(bǔ)丁進(jìn)入下一代，并通過執(zhí)行測(cè)試用例驗(yàn)證每一代補(bǔ)丁的正確性。然而，其適應(yīng)度函數(shù)僅與測(cè)試用例通過與否相關(guān)，易導(dǎo)致補(bǔ)丁雖能通過所有測(cè)試用例，但與源程序的語義偏差極大。由于GenProg的修復(fù)對(duì)象僅為C程序，Martinez等[2]提出了jGenProg來對(duì)GenProg進(jìn)行擴(kuò)展，實(shí)現(xiàn)了對(duì)Java程序的自動(dòng)修復(fù)。相較于GenProg，Kim等[3]提出了一種通過隨機(jī)搜索算法來生成補(bǔ)丁的方法RSRepair，該方法雖未采用適應(yīng)度來指導(dǎo)補(bǔ)丁生成，但其修復(fù)效果與遺傳規(guī)劃算法基本相同。然而，此類程序自動(dòng)修復(fù)技術(shù)由于缺少相關(guān)修復(fù)信息的指導(dǎo)，生成的補(bǔ)丁數(shù)量雖然較多，但僅有極少數(shù)補(bǔ)丁與源程序語義相同，修復(fù)效果不佳。

不同于上述方法，基于模板的程序自動(dòng)修復(fù)方法可從歷史修復(fù)信息中獲取與缺陷相關(guān)的修改信息，如修改位置、修復(fù)目標(biāo)等信息，進(jìn)而指導(dǎo)程序的自動(dòng)修復(fù)。此類方法生成的補(bǔ)丁與源程序語義具有較高的相似性，可提升程序自動(dòng)修復(fù)的效果。近年來，研究人員提出了許多修復(fù)模板挖掘的方法來實(shí)現(xiàn)程序的自動(dòng)修復(fù)。例如：Liu等[4]從StackOverflow問答信息出發(fā)，提出一種程序修復(fù)模板挖掘的方法SOFIX。然而，SOFIX在挖掘修復(fù)信息時(shí)，未對(duì)修復(fù)信息進(jìn)行完善的預(yù)處理，導(dǎo)致模板的修復(fù)效果不佳。此外，SOFIX在搜索修復(fù)模板時(shí)，采用枚舉策略完成程序自動(dòng)修復(fù)，致使程序自動(dòng)修復(fù)的效率不高。Le等[5]提出一種從歷史修復(fù)信息中總結(jié)修復(fù)模板的方法HistoricalFix，但該修復(fù)模板在修復(fù)數(shù)量和粒度上存在局限性。Xuan等[6]提出一種面向條件語句修復(fù)模板挖掘的方法Nopol，該方法僅支持if條件語句的缺陷修復(fù)。

由上述分析可知，現(xiàn)有修復(fù)模板挖掘方法未對(duì)修復(fù)信息進(jìn)行深入分析，忽略了修復(fù)信息中的部分語義，導(dǎo)致挖掘的修復(fù)模板不夠準(zhǔn)確。此外，現(xiàn)有研究大多關(guān)注修復(fù)模板挖掘方法，對(duì)于如何利用修復(fù)模板對(duì)程序進(jìn)行修復(fù)尚未給出具體方法。

因此，本文提出了一種改進(jìn)的程序自動(dòng)修復(fù)方法APRMT，包括修復(fù)模板的挖掘和基于修復(fù)模板的程序自動(dòng)修復(fù)兩部分。具體來說，APRMT通過正則匹配規(guī)則消除修復(fù)信息中的無用信息，避免噪聲信息的干擾，精確分析修復(fù)信息的語義，識(shí)別不完整的修改操作，并對(duì)其補(bǔ)全，避免因信息缺失導(dǎo)致的修復(fù)模板不準(zhǔn)確問題。在此基礎(chǔ)上，APRMT依據(jù)缺陷代碼位置及類型，采用最近最相關(guān)策略搜索當(dāng)前程序缺陷的相關(guān)修復(fù)信息，解決了生成補(bǔ)丁與源代碼語義差別大的問題，縮短了程序自動(dòng)修復(fù)時(shí)間，提高了修復(fù)效率。

1 APRMT修復(fù)模板挖掘

1.1 程序代碼及修復(fù)信息的獲取及預(yù)處理

APRMT方法旨在從StackOverflow問答對(duì)的程序修復(fù)信息中挖掘修復(fù)模板，指導(dǎo)程序的自動(dòng)修復(fù)[7]。因此，本節(jié)首先探討如何從StackOverflow問答對(duì)中提取程序及其修復(fù)信息，以及對(duì)此類信息的預(yù)處理，為后續(xù)模板挖掘奠定基礎(chǔ)。

StackOverflow問答對(duì)中提供了大量關(guān)于程序修復(fù)的代碼段信息，即代碼對(duì)，其中bug表示含有缺陷的代碼段，fixed表示其缺陷修復(fù)后的代碼段。但是在StackOverflow中，一個(gè)bug代碼段可能存在多種fixed代碼段作為其修復(fù)結(jié)果。為了盡可能保證兩段代碼語義的一致性，在選擇代碼對(duì)時(shí)，應(yīng)保留對(duì)bug代碼段修改較小的fixed代碼段。

為提高后續(xù)模板挖掘的有效性，采用APRMT方法對(duì)代碼對(duì)進(jìn)行預(yù)處理，首先通過正則表達(dá)式消除問答代碼對(duì)中的無用信息，提高代碼對(duì)相似度比較的準(zhǔn)確性；然后，采用APRMT計(jì)算代碼對(duì)中兩段代碼的相似程度，并盡可能選取相似度較高的代碼對(duì)作為后續(xù)模板挖掘的基礎(chǔ)。在進(jìn)行代碼相似度計(jì)算時(shí)，TF-IDF算法可為代碼中較為重要的單詞賦予較高的權(quán)重，相比純文本匹配相似度，基于單詞權(quán)重計(jì)算出的代碼相似度更高。因此，本文選用TF-IDF算法計(jì)算代碼之間的相似程度。

1.2 修復(fù)模板挖掘

修復(fù)信息的獲取及預(yù)處理是修復(fù)模板挖掘的基礎(chǔ)。因此，本節(jié)基于篩選出的代碼對(duì)，提取從bug到fixed的修改序列，并采用差異節(jié)點(diǎn)追蹤算法完善修復(fù)信息的語義。在此基礎(chǔ)上，對(duì)同構(gòu)的修改序列進(jìn)行整理歸納得出修復(fù)模板。

代碼對(duì)的修改序列提取采用抽象語法樹差異分析提取工具Gumtree[8]實(shí)現(xiàn)，但該工具不能有效處理差異點(diǎn)是同一父節(jié)點(diǎn)的情況。例如，若從bug代碼段到fixed代碼段的修改序列是在同一個(gè)父節(jié)點(diǎn)下進(jìn)行的移動(dòng)操作，Gumtree無法獲取到該移動(dòng)操作；若修改序列是對(duì)一整棵子樹的移動(dòng)、刪除或插入，Gumtree會(huì)將整個(gè)動(dòng)作分解為對(duì)各個(gè)節(jié)點(diǎn)的操作，這樣會(huì)增加修改序列的復(fù)雜性。

為提高模板挖掘的準(zhǔn)確性，APRMT在提取修改序列的過程中，通過對(duì)代碼對(duì)的差異節(jié)點(diǎn)進(jìn)行追蹤，將代碼對(duì)中涉及的差異節(jié)點(diǎn)進(jìn)行完整輸出，并對(duì)連續(xù)關(guān)聯(lián)的操作進(jìn)行整合，有效避免了上述Gumtree的缺點(diǎn)。

在獲取到具有完整修復(fù)語義信息的修改序列后，對(duì)具有相同構(gòu)造的修改序列進(jìn)行歸納整理，總結(jié)出修復(fù)模板。APRMT最終確定了11個(gè)修復(fù)模板，各模板的名稱、樣式及模板操作元素如表1所示。

1.3 模板操作元素

修復(fù)模板是對(duì)抽象語法樹的修復(fù)描述，包括節(jié)點(diǎn)的更新(update)、刪除(delete)、移動(dòng)(move)以及插入(insert)等操作。模板操作元素對(duì)應(yīng)于程序缺陷的缺陷類型與目標(biāo)修復(fù)類型，即以上4種操作的操作對(duì)象及其結(jié)果的類型。例如表1中的修復(fù)模板變量替換，模板樣式中var1和var2為該修復(fù)模板的模板操作元素，其中var1表示缺陷模板操作元素，var2表示目標(biāo)模板操作元素。本文挖掘的修復(fù)模板中這2個(gè)模板操作元素的類型是一致的，所以在表1第3列均用同一類型表示。從表1可以看出，修復(fù)模板的模板操作元素類型包括變量、語句、方法、變量類型以及二元操作符等。

APRMT對(duì)模板操作元素的使用場景涉及以下2種：①在修復(fù)程序時(shí)通過計(jì)算缺陷代碼類型與缺陷模板操作元素的相似度生成模板池；②在運(yùn)用修復(fù)模板修復(fù)程序缺陷時(shí)，利用目標(biāo)模板操作元素從缺陷程序中搜索有效的修復(fù)信息，完成程序的自動(dòng)修復(fù)。

2 APRMT程序自動(dòng)修復(fù)

在挖掘的11個(gè)修復(fù)模板的基礎(chǔ)上，本文提出了一種程序自動(dòng)修復(fù)方法，其框架如圖1所示。該方法利用常用的缺陷定位工具Gzoltar[9]結(jié)合測(cè)試用例給出代碼語句的可疑度列表，針對(duì)可疑度列表中的各可疑缺陷代碼語句，根據(jù)缺陷代碼類型分析其可能適用的修復(fù)模板，得到模板池。再從模板池中依次取出模板，依據(jù)最近最相關(guān)策略選擇模板操作元素，修改缺陷代碼，生成代碼變體。最后驗(yàn)證代碼變體能否通過測(cè)試用例，以確定程序缺陷是否被成功修復(fù)。

表1 挖掘的修復(fù)模板Table 1 Mined repair template

圖1 基于模板的程序自動(dòng)修復(fù)框架Figure 1 Template-based program automatic repair framework

下面詳細(xì)討論修復(fù)模板的選擇、最近最相關(guān)策略以及程序自動(dòng)修復(fù)。

2.1 修復(fù)模板的選擇

利用缺陷定位工具Gzoltar可將缺陷定位到代碼行，但無法定位此代碼行產(chǎn)生缺陷的元素。APRMT結(jié)合精確編譯錯(cuò)誤信息給出的元素信息，精準(zhǔn)定位到缺陷代碼位置。如表1所示，每個(gè)修復(fù)模板都具有其模板操作元素。APRMT根據(jù)缺陷代碼與缺陷模板元素的相似度生成多個(gè)修復(fù)模板，按其相似度的高低，生成模板池，并依次對(duì)缺陷程序進(jìn)行修復(fù)，直到將程序缺陷成功修復(fù)，或者修復(fù)時(shí)間達(dá)到上限為止。

2.2 最近最相關(guān)策略

APRMT在運(yùn)用修復(fù)模板修改缺陷代碼的抽象語法樹并生成缺陷代碼變體時(shí)，修復(fù)模板中目標(biāo)模板操作元素的搜索空間是缺陷程序本身。本文提出了一種最近最相關(guān)策略，從缺陷程序源代碼中搜索可用于該缺陷修復(fù)的代碼元素。

最近最相關(guān)策略是指運(yùn)用從模板池中取出的修復(fù)模板對(duì)缺陷代碼抽象語法樹進(jìn)行修改時(shí)，缺陷目標(biāo)的修復(fù)代碼元素的選擇依據(jù)。修復(fù)模板在進(jìn)行更新(update)、刪除(delete)、移動(dòng)(move)以及插入(insert)操作時(shí)，修復(fù)目標(biāo)模板操作元素從原程序中，按照與缺陷代碼距離最近、相似程度最高的原則進(jìn)行挑選。這樣既保證了無外來元素的添加，還能提高修復(fù)模板的修復(fù)效率。例如，APRMT利用Gzoltar與編譯定位到的具體缺陷代碼與缺陷模板操作元素的相似程度，匹配參數(shù)替換模板。但是參數(shù)在上下文中會(huì)有眾多的選擇，無法確保哪個(gè)參數(shù)是能夠修復(fù)缺陷的，如果采用枚舉策略，時(shí)間成本會(huì)非常高，修復(fù)缺陷的效率很低。因此，APRMT提出最近最相關(guān)策略，可減少時(shí)間成本，提高修復(fù)效率。

2.3 程序自動(dòng)修復(fù)的實(shí)現(xiàn)

APRMT的實(shí)現(xiàn)借助了Astor[10]工具。Astor是一個(gè)基于驗(yàn)證的程序自動(dòng)修復(fù)框架，其中包含了Gzoltar缺陷定位與Defects4J[11]的數(shù)據(jù)集。該框架提供的可擴(kuò)展點(diǎn)包括：故障定位算法、修改點(diǎn)選取策略、操作符選擇策略、修改點(diǎn)的粒度、成分池定義、操作符空間定義、檢索策略。將APRMT擴(kuò)展到Astor中，可采用：①故障定位算法，使用Gzoltar庫的故障定位算法；②修改點(diǎn)選取策略，對(duì)于APRMT，缺陷代碼行即修改點(diǎn)，優(yōu)先選取可疑度最高的代碼行作為修改點(diǎn)；③操作符選擇策略，對(duì)于APRMT，一個(gè)修復(fù)模板就是一個(gè)操作符，根據(jù)所選的修改點(diǎn)選擇相應(yīng)的操作符。

將APRMT擴(kuò)展到Astor中需要從以下4個(gè)方面進(jìn)行改進(jìn)。

(1)修改點(diǎn)的粒度。Astor涉及的修改點(diǎn)包括語句粒度級(jí)別、表達(dá)式級(jí)別和二元操作符級(jí)別。本文根據(jù)挖掘出的11個(gè)模板，對(duì)Astor從方法調(diào)用級(jí)別、變量級(jí)別和變量類型級(jí)別進(jìn)行擴(kuò)展。例如jGenProg[12]方法使用插入操作時(shí)，修改點(diǎn)為語句，作為插入的成分也是語句。但對(duì)于APRMT中的模板，修改點(diǎn)和修復(fù)成分的粒度可以不相同。例如，參數(shù)添加操作符的修改點(diǎn)粒度為方法調(diào)用級(jí)別，但插入的成分粒度為變量級(jí)別。因此在此處進(jìn)行一個(gè)特殊的擴(kuò)展，直接在Astor原項(xiàng)目代碼中進(jìn)行修改，使修改點(diǎn)的成分粒度與用于生成代碼變體的成分池粒度區(qū)分開來。

(2)成分池定義。成分池與修改點(diǎn)粒度相對(duì)應(yīng)，Astor原有的成分池包括語句池、表達(dá)式池和二元操作符池。根據(jù)擴(kuò)展的修改點(diǎn)粒度，對(duì)成分池進(jìn)行相應(yīng)擴(kuò)展，添加了調(diào)用方法池和變量池。

(3)操作符空間定義。對(duì)于APRMT，一個(gè)修復(fù)模板即一個(gè)操作符。本文將表1所示的11個(gè)修復(fù)模板作為操作符擴(kuò)展到Astor中。

(4)檢索策略。Astor僅針對(duì)給定粒度的可疑代碼元素創(chuàng)建修改點(diǎn)，操作符從給定粒度的成分池中選擇出現(xiàn)次數(shù)最多的成分，對(duì)修改點(diǎn)進(jìn)行修改。在APRMT中采用最近最相關(guān)策略，利用可疑代碼元素，在成分池中選擇合適的成分，作為程序修復(fù)的代碼。

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)集

本文選取Defects4J上的數(shù)據(jù)集作為被測(cè)程序進(jìn)行實(shí)驗(yàn)驗(yàn)證，如表2所示。由于程序自動(dòng)修復(fù)需要利用測(cè)試用例進(jìn)行錯(cuò)誤定位，并驗(yàn)證修復(fù)是否成功，因此選取提供JUnit[13]測(cè)試用例的項(xiàng)目。表2中列出了各項(xiàng)目含有的缺陷數(shù)及其測(cè)試用例個(gè)數(shù)。

表2 Defects4J缺陷程序集合參數(shù)Table 2 Defective program parameters of Defects4J

3.2 實(shí)驗(yàn)環(huán)境

APRMT借助Astor框架實(shí)現(xiàn)程序的自動(dòng)修復(fù)。APRMT利用Gzoltar定位到缺陷語句所在的行，結(jié)合編譯錯(cuò)誤定位到缺陷代碼所在的列，給出缺陷代碼具體的位置信息。再按照可疑度排序依次取出缺陷代碼，利用模板選擇規(guī)則生成該缺陷對(duì)應(yīng)的模板池。最后按照最近最相關(guān)策略從原缺陷程序中搜索目標(biāo)模板操作元素進(jìn)行缺陷代碼的修復(fù)，利用測(cè)試用例驗(yàn)證是否成功修復(fù)。本文實(shí)驗(yàn)在Windows10操作系統(tǒng)上運(yùn)行，每個(gè)程序缺陷的修復(fù)時(shí)間設(shè)為60 min，最大修復(fù)次數(shù)為100次。

3.3 實(shí)驗(yàn)結(jié)果與分析

APRMT使用的模板是從StackOverflow中挖掘的11個(gè)修復(fù)模板，見表1。

不同修復(fù)工具對(duì)Defects4J的修復(fù)結(jié)果如表3所示，其中數(shù)字代表該項(xiàng)目上修復(fù)成功的缺陷個(gè)數(shù)。修復(fù)成功是指測(cè)試用例在修復(fù)后的代碼上執(zhí)行通過，且人工驗(yàn)證了該修復(fù)結(jié)果與目標(biāo)修復(fù)結(jié)果語義一致。

表3 不同修復(fù)工具修復(fù)結(jié)果Table 3 Repair results of different repair tools

由表3可以看出，APRMT成功修復(fù)了26個(gè)缺陷，共耗時(shí)約80 min，平均每個(gè)缺陷修復(fù)時(shí)間為3.1 min，由于缺陷定位不屬于程序自動(dòng)修復(fù)，所以將修復(fù)缺陷的開始時(shí)間設(shè)置為缺陷定位完成之后，未將錯(cuò)誤定位消耗的時(shí)間計(jì)入修復(fù)缺陷時(shí)間內(nèi)。

SOFIX修復(fù)了23個(gè)缺陷，主要原因是其模板挖掘過程中抽象語法樹的分析工具丟失了部分修改操作，造成挖掘的修復(fù)信息不準(zhǔn)確，且SOFIX采用枚舉方法進(jìn)行修復(fù)，可能導(dǎo)致無法在一定時(shí)間內(nèi)完成程序修復(fù)，甚至部分缺陷的修復(fù)需要生成4 196個(gè)代碼變體并逐個(gè)驗(yàn)證，單純修復(fù)這一個(gè)缺陷就需耗費(fèi)大約2 h，雖然最后將缺陷修復(fù)，但是卻失去了程序自動(dòng)修復(fù)的意義。Nopol[14]的修復(fù)僅針對(duì)if-then-else語句中存在的缺陷，因此其只修復(fù)了5個(gè)缺陷，平均每個(gè)耗時(shí)9 min，但是其正確修復(fù)的缺陷數(shù)量及類型限制了程序自動(dòng)修復(fù)的效率。HistoricalFix[15]是在假定缺陷位置已知的情況下進(jìn)行的程序修復(fù)，這將降低程序修復(fù)難度，但其平均每個(gè)缺陷的修復(fù)時(shí)間為20 min，修復(fù)效率不高，而且HistoricalFix收集到的人工修復(fù)信息具有一定的局限性[16]。

此外，為了證明APRMT的有效性，與基于遺傳規(guī)劃的程序自動(dòng)修復(fù)工具jGenProg做了對(duì)比實(shí)驗(yàn)。如表4所示，APRMT和jGenProg對(duì)8種缺陷都修復(fù)成功，但在時(shí)間成本方面，jGenProg大約是APRMT的4倍；在修復(fù)效果方面，APRMT由于結(jié)合了修復(fù)模板中的修復(fù)信息，只需生成135個(gè)補(bǔ)丁便可完成程序自動(dòng)修復(fù)，而jGenProg則需762個(gè)補(bǔ)丁，是APRMT的5.6倍。由此可見，APRMT無論是在時(shí)間效率上，還是修復(fù)效果上都遠(yuǎn)超jGenProg。

由上述分析可知，APRMT的修復(fù)效率是比較穩(wěn)定的，主要原因有2個(gè)方面:一是在修復(fù)模板挖掘的過程中，APRMT關(guān)注的修復(fù)信息不局限于if-then-else條件語句，并且對(duì)修復(fù)信息進(jìn)行預(yù)處理，盡可能挖掘更多的修復(fù)模板，保證修復(fù)模板的有效性與完整性，增加了修復(fù)缺陷個(gè)數(shù)；二是在程序自動(dòng)修復(fù)過程中，APRMT結(jié)合最近最相關(guān)策略，搜索目標(biāo)修復(fù)模板操作元素，避免了枚舉策略的耗時(shí)，提高了程序修復(fù)效果和效率。

表4 APRMT與jGenProg的對(duì)比實(shí)驗(yàn)結(jié)果Table 4 Results of the APRMT vs. jGenProg.

4 結(jié)論

本文提出了一種改進(jìn)的基于模板的程序自動(dòng)修復(fù)方法APRMT。在修復(fù)模板挖掘中，APRMT采用正則匹配消除修復(fù)信息中的無用信息，分析抽象語法樹時(shí)，對(duì)差異節(jié)點(diǎn)進(jìn)行跟蹤，避免了修改動(dòng)作的缺失，提高了挖掘修復(fù)信息的準(zhǔn)確性與完整性。在程序自動(dòng)修復(fù)中，APRMT利用最近最相關(guān)策略，搜索需要修復(fù)的目標(biāo)模板操作元素，實(shí)現(xiàn)程序自動(dòng)修復(fù)。實(shí)驗(yàn)表明，APRMT能在較短的時(shí)間內(nèi)修復(fù)Defects4J上的26個(gè)缺陷，程序自動(dòng)修復(fù)的效果與效率有了較大提升。