A reduced test suite for protocol conformance testing

Let M be a finite-state machine, and let S be an implementation of M. The protocol-testing problem is the problem of determining if S is a correct implementation of M. One known method for solving this problem, called the W-method, has the disadvantage that it generates a relatively large test set. In this paper, we describe three new versions of this method. We prove that these versions all have the same fault detection capability as the W-method. In addition, we show that in most cases all three generate a smaller number of tests than the W-method. Specifically, suppose Ml and Mz are finite-state machines having n and m states, respectively, where Ml is a specification (M), Mz is an implementation (S), and m > n. In addition, suppose they have input alphabet X, where 1X1= k; let a be the total number of strings in a characterization set for Ml, and let ~be the total number of strings in a transition couer set for Ml. The W-method will generate a test set consisting of afl(k M n + 1 -I)/(k -1) strings. In contrast, our first algorithm will generate a test set containing at most B( a + km-n ) strings. For our second algorithm, the number of strings will be ~kmaxt'-l>m-"j, and for the third, ~(kn -1 + km-"), When m >> ~, all three of our algorithms will produce fewer strings than the W-method. Finally, two of our algorithms make use of a heuristic for minimizing the number of strings in a characterization set. We show that the performance ratio for this heuristic has an upper bound of O(log n).