An extended framework for passive asynchronous testing

- A formal framework to passively test systems with asynchronous communications.
- A generalised format to represent properties.
- Efficient algorithms: exponential in the size of the property vs polynomial in the size of the trace.

In passive testing a monitor observes the trace (sequence of inputs and outputs) of the system under test (SUT) and checks that this trace satisfies a given property P, potentially triggering a response if an incorrect behaviour is observed. Recent work has explored a variant of passive testing, in which we have a required property P of the traces of the SUT and there is a first-in-first-out (FIFO) network between the SUT and the monitor. The problem here is that the trace observed by the monitor need not be that produced by the SUT. Previous work has shown how such asynchronous passive testing can be performed if the property P is defined by a pair (ρ,Oρ) that represents the requirement that if trace ρ is produced by the SUT then the next output must be from the set Oρ. This paper generalises the previous work to the case where the property P is defined by a finite automaton.