一种面向大规模URL过滤的多模式串匹配算法

被引：12

作者：

刘燕兵 ^{[1
,2
]}

邵妍 ^{[3
]}

王勇 ^{[4
]}

刘庆云 ^{[1
,2
]}

郭莉 ^{[1
,2
]}

机构：

[1] 中国科学院信息工程研究所

[2] 信息内容安全技术国家工程实验室

[3] 北京邮电大学计算机学院

[4] 不详

来源：

计算机学报 | 2014年 / 37卷 / 05期

关键词：

多模式串匹配; URL过滤; 最优窗口选择; 模式串分组规约; 信息安全; 网络安全;

D O I：

暂无

中图分类号：

TP391.1 [文字信息处理]; TP393.08 [];

学科分类号：

0839 ; 1402 ;

摘要：

对大量有害的URL进行过滤,是目前网络安全应用系统中所亟需的关键技术.使用经典的串匹配算法检测庞大的URL规则集,需要消耗大量的计算资源和存储资源,性能十分低下.该文设计了一种适合于大规模URL过滤的多模式串匹配算法——SOGOPT.该算法在经典的SOG算法基础上,针对URL规则的特点,提出了最优窗口选择、模式串分组规约这两种优化技术,大幅度提高了SOG算法的匹配速度,在大规模URL规则集上效果尤其显著.该文设计的算法非常适合于大规模(100万级)URL实时在线匹配的应用环境.

引用

页码：1159 / 1169

页数：11

共 11 条

[1] 基于存储优化的多模式串匹配算法 [J].

刘燕兵 ;

刘萍 ;

谭建龙 ;

郭莉 .

计算机研究与发展, 2009, 46 (10) :1768-1776

[2] 一种高速精确单模式串匹配算法 [J].

范洪博 ;

姚念民 .

计算机研究与发展, 2009, 46 (08) :1341-1348

[3] 多模式匹配算法及硬件实现 [J].

李伟男 ;

鄂跃鹏 ;

葛敬国 ;

钱华林 .

软件学报, 2006, (12) :2403-2415

[4] 一种时间复杂度最优的精确串匹配算法 [J].

贺龙涛 ;

方滨兴 ;

余翔湛 .

软件学报, 2005, (05) :676-683

[5] 一种用于内容过滤和检测的快速多关键词识别算法 [J].

宋华 ;

戴一奇 .

计算机研究与发展, 2004, (06) :940-945

[6] 两种对URL的散列效果很好的函数 [J].

李晓明 ;

凤旺森 .

软件学报, 2004, (02) :179-184

[7] 改进的多模式匹配算法 [J].

王永成 ;

沈州 ;

许一震 ;

不详 .

计算机研究与发展 , 2002, (01) :55-60

[8]

Multipattern string matching with q -grams[J] . Leena Salmela,Jorma Tarhio,Jari Kyt?joki.Journal of Experimental Algorithmics （JEA） . 2007

[9]

Fast and flexible string matching by combining bit-parallelism and suffix automata[J] . Gonzalo Navarro,Mathieu Raffinot.Journal of Experimental Algorithmics （JEA） . 2000

[10] A NEW APPROACH TO TEXT SEARCHING [J].

BAEZAYATES, R ;

GONNET, GH .

COMMUNICATIONS OF THE ACM, 1992, 35 (10) :74-82

← 1 2 →