Implementing high-speed string matching hardware for network intrusion detection systems

ABSTRACT

This paper presents a string matching hardware on FPGA for network intrusion detection systems. The proposed architecture, consisting of packet classifiers and strings matching verifiers, achieves superb throughput by using several mechanisms. First, based on incoming packet contents, the packet classifiers can dramatically reduce the number of strings to be matched for each packet and, accordingly, feed the packet to a proper verifier to conduct matching. Second, a novel multi-threading finite state machine (FSM) is proposed, which improves FSM clock frequency and allows multiple packets to be examined by a single FSM simultaneously. Design techniques for high-speed interconnect and interface circuits are also presented. Experimental results are presented to explore the trade-offs between system performance, strings partition granularity and hardware resource cost

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: Monther Aldwairi , Thomas Conte , Paul Franzon, Configurable string matching hardware for speeding up intrusion detection, ACM SIGARCH Computer Architecture News, v.33 n.1, March 2005 [doi>10.1145/1055626.1055640]
• 3: Michael Attig , John Lockwood, SIFT: Snort Intrusion Filter for TCP, Proceedings of the 13th Symposium on High Performance Interconnects, p.121-127, August 17-19, 2005 [doi>10.1109/CONECT.2005.33]
• 4: Zachary K. Baker , Viktor K. Prasanna, Time and area efficient pattern matching on FPGAs, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968312]
• 5: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 6: Long Bu , John A. Chandy, FPGA Based Network Intrusion Detection using Content Addressable Memories, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.316-317, April 20-23, 2004
• 7: Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.118-132, July 16-20, 1979
• 8: Dorothy E. Denning, An Intrusion-Detection Model, IEEE Transactions on Software Engineering, v.13 n.2, p.222-232, February 1987 [doi>10.1109/TSE.1987.232894]
• 9: S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood. Deep packet inspection using parallel bloom filters. IEEE Micro, 24(1):52--61, Jan. 2004.
• 10: S. Dharmapurikar, P. Krishnamurthy, T.S. Sproull, and J.W. Lockwood. Deep packet inspection using parallel Bloom filters. IEEE Micro, 24(1):52--61, Jan. 2004.
• 11: Rong-Tai Liu , Nen-Fu Huang , Chih-Hao Chen , Chia-Nan Kao, A fast string-matching algorithm for network processor-based intrusion detection system, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.3, p.614-633, August 2004 [doi>10.1145/1015047.1015055]
• 12: Piti Piyachon , Yan Luo, Efficient memory utilization on network processors for deep packet inspection, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185358]
• 13: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 14: Snort, Inc. The Open Source Network Intrusion Detection System, 2004. http://www.snort.org.
• 15: Haoyu Song , John W. Lockwood, Efficient packet classification for network intrusion detection using FPGA, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046223]
• 16: Y. Sugawara, M. Inaba, and K. Hiraki. Over 10gbps string matching mechanism for multi-stream packet scanning systems. In Lecture Notes in Computer Science, volume 3203, pages 484--493. Springer-Verlag, 2004.
• 17: N. Tuck, T. Sherwood, B. Calder, and G. Varghese. Deterministic memory--efficient string matching algorithms for intrusion detection. In Proc. of the IEEE Infocom Conference, pages 333--340, 2004.
• 18: George Varghese, Network Algorithmics,: An Interdisciplinary Approach to Designing Fast Networked Devices (The Morgan Kaufmann Series in Networking), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 19: S. Wu and Manber. A fast algorithm for multi-pattern searching. Technical Report TR94-17, Department of Computer Science, University of Arizona, 1994.
• 20: Xilinx, Inc. Virtex-IV Pro and Virtex-IV Pro X Platform FPGAs: Complete Data Sheet, 2004.http://www.xilinx.com.
• 21: Fang Yu , Randy H. Katz , T. V. Lakshman, Gigabit Rate Packet Pattern-Matching Using TCAM, Proceedings of the 12th IEEE International Conference on Network Protocols, p.174-183, October 05-08, 2004

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance, Security

Keywords:
FPGA, network intrusion detection systems, string matching