A Comparative Study on DFA-Based Pattern Matching for Deep Packet Inspection
- 1 November 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 255-260
Abstract
Most of the network security applications in today's networks are based on Deep Packet Inspection (DPI). It is a form of computer network packet filtering that examines not only the header portion but also the payload part of a packet as it passes through an inspection point, searching for protocol noncompliance, viruses, Spam, intrusions or some predefined criteria to decide if the packet can pass it or it needs to be routed to a different destination. Most of the systems that perform deep packet inspection implement basic string matching algorithms to match packets against large but finite strings. However, there is growing interest in the use of regular expression-based pattern matching, since regular expressions offer superior expressive power. DFA is employed to implement regular expression matching. DFA representations of a regular expression sets in network applications require large amounts of memory, limiting their practical application. This paper presents an analysis of different compact representation of DFA such as D 2 FA, δFA, δ 2 FA.Keywords
This publication has 11 references indexed in Scilit:
- Differential Encoding of DFAs for Fast Regular Expression MatchingIEEE/ACM Transactions on Networking, 2010
- Second-Order Differential Encoding of Deterministic Finite Automata2009
- Efficient regular expression evaluation2008
- 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
- Advanced algorithms for fast and scalable deep packet inspection2006
- A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching2006