基于位置差的特征序列挖掘快速算法

来源：电讯技术杂志2021年第7期北京时间：

作者：潘向荣,王婷

单位：(中国西南电子技术研究所，成都 610036;电子科技大学 通信抗干扰技术国家级重点实验室，成都 611730)

摘要：面向比特流的未知通信协议识别技术是现代电子侦察技术的重要组成内容。首先分析了AC(AhoCorasick)快速统计算法及基于位置差的长序列拼接算法，并指出了这两个算法存在的不足。采用数组代替二叉树存储比特流中模式序列的位置信息，并通过构造使得数组下标值与二叉树节点值保持一致的关系式，有效降低了对模式序列进行计数及筛选的时间复杂度。进一步，将数组元素依照对应频繁序列出现位置的先后顺序从左到右进行重新排列，提出了基于位置差的特征序列挖掘改进算法。最后，使用Wireshark截取100个地址解析协议（Address Resolution Protocol,ARP）数据包进行仿真验证。结果表明，与原算法相比，改进算法的时间复杂度至少可降低一个数量级。

关键词：未知通信协议识别；特征序列挖掘；数据帧结构；情报信息；比特流；