Generating feasible protocol test sequences from EFSM models using Monte Carlo tree search

Abstract Context: Feasible test sequences generation is a key step in protocol conformance testing based on the Extended Finite State Machine (EFSM) model. To guarantee the feasibility of generated test sequences, transition executability analysis (TEA) technique is widely applied in automatic test derivation. However, the TEA method often suffers from the famous state explosion problem, which has become a major obstacle to its efficient application. Objective: In order to mitigate this issue, this paper proposed a novel heuristic TEA method (MTEA) that uses Monte Carlo tree search (MCTS) to guide the TEA tree expansion for efficiently deriving feasible test sequences. Method: The approach first provides a framework to apply the MCTS algorithm based on multiple decision subtrees, in the context of test sequence generation for EFSM-specified systems, to more efficiently expanding the TEA tree with huge state space, and thus alleviating the problem of state explosion. To achieve this, we then design a reward function to calculate the fitness of nodes currently being expanded in the TEA tree and heuristically direct the search towards a near-optimal solution. Next, an adaptive reduction mechanism of search budget is also introduced to accelerate the convergence of the analysis. Finally, a MTEA-based algorithm for automatically generating feasible test sequences is presented under a specific transition coverage criterion. Results: A detailed case study on 6 popular EFSMs was carried out to evaluate the effectiveness and efficiency of our method. Experimental results show that the MTEA significantly outperforms Breadth-First-Search based TEA method (BTEA) and the standard MCTS-based method (SMCTS), regarding time and space performance. Compared with the BTEA, SMCTS and random TEA method (RTEA), the success rate of test generation of MTEA (98.14% on average) is approximately 2, 1.85 and 3 times higher, respectively. For successful test derivation, MTEA only needs to explore on average 9.95% of the nodes and consume on average 61.68% of the runtime of the BTEA method. Conclusion: The experiments illustrate the promise of our approach for alleviating the state explosion problem in test generation for EFSM-specified systems.