On the generation of minimal-length conformance tests for communication protocols

A technique for generating a test sequence for conformance testing of communication protocols is presented. This approach shows that it is possible to generate optimal-length test sequences which include multiple unique input/output (UIO) sequences and overlapping under certain conditions. In the absence of the above-mentioned conditions, a heuristic technique is used to obtain suboptimal solutions which show significant improvement over optimal solutions without overlapping. The technique is illustrated by the example of the NBS Class 4 Transport Protocol (TP4). The computational complexity of the algorithm is compared with that of previous techniques. A brief discussion of bounds on test sequence length is presented, and the results are compared with these bounds