Protocol testing hierarchies, maximum fault coverage and fault diagnosis

Communication protocols are the rules and conventions designed to enable network entities to communicate. They must be specified completely and implemented correctly. A protocol implementation must be tested for conformance to its specification standard. A protocol specification consists of two parts, a part dealing with the control aspects and a part dealing with the data transfer aspects. The control part of a protocol can be modeled by a finite state machine. A protocol implementation under test is treated as a black-box for conformance testing purposes. The conformance testing is done by applying a test sequence to the implementation and comparing the observed behavior with the expected behavior. Two important features of a test sequence are its ability to capture faults and its length.; The main limitations of the existing methods for test sequence generation include the following: (a) the test sequences may not have maximum coverage with respect to a fault model i.e., detect all the possible faulty implementations that can be described by the fault model, (b) the test sequences may be excessively long (exponentially-bounded by the number of states in the finite state machine model), and (c) it may not be possible to diagnose a detected faulty implementation from the behavior observed during conformance testing.; This dissertation research deals with the following three issues in protocol conformance testing: (a) develop a theory for generating a hierarchy of test sequences (parameterized by length of behaviors tested), which are shown to converge to reliable conformance test sequences, (b) prove conditions for the existence of bounded-length test sequences that can always detect single faults in protocol implementations, and (c) develop a methodology for diagnosing the fault in protocol implementations with single faults.