skip to main content
poster

Towards fast regular expression matching in practice

Published: 27 August 2013 Publication History

Abstract

Regular expression matching is popular in today's network devices with deep inspection function, but due to lack of algorithmic scalability, it is still the performance bottleneck in practical network processing. To address this problem, our method first partition regular expression patterns into simple segments to avoid state explosion, and then compile these segments into a compact data structure to achieve fast matching. Preliminary experiments illustrate that our matching engine scales linearly with the size of the real-world pattern set, and outperforms state-of-the-art solutions.

References

[1]
Snort, http://www.snort.org/.
[2]
DARPA Intrusion Detection Data Sets, http://www.ll.mit.edu/mission/communications/ist/corpora/ideval/data/index.html.
[3]
M. Becchi and P. Crowley. A hybrid finite automaton for practical deep packet inspection. In Proceedings of the 2007 ACM CoNEXT Conference, pages 1--12. ACM, 2007.
[4]
R. Smith, C. Estan, S. Jha, and S. Kong. Deflating the big bang: fast and scalable deep packet inspection with extended finite automata. In Proceedings of the 2008 ACM SIGCOMM Conference, pages 207--218. ACM, 2008.
[5]
F. Yu, Z. Chen, Y. Diao, T. Lakshman, and R. Katz. Fast and memory-efficient regular expression matching for deep packet inspection. In Proceedings of the 2nd ACM/IEEE ANCS Conference, pages 93--102. ACM, 2006.

Cited By

View all
  • (2023)Bolt: Scalable and Cost-Efficient Multistring Pattern Matching With Programmable SwitchesIEEE/ACM Transactions on Networking10.1109/TNET.2022.320252331:2(846-861)Online publication date: Apr-2023
  • (2019)Efficient regular expression matching on LZ77 compressed strings using negative factorsWorld Wide Web10.1007/s11280-019-00667-z22:6(2519-2543)Online publication date: 23-Mar-2019
  • (2016)A Survey on Regular Expression Matching for Deep Packet InspectionIEEE Communications Surveys & Tutorials10.1109/COMST.2016.256666918:4(2991-3029)Online publication date: 1-Oct-2016
  • Show More Cited By

Index Terms

  1. Towards fast regular expression matching in practice

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM SIGCOMM Computer Communication Review
    ACM SIGCOMM Computer Communication Review  Volume 43, Issue 4
    October 2013
    595 pages
    ISSN:0146-4833
    DOI:10.1145/2534169
    Issue’s Table of Contents
    • cover image ACM Conferences
      SIGCOMM '13: Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM
      August 2013
      580 pages
      ISBN:9781450320566
      DOI:10.1145/2486001
    Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 27 August 2013
    Published in SIGCOMM-CCR Volume 43, Issue 4

    Check for updates

    Author Tags

    1. deep inspection
    2. dfa
    3. regular expression matching

    Qualifiers

    • Poster

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)60
    • Downloads (Last 6 weeks)6
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Bolt: Scalable and Cost-Efficient Multistring Pattern Matching With Programmable SwitchesIEEE/ACM Transactions on Networking10.1109/TNET.2022.320252331:2(846-861)Online publication date: Apr-2023
    • (2019)Efficient regular expression matching on LZ77 compressed strings using negative factorsWorld Wide Web10.1007/s11280-019-00667-z22:6(2519-2543)Online publication date: 23-Mar-2019
    • (2016)A Survey on Regular Expression Matching for Deep Packet InspectionIEEE Communications Surveys & Tutorials10.1109/COMST.2016.256666918:4(2991-3029)Online publication date: 1-Oct-2016
    • (2015)FREME: A pattern partition based engine for fast and scalable regular expression matching in practiceJournal of Network and Computer Applications10.1016/j.jnca.2015.05.01255(154-169)Online publication date: Sep-2015
    • (2015)An Efficient Pre-filter to Accelerate Regular Expression MatchingProceedings of the ICA3PP International Workshops and Symposiums on Algorithms and Architectures for Parallel Processing - Volume 953210.1007/978-3-319-27161-3_10(111-119)Online publication date: 18-Nov-2015
    • (2014)Practical regular expression matching free of scalability and performance barriersComputer Communications10.1016/j.comcom.2014.08.00554:C(97-119)Online publication date: 1-Dec-2014
    • (2024)Machine Learning-Enhanced Automation for Invoice Reconciliation: OCR-Based Solutions for Accuracy and Efficiency in Logistics IndustryIntelligent Systems and Applications10.1007/978-3-031-66336-9_23(325-336)Online publication date: 1-Aug-2024
    • (2015)An Efficient Pre-filter to Accelerate Regular Expression MatchingProceedings of the ICA3PP International Workshops and Symposiums on Algorithms and Architectures for Parallel Processing - Volume 953210.1007/978-3-319-27161-3_10(111-119)Online publication date: 18-Nov-2015

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media