摘要：

隨機程式生成（模糊測試）是發現編譯器中錯誤的有效技術，但是成功的模糊測試器需要針對編譯器支援的每種語言進行大量開發工作，並且常常使部分語言空間未經測試。我們引入了 DeepSmith，這是一種新穎的機器學習方法透過為生成器輸入推斷生成模型來加快編譯器驗證。我們的方法基於大量開放原始碼庫，推論出一個學習型的真實世界程式碼結構模型。然後，它使用該模型自動生成數以萬計的現實程式。最後，我們對它們應用已建立的差異測試方法，以揭示編譯器中的錯誤。我們將我們的方法應用於 OpenCL 程式語言，幾乎無需費力就自動暴露錯誤。在對商業和開源編譯器進行的 1000 小時自動測試中，我們發現了所有編譯器中的錯誤，並提交了 67 個錯誤報告。我們的測試用例平均比現有技術小兩個數量級，生成和評估所需的時間減少了 3.03 倍，並且暴露了現有技術無法解決的錯誤。我們的隨機程式生成器僅包含 500 行程式碼，需要 12 個小時的時間來訓練 OpenCL，而最新技術需要 9 個工時才能從生成器移植到 C 和 50,000 行程式碼。透過 18 行程式碼，我們將程式生成器擴充套件到了第二種語言，在 12 個小時的自動測試中發現了 Solidity 編譯器中的崩潰。

關鍵字：機器學習，差異測試，編譯器模糊測試

1. 背景

編譯器應為有效輸入生成正確的程式碼，為無效輸入生成有意義的錯誤。否則可能會阻礙軟體開發，甚至導致災難性的執行時錯誤。儘管如此，正確測試編譯器還是很困難的。現代的最佳化編譯器是大型而複雜的程式，它們的輸入空間很大。手工設計的測試程式套件雖然很重要，但不足以覆蓋如此大的空間，因此不會觸及到編譯器的所有部分。

隨機測試用例的生成（模糊測試）是一種用於識別編譯器錯誤的完善有效的方法。當進行模糊測試時，隨機生成的有效或半有效輸入將輸入到編譯器。任何型別的意外行為，包括崩潰，宕機或錯誤的二進位制程式碼，都表示編譯器錯誤。儘管很容易檢測到編譯器中的崩潰和宕機，但是如果沒有開發人員提供的針對特定程式行為的驗證或從中建立參考輸出的黃金標準編譯器，通常無法確定二進位制檔案是否已正確編譯。在沒有這些的情況下，可以使用差異測試。生成的程式碼和一組輸入形成一個測試用例，該用例在多個測試平臺上進行編譯和執行。如果測試用例應具有確定性的行為，但測試臺之間的輸出不同，則表明已發現錯誤。

編譯器模糊測試要求有效地生成觸發編譯器錯誤的測試用例。最新技術 CSmith 透過定義和取樣覆蓋 C 程式語言子集的機率語法，生成大型隨機程式。透過此語法，CSmith 確保生成的程式碼輕鬆透過編譯器前端，並強調編譯器最複雜的部分，即中端。複雜的靜態和動態分析可確保程式沒有未定義的行為。然後對程式進行差異測試。

雖然 CSmith 已成功用於識別編譯器中的數百個 bug，但它和類似方法都存在重大缺陷。 它們是一項艱鉅的任務，需要對目標程式語言有透徹的瞭解。CSmith 經過多年的發展，由超過 41k 行手寫 C ++程式碼組成。透過將生成邏輯與目標程式語言緊密結合，必須為每種新的目標語言精心且專業地設計語法的每個功能。例如，將 CSmith 從 C 提升到 OpenCL（表面上簡單的任務）花了 9 個月的時間，並增加了 8k 行程式碼。考慮到定義新語法的困難，通常僅實現該語言的子集。

我們提出的是一種快速，有效且省力的方法來生成用於編譯器模糊測試的隨機程式。 我們的方法論利用深度學習的最新進展來自動構建人類如何編寫程式碼的機率模型，而不是刻苦地為同一目的定義語法。 透過在手寫程式碼的語料庫上訓練深度神經網路，它能夠推斷出程式語言的語法和語義以及常見的構造和模式。 我們的方法實質上將隨機程式的生成框架化為一種語言建模問題。 這大大簡化並加快了過程。 生成的程式的表達能力僅受語料庫中內容的限制，而不受開發人員的專業知識或可用時間的限制。 這樣的語料庫可以很容易地從開源儲存庫中組裝。

在本文中，我們主要針對 OpenCL，OpenCL 是一種用於程式設計異構系統的開放標準，儘管我們的方法在很大程度上與語言無關。 我們選擇 OpenCL 的原因有三點：它是一個新興標準，具有在各種異構硬體上實現功能可移植性的挑戰性前景； OpenCL 是“線上”編譯的，這意味著直到將產品部署給客戶，甚至編譯器崩潰和凍結也可能不會被發現。 並且已經有一個手寫的隨機程式生成器可以與該語言進行比較。 我們提供的初步結果支援 DeepSmith 在多語言編譯器模糊測試方面的潛力。

我們做出以下貢獻：

1.一種新穎，自動且快速的方法，用於生成表達性隨機程式，以進行編譯器模糊測試。我們不是透過專家定義的語法，而是從實際示例中推斷程式語言的語法，結構和用法。我們的系統所需的程式碼比最新技術少兩個數量級，並且培訓時間不到一天。

2 . 我們發現了與最新技術類似的錯誤，但也發現了以前的工作無法解決的錯誤，涵蓋了編譯器的更多元件；

3 .在對真實的手寫程式碼進行建模時，我們的測試用例比其他方法更具解釋性。平均測試用例大小比現有技術小兩個數量級，而無需任何昂貴的縮減過程。

2. 實現方案

DeepSmith1 是我們用於編譯器模糊測試的開源框架。儘管該方法與語言無關，但我們將目標對準 OpenCL。 本部分描述了三個關鍵元件：用於隨機程式的生成模型，測試工具以及用於差異測試的投票啟發法。

2.1 系統架構圖2.2 生成模型

為編譯器生成測試用例很困難，因為它們的輸入是高度結構化的。 要生成具有正確結構的文字，需要專業知識和大量工程工作，而對於每種新語言，都必須從頭開始進行重複。 相反，我們將問題視為無監督的機器學習任務，採用最先進的深度學習技術來構建人類如何編寫程式的模型。 我們的方法受到無監督學習中建模具有挑戰性和高維資料集的突破性結果的啟發。 與現有工具相反，我們的方法不需要目標語言的專業知識，並且僅幾百行程式碼。

手寫程式。生成模型需要在示例程式的種子語料庫上進行訓練。我們透過從 GitHub 上的開源儲存庫中挖掘 10k OpenCL 核心來自動化該主體的組裝。我們使用了一個 oracle 編譯器（LLVM 3.9）來靜態檢查原始檔，丟棄格式不正確的檔案。此步驟的主要目的是消除手動檢查從 GitHub 選擇的每個檔案確實包含 OpenCL 的需要。不利的一面是，不會包括任何引發 LLVM 3.9 前端錯誤的培訓候選人。但是，這並不能阻止我們的系統發現該編譯器中的錯誤。超過一百萬行程式碼的語料庫用作 OpenCL 程式碼的代表性示例，可以從中衍生生成模型。

編碼器。程式程式碼的文字表示形式必須編碼為數字序列，以作為輸入輸入到機器學習模型中。先前的機器學習作品使用字元級編碼，令牌級編碼或固定長度特徵向量。我們擴充套件了的字元/令牌級混合編碼，其中將程式語言的關鍵字和通用名稱視為單獨的令牌，而其餘文字則以字元級為基礎進行編碼。這種方法在壓縮輸入文字和使詞彙表中的令牌數量保持較低之間達到了平衡。

我們還採用了保留語義的轉換來簡化訓練程式。首先，對每個原始檔進行預處理以擴充套件宏並刪除條件編譯和註釋。然後，根據宣告順序，使用任意但一致的模式對所有使用者宣告的識別符號進行重新命名： {a，b，c，。 。 。 ，aa，ab，ac， 。 。}代表變數和{A，B，C，。 。 。 ，AA，AB，AC，。 。 。}的功能。這樣可以確保一致的命名約定，而無需修改程式行為。最後，強制執行統一的程式碼樣式，以確保大括號，括號和空格的一致使用。這些重寫的簡化為模型提供了更多學習語言的結構和更深層次的方面並加快學習速度的機會。另一方面，預處理器或前端中的某些錯誤可能不再被發現。我們認為這是可以接受的折衷方案。對於語料庫可以大很多個數量級的語言（例如 C 或 Java），可以在不進行這些修改的情況下生成模型。

神經網路。我們使用遞迴神經網路的長短期記憶（LSTM）架構對程式程式碼進行建模。在 LSTM 體系結構中，不僅根據當前輸入，而且還按順序瞭解先前的輸入來學習。在我們的案例中，這可以根據給定的先前令牌歷史記錄，對令牌出現在文字中的機率進行建模。與以前的遞迴網路不同，LSTM 採用了具有線性啟用功能的勿忘門，從而使它們避免了梯度消失的問題。這使它們有效地學習了長序列上的複雜關係，這對於建模程式程式碼很重要。我們的 LSTM 網路為編碼的語料庫上的詞彙分佈建模。在使用不同的模型引數進行初步實驗後，我們發現每層 512 個節點的兩層 LSTM 網路在學習分佈的保真度和網路大小之間提供了良好的折衷，這限制了訓練和推理的速度。該網路使用隨機梯度下降法訓練了 50 個時期，初始學習率為 0.002，每個時期衰減 5％。使用單個 NVIDIA Tesla P40 在 OpenCL 語料庫上訓練模型花費了 12 個小時。我們為模型提供的程式語言結構或語法沒有先驗知識。

程式生成。對經過訓練的網路進行取樣以生成 新程式。該模型以核心的開頭（在 OpenCL 中使用關鍵字 kernel void 標識）為種子，並逐個令牌取樣。“括號深度”計數器分別在生成或令牌時遞增或遞減，以便可以檢測核心的末端並停止取樣。 然後將生成的令牌序列解碼迴文本，並用於編譯器測試。

2.3 測試工具

OpenCL 是一種嵌入式計算核心語言，需要主機程式碼才能在主機和裝置之間編譯，執行和傳輸資料。 出於編譯器模糊測試的目的，這需要測試工具來執行生成的 OpenCL 程式。 首先，我們使用 CLSmith 的測試工具。 該工具假定一個沒有輸入的核心和一個 ulong 緩衝區作為寫入結果的單個引數。 只有 0.2％的 GitHub 核心共享此結構。 我們希望有一種更靈活的工具，以便測試範圍更廣的程式，能夠支援多引數核心並生成用作輸入的資料。

我們開發了一種工具，該工具首先從函式原型中確定期望的引數，然後為它們生成主機資料。目前，我們支援所有 OpenCL 基本型別和向量型別的標量和陣列。對於跨 n 個執行緒的核心執行，將為指標引數分配大小為 n 的緩衝區，併為其填充 value [1。 。 。 n];標量輸入的值為 n，因為我們觀察到大多數核心都使用標量輸入來指定緩衝區大小。從中建立生成模型的訓練程式是真實程式，因此不共享引數型別限制。因此，該模型可能會生成我們的驅動程式無法為其建立示例輸入的正確程式。在這種情況下，將使用“僅編譯”存根，該存根僅編譯核心，而不會生成輸入資料或執行已編譯的核心。與生成模型不同，此測試工具是特定於語言的，其設計源於領域知識。儘管如此，它還是一個相對簡單的過程，由幾百行 Python 組成。

2.4 差異測試的投票啟發法

我們採用已建立的差異測試方法來暴露編譯器缺陷。與以前的工作一樣，對跨編譯器的程式輸出進行投票已被用來規避 oracle 問題並檢測錯誤編譯。 但是，我們將這種方法擴充套件為不僅描述錯誤編譯，而且描述異常的構建失敗和崩潰。

在評估測試用例的結果時，應立即關注構建崩潰（bc）和構建超時（bto）的結果，表明編譯器的行為是錯誤的。對於所有其他結果，都需要進行差異測試以確認異常行為。我們尋找結果佔多數的測試用例，即測試平臺的某些部分表現出相同的結果，但某些測試平臺卻偏離了。我們使用大多數的存在增加了測試用例有“正確”行為的可能性。

如果對於給定的測試用例，大多數測試平臺成功執行，並且測試平臺產生編譯錯誤或執行時崩潰，則會發生異常構建失敗（abf）或異常執行時崩潰（arc）。如果對於給定的測試用例，如果大多數測試平臺成功執行併產生相同的輸出值，則異常錯誤輸出（awo）就會發生，並且測試平臺產生的結果不同於該大多數輸出。錯誤的錯誤輸出結果表明編譯錯誤，這是一種很難檢測到的錯誤類別，在錯誤類別中編譯器會默默地發出錯誤程式碼。 CSmith 是專門針對此類 Bug 設計的。

異常執行時行為的誤報。生成的程式可能包含未定義或不確定的行為，這些行為將被錯誤地標記為異常。 CSmith 透過在生成過程中執行復雜的分析來規避此問題，以最大程度地減少產生具有不確定行為的程式的機會。儘管可以為我們的系統建立類似的分析作為過濾器，但是我們採用了一種更簡單的方法，僅過濾實際上在實踐中觀察到的幾種不確定性行為。 我們使用 GPUverify 和 Oclgrind 過濾資料競爭，越界和未初始化的訪問。一些編譯器警告提供了不確定性行為的強有力指示（例如，指標與整數之間的比較）我們檢查這些警告並進行相應過濾。 OpenCL 中的浮點運算可能不精確，因此程式碼可以在不同的測試平臺上產生不同的輸出。因此，CSmith 和 CLSmith 不支援浮點運算。 DeepSmith 允許浮點運算，但是由於它不能對輸出進行差分測試，因此它可以檢測到除異常錯誤輸出結果以外的所有結果。

3. 實驗評估3.1 實驗建立

OpenCL 系統。我們進行了 10 個 OpenCL 系統的測試。 我們涵蓋了廣泛的硬體：3 個 GPU，4 個 CPU，一個協處理器和一個模擬器。 測試的編譯器中有 7 種是商業產品，其中 3 種是開源的。 我們的系統套件包括同一裝置的不同驅動程式的組合，以及使用同一驅動程式的不同裝置的組合。

測試平臺。對於每個 OpenCL 系統，我們建立兩個測試平臺。首先，在禁用最佳化的情況下執行編譯器。第二，啟用最佳化。然後，每個測試平臺都是一個三元組，由<裝置，驅動程式，is_optimized>設定組成。 該機制提供了 20 個測試平臺進行評估。

測試用例。對於每個生成的程式，我們建立輸入。此外，我們需要選擇要使用的執行緒數，我們生成兩個測試用例，一個使用一個執行緒，另一個使用 2048 個執行緒。然後，一個測試用例是一個三元組，由<program，inputs，threads>設定組成。

我們將模糊測試和 CLSmith 進行比較。 我們允許兩者在 20 個試驗檯上各執行 48 小時。 CLSmith 使用其預設配置。 測試用例的總執行時間包括生成和執行時間。

3.2 實驗結果

我們報告了 10 個 OpenCL 系統的 DeepSmith 測試結果，每個系統運行了 48 小時。我們在所有測試的編譯器中都發現了錯誤-每個編譯器都崩潰了，並且每個編譯器生成的程式崩潰了或無聲地計算出錯誤的結果。迄今為止，我們已經向編譯器供應商提交了 67 個錯誤報告。我們首先對發現的編譯時和執行時缺陷進行定性分析，然後對我們的方法與 OpenCL 編譯器模糊測試的最新技術 CLSmith 進行定量比較。 DeepSmith 能夠識別出廣泛的缺陷，而 CLSmith 卻無法識別其中的許多缺陷，僅需進行少量工程工作即可。最後，我們使用過去兩年中每個 LLVM 版本的編譯器崩潰率作為編譯器健壯性的度量標準，對編譯器健壯性進行了定量分析。我們發現進步很好，編譯器變得越來越強大，但是新功能和迴歸的引入確保了編譯器驗證仍然是一個移動的目標。

4. 結論

我們為編譯器模糊提供了一個新穎的框架。 透過將隨機程式的生成視為無監督的機器學習問題，我們極大地降低了設計隨機程式生成器所需的成本和人力。 堆疊的大部分內容與程式語言無關，只需要大量示例程式，編碼器和測試工具即可定位新語言。

我們針對具有挑戰性的 OpenCL 多核領域展示了我們的方法。 我們的實現 DeepSmith 已發現 OpenCL 實現中的許多錯誤。 我們在編譯器的某些部分中暴露了一些錯誤，這些錯誤是當前方法所沒有的，例如缺少錯誤處理。 我們對方法的可擴充套件性進行了初步探索。 我們的測試用例很小，比最新的測試用例短兩個數量級，並且易於解釋。