A Bipartite Graph Matching Approach to Generate Optimal Test Sequences for Protocol Conformance Testing

J. Wang (PRC, Australia), H. Li (Australia, PRC), J. Xiao, and C.P. Lam (Australia)


Software engineering, conformance testing, finite state machines, graph


Conformance testing using test sequences is the main means to ensure that a protocol implementation conforms to its specification. For systems which are specified by nondeterministic finite state machines, a commonly used technique to generate test sequences is the generalized Wp-method with reset which often yields long test sequences if no reliable reset function exists in the system. In this paper, we propose a bipartite graph matching approach to optimize test sequences generated using the generalized Wp-method for protocol conformance testing. Our approach significantly reduces the length of the test sequences required for conformance testing while maintaining the same fault detection capability.

Important Links:

Go Back