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