On testing hierarchies for protocols

The authors consider a protocol specification represented as a fully specified Mealy automata, and the problem of testing an implementation for conformance to such a specification. No single sequence-based test can be completely reliable, if one allows for the possibility of an implementation with an unknown number of extra states. They define a hierarchy of test sequences, parameterized by the length of behaviors under test. For the reset method of conformance testing, they prove that the hierarchy has the property that any fault detected by test i is also detected by test i+1, and show that this sequence of tests converges to a reliable conformance test. For certain bridge sequence methods for constructing test sequences, this result does not always hold. In experiments with several specifications, they observe that given a small number of extra states in an implementation, the sequence of tests converge to a total fault coverage for small values of i, for both reset and bridge sequence methods. They also observe that the choice of characterizing sequence has less effect on fault coverage than the choice of behavior length or number of extra states in the implementation