Odena A, Olsson C, Andersen D, et al. Tensorfuzz: Debugging neural networks with coverage-guided fuzzing[C]//International Conference on Machine Learning. PMLR, 2019: 4901-4911.
摘要編譯器是構建軟體最基本的程式設計工具之一。然而，生產編譯器仍然有缺陷。模糊測試通常利用新生成的或變異的輸入來發現新的錯誤或安全漏洞。在本文中，提出了一個基於語法的模糊化工具 DEEPFUZZ。DEEPFUZZ 基於一個生成的序列到序列模型，自動地、連續地生成格式正確的 C 程式。我們使用這套新的 C 程式來模糊現成的 C 編譯器，例如 GCC 和 Clang/LLVM。我們給出了一個詳細的案例研究來分析為模糊測試生成的 C 程式的成功率和覆蓋率的提高。我們用三種抽樣方法和三種生成策略分析了 DEEPFUZZ 的效能。因此，DEEPFUZZ 在路線、功能和分支覆蓋方面提高了測試效率。在我們的初步研究中，我們發現並報告了 GCC 的 8 個 bug，開發人員正在積極解決這些 bug。
介紹我們的工作側重於編譯器測試。透過將覆蓋不同特性的程式輸入到不同的產品編譯器中，開啟不同級別的最佳化，內部編譯器錯誤可能會在編譯期間被觸發，並帶有詳細的錯誤訊息，指示錯誤在哪裡以及是什麼。然而，生成“好的”程式來使測試更加有效，並透過自動化這個過程來構建一個連續的測試框架是具有挑戰性的。現有方法中的每一個測試，包括手工製作的測試，都包含了一些特性，如今常見的是為現代編譯器開發越來越大的測試套件。這提高了測試覆蓋率，但是構建這些測試需要大量的人力。然而，減少人工測試的一個實用方法是模糊測試，或模糊化。
模糊化是一種發現漏洞或安全漏洞的方法。使用自動生成或修改的輸入反覆執行程式，以檢測異常行為，例如程式崩潰。目前使用的主要輸入模糊化技術有黑盒隨機模糊化白盒約束模糊化和語法化模糊化。黑盒和白盒模糊化是全自動的，並且在歷史上已經被證明在二進位制格式檔案解析器中發現安全漏洞是有效的。相比之下，基於語法的模糊化要求輸入語法指定被測應用程式的輸入格式，這通常是手工編寫的。這個過程既費力又耗時，而且容易出錯。然而，基於語法的模糊化是目前已知的最有效的模糊化技術，用於模糊化具有複雜結構輸入格式的應用程式，例如編譯器。在編譯器測試場景中，部署基於語法的模糊化的一種方法是將 C 語法編碼為測試用例生成的規則。但實際上，C11 是 C 語言的當前標準，有 696 頁的詳細規範，這給工程師構建這樣一個基於語法的引擎帶來了障礙。
在本文中，我們考慮了用生成遞迴神經網路為基於語法的模糊化自動生成語法上有效的輸入的問題。更具體地說，我們的目標是訓練一個生成神經網路來學習輸入資料的“語法”，或者更準確地說，語言模式。我們建議利用生產編譯器提供的原始測試套件，在監督學習策略中訓練序列到序列模型。最初，序列到序列模型被廣泛用於機器翻譯和文字生成。從理論上講，透過在原始段落上訓練模型，我們將單詞的正確拼寫、句子的有效句法、寫作行為的詳細風格隱性地編碼到生成模型中。同樣的想法可以應用於程式合成，我們只需要訓練一個模型，在種子資料集的基礎上生成不同的語法有效的程式。對於訓練資料集，我們採用了原始的 GCC 測試套件，其中有超過 10000 個小程式，涵蓋了 C11 標準中指定的大多數功能。在訓練階段，我們調整引數，將 C 程式的語言模式編碼到模型中，在此基礎上，我們不斷生成新的程式用於編譯器模糊化。
貢獻：我們的工作是第一次將生成遞迴神經網路用於基於語法的編譯器模糊化。
首先，建議的框架是全自動的。透過訓練一個序列到序列模型，它可以被看作是訓練資料的語言模式的隱式表示，在我們的上下文中的 C 語法，我們的框架 DEEPFUZZ 將不斷提供新的語法正確的 C 程式。
其次，我們構建了一個實用的工具來模糊化現成的 C 編譯器。我們詳細分析了關鍵因素將如何影響生成模型的準確性和模糊化效能。
第三，我們應用深度模糊技術來測試 GCC 和 CLUNG/LL 虛擬機器。在我們的初步分析中，測試覆蓋率增加了，我們發現並報告了 8 個真實的 bug。
概括序列到序列模型我們在序列到序列模型的基礎上構建了深度模糊，該模型實現了兩個用於字元級序列預測的遞迴神經網路。RNN 是一個由隱藏狀態 h 和可選輸出 y 組成的神經網路。它對可變長度序列進行操作，x = (x1，x2，...，xT)。在每一步中，RNN 的隱藏狀態由以下各項更新。
其中 f 是非線性啟用函式。RNN 可以學習一系列字元的機率分佈來預測下一個符號。因此，在每個時間步長 t，來自 RNN 的輸出是條件分佈 p(XT | XT 1，...x1)。例如，在我們的例子中，在下一個字元的多項式分佈上，我們使用軟最大啟用函式作為輸出.
對於所有可能的符號 j = 1，...，K，其中 wjare 是權重矩陣 w 的行。透過組合這些機率，我們使用學習的分佈，透過在每個時間步迭代地取樣新的字元來生成一個新的序列是簡單的.
序列到序列模型由兩個神經網路組成，一個編碼器和一個解碼器。編碼器學習將可變長度序列編碼成固定長度向量表示，解碼器將把該固定長度向量表示解碼成可變長度序列。當 RNN 的隱藏狀態改變時，編碼器 RNN 讀取輸入序列 x 的每個字元。在讀完這個序列的結尾後，RNN 的隱藏狀態是整個輸入序列的概要。同時，解碼器 RNN 被訓練成透過預測給定隱藏狀態 hhti 的下一個字元 yt 來生成輸出序列。然而，與純 RNN 不同，yt 和 hhti 也受 yt-1 和輸入序列概要 c 的制約。在這種情況下，為了計算解碼器的隱藏狀態，我們有
類似地，下一個字元的條件分佈是
其中 f 和 g 是啟用函式。總體而言，兩個 RNNs 編碼器-解碼器被聯合訓練以生成給定輸入序列的目標序列。
所有 RNN 在迴圈層都有反饋環。這種設計允許他們隨著時間的推移將資訊儲存在“記憶體”中。然而，很難訓練標準的 RNNs 來學習長期的時間依賴性，但這在程式中是常見的。這是因為損失函式的梯度隨時間呈指數衰減。因此，在我們的設計中，我們採用了 RNN 的變體，長短期記憶(LSTM)，特別是在我們的編碼器和解碼器中。LSTM 單位包括一個“儲存單元”,可以將資訊長時間儲存在儲存器中，在這種情況下，可以儲存長曆史資訊。
以前的研究中，序列到序列模型已經被訓練生成語法正確的 PDF 物件來模糊一個 PDF 解析器。這項工作背後的核心思想是，源語言語法可以作為字串對訓練的副產品來學習。在本文中，我們將類似的思想應用於編譯器模糊化。在訓練過程中，我們將序列分成多個固定大小的訓練序列。透過切割序列，我們得到訓練序列 xi = s[id : (i+1)d]，其中 s[k : l]是索引 k 和 l 之間的子序列。每個訓練序列的輸出序列是下一個字元，即 yt = s[(i+1)*d+1]。我們配置這個訓練過程來學習一組訓練序列的生成模型。
工作流程總的來說，我們為兩個主要目標提出了 DEEPFUZZ。首先是從一組語法正確的程式中生成遵循合法語法的新程式。主要挑戰來自長序列處理和語言語法表示。第二個目標是提高編譯器測試效率。我們的目標是提高覆蓋率，並在生產編譯器中捕獲更多內部錯誤。
圖 1 顯示了 DEEPFUZZ 的工作流程。整個工作流程有兩個階段，程式生成和編譯器測試。我們的目標是生產編譯器，如 GCC、GNU 編譯器集合和 LLVM/-Clang。在第一階段，我們使用從最初的人工編譯測試套件中收集的資料來訓練一個生成的序列到序列模型。在我們將序列輸入訓練模型之前，我們對它們進行預處理以避免噪聲。我們將在後面的預處理中詳細介紹預處理步驟。我們要適應的模型是一個通用的順序到順序模型，它有兩層，每層有 512 個隱藏單元。我們將我們的模型配置與實驗裝置中最先進的序列生成研究進行了比較。對於程式生成，我們嘗試不同的生成策略。我們在<生成策略>中詳細介紹了生成策略及其原理。因為我們的目標是模糊生成編譯器，所以我們的目標是生成覆蓋 C 語言大部分特性的程式。因此，我們還採用了取樣變數中詳述的一些取樣方法，以使生成的程式多樣化。
在第二階段，我們將生成的 C 程式反饋給不同最佳化級別的編譯器，並記錄編譯訊息。除了編譯訊息之外，我們記錄執行跟蹤以提供覆蓋資訊。總之，對於這個程式生成任務，我們有三個目標:生成語法有效的程式，提高程式碼覆蓋率，以及檢測新的錯誤。我們針對評估中的三個目標，對三個相關指標(透過率、覆蓋率和缺陷)進行研究。
設計我們建議 DEEPFUZZ 不斷生成語法正確的 C 程式來模糊產品編譯器。如概述中所述，完整的工作流程包含兩個階段，程式生成和編譯器測試。在本節中，我們將介紹更多細節。
預處理在我們設定訓練階段之前，我們將序列分成多個固定大小的訓練序列。每個訓練序列的輸出序列是緊挨著輸入序列的下一個字元。我們配置這個訓練過程來學習所有訓練序列集合上的生成模型。然而，我們注意到級聯序列中有一些噪聲需要很好地處理。在預處理中，我們主要處理三個問題:註釋、空白和宏。
空白：根據 POSIX 標準，空白字元包括公共空格、水平製表符、垂直製表符、回車符、換行符和換行符。為了統一程式風格，我們用一個空格代替了所有的空白字元。
宏：宏是 C 語言程式設計的一個共同特徵。宏是被賦予新名稱的程式碼片段。在我們的實現中，每當使用該名稱時，它總是被宏的內容替換。
取樣變數我們使用學習過的序列到序列模型來生成新的 C 程式。例如，對於字首序列“int”，學習的分佈很有可能預測“main”來跟進。然而，我們的目標是使原始程式多樣化，以產生更多像“int foo = 1；或“int foo = bar(1)；”。因此，我們建議採用一些抽樣方法對學習到的分佈進行抽樣。我們在這裡描述了生成新的 C 程式所採用的三種取樣方法:非樣本、樣本和樣本空間。
非樣本：在這種抽樣方法中，我們直接依靠學習的分佈貪婪地預測給定字首的最佳下一個字元。
樣本：為了克服非樣本方法的侷限性，在給定字首序列的情況下，我們建議對下一個字元進行取樣，而不是選擇最上面的預測字元。
樣本空間：這種取樣方法是樣本和非樣本的結合。在這種方法中，當前綴序列以空格結束時，我們只對所有預測的超過閾值的字元中的下一個字元進行取樣。
生成策略為了不斷模糊生產編譯器，我們使用學習過的模型來生成新的 C 程式語言序列。我們將原始測試套件中的程式視為種子。基於來自原始程式的一個序列作為字首，我們將生成新的程式碼。為了最大限度地利用生成的序列，我們提出了三種生成策略:G1)我們將新生成的基於同一字首序列的程式碼插入到原始格式良好的程式中；G2)我們生成新的程式碼片段，但它們將使用從原始程式的不同位置隨機選取的字首序列生成，然後分別插入回去；G3 我們在原程式的字首序列之後剪切出相同數量的行，並將新生成的新行插入已被剪下的句子的位置。此外，在我們的框架內可以方便地建立更多的生成策略，但我們對這三種策略進行了初步研究。
評估實驗設定為了評估 DEEPFUZZ，我們流水線化了一個原型工作流，該工作流基於一組語法正確的 C 程式來訓練一個序列到序列模型。最初，包含 10000 個格式良好的 C 程式的訓練資料集是從 GCC 測試套件中收集和取樣的。我們訓練了一個 2 層的序列到序列模型，每層有 512 個 LSTM 單元。我們把輟學率定為 0.2。我們已經發布原始碼供公眾傳播。
在以前的一項關於文字生成的研究中，研究人員用超過 100 MB 的訓練資料訓練了一個單層 RNN，在這個單層模型中有 1500 個隱藏單元。學習&模糊模型採用一個生成序列到序列模型來生成新的 PDF 物件，用於 PDF 解析器模糊化，研究人員訓練了一個具有兩層的模型，在每層中有 128 個隱藏單元。他們在包含 534 個格式良好的 PDF 檔案的資料集上訓練了這個模型。在我們的研究中，我們訓練了一個具有兩層的模型，其中在 DEEPFUZZ 框架的每一層中有 512 個 LSTM 單元。訓練資料集包含從生產編譯器測試套件中取樣的 10000 個語法正確的 C 程式，比以前的任何研究都要大。
我們在監督環境中訓練序列到序列模型。為了分析訓練效能，我們訓練了多個由透過次數或時期引數化的模型。曆元被定義為學習演算法的迭代，以遍歷完整的訓練資料集。我們在伺服器上對該模型進行了 50 個時期的訓練。我們在五個不同的時期儲存了模型的快照:10、20、30、40 和 50。訓練一個時期需要 30 分鐘左右，整個訓練週期需要 25 個小時。對於新的程式生成，如設計中所述，我們使用了不同的取樣方法和各種生成策略來生成新的 C 程式。新生成的程式仍然基於原始的訓練資料；換句話說，我們使用原始的 C 程式作為種子，從中隨機選擇字首序列。透過在種子中插入新行或用新行替換行，我們可以得到新的程式。因為新生成的部分會引入新的識別符號、新的分支、新的函式等。這將使新生成程式的控制流程更加複雜，從而提高測試效率。
在我們的研究中，我們使用三個指標來衡量 DEEPFUZZ 的有效性。
透過率是衡量語法有效程式在所有新生成的 C 程式中的比例的指標。序列到序列模型可能會將 C 語言模式編碼到神經網路中。因此，透過率將是一個很好的指標，表明該網路在輸入序列上的訓練效果如何。我們使用 gcc 的命令列來解析一個新生成的程式，如果沒有報告錯誤，它表明這個程式的語法正確。
覆蓋率是測試的具體衡量標準。直覺上，測試覆蓋的程式碼越多，我們就越能保證測試的完整性。我們在分析過程中收集了三種覆蓋資訊:路線覆蓋、功能覆蓋和分支覆蓋。我們使用 gcc 支援的命令列工具 gcov 來收集覆蓋率資訊。
缺陷檢測是測試的目標。對於編譯器測試，透過向不同最佳化級別的編譯器提供更多的程式，預計會觸發崩潰或其他程式碼錯誤等錯誤。作為一種自我保護機制，像 GCC 和 Clang/LLVM 這樣的編譯器定義了一種特殊的錯誤，稱為“內部編譯器錯誤”。這個錯誤表明了編譯器本身在編譯過程中的問題，錯誤訊息將幫助我們找到編譯器中的錯誤。
透過率透過率是生成的語法有效程式與新生成的完整程式的比率。這是一個指標，表明在所提出的序列到序列模型中，C 語言模式編碼得有多好。在我們的評估中，具體來說，我們將分析透過率如何隨著訓練時期的數量、不同的取樣方法和不同的生成策略而變化。
時期：一個時期被定義為學習演算法的迭代，以遍歷完整的訓練資料集。我們對模型進行了總共 50 個時期的訓練，並在不同的時期拍攝了模型的快照:10、20、30、40、50，並將模型應用於新的 C 程式生成。在 G1 的時期策略下，我們嘗試了所有三種取樣方法的程式。
結果:圖 2 顯示了結果。
透過率隨著 10 到 30 個時期的訓練增加而增加。30 代後透過率下降可能是過度擬合的結果。
所有采樣方法的最佳透過率在 30 個時期的訓練中達到。透過率最高為 82.63%。
取樣：在對模型進行訓練後，我們採用了不同的抽樣方法。正如我們所建議的，取樣方法決定了如何根據預測的分佈選擇新的字元，它會影響透過率。因此，我們記錄了基於種子程式在不同取樣方法下新生成的 10000 個程式的透過率:無樣本、樣本和樣本空間。
結果:圖 2 顯示了結果。請注意，本實驗是在 G1 的發電策略下進行的
對於所有的抽樣方法，透過率在訓練的 30 個時期內增加，之後略有下降。
比較所有三種取樣方法的透過率，與其他兩種方法取樣和取樣空間相比，無取樣在每個快照模型上都獲得了更好的透過率。透過率最高為 82.63%。
生成策略:為了生成新的程式，我們引入了三種生成策略:G1)在一個位置插入兩個新行，G2)在不同位置插入兩個新行，G3)替換兩個新行。新生成的行基於種子程式中選擇的字首序列。為了分析透過率如何隨著不同的生成策略而變化，我們記錄了 30 個時期後使用訓練好的模型執行程式生成的結果。此外，我們在這個實驗中沒有使用樣本。
結果:表 1 顯示了結果。
三代戰略的透過率分別為 82.63%、79.86%和 73.23%。透過比較這三種不同生成策略下的透過率，我們得出結論，G1 在無樣本下的透過率表現最好。
就透過率而言，G1 和 G2 的結果相似，高於 G3 的透過率。原因可能是劃掉行會引入不平衡的語句，如未閉合的括號、括號或花括號。
覆蓋率除了透過率之外，如本節開頭所述，因為我們正在進行測試，所以覆蓋率資訊是另一個重要的指標。在這一部分中，我們分析瞭如何透過不同的取樣方法和生成策略來實現覆蓋率的提高。
取樣：為了比較覆蓋率的提高，我們記錄了覆蓋率資訊，包括原始種子測試套件和新生成的測試套件覆蓋了多少行、函式和分支。此外，為了分析抽樣方法如何影響覆蓋率的提高，我們記錄了不同抽樣方法下的覆蓋率提高百分比。
結果:覆蓋率提高的資訊顯示在表 2 中，增加的測試套件包括 10000 個新生成的 C 程式，它們來自 GCC-5 上的 DEEPFUZZ，為了比較這些指標，我們也在圖 3 中給出了它們。
在三種不同的取樣方法中，樣本線上路、功能和分支覆蓋改進方面取得了最佳效能。例如，在生成策略 G2 下，無樣本、樣本和樣本空間的線覆蓋改善分別為 5.41%、7.76%和 7.14%。
不同生成策略的覆蓋率改進模式在不同的抽樣方法中是相似的。G2 永遠是三個中最好的， G1 永遠是最差的。換句話說，抽樣方法的效能與生成策略略有關聯。
生成策略：除了抽樣方法之外，我們還對如何在不同的世代策略下提高這三種不同的覆蓋率感興趣。
結果:圖 3 顯示了使用 G1、G2 和 G3 如何提高覆蓋率。
比較三種不同代策略下的覆蓋範圍改進，G2，即在不同位置插入兩條新線路，在大多數情況下，線上路、功能和分支覆蓋範圍改進方面實現最佳效能。
與抽樣方法相比，代代策略的採用對覆蓋率的提高是一個更有影響的因素。例如，在樣本空間下，三種生成策略的功能覆蓋率改進百分比分別為 0.17%、2.44%和 1.72%。從
G1 改為 G2 後，覆蓋率提高了 42 倍。G2 和 G3 在覆蓋改善方面表現相似，遠高於 G1。
總體來說。為了演示我們的工具在編譯器模糊化上的表現，我們將 DEEPFUZZ 與一個設計良好的實用編譯器測試工具進行了比較。Csmith 是一個可以生成隨機 C 程式的工具。為了進行公平的比較，我們記錄了 Csmith 和 DEEPFUZZ 的覆蓋率改進，它們都用表 3 中生成的 10000 個程式擴充了 GCC 和 LL VM 測試套件。
請注意，在進行此分析時，我們使用樣本作為我們的取樣方法，G2 作為我們的生成策略。我們還在圖 4 中記錄了程式生成過程中的覆蓋率改進。它展示了隨著新測試數量的增加，產品線、功能和分支覆蓋範圍是如何改進的。
結果:
Csmith 將所有病例的覆蓋率提高了不到 1%，而 DEEPFUZZ 將線路、功能和分支的覆蓋率分別提高了 7.14%、2.44%和 3.21%。DEEPFUZZ 實現了比 Csmith 更好的覆蓋率提升。
在 GCC-5 和 CLUNG-3 上，深度模糊的覆蓋改進模式的效能是相似的
新缺陷使用不同的生成策略和取樣方法，基於來自 GCC 測試套件的種子程式，我們可以生成新的程式。因為我們的目標是編譯器模糊化，所以檢測到的缺陷數量是 DEEPFUZZ 功效的一個重要指標。在我們的預賽中學習我們捕獲了 8 個新確認的 GCC 錯誤，我們將詳細說明我們檢測到的兩個錯誤。
GCC Bug 84290:這是我們上報的 Bug。DEEPFUZZ 生成兩個新行(第 5 行和第 6 行)，這觸發了內建函式 atomic load n 的內部編譯器錯誤。觸發該錯誤是因為該函式的第一個引數應該是指標，但它指向一個不完整的型別。此錯誤已修復，新的測試被新增到 GCC 的最新測試套件中。這個檢測到的錯誤顯示了使用語法良好但語義無意義的測試進行編譯器測試的重要性。
1. double f () {2. double r;3. asm ("mov %S1,%S0; mov %R1,%R0" : "=r" (r) : "i" (20));4. asm ("mov %S1,%S0; mov %R1,%R0" : "+r" (r) : "i" (20.));5. ((enum E ∗) 0, 0);6. ;7. return r;8. }GCC Bug 85443:這是我們上報的 Bug。DEEPFUZZ 生成了兩個新行(第 5 行和第 6 行)，這引入了一個新的崩潰。生成的 Atomic 型別的關鍵字，第 6 行的賦值觸發了分段錯誤。這是 GCC-5 上新確認的 bug，在最新版本中已經修復。DEEPFUZZ 檢測到的這個錯誤再次表明了使用語法良好但語義無意義的測試進行編譯器測試的重要性。
1. char acDummy[0xf0] attribute (( BELOW100 ));2. unsigned short B100 attribute (( BELOW100 ));3. unsigned short ∗p = &B100;4. unsigned short wData = 0x1234;5. Atomic int i = 3;6. int a1 = sizeof (i + 1);7. void Do (void) {8. B100 = wData;9. }10. int main (void) {11. ∗p = 0x9876;12. Do ();13. return (∗p == 0x1234) ? 0 : 1;14. }觀察生成的程式，我們注意到許多不良代是由預期表示式引起的。更具體地說，該錯誤訊息表示不平衡括號、括號或花括號等錯誤。我們總結了造成這個問題的兩個主要原因:缺乏培訓和全球資訊的丟失。
由於第一個原因，訓練資料是豐富的，但是在當前的訓練資料集中仍然缺少足夠的重複模式來訓練好的生成模型。在我們未來的工作中，我們可以透過用新的變數或函式名列舉原始測試套件中的所有結構來建立一個更大的訓練資料集。另一方面，由於生成是基於字首序列的，因此會丟失一些超出字首序列範圍的全域性資訊。為了處理這個問題，我們要麼增加訓練序列的長度，以確保捕獲足夠的資訊，要麼我們可以使用一些啟發式方法來幫助模型訓練。前一種方法可能導致生成的程式多樣性降低，後一種方法需要靜態程式分析的幫助。
此外，我們提出的方法是基於字元級序列到序列模型。我們為當前模型提供了一個字元序列，這需要在處理標記級語法方面付出很多努力。這也損害了培訓的可擴充套件性和透過率。在 C 中，關鍵字不到 32 個，內建函式超過 100 個。如果我們在序列-序列模型上執行令牌級序列預測，透過率和可伸縮性都會提高。
結論編譯器測試對於確保計算系統的正確性至關重要。在本文中，我們提出了一個基於語法的自動模糊化工具，稱為 DEEPFUZZ，它學習一個生成遞迴神經網路，不斷生成語法正確的 C 程式來模糊現成的產品編譯器。DEEPFUZZ 生成了 82.63%語法有效的 C 程式，提高了關於行、函式和分支覆蓋的測試效率。