周風順,王林章,李宣東

(計算機軟件新技術國家重點實驗室(南京大學),江蘇 南京 210023)

隨著信息技術的不斷發(fā)展,計算機軟件已經成為現(xiàn)代社會最重要的基礎設施之一.但是由于程序員的疏忽和軟件系統(tǒng)復雜度的增加,這些程序中不可避免地存在缺陷.盡早地發(fā)現(xiàn)并排除這些潛在的缺陷,是學術界和工業(yè)界普遍的共識.程序缺陷自動修復技術可以根據給定的錯誤程序自動生成程序修復候選項,進而修復程序中的缺陷.其修復過程中產生的補丁可以直接用于修改程序,也可以幫助開發(fā)人員改進代碼.因此,程序缺陷自動修復成為我們關注的重點.

程序缺陷自動修復的一般流程包括缺陷定位、候選項生成、驗證及選擇.程序修復方法首先通過缺陷定位方法將給定的帶有缺陷的程序的所有語句按某種規(guī)則排序,得到可疑語句的排列;然后將這些語句作為疑似缺陷逐個傳輸給修復候選項生成算法.修復候選項生成算法會檢測當前缺陷的位置,決定是否能夠輸出候選項:如果能夠,則輸出候選項給測試集進行驗證,通過驗證的候選項將作為結果輸出;若該疑似缺陷的位置無法輸出修復候選項,則從語句排列中獲取下一個可疑語句,重新運行修復候選項生成算法以繼續(xù)尋找潛在的修復候選項.

修復真實缺陷,一直以來是程序缺陷自動修復研究的目標.目前,學術界對現(xiàn)有的修復技術在真實缺陷上的修復能力存在一定爭議[12],關于缺陷修復的討論也有很多.2015年,Qi等人[3]對GenProg和AE兩個工作在105個真實缺陷上的修復進行了手工檢查.其中,Genprog的修復結果中只有兩個是語義正確的,而AE的修復結果中只有3個是語義正確的.由此可見,現(xiàn)有的修復技術存在著修復率低,無法保證修復結果的正確性等問題.

近年來,程序合成技術和機器學習、深度學習等AI技術不斷進步,在軟件工程中有著廣泛的應用.這兩項技術的發(fā)展在解決程序自動修復問題上引起了我們新的思考.程序合成[45]是指從程序語言自動地構造程序,使其滿足特定的規(guī)約.程序合成器通常是在程序空間內進行搜索,以生成滿足各種約束的程序.程序合成通常被使用在代碼補全、軟件開發(fā)、算法設計中[6].近年來,程序合成除了規(guī)約外,還允許用戶額外地提供可能的程序空間框架,一般是語法層面的.這樣的做法有兩點好處:首先,語法為假設空間提供了結構,這可以使搜索的過程更加高效;其次,生成的程序也是可解釋的,因為它們是從語法中衍生出來的.程序合成工具SKETCH[7]首先提出了這個想法,它允許程序員編寫部分程序框架(帶有空白的程序),然后根據規(guī)約自動填補這些空白.深度學習中,長短期記憶網絡(LSTM)[8]是一種特定形式的循環(huán)神經網絡(RNN).LSTM 的關鍵是細胞狀態(tài),細胞的狀態(tài)在整個鏈上運行,只有一些小的線性操作作用于其上,信息很容易保持不變地流過整個鏈.同時,LSTM有一種精心設計的稱為門的結構,可用來選擇式地刪除或添加信息到細胞.LSTM的這些特性使得LSTM廣泛用于序列預測問題.

本文針對現(xiàn)有的修復技術存在的問題,結合程序合成技術和深度學習技術,提出了一種基于程序合成的代碼缺陷自動修復方法.一方面,人工整理常見的缺陷形成缺陷模式并總結修復方式,幫助修復常見的缺陷;另一方面,通過深度學習的方法,從滿足相同規(guī)約的正確程序集中學習正確程序的書寫結構,幫助預測錯誤程序錯誤點的應有的語句結構.在選擇驗證的過程中,我們使用程序合成的方法將樣例程序作為約束,保證合成后代碼的正確性.本文的主要工作在于:

(1) 本文提出了一種基于程序合成的 C/C++程序缺陷自動修復方法,總結了 C/C++程序中常見的錯誤模式,并建立了書寫結構模型.使用缺陷定位方法——基于重寫規(guī)則的定位方式和基于程序頻譜的方式,得到程序中可能的缺陷位置.使用修復選項生成方法——基于重寫規(guī)則的修復選項生成方法和基于預測的修復選項生成方法,得到缺陷的修復選項.

(2) 本文提出了基于程序合成工具 SKETCH[7]的修復選項選擇與確認方法.將帶有修復選項的 C/C++程序轉化為SKETCH代碼,并進行預處理,將該程序的示例程序作為程序的規(guī)約并加入SKETCH代碼.使用SKETCH執(zhí)行程序合成,直到找到滿足規(guī)約的修復,得到正確的修復結果.

(3) 基于上述方法,本文實現(xiàn)了一個C/C++程序缺陷修復的原型工具.

本文第1節(jié)主要介紹基于程序合成的代碼缺陷修復方法的基本框架.第2節(jié)展示實驗結果.第3節(jié)主要介紹相關工作,包括基于搜索的缺陷修復和基于約束求解的缺陷修復.第4節(jié)進行總結和展望.

1 基于程序合成的C/C++程序缺陷自動修復方法

本節(jié)我們提出基于程序合成的C/C++程序缺陷自動修復方法的基本框架(如圖1所示).

Fig.1 Framework of the method圖1 方法框架

程序自動修復的流程包括缺陷定位、候選項生成、候選項驗證.本方法使用缺陷定位方法——基于重寫規(guī)則的定位方法和基于程序頻譜的定位方法,得到程序中可能的缺陷位置;使用修復選項生成方法——基于重寫規(guī)則的修復選項生成方法和基于預測的修復選項生成方法,得到缺陷的修復選項.同時,在修復選項驗證步驟中使用程序合成的方法,保證合成后程序的正確性.該方法分為 3個主要步驟:缺陷定位、修復選項生成、修復選項驗證和一個準備步驟——重寫規(guī)則總結和書寫結構模型構建.

(1) 重寫規(guī)則總結和書寫結構模型構建.

對于重寫規(guī)則,我們對錯誤程序進行整理,總結其中常見的錯誤模式,并人工給出修復方法,將錯誤模式和修復方法配對形成重寫規(guī)則.對于書寫結構模型,我們收集滿足相同規(guī)約的正確程序,提取其中的書寫結構并序列化.將所得的序列化數(shù)據使用長短期記憶模型進行訓練.使用梯度下降算法,當定義的損失函數(shù)在驗證集上的變動小于設定的閾值時停止訓練.將此時的模型用于書寫結構預測.

(2) 缺陷定位.

我們使用基于重寫規(guī)則和基于程序頻譜兩種方式進行缺陷定位.在基于重寫規(guī)則的定位中,我們將錯誤模式與錯誤程序的抽象語法樹進行匹配,得到可能的缺陷節(jié)點.在基于程序頻譜的定位中,我們在錯誤程序上執(zhí)行測試用例,根據語句覆蓋信息,計算程序中語句缺陷疑似度,按疑似度從高到低進行排序,將疑似度高的語句作為缺陷位置.

(3) 修復選項生成.

對于使用重寫規(guī)則確定的缺陷位置,我們直接使用重寫規(guī)則中的修復方法生成修復選項.對于使用程序頻譜確定的缺陷位置,我們將缺陷處前面的序列化數(shù)據作為書寫結構模型的輸入,預測缺陷處的書寫結構,使用當前位置可見的變量進行擴展,得到多個修復候選項.

(4) 修復選項驗證.

首先,將錯誤程序、缺陷定位信息以及修復選項結合,得到擴展的帶有選擇表達式的 C/C++程序,并轉化為相應的SKETCH程序;然后,將程序需要滿足的規(guī)約作為約束,求解每一處選擇表達式的選項,確認修復候選項.

1.1 重寫規(guī)則總結和書寫結構模型構建

1.1.1 重寫規(guī)則

每一條重寫規(guī)則由兩部分組成:一部分表示缺陷模式,另一部分表示修復選項.我們對學生作業(yè)程序中常見的錯誤進行整理,總結了一些常見的錯誤模式及修復選項,具體見表1.

Table 1 Rewrite rules表1 重寫規(guī)則

本節(jié)給出了目前已整理的 C/C++代碼中常見的重寫規(guī)則,這些重寫規(guī)則比較通用,其中主要的缺陷是運算符誤用和代碼邏輯的錯誤.在一些特定的程序中,可能會出現(xiàn)某些特殊的缺陷,如果該缺陷存在特殊的模式,同時也有比較固定的修復方法,那么我們也可以針對這些缺陷設計特定的重寫規(guī)則,以實現(xiàn)對這些缺陷的修復.

1.1.2 序列化

代碼數(shù)據不同于普通的文本數(shù)據,它具有復雜的結構,若直接將代碼視為序列化數(shù)據,便會失去其中的結構信息,長短期記憶網絡也難以從這種缺乏關鍵信息的數(shù)據中學習書寫結構.而抽象語法樹既可以用來表示程序語義,同時也可以表示程序結構,因此,我們采用抽象語法樹對程序進行解析.并且我們在深度優(yōu)先遍歷抽象語法樹的基礎上,用“{”和“}”將每個中間節(jié)點包圍起來,以此來加強序列化數(shù)據中的結構信息.

如圖2是一段簡單的代碼,其語法樹形式如圖3所示,其序列化數(shù)據如圖4所示.

Fig.2 Code fragment圖2 代碼片段

Fig.3 Structure of syntax tree圖3 抽象語法樹結構

Fig.4 Serialized data圖4 序列化數(shù)據

1.1.3 書寫結構模型設計

LSTM廣泛應用于序列預測,我們也使用LSTM來預測缺陷處的書寫結構.我們使用最基本的LSTM模型,該模型的輸入為k個token.通過one-hot編碼將token轉化為特征向量,并輸入到隱藏層的LSTM cell.隱藏層的輸入還包括上一時刻細胞狀態(tài)ct-1以及隱藏層狀態(tài)ht-1.該層的輸出為當前時刻細胞狀態(tài)ct以及隱藏層狀態(tài)ht.將隱藏層的輸出h輸入模型的softmax層,得到預測結果的概率分布,向量中第i個元素的值代表結果為詞匯表中第i個token的概率.

細胞狀態(tài)ct以及隱藏層狀態(tài)ht計算公式如下:

其中,xt為當前token的one-hot編碼,ct-1為上一時刻細胞狀態(tài),ht-1為上一時刻隱藏層狀態(tài).

損失函數(shù)定義為softmax的輸出向量和樣本實際標簽交叉熵的平均值[8].

模型訓練時,采用梯度下降優(yōu)化算法,當損失函數(shù)的變化率小于設定值時停止訓練.

1.2 缺陷定位

缺陷定位是程序修復的重要一步.本文使用了兩種缺陷定位方法:基于重寫規(guī)則的缺陷定位方法與基于程序頻譜的缺陷定位方法.

1.2.1 基于重寫規(guī)則的缺陷定位

在第 1.1節(jié)中,我們設計了重寫規(guī)則,并給出了若干條重寫規(guī)則實例.重寫規(guī)則包括了缺陷模式和修復選項,其中,缺陷模式描述了程序中可能的缺陷.我們可以將重寫規(guī)則中的缺陷模式與源程序在語法樹上進行模式匹配,得到程序中可能的缺陷位置.

算法1.基于重寫規(guī)則的缺陷定位算法.

輸入:重寫規(guī)則Rule,源程序的抽象語法樹T.

輸出:可能的缺陷位置:抽象語法樹上的節(jié)點集合S.

該算法的目的是將缺陷模式與抽象語法樹進行匹配.

· 算法第6行～第12行的廣度優(yōu)先遍歷是主體部分;

· 算法的第4行將源程序抽象語法樹的根節(jié)點加入隊列Q;

· 第7行從隊列Q中取出一個節(jié)點,將該節(jié)點與缺陷模式DT的根節(jié)點進行匹配:若完全匹配,那么該節(jié)點為可能的缺陷節(jié)點,算法的第9行將這個節(jié)點加入集合S;若不匹配,算法的第11行、第12行將該節(jié)點的所有子節(jié)點加入隊列Q;

· 之后,按照廣度優(yōu)先遍歷的順序依次與缺陷模式進行比較.

1.2.2 基于程序頻譜的缺陷定位

使用重寫規(guī)則,我們可以定位出程序中那些具有固定模式的缺陷.但對于程序中更加一般的缺陷,比如表達式計算錯誤,我們無法給出明確的重寫規(guī)則.對于這樣更加一般的缺陷,我們將采用基于程序頻譜的定位方法.程序頻譜從某些角度記錄了程序的執(zhí)行信息,例如條件分支的執(zhí)行信息或無循環(huán)的內部程序路徑,它可以用來跟蹤程序的行為.當執(zhí)行失敗時,可以通過這些信息來識別導致缺陷的可疑代碼.選用程序頻譜的定位方式雖然并不一定精確,但可以快速確定哪些語句與缺陷相關,縮小對缺陷語句的搜索范圍,后期對修復候選項的選擇與驗證也能彌補這種定位帶來的不精確.

對于一個錯誤程序,我們首先獲得一組測試用例,其中包含通過的測試用例和失敗的測試用例.這兩類測試用例對程序語句的覆蓋情況不同,失敗的測試用例覆蓋的語句更有可能存在缺陷.利用這兩類測試用例的覆蓋情況,使用特定的公式,我們就能計算出不同語句存在缺陷的疑似度.按照疑似度對語句進行排序,并依次嘗試進行修復.本文計算疑似度使用的是Tarantula[9,10]計算公式,具體如下:

其中,NCF表示覆蓋語句的失敗的測試用例數(shù)量,NF表示所有失敗的測試用例數(shù)量,NCS表示覆蓋語句的通過的測試用例數(shù)量,NS表示所有通過的測試用例數(shù)量.

表2含有一個簡單程序,其目的是求一組數(shù)據去除最大值、最小值后的平均值.其中,語句6存在缺陷,正確應為max=score[i].表右側是5個測試用例(具體見表下部),其中有2個通過的測試用例,3個失敗的測試用例.表中圓點表示該測試用例覆蓋的語句.

根據語句覆蓋情況,使用上述的公式,得到表3語句疑似度計算結果.從表3中可以看出,語句6存在缺陷的疑似度最高;同時,語句6也正是存在缺陷的語句.

Table 2 Example of program spectrum表2 程序頻譜示例

Table 3 Result of sentence suspicion表3 語句疑似度計算結果

1.2.3 兩種定位方式對比

重寫規(guī)則是我們在調研南京大學《程序設計》課程中連續(xù)2年11題課程作業(yè)、316個學生作業(yè)提交后,人工總結常見的錯誤類型(詳見表1)及針對該類錯誤的修復方式形成的,基于重寫規(guī)則的缺陷定位方式主要也是定位這些人工總結出來的具有固定模式的缺陷.但人工總結難免有所遺漏,基于程序頻譜的缺陷定位針對的就是重寫規(guī)則遺漏的部分,與基于重寫規(guī)則的缺陷定位方式互為補充.

1.3 修復選項生成

在第1.2.1節(jié)中,我們介紹了基于重寫規(guī)則的缺陷定位方法和基于程序頻譜的缺陷定位方法.在得到可能的缺陷位置后,我們將分別使用兩種修復選項生成方法——基于重寫規(guī)則的修復選項生成和基于預測的修復選項生成,對缺陷位置生成修復選項.

1.3.1 基于重寫規(guī)則的修復選項生成

在第 1.2.1中,我們通過重寫規(guī)則得到了可能的缺陷節(jié)點.重寫規(guī)則中包含了修復選項,我們可以利用重寫規(guī)則,對由重寫規(guī)則得到的缺陷節(jié)點,生成實際的修復選項.

算法2.基于重寫規(guī)則的修復選項生成算法.

輸入:重寫規(guī)則Rule,抽象語法樹上的缺陷節(jié)點node.

輸出:針對缺陷節(jié)點node的修復選項集合S.

該算法在第1行匹配標識符(變量名)與語法樹節(jié)點的對應關系,保存在字典NDict中.之后,在第6行～第12行按照廣度優(yōu)先的方式遍歷每一個修復選項ct的所有節(jié)點,在第9行將其中的標識符節(jié)點替換.替換掉標識符節(jié)點的ct就是針對缺陷節(jié)點node的實際修復選項,最后在第13行將ct加入集合S中.

1.3.2 基于預測的修復選項生成

在第 1.2.2節(jié)中,我們介紹了基于程序頻譜的缺陷定位,通過該方法定位到缺陷位置后,我們通過預測的方法來生成修復候選項.在深度學習中,長短期記憶網絡能解決長期依賴問題,適合處理序列預測問題,因此我們選用長短期記憶網絡作為寫結構模型.針對每一處缺陷位置,我們按照之前序列化的方法,將缺陷位置前的正確代碼序列化,并截取固定長度作為書寫結構模型的輸入.反復迭代產生預測,直到匹配到完整的一對“{”,“}”.將模型產生的預測結果作為該處缺陷可能的書寫結構.

由于在序列化的時候我們對變量名進行了抽象,在實際生成候選項時,我們根據書寫結構,使用當前可見的變量名替換結構中的對應部分,產生候選項集.

1.4 修復選項驗證

傳統(tǒng)的驗證方法多使用測試的方法,通過所有的測試用例就認為修復正確,但這樣并不能保證真正的正確.2015年,Qi等人[3]對GenProg和AE兩個工作在105個真實缺陷上的修復進行了手工檢查.其中,Genprog的修復結果中只有兩個是語義正確的,而 AE的修復結果中只有 3個是語義正確的.我們采用程序合成的方法,并使用程序合成工具SKETCH來進行候選項驗證,確保合成后程序的正確性.我們將錯誤程序、缺陷定位信息以及修復選項結合,得到擴展的帶有選擇表達式的C/C++程序,并轉化為相應的SKETCH程序.然后,將正確的樣例程序作為SKETCH程序合成器的約束,在規(guī)定時間內求解SKETCH程序.如果在設定的時間內能夠求解得到每一處選擇表達式的選項,就以此確定 C/C++程序中對應的選擇表達式選項,得到正確的 C/C++程序.如果超出規(guī)定時間或無解,則認為沒有正確的修復選項,修復失敗.

2 工具與評估

本文實現(xiàn)了一個基于程序合成工具 SKETCH的 C/C++程序缺陷自動修復原型工具 AutoGrader,該工具可以修復 C/C++程序上的常見缺陷.為了驗證工具在缺陷修復上的有效性,本文以學生作業(yè)程序為對象,設計了相關實驗,并對比了GenProg和AE兩個工具在缺陷修復上的效果.

2.1 工具框架

圖5展示了我們工具的框架,其中,底層的是工具的輸入,包括待修復的C/C++程序、重寫規(guī)則和正確程序集;中間部分是工具主要實現(xiàn)的模塊,包括解析模塊、模型構建模塊、缺陷定位模塊、修復選項生成模塊、SKETCH程序合成模塊;最上層是工具的輸出.

Fig.5 Framework of the tool圖5 工具框架

2.2 實驗對象

SKETCH合成工具僅能處理小規(guī)模的問題,一方面由于大規(guī)模程序過于復雜,SKETCH求解器的能力不足;另一方面,由于大規(guī)模程序往往包含過多的函數(shù)庫,使用 SKETCH手工實現(xiàn)過于復雜.因此,我們的實驗對象主要是學生作業(yè)程序.學生作業(yè)程序都是小規(guī)模程序,同時可能會包含一些相似的錯誤.

我們收集了2016年～2017年間,南京大學《程序設計》課程的作業(yè),累積11個任務、316個學生提交.經過分析整理,我們選取了兩個任務的學生作業(yè).任務 1是求一個整型數(shù)組在除去最大值和最小值之后的平均值,任務 2是對一個正整數(shù)進行質因子分解.除去編譯發(fā)生錯誤的情況,共有 19題錯誤作業(yè),這些錯誤程序規(guī)模都在20行～30行左右,包含1～3個錯誤.錯誤類型分布見表4.

Table 4 Distribution of error types表4 錯誤類型分布

2.3 實驗設計

基于本文實現(xiàn)的 C/C++程序缺陷自動修復工具 AutoGrader,選取了學生的作業(yè)程序進行實驗.作業(yè)程序有著明確的實驗要求,我們提前給出了示例程序,使用示例程序作為 SKETCH合成的規(guī)約.在實驗中,我們主要討論以下幾個問題.

(1) AutoGrader在作業(yè)程序上的修復效果如何?

(2) AutoGrader對比其他工具有哪些優(yōu)勢?

(3) AutoGrader所采用的缺陷定位方法能否定位到實際的缺陷位置?

實驗的運行環(huán)境如下:CPU Intel Core i7-4790GHz,內存16GB,系統(tǒng)Ubuntu16.04.

2.3.1 修復效果

表5展示了我們的實驗結果.表中Question表示程序的問題,Program表示程序編號,LOC表示程序的代碼行數(shù),Defect表示程序的缺陷數(shù)量,其余列表示對應方法修復缺陷的時間(以s為單位),×表示未能完成修復.我們使用了GenProg和AE這兩個工具進行了對比實驗.

Table 5 Results of repair表5 修復結果

通過實驗數(shù)據表明,我們的工具對作業(yè)程序的修復有如下優(yōu)點.

(1) 對這19個錯誤程序,我們的工具可以對其中的14個進行修復,修復率為73.7%,修復時間都在60s以下;GenProg和AE僅能對其中的8個程序進行修復,盡管修復所需的時間更短,但我們的工具具有更高的修復率.

(2) GenProg和AE僅能修復只含有一個缺陷的程序,我們的工具可以修復多個缺陷.

(3) 由于我們在 SKETCH合成中引入了示例程序,這保證了我們的工具修復后的程序是正確的.而對于GenProg和AE,修復的程序僅能通過測試用例.表格中帶*的數(shù)據表明:修復后的程序通過了測試用例,但不是一個正確的修復.

2.3.2 定位與修復分析

我們的工具使用了基于重寫規(guī)則和基于程序頻譜的缺陷定位技術,為了驗證缺陷定位技術是否能夠定位到程序中實際的缺陷,我們人工對比了程序中實際的缺陷與工具定位的可能的缺陷位置.

表6展示了程序中實際的缺陷位置與定位技術得到的缺陷位置.

Real Defect表示程序的實際缺陷行號,Defect Location表示定位得到的缺陷行號.從表中看到,程序中實際缺陷一共30個,定位技術得到的缺陷個數(shù)為59個.所有實現(xiàn)修復的程序中,定位技術都覆蓋了實際的缺陷.對于未實現(xiàn)修復的程序,除Q1 053外,由于定位得到的缺陷未覆蓋實際缺陷,因此無法實現(xiàn)修復.對于程序Q1 053,定位覆蓋了實際缺陷,而由于錯誤比較特殊,未產生正確的修復選項,因此無法修復.

Table 6 Results of defect location表6 缺陷定位結果

Table 6 Results of defect location (Continued)表6 缺陷定位結果(續(xù))

3 相關工作

3.1 基于搜索的缺陷修復

在基于搜索的方法中,生成程序補丁的過程被看作是從搜索空間中尋找最優(yōu)解的過程.對于待修復的程序來說,該方法將對程序的修改作為潛在補丁,獲得補丁空間.在搜索過程方面,多使用啟發(fā)式方法、演化算法等方法尋找補丁.

GenProg方法[11]由 Weimer等人于 2009年提出.GenProg將程序看作抽象語法樹,將代碼段看作子樹.GenProg的核心算法是遺傳算法,其中,變異操作包括復制別處語句替換當前語句、在當前語句后插入其他語句、刪除當前位置的語句.遺傳操作為選擇兩個適應度高的程序,交換其中的變異操作.如果修改后的程序通過的測試用例越多,程序的適應度就越高.2012年,Le Goues等人對Genprog方法進行了大型實驗[12],選擇了105個大型程序中的缺陷進行修復,成功修復了105個缺陷中的55個.GenProg是缺陷修復技術興起的代表性工作.

2013年,Weimer等人對GenProg方法進行改進,提出了AE方法[13].他們認為GenProg方法生成的候選補丁數(shù)量太多,為了盡可能地減少生成的候選補丁數(shù)量,AE方法提出了等價類的概念.通過設置一系列規(guī)則,快速檢查特定類型的等價變換,在修改時避免產生等價變換.驗證結果表明,修復的時間開銷為原來的三分之一.

2013年,Kim等人提出了PAR方法[14].該方法從開源項目Eclipse JDT中分析了6萬個開發(fā)者人工修復的補丁,總結了常見的10種代碼修復模板,并將模板與GenProg相融合生成補丁.PAR方法生成的補丁具有更好的可讀性.

2014年,Qi等人認為 GenProg方法中的遺傳算法存在計算開銷大、難以識別有效補丁的問題,并提出了RSRepair方法[15],將遺傳算法替換為隨機搜索.實驗表明:RSRepair和 GenProg有著相近的修復能力,并能有效減少生成補丁的時間.

2016年,Fan提出了Prophet方法[16].通過使用機器學習方法,對開源項目中正確代碼的特征進行學習.在實際修復過程中,Prophet方法對可能的修復補丁,分析補丁特征和代碼上下文,通過概率模型計算補丁可能修復程序的概率.最后,根據概率排序對補丁依次進行驗證.

3.2 基于約束求解的缺陷修復

基于約束求解的缺陷修復將在搜索空間尋找補丁的過程轉換為約束求解問題,通過約束求解器獲得可行解并轉換為修復補丁.由于約束求解的特性,這類修復方法往往能夠獲得精確的結果,但也會消耗更多的時間.

該類算法的先驅是2012年的SemFix方法[17],一種C語言的基于約束的修復算法.該算法使用基于組合的程序合成方法生成補丁.將測試用例轉換為約束,使用SMT求解器求解,得到最終補丁.

2014年的Nopol方法[18]是一種專門修復if條件缺陷的方法,針對條件錯誤或者條件語句缺失這兩種常見缺陷進行修復.在實際修復過程中,使用天使定位算法,獲得可能的缺陷位置.與 SemFix方法不同,Nopol僅針對if條件表達式,搜索空間小,可應用于大規(guī)模程序.

2015年,Mechtaev等人提出了DirectFix方法[19],該方法為了提高SemFix方法生成的補丁質量,用語法樹上被改動的元素個數(shù)定義差別,最終生成語法樹上差別最小的補丁.

3.3 其他方法

2010年起,Pei等人提出一種基于契約的方法Autofix[20-22].Autofix是一種基于契約的修復方法,該方法需要程序契約中的規(guī)約信息作為輸入,例如函數(shù)的前置和后置條件等.通過從程序中抽取執(zhí)行序列來對程序行為特征進行抽象,并根據語法特點和程序執(zhí)行信息來定位疑似缺陷語句.隨后選擇不同的修復模式,運用值替換、表達式替換等方式生成補丁代碼.該方法可用于Effiel語言的bug修復.

Gao等人針對C程序中與內存泄露相關的缺陷,提出了Leakfix方法[23].該方法能夠修復大量內存泄漏問題,其主要修復方式是在程序合適的位置插入存儲單元分配語句.

Su等人提出了SRAFGEN方法[24],該方法將大量程序按照控制流結構分類.從錯誤程序所屬的類別中,根據“程序間距離”算法找出與錯誤程序最相似的程序.以此程序為基礎,根據對應的結構,匹配相應的語句,產生修補方案.

Gulwani等人提出了CLARA方法[25],該方法根據控制流結構聚類相似的程序,并為每一類選出一個代表程序.對于錯誤程序,根據控制流結構劃分到相應的類,并嘗試與該類的代表程序匹配,產生條件匹配對,所有條件匹配對中的條件作為可能的修改操作.最終使用0-1線性規(guī)劃選取最終的修改操作.

4 總結與展望

本文提出了一種基于程序合成的 C/C++程序缺陷自動修復方法.使用缺陷定位方法——基于重寫規(guī)則和基于程序頻譜,得到程序中可能的缺陷位置.使用修復選項生成方法——基于重寫規(guī)則和基于預測,得到缺陷的修復選項.并使用程序合成的方法進行修復選項驗證,保證合成后程序的正確性.

在本文方法的實驗中,我們也遇到了一些問題和挑戰(zhàn),這也是我們未來的研究方向:(1) 目前,本文關注的是單條語句的修改,并沒有考慮增加語句或刪除語句的情況,這是我們下一步研究的方向;(2) 目前,本文采用了基于重寫規(guī)則和程序頻譜的缺陷定位,基于重寫規(guī)則的缺陷定位依賴一定的先驗知識,而基于程序頻譜的缺陷定位與精確定位還有一定的差距,下一步將嘗試加入更多的程序缺陷定位方法,以處理如指針錯誤等更多類型的缺陷;(3) 目前,本文在通過預測的修復選項生成過程中,使用當前可見的全部變量替換語句結構中的相應部分,可以考慮提前過濾掉部分無關的修復選項;(4) 目前,數(shù)據集程序數(shù)量較少,下一步將繼續(xù)收集更多的學生作業(yè)程序,在更多的學生作業(yè)程序上驗證我們方法的有效性.