[發明專利]一種基于符號執行的帶反饋測試用例生成方法

有效

• 申請號: 201210219282.5
• 申請日: 2012-06-29
• 公開（公告）號: CN102736979A
• 公開（公告）日: 2012-10-17
• 發明（設計）人: 顧慶;莊元;湯九斌;陳道蓄
• 申請（專利權）人: 南京大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 賀翔

?

技術領域

本發明涉及軟件自動化測試中的測試用例生成，特別涉及在現有測試用例基礎上，應用符號執行方法，通過設定覆蓋目標和選擇種子測試用例，限制約束求解的范圍，以反饋和迭代的方式高效率生成測試用例。

背景技術

在軟件測試過程中，測試用例生成是最重要的環節之一。有效的測試用例生成可以提高測試執行效果，同時降低測試成本和時間。目前測試用例生成基本靠人工來完成，耗時耗力，難以達到理想的程序覆蓋率，因此需要有效的自動化測試用例生成方法。自動化測試用例生成的效果一般由程序覆蓋率來度量，較高的覆蓋率意味著更高的缺陷檢測概率和軟件質量保證能力。一個好的測試用例生成方法能夠以較少的測試用例數量來達到較高的程序覆蓋率。

現有的自動化測試用例生成方法包含三個類別：隨機測試、基于搜索的測試以及符合執行。其中隨機測試方法采用隨機的方式生成測試用例輸入，常生成過多的測試用例，且難以完成對特定程序覆蓋目標的處理；基于搜索的測試方法采用遺傳算法等來達到指定程序路徑的覆蓋，常需要過多的時間來生成測試用例，且受到搜索空間的限制；符號執行方法采用符號變量來執行程序，通過求解約束表達式來達到程序覆蓋目標；在面對較大規模程序時，常遇到約束條件爆炸問題，在現有約束求解技術下難以完成復雜約束表達式的求解。

發明內容

本發明的主要目的是針對傳統自動化測試用例生成方法不能獨立完成自動化測試用例生成任務的問題，提出一種基于符號執行的帶反饋測試用例生成方法，以反饋和迭代的方式，通過收集程序覆蓋信息，設定覆蓋目標，限制符號執行中約束求解的范圍，高效率生成測試用例。

為實現本發明所述目的，本發明采用如下的步驟：

1）執行已有的測試用例并收集測試用例覆蓋信息；確定每個測試用例在執行時覆蓋的被測程序中的語句塊，一個語句塊指在任何程序輸入下，執行情況都相同的一組語句；匯總所有測試用例所覆蓋的語句塊，確定被測程序中尚未覆蓋的語句塊集合；

2）根據被測程序的控制流圖確定符號執行的覆蓋目標；覆蓋目標是被測程序中尚未覆蓋的某個語句塊；

3）對被測程序插樁，植入引導符號執行的控制代碼；控制代碼包括標記語句和判定語句；

4）從已有測試用例集中選擇合適的種子測試用例，用于啟動符號執行方法；

5）針對覆蓋目標應用符號執行方法生成新的測試用例；將新生成的多個測試用例補充到已有的測試用例集合中。

上述5個步驟迭代執行，直至達到給定的測試用例生成目標。

上述步驟2）中根據被測程序控制流圖確定符號執行覆蓋目標的處理過程是：首先根據代碼控制結構，將被測程序語句塊組織成控制流圖?，圖中的節點對應語句塊，邊代表語句塊執行順序；識別被測程序中每個函數/過程/方法中處于最高層次的子樹，定義為上層子樹；然后尋找覆蓋率最低的函數/過程/方法（通過補充已有測試用例使其至少部分覆蓋），在其對應的控制流圖中確定第一個沒有充分覆蓋的上層子樹；最后選擇該上層子樹中第一個沒有被覆蓋的語句塊（對應非控制節點）作為本次符號執行的覆蓋目標。

上述步驟3）中被測程序插樁以植入引導符號執行的控制代碼的處理過程是：首先確定覆蓋目標所在的函數/過程/方法，在其起始位置插入判定變量定義語句，判定變量的初值置為“false”；然后在覆蓋目標之前的位置插入判定變量賦值語句，將判定變量賦值為“true”；最后確定覆蓋目標所處的上層子樹，在上層子樹之后的位置插入控制符號執行的判定語句；在符號執行中，判定語句根據判定變量的取值決定是否繼續補充約束條件以求解更復雜的約束表達式。

上述步驟4）中從已有測試用例集中選擇種子測試用例的處理過程是：首先從已有測試用例中篩選覆蓋了步驟2中覆蓋目標的父節點的所有測試用例；令控制流圖中覆蓋目標所對應的節點為，父節點是中位于節點之前且直接與相連接的節點（按步驟2中的處理方式，父節點有且僅有一個）；然后從這些測試用例中篩選對覆蓋目標所處之上層子樹的覆蓋程度最高的測試用例；最后在剩余的測試用例中選擇覆蓋語句塊總數最少的測試用例作為種子測試用例。