Skyfire: 一種數據驅動的種子生成工具

文/楊鑫

程序深層次的漏洞一般隱藏在程序執行階段，而對于自動化的模糊測試（Fuzzing）來說很難觸發該類漏洞。論文“Skyfire:Data-Driven Seed Generation for 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。

背景介紹

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

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

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

圖1 處理高度結構化輸入的步驟

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

方法概述

第一步，生成正確的種子：能夠通過程序的語法和語義檢測；

第二步，生成多樣性種子：能夠多樣化地覆蓋語法和語義規則；

第三步，生成不常見種子：能夠生成一般Fuzzer生成不了的種子。

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

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

輸出：覆蓋良好的種子。

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

1.PCSG學習

圖2 Skyfire總體架構

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

圖3 CFG的定義

圖4 XSL語言的上下文無關文法部分內容

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

圖5 一個XSL示例文件及其抽象語法樹

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

圖6 CSG的定義

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

圖7 從CFG、CSG到PCSG的演進

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

一是自動從樣本解析出AST；

二是計算每種parent-children對（即產生式規則）在相應上下文下的次數；

三是計算在一種上下文下的每種產生式規則的概率，等于在上下文c下這個產生式規則“α→β1β2…βn”的次數除以所有樹中“α”的次數，公式如下：

q([c]α → β1β2…βn) = count([c]α → β1β2…βn)/count(α)

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

2.種子生成

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

第一步，初始種子生成

初始種子是根據學習出的PCGS，利用左推導方法生成種子輸入產生的，算法也很清晰易懂，如圖10所示。首先設置語法的起始符號t0，然后從t中獲取最左邊的非終結符l和上下文信息c，再從Rl中隨機選取產生式規則r，再在t中對l進行r推導替換，重復這個過程直到沒有剩余的非終端符號。這里使用了四個啟發式規則來生成分布良好的樣本，用不同顏色在算法中標示了出來。第一條紅色代表優先選取低概率的產生規則，這樣可以生成網上爬取的樣本很難覆蓋的功能；第二條紫色是限制相同一產生規則的使用次數，優先應用頻率低的規則；第三條藍色是優先使用低復雜度的產生規則；第四條綠色是限制所有規則的應用次數。

圖9 XSL語言學習的產生規則的一部分

第二步，種子選取

圖10 從PCSG中產生初始種子的算法

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

第三步，種子變異

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

實驗

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

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

總結

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

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

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