Oracles for Distributed Testing

The problem of deciding whether an observed behavior is acceptable is the oracle problem. When testing from a finite state machine (FSM), it is easy to solve the oracle problem and so it has received relatively little attention for FSMs. However, if the system under test has physically distributed interfaces, called ports, then in distributed testing, we observe a local trace at each port and we compare the set of local traces with the set of allowed behaviors (global traces). This paper investigates the oracle problem for deterministic and nondeterministic FSMs and for two alternative definitions of conformance for distributed testing. We show that the oracle problem can be solved in polynomial time for the weaker notion of conformance (⊆_w) but is NP-hard for the stronger notion of conformance (⊆), even if the FSM is deterministic. However, when testing from a deterministic FSM with controllable input sequences, the oracle problem can be solved in polynomial time and similar results hold for nondeterministic FSMs. Thus, in some cases, the oracle problem can be efficiently solved when using ⊆_s and where this is not the case, we can use the decision procedure for ⊆_w as a sound approximation.