Second-Order Differential Encoding of Deterministic Finite Automata
Authors:
- Gianni AntichiGAGianni Antichi
- Andrea Di PietroAPAndrea Di Pietro
- Domenico FicaraDFDomenico Ficara
- Stefano GiordanoSGStefano Giordano
- Gregorio ProcissiGPGregorio Procissi
- Fabio VitucciFVFabio Vitucci
- 1 November 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1930529X,p. 1-6
Abstract
Deep packet inspection is required in an increasing number of network devices, in order to improve network security and provide application-specific services. Instead of standard strings to represent the data set to be matched, state-of-the-art systems adopt regular expressions, due to their high expressive power and flexibility. Typically regular expressions are matched through deterministic finite automata (DFAs), but large rule sets need a memory amount which 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. In a previous work, we have presented a smart representation for DFA which, while preserving fast matching (i.e., a transition per character only), considerably reduces states and transitions. In this paper we introduce a novel optimized automaton, which exploits second order relationships within the DFA and is based on the key concept of "temporary transitions". Results for real data sets show that it allows for a further memory saving.Keywords
This publication has 10 references indexed in Scilit:
- An improved DFA for fast regular expression matchingACM SIGCOMM Computer Communication Review, 2008
- Deflating the big bangACM SIGCOMM Computer Communication Review, 2008
- Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia2007
- An improved algorithm to accelerate regular expression evaluation2007
- A hybrid finite automaton for practical deep packet inspection2007
- Memory-Efficient Regular Expression Search Using State Merging2007
- Advanced algorithms for fast and scalable deep packet inspection2006
- Algorithms to accelerate multiple regular expressions matching for deep packet inspection2006
- Deterministic memory-efficient string matching algorithms for intrusion detection2005
- Enhancing byte-level network intrusion detection signatures with context2003