DPICO: a high speed deep packet inspection engine using compact finite automata

ABSTRACT

Deep Packet Inspection (DPI)has been widely adopted in detecting network threats such as intrusion, viruses and spam. It is challenging, however, to achieve high speed DPI due to the expanding rule sets and ever increasing line rates. A key issue is that the size of the finite automata falls beyond the capacity of on-chip memory thus incurring expensive off-chip accesses. In this paper we present DPICO a hardware based DPI engine that utilizes novel techniques to minimize the storage requirements for finite automata. The techniques proposed are modified content addressable memory (mCAM), interleaved memory banks, and data packing. The experiment results show the scalable performance of DPICO can achieve up to 17.7 Gbps throughput using a contemporary FPGA chip. Experiment data also show that a DPICO based accelerator can improve the pattern matching performance of a DPI server by up to 10 times.

REFERENCES

• 1: Gnu gprof.Free Software Foundation.
• 2: TRE:POSIX Compliant Regular Expression Matching Library.http://laurikari.net/tre/.
• 3: Virtex 4 family overview,January 2007.Xilinx,Inc. http://direct.xilinx.com/bvdocs/publications/ds112.pdf.
• 4: 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]
• 5: F. Anjum, D. Subhadrabandhu, and S. Sarkar. Signature-based intrusion detection for wireless ad-hoc networks: A comparative study of various routing protocols. In IEEE Vehicular Technology Conference October 2003.
• 6: M. Becchi and S. Cadambi. Memory-efficient regular expression search using state merging.INFOCOM 2007 pages pp. 1064--1072, May 2007.
• 7: Joao Bispo, Ioannis Sourdis, Joao M. P. Cardoso, and Stamatis Vassiliadis. Synthesis of regular expressions targeting fpgas:Current status and open issues. In Int. Workshop on Applied Reconfigurable Computing (ARC 2007) pages 179--190, Mangaratiba, Brazil, March 2007.
• 8: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 9: 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]
• 10: Benjamin C. Brodie , David E. Taylor , Ron K. Cytron, A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching, Proceedings of the 33rd annual international symposium on Computer Architecture, p.191-202, June 17-21, 2006
• 11: S. Dharmapurikar and J. Lockwood. Fast and scalable pattern matching for network intrusion detection systems. IEEE Journal on Selected Areas in Communications 24(10):1781--1792 ,October 2006.
• 12: Sailesh Kumar , Sarang Dharmapurikar , Fang Yu , Patrick Crowley , Jonathan Turner, Algorithms to accelerate multiple regular expressions matching for deep packet inspection, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 13: Cheng-Hung Lin , Chih-Tsun Huang , Chang-Ping Jiang , Shih-Chieh Chang, Optimization of regular expression pattern matching circuits on FPGA, Proceedings of the conference on Design, automation and test in Europe: Designers' forum, March 06-10, 2006, Munich, Germany
• 14: 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]
• 15: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7]
• 16: V. Paxson , K. Asanović , S. Dharmapurikar , J. Lockwood , R. Pang , R. Sommer , N. Weaver, Rethinking hardware support for network analysis and intrusion prevention, Proceedings of the 1st USENIX Workshop on Hot Topics in Security, p.11-11, July 31, 2006, Vancouver, B.C., Canada
• 17: 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]
• 18: L. Schaelicke, B. Moore T. Slabach, 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), LNCS, Springer-Verlag September 2003.
• 19: Snort.http://www.snort.org/,2003.
• 20: Lin Tan , Timothy Sherwood, Architectures for Bit-Split String Scanning in Intrusion Detection, IEEE Micro, v.26 n.1, p.110-117, January 2006 [doi>2006-02-17 02:00:03.800]
• 21: Nicholas Weaver , Vern Paxson , Jose M. Gonzalez, The shunt: an FPGA-based accelerator for network intrusion prevention, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216952]
• 22: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
• 23: Fang Yu , Zhifeng Chen , Yanlei Diao , T. V. Lakshman , Randy H. Katz, Fast and memory-efficient regular expression matching 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.1185360]

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Algorithms, Design, Performance, Security

Keywords:
FPGA, content addressable memory, finite automata, intrusion detection