轉載自微軟研究院 AI 頭條
論文編譯：黃小天
今年 2 月，微軟研究院與劍橋大學宣布合作開發了一種名為DeepCoder 的新算法，可以根據問題的輸入輸出自動編寫解題程序。但事實上，DeepCoder 的實現是基於一種原創的、極其精簡的語言，還不能獨立處理較為複雜的問題，目前業界使用的編程語言對於它來說還難以掌握。所以廣大程序員們完全不用擔心會被機器取代！
那麼除此以外程序員們最擔心的是什麼呢？大概就是調 Bug 了吧~ 鑑於機器已經可以完成簡單的編程任務，我們當然希望能利用它更好地輔助程序員的工作。
為此，北京大學、微軟亞洲研究院和電子科技大學的研究人員聯合開發了一種新技術 ACS (Accurate Condition Synthesis)。該技術可以全自動修復軟件系統中的缺陷，無需用戶干預。
比如，下面這段代碼來源於 Apache Math 庫，用於求兩個數的最小公倍數。該段代碼採用了絕對值函數 Math.abs 來保證返回的值是一個正數。但由於實現上的缺陷，在某些輸入的時候會返回負數。
int lcm=Math.abs(mulAndCheck(a/gdc(a,b), b));
return lcm;
這個缺陷的根源是因為負數的數值範圍比正數多一個，所以當傳給 Math.abs 的值是 Integer.MIN_VALUE 時，Math.abs 並不能將輸入轉換成正數，進而導致函數產生負數的輸出。一個正確的實現應該在這個時候返回 ArithmeticException()。
現在假設有一個測試來捕獲這個錯誤，該測試的輸入為 a=Integer.MIN_VALUE 和 b=1，期望的輸出為 ArithmeticException。很顯然，這個測試將在該程序上運行失敗，因為並沒有異常被拋出。
但當我們將這個程序和相應的測試提供給 ACS 時，ACS 將會自動生成如下補丁，準確的修復了該缺陷：
int lcm=Math.abs(mulAndCheck(a/gdc(a,b), b));
+ if (lcm == Integer.MIN_VALUE) {
+ throw new ArithmeticException();
+ }
return lcm;
事實上，缺陷修復技術由來已久。自 2009 年的 GenProg 技術以來，學術界已經提出了數十種不同類別的缺陷修復方法。但傳統的缺陷修復技術一直面臨一個問題——缺陷修復正確率非常低。這是因為傳統缺陷修復系統以通過測試為目標，但實際軟件系統中，測試往往數量有限，通過測試並不意味著程序就是正確的。
比如上面這個例子，現有系統可能生成如下補丁：
int lcm=Math.abs(mulAndCheck(a/gdc(a,b), b));
+ if (b == 1) {
+ throw new ArithmeticException();
+ }
return lcm;
甚至如下補丁：
int lcm=Math.abs(mulAndCheck(a/gdc(a,b), b));
- return lcm;
+ throw new ArithmeticException();
這些補丁都能通過測試，但卻與正確程序差別甚遠。其實，在這個例子中，我們可以很容易地找到能夠通過測試的上百個不正確的修復，這將導致修復技術的正確率變得非常低。
根據 2015 年初美國麻省理工學院的 Martin Rinard 教授在其 ISSTA 論文中的發現，主流缺陷修復技術在真實缺陷上的正確率不超過 10%。雖然後來出現了一些改進的技術，如麻省理工學院的 Prophet 和新加坡國立大學的 Angelix，但這些技術的正確率也都沒有超過 40%。這就意味著，這些技術所產生的補丁中，大多數是錯誤的。而這樣的技術基本沒有辦法在實踐中使用。
而 ACS 技術的正確率和之前的技術相比有了顯著提升。在缺陷修復的基準數據集 Defects4J 上的測試結果中，ACS 生成了 23 個補丁，其中 18 個是正確的，修復正確率接近 80%，顯著超越了現有技術。而在正確率大幅提升的同時，ACS 在該數據集上正確修復的缺陷數量也是同類方法中最多的。目前 ACS 的修復正確率和修復數量都取得了該數據集上的最好結果。
ACS 主要是利用了多源信息，特別是互聯網上廣泛存在的代碼大數據信息來聯合保證修復的正確性。相比已有技術，ACS 綜合使用了三種新的信息：
首先，ACS 發現代碼中的變量使用在數據依賴關係上呈現明顯的局部性特徵，並利用依賴信息對補丁中的變量使用進行排序。
其次，ACS 採用自然語言技術分析代碼中的 Javadoc，再利用 Javadoc 中的信息對錯誤補丁進行過濾。
最後，也是最重要的，ACS 對互聯網上廣泛存在的開源代碼進行統計，發現變量和應用在變量上的操作之間的關聯信息，從而生成正確的補丁。
在上面的例子中，ACS 先利用代碼中的數據依賴確定lcm 是應該使用在if 判斷中的變量，同時根據互聯網上變量和操作之間的關聯確定應該進行==Integer.MIN_VALUE 的判斷，最後再根據測試的預期結果生成if 語句體中的throw 語句，從而生成整個完整的補丁。
ACS 系統的相關論文「Precise Condition Synthesis for Program Repair」已發表在 ICSE 2017 上。論文作者包括北京大學熊英飛研究員、北京大學碩士研究生王杰、電子科技大學本科生嚴潤發、北京大學本科生章嘉晨、微軟亞洲研究院主管研究員韓石、北京大學黃罡教授和張路教授。在投稿 ICSE 2017 後不久，熊英飛研究員就作為中國大陸唯一代表應邀參加了 2017 程序缺陷修復 Dagstuhl 國際研討會，就該論文內容進行了特邀報告，並受到了與會者的一致肯定。
從左至右：微軟亞洲研究院主管研究員韓石，微軟亞洲研究院學術合作經理孫麗君和北京大學熊英飛研究員
三年來，熊英飛研究員和微軟亞洲研究院一直保持著密切的科研合作。不僅與微軟亞洲研究院副院長張冬梅和主管研究員韓石一起承擔了微軟亞洲研究院的合作項目「Enhancing Source Code Mining with Semantics」，並在ICSE 發表了論文，還與張冬梅博士負責的軟件分析組成員合作進行了編譯器測試的研究，且已經在ICSE、ICST 等會議上發表了多篇論文。此外，雙方還聯合在北京大學開設了《軟件分析》課程以培養更多相關優秀人才，等等。
論文：Precise Condition Synthesis for Program Repair
地址： https://www.microsoft.com/en-us/research/wp-content/uploads/2017/02/1608.07754.pdf
摘要：由於修復缺陷很困難，很多研究努力貢獻在了自動缺陷修復上。對於一個未通過測試案例的帶有 bug 的程序，典型的自動修復技術是修改程序以通過所有測試。然而，由於實際項目中的測試程序組通常不充分，通過測試程序組的目標導向經常會導致不正確的補丁。這個問題被稱為弱測試組（weak test suites）或者過擬合。
在本論文中，我們旨在生產精確的補丁，即我們生產的所有補丁有一個較高的正確概率。更具體地說，我們致力於條件合成（condition synthesis），結果表明它比現有方法能夠修復的缺陷多一半。我們的核心見解有三個方面：第一，知道本地語境中的什麼變量用於「if」條件中很重要，我們基於變量之間的依賴關係提出了一種排序方法；第二，我們觀察到API 文檔可用於指導修復進程，並且提出文檔分析技術以進一步過濾變量；第三，知道在變量集上執行什麼謂語很重要，我們建議在現有項目的類似環境中挖掘一組經常使用的謂詞。
基於以上見解，我們開發了一個全新的程序修復系統——ACS，它可在故障位置產生精確的條件。鑑於非常精確的生成條件，我們執行了一個之前被認為是過度擬合的修復操作：直接返回測試 oracle 來修復缺陷。通過這一方法，我們成功修復了 Defects4J 的 4 個項目中的 18 個缺陷，這是目前為止數據集中報告的最大數量的完全自動修復的缺陷。更重要的是，我們方法的評估的精度達 78.3%，明顯高出通常只有低於 40% 精度的先前方法。