基于最长公共子串挖掘的未知链路层协议帧切割算法  

Unknown Link Layer Protocol Frame Segmentation Algorithm Based on Longest Common Substrings Mining

作　　者：陈庆超 王韬 冯文博 尹世庄 CHEN Qing-chao;WANG Tao;FENG Wen-bo;YIN Shi-zhuang(Equipment Simulation Training Center,Army Engineering University of PLA,Shijiazhuang 050003,China;College of Command and Control Engineering,Army Engineering University of PLA,Nanjing 210007,China)

机构地区：[1]中国人民解放军陆军工程大学装备模拟训练中心,石家庄050003 [2]中国人民解放军陆军工程大学指挥控制工程学院,南京210007

出　　处：《计算机科学》2020年第7期227-230,共4页Computer Science

基　　金：国家重点研发计划(2017YFB0802900)。

摘　　要：在日益激烈的现代电子对抗领域中,侦听方截获的原始数据一般是比特流的形式,将比特流划分为数据帧是处理截获数据的首要任务。现有方法虽然可以准确地提取相关序列实现帧切分,但是当需要处理的数据量较大时,时间和空间的消耗量过大,并且实验过程中常常需要预先设定一些阈值。为此,文中提出了一种基于最长公共子串挖掘的未知链路层协议帧切割算法,该算法通过统计一定长度的比特流的最长公共子串,逐步精确前导码和帧起始定界符,从而实现帧切分。实验数据表明,该算法相较于基于频繁序列挖掘以实现帧切分的算法,相关候选序列数量呈指数级下降,最终使得候选序列唯一。该算法的时间复杂度为O(n),且只需单次扫描,充分说明该算法可以高效地实现帧切分。In the increasingly fierce field of modern electronic countermeasures,the original data intercepted by the listener is ge-nerally in the form of bit stream.Dividing the bit stream into data frames is the primary task to process the intercepted data.Although the existing methods can accurately extract the related sequence to achieve frame segmentation,when the amount of data to be processed is large,the consumption of time and space is unacceptable and some thresholds need to be set in advance.For this reason,an unknown link layer protocol frame segmentation algorithm based on the longest common substring mining is proposed in this paper.By counting the longest common substring of the bit stream of a certain length,the preamble and the frame start delimiter become iteratively accurate.Thus,the frame segmentation is realized.The experimental data show that compared with the algorithm based on frequent sequence mining to achieve frame segmentation,the number of candidate sequences of the proposed algorithm is reduced exponentially,and the final candidate sequence is unique.The time complexity of the proposed algorithm is O(n),and only a single scan is required,which fully shows that the proposed algorithm can realize frame segmentation efficiently.

关 键 词：最长公共子串 前导码 帧起始定界符 帧分割 未知链路层协议 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]