[發明專利]基于蒙特卡洛樹搜索的EFSM可執行測試序列生成方法

有效

• 申請號: 202010698489.X
• 申請日: 2020-07-20
• 公開（公告）號: CN111934948B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 舒挺;黃業超
• 申請（專利權）人: 浙江理工大學
• 主分類號: H04L43/50
• 分類號: H04L43/50
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 王琛

1.一種基于蒙特卡洛樹搜索的EFSM可執行測試序列生成方法，其特征在于：應用蒙特卡洛樹搜索算法建立EFSM對應的TEA樹，從中找到一條滿足測試覆蓋條件的路徑，該路徑即為可執行測試序列且該路徑及其路徑上每條變遷的輸入、輸出構成一個完整的測試用例；

所述蒙特卡洛樹搜索算法的具體實施方式為：首先建立EFSM對應的TEA樹，所述TEA樹中每個節點即對應一個狀態且節點包含對應的狀態名稱以及整個EFSM的變量；從給定的起始狀態即根節點開始進行搜索，當某個節點存在有多條輸出變遷時，通過計算每條輸出變遷的UCT值，經過對應UCT值最大的輸出變遷搜索到下一個節點，且每經過一條變遷需查看走過的路徑是否已包含所有測試目標變遷，若是則搜索結束，輸出路徑作為可執行測試序列，否則繼續搜索；

所述UCT值的計算表達式如下：

其中：N為當前節點，N'為N的父節點，UCT(N)為節點N與N'之間變遷的UCT值，Q(N)為當前節點N的累計獎勵值，V(N)為當前節點N的被訪問次數，V(N')為父節點N'的被訪問次數，η為給定的權重系數，Δ(N_i)為在對當前節點N進行第i次蒙特卡洛樹搜索過程的模擬仿真階段中終端節點N_i的獎勵值，budget為蒙特卡洛樹搜索的搜索開銷上限，n為TEA樹中當前節點N至根節點路徑上已覆蓋的測試目標變遷數量，|TS|為所要求覆蓋的測試目標變遷數量，|N_i.ω|為在對當前節點N進行第i次蒙特卡洛樹搜索過程中根節點到終端節點N_i的路徑深度，Max為蒙特卡洛樹搜索所設定的最大探索深度，|N.path|為當前節點N到根節點的路徑深度，μ為給定的開銷參數，用于控制budget的縮放。

2.根據權利要求1所述的EFSM可執行測試序列生成方法，其特征在于：所述蒙特卡洛樹搜索算法在繼續搜索的過程中，若超過所設定的最大探索深度Max，仍未找到一條從根節點起覆蓋所有測試目標變遷的路徑，則重新從根節點開始探索或增大最大探索深度Max或增大開銷參數μ。

3.根據權利要求1所述的EFSM可執行測試序列生成方法，其特征在于：該方法將EFSM可執行測試序列生成問題轉化為一個基于TEA樹搜索的馬爾科夫決策過程，并應用蒙特卡洛樹搜索算法進行求解。

4.根據權利要求1所述的EFSM可執行測試序列生成方法，其特征在于：該方法建立了TEA樹和蒙特卡洛樹搜索算法的融合機制，利用蒙特卡洛樹搜索算法來預測TEA樹中節點的擴展合理性，即在每次TEA樹擴展節點時，建立一棵以蒙特卡洛樹搜索方式建立的TEA子樹，利用這棵TEA子樹狀態空間信息選擇更合理的擴展方向。