Wen-Huei Chen and Chuan Yi Tang
Institute of Computer Science
National Tsing-Hua Unviersity
Hsinchu, Taiwan 300, R.O.C.
As the synchronizable test sequence (generated by exponential-computation-time techniques) overcomes the synchronication problem incurred in protocol confromance testing, a new kind of protocol test sequence, called the tightly-synchronizable test sequence, is proposed to overcome the same problem but with a longer length and, moreover, the tight-synchronization problem incurred in protocol diagnostic testing. A low-order polynomial-time executable technique, called the duplex technique, is proposed to construct the duplex graph from the transition graph of the protocol so as to generate tightly-synchronizable test sequences from tours of the duplex graph. By testing whether the duplex graph is strongly-connected, we can determine whether the protocol possesses a tightly-synchronizable test sequence that tests all transitions. In the case that such a tightly-synchronizable test sequence exists, the technique can: I) be used with the transition-tour method and the Chinese postman algorithm for generation a minimum-length tightlysynchronizable test sequence that tests all transitions; and, ii) be used with the test-subsequence method and the Chinese postman algorithm for generating a tightly-synchronizable test sequence that includes all the given test subsequences, with a length within a bound. In the nonexistence case, we propose that the addition of some types of redundant transitions, called ship and bridge transitions, results in a tightly-synchronizable test sequence that tests all transitions. Furthermore, the duplex technique can be used with the strong connectivity augmentation algorithm to generate the minimum number of ship and bridge transitions.
Keywords: protocol testing, synchronization problem, tight-synchronization problem, tightly-synchronizable test sequence
Received July 5, 1991; revised January 3, 1992.
Communicated by Wen-Tsuen Chen.
* Part of this paper appears as "Synchronizable Protocol Test Generation Via the Duplex Technique" in the IEEE International Conference on Computer Communications, San Franscio, June (1990). (INFOCOM'90)