Synchronizable test sequence generation for protocol conformance testing.

Abstract

This study addresses the synchronization problem that arises during the application of a predetermined test sequence in some test architectures used for protocol conformance testing. A solution to this problem is to construct synchronizable test sequences. For FSM-based protocol specifications, a necessary and sufficient condition is given for the existence of a synchronizable test sequence for a given FSM. A polynomial time algorithm is then developed to determine the existence of such a sequence for a given FSM. A duplex digraph method is developed which transforms the order-specified digraph representing an FSM into a duplex digraph. Using the duplex digraph representation of a given FSM, a polynomial time algorithm is developed to generate a synchronizable test sequence for the FSM which checks only the output function of the FSM. The W-, D- and UIO-methods are extended to an FSM represented by an order-specified digraph by employing synchronizable W-sets, synchronizable DS sequences and synchronizable UIO sequences, respectively. Polynomial time algorithms are then developed to generate synchronizable test sequences for a given FSM which check the transfer function as well as the output function.