Efficient packet classification for network intrusion detection using FPGA

ABSTRACT

Using FPGA technology for real-time network intrusion detection has gained many research efforts recently. In this paper, a novel packet classification architecture called BV-TCAM is presented, which is implemented for an FPGA-based Network Intrusion Detection System (NIDS). The classifier can report multiple matches at gigabit per second network link rates. The BV-TCAM architecture combines the Ternary Content Addressable Memory (TCAM) and the Bit Vector (BV) algorithm to effectively compress the data representations and boost throughput. A tree-bitmap implementation of the BV algorithm is used for source and destination port lookup while a TCAM performs the lookup of the other header fields, which can be represented as a prefix or exact value. The architecture eliminates the requirement for prefix expansion of port ranges. With the aid of a small embedded TCAM, packet classification can be implemented in a relatively small part of the available logic of an FPGA. The design is prototyped and evaluated in a Xilinx FPGA XCV2000E on the FPX platform. Even with the most difficult set of rules and packet inputs, the circuit is fast enough to sustain OC48 traffic throughput. Using larger and faster FPGAs, the system can work at speeds greater than OC192.

REFERENCES

• 1: Snort -The Open Source Network Intrusion Detection System. In http://www.snort.org.
• 2: Florin Baboescu , George Varghese, Scalable packet classification, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.199-210, August 2001, San Diego, California, United States
• 3: Z. Baker and V. Prasanna. Automatic Synthesis of Efficient Intrusion Detection Systems on FPGAs. In Proceedings of FPL'04, 2004.
• 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: Young H. Cho , William H. Mangione-Smith, Deep Packet Filter with Dedicated Logic and Read Only Memories, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.125-134, April 20-23, 2004
• 6: C. Clark and D. Schimmel. Efficient Reconfigurable Logic Circuits for Matching Complex Network Intrusion Detection Patterns. In Proceedings of FPL'03, 2003.
• 7: 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
• 8: T. V. Lakshman , D. Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.203-214, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 9: T. Lee, S. Yusuf, W. Luk, M. Sloman, E. Lupu, and N. Dulay. Irregular Reconfiguration CAM Structures for Firewall Application. In Proceedings of FPL'03, 2003.
• 10: Huan Liu, Efficient Mapping of Range Classifier into Ternary-CAM, Proceedings of the 10th Symposium on High Performance Interconnects HOT Interconnects (HotI'02), p.95, August 21-23, 2002
• 11: J. V. Lunteren and T. Engbersen. Fast and Scalable Packet Classification.IEEE Journal on Selected Areas in Communications, 21:560--570, May 2003.
• 12: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 13: I. Sourdis and D. Pnevmatikatos. A Methodology for the Synthesis of Efficient Intrusion Detection Systems on FPGAs. In Proceedings of FCCM'04, 2004.
• 14: Ed Spitznagel , David Taylor , Jonathan Turner, Packet Classification Using Extended TCAMs, Proceedings of the 11th IEEE International Conference on Network Protocols, p.120, November 04-07, 2003
• 15: V. Srinivasan , George Varghese, Faster IP lookups using controlled prefix expansion, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-10, June 22-26, 1998, Madison, Wisconsin, United States
• 16: D. Taylor. Survey and Taxonomy of Packet Classification Techniques. Tech. Report WUCSE-2004-24, Department of CSE, Washington University in St.Louis, 2004.
• 17: D. Taylor, J. Turner, J. Lockwood, T. Sproull, and D. Parlour. Scalable IP Lookup for Internet Routers. IEEE Journal on Selected Areas in Communications, 21:522--534, May 2003.
• 18: W. N. Eatherton. Hardware-Based Internet Protocol Prefix Lookups. Master Thesis, Washington University in St.Louis, http://www.arl.wustl.edu/, 1999.
• 19: Xilinx. Contend-Addressable Memory v4.0. Xilinx Product Specification S253 (v1.0), Marc 2003.
• 20: F. Yu and R. Katz. Efficient Multi-Match Packet Classification and Lookup with TCAM. In IEEE Symposium on High Performance Interconnects (HotI), Stanford, CA, Aug. 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Design, Security

Keywords:
BV, FPGA, NIDS, TCAM, packet classification, reconfigurable hardware, tree bitmap