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

Domain-specific Algorithm of Protocol State Machine Active Inference

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

Existing protocol state machine inference approaches based on algorithm L^＊ are inefficient owing to ignorance of protocol-specific knowledge. As the protocol messages are abstracted as the independent and insignificant sym- bols, and test samples are completely generated randomly in equivalence query, invalid queries and test samples are inevitable. A protocol state machine active inference algorithm named LN^＋ was proposed, which improves the algorithm LM^＋ in three aspects. Firstly,LN^＋ filters the invalid output query according to the constraint on strict order, which is extracted from conservation samples. Secondly, LN^＋ constructs the extended prefix tree accepter（EPTA） corresponding to the sample set and answers the output query in advance. Thirdly, a new proposed strategy to find counterexamples more effectively is applied to judge the equivalence query based on positive sample mutation. Experimental results show that LN＋ improves the inference efficiency greatly and achieves the same accuracy as algorithm LM^＋.