关键词: 二进制协议, 格式关键词, 边界确定, n-gram, 最佳路径搜索

Abstract: Aiming at the problem of field segmentation in the reverse analysis of binary protocol message format, a novel algorithm with format keywords as the reverse analysis target was proposed, which can optimally determine the boundaries of binary protocol format keywords by improved n-gram algorithm and optimal path search algorithm. Firstly, by introducing the position factor into n-gram algorithm, a boundary extraction algorithm of format keywords was proposed based on the iterative n-gram-position algorithm, which effectively solved the problems that the n value was difficult to determine and the candidate boundary extraction of format keywords with fixed offset position in the n-gram algorithm. Then, the branch metric was defined based on the hit ratio of frequent item boundaries and the left and right branch information entropies, and the constraint conditions were constructed based on the difference of n-gram-position value change rate between keywords and non-keywords. The boundary selection algorithm of format keywords based on the optimal path search was proposed to determine the joint optimal bound for format keywords. The experimental results of testing on five different types of protocol message datasets such as AIS1, AIS18, ICMP00, ICMP03 and NetBios show that, the proposed algorithm can accurately determine the boundaries of different protocol format keywords, its F values are all above 83%. Compared with the classical algorithms of Variance of the Distribution of Variances (VDV) and AutoReEngine, the F value of the proposed algorithm is increased averagely by about 8 percentage points.

Key words: binary protocol, format keyword, boundary determining, n-gram, optimal path search