research-article

iNFAnt: NFA pattern matching on GPGPU devices

Authors:

Niccolo' Cascarano,

Pierluigi Rolando,

Fulvio Risso,

Riccardo SistoAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 40, Issue 5

Pages 20 - 26

https://doi.org/10.1145/1880153.1880157

Published: 22 October 2010 Publication History

Get Access

Abstract

This paper presents iNFAnt, a parallel engine for regular expression pattern matching. In contrast with traditional approaches, iNFAnt adopts non-deterministic automata, allowing the compilation of very large and complex rule sets that are otherwise hard to treat. iNFAnt is explicitly designed and developed to run on graphical processing units that provide large amounts of concurrent threads; this parallelism is exploited to handle the non-determinism of the model and to process multiple packets at once, thus achieving high performance levels.

References

[1]

M. Becchi and P. Crowley. A hybrid finite automaton for practical deep packet inspection. In proceedings of CoNEXT '07, pages 1--12, NY, USA, 2007. ACM.

Digital Library

Google Scholar

[2]

M. Becchi and P. Crowley. Efficient regular expression evaluation: theory to practice. In proceedings of ANCS'08, pages 50--59, NY, USA, 2008. ACM.

Digital Library

Google Scholar

[3]

M. Becchi, C. Wiseman, and P. Crowley. Evaluating regular expression matching engines on network and general purpose processors. In proceedings of ANCS'09, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[4]

F. Kulishov. DFA-based and SIMD NFA-based regular expression matching on Cell BE for fast network traffic filtering. In proceedings of SIN '09, pages 123--127, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[5]

R. Smith, N. Goyal, J. Ormont, K. Sankaralingam, and C. Estan. Evaluating GPUs for network packet signature matching. In proceedings of ISPASS '09, pages 175--184, 2009.

Crossref

Google Scholar

[6]

G. Szabo, I. Godor, A. Veres, and S. Malomsoky, Sz. and. Molnar. Traffic classification over gbit speed with commodity hardware. In accepted for publication in IEEE Journal of Communications Software and Systems, 2010, Vol. 5, Num. 3., 2010.

Google Scholar

[7]

G. Vasiliadis, S. Antonatos, M. Polychronakis, E. P. Markatos, and S. Ioannidis. Gnort: High performance network intrusion detection using graphics processors. In proceedings of RAID '08, pages 116--134, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

Google Scholar

[8]

G. Vasiliadis, M. Polychronakis, S. Antonatos, E. P. Markatos, and S. Ioannidis. Regular expression matching on graphics hardware for intrusion detection. In proceedings of RAID '09, pages 265--283, Berlin, Heidelberg, 2009. Springer-Verlag.

Digital Library

Google Scholar

Cited By

View all

Le Glaunec AKong LMamouras K(2024)HybridSA: GPU Acceleration of Multi-pattern Regex Matching using Bit ParallelismProceedings of the ACM on Programming Languages10.1145/36897718:OOPSLA2(1699-1728)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689771
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
Li CVerbrugge C(2024)Regular Expressions on Modern GPGPUsProceedings of the 16th Workshop on General Purpose Processing Using GPU10.1145/3649411.3649416(26-32)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3649411.3649416
Show More Cited By

Index Terms

iNFAnt: NFA pattern matching on GPGPU devices
1. Networks
  1. Network services
    1. Network monitoring

Recommendations

GPU-based NFA implementation for memory efficient high speed regular expression matching
PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

Regular expression pattern matching is the foundation and core engine of many network functions, such as network intrusion detection, worm detection, traffic analysis, web applications and so on. DFA-based solutions suffer exponentially exploding state ...
GPU-based NFA implementation for memory efficient high speed regular expression matching
PPOPP '12

Regular expression pattern matching is the foundation and core engine of many network functions, such as network intrusion detection, worm detection, traffic analysis, web applications and so on. DFA-based solutions suffer exponentially exploding state ...
A performance study of general-purpose applications on graphics processors using CUDA

Graphics processors (GPUs) provide a vast number of simple, data-parallel, deeply multithreaded cores and high memory bandwidths. GPU architectures are becoming increasingly programmable, offering the potential for dramatic speedups for a variety of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 40, Issue 5

October 2010

73 pages

ISSN:0146-4833

DOI:10.1145/1880153

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2010

Published in SIGCOMM-CCR Volume 40, Issue 5

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

77
Total Citations
View Citations
552
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Le Glaunec AKong LMamouras K(2024)HybridSA: GPU Acceleration of Multi-pattern Regex Matching using Bit ParallelismProceedings of the ACM on Programming Languages10.1145/36897718:OOPSLA2(1699-1728)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689771
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
Li CVerbrugge C(2024)Regular Expressions on Modern GPGPUsProceedings of the 16th Workshop on General Purpose Processing Using GPU10.1145/3649411.3649416(26-32)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3649411.3649416
Wen ZKong LLe Glaunec AMamouras KYang KTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded RepetitionsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640412(151-166)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640412
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
Hu ZHasegawa HYamaguchi YShimada H(2024)Enhancing Detection of Malicious Traffic Through FPGA-Based Frequency Transformation and Machine LearningIEEE Access10.1109/ACCESS.2023.334823412(2648-2659)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2023.3348234
Karakchi RBakos J(2023)NAPOLY: A Non-deterministic Automata Processor OverLaYACM Transactions on Reconfigurable Technology and Systems10.1145/359358616:3(1-25)Online publication date: 22-Jun-2023
https://dl.acm.org/doi/10.1145/3593586
Valizadeh MBerger M(2023)Search-Based Regular Expression Inference on a GPUProceedings of the ACM on Programming Languages10.1145/35912747:PLDI(1317-1339)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591274
Xu HChang HZhu WHong YLangdale GQiu KZhao J(2023)Harry: A Scalable SIMD-based Multi-literal Pattern Matching Engine for Deep Packet InspectionIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10229022(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10229022
Hu ZHasegawa HYamaguchi YShimada H(2023)Realtime Malicious Traffic Detection Targeted for TCP Out-of-Order Packets Based on FPGAIEEE Access10.1109/ACCESS.2023.332385311(112212-112222)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3323853
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.

Cited By

Index Terms

Recommendations

GPU-based NFA implementation for memory efficient high speed regular expression matching

GPU-based NFA implementation for memory efficient high speed regular expression matching

A performance study of general-purpose applications on graphics processors using CUDA