We present a problem of commonly used characterization sequences (CS) for the protocol conformance testing and propose a new test sequence to resolve the problem. The proposed test sequence can decide whether a fault arises in the edge being tested or in edges composing the CS of the tested edge. Additionally, its fault coverage is much wider than that of other test sequence generation methods. To achieve the goal, we introduce the k-strong FSM and the extended UIO(EUIO), and show that it can be constructed from any CS. We also illustrate our technique on Q.2931, which is the call establishing protocol in B-ISDN. To increase the probability that a given FSM might be k-strong, we introduce a new test sequence generation scheme using cyclic input characterization sequence (CICS). Also, we present a technique to reduce the length of the test sequence satisfying the completeness.