一种基于域知识的协议状态机主动推断算法

摘要

现有基于L*算法的协议状态机主动推断方法忽略了协议特有的域知识,将协议报文抽象为相互独立、无意义的符号,并完全随机地生成测试样本进行状态机等价判定,导致产生大量的无效询问和测试样本,在真实网络环境下推断效率较低.在LN+算法的基础上提出了一种基于域知识的协议状态机主动推断算法LN+,其改进主要体现在:依据会话样本集提取各报文之间的强顺序约束关系来过滤无效的输出询问,构建会话样本集对应的扩展前缀树接受器(Extended Prefix TreeAccepter,EPTA)对输出询问进行预响应,提出了一种基于正例样本变异的等价询问近似判定算法以提升寻找反例的效率.实验结果表明,LN+算法能够大幅提高推断效率,并且具有与LM+算法相同的推断准确度.