Adaptive Testing of Nondeterministic Systems with FSM

The paper addresses the problem of testing systems considered as black boxes and modelled by Finite State Machines (FSM). While the theory of testing from deterministic FSMs has received a lot of attention, testing from nondeterministic machines is not yet investigated to the same extend. The paper is devoted to the problem of generation of adaptive test cases for nondeterministic specification FSMs to obtain complete, i.e., sound and exhaustive, test suites. Such tests verify that an implementation conforms to its specification, when the conformance relation is the reduction (trace inclusion) relation. A method for deriving a complete test suite is proposed. In case, when the implementation under test is also nondeterministic, each test case is adaptively executed a predefined number of times ensuring that all nondeterministic choices were taken. Comparison with the existing approaches indicates that the method has several advantages.