一种高效匹配PCRE的扩展自动机

doi:10.3969/j.issn.1000-3428.2010.12.014

计算机工程 ›› 2010, Vol. 36 ›› Issue (12): 39-42.doi: 10.3969/j.issn.1000-3428.2010.12.014

一种高效匹配PCRE的扩展自动机

刘鹏，姚远，邰铭，张铮

(解放军信息工程大学信息工程学院，郑州 450002)

出版日期:2010-06-20 发布日期:2010-06-20
作者简介:刘鹏(1981－)，男，硕士研究生，主研方向：并行计算，网络安全；姚远、邰铭、张铮，副教授
基金项目:
国家“863”计划基金资助项目(2006AA01Z408)

Efficient Extended Automaton Matching Perl-Compatible Regular Expressions

LIU Peng, YAO Yuan, TAI Ming, ZHANG Zheng

(Institute of Information Engineering, PLA Information Engineering University, Zhengzhou 450002)

Online:2010-06-20 Published:2010-06-20

摘要/Abstract

摘要：

分析现有方法处理状态爆炸的局限性，将条件函数和位图结构引入自动机，提出一种位图移位有限自动机(Bs-FA)，并给出由正则表达式到Bs-FA的一般方法。对计数字符组与前缀交迭的情况，仅需引入较小位图空间，就能使整个自动机内存空间明显减少。在实际规则集上评估，并与现有方法进行比较，说明该自动机的应用价值。

关键词: 确定的有限自动, 深度包检测, 正则表达式

Abstract:

The limitation of existing method is analysed, Bitmap shift Finite Automaton(Bs-FA) is proposed by introducing condition function and bitmap structure, and the general method is provided to create Bs-FA from regular expression. In the condition of class of characters which overlaps with prefix, additional less space can reduce the memory storage remarkably. Bs-FA is evaluated on current rule sets and it has an important application value by comparing with recent methods.

Key words: Deterministic Finite Automaton(DFA), deep packet inspection, regular expression

中图分类号:

TP311

刘鹏, 姚远, 邰铭, 张铮. 一种高效匹配PCRE的扩展自动机[J]. 计算机工程, 2010, 36(12): 39-42.

LIU Feng, TAO Yuan, TAI Ming, ZHANG Zheng. Efficient Extended Automaton Matching Perl-Compatible Regular Expressions[J]. Computer Engineering, 2010, 36(12): 39-42.

[1]	王翔,卢毓海,马伟,刘燕兵. 一种针对DFA状态爆炸的正则表达式匹配方法[J]. 计算机工程, 2019, 45(4): 148-156.
[2]	杨嘉佳,姜腊林,姜磊,戴琼,谭建龙. 基于簇聚类和游程编码的正则表达式压缩算法 [J]. 计算机工程, 2014, 40(8): 282-287,292.
[3]	魏强, 李云照, 褚衍杰. 基于图划分的正则表达式分组算法[J]. 计算机工程, 2012, 38(18): 137-139.
[4]	唐彰国, 李焕洲, 钟明全, 张健. 基于网络通信指纹的启发式木马识别系统[J]. 计算机工程, 2011, 37(17): 119-121,139.
[5]	李莲春, 周金治. 网络音视频语义信息抽取系统[J]. 计算机工程, 2011, 37(13): 269-271.
[6]	叶文晨, 汪敏, 陈云寰, 张之远. 一种联合DPI和DFI的网络流量检测方法[J]. 计算机工程, 2011, 37(10): 102-104.
[7]	郭牧怡;刘萍;谭建龙;郭莉. 基于文件标题特征的网络视频去重研究[J]. 计算机工程, 2010, 36(9): 227-229,.
[8]	田里. NIDS中正则表达式匹配电路的改进与优化[J]. 计算机工程, 2010, 36(3): 136-138.
[9]	金军航, 张大方, 黄昆. 高性能正则表达式匹配算法评估[J]. 计算机工程, 2010, 36(19): 269-271.
[10]	宋友;梁士兴;黄璐;. 通用文本处理方法的研究与设计[J]. 计算机工程, 2010, 36(06): 1-4.
[11]	董敏;毕盛;齐德昱. 基于正则表达式的测试数据自动生成技术[J]. 计算机工程, 2009, 35(16): 29-31.
[12]	王功明;吴华瑞;赵春江;杨宝祝. 正则表达式在电子政务客户端校验中的应用[J]. 计算机工程, 2007, 33(09): 269-271.
[13]	张毅坤;侯宇明;崔杜武. 基于有限状态自动机的构件化软件集成测试方法[J]. 计算机工程, 2006, 32(18): 75-78.

一种高效匹配PCRE的扩展自动机

Efficient Extended Automaton Matching Perl-Compatible Regular Expressions

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

Metrics

本文评价

推荐阅读 10