Combining centralised and distributed testing

Abstract

Many systems interact with their environment at distributed interfaces (ports) and sometimes it is not possible to place synchronised local testers at the ports of the system under test (SUT). There are then two main approaches to testing: having independent local testers or a single centralised tester that interacts asynchronously with the SUT. The power of using independent testers has been captured using implementation relation $\dioco$. In this paper we define implementation relation $\diococ$ for the centralised approach and prove that $\dioco$ and $\diococ$ are incomparable. This shows that the frameworks detect different types of faults and so we devise a hybrid framework and define an implementation relation $\diocos$ for this. We prove that the hybrid framework is more powerful than the distributed and centralised approaches. We then prove that the Oracle problem is NP-complete for $\diococ$ and $\diocos$ but can be solved in polynomial time if we place an upper bound on the number of ports. Finally, we consider the problem of deciding whether there is a test case that is guaranteed to force a finite state model into a particular state or to distinguish two states, proving that both problems are undecidable for the centralised and hybrid frameworks.