為了避免發生格式化字串弱點所引起的問題，相關字串處理函式的行為必須有所規範，不應有超越界限存取參數的行為。若攻擊者有能力控制格式化字串函式的字串參數，便能利用此弱點，提供超出參數數量的轉換符號，進行不同型態的攻擊。
在本論文中，我們提出一個對printf與vprintf系列函式的偵測攻擊方法，發展一檢查函式存取參數是否超出界限的工具，稱為FormatDefense。此工具對格式化字串函式進行完整保護，藉由在記憶體上定義防禦線的方式，判斷此型態函式存取參數的合法性；若存取參數超越此防禦線則視為攻擊行為。我們將此方法實作在UNIX環境下，建立一個共享函式庫，並分析除錯資訊與追蹤堆疊變化，取得函式存取參數的界限，當程式執行時，只要連結此函式庫，便能保護格式化字串函式的運作。
　　我們考慮格式化字串儲存位置的變化，共歸納出六種可能的情境，評估偵測方法的有效性。實驗結果顯示，此工具皆能成功偵測到所有情境中的違法存取行為，且超越其他現存的偵測工具，證明我們的方法有更高的精確度；此外，我們將偵測方法應用在已知含有弱點的程式，皆能成功偵測到相關攻擊，驗證此方法的有效性；最後我們利用微型基準測試與巨型基準測試，評估工具所引起的執行負擔，實驗結果發現其負擔是可忽略的，顯示此工具能夠實際應用在真實程式中，防止格式化字串攻擊。

In order to prevent format string vulnerabilities, the behavior of accessing arguments for variadic functions should be regulated. A format string attack occurs because variadic functions rely on the format string argument to determine the number of arguments. Therefore, if an attacker has ability to control the format string argument, he can exploit format string vulnerabilities to attack programs by providing more conversion specifiers than needed. In this thesis, we develop an attack-detecting tool called FormatDefense for printf-like and vprintf-like functions to check if a variadic function accesses arguments outside its argument list. FormatDefense defines the access bound in the memory via offline analysis of debugging information and runtime tracking of the stack. It is implemented as a shared library in the UNIX environment. We consider six scenarios based on format string locations to evaluate the effectiveness of FormatDefense. The result shows that FormatDefense surpasses several existing detection tools in detecting invalid memory access in the six scenarios. Furthermore, FormatDefense can detect exploits successfully on several programs with known format string vulnerabilities. Eventually, we use various microbenchmarks and macrobenchmarks to evaluate the performance overhead. The overhead is negligible so that FormatDefense can be applied to real programs practically to avoid format string attacks.

摘要 i
Abstract ii
誌謝 iii
Table of Contents iv
List of Tables vi
List of Figures vii
1. Introduction 1
1.1 Problem Description 1
1.2 Background 2
1.2.1 Attack Models of the Format String Vulnerability 2
1.2.1.1 Accessing Arguments outside the Real Argument List 4
1.2.1.2 Accessing Tainted Variables 5
1.3 Motivation 6
1.4 Objective 7
1.5 Synopsis 8
2. Related Work 9
2.1 Detection of a Non-static Format String 9
2.2 Protection of a Format String Containing a %n Specifier 10
2.3 Bound Checking Method 11
2.3.1 The Saved Frame Pointer as the Defense Line (line-Sfp) 12
2.3.2 The Format String as the Defense Line (line-Fmt) 13
2.3.3 The Argument List as the Defense Line (line-Arg) 13
2.3.4 The Accuracy of the Defense Lines 15
2.4 Comparison 16
3. Method 18
3.1 Stack Walking 19
3.2 Determining Line-Arg and Detecting Attacks 20
3.3 Examples for Illustrating How to Find Line-Arg 21
3.4 An Algorithm for Detecting Attacks 23
4. Implementation 25
4.1 The Architecture of FormatDefense 25
4.2 Obtaining the Debugging Information 26
4.3 Skipping Read-only Format Strings 28
5. Effectiveness and Performance Evaluation 29
5.1 All Possible Scenarios 29
5.2 Effectiveness of FormatDefense’s Protection against Known Format String Attacks 36
5.3 Performance Benchmark 38
5.3.1 Microbenchmarks 38
5.3.2 Macrobenchmarks 40
5.4 Evaluation Discussion 40
5.4.1 Stack Alignment 41
5.4.2 Interaction between Sibling Functions 43
5.4.3 Attack Space of Line-Fmt in Fmt < Arg < Sfp Relationship 44
6. Conclusion 46
References 47

1. Lhee KS, Chapin SJ. Buffer overflow and format string overflow vulnerabilities. Software–Practice and Experience, 2003; 33 (5): 423-460.
2. Common Vulnerabilities and Exposures. Search Results for format. http://www.cve.mitre.org/cgi-bin/cvekey.cgi?keyword=format+string, January 28, 2008. [28 January 2008]
3. Christey S, Martin RA. Vulnerability Type Distributions in CVE. http://cwe.mitre.org/documents/vuln-trends/index.html, May 22, 2007. [3 Mar 2008]
4. Shankar U, Talwar K, Foster JS, Wagner D. Detecting Format String Vulnerabilities with Type Qualifiers. Proceedings of the 10th conference on USENIX Security Symposium, 2001; 201–218.
5. Chen K, Wagner D. Large-Scale Analysis of Format String Vulnerabilities in Debian Linux. Proceedings of the 2007 workshop on Programming Languages and Analysis for Security, 2007; 75-84.
6. Newsome J, Song D. Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software. Proceedings of the Network and Distributed System Security Symposium (NDSS 2005), 2005.
7. Cheng W, Zhao Q, Yu B, Hiroshige S. TaintTrace: Efficient Flow Tracing with Dynamic Binary Rewriting. Proceedings of 11th IEEE Symposium on Computers and Communications, 2006; 749-754.
8. Xu W, Bhatkar S, Sekar R. Taint-enhanced Policy Enforcement: A Practical Approach to Defeat a Wide Range of Attacks. Proceedings of the 15th conference on USENIX Security Symposium, 2006; 121–136.
9. Cowan C, Barringer M, Beattie S, Kroah-Hartman G, Frantzen M, Lokier J. FormatGuard: Automatic Protection from printf Format String Vulnerabilities. Proceedings of the 10th conference on USENIX Security Symposium, 2001.
10. Baratloo A, Tsai T, Singh N. Libsafe: Protecting Critical Elements of Stacks. December, 1999.
11. You JH, Seo SC, Kim YD, Choi JY, Lee SJ, Kim BK. Kimchi: A Binary Rewriting Defense against Format String Attacks. The 6th International Workshop on Information Security Applications, Jeju Island, Korea, August 22-24, 2005; 179-193.
12. DeKok A. PScan: A Limited Problem Scanner for C Source Files. 2000.
13. Rao DTVR. Detection of Bugs by Compiler Optimizer Using Macro Expansion of Functions. Proceedings of the 5th ACIS International Conference on Software Engineering Research, Management & Applications (SERA 2007), 2007; 855-862.
14. Robbins TJ. Libformat–Protection against Format String Attacks. 2001.
15. Ringenburg MF, Grossman D. Preventing Format-String Attacks via Automatic and Efficient Dynamic Checking. Proceedings of the 12th ACM conference on Computer and Communications Security, 2005; 354-363.
16. Lin Z, Xia N, Li G, Mao B, Xie L. Transparent Run-Time Prevention of Format-String Attacks Via Dynamic Taint and Flexible Validation. Proceedings of the 9th International Conference, Samos Island, Greece, 2006. (Lecture Notes in Computer Science, vol. 4176), 2006; 17-31.
17. Chen S, Xu J, Sezer EC, Gauriar P, Iyer RK. Non-control-data attacks are realistic threats. Proceedings of the 14th conference on USENIX Security Symposium, 2005; 177–192.
18. Tsai T, Singh N. Libsafe 2.0: Detection of Format String Vulnerability Exploits. White Paper, Avaya Labs, February, 2001.
19. Ganapathy V, Seshia SA, Jha S, Reps TW, Bryant RE. Automatic Discovery of API-Level Exploits. Proceedings of the 27th International Conference on Software Engineering, 2005; 312-321.
20. Li W, Chiueh T. Automated Format String Attack Prevention for Win32/X86 Binaries. Proceedings of the 23th Computer Security Applications Conference(ACSAC’07), 2007; 398-409.
21. Eager M, Eager Consulting. Introduction to the DWARF Debugging Format. February, 2007.
22. SecuriTeam. Multiple vulnerabilities in splitvt (Exploit Code). http://www.securiteam.com/unixfocus/5GP0J2A35C.html, 15 Jan. 2001. [3 Mar 2008]
23. SecuriTeam. PFinger Format String Vulnerability. http://www.securiteam.com/unixfocus/6K00N1P3FQ.html, 27 Dec. 2001. [3 Mar 2008]
24. SecuriTeam. tcpflow Format String Vulnerability. http://www.securiteam.com/unixfocus/5FP0H00AUO.html, 10 Aug. 2003. [3 Mar 2008]
25. Ye J. A proposal to align GCC stack – update. http://gcc.gnu.org/ml/gcc/2007-12/msg00567.html, 19 Dec 2007. [3 Mar 2008]
26. Shon H, Allen H, Chris E, Jonathan N, Michael L. Gray Hat Hacking; 382-384