An Improved DFA for Fast Regular Expression Matching
Domenico Ficara (domenico.ficara@iet.unipi.it)
Stefano Giordano (s.giordano@iet.unipi.it)
Gregorio Procissi (g.procissi@iet.unipi.it)
Fabio Vitucci (fabio.vitucci@iet.unipi.it)
Gianni Antichi (gianni.antichi@iet.unipi.it)
Andrea Di Pietro (andrea.dipietro@iet.unipi.it)
Department of Information Engineering, University of Pisa
via G.Caruso 16, Pisa, ITALY
ABSTRACT
Modern network devices need to perform deep packet inspection at high speed for security and application-specifi c 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 nite automata (orthogonal to previous solutions), called Delta Finite Automata (dFA), 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 classi cation area.