Tightly-synchronizable protocol test generation via the duplex technique(Journal)

[[abstract]]As the synchronizable test sequence (generated by exponential-computation-time techniques) overcomes the synchronization problem incurred in protocol conformance 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, the authors 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 generating a minimum-length tightly-synchronizable 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[[fileno]]2030209010083[[department]]資訊工程學