Probabilistic conformance testing of protocols with unobservable transitions

A probabilistic approach to conformance testing of protocols containing unobservable transitions is proposed. It is said that an implementation conforms to its specification if their observable behavior is probabilistically the same, when both are subject to the same random environment simulated by the tester. Under the randomized inputs, faults in unobservable transitions may manifest themselves in certain statistics measurable from the implementation, and hence can be detected by comparing these measurements against the desirable statistics computed from the specification. The sensitivity of the nonconformance criterion to the uncertainty in our knowledge of desirable statistics is also studied. The conventional testing of protocols without unobservable transitions uses mismatch in outputs to detect faults. Here, one relies, in addition, on mismatch in the dynamics of the protocol under input randomization.