IJSSAN

RECONFIGURABLE SELF-ADDRESSABLE MEMORY-BASED FSM A SCALABLE INTRUSION DETECTION ENGINE

---

---

Abstract

One way to detect and thwart a network attack is to compare each incoming packet with predefined patterns, also Called an attack pattern database, and raise an alert upon detecting a match. This article presents a novel pattern-matching Engine that exploits a memory-based, programmable state machine to achieve deterministic processing rates that are Independent of packet and pattern characteristics. Our engine is a self addressable memory based finite state machine (samFsm), whose current state coding exhibits all its possible next states. Moreover, it is fully reconfigurable in that new attack Patterns can be updated easily. A methodology was developed to program the memory and logic. Specifically, we merge “non-equivalent” states by introducing “super characters” on their inputs to further enhance memory efficiency without Adding labels. This is the most high speed self addressable memory based fsm.sam-fsm is one of the most storage-Efficient machines and reduces the memory requirement by 60 times. Experimental results are presented to demonstrate the Validity of sam-fsm.

Recommended Citation

[1] A. Aho and M. Corasick, “Efficient String Matching: An Aid to Bibliographic Search,” Commun. ACM, vol. 18, 1975. [2] B. Commentz-Walter, “A String Matching Algorithm Fast on the Average,” Proc. 6th Int’l. Colloquium Automata, Languages, and Programming, vol. 71, 1979. [3] S. Wu and U. Manber, “A Fast Algorithm for Multi-Pattern Searching,” Tech. Rep. TR94-17, Dept. of Comp. Sci., Univ. of AZ, 1994. [4] K.-K. Tseng et al., “A Parallel Automaton String Matching with Pre-Hashing and Root-Indexing Techniques for Content Filtering Coprocessor,” Proc. 2005 IEEE Int’l. Conf. App-Specific Sys., Architecture Processors, 2005, pp. 113–18. [5] S. Dharmapurikar et al., “Deep Packet Inspection Using Parallel Bloom Fil-ters,” IEEE Micro, vol. 24, no. 1, Jan. 2004, pp. 52–61. [6] I. Sourdis et al., “Packet Pre-Filtering for Network Intrusion Detection,” Proc. 2006 ACM/IEEE Symp. Architecture for Net. Commun. Sys., pp. 183–92. [7] M. Aldwairi, T. Conte, and P. Franzon, “Configurable String Matching Hard-ware for Speeding Up Intrusion Detection,” SIGARCH Comp. Archit. News, vol. 33, no. 1, 2005, pp. 99–107. [8] Y. H. Cho, S. Navab, and W. H. Mangione-Smith, “Specialized Hardware for Deep Network Packet Filtering,” Proc. Reconfigurable Comp. Going Mainstream, 12th Int’l. Conf. Field-Programmable Logic and Applications (FPL‘02), 2002, pp. 452–61. [9] Snort, Snort Rule Database, 2007; http://www.snort.org/pubbin/ downloads.cgi [10] N. Tuck et al., “Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection,” Proc. IEEE INFOCOM, 2004, pp. 333–40