一种关键字表达式的匹配优化方法  

Optimization of Expression Matching for String Matching

作　　者：杨天龙[1] 张宏莉[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院计算机网络与信息安全技术研究中心,哈尔滨150001

出　　处：《电信科学》2013年第1期39-45,共7页Telecommunications Science

基　　金：国家重点基础研究发展规划("973"计划)基金资助项目(No.2011CB302605);国家自然科学基金资助项目(No.61173145)

摘　　要：随着网络安全应用需求的增加,内容检测系统中特征模式集规模不断增长,模式间的冗余重复越来越多。大量模式间的冗余重复直接影响了系统的资源使用率和检测性能。本文首先对表达式的包含关系做了分类,提出了表达式冗余消除算法,然后在BitCount算法的基础上提出了一种时间复杂度为O(1)的掩码验证算法MaskVeri。实验结果表明,改进后的算法性能更高。As the requirement of network security application increases, more and more redundant patterns appear and the patterns＇ amount of intrusion detection system （IDS） raises. The redundant patterns affect the coefficient of utilization of system＇s resource, and the performance of IDS directly. The inclusion relationship for expression was classified, and the algorithms eliminating redundant expressions were proposed. Then, to optimize the BitCount algorithm, a theoretical 0（1） algorithm （MaskVeri） for mask verification was designed. The experimental result shows that MaskVeri performs better than other programming realization.

关 键 词：表达式匹配 掩码验证优化 表达式消除 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]