隨著軟體產業的蓬勃發展，若要維繫良好的軟體品質，必然要能找出軟體錯誤的原因。然而軟體日趨複雜，人工方式除錯成本高昂，已難以應付龐大的程式碼。尋求降低漏洞測試成本、提高除錯效率，成為相關自動化工具發展的最大需求。
自動化的測試工具近年來發展迅速，現存有許多自動化漏洞測試工具，包括Smartfuzz [1]、BFF [2]和FOE [3]等。然而自動化工具中，錯誤分類這個環節的研究日漸趨緩，因此本論文提出一種新的錯誤分類方法，有別於傳統錯誤分類法、基於除錯器的歷史呼叫堆疊(stack trace)為基準，我們提出運用程式碼覆蓋範圍(code coverage)、來達成錯誤分類的需求，。
在評估方面，我們以實際程式(real program)與測試程式(test program)為目標程式，在觀察程式行為後，設計出覆蓋整個原始碼可能路徑的輸入資料。在分類方法上，則是以gcov [4]分析測資涵蓋率，當目標程式輸入測試資料時，若程式發生失誤，則透過分析程式的gcov檔案進行錯誤分類。我們同時針對同筆測試資料經傳統方法分類，比較兩者的分類結果，顯現過去分類方法的缺陷，並探討透過以程式碼覆蓋範圍為基準的方法，改善缺陷、使分類結果更精準。

Software is getting complicated due to the changing needs and flourishing development of software industry. To better improve software quality, we need to find the major reasons which cause the program crash. However, debugging by software developer is not an efficient method, especially in large software. Many automated tools are developed to enhance the fault localization efficiency and reduce the maintenance cost.
Several automated tools include smartfuzz, BFF and FOE. Most of the researches are focused on improving software testing process, and the primary triage method is based on the stack trace hash, and is unchanged for a long time. Therefore, we propose a new triage method based on code coverage.
We use real programs and special test methods as our target. After observing program behavior, we produce different input data sets for all possible paths. Our triage method is designed by analyzing the gcov coverage results, on every time the input causes the program crash. For the same crash input, we also use traditional stack trace hash method to contrast the flaws with our proposed method. Our experiment results reveal that our proposed method based on code coverage exhibits better triages in terms of number of unique bugs and correct classifications of faults.

目錄
摘要 Ⅲ
致謝 Ⅴ
目錄 Ⅵ
表目錄 Ⅷ
圖目錄 Ⅸ
第一章 緒論 1
1-1 研究動機 1
1-2 研究目標 2
1-3 論文大綱 2
第二章 研究背景 3
2-1 失敗程式 3
2-1-1 失敗程式(FAILURE PROGRAM) 3
2-1-2 CRASH DATA 3
2-2 軟體錯誤 4
2-2-1 軟體錯誤(FAULT) 4
2-2-2 錯誤分類(FAULT TRIAGE) 4
2-2-3 錯誤定位 (FAULT LOCALIZATION) 5
2-2-4 DSTAR 5
2-3 CODE COVERAGE RECORD 7
第三章 相關研究 8
3-1 漏洞測試工具原理（FUZZER / FUZZING TOOL） 8
3-2 漏洞測試工具 8
3-2-1 CATCHCONV 8
3-2-2 BFF 9
3-2-3 COVERSET 9
3-3 錯誤分類工具 10
3-3-1 SMARTFUZZ 10
3-3-2 VPM ANALYSIS 10
3-3-3 CERT TRIAGE TOOL 10
3-3-4 基於STACK TRACE的錯誤分類原理 11
3-3-5 基於STACK TRACE的錯誤分類缺陷 13

第四章 研究方法 16
4-1 演算法 16
4-1-1 第一種情況：SV交集S，完全互斥錯誤路徑 18
4-1-2 第二種情況：分支錯誤分類一（暫且無法克服） 18
4-1-3 第三種情況：分支錯誤分類二 19
4-1-4 第四種情況：錯誤輸入資料產生新的路徑生成新分類 19
4-2 研究問題 20
第五章 實驗結果與分析 21
5-1 整合系統架構 21
5-1-1 FUZZING PHASE 21
5-1-2 TEST PHASE 22
5-1-3 TRIAGE PHASE 22
5-1-4 REPORT GENERATE PHASE 22
5-2 實驗實作細節 23
5-2-1 測試資料產生方法 23
5-2-2 使用GCOV紀錄程式碼覆蓋範圍 23
5-3 GCOV檔分析方法 25
5-4 測試結果 26
5-4-1 測試程式分析 26
5-4-2 REAL PROGRAM 30
5-5 不同方法於不同程式碼架構分析 34
5-6 分類方法比較與限制 36
5-6-1 比較 36
5-6-2 限制 36
第六章 結論與未來展望 37
6-1 結論 37
6-2 未來展望 37
參考文獻 38

[1] “SmartFuzz,” [線上]. Available: https://github.com/dmolnar/SmartFuzz.
[2] “BFF (Basic Fuzzing Framework),” CERT, [線上]. Available: http://www.cert.org/vulnerability-analysis/tools/bff.cfm.
[3] “FOE (Failure Observation Engine),” CERT, [線上]. Available: http://www.cert.org/vulnerability-analysis/tools/foe.cfm.
[4] “GCOV online document,” [線上]. Available: https://gcc.gnu.org/onlinedocs/gcc/Gcov.html.
[5] David Molnar, Xue Cong Li, David Wagner, “Dynamic Test Generation to Find Integer Bugs in x86 Binary Linux Programs,” USENIX, pp. 67-82, August 2009.
[6] Wei Jin, Alessandro Orso, “F3: fault localization for field failures,” Proceedings of the 2013 International Symposium on Software Testing and Analysis, pp. 213-223, July 2013.
[7] “GDB: The GNU Project Debugger,” [線上]. Available: https://www.gnu.org/software/gdb/.
[8] “Valgrind,” [線上]. Available: http://valgrind.org/.
[9] W Eric Wong, Vidroha Debroy, Yihao Li, Ruizhi Gao, “Software fault localization using DStar (D*),” IEEE Sixth International Conference (SERE), pp. 21-30, June 2012.
[10] “CERT Triage Tools,” CERT, [線上]. Available: http://www.cert.org/vulnerability-analysis/tools/triage.cfm.
[11] Christopher Theisen, Kim Herzig, Patrick Morrison, Brendan Murphy, Laurie Williams, “Approximating Attack Surfaces with Stack Traces,” IEEE Companion Proceedings of the 37th International Conference on Software Engineering , 2015.
[12] Alexandre Rebert, Sang Kil Cha, Thanassis Avgerinos, Jonathan Foote, David Warren, Gustavo Grieco, David Brumley, “Optimizing seed selection for fuzzing,” USENIX, pp. 861-875, Augest 2014.
[13] P. Willett, “Similarity-based approaches to virtual screening,” Biochemical Society Transactions 31(3), pp. 603-606, June 2003 .
[14] S. Choi, S. Cha, C. C. Tappert, “A Survey of Binary Similarity and Distance Measures,” Journal of Systemics, Cybernetics and Informatics 8(1), pp. 43-48, January 2010.
[15] “D3JS Data-Driven Documents,” [線上]. Available: http://d3js.org/.
[16] P. UHLEY, “A basic distributed fuzzing framework for foe,” [線上]. Available: https://blogs.adobe.com/security/2012/05/.
[17] GODEFROID, P., LEVIN, M. Y., AND MOLNAR, D. Sage, “Whitebox fuzzing for security testing.,” Communications of the ACM 55, pp. 40-44, March 2012.
[18] LANGNER, R. Stuxnet, “Dissecting a cyberwarfare weapon,” IEEE Security & Privacy Magazine 9, 3, pp. 49-51, May 2011.
[19] David A Molnar, David Wagner, “Catchconv: Symbolic execution and run-time type inference for integer conversion errors,” UC Berkeley EECS, February 2007.
[20] “STP,” [線上]. Available: https://github.com/stp/stp.
[21] “Pin - A Dynamic Binary Instrumentation Tool,” [線上]. Available: https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool.
[22] Dan Hao, Tao Xie, Lu Zhang, Xiaoyin Wang, Jiasu Sun, Hong Mei, “Test input reduction for result inspection to facilitate fault localization,” Journal Automated software engineering 17, pp. 5-31, March 2010.
[23] Maverick Woo, Sang Kil Cha, Samantha Gottlieb, David Brumley, “Scheduling black-box mutational fuzzing,” ACM, pp. 511-522, November 2013.
[24] Shih-Kun Huang,Min-Hsiang Huang,Po-Yen Huang,Chung-Wei La,Han-Lin Lu,Wai-Meng Leong, “CRAX: Software Crash Analysis for Automatic Exploit,” Software Security and Reliability (SERE), 2012 IEEE Sixth International Conference on, pp. 78 - 87, 20-22 June 2012.
[25] “S2E - A Platform for In-Vivo Multi-Path Software Analysis,” [線上]. Available: https://github.com/dslab-epfl/s2e & https://s2e.epfl.ch.