Applying adaptive test cases to nondeterministic implementations

摘要

In testing we observe traces of the SUT. If we can deduce that all traces that the SUT can produce in response to an adaptive test case γ have already been observed then we know that we do not have to apply γ. If this is the case then we can reduce the cost of test execution. Previous work has considered the case when the SUT is known to be deterministic and we extended this by investigating the situation in which the SUT could be nondeterministic. We started with the case where we can apply a fairness assumption. We then weakened this assumption to there being a lower bound p on the probability of observing alternative responses of the SUT to any input and in any state. We then considered the general case. In all three cases we showed how the problem can be solved in low-order polynomial time. Since it is sometimes possible to deduce that all possible responses to an adaptive test case γ have already been observed in testing, the expected cost of testing depends upon the order in which we apply the adaptive test cases. This leads to the question of how we can minimise the expected cost of testing. This problem has been considered for a deterministic SUT and there are algorithms for producing preset orders and for applying the adaptive test cases on the fly. Future work will investigate how these approaches can be extended to a nondeterministic SUT.