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

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

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

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

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

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

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

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

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

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

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

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

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

早先一篇文章指出并且考慮了如下的問題：為什么 GenProg 往往生成的 patch 往往比人類程序員現(xiàn)實(shí)中寫的 patch 要簡單很多。那篇文章并沒有給出一個滿意的答案，但是現(xiàn)在原因就顯而易見了——因?yàn)?GenProg 把錯誤的代碼都刪了呀！另一篇 ICSE 2014 上的文章指出 GenProg 往往更擅長于處理和內(nèi)存錯誤（如 Segmentation Fault和Buffer overrun）。這也解釋的通了——因?yàn)橹灰殉鰡栴}的內(nèi)存操作刪光就可以了，嗯！一篇paper指出根據(jù)讓人類程序員去比較人類和 GenProg 生成的 patch，發(fā)現(xiàn) GenProg 產(chǎn)生的 patch 往往更容易維護(hù)——是的，因?yàn)閷?shí)驗(yàn)里假設(shè)了 patch 的正確性，并且考慮到 GenProg 產(chǎn)生的補(bǔ)丁都等價于把問題代碼都刪光。嗯，維護(hù)性的確上升了，畢竟我們解決不了 bug，但是可以解決提出 bug 的代碼！在一些相關(guān)領(lǐng)域的研究中，大家當(dāng)時在 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.

……

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

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

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

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

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