[發明專利]一種用于漏洞發掘的動態符號執行路徑搜索方法

有效

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

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

2.?根據權利要求1所述的一種用于漏洞發掘的動態符號執行路徑搜索算法，其特征在于：所述的路徑搜索具體步驟為：

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

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

2-3、用初始測試輸入作為測試用例實際執行測試程序，查看初始測試用例是否觸發漏洞；

2-4、如果符號執行工作集不為空，從符號執行工作集中選擇一個路徑權重分數最大的測試用例，如果有相同分數的，隨機選擇；首次執行選擇初始測試輸入；如果符號執行工作集為空，則結束；??????

2-5、對選擇的測試用例進行符號執行，獲得新的子測試輸入集；

2-6、如果獲得的子測試輸入集不為空，從子測試輸入集中隨機選擇一個測試用例，跳轉至步驟2-7執行；如果獲得的子測試輸入集為空則跳轉至步驟2-4；?????

2-7、對于步驟2-6選擇的測試用例，實際執行并檢測是否觸發漏洞，并在執行過程中對測試用例進行路徑權重分數計算，執行完畢后加入到符號執行工作集中，并從子測試輸入集中刪除，跳轉至步驟2-6。

3.?根據權利要求1所述的一種用于漏洞發掘的動態符號執行路徑搜索算法，其特征在于，符號執行的過程如下：

3-1、首先將生成的子測試輸入集初始化為空集；

3-2、以步驟2-4中選擇的測試用例作為程序輸入，符號執行該測試程序，首先獲取測試程序當前指令，依據指令類型的不同，進行不同的符號執行操作，同時進行漏洞檢測，如果觸發程序漏洞，則標記當前程序的執行路徑的父路徑，將從程序入口處到觸發漏洞處形成的一條程序路徑視為父路徑，記錄路徑深度，并搜集路徑約束，如果沒有觸發漏洞，則僅搜集路徑約束條件；

3-3、對于搜集到的路徑約束條件，逐一進行約束取反；

3-4、調用求解器對約束表達式進行求解，生成后續的測試輸入；

3-5、將后續的測試輸入加入到子測試輸入集中。

4.根據權利要求1所述的一種用于漏洞發掘的動態符號執行路徑搜索算法，其特征在于：上述路徑權重分數計算方法如下：

4-1、初始化第i個測試用例所對應的執行路徑權重分數score（i）為一個初始設定值S_initial=0，第i個測試用例所對應執行路徑的路徑深度d（i）=0，第i個測試用例對應執行路徑的路徑相關度r（i）=R_max，R_max是一個初始設置的路徑最大相關度，代表某條路徑和漏洞觸發路徑的相似度，這里默認相似度為最大值；

4-2、如果程序沒有運行結束，獲取當前程序的執行指令；

4-3、如果指令為條件跳轉類指令，則判斷是否與符號執行相關，相關則將第i條路徑深度d（i）加1，再判斷該指令所屬執行路徑是否為上次觸發漏洞路徑????????????????????????????????????????????????，的父路徑(可能存在多條漏洞路徑，只要該路徑是某一條漏洞路徑的父路徑即可)，如果不是則將r(i)減1，然后計算路徑權重分數，計算公式如下：，vul_path為預設的一個漏洞路徑權重；如果d（i）大于該路徑的觸發漏洞路徑深度,執行步驟4-2所述的當前程序的執行指令后跳轉至4-4，否則執行步驟4-2所述的當前程序的執行指令，跳轉至4-2；

4-4、返回權重分數score，執行完程序后續指令。