帳號:guest(54.160.243.44)          離開系統
字體大小: 字級放大   字級縮小   預設字形  

詳目顯示

以作者查詢圖書館館藏以作者&題名查詢臺灣博碩士以作者查詢全國書目
作者:黃琨翰
作者(英文):Huang, Kuen-Han
論文名稱(中文):以搜尋式方法偵測程式溢位弱點
論文名稱(英文):Detecting Buffer Overflow Vulnerabilities via Search-based Testing
指導教授(中文):黃世昆
指導教授(英文):Huang, Shih-Kun
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學與工程研究所
學號:9655575
出版年(民國):98
畢業學年度:97
語文別:英文
論文頁數:39
中文關鍵詞:軟體測試搜尋式測試緩衝區溢位
外文關鍵詞:Software TestingSearch-based TestingBuffer Overflow
相關次數:
  • 推薦推薦:0
  • 點閱點閱:392
  • 評分評分:*****
  • 下載下載:10
  • 收藏收藏:0
緩衝區溢位攻擊是一種最惡名昭彰的軟體安全問題。有些工具已經被發展作為緩衝區溢位弱點偵測之用。儘管有偵測的能力,大部分的現有工具無法產生能夠觸發溢位的測試案例。我們提出一個新的方法來解決針對溢位偵測的測試案例產生問題。這個方法使用搜尋式結構測試,能夠找到測試輸入使得程式執行走到目標點,也就是溢位產生的地方。搜尋式測試方法的概念是將產生測試資料以公式化轉換為搜尋的問題。在搜尋式測試中,一個被稱作鏈結方法的資料相依分析技巧可以幫助處理因為資料相依引起的搜尋失敗。鏈結方法被應用在找出影響緩衝區存取是否越界的程式敘述,接著產生抽象路徑引導程式執行滿足緩衝區溢位的條件。論文中展示的兩個最佳化技巧可以減少鏈結方法中在不必要路徑上的花費。在結果評估中顯示,與原有的搜尋式方法相比,我們的方法可以以較有效率的方式來偵測緩衝區溢位。
Buffer overflow attacks are one of the most notorious software security problems. A few tools have been developed to detect buffer overflow vulnerabilities. In spite of the detection capability, most of the existing tools can not generate test cases to trigger an overflow. We propose a new approach that addresses the issue of test case generation for buffer overflow detection. The approach uses search-based structural testing to find test inputs that drive program execution to reach the target node where a buffer overflow could occurs. The idea of search-based testing is to formulate the test data generation for a program under test as a search problem. In search-based testing, a data dependence analysis technique called the Chaining Approach can help to handle the search failure due to data dependencies. The Chaining Approach is applied to identify the program statements that have influence on whether a buffer accesses is out of bound or not, then abstract paths are derived to lead the program execution to satisfy a buffer overflow condition. Two optimization techniques are presented to reduce the cost of exercising unnecessary paths in the Chaining Approach. The evaluation results show that our approach can find test data for buffer overflow detection in a more efficient way than using the original approach in search-based testing.
摘要 i
Abstract ii
誌謝 iii
Table of Contents iv
List of Tables v
List of Figures vi
1. Introduction 1
1.1 Motivation 1
1.1.1 Static Analysis 3
1.1.2 Dynamic Analysis 3
1.2 Problem Description and Objective 4
2. Background 6
2.1 Search-based Test Data Generation 6
2.2 Objective Function 8
2.3 The Chaining Approach 10
2.3.1 Example for the Chaining Approach 12
2.3.2 Formal Description 13
3. Related Work 14
4. Method 16
4.1 Objective Function for Buffer Overflows 16
4.2 Applying the Chaining Approach for Buffer Overflow Detection 17
4.2.1 Extra Out-of-bound Checking 17
4.2.2 Optimization Strategies for the Chaining Approach 19
4.2.2.1 Look-Ahead Strategy 19
4.2.2.2 Tainted-First Strategy 24
5. Implementation 29
5.1 Static Frontend 29
5.2 Dynamic Component: Search-based Testing 29
6. Results 31
6.1 Test Objects 31
6.2 Experimental Setup 32
6.3 Evaluation Results 33
7. Conclusion 35
References 37
[1] N. Tuck, B. Calder and G. Varghese, "Hardware and binary modification support for code pointer protection from buffer overflow," in Proceedings of the International Symposium on Microarchitecture, pp. 209-220, 2004.
[2] CERT, CERT/CC advisories, http://www.cert.org/advisories/, January 2004.
[3] US-CERT, Technical cyber security alerts, http://www.us-cert.gov/cas/techalerts/, June 2009
[4] D. Evans and D. Larochelle, "Improving security using extensible lightweight static analysis," IEEE Software, pp. 42-51, 2002.
[5] M. Zitser, R. Lippmann and T. Leek, "Testing static analysis tools using exploitable buffer overflows from open source code," ACM SIGSOFT Software Engineering Notes, vol. 29, pp. 97-106, 2004.
[6] N. Nethercote and J. Seward, "Valgrind: A framework for heavyweight dynamic binary instrumentation," in Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 89-100, 2007.
[7] O. Ruwase and M. S. Lam, "A practical dynamic buffer overflow detector," in Proceedings of the 11th Annual Network and Distributed System Security Symposium, 2004,
[8] P. Godefroid, N. Klarlund and K. Sen, "DART: Directed automated r andom testing," in Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2005.
[9] K. Sen, D. Marinov and G. Agha, "CUTE: A concolic unit testing engine for C," in Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 263-272, 2005.
[10] C. Cadar and D. Engler, "Execution generated test cases: How to make systems code crash itself," in Proceedings of the 12th International SPIN Workshop on Model Checking of Software (SPIN’05), 2005,
[11] C. Cadar, V. Ganesh, P. M. Pawlowski, D. L. Dill and D. Engler, "EXE: Automatically generating inputs of death," in CCS ’06: Proceedings of the 13th ACM Conference on Computer and Communications Security, pp. 322-335, 2006.
[12] P. McMinn, "Search-based software test data generation: a survey," Software Testing, Verification & Reliability, vol. 14, pp. 105-156, 2004.
[13] B. Korel, "Dynamic Method of Software Test Data Generation," Software Testing, Verification & Reliability, vol. 2, pp. 203-213, 1992.
[14] B. Korel, "Automated software test data generation," IEEE Transactions on Software Engineering, vol. 16, pp. 870-879, 1990.
[15] N. Tracey, J. Clark, K. Mander and J. McDermid, "An automated framework for structural test-data generation," in Proceedings of the 13th IEEE international conference on Automated software engineering, pp. 285-288, 1998.
[16] N. Tracey, J. Clark and K. Mander, "The way forward for unifying dynamic test-case generation: The optimisation-based approach," in International Workshop on Dependable Computing and its Applications (DCIA), 1998, pp. 169-180.
[17] S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas and K. Karapoulios, "Application of genetic algorithms to software testing (application des algorithmes genetiques au test des logiciels)," in 5th International Conference on Software Engineering and its Applications, pp. 625-636, 1992.
[18] P. McMinn and M. Harman, "A theoretical & empirical analysis of evolutionary testing and hill climbing for structural test data generation," in Proceedings of the International Symposium on Software Testing and Analysis (ISSTA 2007), pp. 9-12, 2007.
[19] R. Ferguson and B. Korel, "The chaining approach for software test data generation," ACM Transactions on Software Engineering and Methodology (TOSEM), vol. 5, pp. 63-86, 1996.
[20] P. McMinn and M. Holcombe, "Hybridizing evolutionary testing with the chaining approach," in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), 2004,
[21] P. McMinn and M. Holcombe, "Evolutionary testing using an extended chaining approach," Evolutionary Computation, vol. 14, pp. 41-64, 2006.
[22] N. Tracey, J. Clark, J. McDermid and K. Mander, "Integrating safety analysis with automatic test-data generation for software safety verification," in Proceedings of the 17th International Conference on System Safety, pp. 128–137, 1999.
[23] N. Tracey, J. Clark, K. Mander and J. McDermid, "Automated test-data generation for exception conditions," SOFTWARE—PRACTICE AND EXPERIENCE, pp. 61-79, 2000.
[24] C. Del Grosso, G. Antoniol, M. Di Penta, P. Galinier and E. Merlo, "Improving network applications security: A new heuristic to generate stress testing data," in Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, pp. 1037-1043, 2005.
[25] C. Del Grosso, G. Antoniol, E. Merlo and P. Galinier, "Detecting buffer overflow via automatic test input data generation," Computers and Operations Research, vol. 35, pp. 3125-3143, 2008.
[26] G. C. Necula, S. McPeak, S. P. Rahul and W. Weimer, "CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs," LECTURE NOTES IN COMPUTER SCIENCE, pp. 213-228, 2002.
[27] Boost, "Boost Graph Library," http://www.boost.org/doc/libs/release/libs/graph/
[28] M. Wall, "GAlib: A C++ library of genetic algorithm components," Mechanical Engineering Department, Massachusetts Institute of Technology, 1996.
[29] C. Tsai and S. Huang, "Detection and diagnosis of control interception," in 9th International Conference on Information and Communications Security (ICICS), 2007,
[30] T. Xie, N. Tillmann, P. de Halleux and W. Schulte, "Fitness-guided path exploration in dynamic symbolic execution," Technical Report MSR-TR-2008-123, Microsoft Research, 2008.
[31] K. Inkumsah and T. Xie, "Evacon: A framework for integrating evolutionary and concolic testing for object-oriented programs," in Proceedings of the Twenty-Second IEEE/ACM International Conference on Automated Software Engineering, pp. 425-428, 2007.
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
* *