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

Document Type

Conference Proceeding


ACTA Press


Computing, Health and Science


Computer and Security Science




This article was originally published as: Wang, J., Li, H., Xiao, J., & Lam, C. P. (2007). A bipartite graph matching approach to generate optimal test sequences for protocol conformance testing . Proceedings of the third conference on IASTED International Conference: Advances in Computer Science and Technology. ACST'07. (pp. 147-152). Anaheim, California: ACTA Press. Original article available here


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.