「解放程序員」MIT「創世紀」機器學習新系統，自動生成補丁修復Bug

2017 年 11 月 8 日，在北京國家會議中心舉辦的 AI WORLD 2017 世界人工智慧大會開放售票！早鳥票 5 折 搶票倒計時 7 天開搶。還記得去年一票難求的AI WORLD 2016盛況嗎？今年，我們邀請了冷撲大師」之父 Tuomas 親臨現場，且谷歌、微軟、亞馬遜、BAT、訊飛、京東和華為等企業重量級嘉賓均已確認出席。

長假來了，你放假了，但你辛辛苦苦編程的軟體沒有放假。它還在產生著 bug......

關於程序員大哥發現 bug 以後的心態，我們也略知一二：

別人寫的代碼有 bug——誰寫了這麼個爛代碼，幸虧有哥這樣神一樣的存在才發現，哥真是救世主

自己寫的代碼有bug——

(1)運行很久

<1>別人發現這個程序運行很久了是不是真有bug啊，是不是你弄錯了啊，可以重現么，什麼？可以重現，那問題也不大，要不用戶早投訴了，瞧你那驚慌失措的樣子，至於么？

<2>自己發現這個bug隱藏的很深啊，還好哥犀利犀利，沒有被領導發現，今晚加個菜

(2)新上線程序

<1>別人發現

這個程序剛上線還處於調試階段，有bug很正常，誰的程序沒bug，連操作系統都有bug

<2>自己發現

哥就是犀利，自己開發自己測試，看測試那幫人什麼也不會幹，這麼明顯的bug都測不出來

不管怎麼說，不能讓 bug 把你的長假毀了！讓我們關注一下 MIT 研究團隊的新研究，他們開發了一個稱為「創世紀」的系統，能夠對以前的補丁進行自動學習，生成補丁模板，並對候選補丁進行評估。據研究者說，「創世紀是第一個自動推理補丁生成轉換或根據先前成功的補丁搜索候選補丁空間的系統」，它修復的 bug 幾乎是最好的手編模板系統的兩倍。如果有更多的訓練數據和更強的算力，也許會得到更好的結果，而現在它已經可以讓程序員只花費以前一半的時間來修復 bug 了。

「創世紀」修復的 bug 幾乎是最好的手編模板系統的兩倍

幾乎所有軟體都會有 bug 和安全漏洞，需要時不時的「打補丁」。這些 bug 常常只是一些疏忽引發的。比如說，程序努力在讀取已經刪掉的數據。這些補丁往往也很簡單，比如一行確定數據仍然還存在的代碼。

這種簡單性鼓勵計算機科學家開始探索自動補丁生成的可能性。一些研究團隊，比如MIT 電氣工程與計算機科學教授Martin Rinard 領導的小組，開發了一些模板，這些模板涵蓋了補丁常採用的一般形式。然後，演算法可以使用模板來生成一些候選補丁，並對它們進行評估。

最近，在 ACM 的專題研討會上，Rinard和他的學生Fan Long，以及加州大學聖地亞哥分校的 Peter Amidon 介紹了一個新的系統，該系統能夠通過分析在實際軟體中應用成功的補丁，自己學習構建模板。

手工編碼的補丁生成系統可能有 5 個或 10 個模板，新系統則創建了85 個，這使得它更加多樣化，同時也更精確。這些模板是根據真實補丁的特定類型「訂製」而成，因此不會產生儘可能多的無用備選。在測試中，這個被稱為「創世紀」（Genesis）的新系統修復的錯誤幾乎是最好的手編模板系統的兩倍。

研究報告的第一作者、MIT 電氣工程與計算機科學研究生Long 表示：「你需要進行權衡。一方面，你想產生足夠的備選，好讓這個集里包括有用的補丁。另一方面，你不希望這個集裡面包含太多備選，以致於無法搜索。「

研究者自述：四大貢獻造就第一個自動推理補丁生成轉換系統

論文摘要：

我們提出了一個新的系統，稱為「創世紀」（Genesis），它能夠處理手工編碼的補丁，自動推理代碼轉換，以實現補丁自動生成。我們展示的結果表明了創世紀推理演算法的有效性和完整的創世紀補丁生成系統，它處理了從 372 個Java項目收集的真實補丁和缺陷。據我們所知，創世紀是第一個自動推理補丁生成轉換或根據先前成功的補丁搜索候選補丁空間的系統。

圖1

圖1：創世紀轉換的示例推理和應用。頂部是訓練補丁（初始代碼和補丁代碼），中間是推理轉換（inferred transform），底部是創世記生成的新補丁。

本研究的貢獻主要有以下四點：

• 使用模板AST和生成器進行轉換：我們用模板AST 和發生器，為自由模板變數提出了新的變數。這些轉換使創世紀能夠抽象出補丁和應用程序特定的細節，以捕獲由不同應用程序繪製的多個補丁中存在的常見模式和策略。生成器使創世紀能夠合成所需的新代碼和邏輯，以獲得在大規模實際應用中出現的bug 的正確補丁。

• 補丁泛化：我們提出一種新的補丁泛化演算法，給定一組補丁，自動生成捕獲了補丁中常見補丁生成模式的轉換。該轉換可以生成所有給定的補丁以及在相同或其他應用程序中具有相同模式的其他補丁。

• 搜索空間推理：我們提出了一種新穎的搜索空間推理演算法。從一組訓練補丁開始，該演算法推理出一組轉換，它們一起生成具有良好覆蓋和易處理性的候選補丁的搜索空間。推理演算法包括一個新的採樣演算法，它可以識別訓練補丁中「有前景」的子集來進行泛化，以及針對最終搜索空間選擇問題的基於ILP的解決方案。

• 完整的系統和實驗結果：我們提供了一個完整的補丁生成系統，包括bug 定位和候選補丁評估演算法，它們使用推理搜索空間自動修補大規模現實應用中的缺陷。我們還介紹了這個完整系統的實驗結果。

圖2

圖2：使用整數線性規劃來選擇一組有效的轉換組。

據我們所知，創世紀是第一個自動推理補丁生成轉換或根據先前成功的補丁搜索候選補丁空間的系統。所有實驗數據（包括創世紀源代碼、推理模板和生成的補丁）可從http://groups.csail.mit.edu/pac/patchgen/獲得。

選擇模板：在可以更正的 bug 數量和生成的無用候選補丁數量中做 tradeoff

創世紀訓練的數據集中的每個項目包括兩個代碼塊：原始的、錯誤的代碼和修復它的補丁。創世紀從構建訓練樣本對開始，數據集中的每個項目都與其他項目配對。

接下來，創世紀對每一對進行分析，並創建一個通用的 representation——一個草案模板——這將使它能夠合成兩個原始代碼的補丁。它或許也合成了其他無用的備選。但 representation 必須足夠通用，是備選中成功的補丁。

然後，創世紀會在訓練集中的所有樣本上對每個草案模板進行測試。每個模板僅基於兩個樣本，但它可能適用於其他幾個。對每個模板，都根據兩個標準進行評分：可以更正的錯誤數量和它生成的無用備選數量。例如，生成 10 個備選補丁的模板，其中4 個能夠糾正訓練數據中的錯誤，它就可能會比生成1,000個備選但只有 5 個正確補丁的得分高。

根據這些分數，創世紀選出了500 個最有前景的模板。對於它們中的每一個，它再次用其他樣本中增強初始的兩個訓練樣本集，創造出一個巨大的含有三個樣本的訓練集。對於每一個樣本，它調整其草案模板，以產生更通用的模板。然後執行相同的評估程序，提取 500 個最有前景的模板。

經過四輪這樣的過程，500 個頂級模板中的每一個模板都已經在五個樣本集上進行了訓練。最終的篩選使用了略微不同的評估標準，以確保訓練集中的每個錯誤都可以被糾正。也就是說，在最後的 500 個模板中，可能有一個模板，它的補丁可能只能糾正一個錯誤，在前一輪的評估中得分相對較低。但是，如果它是修補該 bug 的唯一模板，那麼它就是最終勝者。

在研究人員的實驗中，最終的篩選將模板的數量從 500 個減少到85 個。創世紀使用Java 編寫的程序，MIT 的研究者將其性能與最好的手寫Java 補丁生成器進行了對比。創世紀正確修補了 41 個開放源代碼編程項目中的49 個測試用例中的21 個 bug，而舊有的系統則修補了 11 個。

如果有更多的訓練數據和更強的計算能力——以評估更多的候選模板——有可能得到更好的結果。不管怎麼說，一個使得程序員只花費以前一半的時間來修復代碼中錯誤的系統，肯定是有用的。

【掃一掃或點擊閱讀原文搶購五折「早鳥票」】

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！