Scalable regular expression matching on data streams

ABSTRACT

Regular Expression (RE) matching has important applications in the areas of XML content distribution and network security. In this paper, we present the end-to-end design of a high performance RE matching system. Our system combines the processing efficiency of Deterministic Finite Automata (DFA) with the space efficiency of Non-deterministic Finite Automata (NFA) to scale to hundreds of REs. In experiments with real-life RE data on data streams, we found that a bulk of the DFA transitions are concentrated around a few DFA states. We exploit this fact to cache only the frequent core of each DFA in memory as opposed to the entire DFA (which may be exponential in size). Further, we cluster REs such that REs whose interactions cause an exponential increase in the number of states are assigned to separate groups -- this helps to improve cache hits by controlling the overall DFA size.

To the best of our knowledge, ours is the first end-to-end system capable of matching REs at high speeds and in their full generality. Through a clever combination of RE grouping, and static and dynamic caching, it is able to perform RE matching at high speeds, even in the presence of limited memory. Through experiments with real-life data sets, we show that our RE matching system convincingly outperforms a state-of-the-art Network Intrusion Detection tool with support for efficient RE matching.

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: Chee-Yong Chan , Minos Garofalakis , Rajeev Rastogi, RE-tree: an efficient index structure for regular expressions, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.102-119, August 2003 [doi>10.1007/s00778-003-0094-0]
• 3: Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
• 4: 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
• 5: Y. Diao, P. Fischer, et al. Yfilter: Efficient and scalable filtering of XML documents. In phICDE. 2002.
• 6: Yanlei Diao , Shariq Rizvi , Michael J. Franklin, Towards an internet-scale XML dissemination service, Proceedings of the Thirtieth international conference on Very large data bases, p.612-623, August 31-September 03, 2004, Toronto, Canada
• 7: Todd J. Green , Ashish Gupta , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML streams with deterministic automata and stream indexes, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004 [doi>10.1145/1042046.1042051]
• 8: 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
• 9: http://www.ll.mit.edu/IST/ideval/data/data_index.html. Lincoln laboratory, mit.
• 10: http://www.snort.org. Snort network intrusion detection system.
• 11: H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, One-dimensional and multi-dimensional substring selectivity estimation, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.214-230, December 2000 [doi>10.1007/s007780000029]
• 12: T. Johnson, S. Muthukrishnan, et al. Monitoring regular expressions on out-of-order streams. phICDE, 2007.
• 13: Sailesh Kumar , Sarang Dharmapurikar , Fang Yu , Patrick Crowley , Jonathan Turner, Algorithms to accelerate multiple regular expressions matching for deep packet inspection, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
• 14: J. Levandoski, E.Sommer, et al. Application layer packet classifier for linux. http://l7-filter.sourceforge.net/.
• 15: Alex C. Snoeren , Kenneth Conley , David K. Gifford, Mesh-based content routing using XML, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 16: 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]
• 17: S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Tech. Rep. TR-94-17, 1994.
• 18: www.bro ids.org. Bro network intrusion detection system.
• 19: www.cisco.com. Cisco ios ips deployment guide.
• 20: 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:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Algorithms, Design

Keywords:
data streams, deep packet inspection, regular expression matching