Deep packet inspection is a fundamental task to improve network security and provide application-specific services. State-of-the-art systems adopt regular expressions due to their high expressive power. They are typically matched through deterministic finite automata (DFAs), but large rule sets need a memory amount that turns out to be too large for practical implementation. Many recent works have proposed improvements to address this issue, but they increase the number of transitions (and then of memory accesses) per character. This paper presents a new representation for DFAs, orthogonal to most of the previous solutions, called delta finite automata ( δFA), which considerably reduces states and transitions while preserving a transition per character only, thus allowing fast matching. A further optimization exploits Nth order relationships within the DFA by adopting the concept of “temporary transitions”.

Differential encoding of DFAs for fast regular expression matching

GIORDANO, STEFANO;PROCISSI, GREGORIO;VITUCCI, FABIO;ANTICHI, GIANNI
2011

Abstract

Deep packet inspection is a fundamental task to improve network security and provide application-specific services. State-of-the-art systems adopt regular expressions due to their high expressive power. They are typically matched through deterministic finite automata (DFAs), but large rule sets need a memory amount that turns out to be too large for practical implementation. Many recent works have proposed improvements to address this issue, but they increase the number of transitions (and then of memory accesses) per character. This paper presents a new representation for DFAs, orthogonal to most of the previous solutions, called delta finite automata ( δFA), which considerably reduces states and transitions while preserving a transition per character only, thus allowing fast matching. A further optimization exploits Nth order relationships within the DFA by adopting the concept of “temporary transitions”.
Ficara, D; Di Pietro, A; Giordano, Stefano; Procissi, Gregorio; Vitucci, Fabio; Antichi, Gianni
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: http://hdl.handle.net/11568/189239
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 33
  • ???jsp.display-item.citation.isi??? 16
social impact