[發明專利]一種基于擴展有限狀態機可行路徑分析的測試用例自動生成方法

有效

• 申請號: 201110306942.9
• 申請日: 2011-10-10
• 公開（公告）號: CN102368226A
• 公開（公告）日: 2012-03-07
• 發明（設計）人: 楊瑞;陳振宇;徐寶文;張潔
• 申請（專利權）人: 南京大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 黃明哲

技術領域

本發明屬于軟件測試技術領域，尤其是模型測試技術領域，用于擴展有限狀態機(Extended?Finite?State?Machine)中路徑可行性分析，一種基于擴展有限狀態機的自動化測試用例生成方法。

背景技術

軟件測試是軟件發展過程的重要階段，據估計測試花費占整個軟件開發過程的花費的30％-50％。目前測試的方式主要以人工測試為主，人工測試準確性較差，需要花費大量時間和費用。而測試自動化方法可以減少測試過程的代價，提高軟件測試的質量。自動化生成測試用例的一種典型方法是創建軟件的測試模型，并且在模型的基礎上自動化生成測試用例。近年來，隨著面向對象技術的成熟和廣泛應用，基于模型軟件測試方法得到了快速的發展，成為研究的熱點之一，引起了學術界和工業界的廣泛關注。模型驅動的測試方法是在軟件開發過程中通過建立各個級別的模型，在此基礎上進行測試用例的生成、測試用例的執行和測試用例的評估，以檢測軟件中存在的錯誤，驗證實際系統是否符合實際需求，擴展有限狀態機(Extended?Finite?State?Machine)是其中應用最廣泛的模型之一。擴展有限狀態機(Extended?Finite?State?Machine)是由有限狀態機(Finite?State?Machine)擴充而來，有限狀態機模型只能表達實際應用的控制流部分而擴展有限狀態機則既可以表達控制流也可以表達數據流部分，描述復雜的應用系統更加適合。

目前已有許多基于有限狀態機模型的測試序列生成方法，通用的方法是利用圖論的方法遍歷有限狀態機，生成測試序列以達到規定的覆蓋。然而利用擴展有限狀態機生成測試用例仍然是一個開放研究課題，擴展有限狀態機中不可行路徑的存在使得傳統的基于有限狀態機的方法不能應用于擴展有限狀態機模型，擴展有限狀態機模型中路徑是否可行是個不可判定問題，目前還沒有相關的有效方法能夠全面檢測擴展有限狀態機模型中存在的不可行路徑。此外對應路徑的測試數據生成和測試預言(oracle)自動化問題也是擴展有限狀態機模型測試的難題，測試預言是用來判定一個被測系統是否正確的一種機制。

基于可行路徑分析的測試用例自動生成技術旨在解決上述問題。該測試用例自動化生成方法通過路徑可行性分析盡可能的避開不可行路徑、自動化的生成測試用例，并且達到規定的測試充分準則。該方法結合了靜態分析和動態分析技術來找到一個較小的可行路徑集合達到指定的路徑覆蓋準則，此外還開發了可執行模型，通過運行時信息反饋和分散搜索(Scatter?Search)技術來直接指導測試數據的生成。可執行模型帶來的另一個好處是可以用來自動化的創建測試預言。

發明內容

本發明要解決的問題是：通過路徑可行性分析識別部分不可行路徑，并盡可能的避開其余的具有較高不可行概率的路徑，自動化生成路徑對應的測試數據和的創建測試預言，大大提高測試用例生成的效率。

本發明的技術方案為：一種自動化測試用例生成方法，基于擴展有限狀態機可行路徑分析，通過路徑可行性分析盡可能的避開不可行路徑，自動化生成測試用例和創建測試預言，結合靜態分析和動態分析技術獲取可行路徑集合達到指定的路徑覆蓋準則，包括以下步驟：

1)根據擴展有限狀態機模型生成測試路徑候選集，利用遍歷、循環路徑分析和插入方法，生成從擴展有限狀態機模型的起始狀態結點到其他結點的所有路徑作為候選路徑，并約束規定路徑中只插入有限次循環路徑或自循環路徑；

2)路徑可行性評估策略，利用靜態分析技術對候選路徑集中的路徑進行分析，首先識別出其中不可行路徑，將這部分不可行路徑從路徑候選集中移除，然后對其余路徑的可行性提出評估公式，對其進行不可行概率評估并計算出評估值，對候選路徑集中的路徑按不可行概率從小到大進行排序；

3)開發可執行模型，利用圖論遍歷方法和表達式語義解析工具使得擴展有限狀態機模型可執行化，可執行模型定義了模型的動態行為并通過使用語義執行使得靜態模型具有類似程序的動態執行能力；

4)自動生成測試數據和測試預言，由步驟3)的可執行模型的動態執行過程獲得相應的運行時反饋信息，利用所述反饋信息結合分散搜索技術Scatter?Search來指導測試數據生成并自動創建測試預言，生成的測試用例觸發對應的路徑；