Abstract
This dissertation presents several new results for automatically generating conformance test sequences for communication protocols by means of Unique Input/Output (UIO) sequences based on Finite State Machine (FSM). UIO sequences, in combination with an optimization technique known as the Rural Chinese Postman Algorithm [1], have been shown to be effective and efficient in checking the conformance of a protocol implementation to its specification. The contributions of this dissertation are as follows: first to show that if multiple minimum-length UIO sequences are computed for each state of the FSM specification, then the length of the resulting test sequence is significantly reduced without an appreciable increase in the time needed to compute the sequence. Then, this dissertation discusses the weakly connected graph problem and the multiple UIO tour minimization problem. It is proved that by appropriately changing the original assignment graph and using network flow techniques with the chaining method, efficient solutions can be provided. The theoretical approaches behind the solution to these problems are fully characterized. A new comprehensive fault model is developed and analytical expressions are given for the fault coverage. The conditions for undetectability are analyzed and appropriate new algorithms under weak and strong conformance testing are proposed. To further reduce the length of test sequence and to simplify the generation of the UIO sequences, some unique edge labels can be utilized. This can be done by selectively concatenating additional edges prior to each test subsequence. The extended test subsequence can distinguish not only the partial behavior of the original edge under test, but also the end state of any additional edge. This process can be iteratively continued to further reduce the number of tests. Simulation results and illustrative examples are presented. Overhead issues are discussed and significant improvements are shown for achieving almost 100% fault coverage. Finally, a new comprehensive fault model is developed. The conditions for detectability of the faulty extra state are analyzed and an appropriate new algorithm is proposed. The extension of the proposed approach to multiple faulty extra states is discussed.
Shen, Yinan (1993). Validation and verification of Finite State Machines. Texas A&M University. Texas A&M University. Libraries. Available electronically from
https : / /hdl .handle .net /1969 .1 /DISSERTATIONS -1531005.