We improve an earlier test sequence generation method for testing the conformance of a protocol implementation to its specification modeled by an extended finite state machine (EFSM) represented by a flow digraph. The earlier method produces an executable test sequence (i.e., one that has feasible parameter values) that covers a set of define-clear-use paths of the flow digraph for testing the data portion of the EFSM. We first overlap these define-clear-use paths into a shorter executable test sequence that tests the data portion. Second, we overlap the new test sequence with a set of transition-verifying paths for testing the control portion.

A new method is proposed to generate the executable test sequence which simultaneously verifies the protocol control and data portions, that are respectively modeled as a deterministic finite state machine (FSM) and a set of rules between parameter values. The method involves converting the FSM and rules into a SelectO digraph, whose tour can be used to generate the test sequence associated with feasible parameter values that verifies the transitions of the FSM and the rules. The selecting Chinese postman algorithm is used to find a specific tour for minimizing the length of the test sequence that verifies each transition and each rule at least once. Experimentation on the simple session protocol indicates that an executable test sequence can be achieved which is 37% shorter than that achieved by testing the two portions separately.

A test sequence generation method is proposed for testing the conformance of a protocol implementation to its specification in a remote testing system where both external synchronization and input/output operation costs are taken into consideration. The method consists of a set of transformation rules that constructs a duplexU digraph from a given finite state machine (FSM) representation of a protocol specification; and an algorithm that finds a rural postman tour in the duplexU digraph to generate a synchronizable test sequence utilizing multiple UIO sequences. If the protocol satisfies a specific property, namely, the transitions to be tested and the UIO sequences to be employed form a weakly-connected subgraph of the duplexU digraph, the proposed algorithm yields a minimum-cost test sequence. X.25 DTE and ISO Class 0 transport protocols are shown to possess this property. Otherwise, the algorithm yields a test sequence whose cost is within a bound from the cost of the minimum-cost test sequence. The bound for the test sequence generated from the Q.931 network-side protocol is shown to be the cost sum of an input/output operation pair and an external synchronization operation.>

A test sequence generation method is proposed for testing the conformance of a protocol implementation to its specification in a remote testing system, taking both external synchronization and input/output operation costs into consideration. The method consists of a set of transformation rules that constructs a duplexU digraph from a given finite state machine (FSM) representation of a protocol specification and a heuristic algorithm that finds a rural postman tour in the duplexU digraph to generate a synchronizable test sequence utilizing multiple UIO sequences. If the protocol satisfies a specific property, the heuristic algorithm yields a minimum-cost test sequence. The X.25 DTE and ISO Class 0 Transport protocols are proved to possess this specific property. otherwise, the heuristic algorithm yields a test sequence whose cost is within a bound from the cost of the minimum-cost test sequence. The bound for the test sequence generated from the Q.931 Network-side protocol is shown to be the cost sum of an input/output operation and an external synchronization operation.>

A technique is proposed for generating a synchronizable test sequence to ensure protocol implementation conformity to protocol specification. This duplex technique converts the transition graph of a protocol into a duplex graph in order to generate a synchronizable test sequence for the protocol. By introducing the Chinese postman tour, this technique can be applied to the transition-tour method for generating the optimally synchronizable test sequence.>