Abstract
Signature-based network intrusion detection requires fast and reconfigurable pattern matching for deep packet inspection. This paper presents a novel pattern matching engine, which exploits a memory-based programmable state machine to achieve deterministic processing rates that are independent of packet and pattern characteristics. Our engine is a portable predictive pattern matching finite state machine (P 3 FSM), which combines the properties of hardware-based systems with the portability and programmability of software. Specifically we introduce two methods, “Character Aware” and “SDFA”, for encoding predictive state codes which can forecast the next states of our FSM. The result is software based pattern matching which is fast, reconfigurable, memory-efficient and portable.
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
Baker, Z., Prasanna, V.K.: A methodology for synthesis of efficient intrusion detection systems on FPGAs. In: Proc. of the IEEE Conference on Field-Programmable Custom Computing Machines, Napa, CA, April 2004, pp. 135–144 (2004)
Becchi, M., Crowley, P.: An improved algorithm to accelerate regular expression evaluation. In: Proc. of ACM/IEEE Symposium on Architectures for Networking and Communications Systems, Orlando, FL, December 2007. ACM, New York (2007)
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)
Denning, D.: An intrusion–detection model. IEEE Transactions on Software Engineering 13(2), 222–232 (1987)
Fisk, M., Varghese, G.: Applying fast string matching to intrusion detection, Los Alamos National Lab Report (2002)
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)
Mahajan, A., Soewito, B., Parsi, S.K., Weng, N., Wang, H.: Implementing High-speed String Matching Hardware for Network Intrusion Detection Systems. In: Proc. of Sixteenth ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA), Monterey, CA (2008)
Roesch, M.: Snort – lightweight intrusion detection for networks. In: Proc. of the 13th Systems Administration Conference (1999)
Soewito, B., Vespa, L., Mahajan, A., Weng, N., Wang, H.: Self Addressable Memory-based FSM (SAM-FSM): A Scalable Intrusion Detection Engine. IEEE network 23(1), 14–21 (2009)
Wu, S., Manber: A fast algorithm for multi-pattern searching. Technical Report TR94-17, Department of Computer Science, University of Arizona (1994)
Aho, A., Corasick, M.: Efficient string matching: An aid to bibliographic search. Communications of the ACM 18 (1975)
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)
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., Mathew, M., Weng, N. (2009). Predictive Pattern Matching for Scalable Network Intrusion Detection. 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_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-11145-7_20
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)