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

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

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

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

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

1 安全隱患場景

1.1 臟補丁源

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

圖1 臟補丁源污染程序過程

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

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

(1)

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

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

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

(2)

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

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

1.2 臟測試集

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

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

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

(3)

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

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

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

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

2 解決方案

2.1 補丁校驗方案

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

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

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

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

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

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

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

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

輸入：補丁候選者集合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)站分數(shù)

根據(jù)分數(shù)將p插入到Pl

else then

將p插入到Pl的末尾

end if

end for。

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

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

圖5 安全補丁獲取流程

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

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

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

輸出：安全補丁p。

for eachpinPldo

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

if 補丁p通過測試集Ethen

返回p

end if

end if

end for。

2.2 補丁校驗方案

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

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

(4)

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

自動程序修復(fù)方法在進行修復(fù)前無法準確選擇能夠定位缺陷的具體測試用例。定位缺陷的測試用例的測試預(yù)言與程序執(zhí)行流的返回結(jié)果不一致會導(dǎo)致錯誤的檢測結(jié)果。例如，根據(jù)三角形的3條邊a、b和c，確定三角形(a,b,c)的形狀，(3, 3, 3)執(zhí)行流的返回結(jié)果是等腰三角形，該結(jié)果表明程序包含缺陷，而此時測試預(yù)言為等邊三角形，該測試用例的測試預(yù)言與執(zhí)行流的返回結(jié)果不一致，導(dǎo)致誤認為該測試用例為臟測試用例。因此通過數(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 實驗測試與結(jié)果分析

3.1 實驗樣本與環(huán)境配置

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

表1 Defects4J缺陷程序集

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

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

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

3.2 實驗結(jié)果分析

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

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

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

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

3.2.2 過濾補丁方案實驗結(jié)果分析

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

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

圖7 測試集校驗方案誤報率

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

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

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

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

4 結(jié)束語

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