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

• 软件技术与数据库 • 上一篇    下一篇

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

刘 鹏,姚 远,邰 铭,张 铮   

  1. (解放军信息工程大学信息工程学院,郑州 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   

  1. (Institute of Information Engineering, PLA Information Engineering University, Zhengzhou 450002)
  • Online:2010-06-20 Published:2010-06-20

摘要:

分析现有方法处理状态爆炸的局限性,将条件函数和位图结构引入自动机,提出一种位图移位有限自动机(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

中图分类号: