Test sequence generation from the protocol data portion based on the Selecting Chinese Postman algorithm

摘要

Kwast's method for testing a protocol implementation's conformance to its data portion specification (modeled by a set of rules) is improved to generate a shorter test sequence. The protocol is transformed into a Behavior Machine, and Kwast uses a breadth-first search algorithm to search over the machine for obtaining an executable test sequence (i. e., one with executable parameter values) that verifies each rule at least once. In the improved method, test segments for verifying each rule are constructed and a Selecting Chinese Postman algorithm is proposed for selecting and connecting these test segments so as to establish a minimum-length executable test sequence. Experimentation of the Simple Session Protocol indicates a length reduction of 60/100.