Improving the UIOv-method for protocol conformance testing

[[abstract]]The UIOv-method for testing the conformance of a protocol implementation to its specification is improved to generate a shorter test sequence. The traditional UIOv-method utilizes minimum-length Unique Input/Output (UIO) sequences to verify the implementation's states, and thus suffers from a long verification part for checking that these UIO sequences are uniquely implemented. The improved method removes this constraint so that each state can select its UIO sequence from a large set of UIO sequences, and thus some choices may shorten the verification. The exclusive tree data structure is also proposed to represent the mutually exclusive relation between UIO sequences (two UIO sequences are called mutually exclusive if no verification is needed within them); each exclusive tree corresponds to a set of UIO sequences. An algorithm is proposed to generate the exclusive tree whose corresponding UIO sequences can be used with the UIOv-method to shorten the verification while not lengthening the total test sequence. Experimentation of two protocol examples and the Q.931 network-side protocol indicate a length reduction for the verification of 100%, 43% and 64%, respectively, and for the total test sequence of 13.8%, 8.6% and 12.7%, respectively.[[fileno]]2030209010024[[department]]資訊工程學