摘要

程式碼倉庫中提供了數百萬個具有大量漏洞修復的開源專案。 可以利用軟體開發歷史的激增來學習如何修復常見的程式漏洞。 為了探索這種潛力，我們進行了一項實證研究，以評估使用神經機器翻譯技術學習針對實際缺陷的漏洞修復補丁的可行性。 我們從GitHub倉庫的更改歷史記錄中挖掘了數百萬個漏洞修復程式，以提取此類漏洞修復程式的有意義的示例。 然後，我們將錯誤程式碼和相應的修復程式碼抽象化，並使用它們來訓練能夠將錯誤程式碼轉換為其修復版本的Encoder-Decoder模型。 我們的模型能夠修復數百種獨特的未被發現的漏洞。總體而言，此模型能夠預測9％的情況下開發人員生成的修復補丁。

1. 簡介

對於軟體開發人員來說，本地化和修復錯誤是一項費時費力的任務。為了支援程式設計師進行這項活動，研究人員提出了許多旨在自動修復程式的方法。所提出的技術或者使用生成並驗證方法，該方法包括生成許多修復（例如遺傳程式設計），或者生成單個修復的方法。儘管自動程式修復技術仍面臨許多實際應用中的挑戰，但現有工作已在特定情況下取得了長足的進步。在適當的情況下，這些方法在很大程度上有助於降低開發人員的漏洞修復成本。

自動化修復方法的兩個主要問題是產生可供程式設計師接受的補丁，以及使補丁過度適合測試用例，尤其是對於生成和驗證技術而言。為了解決這些問題，可以利用現有專案的歷史記錄（就漏洞修復補丁而言），並將自動生成的補丁與現有補丁進行比較。與從專案歷史中挖掘到的補丁類似的補丁被認為更相關。從過去的修復中識別補丁的另一種方法是透過執行測試用例定位了可能的錯誤程式碼之後，使用機率模型從正確的程式碼生成補丁。

我們的工作是出於以下三個考慮。首先，自動修復方法基於相對有限且手工製作（花費大量精力和專業知識）的一組轉換或修復模式。其次，可以成功地利用現有專案的歷史記錄來了解什麼是“有意義的”程式修復補丁。第三，最近的幾項工作證明了先進的機器學習技術（如深度學習）可以從中學習的能力。大型軟體工程（SE）資料集，可以在許多SE任務中使用的最新模型的一些示例包括：程式碼補全，缺陷預測，錯誤定位，克隆檢測，程式碼搜尋，學習API序列或推薦方法名稱。

像GitHub這樣的平臺提供了大量的變更歷史記錄和來自大量軟體專案的漏洞修復承諾。基於機器學習的方法可以利用這些資料來了解原始漏洞修復活動。在這項工作中，我們評估了基於神經機器翻譯（NMT）的方法是否適合為錯誤程式碼自動生成補丁的任務。

自動從原始漏洞修復中學習可以模擬開發人員編寫的真實補丁。此外，我們利用NMT的功能將錯誤程式碼“翻譯”為修復程式碼，從而模擬在開發人員編寫的補丁程式中執行的AST操作的組合。進一步的好處包括在識別候選補丁時NMT的靜態特性，因為與某些生成和驗證方法不同，我們不需要在補丁生成期間執行測試用例。

我們首先從GitHub挖掘大量（約787k）漏洞修復提交。 從這些提交中，我們使用細粒度的原始碼差異提取方法級別的AST編輯操作。 我們在每個漏洞修復提交中確定多個方法級別的差異，並獨立地考慮每個錯誤提交，從而產生約230萬個漏洞修復對（BFP）。 之後，將BFP的程式碼抽象化，使其更適合NMT模型。 最後，使用編碼器/解碼器模型來了解錯誤程式碼如何轉換為修復程式碼。 一旦訓練了模型，就可以使用它為看不見的程式碼生成補丁。

我們根據經驗調查了NMT生成與開發人員實施的候選補丁相同的候選補丁的潛力。 結果表明，在有錯誤程式碼的情況下，經過訓練的NMT模型能夠成功預測修復程式碼（在9％的情況下）。

2. 方法

圖1展示了我們實驗的NMT方法的概述。黑框表示主要階段，箭頭表示資料流，虛線箭頭表示對外部工具或資料的依賴性。我們使用GitHub Archive（第2.1節）從數千個GitHub倉庫中挖掘漏洞修復提交。從漏洞修復程式中，我們提取了方法級的錯誤程式對和名為漏洞修復程式對（BFP）的相應修復程式碼（第2.2.1節）。 BFP是我們用來學習如何從漏洞修復中修復程式碼的示例（錯誤→修復）。我們使用GumTree 來確定在錯誤程式碼和修復程式碼之間執行的編輯操作（A）的列表。然後，我們使用Java Lexer和Parser將BFP的原始碼（第2.2.2節）抽象為更適合學習的表示形式。在抽象過程中，我們將表示形式中經常使用的識別符號和文字稱為成語。該階段的輸出是抽象的BFP及其對應的對映M，從而可以重構原始原始碼。接下來，我們過濾掉長方法（第2.2.3節），然後使用獲得的集合訓練一個編碼器解碼器模型，該模型能夠學習如何將原始程式碼轉換為相應的修復版本（第2.3節）。經過訓練的模型可用於為看不見的錯誤程式碼生成補丁。

圖1 基於NMT的方法的實驗過程概覽

2.1漏洞修復挖掘

我們從GitHub倉庫下載了2011年3月至2017年10月之間的每個公共GitHub事件，並且我們使用Google BigQuery API來識別所有包含包含模式的訊息的提交：（“ fix”或“ solve”）和（ “錯誤”或“問題”或“問題”或“錯誤”）。我們確定了約1000萬（10,056,052）個漏洞修復提交。由於提交訊息和問題跟蹤程式的內容可能無法準確地識別出漏洞修復的提交，因此兩位作者獨立分析了統計上具有意義的樣本（95％的置信度±5％的置信區間，總大小為384），以確認所提交的內容是否正確。實際上是漏洞修復。在解決了13個不一致的案例之後，他們得出的結論是，所確定的bug修復提交中有97.6％是真實的。有關此評估的詳細資訊，請參見我們的線上附錄。

對於每個漏洞修復提交，我們使用GitHub Compare API [9]提取了漏洞修復前後的原始碼。這使我們可以收集有缺陷的（提交前）和修復後的（提交後）程式碼。我們將丟棄與非Java檔案以及在漏洞修復提交中建立的檔案相關的提交，因為不會有任何錯誤版本可供學習。此外，由於我們的目標是學習不會在整個系統中傳播的有針對性的漏洞修復程式，因此我們丟棄了影響五個以上Java檔案的提交。此過程的結果是787,178個漏洞修復提交的錯誤和修復程式碼。

2.2漏洞修復對分析

BFP（漏洞修復對）是一對（mb，mf），其中mb代表錯誤程式碼元件，而mf代表相應的修復程式碼。我們將使用這些BFP來訓練NMT模型，使其學習原始（mb）到修復（mf）程式碼的轉換，從而能夠生成補丁。

2.2.1**提取。給定（fb，ff）來自漏洞修復bf的一對錯誤和修復檔案，我們使用GumTree Spoon AST Diff工具計算fb和ff之間的AST差異。這樣可以計算在AST級別執行的編輯操作的順序，從而可以將fb的AST轉換為ff的AST。

由於檔案級別的粒度可能太大而無法學習轉換模式，因此我們將程式碼分為方法級別的片段，這些片段將構成我們的BFP。選擇方法級BFP的基本原理有幾個原因。首先，方法代表修復活動的合理目標，因為它們可能實現單個任務或功能。其次，方法為學習修復提供了足夠有意義的上下文，例如方法中使用的變數、引數和方法呼叫。最近的經驗研究證明了這種選擇是合理的，該研究表明，大多數修復補丁是如何由單行，單攪動或最壞情況下的攪動由單行分開組成的。較小的程式碼片段缺少必要的上下文，因此無法考慮。最後，考慮到大小和上下文的可變性，考慮任意長的程式碼片段（例如diff中的塊）會使學習變得更加困難。

我們首先依靠GumTree建立fb和ff節點之間的對映。然後，我們提取對映的方法對列表L = {(m_1b, m_1f), ..., (m_nb, m_nf)}。每對（m_ib，m_if）包含方法m_ib（來自原始檔案fb）和對應的方法m_if（來自修覆文件ff）。接下來，對於每對對映方法，我們使用GumTree演算法提取一系列編輯動作。然後，我們僅考慮那些至少具有一個編輯動作的方法對（即，我們忽略在修復過程中未修改的方法）。因此，此階段的輸出是BFP的列表= {bfp_1，...，bfp_k}，其中每個BFP是三元組bfp = {mb，mf，A}，其中mb是原始方法，mf是相應的修復方法，而A是在mf中轉換mb的編輯動作序列。我們無法排除在修復過程中建立/刪除的方法，因為我們無法從中學習修復操作。總體而言，我們提取了約230萬個BFP。

應當注意，我們用於提取BFP的過程：（i）不捕獲方法外部執行的更改（例如，類簽名，屬性等），並且（ii）將每個BFP視為獨立的漏洞修復程式，這意味著在同一個漏洞修復活動中修改的多種方法，應相互獨立考慮。

2.2.2**抽象。透過在原始原始碼級別上工作，學習漏洞修復模式非常具有挑戰性。這尤其是由於約200萬個採礦專案的識別符號和文字中使用了大量的詞彙表。如此龐大的詞彙量會阻礙我們學習將程式碼轉換作為神經機器翻譯任務的目標。因此，我們對程式碼進行了抽象，並生成了一個表達性但詞彙量有限的表示形式。我們使用Java詞法分析器和解析器將BFP中的每個錯誤和修復方法表示為令牌（token）流。建立在ANTLR 之上的詞法分析器將原始程式碼標記為令牌流，然後將其饋送到Java解析器中，Java解析器可以辨別每個識別符號的作用（即，它是否代表變數、方法或型別名稱）和文字的型別。

每個BFP都是獨立抽象的。給定一個BFP bfp = {mb，mf，A}，我們首先考慮mb的原始碼。原始碼被饋送到Java詞法分析器，從而產生令牌流。令牌流然後被饋送到Java解析器，該解析器識別流中的識別符號和文字。解析器為令牌化流中的每個識別符號/文字生成並替換一個唯一的ID。如果識別符號或文字在流中多次出現，則將其替換為相同的ID。識別符號/文字及其對應的ID的對映將儲存在對映（M）中。 Java解析器的最終輸出是抽象方法（abstract_b）。然後，我們考慮mf的原始碼。 Java詞法分析器生成令牌流，然後將其饋送到解析器。當抽象mf時，解析器繼續使用對映M。解析器僅為新穎的識別符號/文字生成新的ID（尚未包含在M中），這意味著它們存在於mf中，但不存在於mb中。然後，它將所有識別符號/文字替換為相應的ID，從而生成抽象方法（abstract_f）。現在，抽象的BFP是4元組bfpa = {abstract_b，abstract_f，A，M}，其中M是該特定BFP的ID對映。該過程繼續考慮下一個BFP，生成一個新的對映M。請注意，我們首先分析原始程式碼mb，然後分析BFP的相應修復程式碼mf，因為這是學習過程的方向。

將ID按順序和位置方式分配給識別符號和文字：將為找到的第一個方法名稱分配METHOD_1的ID，同樣，第二個方法名稱將接收METHOD_2的ID。對於所有方法和變數名（VAR_X）以及文字（STRING_X，INT_X，FLOAT_X），此過程繼續進行。

一些識別符號和文字經常出現在程式碼中，以至於出於我們抽象的目的，幾乎可以將它們視為語言的關鍵字。對於經常在迴圈中使用的變數i，j或索引，或者對於經常用於條件語句和返回值的文字（如0、1，-1），就是這種情況。類似地，方法名稱（例如大小或新增）在我們的程式碼庫中會出現幾次，因為它們代表了通用概念。這些識別符號和文字常被稱為“成語”。我們在表示中包括慣用語，而不是用生成的ID替換慣用語，而是在抽象程式碼時保留原始文字。

為了定義成語列表，我們首先隨機取樣了300k BFP，並考慮了所有原始原始碼。然後，我們提取了程式碼中使用的每個識別符號/文字的頻率，丟棄了關鍵字、分隔符和註釋。接下來，我們分析了頻率的分佈，並集中在最常見的0.005％常用詞（分佈的離群值）上。兩位作者手動分析了此列表，並整理了272個慣用語集，其中還包括標準Java型別，例如String、Integer、common Exceptions等。慣用語列表可在聯機附錄中找到。

這種表示提供了足夠的上下文和資訊，可以有效地學習程式碼轉換，同時保持有限的詞彙量（| V | 約為430）。可以使用對映（M）將抽象的程式碼映射回真實的原始碼。

圖2 程式碼抽象示例

為了更好地理解我們的表示，讓我們考慮圖2中的示例，在該示例中，我們看到了與在整數列表中找到最小值有關的漏洞修復。原始方法包含三個錯誤，修復程式碼可以糾正這些錯誤。第一個錯誤位於if條件內，其中的buggy方法檢查列表大小是否大於或等於0。這是有問題的，因為沒有任何值的列表不能有最小值返回。第二個錯誤是在方法呼叫getFirst中，它將返回列表中的第一個元素，該元素可能是最小值，也可能不是最小值。最後，如果原始方法中的if條件失敗，則該方法返回0；否則，該方法返回0。當無法識別最小值時返回0是不正確的，因為它指示列表中的元素之一為0。修復程式碼更改了if條件，以與列表大小1（而不是0）進行比較，使用min方法如果條件失敗，則返回最小值並將返回值更改為null。

使用可行的和修復的錯誤程式碼進行培訓，雖然可以解決問題，而且可行，但存在一些問題。當我們將有問題的程式碼片段提供給Java Parser和Lexer時，我們發現對映存在一些問題。例如，抽象的修復程式碼包含INT_2和METHOD_4，它們不包含在錯誤程式碼或其對映的抽象版本中。由於令牌到程式碼的對映僅依賴於原始方法，因此此示例將需要綜合INT_2和METHOD_4的新值。但是，該方法利用了慣用語，因此仍然可以考慮使用此BFP。當將成語與成語一起使用時，我們可以用標記所代表的值替換標記。現在，當檢視帶有錯誤碼的修復程式碼的摘要程式碼時，在修復程式碼中找不到不在錯誤程式碼中的抽象標記。以前，我們需要綜合INT_2和METHOD_4的值，但是INT_2被替換為習慣用語1，METHOD_4被替換為習慣用語min。透過使用成語，我們能夠保留此BFP，同時保持學習真實的，受開發人員啟發的補丁程式的完整性。

2.2.3**過濾。我們過濾掉以下BFP：（i）包含錯誤或修復程式碼中的詞法或語法錯誤（即，詞法分析器或解析器無法處理它們）； （ii）他們的原始和修復的抽象程式碼（abstract_b，abstract_f）產生相等的字串； （iii）在兒童車和修復車之間進行了100次以上的原子AST操作（| A |> 100）。後一個決定的依據是消除分佈的異常值（分佈的第三個四分位數為14個動作），這可能會阻礙學習過程。此外，我們的目標不是學習如此大的漏洞修復補丁。

接下來，我們根據BFP的大小（以令牌數量衡量）對BFP進行過濾。我們決定不考慮長方法（超過50個令牌），而專注於小型BFP。因此，我們建立資料集BFP_small = {bfp≤50}。

2.2.4識別符號和文字的綜合。 BFP是我們用來使模型學習如何修復原始碼的示例。給定a b f p = {mb，mf，A}，我們首先對其程式碼進行抽象，獲得bfpa = {abstract_b，abstract_f，A，M}。原始程式碼abstract_b用作模型的輸入，該模型被訓練為輸出相應的修復程式碼abstract_f。然後可以使用M將此輸出映射回真實的原始碼。

在實際使用場景中，在部署模型時，我們無權訪問oracle（即修復程式碼，abstract_f），而只能訪問輸入程式碼。然後，可以將該原始碼提取出來並饋送到模型，該模型會生成預測程式碼（抽象）作為輸出。只有當abstractp包含的ID也出現在輸入程式碼中時，它們才能映射回真實值。如果修復程式碼建議引入在輸入程式碼中找不到的方法呼叫METHOD_6，則我們無法自動將METHOD_6對映到實際的方法名稱。對於為輸入程式碼中不存在的識別符號或文字生成的任何新建立的ID，都無法映射回原始碼。

因此，看來抽象過程使我們能夠限制詞匯量並促進訓練過程，但這種抽象過程將我們限制在僅學習修補程式中，該修補程式重新排列了在兒童車方法中已經可用的關鍵字，識別符號和文字。這是我們決定將成語納入程式碼表示形式並將其視為語言關鍵字的主要原因。慣用語有助於保留由於無法合成新的識別符號或文字而將被丟棄的BFP。這允許模型學習如何用一個習語替換一個抽象識別符號/文字或用另一個習語替換一個習語（例如，圖2的底部）。

在這些過濾階段之後，資料集BFP_small由58k（58,350）個漏洞修復程式組成。

2.3學習補丁

2.3.1**資料集準備。給定一組BFP（即BFP_small），我們使用例項來訓練Encoder-Decoder模型。給定一個b f pa = {abstract_b，abstract_f，A，M}，我們僅使用原始和修復的抽象程式碼對（abstract_b，abstract_f）進行學習。在學習過程中，沒有向模型提供有關可能的修復動作（A）的其他資訊。給定的BFP集隨機分為：訓練（80％），驗證（10％）和測試（10％）集。在進行分割槽之前，我們確保刪除所有重複的對（abstract_f，abstract_b），以免影響結果，即訓練和測試集中使用同一對。

2.3.2 NMT**。實驗模型基於NMT 中普遍採用的RNN EncoderDecoder體系結構。該模型由兩個主要元件組成：RNN編碼器，將項x的序列編碼為矢量表示； RNN解碼器，將項x的表示解碼為另一項y序列。該模型學習在以另一個（輸入）項序列為條件的（輸出）序列上的條件分佈：P（y1，..，ym | x1，..，xn），其中n和m可能不同。在我們的情況下，給定輸入序列x = abstract_b =（x1，..，xn）和目標序列y = abstract_f =（y1，..，ym），訓練模型以學習條件分佈：P（abstract_f | abstract_b）= P（y1，..，ym | x1，..，xn），其中xi和yj是抽象的源令牌：Java關鍵字，分隔符，ID和習慣用語。圖1顯示了帶有注意機制[3，4，25]的Encoder-Decoder模型的體系結構。編碼器將序列x =（x1，..，xn）作為輸入，併產生狀態序列h =（h1，..，hn）。我們依賴於雙向RNN編碼器[3]，該編碼器由後向RNN和前向RNN組成，能夠根據過去和將來的輸入建立表示。即，每個狀態hi表示以向前和向後的方式讀取序列時兩個RNN產生的狀態的串聯（圖1中的虛線框）：hi = [→hi; ←hi]。

RNN解碼器在給定h的情況下預測目標序列y =（y1，..，ym）的機率。具體地，基於以下條件來計算每個輸出項yi的機率：（i）解碼器中的迴圈狀態si； （ii）前i-1個項（y1，..，yi-1）； （iii）上下文向量ci。後者構成注意機制。向量ci被計算為h中狀態的加權平均值：ci =Ínt = 1 aitht，其中權重ait允許模型更加關注輸入序列的不同部分。具體而言，權重ait定義了預測目標項yt時應考慮的項xi。透過使用隨機梯度下降使目標項的負對數可能性最小，對整個模型進行端到端訓練（聯合進行編碼器和解碼器）。

2.3.3**超引數搜尋。對於基於BFP_small資料集（即M_small）構建的模型，我們透過測試編碼器-解碼器體系結構的十種配置來執行超引數搜尋。配置測試了RNN單元（LSTM和GRU）的不同組合，編碼器/解碼器的層數（1、2、4）和單位（256、512），以及嵌入大小（256， 512）。使用儲存桶和填充來處理序列的可變長度。我們最多訓練了6萬個模型，並在過度擬合訓練資料之前選擇了模型的檢查點。為了指導最佳配置的選擇，我們使用了在驗證集（而不是測試集）上計算的損失函式，而結果是在測試集上計算的。所有資料均可在我們的線上附錄中獲得。

3實驗設計

這項研究的目的是從經驗上評估NMT是否可以用於學習原始漏洞修復方法。上下文包含一個漏洞修復資料集（第2節），旨在回答以下研究問題。

3.1 RQ：神經機器翻譯是學習如何修復程式碼的可行方法嗎？

我們旨在透過經驗評估NMT是否是一種可行的方法，以學習將程式碼從原始轉換為修復狀態的方法。為此，我們使用資料集BFP_small來訓練和評估NMT模型M_small。精確地，給定一個BFP資料集，我們訓練Encoder-Decoder模型的不同配置，然後在驗證集上選擇效能最佳的配置。然後，我們使用測試集的未知例項評估模型的有效性。

評估執行如下：令M為訓練好的模型，T為BFP的測試集（BFP_small），我們針對每個T中的bfp =（abstract_b，abstract_f）評估模型M。具體來說，我們將原始程式碼abstract_b饋送到模型M，該模型將生成單個潛在的補丁abstract_p。我們說，僅當且僅當abstract_p = abstract_f時，該模型才能為程式碼生成成功的修復程式。我們報告測試集中成功修復的BFP的原始計數和百分比。

4結果

4.1 RQ：神經機器翻譯是學習如何修復程式碼的可行方法嗎？

當執行超引數搜尋時，我們發現在驗證集上獲得最佳結果的配置是具有1層雙向編碼器，2層Attention解碼器（均具有256個單元，嵌入大小為512和LSTM RNN單元。我們將M_small模型訓練了5萬輪。

透過在相應的修復程式碼中“轉換”錯誤程式碼，該模型能夠成功地為5835個案例中的538個（在測試集中的BFP的9.22％）生成一個修復程式。儘管成功修復的數量可能看起來相對較小，但需要注意的是，這些修復是透過對模型的一次猜測而生成的，而不是以前的生成許多潛在補丁的方法。此外，值得注意的是，測試集中的所有BFP都是唯一的，模型在訓練或驗證步驟中從未見過。透過將抽象程式碼中的ID替換為對映M中儲存的實際識別符號和文字值，可以將模型生成的所有補丁對映到具體的原始碼。

5 有效的威脅

構造有效性。為了獲得足夠的培訓資料，我們在GitHub倉庫中挖掘了錯誤修正，而不是使用經過整理的錯誤修正資料集，例如Defects4j或IntroClass，這些資料集有用但規模有限。為了減輕資料集中的不確定性，我們手動分析了提取的提交的樣本，並驗證了它們與漏洞修復有關。

內部有效性。我們模型的效能可能取決於超引數配置。我們將在2.3.3節中解釋如何執行超引數搜尋。

外部有效性。我們沒有將NMT模型與支援自動程式修復的最新技術進行比較，因為我們的主要目標不是提出一種新穎的自動程式修復方法，而是進行大規模的實證研究，以調查NMT是否適合生成補丁。需要採取其他步驟將我們採用的方法轉換為端到端的工作工具，例如補丁的自動實施，執行測試用例以檢查其適用性等。這是我們未來工作議程的一部分。

我們只關注Java程式。但是，學習過程與語言無關，並且可以透過替換詞法分析器，解析器和AST區分工具，針對不同的程式語言例項化整個基礎結構。

我們只關注小型方法。在分析提取的BFP的分佈，平衡可用的訓練資料量和句子長度的可變性之後，我們做出了這個決定。

6 結論

我們對NMT的適用性進行了實證研究，目的是從真正的錯誤修正中學習如何修復程式碼。我們首先設計並詳細說明了一個過程，以挖掘，提取和抽象可用的原始漏洞修復程式的原始碼，以便獲得漏洞修復程式的方法級別示例，我們稱之為BFP。然後，我們建立，訓練和調整NMT模型，以將錯誤程式碼轉換為修復程式碼。我們發現我們的模型能夠修復大量獨特的漏洞修復，佔已使用BFP的9％。

這項研究為其他研究人員可以建立並適當評估基於NMT的程式修復技術奠定了堅實的經驗基礎。