面向比特流的频繁模式序列挖掘算法学术研究自主创新重点跨越支持发展引领未来·AcademicResearch金凌1，邱卫东1，杨小牛2，杨红娃2(1上海交通大学通信系统控制技术国家级重点实验室，上海200240；2中国电子科技集团公司第三十六研究所通信系统信息控制与安全国家重点实验室，浙江嘉兴314033)[摘要]在日益激烈的电子对抗中，如何从纯比特流中寻找特征模式序列是分析比特流信息的核心问题。传统的模式匹配方式虽然能够解决特定模式序列的寻找，但是对于频繁序列的发现需要耗费大量的时间和空间。面向比特流的频繁模式序列挖掘算法引入了数据挖掘的思想，解决了模式匹配要多次扫描源数据的问题，利用频繁集挖掘的剪枝方法，减少数据库操作次数，提高了频繁序列的寻找效率。[关键词]数据挖掘；频繁集；比特流；频繁序列；剪枝[中图分类号]TP309.3[文献标识码]A[文章编号]1019-8054(2022)06-0095-03Bitstream-orientedFrequentPatternSequenceMiningAlgorithmJINLing1，QIUWei-dong1，YANGXiao-niu2，YANGHong-wa2(1StateKeyLaboratoryofCommunicationSystemControllingTechnology，ShanghaiJiaotongUniversity，Shanghai200240，China；2No.36InstituteofChinaElectronicsTecnologyGroupCorporation，NationalScienceandTechnologyonCommunicationInformationSecurityControlLaboratory，JiaxingZhejiang314033，China)[Abstract]Intheelectronicwarfare，howtofindcharacteristicpatternsfrompurebitstreamisoneofthecoreissuesindealingwithbitstreaminformation.Althoughthetraditionalpattern-matchingalgorithmscouldimplementthesearchofspecificpattern，thediscoveryoffrequentsequenceswouldtakealotoftimeandspace.Inspiredbytheideaofdatamining，thisnovelitstream-orientedalgorithmisproposedandthuscouldsolvetheproblemofrepeatedscansoftheoriginaldata，reducethedatabaseoperationsbyusingpruningmethodinfrequentitemsetmining，andimprovethesearchefficiencyoffrequentsequences.[Keywords]datamining；frequentitemset；bitstream；frequentsequence；pruning面向比特流的频繁模式序列挖掘算法*收稿日期：2022-11-25作者简介：金凌，11016年生，女，硕士研究生，研究方向：信息安全；邱卫东，1973年生，男，上海交通大学信息安全工程学院，副教授，研究方向：密码学、信息安全；杨小牛，1961年生，男，研究方向：电子对抗；杨红娃，1973年生，男，研究方向：电子对抗。*基金项目：国家863项目“基于虚拟隔离的数据安全防护技术研究”资助(编号2022AA01Z426)。0引言随着信息科技的不断发展，电子对抗日益激烈。通过电子对抗侦察获得的各种信息，如何对其进行进一步分析利用是一个涉及面很广的课题。对于截获的纯比特流，要从其中寻找特征模式序列最直接的方法无疑是进行模式匹配。模式匹配自1977年Boyer-Moore[1]算法和KMP[2]算法提出以来，匹配效率较纯暴力方法有了很大的提高[3]。但在处理比特流时，需要注意两个问题：首先，比特流数据的起始位未必是一个完整字节的起始位，因此必须将比特位作为基本的匹配单位；其次，寻找过程必须枚举所有二进制候选序列分别进行匹配，而每一次模式匹配都需要完整扫描一次源数据，即有多少候选序列就必须扫描多少次源数据。综合这两个问题，利用模式匹配虽然能够解决问题，但是时间和空间的代价仍然很高。传统模式匹配在处理比特流数据中遇到的困难，可以通过引入数据挖掘中的思想来解决。数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系的信息的过程。数据挖掘的方法主要包括聚集、分类、回归和关联规则学习等。其中，关联规则学习中的频繁集挖掘与比特流的频繁模式序列具有一定的相似之处。频繁集挖掘有Apriori[4]、Elact[5]和FP-Growth[6]等经典算法，这些算法对于比特流中的频繁模式序列寻找具有相当的参考价值。然而，比特流的模式序列与数据库项集的挖掘又不完全相同，这里借鉴频繁集挖掘中的FP-Growth算法，结合比特流本身的特征，提出了面向比特流的频繁模式序列挖掘算法。本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！