SQ-Fuzz : 分支覆蓋率指引之組合模糊測試

SQ-Fuzz : Edge Coverage Guided Combinatorial Fuzz Testing

吳建興(CHIEN-HSING WU)

指導教授 ： 黃世昆

國立交通大學/資訊學院/網路工程研究所/碩士(2020年)

摘要

模糊測試是一項熱門的軟體測試技術，利用此工具已挖掘為數甚多的漏洞，例如著名的American Fuzzy Lop(AFL) 可針對檔案格式進行重複變異測試，不論對於處理影音、圖片的程式都有很優異的成果。現有模糊測試研究通常注重輸入對程式帶來的影響，例如AFL是設定好程式需要運行的所有參數，並不斷變異程式所要處理的文件。所以在模糊測試的過程中，主要變動的是輸入的文件。但這樣的測試並沒有考慮到其他會影響程式執行的因素，這些因素可能導致程式的錯誤，我們因此導入組合測試的概念。然而在組合測試中常會遇到組合過多，並且難以評斷哪一種組合較為重要等問題。我們提出利用模糊測試的覆蓋率指引，來挑選出適當的測試組合，以改善組合測試的效能。所實作出的概念性驗證工具 SQ-Fuzz，相較於 AFL 與AFLfast 等知名模糊測試工具， 在binutils這個項目上平均可以增加4成以上的分支覆蓋率，並挖掘出17個程式錯誤。

關鍵字

模糊測試

並列摘要

Fuzz testing is one of the most popular techniques of software testing. Many security researchers and software testers have found so many bugs with fuzz testing. The main idea of fuzz testing is to repeatedly execute programs, and keep mutating the test inputs. The program is monitored for uncommon behaviors like crashes or memory leak. For different types of programs, there are also many different types of fuzzing tools. For example, American Fuzzy Lop(AFL) is efficient to find bugs in programs for processing images, videos, and documents. Almost all the fuzzers explore only single dimension input space, so we want to combine the concept of combinatorial testing and fuzz testing together. The combinatorial testing suggests that testing combinations of parameters. The problem of combinatorial testing is when there are too many parameters, it’s hard for us to generate test cases, and cannot explore too much input space. Hence, we present SQ-Fuzz, using edge coverage feedback-driven to choose valuable parameter combinations. SQ-Fuzz can efficiently explore multi-dimensional input space, and generate valuable test case. We evaluate SQ-Fuzz on famous open source programs of binutils, and have found 17 new bugs. SQ-Fuzz visits 1.4 times more edge coverage than the state-of-the-art fuzzers of AFL and AFLfast.

並列關鍵字

Fuzzing

參考文獻

[1]M. Zalewski, "American fuzzy lop.(2015)," URL http://lcamtuf. coredump. cx/afl, 2015.

[2]D. Vyukov, "Syzkaller," URL https://github.com/google/syzkaller, 2015.

[3]S.-K. Huang, M.-H. Huang, P.-Y. Huang, C.-W. Lai, H.-L. Lu, and W.-M. Leong, "Crax: Software crash analysis for automatic exploit generation by modeling attacks as symbolic continuations," in 2012 IEEE Sixth International Conference on Software Security and Reliability, 2012: IEEE, pp. 78-87.

[4]V. Chipounov, V. Kuznetsov, and G. Candea, "S2E: A platform for in-vivo multi-path analysis of software systems," ACM Sigplan Notices, vol. 46, no. 3, pp. 265-278, 2011.

[5]L. De Moura and N. Bjørner, "Z3: An efficient SMT solver," in International conference on Tools and Algorithms for the Construction and Analysis of Systems, 2008: Springer, pp. 337-340.