Many systems have some persistent internal state and operations that act on this state. Such systems are often specified using a state-based language such as Statecharts or SDL. The existence of an internal state creates a number of issues in testing, such as the necessity to set up the state for a test (the controllability problem) and to check the state after the test (the observability problem).
The testing of a state-based system requires the use of sequences of inputs. These sequences can result from applying adaptive test cases in which the input applied at a step depends upon the output sequence that has been observed. A finite adaptive test case can be represented by a tree. The use of adaptive tests cases is often essential where the specification is either nondeterministic or incomplete and may be useful where we wish to have robust tests; tests that may achieve their test purpose (such as testing a particular transition) even if there is an earlier failure. Further, TTCN test cases are adaptive test cases. One area of research has been the generation of adaptive test cases for use when testing against a state-based specification.
An alternative approach to the adaptive testing of a deterministic system against a non-deterministic finite state machine M involves two phases. Here an initial phase of testing produces a candidate C: a deterministic finite state machine that has the property that if the implementation under test is correct then it must be equivalent to C. We then apply a second phase in which we test the implementation under test against C using standard techniques for testing against a deterministic finite state machine.
When testing a deterministic system, it is possible for the response of the system to one adaptive test case t1 to fully determine the response of the system to another adaptive test case t2. Further, this could be the case even if the response to t1 is not guaranteed to determine the response to t2 in which case we cannot simply eliminate t2 from our test suite without potentially reducing its effectiveness. When this is the case it seems sensible to apply t1 before t2. We thus see that the cost of apply a test suite composed of adaptive test cases depends upon the order in which we apply them. While the problem of finding the order that minimises the expected cost of testing is NP-hard, certain sensible things can be done in low order polynomial time.
Back to Rob Hierons' home page
Last updated: 30 April 2009.