SYNCHRONIZABLE TEST SEQUENCES OF FINITE-STATE MACHINES

The finite state machine (FSM) model is commonly used for specifying c ommunication protocols and other types of distributed systems. For an FSM with multiple ports, multiple testers are needed, but the synchron ization between inputs from different testers becomes a problem. A syn chronizable test sequence of an FSM is a test sequence for which the s ynchronization problem either does not exist or can be solved by commu nication between testers. In this paper, we consider two testing strat egies for an FSM: port-based resting, which does not allow testers for the FSM to communicate with each other, and group-based testing, whic h divides ports of the FSM into mutually disjoint groups and allows te sters for ports in the same group to communicate with each other. For each type of testing, we define a necessary and sufficient condition u nder which a test sequence of an FSM is synchronizable and show how to generate a set of testers according to a given test sequence. We also discuss test sequence generation and fault detection, and present the results of empirical studies. (C) 1998 Elsevier Science B.V. All righ ts reserved.