Hardware implementation for network intrusion detection rules with regular expression support

ABSTRACT

Signature-based network intrusion detection systems (NIDSs), such as Snort and Bro, rely on a rule database that describes traffic patterns for known attacks. They examine each packets flowing through a network segment and report suspicious packets to assure security. An attack signature may be represented in terms of fields in a packet such as source/destination IP addresses, source/destination ports, protocols, specific contents in payload, etc. Typically, a Perl Compatible Regular Expression (PCRE) is used to describe a specific content in the payload which may identify an attack. Our study shows that over 60% of the execution time in an NIDS is found to perform string comparisons against a signature database of over 5,950 tokens and over 1,763 PCREs. This paper proposes to extend a bit-parallel algorithm to support multi-byte processing and PCRE. This design takes a segment of bytes from the payload of a packet and detects all possible tokens including those crossing text segment boundaries. A tool is designed to generate VHDL code from a rule set automatically. Performance results are reported.

REFERENCES

• 1: Snort intrusion detection system. http://snort.org, 2006.
• 2: 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]
• 3: Ricardo Baeza-Yates , Gaston H. Gonnet, A new approach to text searching, Communications of the ACM, v.35 n.10, p.74-82, Oct. 1992 [doi>10.1145/135239.135243]
• 4: 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]
• 5: Young H. Cho , Shiva Navab , William H. Mangione-Smith, Specialized Hardware for Deep Network Packet Filtering, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.452-461, September 02-04, 2002
• 6: B. L. Hutchings , R. Franklin , D. Carver, Assisting Network Intrusion Detection with Reconfigurable Hardware, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.111, September 22-24, 2002
• 7: Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 8: C.-T. D. Lo. Hardware-assisted network-based intrusion detection. In Porc. of International Conference on Informatics, Cybernetics and Systems, Kaohsiung, Taiwan, December 2003.
• 9: C.-T. D. Lo, Y.-G. Tai, K. Psarris, and W.-J. Hwang. Super fast hardware string matching. In Proc. of the 2006 IEEE International Conference on Field Programmable Technology, Bangkok Thailand, December 2006.
• 10: I. McAfee. Mcafee products. http://us.mcafee.com/root/catalog.asp, 2006.
• 11: James Moscola , John Lockwood , Ronald P. Loui , Michael Pachos, Implementation of a Content-Scanning Module for an Internet Firewall, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.31, April 09-11, 2003
• 12: H.-C. Roan, W.-J. Hwang, and C.-T, D. Lo. Shift-or circuit for efficient network intrusion detection pattern matching. In Proc. of the 16th International Conference on Field Programmable Logic and Applications (FPL 2006), pages 785--790, Madrid, SPAIN, August 2006.
• 13: L. Schaelicke, T. Slabach, B. Moore, and C. Freeland. Characterizing the performance of network intrusion detection sensors. In Proceedings of the Sixth International Symposium on Recent Advances in Intrusion Detection (RAID 2003), Berlin - Heidelberg - New York, 2003. Springer-Verlag.
• 14: G. Singh and H. Singh. Databases, models, and algorithms for functional genomics: A bioinformatics perspective. In Molecular Biotechnology, volume 29, pages 165--184, February 2005.
• 15: I. Sourdis and D. Pnevmatikatos. Fast, large-scale string match for a 10gbps fpga-based network intrusion detection system. In Proc. of the 13th International Conference on Field Programmable Logic and Applications (FPL 03), pages 880--889, Lisbon, Portugal, September 2003.
• 16: Lin Tan , Timothy Sherwood, A High Throughput String Matching Architecture for Intrusion Detection and Prevention, Proceedings of the 32nd annual international symposium on Computer Architecture, p.112-122, June 04-08, 2005
• 17: S. Wu and U. Manber. A fast algorithm for multi-pattern searching. In Technical Report TR-94-17, Department of Compucter Science, University of Arizona, 1994.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware; Gate arrays

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Security

Keywords:
FPGAs, intrusion detection, network intrusion detection system, security