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

A Multiple String Matching Algorithm for Large-Scale URL Filtering

作　　者：刘燕兵[1,2] 邵妍[3] 王勇[4] 刘庆云[1,2] 郭莉[1,2] 

机构地区：[1]中国科学院信息工程研究所,北京100093 [2]信息内容安全技术国家工程实验室,北京100093 [3]北京邮电大学计算机学院,北京100876 [4]国家计算机网络与信息安全管理中心,北京100029

出　　处：《计算机学报》2014年第5期1159-1169,共11页Chinese Journal of Computers

基　　金：中国科学院战略性先导科技专项课题"媒体内容安全监管技术"(XDA06030602);国家自然科学基金青年基金项目"复杂规则实时检测的模型和算法研究"(61202477)资助~~

摘　　要：对大量有害的URL进行过滤,是目前网络安全应用系统中所亟需的关键技术.使用经典的串匹配算法检测庞大的URL规则集,需要消耗大量的计算资源和存储资源,性能十分低下.该文设计了一种适合于大规模URL过滤的多模式串匹配算法——SOGOPT.该算法在经典的SOG算法基础上,针对URL规则的特点,提出了最优窗口选择、模式串分组规约这两种优化技术,大幅度提高了SOG算法的匹配速度,在大规模URL规则集上效果尤其显著.该文设计的算法非常适合于大规模(100万级)URL实时在线匹配的应用环境.The filtering of large-scale hazardous URLs plays a fundamental role in many networksecurity applications.The classical multiple string matching algorithms perform poorly on large-scale URLs,due to the heavy consumption of CPU power and memory space.Here we propose amultiple string matching algorithm-SOGOPT for large-scale URL filtering.By exploiting the characteristics of URLs,the proposed algorithm devises two strategies,i.e.the optimal window selection strategy and the pattern set partitioning and reduction strategy,to speed up the classical SOG algorithm.The proposed algorithm improves the searching speed of SOG greatly,especiallyon large-scale URLs.It is very suitable for large-scale （up to 1 million URLs）and online URL filtering.

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

分 类 号：TP309[自动化与计算机技术—计算机系统结构] TP393[自动化与计算机技术—计算机科学与技术]