Protocol Conformance Testing Using Multiple UIO Sequences (NOT KNOWN IF PUBLISHED BECAUSE AUTHOR HAS LEFT AT&T)

This paper presents new results for automatically generating conformance test sequences for communication protocols by means of Unique Input/Output (UIO) sequences [6]. UIO sequences, in combination with an optimization technique known as the Rural Chinese Postman Algorithm [10], have been shown to be effective and efficient in checking the conformance of a protocol implementation to its specification [8],[9]. The contribution of this paper is to show that if multiple minimum-length UIO sequences are computed for each state of the FSM specification then the length of the resulting test sequence is significantly reduced without an appreciable increase in the time needed to compute the sequence. An algorithm for optimal assignment of the multiple UIO sequences is given which based on network flow and is polynomial in the number of states and transitions of the FSM.