Deflating the big bang: fast and scalable deep packet inspection with extended finite automata

ABSTRACT

Deep packet inspection is playing an increasingly important role in the design of novel network services. Regular expressions are the language of choice for writing signatures, but standard DFA or NFA representations are unsuitable for high-speed environments, requiring too much memory, too much time, or too much per-flow state. DFAs are fast and can be readily combined, but doing so often leads to state-space explosion. NFAs, while small, require large per-flow state and are slow.

We propose a solution that simultaneously addresses all these problems. We start with a first-principles characterization of state-space explosion and give conditions that eliminate it when satisfied. We show how auxiliary variables can be used to transform automata so that they satisfy these conditions, which we codify in a formal model that augments DFAs with auxiliary variables and simple instructions for manipulating them. Building on this model, we present techniques, inspired by principles used in compiler optimization, that systematically reduce runtime and per-flow state. In our experiments, signature sets from Snort and Cisco Systems achieve state-space reductions of over four orders of magnitude, per-flow state reductions of up to a factor of six, and runtimes that approach DFAs.

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: Thomas Ball , Sriram K. Rajamani, The SLAM project: debugging system software via static analysis, ACM SIGPLAN Notices, v.37 n.1, p.1-3, Jan. 2002
• 3: M. Becchi and S. Cadambi. Memory-efficient regular expression search using state merging. In IEEE Infocom 2007.
• 4: Michela Becchi , Patrick Crowley, An improved algorithm to accelerate regular expression evaluation, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323573]
• 5: Benjamin C. Brodie , David E. Taylor , Ron K. Cytron, A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching, ACM SIGARCH Computer Architecture News, v.34 n.2, p.191-202, May 2006
• 6: David Brumley , James Newsome , Dawn Song , Hao Wang , Somesh Jha, Towards Automatic Generation of Vulnerability-Based Signatures, Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.2-16, May 21-24, 2006 [doi>10.1109/SP.2006.41]
• 7: Christopher R. Clark , David E. Schimmel, Scalable Pattern Matching for High Speed Networks, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.249-257, April 20-23, 2004
• 8: Edmund M. Clarke, Jr. , Orna Grumberg , Doron A. Peled, Model checking, MIT Press, Cambridge, MA, 2000
• 9: Scott A. Crosby , Dan S. Wallach, Denial of service via algorithmic complexity attacks, Proceedings of the 12th conference on USENIX Security Symposium, p.3-3, August 04-08, 2003, Washington, DC
• 10: S. Dharmapurikar and J. W. Lockwood. Fast and scalable pattern matching for network intrusion detection systems. IEEE Journal on Selected Areas in Comm., 24(10):1781--1792, 2006.
• 11: The Guardian. Trouble on the line. http://technology. guardian.co.uk/weekly/story/0,,1747343,00.html, 2006.
• 12: Mark Handley , Vern Paxson , Christian Kreibich, Network intrusion detection: evasion, traffic normalization, and end-to-end protocol semantics, Proceedings of the 10th conference on USENIX Security Symposium, p.9-9, August 13-17, 2001, Washington, D.C.
• 13: S. W. Hawking. A brief history of time. From the Big Bang to Black Holes. Bantam Book, 1988.
• 14: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 15: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 16: Myles Jordan. Dealing with metamorphism. Virus Bulletin Weekly, 2002.
• 17: Christoforos Kachris , Stamatis Vassiliadis, Design of a web switch in a reconfigurable platform, 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.1185352]
• 18: P. Kapustka. Vonage complaining of VoIP blocking. http://www.networkcomputing.com/channels/~networkinfrastructure/60400413, 2005.
• 19: Sailesh Kumar , Balakrishnan Chandrasekaran , Jonathan Turner , George Varghese, Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323574]
• 20: 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
• 21: Sailesh Kumar , Jonathan Turner , John Williams, Advanced algorithms for fast and scalable 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.1185359]
• 22: 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]
• 23: H. McGhan. Niagara 2 opens the floodgates. In Microprocessor Report, November 2006.
• 24: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 25: M. Neider. Deep packet inspection: A service provider's solution for secure VoIP. VoIP Magazine, Oct 2005.
• 26: 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]
• 27: T. Ptacek and T. Newsham. Insertion, evasion and denial of service: Eluding network intrusion detection. In Secure Networks, Inc., January 1998.
• 28: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 29: Umesh Shankar , Vern Paxson, Active Mapping: Resisting NIDS Evasion without Altering Traffic, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.44, May 11-14, 2003
• 30: Randy Smith , Cristian Estan , Somesh Jha, Backtracking Algorithmic Complexity Attacks against a NIDS, Proceedings of the 22nd Annual Computer Security Applications Conference on Annual Computer Security Applications Conference, p.89-98, December 11-15, 2006 [doi>10.1109/ACSAC.2006.17]
• 31: Randy Smith , Cristian Estan , Somesh Jha, XFA: Faster Signature Matching with Extended Automata, Proceedings of the 2008 IEEE Symposium on Security and Privacy (sp 2008), p.187-201, May 18-21, 2008 [doi>10.1109/SP.2008.14]
• 32: Robin Sommer , Vern Paxson, Enhancing byte-level network intrusion detection signatures with context, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948145]
• 33: I. Sourdis and D. Pnevmatikatos. Fast, large-scale string match for a 10gbps fpga-based network intrusion detection system. In Int. Conf. on Field Programmable Logic and Applications, sep. 2003.
• 34: 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
• 35: N. Tuck, T. Sherwood, B. Calder, and G. Varghese. Deterministic memory-efficient string matching algorithms for intrusion detection. In IEEE INFOCOM 2004, pages 333--340.
• 36: Helen J. Wang , Chuanxiong Guo , Daniel R. Simon , Alf Zugenmaier, Shield: vulnerability-driven network filters for preventing known vulnerability exploits, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 37: 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)

General Terms:
Algorithms, Performance, Security

Keywords:
deep packet inspection, regular expressions, signature matching, xfa