Minimal length checking sequence generation for testing communication protocols.

This study discusses the generation of the minimum length checking sequences for FSM-based protocol conformance testing. The discussion focuses on finding the minimal length of resulting checking sequences for an FSM under different conditions. Without interleaving state identification and transition verification sequences, four methods (D-method, W-method, Wp-method and UIOv-method) of generating minimum length test sequences for FSM$\rm \sb{s}$ with reliable reset feature are reviewed and provided to construct checking sequences. These four methods are then improved to generate minimum length checking sequences for FSM$\rm \sb{s}$ without reliable reset feature and provided to construct checking sequences. Moreover, the effects of interleaving the state identification and transition verification sequences on the length of the checking sequences are studied. An algorithm for interleaving the state identification and transition verification sequences generated by the above four methods with reliable reset feature is proposed. It is observed that the reduction in the length of checking sequences due to interleaving is significant. Finally, the two general models for constructing minimal length checking sequences using distinguishing sequences with interleaved state identification and transition verification sequences are proposed. The proof for the first model to find a minimum length checking sequence in polynomial time is provided. The sequences generated by using both models are proved to be checking sequences. Examples are provided as applications of all the proposed methods and models