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

杨天龙; 张宏莉

doi:10.3969/j.issn.1000-0801.2013.01.006

您当前的位置：

首页 >

文章列表页 >

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

研究与开发 | 更新时间：2024-06-05

- 一种关键字表达式的匹配优化方法
- Optimization of Expression Matching for String Matching
- 电信科学 2013年29卷第1期页码：39-45
- 作者机构：
- 作者简介：
  
  [ "杨天龙，男，哈尔滨工业大学博士研究生，主要研究方向为大规模特征集串匹配技术。" ]
  [ "张宏莉，女，博士，哈尔滨工业大学教授、博士生导师，主要研究方向为网络与信息安全、网络测量与建模、网络计算、并行处理等。" ]
- 基金信息：
  
  国家重点基础研究发展计划（“973”计划）基金资助项目;The National Basic Research Program of China （973 Program）(2011CB302605);国家自然科学基金资助项目(61173145)
- DOI：10.3969/j.issn.1000-0801.2013.01.006
  中图分类号：
- 网络出版日期：2013-01-20，
  
  纸质出版日期：2013-01-20
- 稿件说明：
移动端阅览
杨天龙, 张宏莉. 一种关键字表达式的匹配优化方法[J]. 电信科学, 2013,29(1):39-45.

Tianlong Yang, Hongli Zhang. Optimization of Expression Matching for String Matching[J]. Telecommunications science, 2013, 29(1): 39-45.
杨天龙, 张宏莉. 一种关键字表达式的匹配优化方法[J]. 电信科学, 2013,29(1):39-45. DOI： 10.3969/j.issn.1000-0801.2013.01.006.

Tianlong Yang, Hongli Zhang. Optimization of Expression Matching for String Matching[J]. Telecommunications science, 2013, 29(1): 39-45. DOI： 10.3969/j.issn.1000-0801.2013.01.006.

摘要

随着网络安全应用需求的增加，内容检测系统中特征模式集规模不断增长，模式间的冗余重复越来越多。大量模式间的冗余重复直接影响了系统的资源使用率和检测性能。本文首先对表达式的包含关系做了分类，提出了表达式冗余消除算法，然后在BitCount 算法的基础上提出了一种时间复杂度为O（1）的掩码验证算法MaskVeri。实验结果表明，改进后的算法性能更高。

Abstract

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 O（1）algorithm（MaskVeri）for mask verification was designed. The experimental result shows that MaskVeri performs better than other programming realization.

关键词

Keywords

references

Aho A , Corasick M . Efficient string matching: an aid to bibliographic search . Communications of the ACM , 2008 : 333 - 340

Snort 2.4.x . http://www.snort.org http://www.snort.org , 2006

Clam antiVirus . http://www.clamav.org http://www.clamav.org , 2006

王德才，徐建国，吴哲辉等 . 布尔表达式的化简与并行排序网络验证 . 计算机工程与设计， 2009 ( 14 ): 3322 ～ 3325

Asli B H S.Survey of a new note on karnaugh maps . International Journal of Control and Automation , 2012 , 5 ( 2 ): 21 ～ 24

Jadhav V , Buchade A . Modified quine-McCluskey method.CoRR , 2012 ( 2289 ): 1 ～ 4

Karnough M . The map method for synthesis of combinational logic circuits . AIEE , 1953 : 593 ～ 599

McCluskey E J . Minimization of Boolean function . Bell System Tech Journal , 1956 , 35 ( 5 ): 1417 ～ 1444

曹京，谭建龙，刘萍等 . 布尔表达式匹配问题研究 . 计算机应用研究， 2007 ( 9 ): 70 ～ 72,108

曹京，刘燕兵，刘萍等 . 定序窗口布尔表达式匹配技术研究 . 通信学报， 2007 ( 12 ): 125 ～ 130

张树壮 . 面向网络安全的高性能特征匹配技术研究 . 哈尔滨工业大学博士学位论文， 2011

宋云，龙际珍 . 规则数量无关的多布尔表达式匹配算法 . 软件导刊， 2012 ( 3 ): 57 - 59

浏览量

332

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据