Passive Testing of Stochastic Timed Systems

In this paper we introduce a formal methodology to perform passive testing, based on invariants, for systems where the passing of time is represented in probabilistic terms by means of probability distributions functions. In our approach, invariants express the fact that each time the implementation under test performs a given sequence of actions, then it must exhibit a behavior according to the probability distribution functions reflected in the invariant. We present algorithms to decide the correctness of the proposed invariants with respect to a given specification. Once we know that an invariant is correct, we check whether the execution traces observed from the implementation respect the invariant. In addition to the theoretical framework we have developed a tool, called PASTE, that helps in the automation of our passive testing approach. We have used the tool to obtain experimental results from the application of our methodology.