大规模多串匹配算法的访存行为分析

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (26): 106-109.

大规模多串匹配算法的访存行为分析

陈小军¹,张志斌¹,刘燕兵¹,郭莉²

1.中国科学院计算技术研究所,北京 100080
2.中国科学院研究生院,北京 100039

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-11 发布日期:2007-09-11
通讯作者: 陈小军

Charactering memory access behavior of large scale multi-string matching algorithms

CHEN Xiao-jun¹,ZHANG Zhi-bin¹,LIU Yan-bing¹,GUO Li²

1.Institution of Computing Technology,Chinese Academy of Science,Beijing 100080,China
2.Graduate University of Chinese Academy of Sciences,Beijing 100039,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-09-11 Published:2007-09-11
Contact: CHEN Xiao-jun

摘要/Abstract

摘要： 随着网络带宽的日益增长,病毒和非法信息的形式越来越多,网络安全系统处理的压力越来越大。多串匹配算法作为大部分网络安全系统中的核心扫描部分其性能尤为重要。从微处理器体系结构的角度,用模拟的方法分析了SBOM、AC、WM等三种精确多串匹配算法在大规模规则库的情况下,其性能影响的各种因素,特别是其访存行为特征,并从算法原理上解释了访存性为是如何被影响的。指出当规则库规模增到5 000时,由Cache失效引起的性能损失占全部开销的近10%,而且比重随着规则库规模增大而继续变大。

关键词: 多串匹配, 网络安全, 访存行为, Cache失效

Abstract: Multi-string matching algorithms,as one of the most significant parts in network security system,its performance decides the efficiency of traffic inspection.Analyze the various factors especially memory access behaviors that impact the performance of multi-string matching algorithms.In three typical algorithms,about 10% performance drops are caused by Cache misses with 5 000 patterns.The trend of the drops is enlarging with increasing patterns.

Key words: multi-string matching algorithms, network security, memory access behavior, Cache miss

陈小军¹,张志斌¹,刘燕兵¹,郭莉². 大规模多串匹配算法的访存行为分析[J]. 计算机工程与应用, 2007, 43(26): 106-109.

CHEN Xiao-jun¹,ZHANG Zhi-bin¹,LIU Yan-bing¹,GUO Li². Charactering memory access behavior of large scale multi-string matching algorithms[J]. Computer Engineering and Applications, 2007, 43(26): 106-109.

[1]	王振东，张林，李大海. 基于机器学习的物联网入侵检测系统综述[J]. 计算机工程与应用, 2021, 57(4): 18-27.
[2]	曹磊，李占斌，杨永胜，赵龙飞. 基于双层注意力神经网络的入侵检测方法[J]. 计算机工程与应用, 2021, 57(19): 142-149.
[3]	狄冲，李桐. 网络未知攻击检测的深度学习方法[J]. 计算机工程与应用, 2020, 56(22): 109-116.
[4]	彭春燕，杜秀娟. 水声传感器网络基于深度信息的安全路由协议[J]. 计算机工程与应用, 2020, 56(2): 76-81.
[5]	芶继军，李均华，陈晨，陈一鸣，吕奕达. 基于随机森林的网络入侵检测方法[J]. 计算机工程与应用, 2020, 56(2): 82-88.
[6]	周龙，王晨，史崯. 基于RNN的Webshell检测研究[J]. 计算机工程与应用, 2020, 56(14): 88-92.
[7]	吴德鹏，柳毅. 基于可变网络结构自组织映射的入侵检测模型[J]. 计算机工程与应用, 2020, 56(12): 81-86.
[8]	石乐义，刘佳，刘祎豪，朱红强，段鹏飞. 网络安全态势感知研究综述[J]. 计算机工程与应用, 2019, 55(24): 1-9.
[9]	张舒娟1，张娟2. 对等网络中被动型蠕虫传播动力学建模与分析[J]. 计算机工程与应用, 2019, 55(11): 60-66.
[10]	马占飞1，杨晋2，金溢2，边琦3. 基于IQPSO-IDE算法的网络入侵检测方法[J]. 计算机工程与应用, 2019, 55(10): 115-120.
[11]	冯波1，郭帆2，谭素雯3. 基于IPv6的概率包标记路径溯源方案[J]. 计算机工程与应用, 2016, 52(6): 102-106.
[12]	武鲁强，王赜. 基于位置密钥的无线自组织网络的安全机制[J]. 计算机工程与应用, 2016, 52(16): 132-136.
[13]	陈虹1，王飞1，肖振久1，2，孙丽娜1. 一种融合多源数据的网络安全态势评估模型[J]. 计算机工程与应用, 2015, 51(17): 96-101.
[14]	黄鲁娟1，3，金光1，3，何加铭2，3，江先亮1. 防御DDoS攻击的包标记联合部署方案[J]. 计算机工程与应用, 2014, 50(5): 74-78.
[15]	陈虹1，王飞1，肖振久1，2，孙丽娜1. 基于IHS_LSSVR的网络安全态势预测方法[J]. 计算机工程与应用, 2014, 50(23): 91-94.