Bounds on the length of test sequences for conformance testing of communication protocols.

Abstract

For the general case, we give lower bounds (i.e., approximations to the greatest lower bound (GLB)) on the length of test sequences generated by any D-method without overlapping test segments as well as by any method employing a W-set (W-method) without overlapping test segments. We then establish a lower bound (i.e., an approximation to the GLB) on the length of test sequences generated by any D-method (or W-method) that overlaps test segments. It is observed that the reduction in the length of test sequences generated by any D-method (or W-method) due to overlapping is significant. Thus, two types of efficient algorithms based on overlapping test segments are established for both a method employing a distinguishing sequence and a method employing a W-set. The first type of efficient algorithms utilize the maximum-cardinality minimum-cost matching algorithm. The second type of efficient algorithms utilize the rural Chinese postman tour algorithm. Moreover, the sufficiency conditions for the second type of algorithms to find a minimum length test sequence is polynomial time are indicated. Furthermore, the sufficiency conditions for the second type of algorithms to achieve the optimal length test sequences are discussed. (Abstract shortened by UMI.)