Conformance testing of protocols is the process of checking whether an implementation under test conforms to the standards. In this paper we prove that the multilevel method (M method) [which splits the specification graph into a basic subgraph and one or more higher level subgraph(s)] is capable of diagnosing any number of faults in the higher level subgraph(s), if the basic subgraph is error-free. Heuristics for obtaining the basic subgraph and higher level subgraphs from the specification graph are also given. The advantage of the M method is that it has error recovery and, in addition, it does not assume the presence of reliable reset in the implementation under test. We additionally propose an incremental test sequence generation method, which produces a shorter test sequence and whose fault coverage is same as that of the M method. Finally, we compare the M method with other fault detection and fault diagnostic methods. © 1998 IEEE.