[發(fā)明專利]一種用于漏洞發(fā)掘的動態(tài)符號執(zhí)行路徑搜索方法

有效

• 申請?zhí)枺?/td>: 201410230479.8
• 申請日: 2014-05-28
• 公開（公告）號: CN104008053A
• 公開（公告）日: 2014-08-27
• 發(fā)明（設計）人: 張小松;黃金;牛偉納;陳瑞東;王東;徐浩然;白金;賴特;李金栓;于洲
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 成都華典專利事務所(普通合伙) 51223
• 代理人: 徐豐

技術領域

本發(fā)明涉及軟件測試領域，提供了一種用于漏洞發(fā)掘的動態(tài)符號執(zhí)行路徑搜索方法。

背景技術

軟件開發(fā)是一項腦力密集型且需要豐富編程經(jīng)驗的一項工作，因此，開發(fā)一款正確性、穩(wěn)定性、安全性都符合要求的軟件非常困難。軟件測試是保證軟件可靠性和安全性的關鍵技術，在軟件開發(fā)周期中占據(jù)著非常重要的地位。動態(tài)符號執(zhí)行是目前軟件安全、軟件測試研究領域的熱點技術之一，它通過自動生成測試用例，可以以獲取高代碼覆蓋率，被用于當前許多主流軟件測試工具中。利用動態(tài)符號執(zhí)行技術，通過符號化的方法探索遍歷程序的所有可能執(zhí)行路徑，產(chǎn)生路徑約束，并對約束條件求解，自動化產(chǎn)生測試用例，在理論上能夠?qū)崿F(xiàn)對被測程序全路徑的覆蓋，再輔助其他漏洞檢測技術，可以全面、準確地檢測程序中潛在的漏洞。

使用動態(tài)符號執(zhí)行進行漏洞發(fā)掘的一般過程如下：首先對分析的程序文件（可執(zhí)行文件或者字節(jié)碼文件）進行二進制插樁，在第一次執(zhí)行時，給程序提供一個隨機的或選擇的初始輸入數(shù)據(jù)，然后借助插樁代碼對輸入數(shù)據(jù)符號化，在程序執(zhí)行過程中，同時進行符號執(zhí)行。插樁代碼會記錄符號化的變量在每個執(zhí)行路徑下的操作。在執(zhí)行過程中調(diào)用漏洞檢測模塊檢測程序中的漏洞；符號執(zhí)行在程序的條件分支語句處搜集符號變量的路徑分支條件（路徑約束條件）。在一次執(zhí)行完之后，根據(jù)搜集到的約束條件形成一個約束表達式，對這些表達式按照路徑搜索算法將其中某個條件取反，調(diào)用約束求解器進行求解，從而生成新的測試用例。然后新的測試用例會沿不同路徑進行下一次執(zhí)行過程，如果在執(zhí)行過程中檢測到漏洞，則將記錄漏洞信息并保存相應測試用例。符號執(zhí)行過程將一直繼續(xù)直到所有可能的執(zhí)行路徑都被測試完。

漏洞發(fā)掘方式可以分為被動式和主動式，傳統(tǒng)的漏洞發(fā)掘方式大多都是被動式。被動式漏洞發(fā)掘指的是當某個測試用例觸發(fā)了軟件漏洞，那么該軟件漏洞就被挖掘出來；而主動式漏洞發(fā)掘是指測試用例本身沒有觸發(fā)漏洞，但在執(zhí)行過程中，通過某種方法產(chǎn)生了約束，通過求解該約束，產(chǎn)生新的測試用例，而該新測試用例能夠觸發(fā)漏洞。被動式漏洞發(fā)掘適合檢測路徑不變的漏洞，而對于路徑變化的漏洞，則需采用主動式的檢測方式。

路徑搜索算法是動態(tài)符號執(zhí)行過程中一個重要的組成部分，路徑搜索的目的是實現(xiàn)高的代碼覆蓋率，保證執(zhí)行過程能夠遍歷程序的所有可能執(zhí)行路徑，從而能夠全面的產(chǎn)生測試用例對程序進行檢測。到目前為止，已出現(xiàn)很多路徑搜索方法可供選擇，如：廣度優(yōu)先搜索、代搜索、隨機搜索、元策略等算法。

但是，傳統(tǒng)的廣度優(yōu)先路徑搜索算法，沒有針對漏洞發(fā)掘進行優(yōu)化。其他的路徑搜索算法（代搜索、隨機搜索等）主要目的是提高代碼覆蓋率，也不是針對漏洞發(fā)掘的。本發(fā)明提出了一種基于代搜索算法的路徑搜索算法優(yōu)化方法，標記每次觸發(fā)漏洞的路徑與深度。對于每一個新的測試用例，我們計算該用例執(zhí)行路徑與上次觸發(fā)漏洞路徑的相似度r，并以此計算該路徑的權重分數(shù)score，在下次執(zhí)行測試時選擇執(zhí)行score值最大的測試用例，以減少測試中漏洞觸發(fā)需要的時間，使測試能夠在更短的時間內(nèi)發(fā)現(xiàn)更多的漏洞。

在利用符號執(zhí)行進行漏洞檢測時，傳統(tǒng)路徑搜索算法側(cè)重于路徑搜索，是通用的高代碼覆蓋率路徑搜索算法，不是針對漏洞發(fā)掘的路徑搜索算法；同時，傳統(tǒng)路徑選擇算法沒有利用觸發(fā)漏洞的路徑約束條件，路徑選擇的標準是提高代碼覆蓋率，在路徑選擇時，能夠觸發(fā)漏洞的執(zhí)行路徑可能不一定能優(yōu)先得到執(zhí)行，從而使觸發(fā)漏洞的時間具有一定的隨機性，降低了測試大型軟件漏洞的效率。

發(fā)明內(nèi)容

本發(fā)明的目的在于在傳統(tǒng)代搜索算法的基礎之上，設計了一個改進的路徑搜索方法。一個觸發(fā)漏洞路徑的兄弟路徑，是潛在的在漏洞觸發(fā)路徑。在路徑探索時，記錄每次觸發(fā)漏洞的路徑，對于該路徑的兄弟路徑，在下次執(zhí)行測試時優(yōu)先選擇執(zhí)行，以便更早的對這些區(qū)域進行測試，從而更快的觸發(fā)漏洞，提高大型軟件漏洞檢測的效率。

本發(fā)明為了實現(xiàn)上述目的采用以下技術方案：

一種用于漏洞發(fā)掘的動態(tài)符號執(zhí)行路徑搜索算法，其特征在于：在使用動態(tài)符號執(zhí)行對被測程序的可能執(zhí)行路徑進行搜索的過程中，標記實際執(zhí)行被測程序時觸發(fā)漏洞的路徑，對于路徑探索過程中生成的每一個新的測試用例，計算該測試用例執(zhí)行路徑與上次觸發(fā)漏洞路徑的相關度r，并以此計算該測試用例對應執(zhí)行路徑的權重分數(shù)score，在下次執(zhí)行測試時選擇score值最大的測試用例執(zhí)行。?

上述技術方案中，所述的路徑搜索具體步驟為：

2-1、給出一個初始測試輸入作為測試用例；

2-2、將初始測試輸入加入符號執(zhí)行工作集，并初始化該初始測試輸入的路徑權重分數(shù)為0；