Michela Becchi
ABSTRACT
Modern network intrusion detection systems need to perform regular expression matching at line rate in order to detect the occurrence of critical patterns in packet payloads. While deterministic finite automata (DFAs) allow this operation to be performed in linear time, they may exhibit prohibitive memory requirements. In [9], Kumar et al. propose Delayed Input DFAs (D2FAs), which provide a trade-off between the memory requirements of the compressed DFA and the number of states visited for each character processed, which corresponds directly to the memory bandwidth required to evaluate regular expressions.
In this paper we introduce a general compression technique that results in at most 2N state traversals when processing a string of length N. In comparison to the D2FA approach, our technique achieves comparable levels of compression, with lower provable bounds on memory bandwidth (or greater compression for a given bandwidth bound). Moreover, our proposed algorithm has lower complexity, is suitable for scenarios where a compressed DFA needs to be dynamically built or updated, and fosters locality in the traversal process. Finally, we also describe a novel alphabet reduction scheme for DFA-based structures that can yield further dramatic reductions in data structure size.
- A. V. Aho and M. J. Corasick, "Efficient String Matching: An Aid to Bibliographic Search," Communication of ACM, 1975. Google Scholar
Digital Library
- J. E. Hopcroft and J. D. Ullman, "Introduction to Automata Theory, Languages, and Computation," Addison Wesley, 1979. Google ScholarDigital Library
- J. Hopcroft, "An nlogn algorithm for minimizing states in a finite automaton," in Theory of Machines and Computation, J. Kohavi, Ed. New York: Academic, 1971, pp. 189--196.Google Scholar
- R. Prim, "Shortest connection networks and some generalizations," Bell System Technical Journal, 1957.Google ScholarCross Ref
- J. B. Kruskal, "On the shortest spanning subtree of a graph and the traveling salesman problem," Proc. of the American Mathematical Society, Vol. 7, No. 1. (Feb., 1956), pp. 48--50.Google ScholarCross Ref
- Y. J. Chu and T. H. Liu, "On the shortest arborescence of a directed graph", Science Sinica, v.14, 1965, pp. 1396--1400.Google Scholar
- J. Edmonds, "Optimum branchings", J. Research of the National Bureau of Standards, 71B, 1967, pp.233--240.Google ScholarCross Ref
- R. E. Tarjan, "Data Structures and Network Algorithms," SIAM 1983. Google ScholarDigital Library
- S. Kumar et alt., "Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection," in ACM SIGCOMM, Sept 2006. Google ScholarDigital Library
- M. Roesch, "SNORT: Lightweight Intrusion Detection for Networks," in 13th System Administration Conf., Nov 1999. Google ScholarDigital Library
- SNORT: http://www.snort.orgGoogle Scholar
- Bro: A System for Detecting Network Intruders in Real-Time. http://www.icir.org/vern/bro-info.htmlGoogle Scholar
- Cisco Systems. Cisco Adaptive Security Appliance. http://www.cisco.com. 2007.Google Scholar
- Citrix Systems. Citrix Application Firewall. http://www.citrix.com. 2007.Google Scholar
- F. Yu et alt., "Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection", in ANCS 2006. Google ScholarDigital Library
- S. Kumar, J. Turner and J. Williams, "Advanced Algorithms for Fast and Scalable Deep Packet Inspection", in ANCS 2006. Google ScholarDigital Library
- S. Sen et alt., "Accurate, Scalable In-network Identification of P2P Traffic Using Application Signatures", in Proc. of the XIII Intl. WWW Conf., New York City, May 2004. Google ScholarDigital Library
- N. Tuck et alt., "Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection", in IEEE Infocom, pp. 333--340, Mar 2004.Google Scholar
- G. Varghese, "Network Algorithms: An Interdisciplinary Approach to Designing Fast Networked Devices", Morgan Kaufmann, 1st ed., 2004. Google ScholarDigital Library
- R. Sommer and V. Paxson, "Enhancing byte-level network intrusion detection signatures with context.", in ACM CCS 2003. Google ScholarDigital Library
- R. Sidhu and V. K. Prasanna, "Fast Regular Expression Matching using FPGAs", in FCCM 2001. Google ScholarDigital Library
- C. R. Clark and D. E. Schimmel, "Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns," In FPL 2003.Google Scholar
- J. Moscola, J. Lockwood, R. P. Loui, and M. Pachos, "Implementation of a content-scanning module for an internet firewall," in FCCM, Napa, CA, USA, April 2003. Google ScholarDigital Library
- http://www.tensilica.comGoogle Scholar
- Cisco Systems. Silicon Packet Processor in the CRS-1 Router. http://www.cisco.com/en/US/products/ps5763/index.htmlGoogle Scholar
- M. Adiletta et al., "The Next Generation of Intel IXP Network Processors", in Intel Tech. Journal, Vol. 6, Iss 3, 2002.Google Scholar
Index Terms
- An improved algorithm to accelerate regular expression evaluation
Recommendations
An improved DFA for fast regular expression matching
Modern network devices need to perform deep packet inspection at high speed for security and application-specific services. Finite Automata (FAs) are used to implement regular expressions matching, but they require a large amount of memory. Many recent ...
Algorithms to accelerate multiple regular expressions matching for deep packet inspection
Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communicationsThere is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems that perform deep packet inspection implement ...
Algorithms to accelerate multiple regular expressions matching for deep packet inspection
SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communicationsThere is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems that perform deep packet inspection implement ...
Comments