Abstract
In the midst of vastly numbered and quickly growing internet security threats, Network Intrusion Detection System (NIDS) becomes more important to network security every day. Vital to effective NIDS is a multi-pattern matching engine which requires deterministic performance and adaptability to new threats. Memory-based Deterministic Finite Automata (DFA) are ideal for pattern matching but have severe memory requirements that make them difficult to implement. Many previous heuristic techniques have been proposed to reduce memory requirements, however in this paper, we aim to effectively understand the basic relationship between DFA characteristics and memory, in order to create minimal memory DFA implementations. We show what DFA characteristics either cause or reduce memory requirements, as well as how to optimize DFA to exploit those characteristics. Specifically, we introduce the concepts of State Independence and State Irregularity, which are DFA characteristics that can reduce memory waste and allow for memory reuse. Furthermore, we introduce DFA normalization which optimizes DFA to fully exploit these characteristics. Altogether this work serves as a source for how to extract and utilize DFA characteristics to create minimal memory implementations.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aho, A., Corasick, M.: Efficient string matching: An aid to bibliographic search. Communications of the ACM 18 (1975)
Brodie, B.C., Taylor, D.E., Cytron, R.K.: A scalable architecture for high-throughput regular-expression pattern matching. SIGARCH Comput. Archit. News 34(2), 191–202 (2006)
Roesch, M.: Snort – lightweight intrusion detection for networks. In: Proc. of the 13th Systems Administration Conference (1999)
Varghese, G.: Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, 1st edn. Morgan Kaufmann, San Francisco (2005)
Bu, L., Chandy, J.A.: Fpga based network intrusion detection using content addressable memories. In: FCCM 2004: Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Washington, DC, USA, pp. 316–317 (2004)
Tuck, N., Sherwood, T., Calder, B., Varghese, G.: Deterministic memory-efficient string matching algorithms for intrusion detection. In: Proc. of the IEEE Infocom Conference, pp. 333–340 (2004)
Yu, F., Chen, Z., Diao, Y., Lakshman, T., Katz, R.H.: Fast and memory-efficient regular expression matching for deep packet inspection. EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2006-76 (May 2006)
Fisk, M., Varghese, G.: Applying fast string matching to intrusion detection, los Alamos National Lab Report (2002)
Becchi, M., Crowley, P.: An improved algorithm to accelerate regular expression evaluation. In: Proc. of ANCS, pp. 145–154. ACM, Orlando (2007)
Kumar, S., Dharmapurikar, S., Yu, F., Crowley, P., Turner, J.: Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: Proc. of ACM SIGCOMM, pp. 339–350. ACM, New York (2006)
van Lunteren, J.: High-performance pattern-matching for intrusion detection. In: INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pp. 1–13 (2006)
Smith, R., Estan, C., Jha, S., Kong, S.: Deflating the big bang: fast and scalable deep packet inspection with extended finite automata. In: SIGCOMM 2008: Proceedings of the ACM SIGCOMM 2008 conference on Data communication, New York, USA, pp. 207–218 (2008)
Snort Rule Database, Snort (2009), http://www.snort.org/pub-bin/downloads.cgi
Soewito, B., et al.: Self addressable memory-based fsm (sam-fsm): A scalable intrusion detection engine. IEEE Network Special Issue on Recent Developments in Network Intrusion Detection 23(1), 14–21 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vespa, L., Weng, N. (2009). Deterministic Finite Automata Characterization for Memory-Based Pattern Matching. In: Qing, S., Mitchell, C.J., Wang, G. (eds) Information and Communications Security. ICICS 2009. Lecture Notes in Computer Science, vol 5927. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11145-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-11145-7_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11144-0
Online ISBN: 978-3-642-11145-7
eBook Packages: Computer ScienceComputer Science (R0)