以減少指標過度污染方法加速基於污染分析之實際與符號混合執行測試技術

Abstract

在基於污染分析的實際/符號混合執行測試技術(taint-based concolic testing)上, 對於間接從記憶體中讀取出來的資料，污染傳播的結果可能造成指標過度污染(pointer overtaint)或是指標污染傳遞斷層(pointer undertaint)。這兩種不適當的污染傳播方式會使基於污染分析的實際/符號混合執行測試技術發生不足夠條件或多餘條件的情形。缺乏某些程式執行路徑的條件將導致錯誤的測試結果，而增加多餘程式執行路徑的條件則相對地造成條件解算器(constraint solver)的負擔，延長測試的時間。在本篇論文中，為了節省測試的時間,我們提出第一個方法來處理在基於污染分析的實際/符號混合執行測試技術上間接記憶體讀取(indirect memory retrieval)所導致的指標過度污染問題。我們所提出的方法可以辨識程式中變數和分枝條件(branch condition)的關係，若兩者存在著明確的關係，間接記憶體讀取所導致的指標過度污染便可被減少，且也能在不缺乏某些程式執行路徑條件的情況下，刪除多餘的程式執行路徑條件。由於減少了指標過度污染來縮小路徑執行條件(path constraint)的集合大小，測試的時間也可被減少。在有系統探索程式路徑及偵測程式弱點的同時，我們提出的方法可以有效地加速基於污染分析的實際/符號混合執行測試技術。

In taint-based concolic testing, the taint propagation of indirect memory retrieval may cause either pointer undertaint or overtaint. The inappropriate taint will cause insuffi-cient or redundant constraints for taint-based concolic testing. The insufficient con-straint will lead to an exploitable testing. On the other hand, the redundant constraint significantly slows down the test due to the fact that the constraint solving time de-pends on the constraint size. In this paper, to save the constraint solving time, we propose the first approach to coping with pointer overtaint problems caused by the indirect memory retrieval in taint-based concolic testing. The new tainting approach identifies the relation between variables and branch conditions in an analyzed program. With the confirmative relation, pointer overtaint caused by the indirect memory retrieval can be pruned to eliminate redundant constraints without the occurrence of insufficient constraints. The size of the path constraints is so depressed that the con-straint solving time is reduced. While exploring the target program exhaustively and detecting potential vulnerabilities, the proposed tainting approach can substantially accelerate taint-based concolic testing.