[發明專利]一種基于前向探針的離線符號執行路徑搜索方法

在審

• 申請號: 202010085873.2
• 申請日: 2020-02-11
• 公開（公告）號: CN111400165A
• 公開（公告）日: 2020-07-10
• 發明（設計）人: 魏強;武澤慧;柳曉龍;杜江;李錫星;麻榮寬
• 申請（專利權）人: 中國人民解放軍戰略支援部隊信息工程大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 鄭州大通專利商標代理有限公司 41111
• 代理人: 張立強

本發明涉及一種基于前向探針的離線符號執行路徑搜索方法，當模糊測試工具產生的樣本無法遍歷新的狀態轉移時，算法會調用符號執行引擎選取一個隊列中的樣本，沿著樣本執行軌跡從程序入口開始逐個翻轉分支點并且嘗試求解能夠遍歷分支點的另一條邊的樣本，若發現了新的狀態轉移，即沒有被符號執行遍歷過，也沒有被模糊測試遍歷過，則返回真，否則會創建一個動態符號執行探針繼續向前執行，若有限步之內沒有發現新的狀態轉移，則返回假。本發明可以提高符號執行技術與模糊測試技術結合算法的覆蓋率，準確度較高，提高了遍歷新的狀態轉移的速度，并且對測試效率影響很小；解決了已有算法對于翻轉后不能立即產生新的狀態轉移的分支點不進行約束求解的問題。

技術領域

本發明屬于軟件安全測試技術領域，尤其涉及一種基于前向探針的離線符號執行路徑搜索方法。

背景技術

模糊測試工具通過隨機變異的方法來產生大量的畸形樣本對程序進行壓力測試，并且監控畸形樣本能否觸發程序崩潰或異常。但是，大多數通過變異產生的樣本難以通過程序內部的復雜檢查，從而導致無法發現程序深層的漏洞。符號執行工具雖然理論上可以提高測試覆蓋率，但是由于路徑爆炸問題限制了其分析的路徑深度。

為了發揮模糊測試技術與符號執行技術各自的優勢，并且彌補各自的不足，DrillerCore路徑搜索算法(Stephens N,Grosen J,Salls C,et al.Driller:AugmentingFuzzing Through Selective Symbolic Execution[C]//NDSS.2016,16(2016):1-16.)將兩者相結合，利用符號執行引擎的求解優勢來輔助模糊測試工具通過程序中的復雜檢查。例如，命令解析程序從用戶讀取命令字符串，將其與程序內置的命令列表進行比較，并將用戶提供的參數傳遞給對應的命令處理函數。在這種情況下，復雜的檢查就是命令字符串的比較，但是模糊隨機變異輸入將有非常小的概率發送正確的命令字符串。當模糊測試工具產生的樣本無法遍歷到新的狀態轉移時，算法會調用符號執行引擎來產生新的樣本。符號執行引擎能夠求解出正確的命令字符串之后，調用模糊測試工具來變異命令參數，而不會遇到路徑爆炸。

但是該算法會導致有些控制流依賴的狀態轉移無法被遍歷。因為有些分支點被翻轉以后雖然無法立即產生新的狀態轉移，但是會間接影響該分支點之后的狀態轉移。如果程序中有較長的命令字符串匹配，僅僅依靠隨機變異很難滿足約束條件，所以很快模糊測試方法就無法發現新的狀態轉移。復雜分支的約束只能依靠符號執行引擎來進行求解，但是算法對于翻轉后沒有新的狀態轉移的分支點的約束條件不進行求解，即無法發揮符號執行引擎的求解優勢。

發明內容

本發明針對DrillerCore路徑搜索算法對于翻轉后不能立即產生新的狀態轉移的分支點不進行約束求解，只看眼前利益的路徑搜索算法會導致控制依賴于該分支點的狀態轉移無法被遍歷的問題，提出一種基于前向探針的離線符號執行路徑搜索方法。

為了實現上述目的，本發明采用以下技術方案：

一種基于前向探針的離線符號執行路徑搜索方法，包括：

步驟1：對程序使用模糊測試工具進行分析，將模糊測試工具產生的能夠遍歷新的狀態轉移的樣本作為下一代變異的種子樣本；

步驟2：當步驟1中產生的樣本無法遍歷新的狀態轉移時，符號執行引擎從樣本隊列中選取一個樣本生成離線符號執行軌跡；

步驟3：將步驟2中生成的離線符號執行軌跡從程序入口開始逐個翻轉分支點，并創建一個動態符號執行探針作為前向探針沿著翻轉狀態向前探測該分支點是否影響后續分支的跳轉，同時探測附近是否有新的狀態轉移；

步驟4：如果步驟3中分支點在翻轉時發現新的狀態轉移，或者前向探針探測到該分支點附近有新的狀態轉移，則嘗試對翻轉狀態進行約束求解；

步驟5：如果步驟4中翻轉狀態可解，則將產生的新樣本加入到模糊測試樣本隊列中，將翻轉狀態加入到已遍歷集合中；