Performing deep packet inspection at high speed is a fundamental task for network security and application-specific services. In state-of-the-art systems, sets of signatures to be searched are described by regular expressions, and finite automata (FAs) are employed for the search. In particular, deterministic FAs (DFAs) need a large amount of memory to represent current sets, therefore the target of many works has been the reduction of memory footprint of DFAs. This paper, instead, focuses on speed multiplication by enlarging the amount of bytes observed in the text (i.e., searching for k-bytes per state-traversal). For this purpose, an interesting yet simple inverse homomorphism is employed to reduce the amount of transitions in the modified DFA. The algorithm results to be remarkably faster than standard DFAs, and provides also a good compression scheme that is orthogonal to other schemes.

Faster DFAs Through Simple and Efficient Inverse Homomorphisms

GIORDANO, STEFANO;PROCISSI, GREGORIO;VITUCCI, FABIO;ANTICHI, GIANNI;
2009-01-01

Abstract

Performing deep packet inspection at high speed is a fundamental task for network security and application-specific services. In state-of-the-art systems, sets of signatures to be searched are described by regular expressions, and finite automata (FAs) are employed for the search. In particular, deterministic FAs (DFAs) need a large amount of memory to represent current sets, therefore the target of many works has been the reduction of memory footprint of DFAs. This paper, instead, focuses on speed multiplication by enlarging the amount of bytes observed in the text (i.e., searching for k-bytes per state-traversal). For this purpose, an interesting yet simple inverse homomorphism is employed to reduce the amount of transitions in the modified DFA. The algorithm results to be remarkably faster than standard DFAs, and provides also a good compression scheme that is orthogonal to other schemes.
2009
9781424435128
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/196256
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact