基于遺傳算法和代碼相似性自動(dòng)修復(fù)程序錯(cuò)誤

石建樹(shù) 王憲勇

摘要：由于軟件產(chǎn)品的復(fù)雜性，軟件開(kāi)發(fā)過(guò)程中開(kāi)發(fā)人員無(wú)法避免bug的產(chǎn)生。為了提高軟件開(kāi)發(fā)的效率，提出了一種基于遺傳算法和代碼相似性的bug自動(dòng)修復(fù)方法。首先，搜索與源程序相似的bug代碼，并找到與其相關(guān)的修復(fù)代碼。然后，將修復(fù)代碼轉(zhuǎn)換為抽象語(yǔ)法樹(shù)，生成候選補(bǔ)丁。接下來(lái)，使用基于給定測(cè)試用例的適應(yīng)度函數(shù)來(lái)驗(yàn)證候選補(bǔ)丁是否有效。最后，生成輸出補(bǔ)丁修復(fù)源錯(cuò)誤代碼。

關(guān)鍵詞：遺傳算法;代碼相似性;自動(dòng)程序修復(fù);軟件維護(hù)

中圖分類(lèi)號(hào)：TP311.5 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）31-0209-03

1概述

由于現(xiàn)代軟件產(chǎn)品的復(fù)雜性，軟件開(kāi)發(fā)過(guò)程中開(kāi)發(fā)人員無(wú)法避免bug的產(chǎn)生。由于有大量的bug報(bào)告，開(kāi)發(fā)人員必須花費(fèi)更多的時(shí)間和精力來(lái)修復(fù)bug。由于每天都有大量的bug，開(kāi)發(fā)人員需要花費(fèi)更多的時(shí)間來(lái)跟蹤這些bug。開(kāi)發(fā)人員手工生成的補(bǔ)丁的正確率也難以保證。因此，一種速度快，準(zhǔn)確率高的自動(dòng)修復(fù)技術(shù)可以顯著地節(jié)省軟件開(kāi)發(fā)的時(shí)間和成本，提高軟件質(zhì)量。

如果開(kāi)發(fā)人員能夠獲得有用的信息描述，開(kāi)發(fā)人員就可以輕松地跟蹤并修復(fù)bug。但是，如果錯(cuò)誤報(bào)告包含的信息不夠，開(kāi)發(fā)人員可能很難進(jìn)行調(diào)試。因此，利用相似的bug代碼的修復(fù)信息進(jìn)行自動(dòng)修復(fù)，可以在缺少描述信息的情況下有效地修復(fù)bug。

針對(duì)上述問(wèn)題，本文提出一種基于遺傳算法和代碼相似性的程序自動(dòng)修復(fù)方法。搜索與源bug代碼相關(guān)的類(lèi)似bug代碼，以及其修復(fù)代碼。然后，將其轉(zhuǎn)換為抽象語(yǔ)法樹(shù)（AST）。最后應(yīng)用遺傳規(guī)劃為源bug代碼生成補(bǔ)丁。此方法支持自動(dòng)修復(fù)，可以減少修復(fù)bug的時(shí)間和工作量，并且可以提高bug修復(fù)的質(zhì)量和補(bǔ)丁的可讀性。

2相關(guān)工作

許多研究人員提出了程序自動(dòng)修復(fù)方法。如表1所示，我們對(duì)與本文相關(guān)的自動(dòng)修復(fù)技術(shù)進(jìn)行了比較。

Le Goues等人提出了GenProg，其使用基于AST的遺傳規(guī)劃。GenProg將錯(cuò)誤的源代碼轉(zhuǎn)換為AST，然后使用選擇、交叉、變異等操作生成新的AST。齊玉華等人為了驗(yàn)證GenProg中遺傳編程對(duì)補(bǔ)丁生成過(guò)程是否有效，提出了基于隨機(jī)搜索的RSRepair方法。Simfix通過(guò)分析現(xiàn)有補(bǔ)丁形成抽象的過(guò)程修復(fù)空間，并且通過(guò)分析相同程序中相似的代碼片段形成具體的修復(fù)空間。文明等人提出了CapGen，CapGen以細(xì)粒度的方式在AST節(jié)點(diǎn)級(jí)別工作，這種設(shè)計(jì)使其能夠找到更精確的修復(fù)組件。為了解決細(xì)粒度所帶來(lái)的搜索空間巨大的問(wèn)題，其使用三種上下文模型使正確的補(bǔ)丁能夠排在更靠前的位置。DeepRepair使用基于深度學(xué)習(xí)的代碼相似性對(duì)修復(fù)成分進(jìn)行優(yōu)先級(jí)排序和轉(zhuǎn)換。它計(jì)算代碼元素之間的距離來(lái)度量相似性。其通過(guò)智能選擇和調(diào)整修復(fù)成分來(lái)生成補(bǔ)丁。

3錯(cuò)誤修復(fù)

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

本文使用Defects4i數(shù)據(jù)集。高質(zhì)量的數(shù)據(jù)集對(duì)于評(píng)估自動(dòng)修復(fù)方法的有效性是必不可少的。Defects4i缺陷數(shù)據(jù)集共包含6個(gè)Java項(xiàng)目（Commons Lang、JFreeChart、CommonsMath、Joda-Time、Mockito和Closure Compiler），總bug數(shù)為438個(gè)，近年來(lái)關(guān)于自動(dòng)修復(fù)的研究也廣泛采用了該基準(zhǔn)。Defects4i數(shù)據(jù)集中的錯(cuò)誤程序都來(lái)自實(shí)際項(xiàng)目，并且其自帶的測(cè)試用例集能夠較好的覆蓋程序的預(yù)期行為。

3.2錯(cuò)誤定位

識(shí)別錯(cuò)誤代碼行是修復(fù)的先決條件。為了找到錯(cuò)誤代碼的位置，應(yīng)該執(zhí)行錯(cuò)誤定位技術(shù)。錯(cuò)誤定位技術(shù)的精確度對(duì)后續(xù)的修復(fù)效果起到關(guān)鍵的影響。目前研究人員已經(jīng)提出了大量的程序錯(cuò)誤定位方法。其中基于程序頻譜的定位方法是目前的主流方法。其根據(jù)測(cè)試用例的覆蓋率來(lái)判斷語(yǔ)句的可疑度。最終向修復(fù)過(guò)程輸出一組按可疑度大小排列的語(yǔ)句。本文使用錯(cuò)誤定位工具Gzoltar，此工具使用Ochiai算法檢索故障空間和可疑值。

3.3遺傳規(guī)劃

在本節(jié)中，我們將使用相似的bug修復(fù)信息描述遺傳規(guī)劃的應(yīng)用。算法概覽如圖1所示。

3.3.1種群初始化

利用克隆檢測(cè)技術(shù)㈣搜索與源bug代碼相似的bug代碼，并得到相似錯(cuò)誤代碼的修復(fù)代碼。為了找到最相似的修復(fù)代碼，將修復(fù)代碼中的每一行代碼轉(zhuǎn)換為令牌序列。使用最長(zhǎng)公共子序列（LCS）對(duì)這些行和源錯(cuò)誤行的令牌序列進(jìn)行比較。從這些行中獲取具有最高LCS值的令牌序列。保留關(guān)鍵詞、變量名和常數(shù)，使用隨機(jī)操作符生成新的代碼行，并將該行與錯(cuò)誤行交換。重復(fù)這個(gè)步驟，直到初始補(bǔ)丁的數(shù)量等于種群的大小。

3.3.2遺傳操作

當(dāng)前種群中沒(méi)有合格的個(gè)體時(shí)，將執(zhí)行選擇操作符。我們用適應(yīng)度函數(shù)將個(gè)體按降序排序，使一半的個(gè)體都為父代。為了便于初始種群的構(gòu)建，將適應(yīng)度函數(shù)做規(guī)范化處理。以下為個(gè)體i的適應(yīng)度函數(shù)規(guī)范化處理過(guò)程，這個(gè)規(guī)范化的適應(yīng)度值僅用于初始種群選擇。

其中，i為種群中第i個(gè)個(gè)體;fitc（i）表示i個(gè)體適應(yīng)度值;fits表示種群中最小適應(yīng)度值;fit1表示種群中最大適應(yīng)度值。

交叉的目的是交換兩個(gè)AST中的子樹(shù)節(jié)點(diǎn)。在每個(gè)母樹(shù)中選擇可更改的目標(biāo)節(jié)點(diǎn)。選擇目標(biāo)節(jié)點(diǎn)后，通過(guò)跟蹤父節(jié)點(diǎn)來(lái)驗(yàn)證兩個(gè)節(jié)點(diǎn)是否可以交換。在變異中，選用刪除、插入和交換三種操作。

3.3.3適應(yīng)度函數(shù)

迭代遺傳規(guī)劃算法，直到某些值達(dá)到限定條件。設(shè)置了三個(gè)限定條件;運(yùn)行時(shí)間、代數(shù)和適應(yīng)度值。如果達(dá)到限定時(shí)間和迭代次數(shù)還沒(méi)有生成正確的補(bǔ)丁，則修復(fù)失敗。個(gè)體適應(yīng)度值如果是1，則停止迭代輸出補(bǔ)丁。在每個(gè)迭代步驟中，并必須計(jì)算每個(gè)個(gè)體的適應(yīng)度值。

其中，a為通過(guò)正測(cè)試用例的系數(shù);β為未通過(guò)反測(cè)試用例的系數(shù);y為通過(guò)反測(cè)試用例的系數(shù);Pp代表通過(guò)的正測(cè)試用例;Ⅳ。代表通過(guò)的反測(cè)試用例;P為正測(cè)試用例集，N為反測(cè)試用例集。

方程結(jié)果的取值范圍為0～1。值越接近1，個(gè)體越接近正確解。由于此模型包含了基本的功能，并且沒(méi)有引發(fā)意外的行為，所以適應(yīng)度更接近于1。a的值應(yīng)大于β和y，因?yàn)榇讼禂?shù)表示個(gè)體是否包含基本功能。

4結(jié)論

本文提出了一種自動(dòng)修復(fù)程序缺陷的方法。首先，我們通過(guò)手工檢查發(fā)現(xiàn)了可疑的錯(cuò)誤代碼行。然后，我們使用具有類(lèi)似bug修復(fù)信息的GP生成候選補(bǔ)丁。接下來(lái)，我們驗(yàn)證候選補(bǔ)丁是否可采用。最后，我們生成補(bǔ)丁來(lái)修復(fù)程序錯(cuò)誤。使用我們的方法，我們期望花費(fèi)在修復(fù)bug上的時(shí)間和精力可以減少。在未來(lái)，計(jì)劃創(chuàng)建一個(gè)自動(dòng)故障修復(fù)工具并且利用大規(guī)模的bug修復(fù)信息修復(fù)和測(cè)試用例排序技術(shù)更有效地完成自動(dòng)修復(fù)過(guò)程。