Computer Science ›› 2020, Vol. 47 ›› Issue (7): 227-230.doi: 10.11896/jsjkx.190600073

• Computer Network • Previous Articles     Next Articles

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)

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

CLC Number: 

  • 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] LIU Xin, WANG Jun, SONG Qiao-feng, LIU Jia-hao. Collaborative Multicast Proactive Caching Scheme Based on AAE [J]. Computer Science, 2022, 49(9): 260-267.
[2] GUO Peng-jun, ZHANG Jing-zhou, YANG Yuan-fan, YANG Shen-xiang. Study on Wireless Communication Network Architecture and Access Control Algorithm in Aircraft [J]. Computer Science, 2022, 49(9): 268-274.
[3] HU An-xiang, YIN Xiao-kang, ZHU Xiao-ya, LIU Sheng-li. Strcmp-like Function Identification Method Based on Data Flow Feature Matching [J]. Computer Science, 2022, 49(9): 326-332.
[4] JIANG Yang-yang, SONG Li-hua, XING Chang-you, ZHANG Guo-min, ZENG Qing-wei. Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game [J]. Computer Science, 2022, 49(9): 333-339.
[5] WANG Lei, LI Xiao-yu. LBS Mobile Privacy Protection Scheme Based on Random Onion Routing [J]. Computer Science, 2022, 49(9): 347-354.
[6] WANG Xing-wei, XIN Jun-chang, SHAO An-lin, BI Yuan-guo, YI Xiu-shuang. Study on Development Status and Countermeasures of Industrial Intranet in Enterprises [J]. Computer Science, 2022, 49(7): 1-9.
[7] ZHANG Chong-yu, CHEN Yan-ming, LI Wei. Task Offloading Online Algorithm for Data Stream Edge Computing [J]. Computer Science, 2022, 49(7): 263-270.
[8] FEI Xing-rui, XIE Yi. Click Streams Recognition for Web Users Based on HMM-NN [J]. Computer Science, 2022, 49(7): 340-349.
[9] ZHAO Dong-mei, WU Ya-xing, ZHANG Hong-bin. Network Security Situation Prediction Based on IPSO-BiLSTM [J]. Computer Science, 2022, 49(7): 357-362.
[10] WANG Si-ming, TAN Bei-hai, YU Rong. Blockchain Sharding and Incentive Mechanism for 6G Dependable Intelligence [J]. Computer Science, 2022, 49(6): 32-38.
[11] Ran WANG, Jiang-tian NIE, Yang ZHANG, Kun ZHU. Clustering-based Demand Response for Intelligent Energy Management in 6G-enabled Smart Grids [J]. Computer Science, 2022, 49(6): 44-54.
[12] WEI Hui, CHEN Ze-mao, ZHANG Li-qiang. Anomaly Detection Framework of System Call Trace Based on Sequence and Frequency Patterns [J]. Computer Science, 2022, 49(6): 350-355.
[13] TAO Li-jing, QIU Han, ZHU Jun-hu, LI Hang-tian. Model for the Description of Trainee Behavior for Cyber Security Exercises Assessment [J]. Computer Science, 2022, 49(6A): 480-484.
[14] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[15] GAO Wen-long, ZHOU Tian-yang, ZHU Jun-hu, ZHAO Zi-heng. Network Attack Path Discovery Method Based on Bidirectional Ant Colony Algorithm [J]. Computer Science, 2022, 49(6A): 516-522.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!