Cyber Grand Challenge(CGC)是由美國國防部高等研究計畫署(DARPA)舉辦的全自動化電腦攻防競賽。本論文參考競賽規則，結合模糊測試、錯誤定位、與修補三樣技術，建造一個全自動化的Cyber Reasoning System(CRS)。我們實驗室在自動化攻擊方面已有成果，因此希望結合錯誤定位技術，進一步發展成自動化修補技術，形成一個全自動化的攻防系統。除了競賽題目外，我們嘗試將系統應用在真實程式的漏洞，希望以自動化的方式改善資訊安全，彌補人力無暇顧及的部分。

The department of defense (DOD) in the US has called for the contest in automatic attack and defense. The contest is a big challenge on the security development and called Cyber Grand Challenge (CGC). We consult to the competition rules and develop an automatic cyber reasoning system (CRS) to fulfill the goals. Our CRS combines with the techniques of fuzz testing, fault localization, and binary patch to build an automatic defense system. With the former efforts developed in the SQLab for automatic attack, we further integrate into a CRS for automatic attack and defense. Other than the sample problems in the CGC, we evaluate our systems in the binary patch capability on real programs. This work will be a preliminary study for potential participations on the future CGC.

摘要 I
ABSTRACT II
誌謝 III
表目錄 VI
圖目錄 VII
1 Introduction 1
1-1 Motivation 1
1-2 Problem Description 2
1-3 Objective 2
1-4 Overview 3
2 Background 4
2-1 Software Debugging 4
2-1-1 Program Failure 4
2-1-2 Manual Debugging 6
2-1-3 Automatic Debugging 6
2-2 Fault Localization 7
2-2-1 Slicing-based Techniques 7
2-2-2 Binary Similarity Coefficient-based Analysis 9
2-3 Cyber Grand Challenge 11
3 Method 13
3-1 System Architecture 13
3-2 Fault Localization 15
3-2.1 Binary Similarity Analysis With Dstar algorithm 15
3-2-2 Dynamic Program Slicing 18
3-3 Autonomous Patching 19
3-3-1 Stack Overflow Classified 20
3-3-2 Autonomous Understanding Fault 21
3-3-3 Autonomous Fault Patching 22
4 Result 24
5 Future Work 28
6 Conclusion 29
參考資料 31

1. Antoniol, G., et al. Is it a bug or an enhancement?: a text-based approach to classify change requests. in Proceedings of the 2008 conference of the center for advanced studies on collaborative research: meeting of minds. 2008. ACM.
2. Martin, B., et al., 2011 CWE/SANS top 25 most dangerous software errors. Common Weakness Enumeration, 2011. 7515.
3. Ayewah, N., et al., Using static analysis to find bugs. Software, IEEE, 2008. 25(5): p. 22-29.
4. Ball, T. The concept of dynamic analysis. in Software Engineering—ESEC/FSE’99. 1999. Springer.
5. Vessey, I., Expertise in Debugging Computer Programs. Information Systems Working Papers Series, Vol, 1984.
6. Weiser, M. Program slicing. in Proceedings of the 5th international conference on Software engineering. 1981. IEEE Press.
7. Agrawal, H. and J.R. Horgan. Dynamic program slicing. in ACM SIGPLAN Notices. 1990. ACM.
8. DeMillo, R.A., H. Pan, and E.H. Spafford. Critical slicing for software fault localization. in ACM SIGSOFT Software Engineering Notes. 1996. ACM.
9. Gyimóthy, T., Á. Beszédes, and I. Forgács. An efficient relevant slicing method for debugging. in Software Engineering—ESEC/FSE’99. 1999. Springer.
10. Zhang, X., R. Gupta, and Y. Zhang. Precise dynamic slicing algorithms. in Software Engineering, 2003. Proceedings. 25th International Conference on. 2003. IEEE.
11. Zhang, X., N. Gupta, and R. Gupta. Pruning dynamic slices with confidence. in ACM SIGPLAN Notices. 2006. ACM.
12. Parnin, C. and A. Orso. Are automated debugging techniques actually helping programmers? in Proceedings of the 2011 International Symposium on Software Testing and Analysis. 2011. ACM.
13. Choi, S.-S., S.-H. Cha, and C.C. Tappert, A survey of binary similarity and distance measures. Journal of Systemics, Cybernetics and Informatics, 2010. 8(1): p. 43-48.
14. Luk, C.-K., et al. Pin: building customized program analysis tools with dynamic instrumentation. in Acm Sigplan Notices. 2005. ACM.
15. Wong, W.E., et al. Software fault localization using DStar (D*). in Software Security and Reliability (SERE), 2012 IEEE Sixth International Conference on. 2012. IEEE.
16. Miller, M., A Brief History of Exploitation Techniques & Mitigations on Windows. 2007.