Abstract: Interoperability testing is a basic guarantee for interconnecting network devices and transporting the information between these devices. Interoperability testing involves at least two IUTs（implementation under test）, and sometimes one of them is called QE(qualified equipment) which plays a measurement role during the testing process and can be used to verdict the other IUT’s interoperability capability. Firstly，the content of interoperability testing of a protocol is introduced and the relation between interoperability testing and conformance testing is given. Secondly, according to the nondeterministic finite state machine of specification and the current experience of interoperability testing, a probability nondeterministic finite state machine(PNFSM) is constructed gradually. The achieved model efficiently describes the current situation of interoperability testing. Thirdly, based on PNFSM and a certain policy, a binary tree which covers all states of PNFSM is generated. The algorithms which are used to select test sequences from the binary tree are presented. The algorithms’ validity is proved through an example and the final test sequences are listed in a table. Furthermore, the testing scenario of counting to infinite in RIP is used as an experiment to simply illuminate the modeling method. Finally, the conclusion and the research work in the future are introduced.