Testing from a state based specification

Many systems have some internal state that affects and is affected by operations of the system. Such systems are typically specified using state based languages such as Statecharts, SDL, and X-machines. Systems specified using such languages may be tested by applying methods based on deterministic finite state machines (DFSMs) or non-deterministic finite state machine (NFSM). These test techniques are usually applied after the specification has been converted into a DFSM or NFSM by either expanding out the data (possibly after putting bounds on the types) or by applying some abstraction.

The widespread use of state based systems, and the importance of their correctness, has led to much interest in testing from DFSMs and NFSMs. Non-determinism in the specification is not unusual. Typically this comes either from some abstraction that has been applied or there being a number of acceptable behaviours in response to some input sequence. However, most work has focused on testing from DFSMs rather than NFSMs.

When testing from an FSM M it is usual to assume that the implementation under test (IUT) behaves likes some unknown element of a given fault model. Usually this fault model is the set, F, FSMs with the same input and output alphabets as M and no more than $m$ states (some predetermined m). Then a test suite is a checking experiment if and only if it distinguishes every element of F, that does not conform to M, from M. Ideally, the test suite used is a checking experiment but this is not always feasible - in such cases we typically produce a test sequence that tests each transition of M.

Work in this area has considered a number of problems including the following.

Back to Rob Hierons' home page

Last updated: June 2010.

Disclaimer The contents of this page falls outside the responsibility of Brunel University.