关键词: 协议格式推断, 互信息, 扩展前缀树, 多序列比对算法

Abstract: Network protocol format inference is of great significance in many network security applications. Most existing protocol format inference methods suffer from high computation complexity and low accuracy. A extended prefix tree based protocol format inference method is proposed in the paper. Firstly, the candidate keywords are obtained through N-gram word segmentation and merged into protocol keywords of different lengths according to mutual information. On the basis of protocol keywords, the extended prefix tree is constructed according to protocol keyword sequences, and the initial clustering is performed on the extended tree. Then, through  segmental multiple sequence alignment based on the extended prefix tree, the similar format will be combined and the precise protocol format can be obtained. Compared with traditional format inference methods, the proposed method reduces the time complexity of inference. Experimental results show that the proposed method performs well for both text protocols and binary protocols.

Key words: protocol format inference, mutual information, extended prefix tree, multiple sequence alignment algorithm