research-article

A hybrid finite automaton for practical deep packet inspection

Authors:

Michela Becchi,

Patrick CrowleyAuthors Info & Claims

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

Article No.: 1, Pages 1 - 12

https://doi.org/10.1145/1364654.1364656

Published: 10 December 2007 Publication History

Abstract

Deterministic finite automata (DFAs) are widely used to perform regular expression matching in linear time. Several techniques have been proposed to compress DFAs in order to reduce memory requirements. Unfortunately, many real-world IDS regular expressions include complex terms that result in an exponential increase in number of DFA states. Since all recent proposals use an initial DFA as a starting-point, they cannot be used as comprehensive regular expression representations in an IDS.

In this work we propose a hybrid automaton which addresses this issue by combining the benefits of deterministic and non-deterministic finite automata. We test our proposal on Snort rule-sets and we validate it on real traffic traces. Finally, we address and analyze the worst case behavior of our scheme and compare it to traditional ones.

References

[1]

A. V. Aho and M. J. Corasick, "Efficient String Matching: An Aid to Bibliographic Search," Communications of the ACM, pp. 333--340, 1975.

Digital Library

[2]

B. Commentz-Walter, "A string matching algorithm fast on the average," in ICALP, July 1979.

Digital Library

[3]

S. Wu, U. Manber, "A fast algorithm for multi-pattern searching," Tech. Report TR-94-17, Univ of Arizona, 1994.

[4]

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

Digital Library

[5]

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.

[6]

M. Roesch, "Snort: Lightweight Intrusion Detection for Networks," in System Administration Conf., 1999

Digital Library

[7]

Snort: http://www.Snort.org/

[8]

Cisco Systems. Cisco ASA 5505 Adaptive Security Appliance. http://www.cisco.com.2007.

[9]

Citrix Systems. Citrix Application Firewall. http://www.citrix.com. 2007.

[10]

Bro: http://bro-ids.org/

[11]

Vern Paxson et al., "Flex: A fast scanner generator," http://www.gnu.org/software/flex/

[12]

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

Digital Library

[13]

N. Tuck, T. Sherwood, B. Calder, and G. Varghese, "Deterministic memory-efficient string matching algorithms for intrusion detection," in Infocom 2004.

[14]

L. Tan, and T. Sherwood, "A High Throughput String Matching Architecture for Intrusion Detection and Prevention," ISCA 2005.

Digital Library

[15]

F. Yu, Z. Chen, Y. Diao, T. V. Lakshman, and R. H. Katz, "Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection", in ANCS 2006

Digital Library

[16]

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

Digital Library

[17]

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

Digital Library

[18]

M. Becchi and S. Cadambi, "Memory-Efficient Regular Expression Search Using State Merging", in INFOCOM 2007

[19]

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

Digital Library

[20]

M. Becchi and P. Crowley, "Addressing complex regular expressions through counting automata", Washington University Tech. Report, July 2007.

[21]

R. W. Floyd, and J. D. Ullman, "The Compilation of Regular Expressions into Integrated Circuits", Journal of ACM, vol. 29, no. 3, pp 603--622, July 1982.

Digital Library

[22]

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

Digital Library

[23]

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

[24]

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

Digital Library

[25]

Internet traffic traces: http://cctf.shmoo.com/

[26]

Cu-11 standard cell/gate array ASIC, IBM. www.ibm.com

Cited By

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
Wang XGong LCao JLou WWang WWang CZhou XIenne PZhang Z(2023)hAP: A Spatial-von Neumann Heterogeneous Automata Processor with Optimized Resource and IO Overhead on FPGAProceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3543622.3573190(185-196)Online publication date: 12-Feb-2023
https://dl.acm.org/doi/10.1145/3543622.3573190
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
Show More Cited By

Index Terms

A hybrid finite automaton for practical deep packet inspection
1. Security and privacy
  1. Network security

Recommendations

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

There is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems that perform deep packet inspection implement ...
Advanced algorithms for fast and scalable deep packet inspection
ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems

Modern deep packet inspection systems use regular expressions to define various patterns of interest in network data streams. Deterministic Finite Automata (DFA) are commonly used to parse regular expressions. DFAs are fast, but can require ...
DFA-based and SIMD NFA-based regular expression matching on cell BE for fast network traffic filtering
SIN '09: Proceedings of the 2nd international conference on Security of information and networks

Regular expression matching is the heart of many data processing routines, such as string search, network traffic filtering, etc. The traditional way of regexp matching is building and execution of a deterministic finite automaton (DFA), that provides O(...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

December 2007

448 pages

ISBN:9781595937704

DOI:10.1145/1364654

General Chairs:
Jim Kurose
University of Massachusetts
,
Henning Schulzrinne
Columbia University

Copyright © 2007 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

Alcatel-Lucent
SIGCOMM: ACM Special Interest Group on Data Communication
Thomson
CISCO
IMDEA
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Computing and Communication Foundations

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

191
Total Citations
View Citations
1,055
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Wang XGong LCao JLou WWang WWang CZhou XIenne PZhang Z(2023)hAP: A Spatial-von Neumann Heterogeneous Automata Processor with Optimized Resource and IO Overhead on FPGAProceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3543622.3573190(185-196)Online publication date: 12-Feb-2023
https://dl.acm.org/doi/10.1145/3543622.3573190
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
Conficconi DSozzo ECarloni FComodi AScolari ASantambrogio M(2023)An Energy-Efficient Domain-Specific Architecture for Regular ExpressionsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2022.315794811:1(3-17)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TETC.2022.3157948
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
Lu YWang XYuan FCao CZhang XLiu Y(2023)RegexClassifier: A GNN-Based Recognition Method for State-Explosive Regular Expressions2023 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC58397.2023.10218248(1039-1045)Online publication date: 9-Jul-2023
https://doi.org/10.1109/ISCC58397.2023.10218248
Lee BLim KLee JJung CKim DLee KCho HKwon Y(2023)Dazzle-attack: Anti-Forensic Server-side Attack via Fail-Free Dynamic State MachineInformation Security Applications10.1007/978-3-031-25659-2_15(204-221)Online publication date: 4-Feb-2023
https://doi.org/10.1007/978-3-031-25659-2_15
Xu CYu KXu XBao XWu SZhao B(2022)Offset-FA: A Uniform Method to Handle Both Unbounded and Bounded Repetitions in Regular Expression MatchingSensors10.3390/s2220778122:20(7781)Online publication date: 13-Oct-2022
https://doi.org/10.3390/s22207781
Parravicini DConficconi DSozzo EPilato CSantambrogio M(2021)CICERO: A Domain-Specific Architecture for Efficient Regular Expression MatchingACM Transactions on Embedded Computing Systems10.1145/347698220:5s(1-24)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3476982
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.

Media

Figures

Other

Tables

View Table of Contents