IMPROVING THE UIOV-METHOD FOR PROTOCOL CONFORMANCE TESTING

The UIOv-method for testing the conformance of a protocol implementati on to its specification is improved to generate a shorter test sequenc e. The traditional UIOv-method utilizes minimum-length Unique Input/Ou tput (UIO) sequences to verify the implementation's states, and thus s uffers from a long verification part for checking that these UIO seque nces are uniquely implemented. The improved method removes this constr aint so that each state can select its UIO sequence from a large set o f UIO sequences, and thus some choices may shorten the verification. T he exclusive tree data structure is also proposed to represent the mut ually exclusive relation between UIO sequences (two UIO sequences are called mutually exclusive if no verification is needed within them); e ach exclusive tree corresponds to a set of UIO sequences. An algorithm is proposed to generate the exclusive tree whose corresponding UIO se quences can be used with the UIOv-method to shorten the verification w hile not lengthening the total test sequence. Experimentation of two p rotocol examples and the Q.931 network-side protocol indicate a length reduction for the verification of 100%, 43% and 64%, respectively, an d for the total test sequence of 13.8%, 8.6% and 12.7%, respectively.