A heuristic transition executability analysis method for generating EFSM-specified protocol test sequences

Automatic executable test sequence generation is a challenging task for protocol test based on the Extended Finite State Machine (EFSM) model. Transition executability analysis (TEA) can guarantee the executability of generated test sequences. However, as a reachability analysis technique, it often suffers from the state explosion problem. To remedy the situation, this paper proposes a heuristic transition executability analysis (HTEA) method for compressing the explored state space during test sequences derivation. In our approach, a transition feasibility guidance matrix is first constructed through extracting the inherent constraint relationship between each adjacent transitions in the EFSM under testing. Then, relying on the built matrix and related runtime feedback, we define an objective function to dynamically evaluate state nodes in the HTEA expanding tree. Finally, the proposed objective function is utilized to heuristically guide the state space traversal in the HTEA tree for executable test sequences generation. Consequently, the executable test generation problem can be reformulated into a multi-objective search problem based on a HTEA tree. Experimental results impressively show the potential of the novel method for avoiding the state explosion during test generation, compared with the classic TEA technique in the breath-first way.