前言

本文旨在介紹2016年軟件學報文章——自動程序修復方法研究進展。

1 作者

中文引用格式: 玄躋峰,任志磊,王子元,謝曉園,江賀.自動程序修復方法研究進展.軟件學報,2016,27(4):771?784. http://www.
jos.org.cn/1000-9825/4972.htm
英文引用格式: Xuan JF, Ren ZL, Wang ZY, Xie XY, Jiang H. Progress on approaches to automatic program repair. Ruan Jian
Xue Bao/Journal of Software, 2016,27(4):771?784 (in Chinese). http://www.jos.org.cn/1000-9825/4972.htm

2 摘要內容

回顧了基于測試集的程序修復的現有文獻,按照自動修復方法和實證基礎兩個方面陳述了研究進展.

首先,將已有的自動修復方法劃分為 3類, 分別是基于搜索的、基于代碼窮舉的和基于約束求解的補丁生成方法;

其次,細致地描述了程序修復的實證研究基礎以及該研究領域中的爭議;

然后,簡要介紹了程序修復的相關技術作為修復方法的補充;最后做出總結,描述了面臨的機遇和挑戰.

3 introduction

1） 歷史數據表明,超過45%的現代軟件開發成本消耗于定位和修復 bug 過程中。
[1] Pressman RS. Software Engineering: A Practitioner’s Approach. 7th ed., New York: McGraw-Hill, 2010. 437?443.

文獻引用的好棒

2）隨著軟件測試和調試技術的提高,自動化的程序 bug 定位技術已經得到了一定的
研究和發展[2,3],然而自動化的程序 bug 修復方法仍處在初級階段.隨著程序 bug 數量的日益積累,自動修復技術
的深入研究及應用已迫在眉睫.

**就是說現在缺陷定位發展的比APR成熟一點。
好像確實是這樣**

[2] Xie X, Chen TY, Kuo FC, Xu B. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM
Trans. on Software Engineering and Methodology, 2013,22(4):31:1?31:40. [doi: 10.1145/2522920.2522924]
[3] Wen WZ, Li BX, Sun XB, Liu CC. Technique of software fault localization based on hierarchical slicing spectrum. Ruan Jian Xue
Bao/Journal of Software, 2013,24(5):977?992 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4342.htm [doi:
10.3724/SP.J.1001.2013.04342]

疑問：為什么要引用文獻[3]呢，是因為同樣來自journal of software嗎

3）自動生成程序補丁(patch),進而修復程序中的錯誤.修復中產生的程序補丁既可以自動添加
到程序中,也可以用于指導開發者繼續改進代碼.與現代軟件工業中廣泛出現的敏捷開發(agile development)和
持續集成(continuous integration)相結合,自動程序修復方法將有效地降低程序修復的成本.從技術角度來看,研
究者將程序修復看作從潛在的搜索空間(search space)中搜索補丁的過程,而優秀的修復技術可以大幅度提高補
丁搜索的準確率,并減少用于搜索的時間消耗[5,6].該研究思路與基于搜索的軟件工程契合[7].例如,自動程序修
復中的先驅方法 GenProg 就是一種基于遺傳規劃(genetic programming)的 C 程序修復算法[8]

這里講了：自動生成的補丁的用處 + 工業化潛力 + 基于搜索的軟件工程 + 補丁搜索、搜索空間（search space）

4 自動修復面臨什么挑戰？？

• 一方面,研究者嘗試設計算法為程序自動生成補丁,而所生成的補丁與真實人工添加的補丁尚存較大
  差別;
• 另一方面,研究者正在探索自動修復的實證基礎(empirical foundation),然而該研究并非一帆風順,曾在
  2014 年[9]和 2015 年[10,11]掀起了兩次領域內的學術爭論

第一個，經常會得到可行但非正確補丁；
第二個，我感覺和第一個一樣的。

[9] Monperrus M. A critical review of automatic patch generation learned from human-written patches: Essay on the problem statement
and the evaluation of automatic software repair. In: Proc. of the 36th Int’l Conf. on Software Engineering (ICSE). 2014. 234?242.
[doi: 10.1145/2568225.2568324]
[10] Qi Z, Long F, Achour S, Rinard M. An analysis of patch plausibility and correctness for generate-and-validate patch generation
systems. In: Proc. of the Int’l Symp. on Software Testing and Analysis (ISSTA). 2015. 24?36. [doi: 10.1145/2771783.2771791]
[11] Smith EK, Barr E, Le Goues C, Brun Y. Is the cure worse than the disease? Overfitting in automated program repair. In: Proc. of
the European Software Engineering Conf. and ACM SIGSOFT Int’l Symp. on Foundations of Software Engineering (ESEC/FSE).
2015. 532?543. [doi: 10.1145/2786805.2786825]

這三篇文獻都值得認真一讀，無一不是頂會

5 截至本文成文之際(2015 年 8 月 31 日),自動程序修復方法尚未有工業應用.

說明，工業級應用確實難度太大。

6 APR的修復框架，我覺得很有用

APR修復框架，當然，是基于測試用例集的APR

7 震驚，kali竟然沒有做缺陷定位，而且SemFix竟然沒有補丁驗證。

需要注意的是:其一,基于代碼窮舉的方法和基于約束求解的方法也可以看作某種程度的搜索,但本文遵從
基于搜索的軟件工程領域的約定,只將第 1 類方法稱為基于搜索的補丁生成方法;其二,圖 1 的流程是經過總結
已有方法而得到的大概流程 [24,26].在一些修復算法中,某些步驟可能被簡化.例如:在基于代碼窮舉的方法
Kali[10]中,所有的程序語句沒有經過故障定位,而按照自然順序直接排列;而在基于約束求解的方法 SemFix[22]
中,在補丁生成后無需進行補丁的驗證.第 3 節詳細介紹修復方法

我感覺這句話對我很有用

8 想問下基于約束求解的方法到底咋實現的，還不用補丁驗證

基于搜索的方法是程序
修復中的主要部分,尤其在領域創始之初更占有重要地位,代表算法包括基于遺傳規劃的抽象語法樹修復算法
GenProg[5]、基于程序等價性的遺傳修復算法 AE[20]、基于隨機搜索的修復算法 RSRepair[16]等.基于代碼窮舉
的方法無差別地變異全部可疑語句,同時,有策略地窮舉可能出現的代碼修改,追求補丁的有效性而忽略算法效
率.這類算法不多,代表算法包括程序變異算法[21]、代碼消除算法 Kali[10].基于約束求解的方法,顧名思義,將補
丁生成轉換為約束求解問題,應用求解器直接計算可行解(feasible solution),進而轉換為最終補丁,代表算法包
括程序語義修復 SemFix[22]、補丁簡化算法 DirectFix[23]、條件 bug 修復 Nopol[24,25]等.

9 文章已經意識到了補丁正確性的問題，看來補丁正確性早有關注

能夠通過測試集的補丁并不一定正確.正確性(correctness)指的是修復后的程序達到了預期的行為,即,程序
的輸出能夠滿足潛在的測試預言(test oracle).例如,一個修復劃分三角形類別程序的補丁正確,指的是程序可以
無誤地劃分任何潛在的三角形類別,而不是僅僅滿足有限數量的測試用例的通過.正確性目前還不能通過自動
技術完成,只能手動驗證.近期的一些工作采用了正確性作為評價標準[10,25,26].

[10] Qi Z, Long F, Achour S, Rinard M. An analysis of patch plausibility and correctness for generate-and-validate patch generation
systems. In: Proc. of the Int’l Symp. on Software Testing and Analysis (ISSTA). 2015. 24?36. [doi: 10.1145/2771783.2771791]
[25] Xuan JF, Martinez M, DeMarco F, Clément M, Lamelas-Marcote S, Durieux T, Le Berre D, Monperrus M. Nopol: Automatic repair
of conditional statement bugs in Java programs. Technical Report, INRIA, 2015. 1?22.
[26] Martinez T, Durieux T, Xuan JF, Monperrus M. Automatic repair of real bugs in Java: A large-scale experiment on the Defects4J
dataset. Technical Report, arXiv:1505.07002, ArXiv, 2015. 1?11.

10 這些文章都值得一看

2012 年,Qi 等人[12,13]提出通過弱重編譯(weak recompilation)的方法優化 GenProg 的修復效率,能夠較早地
找到補丁.其后的 2013 年,他們[14]應用故障記錄的測試用例排序(fault-recorded test prioritization)方法進一步提
高了修復效率.此外,他們[15]還通過程序修復的結果來評估故障定位方法.

[12] Qi Y, Mao X, Lei Y. Making automatic repair for large-scale programs more efficient using weak recompilation. In: Proc. of the
IEEE Int’l Conf. on Software Maintenance (ICSM). 2012. 254?263. [doi: 10.1109/ICSM.2012.6405280]
[13] Qi Y, Mao X, Wen Y, Dai Z, Gu B. More efficient automatic repair of large-scale programs using weak recompilation. Science
China Information Sciences, 2012,55(12):2785?2799. [doi: 10.1007/s11432-012-4741-1]
[14] Qi Y, Mao X, Lei Y. Efficient automated program repair through fault-recorded testing prioritization. In: Proc. of the IEEE Int’l
Conf. on Software Maintenance (ICSM). 2013. 180?189. [doi: 10.1109/ICSM.2013.29]
[15] Qi Y, Mao X, Lei Y, Wang C. Using automated program repair for evaluating the effectiveness of fault localization techniques. In:
Proc. of the Int’l Symp. on Software Testing and Analysis (ISSTA). 2013. 191?201. [doi: 10.1145/2483760.2483785]
[16] Qi Y, Mao X, Lei Y, Dai Z, Wang C. The strength of random search on automated program repair. In: Proc. of the 36th Int’l Conf.
on Software Engineering (ICSE). 2014. 254?265. [doi: 10.1145/2568225.2568254]

11 APR的發展

2013 年,Kim 等人[6]從人工書寫的補丁中學習代碼模式,并將模式與 GenProg 相融合生成補丁.該方法生成
的補丁可以避免出現通過優化算法而得到的無意義的補丁.Weimer 等人[20]考慮增強發現潛在補丁的能力,提出
了基于程序等價性(program equivalence)的遺傳修復算法 AE.
2014 年,Qi 等人[16]通過研究發現,GenProg 算法中的遺傳規劃算法對于高效生成補丁并不奏效.他們用隨機
搜索(random search)替換了遺傳算法,并設計了 RSRepair 用于程序修復.實驗結果表明:相對于 GenProg 方法,
RSRepair 能夠減少生成補丁的時間消耗.
2015 年,Martinez 和 Monperrus[33]通過挖掘程序修復的歷史數據,建立了概率模型預測新 bug 的修復.超過 6
萬個 Java 語言的代碼變更提交(code commit)被轉換為抽象語法樹,用于修復概率模型的建立.同是 2015 年,
Long 和 Rinard[34]提出了 Prophet,一種學習現有補丁以指導未來補丁排序的算法.它通過最大似然(maximum
likelihood)模型識別最可能成功的補丁的概率,其算法本質是補丁排序的過程.該方法可以修復 69 個真實 bug
中的 15 個,具有一定的準確度

我感覺這些都可以看一看。

12 基于約束求解的方法——原理

2012 年,該類算法的先驅,Nguyen 等人提出 SemFix[22],一種 C 程序的基于約束的語義修復算法.該算法將測
試用例轉換為約束,并應用 SMT(satisfiability modulo theories)求解器求解,最終轉換為補丁并輸出.生成補丁的
過程源自基于組件的程序合成算法(component based program synthesis)[37],該算法將備選語句作為組件,提取預
期的輸入輸出,并建立約束求解模型.另外,SemFix 采用 Tarantula 算法[38]定位潛在的 bug 位置.與基于搜索的方
法,如 GenProg 不同,SemFix 不需要為生成的補丁調用測試用例驗證修復性;約束機制已將測試用例作為輸入,
并進而轉化為解輸出.
2014 年,DeMarco 和 Xuan 等人[24,25]設計了 Nopol,一種面向 Java 條件語句 bug 的基于約束求解的方法.該
方法針對錯誤條件或條件語句缺失這兩種常見 bug 進行修復.過程中,采用天使定位(angelic fix localization)算
法[39]確定潛在修復的位置.與 SemFix 不同,Nopol 中的天使定位算法只針對條件值(即布爾值),其搜索空間小,
計算成本低,可以應用于大規模程序.該算法中采用利于面向對象故障定位的 Ochiai 算法[40]獲取被修復語句的
排序.實驗中,Nopol 可以修復 22 個大規模 Java 程序的真實 bug 中的 17 個,具有較高的準確率.

2015 年,Mechtaev 等人提出了補丁簡化算法 DirectFix[23].該方法將補丁中潛在的程序組件轉換為最大可滿足性問題(maximum satisfiability,即 MaxSat),求解后轉換為具體的簡化后的補丁.

Ke 等人[41]設計了 SearchRepair,一種基于語義代碼搜索(semantic code search)的修復方法.該方法通過將數
據庫中的代碼段編碼為基于輸入輸出的 SMT 模型中的約束,進而求解補丁.相對于已有算法 GenProg、 AE 和
RSRepair,算法 SearchRepair 可以獲得更多的補丁,且補丁質量較高

13 震驚，原來Nopol如12 中所說： 采用天使定位算法只針對條件值，使得搜索空間變小，計算成本低。。。確實創新了

從這里面我學到了：
1）因為約束求解，如果不只針對條件值的話，會導致搜索空間特別大，這樣的話確實不適用于大規模缺陷程序修復

2）原來idea可以這樣出來，看來平時得多思考，多讀書、論文。

原來原理就是：（參考SemFix的描述）通過將測試用例轉化成約束。。。進行求解。

總結

以上是生活随笔為你收集整理的2016年自动修复综述——自动程序修复方法研究进展 [软件学报 Journal of Software 2016]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。