基于變異和約束求解的程序缺陷自動修復(fù)方法

董 蘭，洪 玫，伍 佳

(四川大學(xué) 計算機學(xué)院(軟件學(xué)院)，四川 成都 610065)

0 引 言

目前軟件缺陷自動修復(fù)技術(shù)[1]主要有基于啟發(fā)式搜索、語義約束、人工修復(fù)模板、統(tǒng)計分析等方法，其中大部分方法都通用的，缺陷修復(fù)的召回率和準(zhǔn)確率不高[2]。對于基于人工修復(fù)模板的方法具有針對性，只能針對常見、特征明確的缺陷類型。而基于測試的缺陷修復(fù)方法則依賴于通過的測試數(shù)據(jù)，而在Defects4 J庫中有95%以上的程序缺陷在被修復(fù)之前沒有相應(yīng)的未通過測試，而測試覆蓋率與補丁質(zhì)量成正相關(guān)，挖掘到的程序規(guī)約信息有限，約束求解效果不好[2]。

本文針對Java程序中出現(xiàn)頻率較高的條件語句的相關(guān)缺陷修復(fù)問題，將啟發(fā)式搜索方法與語義約束求解方法相結(jié)合，提出一個更高效的解決方案。針對條件語句缺失錯誤，基于約束求解，通過收集程序語義信息，采用基于組件的程序合成技術(shù)，生成候選條件表達式。同時，針對條件語句邏輯表達式錯誤，首先采用變異技術(shù)，生成候選補??；其次，對于條件語句邏輯表達式錯誤中不能利用變異技術(shù)修復(fù)的缺陷，再使用約束求解方法生成補丁。最后驗證補丁的有效性。該方案解決了Java程序自動修復(fù)中的重要問題，并在修復(fù)效率上有所提高，值得借鑒和參考。

1 相關(guān)工作

在自動軟件缺陷修復(fù)技術(shù)中，常用的修復(fù)方法是基于啟發(fā)式搜索的技術(shù)，該方法通過改變原始缺陷程序生成新程序作為候選補丁。代表性研究有GenProg、RSRepair、Kail等方法。GenProg[3]采用抽象語法樹、遺傳算法，運用交叉、變異算子等生成程序候選補丁。RSRepair[4]選擇隨機搜索來指導(dǎo)生成-驗證過程，而Kail[5]是一種試圖通過刪除潛在的不必要但有害的功能來修復(fù)程序的技術(shù)。

基于語義約束的缺陷修復(fù)方法，其綜合應(yīng)用缺陷定位、天使調(diào)試、約束求解、程序合成等多種技術(shù)[6]來修復(fù)補丁，代表性研究有SemFix、Angelix和Nopol等方法。SemFix[7-9]綜合使用天使調(diào)試和基于組件的程序合成算法，約束求解器求解獲得程序補丁。Angelix[10]旨在保持可伸縮性的同時綜合多行修復(fù)。而Nopol[11，12]合成了在條件或循環(huán)語句中發(fā)生的一條更改條件組成的修復(fù)，利用天使修復(fù)定位獲得天使值，通過合成條件表達式修復(fù)缺陷。

針對Java程序缺陷的修復(fù)方法，除了Nopol方法之外，還有針對修復(fù)Java語言的內(nèi)存溢出、資源泄露、空指針引用、內(nèi)存溢出等缺陷的FootPatch方法[13]，以及高精度的條件語句綜合技ACS[14]，針對空指針、數(shù)據(jù)越界以及類型強轉(zhuǎn)缺陷的Genesis自動修復(fù)技術(shù)[15]。

由于單一的自動缺陷修復(fù)方法不能保證任何類型的缺陷都可以成功修復(fù)[16]，因此，針對特定缺陷類型，考慮綜合的自動化修復(fù)方法就有一定的研究價值。本文針對Java程序中條件語句邏輯錯誤和條件語句缺失錯誤兩類缺陷，借鑒啟發(fā)式搜索中的變異方法和語義驅(qū)動的約束求解、組件合成等方法，并對這些方法進行綜合運用，以提高缺陷修復(fù)率和補丁精度。

2 問題描述和基本思路

研究者通過挖掘和分析7個大型開源Java項目的歷史缺陷修復(fù)記錄，總結(jié)了9大類、27個缺陷修復(fù)模式。其中，最常見的是IF條件相關(guān)(IF)，占19.7%～33.9%[17]。而IF-CC和 IF-APC所對應(yīng)的條件語句錯誤和條件語句缺失兩類缺陷在實際缺陷中占據(jù)較大比例，見表1。

表1 Java程序中的缺陷修復(fù)模式

因此針對Java程序中的條件語句邏輯錯誤和條件語句缺失錯誤的常見缺陷，探索缺陷自動修復(fù)方法。條件語句邏輯表達式錯誤是指條件表達式存在邏輯錯誤，導(dǎo)致程序無法執(zhí)行到期望的分支；條件語句缺失錯誤是指在執(zhí)行某些操作之前，缺少前置條件的檢查，比如檢測空指針。

針對上述兩類條件語句相關(guān)的缺陷，本文采用收集測試信息(G1)，使用本文提出的方法生成滿足的候選補丁(G2)，最后通過測試套件驗證候選補丁(G3)這3個階段過程，實現(xiàn)缺陷的自動修復(fù)。首先通過執(zhí)行相關(guān)的測試用例，收集程序執(zhí)行時待修復(fù)程序位置處可訪問的數(shù)據(jù)變量和對應(yīng)的值，形成待求解的修復(fù)方程式；其次，確定可修復(fù)程序位置的語句類型以采用不同的補丁生成方案進行缺陷修復(fù)。如果待修復(fù)位置是條件語句表達式缺陷，先采用變異技術(shù)產(chǎn)生候選補丁，如果沒有相符合的補丁，再使用基于約束求解方法，合成條件表達式；如果是條件語句缺失缺陷，直接應(yīng)用基于約束求解方法生成表達式，并將生成的表達式作為前置條件添加在源程序中。最后，運行測試用例，再次進行補丁驗證。整體方案流程如圖1所示。

圖1 方案流程

3 基于測試數(shù)據(jù)形成缺陷修復(fù)方程式

根據(jù)測試用例的執(zhí)行，收集與待修復(fù)缺陷相關(guān)的測試用例執(zhí)行過程中的上下文信息。

3.1 條件表達式實際輸入數(shù)據(jù)收集

在程序執(zhí)行過程中，收集執(zhí)行到待修復(fù)條件語句exp-patch之前所有可訪問的變量以及變量值，包括基本類型數(shù)據(jù)和面對對象程序的特定數(shù)據(jù)，主要包括局部變量、成員變量、方法參數(shù)以及它們對應(yīng)的值。將收集到的數(shù)據(jù)稱為輸入數(shù)據(jù)，用Il，m，n，其中，l表示待修復(fù)條件表達式exp-patch所在位置，n和m分別表示第n個測試用例的第m次執(zhí)行。除此之外，還增加3個基準(zhǔn)常數(shù){-1，0，1}來豐富Il，m，n， 其它的數(shù)據(jù)都可以基于這3個基準(zhǔn)常數(shù)構(gòu)建。假設(shè)l位置在可修復(fù)的程序位置范圍內(nèi)有a個基本變量和一組對象集合O(共O個對象)，則Il，m，n包含的數(shù)據(jù)如下：

a個基本變量以及變量對應(yīng)的變量值。如：a→10；

w個boolean值，分別表示O個對象是否為空。如：obj1=null→false；

object中對象各自對應(yīng)類的狀態(tài)查詢方法及其輸出，如obj2.size()→5；

常數(shù)，如0，1，-1。

3.2 條件表達式期望輸出結(jié)果收集

當(dāng)執(zhí)行完待修復(fù)的條件表達式exp-patch時，能使所有測試用例能執(zhí)行通過的值稱為條件表達式的期望輸出。取值范圍為{true，false}，用Ol，m，n來表示期望輸出。如果l位置為條件語句，對于測試用例執(zhí)行是失敗的，天使值即為exp-patch期望輸出，天使值(angelicValue)指可以讓失敗的測試用例執(zhí)行成功的值，取值范圍為{true，false}；如果是成功的測試用例，條件表達式exp-patch的實際輸出即為期望輸出。如果l位置為非條件語句，針對失敗的測試用例，Ol，m，n其對應(yīng)值均為false，對于成功的測試用例，Ol，m，n均為true。

3.3 缺陷修復(fù)方程式形成

根據(jù)上述實際輸入的數(shù)據(jù)Il，m，n和期望的輸出結(jié)果Ol，m，n， 可以形成式(1)的待求解的修復(fù)方程式F，定義為

(1)

所有的 都包含了表達式exp-patch應(yīng)該滿足的程序語義約束，可以使用約束求解器對該約束進行求解，合成候選補丁。

4 基于變異分析技術(shù)的程序候選補丁生成

變異分析一般用于檢測測試套件對程序缺陷的發(fā)現(xiàn)能力[18]，其思路主要是對原程序P中引入小的代碼修改，形成缺陷的變體P′， 然后運行測試套件TS，觀察測試套件在原程序P和程序變體P′中的執(zhí)行情況，查看測試套件是否能夠檢測到引入的缺陷。其中，引起代碼修改的操作被定義為變異算子。

基于文獻的研究[19]，對于條件語句缺陷自動修復(fù)，將變異技術(shù)應(yīng)用其中。如果待修復(fù)的表達式exp-patch為if條件語句時，使用預(yù)先設(shè)計的變異算子，在該條件表達式中植入小的代碼變更，產(chǎn)生所有可能的一階程序變體P′bug， 作為候選補丁。本文依據(jù)修復(fù)錯誤的條件三要素：條件子句、變量和操作符，設(shè)計了如下變異算子。

變異算子1：否定條件表達式，如if(a>0‖b<0) 變異成if(！a>0‖b<0)；

變異算子2：替換同類運算符，包括運算符、關(guān)系運算符和邏輯運算符，如if(a>0‖b<0) 變異成if(a>0‖b>0)；

變異算子3：移除條件表達式中的一個條件子句，如if(a<0‖b<0) 變異成if(a<0)；

在應(yīng)用變異算子3時，還可以考慮失敗的測試用例所對應(yīng)的天使值，如果所有失敗測試用例的天使值都為true，則表示失敗測試用例執(zhí)行完條件表達式的輸出應(yīng)該由false轉(zhuǎn)變?yōu)閠rue；如果都為false，則表示失敗測試用例執(zhí)行完條件表達式的輸出應(yīng)該由true轉(zhuǎn)變?yōu)閒alse。通過移除一個條件子句來收縮、擴張條件表達式的判定范圍，具體的移除方式為：收縮判定范圍：if(clause‖clause1)>=if(clause)。 擴張判定范圍：if(clause&&clause1)>=if(clause)。

本文只使用Pbug的一階變體作為候選補丁，比如，對條件表達式if(x>0‖y<0) 進行變異，所有可能的候選補丁見表2。

表2 基于變異算子生成補丁

由于利用變異技術(shù)產(chǎn)生條件表達式的候選補丁時，可能會生成大量無效的程序變體。為了避免這種情況，此時，3.3節(jié)得到的修復(fù)方程式可用于初步篩選變異生成的程序變體，使?jié)M足程序語義約束的變體作為候選補丁，以減少待驗證補丁的數(shù)量。

5 基于約束求解的程序補丁合成方法

對于上述候選補丁不能修復(fù)缺陷的情況，作為補充本文還提供一種語義驅(qū)動的補丁生成方法。利用自動化程序合成技術(shù)，將補丁生成問題轉(zhuǎn)化為約束求解的問題，將求得解轉(zhuǎn)化為程序補丁。通過運行測試用例，獲取一系列的<輸入，期望輸出>對，作為I/O的Oracle；定義一組用于合成程序的基礎(chǔ)組件，如操作符、常數(shù)值、函數(shù)方法等；合成過程以一系列<輸入，期望輸出>對和基礎(chǔ)組件作為輸入，輸出一段滿足所有<輸入，期望輸出>對的程序[9]。

假設(shè)待修復(fù)的條件表達式exp-patch的實際輸入數(shù)據(jù)包含兩個變量x和y以及常數(shù)0，獲取的I/OOracle為 <{x=1，y=2，0}，true>、 <{x=2，y=1，0}，false>， 可用基礎(chǔ)組件C={+、-、>、<}。 一種有效的合成過程如圖2所示，用矩形表示組件，并用位置號標(biāo)識(標(biāo)簽“l(fā)oc”)，邊表示如何將在給定位置生成的值用作在另一位置的輸入(與每個位置關(guān)聯(lián)的標(biāo)簽“input”)，式(1)生成約束表達式之后，SMT求解器為與每個位置關(guān)聯(lián)的變量輸入找到適當(dāng)?shù)闹怠?/p>

圖2 基于約束求解的程序補丁合成示例

假設(shè)合成條件表達式exp-patch使用一組基礎(chǔ)組件 {f1，f2，…，fn}，fi表示第i個組件，Ii表示組件的輸入，ri表示組件的輸出。所有組件的輸入集合和輸出集合分別為下述I和R

待求解條件表達式的一組實際輸入為I0(即Il，m，n)， 對應(yīng)期望輸出為r(即Ol，m，n)， 所有的輸入輸出集合為

IO={I∪R∪I0{r}}

定義位置變量

LOC={locx|x∈IO}

locx表示IO中的每個元素x的索引位置；取值變量

V={vx|x∈IO}

vx表示IO中的每個元素x的取值。對于每個測試用例的每次執(zhí)行，位置變量代表了補丁的組成結(jié)構(gòu)，應(yīng)該保持一致。取值變量則被SMT求解器使用，用于保證合成的程序符合I/Ooracle。

LOC應(yīng)該保證語法約束和語義約束[7]。語法約束規(guī)定了在程序語法結(jié)構(gòu)上待求解的條件表達式exp-patch應(yīng)該滿足的要求，其定義如式(2)所示

(2)

式中：φfixed該約束表示對于待求解條件表達式的實際輸入I0中的第i個元素，其位置變量loc的值為i； 對于待求解條件表達式的期望輸出r中的元素，其位置變量loc的值M。φoutput(R)該約束限制一個基礎(chǔ)組件fi所定義的中間變量r；其位置變量loc，應(yīng)該在 |I0|+1 到M之間。φinput(I) 表示不同的基礎(chǔ)組件能夠處理不同類型的數(shù)據(jù)，該約束對每個基礎(chǔ)組件所使用的數(shù)據(jù)x的數(shù)據(jù)類型進行限制。定義type(x) 方法可以返回與x具有相同數(shù)據(jù)類型的數(shù)據(jù)，基礎(chǔ)組件的輸入數(shù)據(jù)x只能取自于這些數(shù)據(jù)，即LOCx=LOCy。φcons(LOC，R) 該約束表示每個基礎(chǔ)組件所定義的變量都應(yīng)該有不同的位置變量，以便在其中使用該變量時，可以索引到。φacyc(LOC，I，R) 該約束則限制了在同一個位置的元素應(yīng)該具有相同的數(shù)據(jù)值。

除了語法約束之外，LOC還應(yīng)滿足一定的語義約束。其定義如式(3)所示

(3)

式中：φlib(I，R) 該約束表示任意一個基礎(chǔ)組件的輸入vIi經(jīng)過基礎(chǔ)組件所定義的計算fi后，輸出值為vri，φconn(LOC，I0，r，I，R) 該約束限制了在同一個位置的元素應(yīng)該具有相同的數(shù)據(jù)值。

結(jié)合語法約束和語義約束，對于I/Ooracle中所有的<輸入，期望輸出>對，LOC需要滿足的完整約束如式(4)所示

(4)

利用SMT求解器對約束θ求解，若LOC為該約束的解，則根據(jù)LOC和定義的基本組件，可以構(gòu)造出滿足程序約束的條件表達式exp-patch。

如果可修復(fù)程序位置為if條件語句，則直接使用表達式exp-patch對原始表達式進行替換，形成候選的程序補?。蝗绻麨榉莍f條件語句，則將表達式exp-patch作為前置條件添加，形成候選補丁。

6 實驗驗證

實驗基于上述問題設(shè)計實現(xiàn)了一個條件語句缺陷自動修復(fù)工具原型MSFix，進行方案的可行性和有效性驗證。

實驗對象選擇Defects4 J[20]數(shù)據(jù)集中的14個Java項目的62個條件語句缺陷，其中條件語句錯誤缺陷41個，條件語句缺失缺陷21個，見表3。

表3 實驗對象信息

實驗采用召回率和準(zhǔn)確率來評價缺陷修復(fù)效果。在修復(fù)一個缺陷的過程中，如果能夠找到一個有效補丁能通過所有的測試，則認為該缺陷被成功修復(fù)，召回率計算方式如式(5)所示

(5)

在修復(fù)缺陷的過程中，如果一個有效補丁正確修復(fù)了缺陷，則認為該補丁是正確的補丁，補丁準(zhǔn)確率計算方式如式(6)所示

(6)

6.1 可行性實驗——Java程序中條件語句缺陷的修復(fù)

通過運行MSFix，對上述的缺陷進行修復(fù)，返回MSFix的修復(fù)結(jié)果。如果缺陷修復(fù)成功，將MSFix修復(fù)的補丁與Defects4 J提供的補丁進行比較，驗證補丁的有效性。由表4的實驗結(jié)果可知，在上面提供的項目中69個條件語句缺陷來說，MSFix能夠修復(fù)39個缺陷，并且整體的召回率為62.90%。

表4 MSFix的整體實驗結(jié)果

在62個條件語句缺陷中，也有23個缺陷沒有修復(fù)成功。分析其修復(fù)失敗的原因主要是：

(1)由于本文方案輸入的可疑語句是通過可疑分數(shù)進行定位的，可疑語句定位時會計算可疑分數(shù)閾值，并舍棄可疑分數(shù)低于閾值的程序方法，只對剩余方法中的程序語句進行分析。由于部分缺陷(如 Math-26)的測試用例不夠充足，缺少失敗測試用例對錯誤語句的覆蓋，導(dǎo)致錯誤語句所在的程序方法的可疑分數(shù)較低。在進行可疑語句定位時，含有錯誤語句的程序方法被舍棄，最終可疑語句列表中沒有真正錯誤的語句。

(2)由于本文方案輸入的可疑語句是通過缺陷定位得到的。在定位可修復(fù)程序位置過程中，期望每個失敗的測試用例都存在一個使其能夠執(zhí)行通過的天使值。由于部分缺陷(如Lang-16)的一個失敗測試用例中存在多個assert斷言，這些assert斷言覆蓋了if結(jié)構(gòu)的then分支和else分支。在使用true/false替換if條件表達式后，重新運行這個失敗的測試用例，沒有辦法同時滿足多個assert斷言。因此，無法找到這個失敗測試用例的天使值，導(dǎo)致可修復(fù)程序位置定位失敗。通過以上分析可知，測試用例的質(zhì)量不高是導(dǎo)致缺陷修復(fù)失敗的重要原因。針對情況(1)，可以通過額外增加失敗的測試用例來提高錯誤語句的覆蓋率，使其能夠出現(xiàn)在可疑語句列表中，或者排名更靠前。針對情況(2)，可以通過拆分失敗的測試用例，使每個測試用例中只有一個assert斷言，在可修復(fù)程序位置定位中，更可能找到使失敗測試用例都通過天使值。

6.2 有效性實驗——缺陷修復(fù)效果與其它方法的對比

目前針對修復(fù)Java程序缺陷的方案中，Nopol[11，12]、jGenProg[3]和jKali[5]這3種工具比較有代表性，在比較多的相關(guān)研究中引用。因此，在方案有效性實驗中，選擇這3種工具作為比較對象。對上述選擇的62個條件語句缺陷，分別應(yīng)用上述的3個工具和MSFix進行自動修復(fù)，記錄并分析每個工具的修復(fù)效果，計算每個工具的缺陷召回率和準(zhǔn)確率，并進行分析。表5展示了4種方法的整體修復(fù)結(jié)果。可以看出MSFix和上面3種修復(fù)工具相比，其修復(fù)的正確補丁數(shù)量是最多的，一共修復(fù)了21個，而其它3個工具卻修復(fù)沒有超過有效補丁數(shù)量的一半。并且MSFix的召回率和準(zhǔn)確率都分別達到了62.90%和53.85%。其它3種工具的召回率和準(zhǔn)確率都比較偏低。

表5 4種工具對比的整體實驗結(jié)果

使用Venn圖來展示這4個工具所修復(fù)缺陷之間的交叉重疊情況。由表5和圖3可知，jGenProg和jKal的召回率相對較低，并且被jGenProg和jKal這兩個工具修復(fù)的缺陷都能夠被Nopel和MSFix修復(fù)。MSFix和與Nopel相比，MSFix能夠修復(fù)17個Nopel無法修復(fù)的缺陷，召回率提高了22.58%。

圖3 4個工具修復(fù)缺陷韋恩

由于jGenProg和jKali在基于各自定義的操作修改缺陷程序形成候選補丁時，對所有類型的缺陷都執(zhí)行相同的修復(fù)操作。雖然能夠修復(fù)條件語句缺陷，但相比于MSFix和Nopol，jGenProg和jKali，缺少更有針對性的分析。因此，在修復(fù)條件語句缺陷時，jGenProg和jKali生成的有效補丁相對較少，缺陷修復(fù)較低。另外，Nopol在生成候選補丁時，只使用了基于約束求解的補丁生成方法。本文方案則在此基礎(chǔ)之上，增加、并且優(yōu)先使用變異技術(shù)生成程序補丁，綜合使用兩種補丁生成方法，使得對條件語句缺陷具有更高的修復(fù)率。

在補丁準(zhǔn)確率方面，4個工具都基于測試套件進行修復(fù)，但本文方法在生成程序補丁時，優(yōu)先考慮使用變異技術(shù)對原始表達式進行變異，基于真實的缺陷修復(fù)記錄，為條件語句定義合適的變異算子，該方法更可能產(chǎn)生符合開發(fā)人員預(yù)期的程序補丁。因此，MSFix能夠優(yōu)先輸出正確的程序補丁，補丁準(zhǔn)確率相對其它3種方法都有所提高。

7 結(jié)束語

缺陷自動修復(fù)方法是幫助開發(fā)人員減少調(diào)試成本的有效技術(shù)，為了修復(fù)Java程序中常見的條件語句缺失缺陷和條件語句邏輯錯誤缺陷，本文提出了基于變異分析和約束求解的程序補丁合成技術(shù)，實驗結(jié)果表明本文方案能夠修復(fù)真實的條件語句缺陷，并且相比于現(xiàn)有修復(fù)方法，本文方案具有更好的修復(fù)效果。在相當(dāng)程度上解決了Java程序中條件語句缺陷的自動修復(fù)問題。但本文的研究基于Java程序，對其它語言的適應(yīng)性還有待進一步的實驗驗證。在變異分析中，只采取了3種變異算子，在未來工作中，可以考慮增加更多的變異算子，以提高缺陷修復(fù)的能力；此外實驗結(jié)果表明本方法修復(fù)的補丁和現(xiàn)有的工具相比，修復(fù)的補丁既有重疊的又有獨有的，為了提高缺陷自動修復(fù)的可靠性和完備性，在未來工作中，可以考慮綜合使用補丁修復(fù)的工具，對本文方法做出進一步的改進，以提高補丁修復(fù)率。