[發明專利]一種基于擴展有限狀態機模型的測試用例生成方法及平臺

在審

• 申請號: 202110282059.4
• 申請日: 2021-03-16
• 公開（公告）號: CN113157562A
• 公開（公告）日: 2021-07-23
• 發明（設計）人: 王軼昆;王軼辰;曹志欽
• 申請（專利權）人: 王軼昆;北京賽若科技有限公司
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06N3/12
• 代理公司: 北京風雅頌專利代理有限公司 11403
• 代理人: 王剛

1.一種基于擴展有限狀態機模型的測試用例生成方法，其特征在于，包括：

對基于需求生成的擴展有限狀態機模型，定義并設計獨立路徑覆蓋準則；

分別通過基于廣度優先搜索算法的有限狀態機模型序列生成方法和基于遺傳算法的有限狀態機模型測試序列生成方法，生成滿足獨立路徑覆蓋準則的測試序列集；

通過故障注入，對有限狀態機模型的故障傳播路徑進行建模；

滿足所述故障傳播路徑的基礎上，基于多種群遺傳算法的擴展有限狀態機模型測試數據生成方法，生成擴展有限狀態機模型測試數據。

2.根據權利要求1所述的基于擴展有限狀態機模型的測試用例生成方法，其特征在于，所述獨立路徑覆蓋準則包括：

給定一個擴展有限狀態機模型的測試序列集A，用ξ表示A所有序列所包含的遷移集合，t_pi表示第i條序列所包含的遷移，若任意屬于A的測試序列Pi與Pj至少存在一條遷移的區別，即#(ran(Pi-Pj))＝1，A恰好覆蓋擴展有限狀態機模型中的所有遷移，使且且所有遷移至少組合一次，則A為擴展有限狀態機模型的獨立路徑覆蓋準則；

其中，#表示集合長度操作符號，ran表示值域操作符號，n表示測試序列的數目。

3.根據權利要求1所述的基于擴展有限狀態機模型的測試用例生成方法，其特征在于，所述基于廣度優先搜索算法的有限狀態機模型序列生成方法包括：

至少引入一個新遷移的測試定義序列為擴展有限狀態機模型中獨立路徑；

通過增加判斷條件的廣度優先搜索算法為擴展有限狀態機模型生成測試序列，所述廣度優先搜索算法包括，

A1初始化擴展有限狀態機模型，輸入起點Vs，終點Vd，將起點Vs的子節點加入至搜索隊列中；

A2從隊列中取出第一個節點，若隊列不為空，轉A3，否則轉A6；

A3判斷節點是否為終點，若是獲取該路徑，并轉A4，否則轉A5；

A4判斷該路徑是否為獨立路徑，若是添加至路徑集S’，并轉A5，否則刪除該路徑；

A5將該節點的子節點添加至搜索隊列；

A6判斷路徑集S’是否滿足獨立路徑覆蓋，若是輸出最終路徑集S，否則轉到A2。

4.根據權利要求3所述的基于擴展有限狀態機模型的測試用例生成方法，其特征在于，所述基于遺傳算法的有限狀態機模型測試序列生成方法包括：

B1擴展有限狀態機模型，輸入起點Vs，終點Vd，將廣度優先搜索算法生成的所有路徑作為遺傳算法的初始種群；

B2計算種群中每個個體的適應度值其中Pi表示第i個測試序列，z表示已有生成的測試序列數目，N表示測試序列Pi與已有的測試序列Tn相同的遷移數目，Tn表示已有生成的測試序列；

B3對種群中的個體進行選擇、交叉、變異，形成新的種群；

B4判斷種群是否滿足獨立路徑覆蓋或達到最大迭代次數，若是輸出最終結果，否則回到B3。

5.根據權利要求1所述的基于擴展有限狀態機模型的測試用例生成方法，所述故障傳播路徑的生成方法包括：

將故障相關比值最大的路徑作為故障傳播路徑；

所述故障相關比值符合以下公式

其中，N_input表示路徑相關的輸入變量與注入故障相關的輸入變量相同的個數，N_output表示路徑相關的輸出變量與注入故障相關的輸出變量相同的個數，t_num表示與注入缺陷相關的輸入輸出變量的個數，k1，k2是修正系數。