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

有效

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

技術領域

本發明涉及對符號執行過程進行指導以提高其效率的方法，屬于軟件測試技術領域。

背景技術

軟件測試是一種重要的軟件可靠性保證方法，在實踐中被廣泛運用。傳統的軟件測試方法（例如隨機測試或人工測試）盡管有效，但在某些情況下效率較低，無法滿足日益增長的軟件開發需求。

符號執行也是一種經典的程序測試和分析技術。使用符號執行方法，人們可以自動的，系統化的探索程序的執行空間，同時產生擁有高覆蓋度的測試用例集。

符號執行的過程中，用符號值替代了輸入參數的實際值。在程序執行的過程中，當執行遇到分支時，執行會復制相關的執行狀態，使得符號執行可以走向分支的兩個方向，并且記錄下相應方向中與輸入的符號參數相關的約束條件。之后符號執行選擇合適的分支方向，繼續對應的執行。當某個執行達到程序出口或者發現錯誤時，符號執行利用約束求解器求解該執行對應的路徑上記錄的約束條件，以得出符合該執行的輸入的實際值，并輸出相關的測試用例。這樣，重放該測試用例，可以得到和符號執行相同的執行效果。由于符號執行是根據路徑計算相應的測試用例輸入，因此一個用例可以對應相應的一組測試用例集合，有效的避免冗余用例，提高了測試的效率。

在實際應用中，由于大量的分支組合以及循環，遞歸的存在，使得程序中的路徑數目極大甚至無窮。因此，在實際運用中，符號執行的一個關鍵問題在于如何指導執行的過程使其能夠探索程序中更加有用的部分。關于這一問題，各種方法被提出以指導或優化符號化探索程序的過程，但是這些方法或者針對特殊情況或者效率不高。

發明內容

技術問題：本發明的目的指導符號執行的過程，將其導向程序中探索較少的部分，使其能夠更好的覆蓋程序并且盡可能的發現程序中的錯誤，有效地解決符號執行效率問題。

技術方案：本發明引入路徑片段頻譜的概念，不同的路徑片段頻譜從各個角度分析程序執行的行為，以獲得不同層次的程序行為分析，構成程序行為的框架。本發明還根據已探索部分的路徑片段頻譜分析當前符號執行的行為，用以指導符號執行探索程序中探索較少的部分。

本發明所述的基于路徑片段頻譜的符號執行搜索方法具體流程如下：

步驟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。

有益效果：本發明所述的基于路徑片段頻譜的符號執行策略，可以有效的指導符號執行探索當前狀態下程序中探索較少的部分。具體說來，本發明所述的方法具有如下有益效果：

（1）本發明所述的基于路徑片段頻譜的符號執行搜索策略，可以調整路徑片段的長度以獲得不同的測試精度，能夠根據不同的程序系統或用戶的需求調整。

（2）本發明所述的基于路徑片段頻譜的符號執行搜索策略，有效的利用了符號執行過程中的已執行部分，能夠根據已經執行的上下文信息指導符號執行的過程，使其能夠產生覆蓋度更高的測試用例。