计算机科学 ›› 2020, Vol. 47 ›› Issue (7): 227-230.doi: 10.11896/jsjkx.190600073

• 计算机网络 • 上一篇    下一篇

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

陈庆超1, 王韬1, 冯文博2, 尹世庄1   

  1. 1 中国人民解放军陆军工程大学装备模拟训练中心 石家庄050003
    2 中国人民解放军陆军工程大学指挥控制工程学院 南京210007
  • 收稿日期:2019-06-23 出版日期:2020-07-15 发布日期:2020-07-16
  • 通讯作者: 王韬(a13592247640@foxmail.com)
  • 作者简介:cqc62808@163.com
  • 基金资助:
    国家重点研发计划(2017YFB0802900)

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

CHEN Qing-chao1, WANG Tao1, FENG Wen-bo2, YIN Shi-zhuang1   

  1. 1 Equipment Simulation Training Center,Army Engineering University of PLA,Shijiazhuang 050003,China
    2 College of Command and Control Engineering,Army Engineering University of PLA,Nanjing 210007,China
  • Received:2019-06-23 Online:2020-07-15 Published:2020-07-16
  • About author:CHEN Qing-chao,born in 1996,postgraduate.His main research interests include cyber security and so on.
    WANG Tao,born in 1964,Ph.D,professor.His main research interests include cyber security and cryptography.
  • Supported by:
    This work was supported by the National Key R&D Program of China(2017YFB0802900)

摘要: 在日益激烈的现代电子对抗领域中,侦听方截获的原始数据一般是比特流的形式,将比特流划分为数据帧是处理截获数据的首要任务。现有方法虽然可以准确地提取相关序列实现帧切分,但是当需要处理的数据量较大时,时间和空间的消耗量过大,并且实验过程中常常需要预先设定一些阈值。为此,文中提出了一种基于最长公共子串挖掘的未知链路层协议帧切割算法,该算法通过统计一定长度的比特流的最长公共子串,逐步精确前导码和帧起始定界符,从而实现帧切分。实验数据表明,该算法相较于基于频繁序列挖掘以实现帧切分的算法,相关候选序列数量呈指数级下降,最终使得候选序列唯一。该算法的时间复杂度为O(n),且只需单次扫描,充分说明该算法可以高效地实现帧切分。

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

Abstract: 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.

Key words: Frame segmentation, Frame starting delimiter, Longest common substring, Preamble, Unknown link layer protocol

中图分类号: 

  • TP393
[1]WALTZ E.Information Warfare:Principle and Operations[M].Beijing:Publishing House of Electronics Industry,2003:1-20.
[2]FEN L,TONG L,CHUN-RUI Z,et al.Length Identification of Unknown Data Frame[C]//Computational Intelligence and Security(CIS),2012 Eighth International Conference on.IEEE,2012.
[3]WU Y C,XU T H,WANG L M.Design of frame synchronization circuit[J].Modern Electronic Technique,2003,26(4):69-71,73.
[4]YU P D,PENG H,GONG K X,et al.Fast Blind Recognition of Convolutional Interleavers Based on Existence of Frame Sync Codes[J].Acta Electronica Sinica,2018,46(6):1530-1536.
[5]LIU H Y,CHEN J,CHEN G Q.Review of Classification Algorithms for Data Mining[J].Journal of Tsinghua University(Scie-nce and Technology),2002,42(6):727-730.
[6]SUN L,ZHU Y Q.Study of Key Techniques in Mining Frequent Sequential Patterns[J].Computer Engineering,2006,32(11):95-96.
[7]VURAL S,WANG N,BUCKNELL P,et al.Dynamic preamble subset allocation for RAN slicing in 5G networks[J].IEEE Access,2018,6:13015-13032.
[8]JIN L.Study on bit stream oriented unknown frame head identification[D].Shanghai:Shanghai Jiaotong University,2011:29-39.
[9]BAI Y,YANG X J,ZHANG Y.A Recognition Method of m-sequence Synchronization Codes Using Higher-order Statistical Processing[J].Journal of Electronics and Information Technology,2012,34(1):33-37.
[10]WANG H Z H,XUE K P,HONG P L,et al.An unknown link protocol bit stream segmentation algorithm based on frequent
statistics and association rules[J].Journal of University of Sci-ence and Technology of China,2013,43(7):554-560.
[11]XUE K P,LIU B,WANG J S,et al.Data Link Bit Stream Oriented Association Analysis on Unknown Frame[J].Journal of Electronics & Information Technology,2017,39(2):374-380.
[12]LEI D,WANG T,WANG X H,et al.Unknown protocol frame segmentation algorithm based on preamble mining[J].Journal of Computer Applications,2017,37(2):440-444,449.
[13]WU Y M.The Frame Location and Protocol Feature AnalysisFrom The Bit-Stream in The Wireless Network[D].Chengdu:University of Electronic Science and Technology of China,2014.
[14]YU T,WANG S,YU X.A Preamble Mining Algorithm Oriented to Binary Protocol Using Random Probes[C]//International Conference on Intelligent Information Hiding and Multimedia Signal Processing.Springer,Cham,2017:318-326.
[15]MOHAMMED Y,MALIK K,NUR A,et al.Mobile forensic ima-ges and videos signature pattern matching using M-aho-corasick[J].International Journal of Advanced Computer Science and Applications,2016,7(7):261-264.
[16]QIAO Z,GOTO K,OHSHIMA T,et al.Dictionary matching:review of the aho-corasick algorithm and vision for large dictio-naries[C]//Proceedings of the 8th International Conference on Information Systems and Technologies.ACM,2018:4.
[17]HOOSHMAND S,TAVAKOLI N,ABEDIN P,et al.On Computing Average Common Substring Over Run Length Encoded Sequences[J].Fundamenta Informaticae,2018,163(3):267-273.
[18]THANKACHAN S V,APOSTOLICO A,ALURU S.A prova-bly efficient algorithm for the k-mismatch average common substring problem[J].Journal of Computational Biology,2016,23(6):472-482.
[19]BARROS V,LIAO L,ROUSSEAU J.On the shortest distance between orbits and the longest common substring problem[J].Advances in Mathematics,2019,344:311-339.
[20]KOCIUMAKA T,RADOSZEWSKI J,STARIKOVSKAYA T.Correction to:Longest Common Substring with Approximately k Mismatches[J].Algorithmica,2019,81(7):3074.
[21]TANENBAUM A S,WETHERALL D J.Computer Networks:International Edition[M].Pearson Schweiz Ag,2010:153-154.
[1] 刘鑫, 王珺, 宋巧凤, 刘家豪.
一种基于AAE的协同多播主动缓存方案
Collaborative Multicast Proactive Caching Scheme Based on AAE
计算机科学, 2022, 49(9): 260-267. https://doi.org/10.11896/jsjkx.210800019
[2] 郭鹏军, 张泾周, 杨远帆, 阳申湘.
飞机机内无线通信网络架构与接入控制算法研究
Study on Wireless Communication Network Architecture and Access Control Algorithm in Aircraft
计算机科学, 2022, 49(9): 268-274. https://doi.org/10.11896/jsjkx.210700220
[3] 胡安祥, 尹小康, 朱肖雅, 刘胜利.
基于数据流特征的比较类函数识别方法
Strcmp-like Function Identification Method Based on Data Flow Feature Matching
计算机科学, 2022, 49(9): 326-332. https://doi.org/10.11896/jsjkx.220200163
[4] 姜洋洋, 宋丽华, 邢长友, 张国敏, 曾庆伟.
蜜罐博弈中信念驱动的攻防策略优化机制
Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game
计算机科学, 2022, 49(9): 333-339. https://doi.org/10.11896/jsjkx.220400011
[5] 王磊, 李晓宇.
基于随机洋葱路由的LBS移动隐私保护方案
LBS Mobile Privacy Protection Scheme Based on Random Onion Routing
计算机科学, 2022, 49(9): 347-354. https://doi.org/10.11896/jsjkx.210800077
[6] 王兴伟, 信俊昌, 邵安林, 毕远国, 易秀双.
企业内部工业互联网现状与发展对策研究
Study on Development Status and Countermeasures of Industrial Intranet in Enterprises
计算机科学, 2022, 49(7): 1-9. https://doi.org/10.11896/jsjkx.210900029
[7] 张翀宇, 陈彦明, 李炜.
边缘计算中面向数据流的实时任务调度算法
Task Offloading Online Algorithm for Data Stream Edge Computing
计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195
[8] 费星瑞, 谢逸.
基于HMM-NN的用户点击流识别
Click Streams Recognition for Web Users Based on HMM-NN
计算机科学, 2022, 49(7): 340-349. https://doi.org/10.11896/jsjkx.210600127
[9] 赵冬梅, 吴亚星, 张红斌.
基于IPSO-BiLSTM的网络安全态势预测
Network Security Situation Prediction Based on IPSO-BiLSTM
计算机科学, 2022, 49(7): 357-362. https://doi.org/10.11896/jsjkx.210900103
[10] 王思明, 谭北海, 余荣.
面向6G可信可靠智能的区块链分片与激励机制
Blockchain Sharding and Incentive Mechanism for 6G Dependable Intelligence
计算机科学, 2022, 49(6): 32-38. https://doi.org/10.11896/jsjkx.220400004
[11] Ran WANG, Jiang-tian NIE, Yang ZHANG, Kun ZHU.
Clustering-based Demand Response for Intelligent Energy Management in 6G-enabled Smart Grids
Clustering-based Demand Response for Intelligent Energy Management in 6G-enabled Smart Grids
计算机科学, 2022, 49(6): 44-54. https://doi.org/10.11896/jsjkx.220400002
[12] 魏辉, 陈泽茂, 张立强.
一种基于顺序和频率模式的系统调用轨迹异常检测框架
Anomaly Detection Framework of System Call Trace Based on Sequence and Frequency Patterns
计算机科学, 2022, 49(6): 350-355. https://doi.org/10.11896/jsjkx.210500031
[13] 陶礼靖, 邱菡, 朱俊虎, 李航天.
面向网络安全训练评估的受训者行为描述模型
Model for the Description of Trainee Behavior for Cyber Security Exercises Assessment
计算机科学, 2022, 49(6A): 480-484. https://doi.org/10.11896/jsjkx.210800048
[14] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[15] 高文龙, 周天阳, 朱俊虎, 赵子恒.
基于双向蚁群算法的网络攻击路径发现方法
Network Attack Path Discovery Method Based on Bidirectional Ant Colony Algorithm
计算机科学, 2022, 49(6A): 516-522. https://doi.org/10.11896/jsjkx.210500072
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!