随着通信网络的普及和需求的复杂化,网络协议规模日趋复杂庞大,这对协议的实现和开发提出了新的挑战。通信网络分布性,异构性和实时性等特点决定了网络协议实现不仅要求功能正确完善,更强调协议实现之间具有良好的一致性互通。网络协议实现与网络协议规范之间的微小偏差,都可能给通信网络带来不可估量的灾难性后果。协议一致性测试是评价协议实现和协议规范符合程度的实验活动,也是确保网络通信质量的重要手段之一。为了避免传统手工生成一致性测试序列费时费力并且质量难以保证的弊端,基于形式化扩展有限状态机EFSM模型自动生成协议一致性测试序列成为了一个热点研究问题。EFSM模型在FSM模型的基础上扩充了丰富的变量和谓词条件,在扩充协议控制和数据部分建模能力的同时,也增加了一致性测试序列自动生成的困难。当前,基于EFSM模型自动生成协议一致性测试序列的研究热点问题主要集中在四个方面：1)如何生成可执行的状态验证序列；2)如何保证生成的一致性测试序列的可执行性；3)如何设计基于控制流和数据流的可执行测试序列生成算法；4)如何设计协议一致性测试序列自动生成集成环境。本文以这四个热点问题为研究主线,围绕基于EFSM模型协议一致性测试序列自动生成的关键技术问题进行了系统和深入的研究。所做的研究工作和创新性研究成果主要有以下几个方面：(1)提出了一种新的可执行状态验证序列ESIS (Executable State Identification Sequences)生成算法。新算法基于宽度优先搜索可执行分析树EAT (Executability Analysis Tree)的思想,从状态验证需求的角度,在EFSM的状态格局投影子空间中,采用分步计算的方式生成具体验证场景下的最短可执行状态验证序列,从而避免了在完全状态格局空间中单步计算所有状态验证序列的复杂性。(2)深入的分析了ESIS序列生成过程中EAT树的宽度优先搜索过程,在给出EAT树变迁区分度因子和节点收敛度因子概念的基础上,提出了一种ESIS序列自适应生成算法。新算法利用EAT树节点权重函数作为节点搜索引擎,把ESIS序列自动生成问题转化为自适应搜索权重最大的EAT节点问题来解决。实验结果表明,与宽度优先搜索算法相比,自适应生成算法具有较好的时空特性。(3)提出了一种启发式探索EFSM协议模型状态格局空间的可执行测试序列生成方法,并以此为基础,给出了一种新的控制流测试序列生成算法。新方法以启发式状态格局探索策略替代传统的宽度优先搜索方式生成可执行协议测试序列。该算法把协议可执行测试序列生成转化为在协议状态格局空间中探寻最小权值路径的问题。实验数据表明,新算法可以有效缓解可执行性分析过程中的状态空间爆炸问题。(4)针对EFSM模型变迁及变迁之间的关联关系进行了详细的讨论和分析,定义了一个邻接变迁关联图,提出了一种基于邻接变迁关联图的EFSM模型可执行测试序列生成算法,并结合控制流和数据流测试覆盖策略给出了一种新的控制流&数据流相叠加的测试序列生成方法。新算法首先根据变量和谓词包含情况对变迁进行分类,然后深入挖掘了邻接变迁之间的关联关系。最后,基于自适应预测搜索函数启发式引导搜索可执行性分析树生成可执行的测试序列。新算法在保证生成的测试序列可执行性的同时在测试序列最短长度和测试序列生成开销之间进行了权衡。(5)基于本文给出的一些新算法,提出了一种基于EFSM模型可执行一致性测试序列自动生成集成环境设计思路,并实现了一个原型系统。该集成测试环境完整支持协议一致性测试序列生成过程的多个关键环节：协议形式化建模、一致性测试序列自动生成和测试序列TTCN-3形式化描述。