吳川

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

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

中圖分類號：TP311 文獻標識碼：A

1 引言（Introduction）

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

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

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

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

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

automatic software repair based on search method）

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

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

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

in search based automatic software repair）

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

3.1 缺陷定位

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

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

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

3.2 搜索策略

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

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

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

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

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

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

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

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

4 結(jié)論（Conclusion）

軟件自動修復方法是目前軟件維護領(lǐng)域的一個研究熱點。本文結(jié)合傳統(tǒng)的軟件測試技術(shù)，提出基于搜索的軟件自動修復框架，將軟件修復看成一個不斷使用測試用例對程序進行補丁的選擇并評價的迭代過程。研究者需要注意缺陷定位、搜索策略，以及測試用例的質(zhì)量，并提出了一些關(guān)鍵問題。因此，在已有研究工作的基礎上，針對本文提出的關(guā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] 玄躋峰，等.自動程序修復方法研究進展[J].軟件學報，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)域：軟件工程.