Diagnosing faults in protocol testing

In protocol development for communication networks, conformance testing is an essential step to increase confidence in the correctness of a protocol implementation. In an implementation that fails conformance tests, it is necessary to diagnose the implementation in order to locate the faults. The research presented here investigates three key aspects of conformance testing and fault diagnosis of protocol implementations: (1) A sufficient condition for the existence of a diagnostic distinguishing sequence for a protocol finite state machine is identified. (2) A methodology for the diagnosis of protocol implementations with single faults is formulated. (3) New and efficient algorithms are given for the construction of protocol machines from an implementation. These algorithms use only knowledge of a protocol test sequence (i.e. input and corresponding output sequence) to construct a minimal size machine compatible with the given input sequence.