黃昱銘，馬建峰,2，劉志全，魏凱敏，馮丙文,3,4,5

(1.暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州 510632；2．西安電子科技大學(xué) 網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071；3.中國科學(xué)院信息工程研究所 信息安全國家重點(diǎn)實(shí)驗(yàn)室，北京 100093；4.廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 520006；5.廣東省智能信息處理重點(diǎn)實(shí)驗(yàn)室/深圳市媒體信息內(nèi)容安全重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518060)

由于需求理解錯(cuò)誤、開發(fā)過程不合理和開發(fā)者經(jīng)驗(yàn)不足，軟件中不可避免地會(huì)存在已知或未知的缺陷。通過軟件維護(hù)減少由于軟件錯(cuò)誤(Software Error)引起的軟件缺陷(Software Defect)是軟件工程中不可缺少的重要環(huán)節(jié)。傳統(tǒng)方法通過人力進(jìn)行軟件維護(hù)會(huì)浪費(fèi)大量的勞動(dòng)力和時(shí)間成本[1]。因此，研究者們越來越關(guān)注自動(dòng)程序修復(fù)(Automatic Program Repair，APR)。

當(dāng)前主流的自動(dòng)程序修復(fù)方法是使用測試集(Test Suite)對程序缺陷進(jìn)行定位和修復(fù)。使用測試集修復(fù)程序缺陷的自動(dòng)程序修復(fù)方法主要分為兩類[2]：一類是基于搜索，另一類是基于語義。基于搜索的自動(dòng)程序修復(fù)方法通過基于搜索的軟件工程(Search Based Software Engineering)[3]在搜索空間中尋找最合適的補(bǔ)丁。這類自動(dòng)程序修復(fù)方法的代表有GenProg[4]等?；谡Z義的自動(dòng)程序修復(fù)方法通過提取程序的語義信息和測試集中的補(bǔ)丁約束以合成合適的補(bǔ)丁。這類自動(dòng)程序修復(fù)方法的代表有ACS[5]等。

自動(dòng)程序修復(fù)方法修復(fù)程序缺陷與人工修復(fù)方法相比，雖然能更快地定位和修復(fù)缺陷，節(jié)省勞動(dòng)力和時(shí)間成本，但是無法保證缺陷修復(fù)的正確性。雖然一些自動(dòng)程序修復(fù)方法對補(bǔ)丁進(jìn)行了約束[6]，但由于約束不完整無法保證補(bǔ)丁的質(zhì)量。一些自動(dòng)程序修復(fù)方法通過學(xué)習(xí)開發(fā)者修復(fù)缺陷的過程提高修復(fù)的精確性[6-7]，但無法保證訓(xùn)練集的污染不會(huì)影響修復(fù)結(jié)果的正確性。針對自動(dòng)程序修復(fù)方法修復(fù)缺陷的質(zhì)量問題，國內(nèi)外研究者做了大量工作。當(dāng)前，缺陷修復(fù)質(zhì)量的研究主要集中在修復(fù)精度與修復(fù)速度[8-9]。筆者同樣關(guān)注自動(dòng)程序修復(fù)方法修復(fù)缺陷的質(zhì)量問題，但不同于現(xiàn)有研究，筆者主要研究自動(dòng)程序修復(fù)方法修復(fù)缺陷過程中的安全性。筆者指出了自動(dòng)程序修復(fù)方法在修復(fù)缺陷過程中存在的安全隱患場景，并為兩種安全隱患場景分別提出相應(yīng)的解決方案。

1 安全隱患場景

1.1 臟補(bǔ)丁源

開發(fā)者能夠通過代碼克隆(Code Cloning)加速開發(fā)進(jìn)程，然而代碼克隆嚴(yán)重降低程序的安全性。代碼克隆是程序缺陷傳播的最主要方式[10]，不僅增加了軟件維護(hù)成本，而且嚴(yán)重影響代碼的質(zhì)量[11]。與代碼克隆類似，基于搜索的自動(dòng)程序修復(fù)方法在補(bǔ)丁空間中搜索合適的補(bǔ)丁修復(fù)程序缺陷，補(bǔ)丁空間來源于程序或開源的代碼倉庫，如果補(bǔ)丁攜帶缺陷，缺陷則會(huì)隨補(bǔ)丁進(jìn)入程序中。

圖1 臟補(bǔ)丁源污染程序過程

如圖1所示，自動(dòng)程序修復(fù)方法首先定位缺陷錯(cuò)誤位置，緊接著通過解析缺陷位置處的語義信息，在補(bǔ)丁空間中搜索合適的補(bǔ)丁。自動(dòng)程序修復(fù)方法常用的補(bǔ)丁空間有自身代碼、開源社區(qū)和問答網(wǎng)站等，并最終通過測試集驗(yàn)證補(bǔ)丁的正確性。如果在補(bǔ)丁空間中選取的補(bǔ)丁中包含新的未知缺陷，且新的缺陷不能通過該測試集進(jìn)行檢測，那么自動(dòng)程序修復(fù)方法就會(huì)將未知缺陷引入到程序中，進(jìn)而影響程序的安全性和質(zhì)量，會(huì)增加軟件的維護(hù)成本。

定義F為程序中所有函數(shù)的集合，V為程序中所有缺陷函數(shù)的集合，R為開源代碼倉庫中函數(shù)的集合，S為補(bǔ)丁空間中函數(shù)的集合。對于集合V和S，滿足V?F，S=F∪R。定義缺陷檢測器DE為測試集E維度下函數(shù)集F到{0, 1}的一個(gè)映射，可表示為

(1)

缺陷檢測器DE接受一個(gè)程序并返回1(包含缺陷)或0(不包含缺陷)。

定義1自動(dòng)程序修復(fù)方法修復(fù)程序缺陷需要根據(jù)缺陷函數(shù)的語義信息，在補(bǔ)丁空間中尋找合適的補(bǔ)丁，在測試集E的維度下成功修復(fù)缺陷:

?f∈V, ?s∈S:DE(R(f,s))=0 ，

(2)

其中，R(f,s)為返回自動(dòng)程序修復(fù)方法通過補(bǔ)丁函數(shù)s修復(fù)缺陷函數(shù)f后的結(jié)果，即返回插入補(bǔ)丁后的函數(shù)。

自動(dòng)程序修復(fù)方法根據(jù)缺陷函數(shù)f和測試集E在集合S中尋找補(bǔ)丁s，使DE(s)‖DE(R(f,s))=0。然而，在其他測試集(如E′)維度下有DE′(s) = 1，即補(bǔ)丁s包含未知缺陷，但在測試集E′維度下無法定位該未知缺陷，此時(shí)修復(fù)后的程序包含該未知缺陷，使DE′(R(f,s)) = 1，此時(shí)觸發(fā)安全隱患。

1.2 臟測試集

測試預(yù)言(Test Oracle)是判斷軟件系統(tǒng)測試是否通過的關(guān)鍵機(jī)制，對整個(gè)軟件測試過程起決定性作用[12]。當(dāng)前主流的自動(dòng)程序修復(fù)方法主要通過測試集定位程序缺陷，并使用測試集校驗(yàn)補(bǔ)丁的正確性。因此，測試集的正確性在很大程度上影響自動(dòng)程序修復(fù)方法的修復(fù)結(jié)果。

定義2臟測試集是指測試集中部分測試用例的測試預(yù)言與期望功能不一致，即

?e∈E:O(e)≠H(e) ，

(3)

其中，O(e)為返回測試用例e的測試預(yù)言，H(e)為返回e的期望功能。

自動(dòng)程序修復(fù)方法若使用臟測試集定位缺陷和校驗(yàn)補(bǔ)丁，就能夠?qū)㈠e(cuò)誤補(bǔ)丁引入程序，甚至影響程序原本正常的功能。

如圖2所示，自動(dòng)程序修復(fù)方法使用臟測試集定位到錯(cuò)誤的缺陷位置，此時(shí)基于搜索的自動(dòng)程序修復(fù)方法根據(jù)錯(cuò)誤的缺陷位置在補(bǔ)丁空間中尋找錯(cuò)誤的修復(fù)補(bǔ)丁，而基于語義的自動(dòng)程序修復(fù)方法會(huì)生成錯(cuò)誤的補(bǔ)丁約束，合成錯(cuò)誤的補(bǔ)丁。因此，如果采用該場景下生成的補(bǔ)丁修復(fù)程序，則將使程序產(chǎn)生新的缺陷，進(jìn)而影響程序的安全性。

圖2 臟測試集污染程序過程

2 解決方案

2.1 補(bǔ)丁校驗(yàn)方案

為不干預(yù)自動(dòng)程序修復(fù)方法的修復(fù)過程，針對上節(jié)指出的臟補(bǔ)丁源場景，可通過兩個(gè)步驟的篩選獲取安全性更高的補(bǔ)丁，即對自動(dòng)程序修復(fù)生成的補(bǔ)丁候選者列表進(jìn)行優(yōu)先級排序，并靜態(tài)分析校驗(yàn)候選者列表中的補(bǔ)丁。

2.1.1 補(bǔ)丁候選者優(yōu)先級排序

為促使自動(dòng)程序修復(fù)方法快速獲取安全性更高的補(bǔ)丁，文中針對不同的補(bǔ)丁空間，對補(bǔ)丁候選者列表采取不同的排序策略。

如果自動(dòng)程序修復(fù)方法是在自身代碼中搜尋補(bǔ)丁，則以復(fù)雜度作為指標(biāo)對補(bǔ)丁候選者列表進(jìn)行排序，具體流程如圖3所示。復(fù)雜度越高的代碼，涵蓋缺陷的可能性越高。文中首先根據(jù)函數(shù)單位和控制流圖將程序代碼劃分為多個(gè)區(qū)域，并采用文獻(xiàn)[13]提出的程序復(fù)雜度計(jì)算方法計(jì)算每個(gè)區(qū)域的復(fù)雜度，再根據(jù)補(bǔ)丁候選者列表中各補(bǔ)丁候選者所在的區(qū)域，遵照區(qū)域復(fù)雜度進(jìn)行排序，優(yōu)先獲取復(fù)雜度更低的補(bǔ)丁。

圖3 以自身代碼為搜索空間的補(bǔ)丁優(yōu)先級列表生成流程

圖4 以開源社區(qū)或問答網(wǎng)站為搜索空間的優(yōu)先級列表生成流程

如果自動(dòng)化程序修復(fù)方法在開源社區(qū)或問答網(wǎng)站中尋找補(bǔ)丁，則以信任度作為指標(biāo)對候選者列表進(jìn)行排序，具體流程如圖4所示。通過開源社區(qū)或問答網(wǎng)站給出的評分指標(biāo)對補(bǔ)丁候選者列表進(jìn)行排序。例如，以代碼的星級作為GitHub(https://github.com/)中代碼質(zhì)量的衡量指標(biāo)。

補(bǔ)丁候選者列表的具體排序算法描述如下：

輸入：補(bǔ)丁候選者集合P。

輸出：優(yōu)先級列表Pl。

for eachpinPdo

ifp∈自身程序 then

獲取p所在區(qū)域的復(fù)雜度

根據(jù)復(fù)雜度將p插入到Pl

else ifp∈開源社區(qū)∪問答網(wǎng)站 then

獲取p在開源社區(qū)或問答網(wǎng)站分?jǐn)?shù)

根據(jù)分?jǐn)?shù)將p插入到Pl

else then

將p插入到Pl的末尾

end if

end for。

2.1.2 靜態(tài)校驗(yàn)分析

為防止程序引入臟補(bǔ)丁，需要校驗(yàn)補(bǔ)丁候選者，文中采用靜態(tài)分析技術(shù)對補(bǔ)丁候選者進(jìn)行校驗(yàn)。程序靜態(tài)分析(Program Static Analysis)在不運(yùn)行程序[14]且不需要測試集的情況下，校驗(yàn)代碼的可靠性和安全性。文中采用LLVM(Low Level Virtual Machine)[15]框架中的Clang靜態(tài)分析器(Clang Static Analyzer)構(gòu)建靜態(tài)分析框架。LLVM構(gòu)建的靜態(tài)分析框架具有更好的擴(kuò)展性和伸縮性，能夠快速地為特定的缺陷設(shè)計(jì)檢查器，并且能夠使用LLVM內(nèi)置的缺陷檢查器，包括空指針、不安全應(yīng)用程序編程接口和除零錯(cuò)誤等。

圖5 安全補(bǔ)丁獲取流程

如圖5所示，對2.1.1節(jié)中優(yōu)先級列表中的候選補(bǔ)丁進(jìn)行安全性校驗(yàn)。具體來講，首先從補(bǔ)丁候選者優(yōu)先級列表中抽取優(yōu)先級最高的補(bǔ)丁；然后通過靜態(tài)分析校驗(yàn)該補(bǔ)丁的安全性，如果通過靜態(tài)分析檢查，則再使用測試集對該補(bǔ)丁進(jìn)行評估，如果該補(bǔ)丁通過測試集，則該補(bǔ)丁正確合法，自動(dòng)程序修復(fù)方法使用該補(bǔ)丁修復(fù)程序缺陷；若該補(bǔ)丁未通過靜態(tài)分析檢查或未通過測試集，則選取優(yōu)先級次高的補(bǔ)丁進(jìn)行檢驗(yàn)，直至找到正確合法的補(bǔ)丁或檢驗(yàn)完所有的候選補(bǔ)丁。

靜態(tài)分析校驗(yàn)補(bǔ)丁的具體算法描述如下：

輸入：測試集E、優(yōu)先級列表Pl。

輸出：安全補(bǔ)丁p。

for eachpinPldo

if 靜態(tài)分析補(bǔ)丁p不包含缺陷 then

if 補(bǔ)丁p通過測試集Ethen

返回p

end if

end if

end for。

2.2 補(bǔ)丁校驗(yàn)方案

針對第1節(jié)指出的臟測試集場景，對測試集的格式進(jìn)行規(guī)范。測試集中的每個(gè)測試用例對應(yīng)一個(gè)執(zhí)行流，這里規(guī)定測試集中每一個(gè)執(zhí)行流成對，即相同的執(zhí)行流出現(xiàn)2n次(其中n∈Z+)，并定義形式化的測試集:

E={ei|i∈[1,2n]} 。

(4)

測試集E中(e2k-1,e2k)為一個(gè)測試用例對，其中k∈[1,n]，每個(gè)測試用例對中測試用例對應(yīng)的執(zhí)行流相同。規(guī)范測試集的格式后，判斷測試用例對中兩個(gè)測試用例的執(zhí)行流是否相同，如果不相同，則該測試集是臟測試集，阻止自動(dòng)程序修復(fù)方法通過該測試集進(jìn)行缺陷定位和補(bǔ)丁校驗(yàn)。

自動(dòng)程序修復(fù)方法在進(jìn)行修復(fù)前無法準(zhǔn)確選擇能夠定位缺陷的具體測試用例。定位缺陷的測試用例的測試預(yù)言與程序執(zhí)行流的返回結(jié)果不一致會(huì)導(dǎo)致錯(cuò)誤的檢測結(jié)果。例如，根據(jù)三角形的3條邊a、b和c，確定三角形(a,b,c)的形狀，(3, 3, 3)執(zhí)行流的返回結(jié)果是等腰三角形，該結(jié)果表明程序包含缺陷，而此時(shí)測試預(yù)言為等邊三角形，該測試用例的測試預(yù)言與執(zhí)行流的返回結(jié)果不一致，導(dǎo)致誤認(rèn)為該測試用例為臟測試用例。因此通過數(shù)據(jù)流分析增加檢測精度，通過數(shù)據(jù)流向判斷執(zhí)行流是否一致辨別臟測試用例，算法的具體描述如下：

輸入：測試集E={ei|i∈[1,2n]}。

if測試集格式符合規(guī)范 then

for eachkin [1,n] do

ife2k-1的執(zhí)行流≠e2k的執(zhí)行流then

end if

end for

end if

其中判斷測試用例對(e2k-1,e2k)中測試用例對應(yīng)的執(zhí)行流是否相等的判斷算法如下：

輸入：測試用例對(e2k-1,e2k)。

輸出：e2k-1是否為臟測試用例。

if oracle(e2k-1)≠func(e2k-1) or oracle(e2k)≠func(e2k) then

e2k-1為臟測試用例

else if數(shù)據(jù)流分析e2k-1和e2k的執(zhí)行過程不一致 then

e2k-1為臟測試用例

end if。

3 實(shí)驗(yàn)測試與結(jié)果分析

3.1 實(shí)驗(yàn)樣本與環(huán)境配置

如表1所示，選取Defects4J[16]缺陷程序集作為測試樣本。Defects4J缺陷程序集中共有5個(gè)項(xiàng)目，即Chart、Lang、Math、Time和Closure Compiler，但由于Closure Compiler項(xiàng)目中缺少測試用例，無法定位缺陷，因此選取前4個(gè)項(xiàng)目進(jìn)行實(shí)驗(yàn)測試。

表1 Defects4J缺陷程序集

修復(fù)工具以GenProg和PAR[7]為基礎(chǔ)，并增加兩種解決方案，即補(bǔ)丁校驗(yàn)方案和測試集校驗(yàn)方案。選取GenProg和PAR的理由如下：GenProg開源且擴(kuò)展性好，易于觀察修復(fù)效果；PAR雖未開源，但修復(fù)效果接近人工修復(fù)且實(shí)現(xiàn)簡單。文中根據(jù)PAR提供的修復(fù)模板，重新實(shí)現(xiàn)了PAR原型。將添加解決方案后的修復(fù)工具分別命名為GenProg Plus和PAR Plus。

將Defects4J中的原測試集拷貝一份，并將測試用例和測試預(yù)言根據(jù)2.2節(jié)提出的規(guī)范測試集格式隨機(jī)更改拷貝測試集中的測試用例(更改后的測試用例執(zhí)行流相同但具體測試數(shù)據(jù)不同)，并在拷貝測試集中設(shè)置臟測試用例，最后組合原測試集和拷貝測試集以生成規(guī)范測試集。以測試用例數(shù)為2 205的Chart項(xiàng)目為例，設(shè)原測試集為E，文中將E拷貝一份(設(shè)為E′)，并在E′中隨機(jī)設(shè)置臟測試用例，然后通過項(xiàng)目源碼將部分測試用例修改為執(zhí)行流相同、具體測試數(shù)據(jù)不同的測試用例，再將E與E′中的測試用例按順序?qū)?yīng)，最終生成測試用例數(shù)為4 410的規(guī)范測試集。

實(shí)驗(yàn)測試運(yùn)行在Ubuntu 14.04.6環(huán)境下，具體配置為AMD Ryzen 52 500U with Radeon Vega Mobile Gfx 2.00GHz、8GB內(nèi)存。

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 測試集校驗(yàn)結(jié)果分析

測試集校驗(yàn)方案對缺陷測試集的校驗(yàn)結(jié)果如表2和圖6所示，其中Chart項(xiàng)目中包含的錯(cuò)誤用例數(shù)為35個(gè)，實(shí)際檢出數(shù)為38個(gè)，即測試集校驗(yàn)方案存在少量的誤報(bào)。Defects4J中的其他項(xiàng)目與Chart項(xiàng)目類似，也存在少量的誤報(bào)。Defects4J中4個(gè)項(xiàng)目的誤報(bào)率分別為8.57%、5.26%、7.02%和7.94%，平均誤報(bào)率為7.20%，具體如圖7所示。

表2 測試集校驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明，文中所提出的測試集校驗(yàn)方案能夠根據(jù)測試用例的執(zhí)行流判斷測試集的正確性，高準(zhǔn)度地定位測試集中臟測試用例的位置，并通過臟測試用例的錯(cuò)誤位置，將臟測試用例修改正確。雖然測試集校驗(yàn)方案存在少量的誤報(bào)，但誤報(bào)率較小，能夠?qū)㈠e(cuò)誤測試用例的范圍顯著縮小，并由人工在修改臟測試用例時(shí)確認(rèn)誤報(bào)的測試用例。

3.2.2 過濾補(bǔ)丁方案實(shí)驗(yàn)結(jié)果分析

GenProg在修復(fù)Defects4J中缺陷時(shí)可選的補(bǔ)丁候選者較少，因此，文中在Defects4J中添加額外代碼，從而提供比GenProg更多的補(bǔ)丁候選者驗(yàn)證補(bǔ)丁校驗(yàn)方案。GenProg和PAR中添加補(bǔ)丁校驗(yàn)方案前后修復(fù)缺陷數(shù)對比分別如表3和表4所示。實(shí)驗(yàn)結(jié)果表明，GenProg和GenProg Plus、PAR和PAR Plus修復(fù)Defects4J中各項(xiàng)目的缺陷數(shù)都分別相同，因而添加補(bǔ)丁校驗(yàn)方案不影響自動(dòng)程序修復(fù)方法的穩(wěn)定性。添加補(bǔ)丁校驗(yàn)方案后，自動(dòng)程序修復(fù)方法仍然能夠盡可能地修復(fù)程序缺陷。

圖6 錯(cuò)誤用例數(shù)和測試集校驗(yàn)方案實(shí)例檢出數(shù)對比

圖7 測試集校驗(yàn)方案誤報(bào)率

表3 GenProg添加方案前后修復(fù)缺陷數(shù)對比

表4 PAR添加前后修復(fù)缺陷數(shù)對比

圖8揭示了Math項(xiàng)目(版本號：85)內(nèi)UnivariateRealSolverUtils.Java文件中缺陷程序代碼片段使用補(bǔ)丁校驗(yàn)方案前后的修復(fù)結(jié)果。在添加補(bǔ)丁校驗(yàn)方案前，修復(fù)后的程序雖然能夠通過測試集，但仍然存在缺陷。如圖8(b)中第200行所示，程序無法應(yīng)對function不為空且需要拋出異常的情況；而添加補(bǔ)丁校驗(yàn)方案后，條件語句中涵蓋的情況更多，獲取的補(bǔ)丁能夠通過測試集且不包含新的缺陷。從實(shí)驗(yàn)修復(fù)結(jié)果不難發(fā)現(xiàn)，自動(dòng)程序修復(fù)方法修復(fù)缺陷的結(jié)果存在安全隱患，而添加文中所提出的補(bǔ)丁校驗(yàn)方案后，在修復(fù)缺陷的同時(shí)，選擇的補(bǔ)丁更為安全有效。

圖8 添加補(bǔ)丁校驗(yàn)方案前后的修復(fù)結(jié)果對比

4 結(jié)束語

筆者指出自動(dòng)程序修復(fù)方法在修復(fù)缺陷過程中存在的兩種安全隱患場景，即臟補(bǔ)丁源場景和臟測試集場景，并為兩種安全隱患場景分別提出相應(yīng)的解決方案，即補(bǔ)丁校驗(yàn)方案和測試集校驗(yàn)方案。此外，基于Defects4J庫中的測試用例和缺陷程序進(jìn)行了實(shí)驗(yàn)測試。實(shí)驗(yàn)結(jié)果表明，筆者所提出的測試集校驗(yàn)方案能夠精確地定位臟測試用例，并具有較小的平均誤報(bào)率(即7.2%)；所提出的補(bǔ)丁校驗(yàn)方案不影響自動(dòng)程序修復(fù)方法的穩(wěn)定性，并能夠促使自動(dòng)程序修復(fù)方法獲取更安全有效的補(bǔ)丁。筆者所提出的兩種解決方案能夠有效消除自動(dòng)程序修復(fù)方法在修復(fù)過程中出現(xiàn)的安全隱患，并提高程序修復(fù)的穩(wěn)定性和修復(fù)后程序的安全性。