[發明專利]基于路徑片段頻譜的符號執行搜索方法

有效

• 申請號: 201410055286.3
• 申請日: 2014-02-18
• 公開（公告）號: CN103870391A
• 公開（公告）日: 2014-06-18
• 發明（設計）人: 李游;王林章;李宣東;陳志
• 申請（專利權）人: 南京大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 楊曉玲

1.一種基于路徑片段頻譜的符號執行搜索方法，其特征在于該方法所包含的步驟為：

步驟1、測試人員設定待測試的源代碼程序的路徑片段的長度，所述源代碼程序的路徑片段是指源代碼程序對應的程序控制流圖中一組連續的選擇分支節點和執行方向所構成的路徑，所述路徑片段的長度是指其中選擇分支節點的個數；

步驟2、利用路徑片段頻譜信息指導符號執行的過程

對待測試的源代碼程序進行符號執行過程，在此過程中，記錄或更新已執行的指定長度的路徑片段頻譜，選擇已執行次數較少的路徑片段繼續符號執行；

所述路徑片段頻譜是由指定長度的所有不同路徑片段在符號執行過程中已執行的次數所組成列表；

所述符號執行是指使用符號變量代替具體變量，不執行程序的前提下模擬程序執行來進行相關測試分析的技術，一般與約束滿足問題求解方法一同使用；

步驟2的具體過程如下：

步驟2.1、逐條模擬執行程序語句，若執行過程遇到選擇分支語句，則進入步驟2.2；若執行過程發現錯誤或到達程序出口，進入步驟2.5；

步驟2.2、產生一個新的程序執行，復制當前執行的狀態，將兩個執行分別指向選擇分支語句的兩個方向，并將這兩個執行掛起，進入步驟2.3；

步驟2.3、獲取步驟2.2產生的兩個執行的對應的路徑片段，若路徑片段未被執行，則在路徑頻譜中加入該路徑片段，記錄其已執行次數為0，結束后進入步驟2.4；

步驟2.4、從所有掛起的執行中選擇對應的路徑片段已執行次數最少的一個，若執行次數最少的掛起執行不唯一，則在其中隨機選擇一個，將其對應的路徑片段已執行次數加1，回到步驟2.1；若沒有掛起的執行，則結束步驟2；

步驟2.5、根據當前的發現錯誤或到達程序出口的執行，計算其對應的程序輸入，并結束該執行，進入步驟2.4。