Fuzzing技術綜述

摘 要:通過分析比較多種Fuzzing技術的定義，結合其當前發展所基于的知識和采用的方法，給出了Fuzzing技術的一個新的定義;重點從與黑盒測試技術的區別、測試對象、架構和測試數據產生機理四個方面總結了當前Fuzzing技術采用的一些新思想、新方法以及它們的缺陷。針對這些缺陷和實際應用中的需求，分別提出了當前Fuzzing技術下一步的具體研究方向和對應的研究方法。

關鍵詞:Fuzzing技術; 黑盒測試; 架構; 測試數據; 生成; 變異; 動態測試; 知識

中圖分類號:TP391 文獻標志碼:A

文章編號:1001-3695(2010)03-0829-04

doi:10.3969/j.issn.1001-3695.2010.03.006

Survey on Fuzzing

WU Zhi-yong， WANG Hong-chuan， SUN Le-chang， PAN Zu-lie， LIU Jing-ju

(Dept. of Network Engineering， Electronic Engineering Institute of PLA， Hefei 230037， China)

Abstract:By analyzing and comparing several definitions of Fuzzing， this paper gave a new definition accroding to the know-ledge and methods using currently， summerized its new ideas， new methods and corresponding defeats from these aspects like differences from black-box testing， framework and test data generation mechanism. Based on these defeats and the requiments from practical application， proposed concrete research directions and methods.

Key words:Fuzzing; black-box testing; construction; test data; generation; mutation; dynamic test; knowledge

Fuzzing技術源于軟件測試中的黑盒測試技術，它的基本思想是把一組隨機數據作為程序的輸入，并監視程序運行過程中的任何異常，通過記錄導致異常的輸入數據進一步定位軟件中缺陷的位置。1990年Miller等人[1]發現，通過簡單的Fuz-zing可以使運行于UNIX系統上的多于25%的程序崩潰;2002年Aitel[2，3]通過自己設計實現的Fuzzing工具SPIKE成功地發現了多個未知漏洞;2008年Godefroid等人[4，5]利用Fuzzing工具SAGE發現大型Windows應用程序中二十多個未知漏洞。關于Fuzzing的定義，人們從不同的角度進行了描述。Miller等人[1，6]認為Fuzzing(或Fuzz testing)是軟件測試中的隨機測試技術;Sutton等人[7]認為Fuzzing的重要組成部分是暴力測試;Andrea等人[8]認為Fuzzing是一種簡單的黑盒測試技術;Oehlert[9]認為Fuzzing是黑盒測試技術中的邊界測試技術，Vuagnoux[10]認為Fuzzing是黑盒測試、錯誤注入、壓力測試的技術融合。總體來說，傳統的Fuzzing是指一種非常簡單的黑盒測試技術或者隨機測試技術[1，6，7，11]，用來發現軟件的缺陷(flaws)。筆者認為Fuzzing是把隨機測試和邊界測試技術、協議和軟件知識、具體執行和試探性攻擊結合在一起的技術方法。

Fuzzing作為一項發現軟件錯誤的測試技術具備如下優點:其測試目標是二進制可執行代碼，比基于源代碼的白盒測試方法適用范圍更廣泛;Fuzzing是動態實際執行的，不存在靜態分析技術[12，13]中存在的大量的誤報問題;Fuzzing原理簡單，沒有大量的理論推導和公式計算，不存在符號執行技術[5，8，14~22]中的路徑狀態爆炸問題;Fuzzing自動化程度高，無須在逆向工程過程中大量的人工參與。因此，Fuzzing技術是一種有效且代價低的方法，在許多領域受到歡迎，許多公司和組織用其來提高軟件質量[23~25]，漏洞分析者使用它發現和報告漏洞[26]，黑客使用它發現并秘密利用漏洞。國內對Fuzzing技術有了初步的研究[27]和簡單的應用[28~31]。

1 早期Fuzzing技術

早期的Fuzzing技術僅是一種簡單的隨機測試技術[1，6]，但卻有效地發現了許多程序中的錯誤。文獻[6]中設計的Fuzzing工具包括一個隨機字符串產生器，產生包含可打印字符和控制字符的字符串;一些腳本用來加強測試過程的自動化，并記錄程序崩潰的現場以協助追蹤錯誤原因和地址。早期的程序中出現的錯誤也比較簡單，如代碼中因沒有對輸入的字符串的長度進行檢查，而導致棧溢出。

由于早期的Fuzzing技術操作起來簡單，與其測試目標程序的關聯性小，它的優點包括:a)可用性，不需要獲得目標程序的源代碼就可以測試;b)復用性，如測試FTP(file transfer protocol)的Fuzzing程序可以用來測試任何FTP服務器;c)簡單性，無須過多了解目標程序。然而，Fuzzing技術不可避免地帶有隨機測試產生大量冗余測試輸入、覆蓋率低導致發現軟件缺陷概率低的缺點[32]，同時帶有黑盒測試的低智能性的缺點，即黑盒測試只測試了程序的初始狀態，而很多程序尤其是網絡協議程序的很多錯誤是隱藏在程序的后序狀態中的。

2 Fuzzing技術的研究現狀

2.1 與黑盒測試技術的區別

經過近二十年的發展，源于黑盒測試技術的Fuzzing技術顯示出與前者的不同，主要表現在:a)測試需求的著眼點不同。Fuzzing測試著眼于發現軟件安全性相關的錯誤，黑盒測試著眼于測試軟件的功能的正確性。b)測試用例的側重點不同。由于測試需求的不同，Fuzzing的測試用例大多數都是畸形的測試用例，黑盒測試的用例的大多數都是正確的測試用例。Fuzzing為了提高測試用例的有效性，則必須提高測試用例的正確性，從而使測試用例的畸形數據能夠達到程序的潛在不安全點。c)由于測試用例的產生機理不同，Fuzzing為了產生有效的畸形數據，需要考慮到測試用例的數據格式、目標程序的結構流程和程序運行的中間狀態;而黑盒測試只關心目標程序的外部接口和外部輸入，從這個意義上講，現在的Fuzzing技術更接近于灰盒測試。

2.2 Fuzzing的測試對象

在Fuzzing技術的有效性進一步得到驗證之后，出現了許多針對特定類型應用程序或者協議的Fuzzing工具，如針對瀏覽器的mangleme、針對文件應用程序的FileFuzzing和SPIKEfile、針對ActiveX的COMRaider和AxMan，尤其突出的是2002年出現的針對網絡協議的SPIKE[2，3]。后來，進一步出現了針對性更強、功能也更為單一的Fuzzing工具，如針對IRC協議的ircfuzz[33]，針對DHCP協議的dhcpfuzz[34]和針對FTP的tftpfuzz[34]工具等。當前的Fuzz工具主要是針對文件格式應用程序和網絡協議應用程序，但也出現了可以測試瀏覽器[7]、操作系統內核[35]、Web應用程序[36]的Fuzz工具。另外，引入了agent思想的工具Peach[35]可以對分布式系統進行Fuzz測試。

2.3 Fuzzing的架構

最為簡單的Fuzzing架構如圖 1所示，包含引擎和監視兩個模塊。引擎模塊的功能是產生Fuzzing需要的數據并把數據發送到目標程序使之運行;監視模塊的功能是監視目標程序的運行狀態是否出錯。早期Fuzzing[1，6]的實現就是采用了該模型，監視模塊功能的實現借助于簡單的腳本來記錄程序出錯的信息。

隨著Fuzzing技術的進一步發展，出現了如圖 2所示的架構設計。為了避免產生大量無效[9]的測試數據，新架構中出現了參數腳本和樣本文件。參數腳本給出了引擎生成的測試用例中的數據的格式、長度等與數據之間的一些關系，如SPIKE、Sulley[37]使用的類C格式的腳本，Peach[38]使用的XML格式的腳本。樣本文件是許多基于變異技術(mutation-based)的數據生成方式的Fuzzing工具用來變異測試數據的基準。基于樣本文件產生的測試數據可以大大提高測試用例的有效性，可以提高測試的代碼覆蓋率，可以減輕測試用例構造的復雜度。Fuzzing測試文件格式應用程序依據的樣本文件是其相應格式(如DOC、PDF等)的樣本文件(如Peach)，Fuzzing測試網絡協議應用程序的樣本文件是通過嗅探工具(如Ethereal[39]或WireShark[40])的數據包轉換的樣本文件(如Peach、Sulley、AutoDafe[41]、SPIKE Proxy[36]等)。

在圖 2所示的架構中，Fuzzing引擎的模塊劃分粒度更為細化，其目的是加強代碼的可復用性和整個Fuzzing構架的靈活性，以方便用戶根據需求快速制定適合其他多種協議的Fuzzing程序。

Fuzzing的監視模塊發生了很大的變化，轉換為功能更為豐富的代理(agent)模塊(如工具Peach、Sulley)，一方面可以并行Fuzzing的過程以提高Fuzzing的效率，一方面可以使引擎和代理分離開來在不同的機子上運行，可以對分布式應用程序進行Fuzzing測試。a)許多代理都包括程序監控子模塊，用來監視和控制程序的運行情況。由于開發調試器的工作量大，大多數工具使用的是第三方的調試工具，如Peach，有的工具使用的是可以定制特殊需求的調試器，如Sulley、AutoDafe。b)代理中還添加了日志模塊，主要用來記錄發生異常的現場，以協助用戶進一步定位應用程序發生錯誤的位置，還要記錄使之發生異常的測試用例或者程序輸入，以使該錯誤可以恢復。另外，極少數工具如Sulley添加了分析模塊，用來統計Fuzzing測試的結果信息，如代碼覆蓋率等。

2.4 Fuzzing測試數據的產生機理

早期的Fuzzing技術就是隨機測試技術，測試數據多數是隨機產生的畸形數據。為了提高Fuzzing產生數據的有效性，出現了下面兩種產生測試數據的思想:

a)基于格式分析和程序理解相結合的數據產生方法，其代表工具有SPIKE、Peach、Sulley、AutoDafe等。通過對文件和協議的理解，該方法產生的數據可以有效地越過應用程序中對固定字段、校驗和、長度的檢查，從而使Fuzzing的測試數據的有效性大大加強。該方法又可以分為基于生成技術的方法(generation-based)和基于變異技術的方法(mutation-based)[42]或兩者相結合(如工具Peach)的方法。基于生成技術的測試數據產生方法通常是給出文件格式或者網絡協議具體的描述規則，然后依據此規則產生測試數據。該方法需要用戶對格式或者協議有非常深的了解，并需要大量的人工參與[10]。基于變異技術的數據產生方式通常是在對格式或者協議有所了解的前提下，對獲得的樣本數據中的某些域進行變化，從而產生新的變異數據。該方法對初始值有著很強的依賴性，不同的初始值會帶來差異很大的代碼覆蓋率，從而會產生差異很大的Fuzzing效果[42]。還有一種完全自動化的基于變異技術的數據產生方式，如工具AutoDafe和SPIKE Proxy，該方法利用協議的自動分析技術[7，36，41]實施對測試數據的自動生成。但由于協議自動分析技術的準確率還有待進一步提高，其Fuzzing測試效果并不理想。總之，基于格式分析和程序理解相結合的數據產生方法的優點是執行效率比較高、應用范圍廣、通用性強，缺點是仍然需要大量的人工參與來進行多種知識(如協議知識、數據格式知識、應用程序知識)的獲取并實現這些知識到測試用例的轉換。

b)基于靜態分析與動態測試相結合的數據產生方法。通過與靜態分析技術、符號執行技術、具體執行技術等多種技術[4，5，8]相結合，從而在達到一個較高的代碼覆蓋率的測試基礎上進行Fuzzing測試。本質上來說，這種方法是白盒測試與Fuzzing測試技術的融合。該方法通過借助軟件測試中的技術使Fuzzing技術得到一個不錯的代碼覆蓋率，該方法的缺點是仍然無法克服符號執行中的狀態爆炸問題，也無法完全自動解決部分程序自帶的高強度的程序檢查(如校驗和和加密數據)問題;另外，該方法采用了類似于窮搜索的思路，每次執行需要大量的時間，效率低;而且每次執行都需要復雜的符號運算，從而消耗了大量的時間。

3 Fuzzing技術的研究方向

Fuzzing技術以其簡單有效的優點得到了越來越多的關注，結合上述技術的不足和實際應用中的需求，其研究方向可以歸納為以下幾個方面:

a)Fuzzing測試平臺的通用性研究。由于Fuzzing的測試對象越來越廣泛，如何構建通用的、可擴展性強的通用平臺對于提高Fuzzing技術的整體發展十分必要。通用的測試平臺應該具備下面幾個功能:具備數據格式的解釋功能從而產生適合多種數據格式的有效的畸形測試數據;具備獨立的、可定制的數據產生變異功能，可以產生多種類型的、針對性強的畸形數據;具備可操作的跟蹤調試功能以反饋運行時的多種信息;具備高效的引擎以協調多個模塊之間的自動化運行。

b)知識獲取的自動化程度的提高。實際的Fuzzing測試過程顯示絕大部分的時間都花費在輸入數據格式、程序狀態轉換的人工分析上;提高測試數據或通信協議的自動化分析或半自動化分析水平可以有效提高Fuzzing的測試效率。

c)多維的Fuzzing測試用例生成技術研究。當前的Fuzzing測試用例生成技術都是一維的，即每次只變化一個輸入元素，而許多漏洞是由多個輸入元素共同作用引起的。多維測試用例生成技術的研究可以有效擴展Fuzzing發現的漏洞范圍，但是多維Fuzzing測試用例會帶來類似于組合測試中的狀態爆炸問題，現有的組合測試理論成果對于解決Fuzzing多維測試中的狀態爆炸問題有一定的借鑒意義。

d)智能的測試用例生成技術研究。利用漏洞知識給出合適的導向，結合智能算法像遺傳算法[10]、模擬退火算法可以有效避免Fuzzing隨機性強、漏洞漏報率高的缺點。

e)Fuzzing測試的程序多狀態的自動覆蓋技術研究。可以解決需要人工參與才能覆蓋程序的多個狀態問題，從而提高整體Fuzzing測試的效率。

f)Fuzzing測試效果的評估技術研究。以黑盒測試中的代碼覆蓋率來評價Fuzzing的測試效果是不直接、不科學的;從覆蓋不安全代碼的覆蓋率、程序狀態的覆蓋率、輸入邊界測試的充分性、緩沖區邊界覆蓋的充分性、測試數據的有效性和知識獲取的充分性等多個角度來衡量Fuzzing的測試效果會更加科學，也會更好地指導Fuzzing測試用例的生成和Fuzzing技術的進一步發展。

參考文獻:

[1]MILLER B P， FREDRIKSON L， SO B. An empirical study of the reliablity of UNIX utilities[J]. Communications of the ACM， 1990，33(2):32.

[2]AITEL D. The advantages of block-based protocol analysis for security testing[R].New York: Immunity Inc， 2002.

[3]SPIKE[EB/OL].(2009-06). http://www.immunitysec.com/resources-freesoftware.shtml.

[4]GODEFROID P， LEVIN M， MOLNAR D. Active property checking[C]//Proc of the 8th ACM International Conference on Embedeling Software. 2008:19-24.

[5]GODEFROID P， LEVIN M， MOLNAR D. Automated whitebox fuzz testing[C]//Proc of Network Distributed Security Symposium. 2008.

[6]MILLER B P， KOSKI D， LEE C P，et al. Fuzzing revisted: a reexamination of the reliability of UNIX utilities and services[R].Madison: University of Wisconsin Madison， 1995.

[7]SUTTON M， GREENE A， AMINI P. Fuzzing: brute vulnerability discovery[M].[S.l.]: Pearson Education Inc， 2007: 16.

[8]ANDREA L， LORENZO M， MATTIA M，et al. A smart fuzzer for x86 executables[C]//Proc of the 3rd International Workshop on Software Engineering for Secure Systems.[S.l.]: IEEE Computer Society， 2007:7.

[9]OEHLERT P. Violating assumption with fuzzing[J]. IEEE Security and Privacy，2005，3(2):58-62.

[10]VUAGNOUX M. Autodafe: an act of software torture[EB/OL]. (2006). http://autodafe.sourceforge.net/docs/autodafe.pdf.

[11]FORRESTER J E， MILLER B P. An empirical study of the robustness of windows NT applications using random testing[C]//Proc of the 4th USENIX Windows System Symposium. 2000:6.

[12]LAROCHELLE D， EVANS D. Statically detecting likely buffer overflow vulnerabilities[C]//Proc of the 10th on USENIX Security Symposium. Berkeley: USENIX Association， 2001.

[13]DOR N， RODEH M， SAGIV M. CSSV: towards a realistic tool for statically detecting all buffer overflows in C[J]. ACM SIGPLAN Notices， 2003，38:155-167.

[14]BUSH W R， PINCUS J D， SIELAFF D J. A static analyzer for fin-ding dynamic programming errors[J]. Software-Practice Experience， 2000，30(7):775-802.

[15]XIE Yi-chen， CHOU A， ENGLER D. ARCHER: using symbolic， path-sensitive analysis to detect memory access errors[C]//Proc of the 9th European Software Engineering Conference Held Jointly with 11th ACM SIGSOFT International Symposium on Foundations of Software Engineering.New York: ACM Press， 2003:327-336.

[16]GODEFROID P， KLARLUND N， SEN K. DART: directed automated random testing[J]. ACM Sigplan Notices， 2005，40(6):213-223.

[17]CADAR C， GANESH V， PAWLOWSKI P M，et al. EXE: automatically generating inputs of death[J]. ACM Trans on Inf System Secur， 2008，22:1-38.

[18]CRISTIAN C， VIJAY G， PETER M P， et al. EXE: automatically generating inputs of death[C]//Proc of the 13th ACM Conference on Computer and Communications Security.New York: ACM Press， 2006:322-335.

[19]YANG Jun-feng， SAR C， TWOHEY P，et al. Automatically generation malicious disks using symbolic execution[C]//Proc of IEEE Symposium on Security and Privacy.[S.l.]: IEEE Computer Society， 2006.

[20]GODEFROID P. Compositional dynamic test generation[C]//Proc of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.New York: ACM Press， 2007:47-54.

[21]CADAR C， DUMBAR D， ENGLER D. Klee:unassisted and automatic generation of high-coverage tests for complex systems programs[C]//Proc of the 8th USENIX Symposium on Operating System Design and Implementation. 2008.

[22]ANAND S， GODEFROID P， TILLMANN N. Demand-driven compositional symbolic execution，MSR-TR-2008-138[R].[S.l.]:Microsoft Research， 2007:367-381.

[23]HOWARD M. Inside the windows security push[J].IEEE Security Privacy， 2003，1(1):57-61.

[24]LIPNER S， HOWARD M. The trustworthy computing security development lifecycle[EB/OL].(2005).http://msdn.microsoft.com/security/default.aspx?pull=/library/en-us/dnsecure/html/sdl.asp.

[25]MAXWELL S A. The bulletproof penguin， secure linux through fuzzing[EB/OL]. (2001). http://home.pacbell.net/s-max/scott/bulletproof-penguin.html.

[26]GRIMES R. The buzz about fuzzers[EB/OL].(2005). http://www.infoworld.com/article/05/09/09/37OPsecadvise_1.html.

[27]邵林，張小松，蘇恩標. 一種基于Fuzzing技術的漏洞發掘新思路[J]. 計算機應用研究，2009，26(3):1086-1088.

[28]吳毓書，周安民，吳少華，等. 基于Fuzzing的ActiveX控件漏洞發掘技術[J].計算機應用，2008，28(9) :2252-2254.

[29]魏瑜豪，張玉清. 基于Fuzzing的MP3播放軟件漏洞發掘技術[J].計算機工程，2007，33(24):158-160，167.

[30]成厚富，張玉清. 基于Fuzzing的藍牙OBEX漏洞挖掘技術[J].計算機工程，2008，34(19):151-153，156.

[31]高峻，徐志大，李健. 針對符合文檔的Fuzzing測試技術[J].計算機與數字工程，2008，36(12):116-119.

[32]OFFUTT A J， HAYES J H. A semantic model of program faults[C]//Porc ofACM SIGSOFT International Symposium on Software Testing and Analysis. San Diego: ACM Press， 1996.

[33]Ircfuzz[EB/OL].(2009-06).http://www.digitaldwarf.be/products/ircfuzz.c.

[34]Dhcpfuzz[EB/OL].(2009-06).http://www.digitaldwarf.be/products/dhcpfuzz.pl.

[35]Tftpfuzz[EB/OL].(2009-06).http://www.digitaldwarf.be/products/tftpfuzz.py.

[36]SPIKE Proxy[EB/OL].(2009-06). http://www.immunitysec.com/resources-freesoftware.shtml.

[37]Sulley[EB/OL].(2009-06). http://www.fuzzing.org.

[38]Peach[EB/OL].(2009-06). http://www.peachFuzzer.com;http://peachfuzz.sourceforge.net. http://peachfuzz@googlegroups.com.

[39]Ethereal[EB/OL].(2009-06). http://www.ethereal.com.

[40]Wireshark[EB/OL].(2009-06). http://www.wireshark.org.

[41]AutoDafe[EB/OL].(2009-06). http://autodafe.sourceforge.net; http://autodafe.sourceforge.net/docs/autodafe.pdf.

[42]MILLER C， PETERSON Z N J. Analysis of mutation and generation-based fuzzing[EB/OL].(2009-07). http://securityevaluators.com/files/papers/analysisfuzzing.pdf.

[43]LIU Guang-hong， WU Gang， ZHENG Tao，et al. Vulnerability analysis for x86 executables using genetic algorithm and fuzzing[C]//Proc of the 3rd International Conference on Convergence Hybird Information Technology. 2008:491-497.

[44]KAKSONEN R. A functional method for assessing protocol implementation security[D].Oulu，Finland:University of Oulu， 2001.

[45]SUTTON M， GREENE A. The art of file format fuzzing[EB/OL].(2004). http://www.blackhat.com/presentations/bh-Jp-05.bh_jp-05-sutton-greene.pdf.

[46]GPF[EB/OL].(2009-06). http://www.appliedsec.com/resources.html.