[分享總結 - Summary] Skyfire: Data-Driven Seed Generation for Fuzzing

本文是3月15日NISL論文分享活動的回顧，方便感興趣的讀者以及錯過直播的讀者了解分享內容。

本文作者為 楊鑫。版權歸原作者所有，未經授權請勿轉載，謝謝！

This is the summary of NISL Paper Reading Seminar on Mar 15, for interested readers or those missing our live broadcast.

This summary is written by Xin Yang. All rights reserved. Authorization is required for re-post.

摘要

對於輸入格式是高度結構化文件的程序來說，其處理流程一般是：語法解析–語義檢查–程序執行。程序深層次的漏洞一般隱藏在程序執行階段，而對於自動化的模糊測試（Fuzzing）來說很難觸發該類漏洞。

該論文提出了一種數據驅動的種子生成方法，叫做Skyfire。Skyfire通過從大量的已知樣本中學習而生成覆蓋良好的種子作為Fuzzing的輸入對處理高度結構化輸入的程序進行測試。Skyfire接收輸入樣本集合和文法，通過自動化學習PCSG（Probabilistic context-sensitive grammar，一種帶概率的上下文有關文法，包含語義規則和語法特徵），並利用其生成種子文件。

本文利用收集的樣本和Skyfire生成的種子作為AFL的seed對開源的XSLT、XML等引擎進行測試，證明skyfire生成的種子文件分布（提高了20%行覆蓋率和15的函數覆蓋率）和發現漏洞能力。同時也對閉源的IE11的JavaScript引擎測試。其發現了19個新的內存破壞型bug（其中16個新的漏洞）和32個拒絕服務bug。

1 背景介紹

Fuzzing是一種自動化的隨機測試技術，其通過變異或者生成的方法生成大量的測試樣本，並利用生成的測試樣本對目標程序進行測試和監控，以發現程序異常和缺陷。

模糊測試的輸入種子文件的質量是對測試效果的重要影響因素。如圖1所示，基於變異的方法是通過隨機或者啟發式的方法對合法的輸入種子文件進行變異生成測試用例，大部分的生成用例在早期的語法檢查階段就被拒絕而導致程序退出。然而，基於生成的方法是利用格式描述或文法描述來生成測試用例，可以快速的通過語法檢查階段，但是大部分程序在語義檢查階段也難以通過，這都限制了這些方法難以挖掘程序的深層次漏洞。一個高效的Fuzzer需要實現大部分的生成樣本可以到達處理執行階段（execution stage）。

基於生成的方法能夠實現對語法規則的描述和生成，但是想要通過語義規則的檢查卻是非常困難的。一方面，對於不同的程序有不同的語義規則，編寫的生成規則難以復用；另一方面，這樣的手動描述方法是非常耗時費力的，而且有時候甚至是難以實現的。

本文使用一種擴展的上下文敏感的文法（包含語義信息和概率信息）來生成測試用例，並將其作為Fuzzer的輸入進行測試。Skyfire面向的目標程序是接收高度結構化輸入的程序，目的是生成覆蓋良好的測試用例。

2 方法概述

2.1 生成目標

1. 生成正確的種子：能夠通過程序的語法和語義檢測；
2. 生成多樣性種子：能夠多樣化地覆蓋語法和語義規則；
3. 生成不常見種子：能夠生成一般Fuzzer生成不了的種子。

2.2 處理過程

Skyfire通過學習PCSG，可以生成覆蓋良好的種子，供後續fuzzing，總體架構如圖2所示。

輸入：爬取的樣本集合+程序的語法規則（github上ANTLR社區開源）

輸出：覆蓋良好的種子。

包含以下主要步驟：

1. PCSG學習：根據輸入自動化抽取帶概率的上下文有關文法規則；
2. 種子生成：

初始種子生成：根據抽取的規則採用左推導方法進行初始種子生成；

種子選取：採用覆蓋率作為衡量標準進行樣本去重選取；

種子變異：利用隨機替換原則對同種類型的葉子節點進行變異；

下面詳細介紹這些主要步驟。

2.2.1 PCSG學習

這裡是Skyfire的很重要的一點，為了更好理解這個過程，先介紹下CFG（Context-free grammar，上下文無關文法）、CSG（Context-sensitive grammar，上下文有關文法）。CFG的定義如圖3，它是一個四元組，由一組有限的α→β1β2...βn形式的產生式規則組成。其中α∈N是有限的非終端符號集，βi屬於一組有限的非終端符號和終端符號的並集。這套文法可以用來表示一個語言的語法規則。圖4是XSL語言的上下文無關文法部分內容。

根據上下文無關文法，可以將一個XSL文件解析為抽象語法樹，圖5就是一個XSL文件及其抽象語法樹。上下文無關文法能很好地表達語法信息，但因為上下文無關，不能表達上下文相關的語義信息。

因此，可以用上下文有關文法來加入語義信息。圖6是作者定義的一種上下文有關文法，給產生式中增加了上下文信息。上下文包含四項信息，順序依次為α的曾祖父母類型、祖父母類型、父類類型、第一兄弟姐妹的值或第一兄弟姐妹的類型（如果值為空的話）。

為了生成分布良好的種子，作者還將概率附加到每個產生規則的上下文中，來定義在一個上下文下，每種產生式規則的概率。這樣，就有了本文的核心和一大創新點：帶概率的上下文有關文法PCSG，可以將CFG、CSG和PCSG結合起來看，如圖7所示。

PCSG的學習過程分為以下幾步：

1. 自動從樣本解析出AST；
2. 計算每種parent-children對（即產生式規則）在相應上下文下的次數；
3. 計算在一種上下文下的每種產生式規則的概率，等於在上下文c下這個產生式規則「α→β1β2...βn」的次數除以所有樹中「α」的次數，公式如下：

例如圖8所示，綠色的節點5和節點14是父子對，對應的是上下文<null, document, prolog, <?xml>下的產生規則attribute -> Version=「1.0」，它對應的上下文為曾祖父為空，祖父母為文檔，父為PROLOG，第一個兄弟為<?xml。圖9是XSL語言學習的產生規則的一部分，在上下文<NULL、NULL、NULL、NULL>下只有兩個產生規則的左邊是document，這與document是XSL語言的開始符號這一事實是一致的。

2.2.2 種子生成

整個種子生成過程可以分為三步：初始種子生成、種子選擇、種子變異。

（1）初始種子生成

初始種子是根據學習出的PCGS，利用左推導方法生成種子輸入產生的，演算法也很清晰易懂，如圖10所示。首先設置語法的起始符號t0，然後從t中獲取最左邊的非終結符l和上下文信息c，再從Rl中隨機選取產生式規則r，再在t中對l進行r推導替換，重複這個過程直到沒有剩餘的非終端符號。

這裡使用了四個啟發式規則來生成分布良好的樣本，我用不同顏色在演算法中標示了出來。第一條紅色代表優先選取低概率的產生規則，這樣可以生成網上爬取的樣本很難覆蓋的功能；第二條是限制相同一產生規則的使用次數，優先應用頻率低的規則；第三條是優先使用低複雜度的產生規則；第四條是限制所有規則的應用次數。

（2）種子選取

上面的步驟可以生成很多的初始種子，但並不是所有種子都是唯一和重要的，作者以覆蓋率作為標準進行種子去冗餘篩選，對於開源程序使用gcov獲取代碼和函數覆蓋率，對於閉源程序使用PIN獲取基本塊覆蓋率。

（3）種子變異

上面的步驟可以產生語法結構多樣的種子，為了進一步確保語義的多樣性，SkyFire會對生成的種子進行Big-Step變異。這種Big-step的變異可以產生一般Fuzzer的small-step變異難以生成的種子。方法是從AST中選取葉子節點，並利用同種類型的葉子節點對其進行隨機替換，只用右邊是終結符的推導規則。

3 實驗

實驗利用爬取的種子文件對libxslt、libxml2、Sabotron進行測試，測試能夠有效發現漏洞，並且漏洞持續發現能力比直接用爬取的種子文件進行測試效果更好。

此外，測試的覆蓋率等得到明顯的提升效果。目前該方法對JavaScript語言的測試效果不是特別理想，需要進一步的改進。

4 總結

本文實現的數據驅動的種子生成方法利用文法和樣本自動抽取語義信息，並利用語義信息和語法規則進行種子生成，能夠保證生成種子文件通過語法解析和語義檢查，能夠執行到目標程序的更深的路徑，從而更有效的發現深層次的漏洞。

Skyfire目前對於XML、XSL語言的應用效果很好，能夠保證漏洞發現能力和覆蓋率，但是對於JS這種較為複雜的語言應用不夠理想。

5 未來工作

作者將繼續應用和擴展這種種子生成方法，以便更好地支持更多不同的語言，如javascript、SQL、C和Java。除了查找安全漏洞之外，作者還希望使用生成的種子輸入來查找編譯器錯誤。

致謝和參考

在研讀本文的學習過程中，主要參考了原文[1]和兩位作者（Junjie Wang和Bihuan Chen）提供的PPT資料，以及一篇博客[2]，這篇論文總結也是主要融合兩者的內容進行整理的，在此感謝你們的無私分享，同時也感謝請教和交流過的老師和同學們，謝謝你們。

1. J. Wang, B. Chen, L. Wei and Y. Liu. Skyfire: Data-Driven Seed Generation for Fuzzing, IEEE S & P 2017.

2. G1-2討論班Blog. 2017. Skyfire-Data-Driven Seed Generation for Fuzzing. https://taolunban.github.io/2017-06-21-Skyfire-%20Data-Driven%20Seed%20Generation%20for%20Fuzzing