A reduced test suite for protocol conformance testing
Philip J. Bernhard · ACM Transactions on Software Engineering and Methodology · 1994
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).