基于搜索的軟件自動修復(fù)框架及其關(guān)鍵問題探討

吳川

摘 要：軟件在開發(fā)和維護(hù)的過程中均可能產(chǎn)生軟件缺陷，如果能夠成功自動修復(fù)部分缺陷，則可以有效減少程序調(diào)試時間，避免損失。軟件自動修復(fù)是一個新興課題，尚存在很多需要解決的問題。本文首先介紹了軟件自動修復(fù)的概念，并提出了基于搜索的軟件自動修復(fù)的框架；接著，從缺陷定位、搜索策略、測試數(shù)據(jù)生成三個方面概括了基于搜索的軟件自動修復(fù)面臨的主要挑戰(zhàn)，以及需要解決的一些關(guān)鍵問題；最后，總結(jié)全文并指出下一步的工作。所提框架及其關(guān)鍵問題的探討，有助于軟件自動修復(fù)技術(shù)的進(jìn)一步研究和在工業(yè)生產(chǎn)中的推廣應(yīng)用。

關(guān)鍵詞：基于搜索的軟件自動修復(fù)；缺陷定位；測試數(shù)據(jù)生成

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

1 引言（Introduction）

對于有缺陷的軟件，一旦發(fā)生運(yùn)行故障或其他軟件錯誤，需要及時的對源程序進(jìn)行修復(fù)。在發(fā)現(xiàn)軟件缺陷后，軟件自動修復(fù)是指，利用已有的程序補(bǔ)丁自動修復(fù)程序的過程[1]。具體而言，首先，識別可能存在缺陷的程序?qū)嶓w，其次，根據(jù)具有缺陷可能性的大小對可疑程序?qū)嶓w排序，并自動生成相關(guān)程序的補(bǔ)丁，接著，通過某種方法評估程序補(bǔ)丁的有效性，并選擇正確的補(bǔ)丁。缺陷軟件自動修復(fù)問題的研究具有極高的現(xiàn)實(shí)需求，可以有效減少程序調(diào)試時間，提高軟件運(yùn)行的效率，減少因缺陷帶來的損失，因此，吸引了很多研究人員的關(guān)注[2-4]。

按照補(bǔ)丁生成的方式，軟件自動修復(fù)的方法可以分為兩大類：基于語義的修復(fù)方法和基于搜索的方法[4]。其中，基于搜索的方法是最早提出的一類軟件程序修復(fù)方法[5]。該方法是一種“生成—確認(rèn)”方法，將修復(fù)問題看成一個組合優(yōu)化問題，運(yùn)用元啟發(fā)式搜索算法，在搜索空間內(nèi)通過搜索生成候選補(bǔ)丁，并借助配套測試用例集對該補(bǔ)丁進(jìn)行驗(yàn)證?；谒阉鞯能浖詣有迯?fù)能夠利用已有的程序信息，并結(jié)合已有的軟件維護(hù)技術(shù)，提供自動化的軟件修復(fù)方案，易于部署和實(shí)施，在軟件程序修復(fù)中占有重要地位。

已有的軟件維護(hù)技術(shù)，例如缺陷定位，測試數(shù)據(jù)生成等，這些技術(shù)的應(yīng)用降低了軟件自動修復(fù)問題研究的難度，但是，如何更好地將上述技術(shù)應(yīng)用到軟件修復(fù)中，以及針對性的提高修復(fù)的效率，在該研究領(lǐng)域還需要解決很多問題。

在已有工作的基礎(chǔ)上，提出和傳統(tǒng)軟件維護(hù)技術(shù)相結(jié)合的基于搜索的軟件自動修復(fù)框架，指出其中需要解決的一些關(guān)鍵問題，并提出一些可行的解決方案，可以為從事軟件自動修復(fù)研究提供參考。

2 基于搜索的軟件自動修復(fù)框架（Framework of

automatic software repair based on search method）

軟件修復(fù)首先需要確定軟件缺陷位于源程序的位置，其次，采用合適的方法生成補(bǔ)丁，最后，還要評估生成補(bǔ)丁的有效性。自動性的修復(fù)工作除了需要源程序外，還需要有配套的測試用例集，并且測試用例集中至少包含一個運(yùn)行結(jié)果未達(dá)預(yù)期的測試用例。一方面，需要測試用例集收集程序的執(zhí)行頻譜，定位軟件的缺陷；另一方面，若修復(fù)方法生成的補(bǔ)丁可以使得配套的所有測試用例均能執(zhí)行通過，則可以認(rèn)為該補(bǔ)丁正確?；诖耍浖詣有迯?fù)工作可以分為三個方面：（1）缺陷定位，（2）補(bǔ)丁生成，（3）補(bǔ)丁驗(yàn)證。進(jìn)一步，如圖1所示，本文提出基于搜索的軟件修復(fù)框架可以分為五個階段，期望在充分使用傳統(tǒng)技術(shù)的基礎(chǔ)上，例如缺陷定位、回歸測試等等，致力提高軟件修復(fù)的效率。

該框架依托于源程序和已有的測試用例集，首先進(jìn)行缺陷定位，得到可疑的程序?qū)嶓w隊(duì)列；然后，取懷疑度最大的程序?qū)嶓w，確定測試相關(guān)的范圍，并對已有的測試用例集更新，接著，采用搜索的方法生成相關(guān)程序?qū)嶓w的補(bǔ)?。粚τ谏傻难a(bǔ)丁，通過回歸測試的方法對補(bǔ)丁進(jìn)行驗(yàn)證，如果回歸測試通過，則修復(fù)工作結(jié)束，否則，繼續(xù)依次取懷疑度最大的實(shí)體，迭代進(jìn)行補(bǔ)丁生成和驗(yàn)證。若上述步驟沒有得到正確的程序補(bǔ)丁，則修復(fù)失敗。

3 基于搜索的軟件自動修復(fù)關(guān)鍵問題（Key issues

in search based automatic software repair）

基于搜索的軟件自動修復(fù)框架涉及很多軟件測試或維護(hù)的關(guān)鍵問題，目前尚未存在有效解決方案的如表1所列，在現(xiàn)有的軟件測試和維護(hù)技術(shù)的研究基礎(chǔ)上，根據(jù)采用技術(shù)的不同，這些關(guān)鍵問題，涵蓋以下三個方面：（1）缺陷定位，（2）搜索策略，（3）測試用例的質(zhì)量。表1所列關(guān)鍵問題的解決將有助于提高基于搜索的軟件自動修復(fù)效率。

3.1 缺陷定位

所謂缺陷定位，是指基于程序的結(jié)構(gòu)和測試用例執(zhí)行的軌跡，確定軟件缺陷的位置?；谌毕荻ㄎ坏慕Y(jié)果，能夠有針對性的修復(fù)程序，從而降低程序修復(fù)的成本?？梢钥闯觯毕荻ㄎ皇擒浖詣有迯?fù)中的先決問題，只有能夠?qū)⒋嬖谌毕莸某绦驅(qū)嶓w識別出來，才能夠根據(jù)定位的結(jié)果生成程序補(bǔ)丁。在軟件自動修復(fù)問題中，為了利用執(zhí)行信息，便于部署實(shí)施，基于程序頻譜的缺陷定位方法被廣泛應(yīng)用。按照程序頻譜統(tǒng)計(jì)的數(shù)據(jù)，缺陷定位的結(jié)果一般是排好序的程序?qū)嶓w序列，依據(jù)缺陷定位方法的計(jì)算，序列首位的程序?qū)嶓w含有缺陷的可能性最大，序列末位的程序?qū)嶓w含有缺陷的可能性最小。如果序列首位的程序?qū)嶓w就是含有缺陷的程序?qū)嶓w，那么，只需要迭代一次補(bǔ)丁生成并驗(yàn)證的過程就可以完成軟件自動修復(fù)過程。如果序列末位的程序?qū)嶓w是含有缺陷的程序?qū)嶓w，那么，軟件自動修復(fù)的過程需要迭代多次才能找到正確的補(bǔ)丁。因此，缺陷定位結(jié)果的精確程度會極大的影響后續(xù)生成補(bǔ)丁的效率。

在缺陷定位中，一個待解決的關(guān)鍵問題是大規(guī)模軟件的缺陷定位。在實(shí)際應(yīng)用中，現(xiàn)有的基于頻譜的缺陷定位方法需要能夠準(zhǔn)確提取每個程序?qū)嶓w被成功測試用例以及失敗測試用例覆蓋的次數(shù)，而軟件的程序規(guī)模一般比實(shí)證研究中的測試對象規(guī)模大，這使得程序的頻譜提取較難，缺陷定位的計(jì)算復(fù)雜度增加，且定位結(jié)果不準(zhǔn)確，這就需要能夠針對較大規(guī)模的軟件提出針對性的缺陷定位方法。

另外，需要解決的關(guān)鍵問題是，在缺陷定位中，定位的程序?qū)嶓w往往是失效的程序?qū)嶓w，但該語句并不一定存在缺陷。具體而言，如果某個程序?qū)嶓w存在缺陷，那么，處于該實(shí)體之后的程序?qū)嶓w，由于缺陷的傳播關(guān)系，都有可能發(fā)生失效。如果能夠在缺陷定位中，每次都定位到導(dǎo)致程序失效的缺陷源頭，將極大的提高軟件自動修復(fù)的效率。

3.2 搜索策略

在軟件工程中引入搜索的方法來解決問題，最早由Harman提出[6]，用來解決一些組合優(yōu)化問題。在軟件自動修復(fù)中，搜索的策略是影響修復(fù)效率的重要因素。用來修復(fù)程序的候選補(bǔ)丁，可以看成是對程序的一次修改行為，那么可以基于程序的修改，構(gòu)造候選補(bǔ)丁，而生成候選補(bǔ)丁并進(jìn)行選擇的過程可以看成一個組合優(yōu)化問題?；谠摻M合優(yōu)化問題，可以嘗試建立問題的數(shù)學(xué)模型并采用搜索的方法求解。

如前所述，基于搜索的軟件自動修復(fù)技術(shù)是從候選空間中尋找補(bǔ)丁并進(jìn)行評價(jià)的過程。針對該組合優(yōu)化問題，如何建立一個有效的數(shù)學(xué)模型，學(xué)術(shù)界多次就此類問題研究[5]。在建立模型和求解的過程中，如果因補(bǔ)丁生成的操作算子較少，過小的解空間，容易導(dǎo)致無法找到最優(yōu)解；而補(bǔ)丁生成的操作算子太多，過大的解空間將增加求解難度，典型的表現(xiàn)是，在求解過程中，易生成太多近似解，加大補(bǔ)丁驗(yàn)證的所耗費(fèi)的時間。

另外，針對建立的數(shù)學(xué)模型，采取合適的求解方法也是修復(fù)技術(shù)的關(guān)鍵。已有的用來生成補(bǔ)丁和選擇補(bǔ)丁的搜索方法如表2所列。這些方法，先構(gòu)造程序?qū)?yīng)的抽象語法樹或測試用例集，組成進(jìn)化種群，然后使用不同的搜索策略進(jìn)化并搜索，以期望得到正確的程序補(bǔ)丁。其中，用遺傳規(guī)劃方法的GenProg[5]比較耗時，而采用隨機(jī)算法，雖然能夠減少方法的執(zhí)行時間的，但需要更多的先驗(yàn)知識[9]。其他的搜索算法也存在效率過低，求解時間過長的問題。這意味著，對已有的搜索方法進(jìn)一步研究，提出效率更高，更具有針對性的策略，是已有以后研究工作的重點(diǎn)。在不同的方法中，如何表示補(bǔ)丁，如何評價(jià)補(bǔ)丁，均是求解方法無可回避的難點(diǎn)。此外，參考有效的軟件可靠性模型[10]，如何去除一些求解正確，但違背程序語義，不能應(yīng)用于實(shí)際修復(fù)的補(bǔ)丁，也是以后研究工作需要解決的問題。

3.3 測試用例的質(zhì)量

對于修復(fù)后的程序，如果所有測試用例的運(yùn)行結(jié)果均符合預(yù)期，這說明軟件自動修復(fù)成功；反之，則修復(fù)失敗。因此，測試用例質(zhì)量影響軟件修復(fù)過程的成敗[11]。

首先，高質(zhì)量的測試用例集是基于搜索的軟件自動修復(fù)的方法必須提供的且測試用例應(yīng)該隨著程序的修復(fù)而不斷迭代更新。這是因?yàn)椋S著程序的修復(fù)，程序的控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)也可能發(fā)生改變，在這樣的情況下，已有的測試用例可能存在充分性不夠或部分失效。此時，如果按照現(xiàn)有測試用例修復(fù)軟件的程序，那么，有可能存在過適應(yīng)問題，即雖然修復(fù)的程序通過了測試用例的驗(yàn)證，但是修復(fù)的程序離預(yù)期的程序語義相差較大或仍然存在缺陷。在這種情況下，合理的做法是根據(jù)修復(fù)后的程序，對測試用例進(jìn)行更新。鑒于軟件修復(fù)的過程是一個迭代修復(fù)的過程，高效率的測試用例再生成方法有助于提高軟件自動修復(fù)效率。

更為重要的是，軟件初始配套的測試用例規(guī)模一般是比較大的，若所有測試用例均要運(yùn)行，一次修復(fù)的若干補(bǔ)丁驗(yàn)證的過程就需要執(zhí)行很長時間，這將極大的降低軟件自動修復(fù)的效率。所以在軟件修復(fù)中，需要合理的確定測試范圍，并根據(jù)測試范圍來選擇測試用例對修復(fù)后的程序進(jìn)行驗(yàn)證。該關(guān)鍵問題的解決不僅有利于提高回歸測試的效率，也有利于進(jìn)一步減少軟件自動修復(fù)的時間。

需要提及的是，基于搜索的軟件自動修復(fù)關(guān)鍵問題不僅僅是本文列出的六個問題，但在本文提出的基于搜索的軟件自動修復(fù)框架下，上述六個問題的解決，應(yīng)用于基于搜索的方法時，無疑將極大的提高軟件自動修復(fù)的效率。

4 結(jié)論（Conclusion）

軟件自動修復(fù)方法是目前軟件維護(hù)領(lǐng)域的一個研究熱點(diǎn)。本文結(jié)合傳統(tǒng)的軟件測試技術(shù)，提出基于搜索的軟件自動修復(fù)框架，將軟件修復(fù)看成一個不斷使用測試用例對程序進(jìn)行補(bǔ)丁的選擇并評價(jià)的迭代過程。研究者需要注意缺陷定位、搜索策略，以及測試用例的質(zhì)量，并提出了一些關(guān)鍵問題。因此，在已有研究工作的基礎(chǔ)上，針對本文提出的關(guān)鍵問題，給出有效的具體解決方案將是下一步的研究工作。

參考文獻(xiàn)（References）

[1] Kim D，et al.Automatic Patch Generation Learned from Human-Written Patches[C].International Conference on Software Engineering，2013：802-811.

[2] Goues CL，F(xiàn)orrest S，Weimer W.Current Challenges in Automatic Software Repair[J].Software Quality Journal，2013，21（3）：421-443.

[3] Pei Y，et al.Automated Fixing of Programs with Contracts[J].IEEE Transactions on Software Engineering，2014，40（5）：427-449.

[4] 玄躋峰，等.自動程序修復(fù)方法研究進(jìn)展[J].軟件學(xué)報(bào)，2016，

27（4）：771-784.

[5] Weimer W，et al.Automatically Finding Patches using Genetic Programming[C].International Conference on Software Engineering，2009：364-374.

[6] Harman M，Mansouri SA，Zhang YY.Search-Based Software Engineering：Trends，Techniques and Applications[J].ACM Computing Surveys，2012，45（1）：1-6.

[7] Long F，Rinard M.An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems[C].International Conference on Software Engineering，2016：702-713.

[8] Arcuri A，Yao X.A Novel Co-Evolutionary Approach to Automatic Software Bug Fixing[C].IEEE Congress on Evolutionary Computation（IEEE World Congress on Computational Intelligence），2008：162-168.

[9] Qi YH，et al.The Strength of Random Search on Automated Program Repair[C].Software Engineering，2014：254-265.

[10] 王二威.軟件可靠性模型研究綜述[J].軟件工程，2016（02）：

1-2；57.

[11] Smith E K，et al.Is the Cure Worse than the Disease？ Overfitting in Automated Program Repair[C].10th Joint Meeting on Foundations of Software Engineering，2015：532-543.

作者簡介：

吳 川（1980-），男，博士，講師.研究領(lǐng)域：軟件工程.