Adaptive Executable Test Sequences Generation from an Extended Finite State Machine

Automatic test sequences generation using the extended finite state machine (EFSM) model can improve the test efficiency. However, unexecutable test sequences due to the conflicts among the predicates and internal variables of transitions in an EFSM may exist. The existence of unexecutable test sequences increases the difficulties of automatic test sequences generation. How to determine whether a test sequence is executable becomes a challenging problem. In this paper, the intrinsic characteristics and dependence relations among transitions in an EFSM are discussed in detail. Then an adaptive approach to automated executable test sequence generation for EFSM models is proposed, which is based on an adjacency transition dependence graph. In this method, firstly, transitions are classified according to their variables and predicates; Then dependence relationships between any two adjacency transitions can be mined and defined; Finally, executable test sequences are generated through expanding a reachability analysis tree, with the heuristic guidance using an adaptive exploration function. Experimental results show that, compared with the reachability analysis algorithm based on bread-first-search, the proposed method can reduce the number of states explored in the reachability analysis process and relieve the state explosion problem. As a result, the efficiency of automatic executable test sequences generation is improved. In the worst case, time and space complexity of the proposed method is also not more than the bread-first-search algorithm.