程序錯誤自動修複目前面臨的問題？

01-09

程序錯誤修複目前可大致劃分為兩大類技術：

1）基於搜索（generate-and-validate）

方法：通過錯誤修復規則生成候選補丁組成的搜索空間，利用搜索演算法進行補丁驗證並找到正確的補丁，一般用回歸測試。

主要代表性工作：genprog(遺傳演算法，icse09/icse12)、par(人工模板，icse13)、spr(condition synthesis+transformation schemas，fse15-MIT)、QAFix(QA ，Crash Bugs，ASE15-PKU)等等。

2）基於語義分析（targeted
techniques）

方法：針對特定錯誤進行分析，利用靜態分析技術（數據流、控制流、符號執行和約束求解等）獲得希望的補丁。
主要代表性工作：SemFix(局部符號執行，icse13)、DirectFix(icse2015)、Anglelix(輕量符號執行，icse16)、DFixer (控制流分析/提前獲取鎖，icse2016)等等。

ps：國內的大牛 @熊英飛老師講的軟體分析中，感覺以上兩類技術正好契合「軟體解析學」和「程序分析」兩類方法，但目前兩類技術遇到的困難和問題是什麼呢？

我不傾向於認為SemFix/DirectFix/Angelix是和基於搜索的技術截然不同的方法。因為他們實際是把修復問題轉成了約束求解問題，而約束求解的SMT Solver用的方法是轉成SAT問題，而SAT問題的解法還是搜索。所以歸根結底還是搜索。

如果要分類，我比較傾向於有完整規約的修復和沒有完整規約的修復兩類。基於測試的修復工作都是屬於沒有完整規約的。沒有完整規約的修複目前遇到的主要問題是正確率低，即可以得到很多通過測試的（plausible）補丁，但是這些補丁中正確的不多。所以現在做的很多工作都是如何在眾多plausible補丁中盡量把正確的給找出來。這裡主要用的是一些啟發式規則和學習得到的概率模型，比如Prophet的排序，Qlose的語義相似性等等。我們今年的一篇在投工作也是想辦法通過啟發式規則和概率模型提高正確率（http://arxiv.org/abs/1608.07754）。Westley Weimer在DSN上也有一篇position論文討論了提高正確率的各種可能方法。

有完整規約的工作有相當大一部分都是針對特定類型的缺陷，比如上面提到的蔡彥的DFixer，我們之前也做過修復內存泄露的LeakFix(LeakFix)，其規約都是和原程序語義等價。這些工具的問題面向各自不同的領域各不相同。剩下一部分是假設程序中有完整的形式化規約，比如在CAV上的多篇修復的論文，以及裴玉老師的工作。這部分工作的一大問題如果最後要證明規約，通常比較難scale up，支持不了大程序。同時Benchmark也是一個問題，並沒有那麼多有規約的程序可以做實驗。