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

董 蘭，洪 玫，伍 佳

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

0 引 言

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

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

1 相關工作

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

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

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

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

2 問題描述和基本思路

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

表1 Java程序中的缺陷修復模式

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

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

圖1 方案流程

3 基于測試數據形成缺陷修復方程式

根據測試用例的執行，收集與待修復缺陷相關的測試用例執行過程中的上下文信息。

3.1 條件表達式實際輸入數據收集

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

a個基本變量以及變量對應的變量值。如：a→10；

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

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

常數，如0，1，-1。

3.2 條件表達式期望輸出結果收集

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

3.3 缺陷修復方程式形成

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義位置變量

LOC={locx|x∈IO}

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

V={vx|x∈IO}

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

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

(2)

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

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

(3)

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

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

(4)

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

如果可修復程序位置為if條件語句，則直接使用表達式exp-patch對原始表達式進行替換，形成候選的程序補丁；如果為非if條件語句，則將表達式exp-patch作為前置條件添加，形成候選補丁。

6 實驗驗證

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

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

表3 實驗對象信息

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

(5)

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

(6)

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

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

表4 MSFix的整體實驗結果

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

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

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

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

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

表5 4種工具對比的整體實驗結果

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

圖3 4個工具修復缺陷韋恩

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

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

7 結束語

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