An Improved DFA for Fast Regular Expression Matching

被引：101

作者：

Ficara, Domenico ^{[1
]}

Giordano, Stefano ^{[1
]}

Procissi, Gregorio ^{[1
]}

Vitucci, Fabio ^{[1
]}

Antichi, Gianni ^{[1
]}

Di Pietro, Andrea ^{[1
]}

机构：

[1] Univ Pisa, Dept Informat Engn, Pisa, Italy

来源：

ACM SIGCOMM COMPUTER COMMUNICATION REVIEW | 2008年 / 38卷 / 05期

关键词：

Algorithms; Design; Security; DFA; Intrusion Prevention; Deep Packet Inspection; Regular Expressions; Packet Classification;

D O I：

10.1145/1452335.1452339

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Modern network devices need to perform deep packet inspection at high speed for security and application-specific services. Finite Automata (FAs) are used to implement regular expressions matching, but they require a large amount of memory. Many recent works have proposed improvements to address this issue. This paper presents a new representation for deterministic finite automata (orthogonal to previous solutions), called Delta Finite Automata (delta FA), which considerably reduces states and transitions and requires a transition per character only, thus allowing fast matching. Moreover, a new state encoding scheme is proposed and the comprehensive algorithm is tested for use in the packet classification area.

引用

页码：31 / 40

页数：10

共 28 条

[1] EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH
AHO, AV
CORASICK, MJ
[J]. COMMUNICATIONS OF THE ACM, 1975, 18 (06) : 333 - 340
[2] AHO AV, 1985, COMPILERS PRINCIPLES
[3] [Anonymous], CLASSBENCH PACKET CL
[4] [Anonymous], SNORT LIGHTW INTR DE
[5] Becchi M., 2007, P 2007 ACM CONEXT C, P1
[6] Becchi M., REGEX TOOL
[7] Becchi M., 2007, P INFOCOM 2007 MAY
[8] Becchi Michela, 2007, P 2007 ACM IEEE S AR, P145, DOI DOI 10.1145/1323548.1323573
[9] *BRO, 2003, BRO SYST DET NETW IN
[10] Brodie B. C., 2006, P ISCA 06 JUN

← 1 2 3 →