disclaimer：我對于 program repair 的了解僅限于一節(jié)軟件工程的課，觀點也大多是基于課上的討論，我對于 program repair 相關的研究也沒有進行更廣泛的閱讀，所以以下的敘述可能是 biased。

今天我們要講一個和程序修復（program repair）有關的故事。看到標題熟悉程序修復的朋友可能就懂了，我要開始講 GenProg 了。

在2009年，一篇名為 Automatically finding patches using genetic programming 的論文橫空出世，介紹了如何使用進化算法進行程序修復（program repair）。所謂程序修復，就是給定一個程序和一個不能通過測試的 test，然后使用一些可以被自動化的手段來自動修復程序中的bug，使得這個程序能夠通過測試。這看起來很難實現(xiàn)，對吧？考慮到程序生成（program synthesis）的搜索空間之大（對于非常非常小的程序，這樣的空間就能有2的幾百次方）。更為神奇的是，他們所針對的程序往往都是非常大的，比如php和python的源碼，動輒幾十甚至幾百萬行?？赡苁怯捎谶@篇文章的效果實在是太好了，它一舉拿下了當年 ICSE 的 best paper，并在之后的其他會議中多次獲得獎項。同一時期的另外幾篇 paper 的出現(xiàn)（AutoFix，ClearView）更使得2009年可以說是成為了程序修復的元年，在這一年之后關于程序修補的論文數(shù)量激增，程序修補迅速成為了一個軟件工程中炙手可熱的領域。

所以這篇文章講的是什么呢？我當時沒有直接讀那篇文章，而是讀了他們?nèi)曛蟮囊黄麨锳 Systematic Study of Automated Program Repair: Fixing 55 out of 105 Bugs for $8 Each的回顧文章。文章中算法的基本思路很直接：在源代碼上出 bug 可能性高的位置（fault locoalization）進行隨機的突變操作來模擬人手動編寫 patch 的過程，然后在修補后的程序上再跑一遍 test，計算一個適合函數(shù)（fitness function），在看起來更有希望的程序進行交配，也就是把它們上的 patch 縫合在一起。重復進行這個過程，直到所有的 test 都通過。這里的突變操作共有三種（是不是像極了寫編程作業(yè)時候的你）：

刪除一段代碼。從程序的其他地方復制一段代碼插入。從程序的其他地方復制一段代碼替換之前的代碼。

在 evaluation 的部分中，它們收集了大型軟件如 Python （407k LOC），php （1046k LOC），gzip（491k LOC），wireshark（2814k LOC）在 git 的 commit history 中出現(xiàn)的 105 個 bug，然后使用分布式計算來大規(guī)模的運行 GenProg。最后發(fā)現(xiàn)，在這 105 個 bug 中，55 個 bug 得到了修補，平均的花費僅需 $7.32。這個結果不能不讓人感到震驚，考慮到一個硅谷程序員每天的工資都要幾百美刀，這實在是好的驚人了。可以想見的是，如果這個技術能夠獲得應用，那很多程序員肯定都失業(yè)了。

最后，文章的作者公開了測試所用的數(shù)據(jù)集，并且（就像所有 paper 一樣）添加了一小節(jié) threats to validity 的聲明，聲稱為了防止數(shù)據(jù)集是精挑細選以增強效果的，他們用來測試的軟件都是他們能夠獲得的最好努力了（如http://Sourceforge.net/Google code上行數(shù)最多的開源軟件），但是他們只 evaluate 了開源軟件，只考慮 race condition 意外的 bug 之類的云云，總之就是一些讀者看到標題就會跳過的東西。

好了，到目前為止，這篇 paper 看起來展示了遺傳算法在軟件工程領域的巨大成功。但是真的是這樣嗎？事情沒有那么簡單，2015年的 ISSTA 上發(fā)表了一篇名為 An Analysis of Patch Plausibility and Correctness for Generate-and-Validate Patch Generation Systems 的 paper。paper 中在 GenProg 和其他兩個基于“打補丁”的 Program Repair 工具上重復了那個 105 個 bug實驗，然后發(fā)現(xiàn)了一些十分有趣的結論：

在 GenProg 聲稱的修復的 55 個 bug 里，共有 37 個被修復的 bug 其實根本不能通過測試樣例，之所以能夠通過的原因是因為對于運行的結果檢測不夠強（weak proxy）。比如說在測試 Stack 的時候，程序員可能會寫下如“for i in range(10): a.push(i); assert(a.size()==10)”的測試樣例，但是一個永遠只會往數(shù)組里放入1的實現(xiàn)也可以通過測試——因為這里只檢測了數(shù)據(jù)結構的 cardinality 而沒有測試這其中的每一個元素的正確性。在 php 的測試中，GenProg聲稱共修復了 44 個 bug 中的 28 個，這 28 個修復中包括了 196 個 patch。這其中只有 29 個能夠“真正地”通過測試數(shù)據(jù)。這是因為測試的腳本也是用 php 寫成的，所以 php 的運行結果依賴于這個 php 編譯器，所以GenProg 就生成了一個使測試腳本的永遠 exit code 返回 0 的程序來通過所有測試。在前面提到的GenProg“通過了測試”的所有 18 個 patch 中，只有 2 個 patch 是正確的，剩下的 patch 雖然通過了測試，但事實上都有著很多非?；闹嚨腻e誤。但是由于弱測試數(shù)據(jù)的原因，這樣的錯誤并不能夠被檢測出來。在 GenProg 原論文的 case study 中，用到的 patch 便是這兩個正確的 patch 中的一個。為了研究清楚 GenProg 不能夠生成出正確的 patch 是不是因為測試數(shù)據(jù)太弱的原因——也許加強了數(shù)據(jù)錯誤的 patch 就不會出現(xiàn)了呢？——文章的作者又挑選了其中的兩個 GenProg 只會輸出錯誤 patch 的 bug 并加強了數(shù)據(jù)以覆蓋更多的可能出錯的 case，結果顯示在加強了數(shù)據(jù)之后，GenProg 無法產(chǎn)生輸出任何的 patch。在對 GenProg 產(chǎn)生出來的所有對于測試返回了正確答案的 110 個 patch 的研究發(fā)現(xiàn)，這110 個 patch 中有 104 個都等同于把和 bug 所在模塊的代碼直接刪除。在把錯誤的部分刪除之后，程序十分有效的避免了諸如整數(shù)溢出，buffer溢出。因為測試數(shù)據(jù)過弱，直接將功能性的代碼刪除就可以通過所有的測試——只要你什么都不做，你就什么都不會出錯～

除了文章里面提到的，GenProg 其實還生成了一些好玩的程序（以下僅憑印象復述）：

對于一個所有 test 都在docker里面運行的程序，GenProg 生成了一個殺掉 docker 進程的程序并通過了測試。對于一個通過輸入輸出文件來進行測試的程序，GenProg生成了一個直接修改正確答案的程序并通過了測試。對于某一個程序，GenProg刪除了測試目錄下的所有文件并通過了測試。對于另一個程序，GenProg直接修改了保存正確答案的那塊內(nèi)存區(qū)域并通過了測試...GenProg是如何通過測試的

最后，文章的作者提出了一個名為 Kali 的程序修補工具，這個工具只會做一件事，那就是刪除——將 GenProg 的變異算子從插入/刪除/修改三個操作變?yōu)橹皇Ｏ聞h除，并增加了把 if 里的condition覆蓋為恒真或恒假的操作，以及在方法中插入直接返回 NULL 和 -1的語句。結果顯示，這個 Kali 的效果甚至吊打 GenProg——GenProg只產(chǎn)生了兩個正確的補丁，而 Kali 產(chǎn)生了三個！如果我們考慮前文所有通過了測試但是不一定對的patch，那么在 GenProg 需要花費 $7.3 的價格在分布式集群上花費幾個小時才能找到patch的情況下，Kalin往往能夠在十幾分鐘就能找到 patch！也就是說，僅僅從結果來看，我們也應該使用 Kali 而不是 GenProg。嗯，可見，刪庫跑路才是正確的選擇——只要你什么都不做，你就什么都不會做錯！

讓我們再來回顧一下一些基于或是提到 GenProg 的研究：

早先一篇文章指出并且考慮了如下的問題：為什么 GenProg 往往生成的 patch 往往比人類程序員現(xiàn)實中寫的 patch 要簡單很多。那篇文章并沒有給出一個滿意的答案，但是現(xiàn)在原因就顯而易見了——因為 GenProg 把錯誤的代碼都刪了呀！另一篇 ICSE 2014 上的文章指出 GenProg 往往更擅長于處理和內(nèi)存錯誤（如 Segmentation Fault和Buffer overrun）。這也解釋的通了——因為只要把出問題的內(nèi)存操作刪光就可以了，嗯！一篇paper指出根據(jù)讓人類程序員去比較人類和 GenProg 生成的 patch，發(fā)現(xiàn) GenProg 產(chǎn)生的 patch 往往更容易維護——是的，因為實驗里假設了 patch 的正確性，并且考慮到 GenProg 產(chǎn)生的補丁都等價于把問題代碼都刪光。嗯，維護性的確上升了，畢竟我們解決不了 bug，但是可以解決提出 bug 的代碼！在一些相關領域的研究中，大家當時在 related works 中都是這么介紹 GenProg的：We selected GenProg for the reason that it is almost the only state-of-the-art automated repair tool having the ability of fixing real-word, large-scale C faulty programs.

……

當然了，這篇文章的目的顯然不是讓大家以后每次 debug 的時候把代碼都刪掉，而是思考哪里出了問題（順便一提，GenProg 還拿了去年的十年最有影響力論文獎）。 所以，GenProg弄錯了什么呢？首先它弄錯了一個假設，那就是測試正確性=正確性。事實上，現(xiàn)實軟件中的測試往往都是非常貧弱的，并不能夠代表真正的正確性。如果 GenProg 的作者們能夠擁有一個判斷程序正確性的神諭機（Oracle），那么他們就會早早的發(fā)現(xiàn) GenProg 幾乎不能產(chǎn)生任何正確的補丁了。

現(xiàn)實中我們顯然不能擁有這樣一個神諭機，那我們要做些什么才能避免出這樣的烏龍呢？這更是值得大家思考的一個問題。給我上這門課的教授指出了以下幾點：

注重可解釋性：跑出一段很好的實驗數(shù)據(jù)并不能說明什么，更重要的是為什么，是哪一原因使得 GenProg 擁有那么強大的程序修復能力。由于 codebase 過于龐大，再加上產(chǎn)生的 patch 是出于 AST 形態(tài)下的，GenProg 的原作者們并沒有仔細研究 GenProg 產(chǎn)生的 patch 是什么樣的，以及它們?yōu)槭裁茨軌蛐迯?bug，只是報告了實驗中產(chǎn)生的結果。注重熔斷實驗（abduction study）：如果我們讀原 paper 就會發(fā)現(xiàn)，在原 paper 的 evaluation 中，作者甚至沒有提供一個基準算法 （baseline），而僅僅是 report 了 GenProg 修復代碼的能力。事實上，在 ICSE 2011 上一篇影響深遠的文章 A Practical Guide for Using Statistical Tests to Assess Randomized Algorithms in Software Engineering 就指出，GenProg 并沒有提供一個基準（如隨機搜索）來衡量他們的表現(xiàn)。事實上，他們發(fā)現(xiàn)，大部分 patch 往往都只在進行了 400 次進化就得到了（population size = 40, evolvution = 10）。這說明實際上搜索的空間非常小，那么一個隨機搜索是不是表現(xiàn)的甚至可以更好呢？做更多更高質(zhì)量的實驗：計算機科學是科學，而科學就是一個實驗-歸納的過程。所以做更加廣泛和更加科學的實驗可以使人們更加接近正確的結論。在這里，也幸好原作者當初慷慨的公布了他們用于測試的數(shù)據(jù)集才使得其他研究者可以快速地發(fā)現(xiàn)他們的謬誤（這算不算給自己挖坑呢233）。

總結的說，這一個大烏龍的影響是很深遠的，它說明了科學研究中很多的謬誤都有可能出現(xiàn)在計算機科學中。對于一些應用層面的研究，我們只有引入了科學的研究方法，以及對于可解釋性的注重，才能夠去盡量的避免類似的錯誤的產(chǎn)生。不過話說回來，在這樣一個連接主義的人工智能盛行的年代，可解釋性似乎已經(jīng)被扔進了歷史的垃圾桶里，這在某種層面上來說也許就是一種悲哀。

以上就是【天??！這居然是！不要告訴別人（8-8÷8=多少）8+3×5=多少-所以，你想用 $8 的價格修一個bug嗎？】的全部內(nèi)容。