Many systems have an internal state at any given time. Statecharts (UML) can be used to specify these systems and the state changes that occur. Most Object-Oriented (OO) systems will have encapsulated states which are not easily visible so these states need to be tested.

A state-based model of a system will include states and transitions between states. States are represented by nodes in a statechart.

To test a transition, the initial state from which that transition occurs needs to be known. The final state after the transition has occurred also needs to be known.

FSM Testing

Testing from a Finite State Machine involves comparing the Implementation Under Test (IUT) to the FSM in terms of the transitions and associated output that should occur. Because of FSM testing being a typically black-box style of testing, the actual internal state of the IUT is not always easily visible. Because of this, the problems of Controllability and Observability come into play.

Controllability is the ability to ensure that the correct start state for a test exists. Observability refers to the ability to see the final state of the IUT after a test has been run. Checking the final state of a transition can be done using several methods which use the following concepts:

- Distinguishing Sequence (DS)
- Unique Input/Output Sequence (UIO)
- Characterising Set

Distinguishing Sequence (DS)

A Distinguishing Sequence is an input sequence which produces a unique output for each state. A DS can therefore be used to distinguish what starting state the system was in. Inputting the DS will result in an output which determines absolutely what the start state was.

Unique Input/Output Sequence (UIO)

A UIO applies to a single state only. Whereas a DS can universally identify any state, a UIO simply distinguishes a single state from all the other states. A UIO for one state therefore cannot be used to identify any state within a system. A DS is therefore more powerful than UIOs but sometimes a DS may not exist for a program / system.

Characterising Set

It may be the case that both a DS and a UIO for each state do not exist. Even so, all minimal FSMs have a characterising set. A characterising set is a set of input values which will identify the state of a system by giving a unique set of output values for each state in the system. This is different to a Distinguishing Sequence because a DS is a sequence of input values which are used one after the other. The input values in a characterising set are all to be used directly after the state / transition being tested has been reached / executed.

To use a characterising set to test a transition, resets must be used. A test "preamble" is used to get the system state to the desired initial state of the test. Then an input is used to trigger the transition being tested. Following this, one of the values from the characterising set is used, the output recorded, and a reset used. This whole process is repeated until all the values within the characterising set have been used. All of the recorded outputs form a set which verifies whether the final state was the correct one.

See Chow's Method for more information on using characterising sets.

Search for "State-Based Testing Verification" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "State-Based Testing Verification" on the rest of Computing Students: State-Based Testing Verification