以搜尋式方法偵測程式溢位弱點

Abstract

緩衝區溢位攻擊是一種最惡名昭彰的軟體安全問題。有些工具已經被發展作為緩衝區溢位弱點偵測之用。儘管有偵測的能力，大部分的現有工具無法產生能夠觸發溢位的測試案例。我們提出一個新的方法來解決針對溢位偵測的測試案例產生問題。這個方法使用搜尋式結構測試，能夠找到測試輸入使得程式執行走到目標點,也就是溢位產生的地方。搜尋式測試方法的概念是將產生測試資料以公式化轉換為搜尋的問題。在搜尋式測試中，一個被稱作鏈結方法的資料相依分析技巧可以幫助處理因為資料相依引起的搜尋失敗。鏈結方法被應用在找出影響緩衝區存取是否越界的程式敘述，接著產生抽象路徑引導程式執行滿足緩衝區溢位的條件。論文中展示的兩個最佳化技巧可以減少鏈結方法中在不必要路徑上的花費。在結果評估中顯示，與原有的搜尋式方法相比，我們的方法可以以較有效率的方式來偵測緩衝區溢位。

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.