On the formal methods for protocol conformance testing.

Abstract

The use of formal methods allows automated generation and optimization of test sequences. Developing formal methods for generating communications protocol conformance tests has drawn considerable attention in recent years. This thesis describes the implementation of five formal methods of protocol conformance test sequence generation proposed in the literature. These methods are: Transition tour (T) method, Distinguishing sequence (D) method, Characterizing sequence (W) method, Unique Input/Output sequence (UIO) method and Multiple UIO-method. Some related graph theoretic optimization techniques for the Chinese Postman Problem (CPP) and Rural Chinese Postman Problem (RCPP) are applied to T-method and UIO-method respectively to determine minimum-cost test sequences. It is shown in this thesis that the solution to the RCPP can also be applied to D-method and W-method to derive minimum-cost test sequences. The application of five formal methods to a real protocol, Transport protocol class 4, is then discussed.