Deriving checking sequences for nondeterministic FSMs

Abstract

Most FSM based methods for test derivation are developed for initialized Finite State Machines (FSM) and the latter means that a reliable reset is assumed in an implementation under test in order to glue test sequences together. If the reset is rather expensive then the number of test sequences has to be reduced and when it is reduced to a single sequence, this sequence is called a checking sequence. In this paper, a methods is proposed for deriving an adaptive checking sequence when the specification FSM is nondeterministic and the conformance relation is the reduction relation. The latter means that the behavior of a conforming implementation should be contained in the behavior of the specification. A method returns an adaptive checking sequence that detects each nonconforming implementation that has not more states than the specification FSM under the conditions that the specification has a distinguishing sequence and a deterministic strongly connected submachine. These conditions can be weakened for the case when the specification has a distinguishing test case and each state of the specification is definitely reachable from another state. The testing process is adaptive, i.e., the next input is determined based on the outputs produced for the previous inputs. Such adaptive distinguishing sequences can be shorter than preset checking sequences.