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

有效

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

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

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

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

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

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

測試用例的生成過程為：首先從步驟1)和步驟2)生成的測試路徑候選集中按不可行概率順序選取一條候選路徑，檢查該路徑中的邊是否被指定的測試充分性準則覆蓋，若是則跳過該路徑選取候選集中的下一條路徑進行生成，以避開不可行路徑，提高測試用例生成的效率，同時動態識別不可行路徑；否則利用步驟3)開發的可執行模型和步驟4)獲取的運行時反饋信息，結合分散搜索方法Scatter?Search，對選擇的路徑進行語義執行，并利用反饋信息搜索狀態空間中的解，若在規定迭代次數范圍內找到解集則將結果加入測試用例結果集，否則認為該路徑不可執行。

2.根據權利要求1所述的一種自動化測試用例生成方法，其特征是步驟1)具體為：首先利用圖論的遞歸遍歷算法找出從擴展有限狀態模型源結點到其他所有結點間的所有簡單狀態路徑，所述簡單狀態路徑由狀態序列構成，且路徑中不含循環；并識別出擴展有限狀態機模型中所有的狀態循環路徑，所述狀態循環路徑由狀態序列構成，源結點和終止結點相同，包括自循環路徑；檢查簡單狀態路徑，檢查其實是否有能和狀態循環路徑匹配的結點，若是，則將狀態循環路徑插入簡單路徑，生成狀態路徑候選集；再利用全組合方法將狀態路徑轉換為遷移路徑集合，并將生成的遷移路徑集合作為最終的測試路徑候選集。