一种基于状态融合的协议状态机推断方法

针对现有协议状态机推断方法忽视协议系统输入输出报文之间的内在关系,导致自动化程度较低等问题,提出一种基于状态融合的协议状态机推断方法。首先采集会话样本,将会话过程的输入输出报文序列抽象为符号序列;然后采用扩展前缀树转换器(EPTT)构建初始状态机,通过各状态对相同输入符号序列的状态转换和输出响应评判其相似度,依据相似度的高低搜寻候选状态对并尝试对其融合,同时有针对性地构造测试用例以验证此次融合的正确性。上述流程反复执行,直到没有可融合的状态。结果表明,该方法自动化程度较高,推断出的结果与真实协议状态机高度吻合。

Method of protocol state machine inference based on state merging

The existing protocol state machine inference methods ignore the relationship of input and output messages and are not automated. A method of protocol state machine inference based on state merging was put forward. Firstly, session samples were collected, and the input and output messages of session were abstracted into symbol sequences. Then the extended prefix tree transducer (EPTT) was used to build the initial state machine, and the similarity of all states evaluated according to the state transition and output responses. The candidate states for merger were determined based on the level of state similarity. Meanwhile, test cases were generated to prove the validity of this merger and these processes repeated until there are no states that can be merged. Experimental results show that the method can infer highly accurate protocol state machine automatically.