针对EFSM中状态迁移不确定导致的协议一致性测试序列生成困难的问题, 提出了一种协议一致性测试序列生成算法。该算法基于互异代表系理论为每个协议状态变迁赋权值, 再基于分支界限法搜索生成的协议测试序列, 将协议一致性测试序列的生成转换为寻找最小权值状态变迁路径的问题。该算法克服了无赋权要求的宽度优先搜索的缺陷, 降低了测试序列的搜索与生成时间复杂度, 提高了测试序列生成的效率。