Conference Paper
Title: Faster DFAs Through Simple and Efficient Inverse Homomorphisms
Authors: Domenico Ficara, Stefano Giordano, Gregorio Procissi, Fabio Vitucci, Gianni Antichi, Andrea Di Pietro

Conference: Infocom2009, Rio de Janeiro, Brazil, April 2009
Abstract: Deep Packet Inspection is required to be performed by a large number of modern network devices at high speed, to enforce network ecurity and provide applicationspecific services. In state-of-the-art systems, data sets of the signatures to be searched are described by regular expressions and finite automata (FAs) are employed to perform the search. However, current signature sets need a large amount of memory to be
searched with deterministic FAs (DFAs) while with non-deterministic automata (NFAs) several memory accesses per byte may occur. Many recent works have addressed these issues and reduced the memory footprint of DFAs. These memory reductions help fitting the required data-structures in smaller and faster memories, thus resulting in a matching speed increment. This paper, instead, focuses on speed multiplication by enlarging the amount of bytes observed in the text. The target is to modify a DFA in order to search for k bytes per state-traversal, thus obtaining a k-step DFA. For this purpose, an effective yet simple inverse homomorphism is employed to reduce the amount of transitions. The inverse homomorphism we use is fast, easily implementable and it considerably simplifies the creation of k-step DFAs. The algorithm also proves to be a good compression scheme for regular DFA that is orthogonal to other schemes.