协议测试是协议工程中的一个重要环节，其目的是为了保证协议实现按照协议描述稳定可靠地运行，对于通信产品的质量保证有着重要的意义。协议测试包括四个方面：一致性测试、互操作性测试、性能测试和坚固性测试。一致性测试是为了检测协议实现与协议规范符合的程度，互操作性测试旨在检测同一种或同一类协议的不同实现版本之间的互通互操作能力，此二者均是协议实现体可正确工作的基本保证。在过去的研究工作中，人们主要着重于一致性测试，而对互操作性测试的研究较少。虽然一致性是保证互操作性的一个必要的步骤，但通过一致性测试的协议实现体不一定能正确地互操作，对协议实现体进行直接的互操作性测试是必不可少的。测试系统设计和测试套具的产生是协议测试中要解决的两大问题。测试系统设计重点解决测试方法和测试系统结构的问题，测试套具的产生要解决测试“彻底性”和“标准化”的问题，解决测试套具自动生成问题。互操作性测试的研究工作可以大致分成两类，第一类是对互操作性测试一般概念的研究和互操作性测试的实验，第二类是系统化的互操作性测试序列生成。本文工作的重点是围互操作性测试序列的自动生成和优化、测试覆盖、测试可靠性等相关问题展开的。本文的研究工作主要集中在如下几个方面：(1)基于复合有限状态机模型的最小代价互操作性测试序列生成算法在测试序列生成算法中，测试代价是评估测试序列优劣的一个重要指标。但目前很多互操作性测试的研究工作均只讨论了对系统可以完全描述和完全控制的条件下如何生成满足转移覆盖的互操作性测试序列覆盖互操作系统的交互行为，很少考虑生成的测试序列的代价。本文将分析互操作系统中的测试代价的组成，通过对系统的可达性分析，构造复合有限状态机的加权转移图，采用带权图的边覆盖问题的算法生成最优互操作性测试序列，同时给出了该问题的一个贪心近似算法。该方法可有效地提高测试效率。(2)局部描述系统的互操作性测试序列生成互操作性测试在现实中经常会有这样的情况：需要测试待测系统和另一个现存系统的互操作能力，由于现存系统过于复杂或没有足够的信息，无法对整个互操作系统进行完整地建模描述。在这种情况下生成的测试序列需要满足路径覆盖方可保证互操作性测试的彻底性。本文讨论了在局部描述的互操作系统中基于有向图的单边互操作性测试序列生成算法，提出了互操作性测试的最小完全覆盖准则以指导测试序列的生成，并给出了相应的生成算法。采用该方法可以获得覆盖所有互操作转移序列的最小测试集，在保证测试覆盖率的前提下显著降低测试的代价。(3)测试可靠性及动态测试方法传统的测试序列生成算法都只从静态的角度考虑测试序列的效果，忽略了在测试过程中由于测试序列之间状态转移的相关性而造成的局部测试结果对测试序列执行的影响。引入动态测试方法可以在测试执行时根据测试过程绕过一些局部错误，对待测体实施更完善的测试，并可以避免一些不必要的测试执行。本文提出了基于局部错误诊断信息的动态测试方法，在测试过程中动态收集局部测试信息，采用错误诊断方法对局部错误进行准确定位，再根据诊断结果指导下一步的测试执行。该方法可以更有效地提高测试结果的可靠性和测试执行效率。