利用迴圈特性加速靜態與動態程式分析

RELEASE: Generating Exploits using Loop-Aware Concolic Execution

李秉翰(Bing-Han Li)

指導教授 ： 謝續平

國立交通大學/資訊學院/網路工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00913

摘要

自動尋找軟體漏洞以及產生如何滲透軟體安全之過程為當今軟體測試方法所迫切需求。實際/符號混和執行測試技術(concolic execution)為符合此需求的新技術之一，其結合了實際執行測試的速度優點以及符號化執行測試的廣泛可測範圍。然而，此技術繼承了符號化執行測試的限制 －面對迴圈時，當迴圈執行次數與外部輸入值有相依性，此技術必須將每種可能的外部輸入值都執行過一次，進而造成效能嚴重降低，甚至退化成為隨機測試。而迴圈是程式語言中大量使用的一種必要格式，這造成此技術面臨相當大的挑戰。在本論文中，我們提出一個新的實際/符號混和執行測試技術，稱為：”迴圈感知實際/符號混和執行測試技術(loop-aware concolic execution)”。本新技術可精確分析迴圈相關變數，並減少軟體測試所需之時間。為了展示此項新技術，我們開發了一套分析系統，稱為：”RELEASE”。在本分析系統中，我們將此項新技術應用在分析緩衝區溢位漏洞，並產生如何滲透軟體安全之外部輸入值。

關鍵字

實際與符號化執行 ； 符號化執行 ； 軟體測試

並列摘要

Automatically finding vulnerabilities and even generating exploits are eagerly needed by software testing engineers today. And for security issue, many testing software are usually lake of source code and symbol table information. Concolic execution is a novel technique, which takes advantage of the rapid executing speed of concrete ex-ecution and the wide testing coverage of symbolic execution, to find and understand software bugs, including vulnerabilities, with only analyzing machine code. However, a serious limitation of concolic execution inherited from symbolic execution is its poor analysis result with loops, a common programming construct. Namely, when the number of iterations depends on the inputs, the analysis cannot determine possible execution paths of the program. In this paper, we propose a new concolic execution technique, loop-aware concolic execution, for testing software and producing more precise analysis on loop-related variables with fewer execution steps. To demonstrate our technique, we developed a concolic analyzer, called RELEASE, and apply it to discover buffer-overflow vulnerabilities and generate exploits of software.

並列關鍵字

Concolic Execution ； Symbolic Execution ； Software Testing

參考文獻

[1] B. P. Miller, L. Fredriksen, and B. So, “An Empirical-Study of the Reliability of Unix Utilities,” Communications of the Acm, vol. 33, no. 12, pp. 32-43, Dec, 1990.

[4] J. C. King, “Symbolic Execution and Program Testing,” Communications of the Acm, vol. 19, no. 7, pp. 385-394, 1976.

[6] A. Lanzi, L. Martignoni, M. Monga, and R. Paleari, “A Smart Fuzzer for x86 Executables,” in Proceedings of the Third International Workshop on Software Engineering for Secure Systems, 2007, p. 7.

[8] T. Reps, G. Balakrishnan, J. Lim, and T. Teitelbaum, “A next-generation platform for analyzing executables,” in Proceedings of the Third Asian Symposium on Programming Languages and Systems (APLAS'05), Tsukuba, Japan, 2005, pp. 212-229.

[21] F. Bellard, “QEMU, a fast and portable dynamic translator,” in Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference (ATEC'05), Anaheim, California, USA, 2005, p. 41.