技術(shù)報(bào)告基于搜索的軟件自動(dòng)修復(fù)框架及其關(guān)鍵問(wèn)題探討

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

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

3、方法可以分為兩大類(lèi)：基于語(yǔ)義的修復(fù)方法和基于搜索的方法4。其中，基于搜索的方法是最早提出的一類(lèi)軟件程序修復(fù)方法5。該方法是一種“生成確認(rèn)”方法，將修復(fù)問(wèn)題看成一個(gè)組合優(yōu)化問(wèn)題，運(yùn)用元啟發(fā)式搜索算法，在搜索空間內(nèi)通過(guò)搜索生成候選補(bǔ)丁，并借助配套測(cè)試用例集對(duì)該補(bǔ)丁進(jìn)行驗(yàn)證?；谒阉鞯能浖詣?dòng)修復(fù)能夠利用已有的程序信息，并結(jié)合已有的軟件維護(hù)技術(shù)，提供自動(dòng)化的軟件修復(fù)方案，易于部署和實(shí)施，在軟件程序修復(fù)中占有重要地位。已有的軟件維護(hù)技術(shù)，例如缺陷定位，測(cè)試數(shù)據(jù)生成等，這些技術(shù)的應(yīng)用降低了軟件自動(dòng)修復(fù)問(wèn)題研究的難度，但是，如何更好地將上述技術(shù)應(yīng)用到軟件修復(fù)中，以及針對(duì)性的提高修復(fù)的效率，在該研究領(lǐng)域還需

4、要解決很多問(wèn)題。在已有工作的基礎(chǔ)上，提出和傳統(tǒng)軟件維護(hù)技術(shù)相結(jié)合的基于搜索的軟件自動(dòng)修復(fù)框架，指出其中需要解決的一些關(guān)鍵問(wèn)題，并提出一些可行的解決方案，可以為從事軟件自動(dòng)修復(fù)研究提供參考。2 基于搜索的軟件自動(dòng)修復(fù)框架（Framework ofautomatic software repair based on search method）軟件修復(fù)首先需要確定軟件缺陷位于源程序的位置，其次，采用合適的方法生成補(bǔ)丁，最后，還要評(píng)估生成補(bǔ)丁的有效性。自動(dòng)性的修復(fù)工作除了需要源程序外，還需要有配套的測(cè)試用例集，并且測(cè)試用例集中至少包含一個(gè)運(yùn)行結(jié)果未達(dá)預(yù)期的測(cè)試用例。一方面，需要測(cè)試用例集收集程序的執(zhí)

5、行頻譜，定位軟件的缺陷；另一方面，若修復(fù)方法生成的補(bǔ)丁可以使得配套的所有測(cè)試用例均能執(zhí)行通過(guò)，則可以認(rèn)為該補(bǔ)丁正確?；诖?，軟件自動(dòng)修復(fù)工作可以分為三個(gè)方面：（1）缺陷定位，（2）補(bǔ)丁生成，（3）補(bǔ)丁驗(yàn)證。進(jìn)一步，如圖1所示，本文提出基于搜索的軟件修復(fù)框架可以分為五個(gè)階段，期望在充分使用傳統(tǒng)技術(shù)的基礎(chǔ)上，例如缺陷定位、回歸測(cè)試等等，致力提高軟件修復(fù)的效率。該框架依托于源程序和已有的測(cè)試用例集，首先進(jìn)行缺陷定位，得到可疑的程序?qū)嶓w隊(duì)列；然后，取懷疑度最大的程序?qū)嶓w，確定測(cè)試相關(guān)的范圍，并對(duì)已有的測(cè)試用例集更新，接著，采用搜索的方法生成相關(guān)程序?qū)嶓w的補(bǔ)丁；對(duì)于生成的補(bǔ)丁，通過(guò)回歸測(cè)試的方法對(duì)補(bǔ)丁進(jìn)

6、行驗(yàn)證，如果回歸測(cè)試通過(guò)，則修復(fù)工作結(jié)束，否則，繼續(xù)依次取懷疑度最大的實(shí)體，迭代進(jìn)行補(bǔ)丁生成和驗(yàn)證。若上述步驟沒(méi)有得到正確的程序補(bǔ)丁，則修復(fù)失敗。3 基于搜索的軟件自動(dòng)修復(fù)關(guān)鍵問(wèn)題（Key issuesin search based automatic software repair）基于搜索的軟件自動(dòng)修復(fù)框架涉及很多軟件測(cè)試或維護(hù)的關(guān)鍵問(wèn)題，目前尚未存在有效解決方案的如表1所列，在現(xiàn)有的軟件測(cè)試和維護(hù)技術(shù)的研究基礎(chǔ)上，根據(jù)采用技術(shù)的不同，這些關(guān)鍵問(wèn)題，涵蓋以下三個(gè)方面：（1）缺陷定位，（2）搜索策略，（3）測(cè)試用例的質(zhì)量。表1所列關(guān)鍵問(wèn)題的解決將有助于提高基于搜索的軟件自動(dòng)修復(fù)效率。3.1

7、缺陷定位所謂缺陷定位，是指基于程序的結(jié)構(gòu)和測(cè)試用例執(zhí)行的軌跡，確定軟件缺陷的位置?；谌毕荻ㄎ坏慕Y(jié)果，能夠有針對(duì)性的修復(fù)程序，從而降低程序修復(fù)的成本?？梢钥闯?，缺陷定位是軟件自動(dòng)修復(fù)中的先決問(wèn)題，只有能夠?qū)⒋嬖谌毕莸某绦驅(qū)嶓w識(shí)別出來(lái)，才能夠根據(jù)定位的結(jié)果生成程序補(bǔ)丁。在軟件自動(dòng)修復(fù)問(wèn)題中，為了利用執(zhí)行信息，便于部署實(shí)施，基于程序頻譜的缺陷定位方法被廣泛應(yīng)用。按照程序頻譜統(tǒng)計(jì)的數(shù)據(jù)，缺陷定位的結(jié)果一般是排好序的程序?qū)嶓w序列，依據(jù)缺陷定位方法的計(jì)算，序列首位的程序?qū)嶓w含有缺陷的可能性最大，序列末位的程序?qū)嶓w含有缺陷的可能性最小。如果序列首位的程序?qū)嶓w就是含有缺陷的程序?qū)嶓w，那么，只需要迭代一次補(bǔ)丁

8、生成并驗(yàn)證的過(guò)程就可以完成軟件自動(dòng)修復(fù)過(guò)程。如果序列末位的程序?qū)嶓w是含有缺陷的程序?qū)嶓w，那么，軟件自動(dòng)修復(fù)的過(guò)程需要迭代多次才能找到正確的補(bǔ)丁。因此，缺陷定位結(jié)果的精確程度會(huì)極大的影響后續(xù)生成補(bǔ)丁的效率。在缺陷定位中，一個(gè)待解決的關(guān)鍵問(wèn)題是大規(guī)模軟件的缺陷定位。在實(shí)際應(yīng)用中，現(xiàn)有的基于頻譜的缺陷定位方法需要能夠準(zhǔn)確提取每個(gè)程序?qū)嶓w被成功測(cè)試用例以及失敗測(cè)試用例覆蓋的次數(shù)，而軟件的程序規(guī)模一般比實(shí)證研究中的測(cè)試對(duì)象規(guī)模大，這使得程序的頻譜提取較難，缺陷定位的計(jì)算復(fù)雜度增加，且定位結(jié)果不準(zhǔn)確，這就需要能夠針對(duì)較大規(guī)模的軟件提出針對(duì)性的缺陷定位方法。 另外，需要解決的關(guān)鍵問(wèn)題是，在缺陷定位中，定位的

9、程序?qū)嶓w往往是失效的程序?qū)嶓w，但該語(yǔ)句并不一定存在缺陷。具體而言，如果某個(gè)程序?qū)嶓w存在缺陷，那么，處于該實(shí)體之后的程序?qū)嶓w，由于缺陷的傳播關(guān)系，都有可能發(fā)生失效。如果能夠在缺陷定位中，每次都定位到導(dǎo)致程序失效的缺陷源頭，將極大的提高軟件自動(dòng)修復(fù)的效率。3.2 搜索策略在軟件工程中引入搜索的方法來(lái)解決問(wèn)題，最早由Harman提出6，用來(lái)解決一些組合優(yōu)化問(wèn)題。在軟件自動(dòng)修復(fù)中，搜索的策略是影響修復(fù)效率的重要因素。用來(lái)修復(fù)程序的候選補(bǔ)丁，可以看成是對(duì)程序的一次修改行為，那么可以基于程序的修改，構(gòu)造候選補(bǔ)丁，而生成候選補(bǔ)丁并進(jìn)行選擇的過(guò)程可以看成一個(gè)組合優(yōu)化問(wèn)題。基于該組合優(yōu)化問(wèn)題，可以嘗試建立問(wèn)題的

10、數(shù)學(xué)模型并采用搜索的方法求解。如前所述，基于搜索的軟件自動(dòng)修復(fù)技術(shù)是從候選空間中尋找補(bǔ)丁并進(jìn)行評(píng)價(jià)的過(guò)程。針對(duì)該組合優(yōu)化問(wèn)題，如何建立一個(gè)有效的數(shù)學(xué)模型，學(xué)術(shù)界多次就此類(lèi)問(wèn)題研究5。在建立模型和求解的過(guò)程中，如果因補(bǔ)丁生成的操作算子較少，過(guò)小的解空間，容易導(dǎo)致無(wú)法找到最優(yōu)解；而補(bǔ)丁生成的操作算子太多，過(guò)大的解空間將增加求解難度，典型的表現(xiàn)是，在求解過(guò)程中，易生成太多近似解，加大補(bǔ)丁驗(yàn)證的所耗費(fèi)的時(shí)間。另外，針對(duì)建立的數(shù)學(xué)模型，采取合適的求解方法也是修復(fù)技術(shù)的關(guān)鍵。已有的用來(lái)生成補(bǔ)丁和選擇補(bǔ)丁的搜索方法如表2所列。這些方法，先構(gòu)造程序?qū)?yīng)的抽象語(yǔ)法樹(shù)或測(cè)試用例集，組成進(jìn)化種群，然后使用不同的搜索

11、策略進(jìn)化并搜索，以期望得到正確的程序補(bǔ)丁。其中，用遺傳規(guī)劃方法的GenProg5比較耗時(shí)，而采用隨機(jī)算法，雖然能夠減少方法的執(zhí)行時(shí)間的，但需要更多的先驗(yàn)知識(shí)9。其他的搜索算法也存在效率過(guò)低，求解時(shí)間過(guò)長(zhǎng)的問(wèn)題。這意味著，對(duì)已有的搜索方法進(jìn)一步研究，提出效率更高，更具有針對(duì)性的策略，是已有以后研究工作的重點(diǎn)。在不同的方法中，如何表示補(bǔ)丁，如何評(píng)價(jià)補(bǔ)丁，均是求解方法無(wú)可回避的難點(diǎn)。此外，參考有效的軟件可靠性模型10，如何去除一些求解正確，但違背程序語(yǔ)義，不能應(yīng)用于實(shí)際修復(fù)的補(bǔ)丁，也是以后研究工作需要解決的問(wèn)題。3.3 測(cè)試用例的質(zhì)量對(duì)于修復(fù)后的程序，如果所有測(cè)試用例的運(yùn)行結(jié)果均符合預(yù)期，這說(shuō)明軟件

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

13、方法有助于提高軟件自動(dòng)修復(fù)效率。更為重要的是，軟件初始配套的測(cè)試用例規(guī)模一般是比較大的，若所有測(cè)試用例均要運(yùn)行，一次修復(fù)的若干補(bǔ)丁驗(yàn)證的過(guò)程就需要執(zhí)行很長(zhǎng)時(shí)間，這將極大的降低軟件自動(dòng)修復(fù)的效率。所以在軟件修復(fù)中，需要合理的確定測(cè)試范圍，并根據(jù)測(cè)試范圍來(lái)選擇測(cè)試用例對(duì)修復(fù)后的程序進(jìn)行驗(yàn)證。該關(guān)鍵問(wèn)題的解決不僅有利于提高回歸測(cè)試的效率，也有利于進(jìn)一步減少軟件自動(dòng)修復(fù)的時(shí)間。需要提及的是，基于搜索的軟件自動(dòng)修復(fù)關(guān)鍵問(wèn)題不僅僅是本文列出的六個(gè)問(wèn)題，但在本文提出的基于搜索的軟件自動(dòng)修復(fù)框架下，上述六個(gè)問(wèn)題的解決，應(yīng)用于基于搜索的方法時(shí)，無(wú)疑將極大的提高軟件自動(dòng)修復(fù)的效率。4 結(jié)論（Conclusion）

14、軟件自動(dòng)修復(fù)方法是目前軟件維護(hù)領(lǐng)域的一個(gè)研究熱點(diǎn)。本文結(jié)合傳統(tǒng)的軟件測(cè)試技術(shù)，提出基于搜索的軟件自動(dòng)修復(fù)框架，將軟件修復(fù)看成一個(gè)不斷使用測(cè)試用例對(duì)程序進(jìn)行補(bǔ)丁的選擇并評(píng)價(jià)的迭代過(guò)程。研究者需要注意缺陷定位、搜索策略，以及測(cè)試用例的質(zhì)量，并提出了一些關(guān)鍵問(wèn)題。因此，在已有研究工作的基礎(chǔ)上，針對(duì)本文提出的關(guān)鍵問(wèn)題，給出有效的具體解決方案將是下一步的研究工作。參考文獻(xiàn)（References）1 Kim D，et al.Automatic Patch Generation Learned from Human-Written PatchesC.International Conference on S

15、oftware Engineering，2013：802-811.2 Goues CL，F(xiàn)orrest S，Weimer W.Current Challenges in Automatic Software RepairJ.Software Quality Journal，2013，21（3）：421-443.3 Pei Y，et al.Automated Fixing of Programs with ContractsJ.IEEE Transactions on Software Engineering，2014，40（5）：427-449.4 玄躋峰，等.自動(dòng)程序修復(fù)方法研究進(jìn)展J.軟件

16、學(xué)報(bào)，2016，27（4）：771-784.5 Weimer W，et al.Automatically Finding Patches using Genetic ProgrammingC.International Conference on Software Engineering，2009：364-374.6 Harman M，Mansouri SA，Zhang YY.Search-Based Software Engineering：Trends，Techniques and ApplicationsJ.ACM Computing Surveys，2012，45（1）：1-6.7 L

17、ong F，Rinard M.An Analysis of the Search Spaces for Generate and Validate Patch Generation SystemsC.International Conference on Software Engineering，2016：702-713.8 Arcuri A，Yao X.A Novel Co-Evolutionary Approach to Automatic Software Bug FixingC.IEEE Congress on Evolutionary Computation（IEEE World Congress on Computational Intelligence），2008：162-168.9 Qi YH，et al.The Strength of Random Searc