模糊測試是目前軟體測試方法中最有效的一種。藉由反覆隨機的測試，找尋
程式的弱點或有問題的片段，協助程式開發者發現並修改程式的缺陷。
本論文改良模糊測試工具 American fuzzy lop (AFL) 、融入 Adaptive Random
Sequence 與 Category-Partition-based Distance 方法，修改此二方法以符合 AFL 的
設計方式，精進模糊測試所產生資料的離散程度，藉以提升測試資料對目標程式
的覆蓋率。
目前已對幾個開放原始碼的套件進行測試，確實能提升程式覆蓋率

This thesis proposed a way to improve test case coverage in fuzz testing that
combine Adaptive Random Sequence and Category–Partition-base Distance with
American fuzzy lop (AFL).
Finally, we applied this fuzzer to test several known vulnerabilities open source
applications, and the coverage is improved.

摘要 I
誌謝 III
目錄 IV
圖目錄 VII
表目錄 IX
第一章 緒論 1
1-1 研究動機 1
1-2 研究目標 1
1-3 論文大綱 2
第二章 研究背景 3
2-1 軟體品質測試 3
2-2 黑盒測試 3
2-3 模糊測試 4
2-3-1 變異測試 5
2-3-2 生成測試 6
2-4 AMERICAN FUZZY LOP 8
2-5 ADAPTIVE RANDOM TESTING 13
2-6 ADAPTIVE RANDOM SEQUENCE 15
2-7 CATEGORY-PARTITION-BASED DISTANCE 16
第三章 相關研究 18
第四章 研究方法 21
4-1 AFL系統架構 21
4-2 RANDOM HAVOC 28
4-3 ARS演算法實作 30
4-3-1 Category-Partition-based Distance 之實作 30
4-3-2方法評估 31
4-3-3 預測關鍵字插入方法實作 33
4-3-4 ARS方法實作 36
第五章 實驗解果與分析 38
5-1實驗環境 38
5-2樣本程式 39
5-3數據比較 41
第六章 結論與未來展望 46
結論 46
未來發展方向 46
參考文獻 48

[1] Z. Durumeric, J. Kasten, D. Adrian, J. A. Halderman, M. Bailey, F. Li, N. Weaver, J. Amann, J. Beekman, and M. Payer, "The matter of heartbleed." pp. 475-488.
[2] F. Bellard, "QEMU, a fast and portable dynamic translator." pp. 41-46.
[3] X. Zhang, X. Xie, and T. Y. Chen, "Test Case Prioritization Using Adaptive Random Sequence with Category-Partition-Based Distance." pp. 374-385.
[4] T. Y. Chen, H. Leung, and I. Mak, "Adaptive random testing," Advances in Computer Science-ASIAN 2004. Higher-Level Decision Making, pp. 320-329: Springer, 2004.
[5] B. Beizer, and J. Wiley, “Black box testing: Techniques for functional testing of software and systems,” iEEE Software, vol. 13, no. 5, pp. 98, 1996.
[6] B. P. Miller, “Fuzz testing of application reliability,” UW-Madison Computer Sciences, 2007.
[7] A. Takanen, J. D. Demott, and C. Miller, Fuzzing for software security testing and quality assurance: Artech House, 2008.
[8] A. T. Acree, T. A. Budd, R. A. DeMillo, R. J. Lipton, and F. G. Sayward, Mutation Analysis, DTIC Document, 1979.
[9] P. Garg, “Fuzzing-mutation vs. generation,” InfoSec Institute. Np, vol. 4, 2012.
[10] M. Zalewski, "American fuzzy lop," 2007.
[11] T. J. Ostrand, and M. J. Balcer, “The category-partition method for specifying and generating fuctional tests,” Communications of the ACM, vol. 31, no. 6, pp. 676-686, 1988.
[12] W. Dorman, “CERT Basic Fuzzing Framework,” blog, 2010.
[13] N. Stephens, J. Grosen, C. Salls, A. Dutcher, R. Wang, J. Corbetta, Y. Shoshitaishvili, C. Kruegel, and G. Vigna, "Driller: Augmenting fuzzing through selective symbolic execution."
[14] K. Sen, D. Marinov, and G. Agha, "CUTE: a concolic unit testing engine for C." pp. 263-272.
[15] M. Böhme, V.-T. Pham, and A. Roychoudhury, "Coverage-based greybox fuzzing as markov chain." pp. 1032-1043.
[16] 維基百科編者. "Curl," 2017-02-24UTC12:58:12+00:00 （UTC）; https://zh.wikipedia.org/w/index.php?title=CURL&oldid=43345587.
[17] 維基百科編者. "W3m," 2014-12-14UTC12:36:05+00:00 （UTC）; https://zh.wikipedia.org/w/index.php?title=W3m&oldid=33606229.
[18] G. E. Schalnat, A. Dilger, J. Bowler, and G. Randers-Pehrson, "libpng-The official PNG reference library."