Abstract:

Reachability analysis, which is widely used to generate executable protocol conformance test sequences, often causes state explosion problem. To overcome the problem, a heuristic state configuration exploration method is proposed. Using a weight extend finite state machine as a protocol model, the new method employs the heuristic state configuration exploration to replace the traditional strategy of breadth-first-search. In this way, the generation of executable protocol conformance test sequences is reformulated to find the minimum weight path in the whole state configuration space of a protocol implementation under test . The experiment results show that the proposed method is superior to breadth-first-search algorithm in time and space complexity.

Key words: protocol conformance test, weight extend finite state machine, state configuration, reachability analysis