More Web Proxy on the site http://driver.im/

research-article

Efficient regular expression evaluation: theory to practice

Authors:

Michela Becchi,

Patrick CrowleyAuthors Info & Claims

ANCS '08: Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems

Pages 50 - 59

https://doi.org/10.1145/1477942.1477950

Published: 06 November 2008 Publication History

Abstract

Several algorithms and techniques have been proposed recently to accelerate regular expression matching and enable deep packet inspection at line rate. This work aims to provide a comprehensive practical evaluation of existing techniques, extending them and analyzing their compatibility. The study focuses on two hardware architectures: memory-based ASICs and FPGAs.

References

[1]

A. Aho and M. Corasick, "Efficient String Matching: An Aid to Bibliographic Search," Communication of ACM, 1975.

Digital Library

[2]

J. Hopcroft and J Ullman, "Introduction to Automata Theory, Languages, and Computation," Addison Wesley, 1979.

Digital Library

[3]

J. Hopcroft, "An nlogn algorithm for minimizing states in a finite automaton," in Theory of Machines and Computation, J. Kohavi, Ed. New York: Academic, 1971, pp. 189--196.

[4]

K. Thompson, "Regular expression search algorithm," in Communications of the ACM, vol. 11, Issue. 6, June 1968, pp. 419--422.

Digital Library

[5]

R. McNaughton and H. Yamada, "Regular Expressions and State Graphs for Automata," in IEEE Transactions on Electronic Computers, EC-9(1), pp. 39--47, 1960.

[6]

S. Kumar et al., "Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection," in ACM SIGCOMM, Sept 2006.

Digital Library

[7]

M. Becchi and P. Crowley, "An Improved Algorithm to Accelerate Regular Expression Evaluation," in ANCS 2007.

Digital Library

[8]

B. Brodie et al., "A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching," in ISCA 2006.

Digital Library

[9]

S. Kumar et al., "Advanced Algorithms for Fast and Scalable Deep Packet Inspection," in ANCS 2006.

Digital Library

[10]

F. Yu et al., "Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection," in ANCS 2006.

Digital Library

[11]

M. Becchi and P. Crowley, "A Hybrid Finite Automaton for Practical Deep Packet Inspection," in CoNEXT 2007.

Digital Library

[12]

S. Kumar et al., "Curing Regular Expressions Matching Algorithms from Insomnia, Amnesia, and Acalculia," in ANCS 2007.

Digital Library

[13]

R. Smith et al., "XFA: Faster Signature Matching with Extended Automata," in 2008 IEEE Symposium on Security and Privacy.

Digital Library

[14]

R. Sidhu and V. K. Prasanna, "Fast Regular Expression Matching using FPGAs," in FCCM 2001.

Digital Library

[15]

C. R. Clark and D. E. Schimmel, "Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns," in FPL 2003.

[16]

J. Moscola et al., "Implementation of a content-scanning module for an internet firewall," in FCCM 2003.

Digital Library

[17]

R. Franklin et al., "Assisting Network Intrusion Detection with Reconfigurable Hardware," in FCCM 2002.

Digital Library

[18]

C. R. Clark et al., "Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns," in FLP 2003.

[19]

I. Sourdis et al., "Pre-decoded CAMs for Efficient and High-Speed NIDS Pattern Matching," in FCCM 2004.

Digital Library

[20]

A. Mitra et al., "Compiling PCRE to FPGA for Accelerating SNORT IDS," in ANCS 2007.

Digital Library

[21]

M. Roesch, "SNORT: Lightweight Intrusion Detection for Networks," in 13th System Administration Conf., Nov 1999.

Digital Library

[22]

SNORT: http://www.snort.org

[23]

R. Sommer and V. Paxson, "Enhancing byte-level network intrusion detection signatures with context," in CCS 2003.

Digital Library

[24]

Xilinx: http://www.xilinx.com

Cited By

Somaini ACarloni FAgosta GSantambrogio MConficconi DDoerfert JGrosser TLeather HSadayappan P(2025)Combining MLIR Dialects with Domain-Specific Architecture for Efficient Regular Expression MatchingProceedings of the 23rd ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3696443.3708916(255-270)Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1145/3696443.3708916
Bille PGørtz IPedersen M(2025)Fast Practical Compression of Deterministic Finite AutomataSOFSEM 2025: Theory and Practice of Computer Science10.1007/978-3-031-82670-2_11(136-150)Online publication date: 7-Feb-2025
https://doi.org/10.1007/978-3-031-82670-2_11
Nguyen TBecchi M(2024)A Transducers-based Programming Framework for Efficient Data TransformationProceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques10.1145/3656019.3676891(66-77)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1145/3656019.3676891
Show More Cited By

Index Terms

Efficient regular expression evaluation: theory to practice

Recommendations

Dynamically reconfigurable regular expression matching architecture
ASAP '08: Proceedings of the 2008 International Conference on Application-Specific Systems, Architectures and Processors

Regular Expressions are generic representations for a string or a collection of strings. This paper focuses on implementation of a regular expression matching architecture on reconfigurable fabric like FPGA. We present a Non-deterministic Finite ...
A regular expression matching circuit: Decomposed non-deterministic realization with prefix sharing and multi-character transition

This paper shows a compact realization of regular expression matching circuits on FPGAs. First, the given regular expression is converted into a non-deterministic finite automaton (NFA) by the modified McNaughton-Yamada method. Second, to reduce the ...
Area-efficient arithmetic expression evaluation using deeply pipelined floating-point cores

Recently, it has become possible to implement floating-point cores on field-programmable gate arrays (FPGAs) to provide acceleration for the myriad applications that require high-performance floating-point arithmetic. To achieve high clock rates, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '08: Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems

November 2008

191 pages

ISBN:9781605583464

DOI:10.1145/1477942

General Chair:
Mark Franklin
Washington University in St. Louis
,
Program Chairs:
D. K. Panda
Ohio State University
,
Dimitri Stiliadis
Bell Laboratory

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Division of Computing and Communication Foundations

Conference

ANCS '08

Sponsor:

ANCS '08: Symposium on Architecture for Networking and Communications Systems

November 6 - 7, 2008

California, San Jose

Acceptance Rates

ANCS '08 Paper Acceptance Rate 17 of 67 submissions, 25%;

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

129
Total Citations
View Citations
1,104
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Somaini ACarloni FAgosta GSantambrogio MConficconi DDoerfert JGrosser TLeather HSadayappan P(2025)Combining MLIR Dialects with Domain-Specific Architecture for Efficient Regular Expression MatchingProceedings of the 23rd ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3696443.3708916(255-270)Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1145/3696443.3708916
Bille PGørtz IPedersen M(2025)Fast Practical Compression of Deterministic Finite AutomataSOFSEM 2025: Theory and Practice of Computer Science10.1007/978-3-031-82670-2_11(136-150)Online publication date: 7-Feb-2025
https://doi.org/10.1007/978-3-031-82670-2_11
Nguyen TBecchi M(2024)A Transducers-based Programming Framework for Efficient Data TransformationProceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques10.1145/3656019.3676891(66-77)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1145/3656019.3676891
Ge TZhang TLiu HTsafrir DMUSUVATHI MGupta RAbu-Ghazaleh N(2024)ngAP: Non-blocking Large-scale Automata Processing on GPUsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624848(268-285)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3617232.3624848
Cicolini LCarloni FSantambrogio MConficconi DGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)One Automaton to Rule Them All: Beyond Multiple Regular Expressions ExecutionProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444810(193-206)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444810
Liu HPai SJog A(2023)Asynchronous Automata Processing on GPUsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35794537:1(1-27)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3579453
Bachini Lopes FSchaeffer-Filho ANazar G(2023)Modular VNF Components Acceleration With FPGA OverlaysIEEE Transactions on Network and Service Management10.1109/TNSM.2022.321144820:1(846-857)Online publication date: Mar-2023
https://doi.org/10.1109/TNSM.2022.3211448
Wang SZhang MLi GLiu CWang ZLiu YXu M(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
https://doi.org/10.1109/TNET.2022.3202523
Gong LWang CXia HChen XLi XZhou X(2023)Enabling Fast and Memory-Efficient Acceleration for Pattern Matching Workloads: The Lightweight Automata Processing EngineIEEE Transactions on Computers10.1109/TC.2022.318733872:4(1011-1025)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TC.2022.3187338
Košař VŠišmiš LMatoušek JKořenek J(2023)Accelerating IDS Using TLS Pre-Filter in FPGA2023 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC58397.2023.10218049(436-442)Online publication date: 9-Jul-2023
https://doi.org/10.1109/ISCC58397.2023.10218049
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten