Applying adaptive test cases to nondeterministic implementations

Abstract

The testing of a state-based system involves the application of sequences of inputs and the observation of the resultant input/output sequences (traces). These traces can result from preset input sequences or adaptive test cases in which the choice of the next input depends on the trace that has observed up to that input. Adaptive test cases are used in a number of areas including protocol conformance testing and adaptivity forms the basis of the standardised test language TTCN. Suppose that we apply adaptive test case ° to the system under test (SUT) and observe the trace ¯¾. If the SUT is deterministic and we apply ° again, after resetting the SUT, then we will observe ¯¾ again. Further, if we have another adaptive test case °0 where a prefix ¯¾0 of ¯¾ is a possible response to °0 then we know that the application of °0 must lead to ¯¾0. Thus, for a deterministic SUT the response of the SUT to an adaptive test case °0 might be deduced from the response of the SUT to another adaptive test case. This observation can be used to reduce the cost of testing: we only apply adaptive test case °0 if we cannot deduce the response to °0 from the set of observations. While many systems are deterministic, nondeterminism is becoming increasingly common. Nondeterminism in the SUT is typically a consequence of limits in the ability to observe the SUT. For example, it could be a result of information hiding, real time properties, or of different possible interleavings in a concurrent system (see, for example. This paper investigates the case where the SUT is nondeterministic. We consider the situation in which a set O of traces has been observed in testing and we are considering applying an adaptive test case °. In general we cannot expect to be able to deduce the response of a nondeterministic SUT to an adaptive test case ° since there may be more than one possible response. Instead we consider the question of how we can decide whether the application of ° could lead to a trace that has not been observed. A solution to this would allow us to reduce the cost of testing: if all possible responses of the SUT to ° have already been observed then we do not have to apply ° in testing and thus reduce the cost of test execution. This paper considers three cases. Section 3 considers the case where we can apply a fairness assumption. Section 4 weakens this assumption to us having a lower bound p on the probability of observing alternative responses of the SUT to any input and in any state. Section 5 then considers the general case.