周風(fēng)順,王林章,李宣東

(計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)),江蘇 南京 210023)

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

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

修復(fù)真實(shí)缺陷,一直以來(lái)是程序缺陷自動(dòng)修復(fù)研究的目標(biāo).目前,學(xué)術(shù)界對(duì)現(xiàn)有的修復(fù)技術(shù)在真實(shí)缺陷上的修復(fù)能力存在一定爭(zhēng)議[12],關(guān)于缺陷修復(fù)的討論也有很多.2015年,Qi等人[3]對(duì)GenProg和AE兩個(gè)工作在105個(gè)真實(shí)缺陷上的修復(fù)進(jìn)行了手工檢查.其中,Genprog的修復(fù)結(jié)果中只有兩個(gè)是語(yǔ)義正確的,而AE的修復(fù)結(jié)果中只有3個(gè)是語(yǔ)義正確的.由此可見(jiàn),現(xiàn)有的修復(fù)技術(shù)存在著修復(fù)率低,無(wú)法保證修復(fù)結(jié)果的正確性等問(wèn)題.

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

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

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

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

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

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

1 基于程序合成的C/C++程序缺陷自動(dòng)修復(fù)方法

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

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

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

(1) 重寫規(guī)則總結(jié)和書寫結(jié)構(gòu)模型構(gòu)建.

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

(2) 缺陷定位.

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

(3) 修復(fù)選項(xiàng)生成.

對(duì)于使用重寫規(guī)則確定的缺陷位置,我們直接使用重寫規(guī)則中的修復(fù)方法生成修復(fù)選項(xiàng).對(duì)于使用程序頻譜確定的缺陷位置,我們將缺陷處前面的序列化數(shù)據(jù)作為書寫結(jié)構(gòu)模型的輸入,預(yù)測(cè)缺陷處的書寫結(jié)構(gòu),使用當(dāng)前位置可見(jiàn)的變量進(jìn)行擴(kuò)展,得到多個(gè)修復(fù)候選項(xiàng).

(4) 修復(fù)選項(xiàng)驗(yàn)證.

首先,將錯(cuò)誤程序、缺陷定位信息以及修復(fù)選項(xiàng)結(jié)合,得到擴(kuò)展的帶有選擇表達(dá)式的 C/C++程序,并轉(zhuǎn)化為相應(yīng)的SKETCH程序;然后,將程序需要滿足的規(guī)約作為約束,求解每一處選擇表達(dá)式的選項(xiàng),確認(rèn)修復(fù)候選項(xiàng).

1.1 重寫規(guī)則總結(jié)和書寫結(jié)構(gòu)模型構(gòu)建

1.1.1 重寫規(guī)則

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

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

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

1.1.2 序列化

代碼數(shù)據(jù)不同于普通的文本數(shù)據(jù),它具有復(fù)雜的結(jié)構(gòu),若直接將代碼視為序列化數(shù)據(jù),便會(huì)失去其中的結(jié)構(gòu)信息,長(zhǎng)短期記憶網(wǎng)絡(luò)也難以從這種缺乏關(guān)鍵信息的數(shù)據(jù)中學(xué)習(xí)書寫結(jié)構(gòu).而抽象語(yǔ)法樹既可以用來(lái)表示程序語(yǔ)義,同時(shí)也可以表示程序結(jié)構(gòu),因此,我們采用抽象語(yǔ)法樹對(duì)程序進(jìn)行解析.并且我們?cè)谏疃葍?yōu)先遍歷抽象語(yǔ)法樹的基礎(chǔ)上,用“{”和“}”將每個(gè)中間節(jié)點(diǎn)包圍起來(lái),以此來(lái)加強(qiáng)序列化數(shù)據(jù)中的結(jié)構(gòu)信息.

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

Fig.2 Code fragment圖2 代碼片段

Fig.3 Structure of syntax tree圖3 抽象語(yǔ)法樹結(jié)構(gòu)

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

1.1.3 書寫結(jié)構(gòu)模型設(shè)計(jì)

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

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

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

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

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

1.2 缺陷定位

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

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

在第 1.1節(jié)中,我們?cè)O(shè)計(jì)了重寫規(guī)則,并給出了若干條重寫規(guī)則實(shí)例.重寫規(guī)則包括了缺陷模式和修復(fù)選項(xiàng),其中,缺陷模式描述了程序中可能的缺陷.我們可以將重寫規(guī)則中的缺陷模式與源程序在語(yǔ)法樹上進(jìn)行模式匹配,得到程序中可能的缺陷位置.

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

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

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

該算法的目的是將缺陷模式與抽象語(yǔ)法樹進(jìn)行匹配.

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

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

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

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

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

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

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

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

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

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

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

Table 3 Result of sentence suspicion表3 語(yǔ)句疑似度計(jì)算結(jié)果

1.2.3 兩種定位方式對(duì)比

重寫規(guī)則是我們?cè)谡{(diào)研南京大學(xué)《程序設(shè)計(jì)》課程中連續(xù)2年11題課程作業(yè)、316個(gè)學(xué)生作業(yè)提交后,人工總結(jié)常見(jiàn)的錯(cuò)誤類型(詳見(jiàn)表1)及針對(duì)該類錯(cuò)誤的修復(fù)方式形成的,基于重寫規(guī)則的缺陷定位方式主要也是定位這些人工總結(jié)出來(lái)的具有固定模式的缺陷.但人工總結(jié)難免有所遺漏,基于程序頻譜的缺陷定位針對(duì)的就是重寫規(guī)則遺漏的部分,與基于重寫規(guī)則的缺陷定位方式互為補(bǔ)充.

1.3 修復(fù)選項(xiàng)生成

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

1.3.1 基于重寫規(guī)則的修復(fù)選項(xiàng)生成

在第 1.2.1中,我們通過(guò)重寫規(guī)則得到了可能的缺陷節(jié)點(diǎn).重寫規(guī)則中包含了修復(fù)選項(xiàng),我們可以利用重寫規(guī)則,對(duì)由重寫規(guī)則得到的缺陷節(jié)點(diǎn),生成實(shí)際的修復(fù)選項(xiàng).

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

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

輸出:針對(duì)缺陷節(jié)點(diǎn)node的修復(fù)選項(xiàng)集合S.

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

1.3.2 基于預(yù)測(cè)的修復(fù)選項(xiàng)生成

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

由于在序列化的時(shí)候我們對(duì)變量名進(jìn)行了抽象,在實(shí)際生成候選項(xiàng)時(shí),我們根據(jù)書寫結(jié)構(gòu),使用當(dāng)前可見(jiàn)的變量名替換結(jié)構(gòu)中的對(duì)應(yīng)部分,產(chǎn)生候選項(xiàng)集.

1.4 修復(fù)選項(xiàng)驗(yàn)證

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

2 工具與評(píng)估

本文實(shí)現(xiàn)了一個(gè)基于程序合成工具 SKETCH的 C/C++程序缺陷自動(dòng)修復(fù)原型工具 AutoGrader,該工具可以修復(fù) C/C++程序上的常見(jiàn)缺陷.為了驗(yàn)證工具在缺陷修復(fù)上的有效性,本文以學(xué)生作業(yè)程序?yàn)閷?duì)象,設(shè)計(jì)了相關(guān)實(shí)驗(yàn),并對(duì)比了GenProg和AE兩個(gè)工具在缺陷修復(fù)上的效果.

2.1 工具框架

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

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

2.2 實(shí)驗(yàn)對(duì)象

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

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

Table 4 Distribution of error types表4 錯(cuò)誤類型分布

2.3 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

2.3.1 修復(fù)效果

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

Table 5 Results of repair表5 修復(fù)結(jié)果

通過(guò)實(shí)驗(yàn)數(shù)據(jù)表明,我們的工具對(duì)作業(yè)程序的修復(fù)有如下優(yōu)點(diǎn).

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

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

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

2.3.2 定位與修復(fù)分析

我們的工具使用了基于重寫規(guī)則和基于程序頻譜的缺陷定位技術(shù),為了驗(yàn)證缺陷定位技術(shù)是否能夠定位到程序中實(shí)際的缺陷,我們?nèi)斯?duì)比了程序中實(shí)際的缺陷與工具定位的可能的缺陷位置.

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

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

Table 6 Results of defect location表6 缺陷定位結(jié)果

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

3 相關(guān)工作

3.1 基于搜索的缺陷修復(fù)

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

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

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

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

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

2016年,Fan提出了Prophet方法[16].通過(guò)使用機(jī)器學(xué)習(xí)方法,對(duì)開源項(xiàng)目中正確代碼的特征進(jìn)行學(xué)習(xí).在實(shí)際修復(fù)過(guò)程中,Prophet方法對(duì)可能的修復(fù)補(bǔ)丁,分析補(bǔ)丁特征和代碼上下文,通過(guò)概率模型計(jì)算補(bǔ)丁可能修復(fù)程序的概率.最后,根據(jù)概率排序?qū)ρa(bǔ)丁依次進(jìn)行驗(yàn)證.

3.2 基于約束求解的缺陷修復(fù)

基于約束求解的缺陷修復(fù)將在搜索空間尋找補(bǔ)丁的過(guò)程轉(zhuǎn)換為約束求解問(wèn)題,通過(guò)約束求解器獲得可行解并轉(zhuǎn)換為修復(fù)補(bǔ)丁.由于約束求解的特性,這類修復(fù)方法往往能夠獲得精確的結(jié)果,但也會(huì)消耗更多的時(shí)間.

該類算法的先驅(qū)是2012年的SemFix方法[17],一種C語(yǔ)言的基于約束的修復(fù)算法.該算法使用基于組合的程序合成方法生成補(bǔ)丁.將測(cè)試用例轉(zhuǎn)換為約束,使用SMT求解器求解,得到最終補(bǔ)丁.

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

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

3.3 其他方法

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

Gao等人針對(duì)C程序中與內(nèi)存泄露相關(guān)的缺陷,提出了Leakfix方法[23].該方法能夠修復(fù)大量?jī)?nèi)存泄漏問(wèn)題,其主要修復(fù)方式是在程序合適的位置插入存儲(chǔ)單元分配語(yǔ)句.

Su等人提出了SRAFGEN方法[24],該方法將大量程序按照控制流結(jié)構(gòu)分類.從錯(cuò)誤程序所屬的類別中,根據(jù)“程序間距離”算法找出與錯(cuò)誤程序最相似的程序.以此程序?yàn)榛A(chǔ),根據(jù)對(duì)應(yīng)的結(jié)構(gòu),匹配相應(yīng)的語(yǔ)句,產(chǎn)生修補(bǔ)方案.

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

4 總結(jié)與展望

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

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