research-article

BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions

Authors:

Alexis Le Glaunec,

Konstantinos Mamouras,

Kaiyuan YangAuthors Info & Claims

ASPLOS '24: Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2

Pages 151 - 166

https://doi.org/10.1145/3620665.3640412

Published: 27 April 2024 Publication History

Abstract

Regular pattern matching is pervasive in applications such as text processing, malware detection, network security, and bioinformatics. Recent studies have demonstrated specialized in-memory automata processors with superior energy and memory efficiencies than existing computing platforms. Yet, they lack efficient support for the construct of bounded repetition that is widely used in regular expressions (regexes). This paper presents BVAP, a software-hardware co-designed in-memory Bit Vector Automata Processor. It is enabled by a novel theoretical model called Action-Homogeneous Non-deterministic Bit Vector Automata (AH-NBVA), its efficient hardware implementation, and a compiler that translates regexes into hardware configurations. BVAP is evaluated with a cycle-accurate simulator in a 28nm CMOS process, achieving 67-95% higher energy efficiency and 42-68% lower area, compared to state-of-the-art automata processors (CA, eAP, and CAMA), across a set of real-world benchmarks.

References

[1]

Ricardo A. Baeza-Yates and Gaston H. Gonnet. Efficient text searching of regular expressions. In Giorgio Ausiello, Mariangiola Dezani-Ciancaglini, and Simonetta Ronchi Della Rocca, editors, Automata, Languages and Programming, pages 46--62, Heidelberg, 1989. Springer.

[2]

Michela Becchi and Patrick Crowley. Extending finite automata to efficiently match Perl-compatible regular expressions. In Proceedings of the 2008 ACM CoNEXT Conference, CoNEXT '08, New York, NY, USA, 2008. ACM.

Digital Library

[3]

Joao Bispo, Ioannis Sourdis, Joao M. P. Cardoso, and Stamatis Vassiliadis. Regular expression matching for reconfigurable packet inspection. In 2006 IEEE International Conference on Field Programmable Technology, pages 119--126, USA, 2006. IEEE.

[4]

Chunkun Bo, Vinh Dang, Elaheh Sadredini, and Kevin Skadron. Searching for potential gRNA off-target sites for CRISPR/Cas9 using automata processing across different platforms. In 2018 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 737--748. IEEE, 2018.

[5]

Niccolo' Cascarano, Pierluigi Rolando, Fulvio Risso, and Riccardo Sisto. iNFAnt: NFA pattern matching on GPGPU devices. ACM SIGCOMM Computer Communication Review, 40(5):20--26, 2010.

Digital Library

[6]

Matheus Cavalcante, Fabian Schuiki, Florian Zaruba, Michael Schaffner, and Luca Benini. Ara: A 1-ghz+ scalable and energy-efficient risc-v vector processor with multiprecision floating-point support in 22-nm fd-soi. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 28(2):530--543, 2020.

[7]

Milan Ceška, Vojtech Havlena, Lukáš Holík, Jan Korenek, Ondrej Lengál, Denis Matoušek, Jirí Matoušek, Jakub Semric, and Tomáš Vojnar. Deep packet inspection in FPGAs via approximate nondeterministic automata. In 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), pages 109--117. IEEE, 2019.

[8]

Jian Chen, Xiaoyu Zhang, Tao Wang, Ying Zhang, Tao Chen, Jiajun Chen, Mingxu Xie, and Qiang Liu. Fidas: Fortifying the cloud via comprehensive FPGA-based offloading for intrusion detection: Industrial product. In Proceedings of the 49th Annual International Symposium on Computer Architecture, ISCA '22, page 1029--1041, New York, NY, USA, 2022. Association for Computing Machinery.

Digital Library

[9]

ClamAV. ClamAV - open source antivirus engine. Available at https://www.clamav.net/, 2023. [Online; Accessed 17 July, 2023].

[10]

Paul Dlugosch, Dave Brown, Paul Glendenning, Michael Leventhal, and Harold Noyes. An efficient and scalable semiconductor architecture for parallel automata processing. IEEE Transactions on Parallel and Distributed Systems, 25(12):3088--3098, 2014.

[11]

Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg. Counter machines and counter languages. Mathematical Systems Theory, 2(3):265--283, 1968.

[12]

Apache Software Foundation. Apache Spamassassin. Available at https://spamassassin.apache.org/, 2022. [Online; Accessed 17 July, 2023].

[13]

Wouter Gelade, Marc Gyssens, and Wim Martens. Regular expressions with counting: Weak versus strong determinism. In Mathematical Foundations of Computer Science 2009, pages 369--381, Heidelberg, 2009. Springer.

[14]

Victor Mikhaylovich Glushkov. The abstract theory of automata. Russian Math. Surveys, 16(5):1--53, 1961.

[15]

Vaibhav Gogte, Aasheesh Kolli, Michael J. Cafarella, Loris D'Antoni, and Thomas F. Wenisch. HARE: Hardware accelerator for regular expressions. In 2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 1--12. IEEE, 2016.

[16]

Yi Huang, Zhiyu Chen, Dai Li, and Kaiyuan Yang. CAMA: Energy and memory efficient automata processing in content-addressable memories. In 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pages 25--37, New York, NY, USA, 2022. IEEE.

[17]

Lingkun Kong, Qixuan Yu, Agnishom Chattopadhyay, Alexis Le Glaunec, Yi Huang, Konstantinos Mamouras, and Kaiyuan Yang. Software-hardware codesign for efficient in-memory regular pattern matching. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2022, pages 733--748, New York, NY, USA, 2022. ACM.

Digital Library

[18]

Alexis Le Glaunec, Lingkun Kong, and Konstantinos Mamouras. Regular expression matching using bit vector automata. Proceedings of the ACM on Programming Languages, 7(OOPSLA1), 2023.

Digital Library

[19]

Marzieh Lenjani and Mahmoud Reza Hashemi. Tree-based scheme for reducing shared cache miss rate leveraging regional, statistical and temporal similarities. IET Computers & Digital Techniques, 8(1):30--48, 2014.

[20]

Hongyuan Liu, Mohamed Ibrahim, Onur Kayiran, Sreepathi Pai, and Adwait Jog. Architectural support for efficient large-scale automata processing. In 2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 908--920, New York, NY, USA, 2018. IEEE.

Digital Library

[21]

Hongyuan Liu, Sreepathi Pai, and Adwait Jog. Why GPUs are slow at executing NFAs and how to make them faster. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '20, pages 251--265, New York, NY, USA, 2020. ACM.

Digital Library

[22]

Hongyuan Liu, Sreepathi Pai, and Adwait Jog. Asynchronous automata processing on GPUs. Proc. ACM Meas. Anal. Comput. Syst., 7(1), mar 2023.

Digital Library

[23]

Jan Van Lunteren, Christoph Hagleitner, Timothy Heil, Giora Biran, Uzi Shvadron, and Kubilay Atasu. Designing a programmable wire-speed regular-expression matching accelerator. In 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture, pages 461--472, New York, NY, USA, 2012. IEEE.

Digital Library

[24]

Konstantinos Mamouras and Agnishom Chattopadhyay. Efficient matching of regular expressions with lookaround assertions. Proceedings of the ACM on Programming Languages, 8(POPL), 2024.

Digital Library

[25]

Pcre syntax. Available at https://www.pcre.org/original/doc/html/pcrepattern.html, 2023. [Online; Accessed 18 July, 2023].

[26]

Reza Rahimi, Elaheh Sadredini, Mircea Stan, and Kevin Skadron. Grapefruit: An Open-Source, Full-Stack, and Customizable Automata Processing on FPGAs. In 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), pages 138--147, New York, NY, USA, May 2020. IEEE.

[27]

RegexLib. Regular expression Library. Available at https://regexlib.com/, 2023. [Online; Accessed 17 July, 2023].

[28]

Martin Roesch. Snort - lightweight intrusion detection for networks. In Proceedings of the 13th USENIX Conference on System Administration, LISA '99, page 229--238, USA, 1999. USENIX Association.

Digital Library

[29]

Indranil Roy and Srinivas Aluru. Discovering motifs in biological sequences using the Micron Automata Processor. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13(1):99--111, 2016.

Digital Library

[30]

Elaheh Sadredini, Reza Rahimi, Marzieh Lenjani, Mircea Stan, and Kevin Skadron. Impala: Algorithm/architecture co-design for in-memory multi-stride pattern matching. In 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 86--98, 2020.

[31]

Elaheh Sadredini, Reza Rahimi, Vaibhav Verma, Mircea Stan, and Kevin Skadron. eAP: A scalable and efficient in-memory accelerator for automata processing. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO '52, pages 87--99, New York, NY, USA, 2019. ACM.

Digital Library

[32]

Christian J. A. Sigrist, Lorenzo Cerutti, Edouard de Castro, Petra S. Langendijk-Genevaux, Virginie Bulliard, Amos Bairoch, and Nicolas Hulo. PROSITE, a protein domain database for functional characterization and annotation. Nucleic Acids Research, 38(suppl_1):D161--D166, 2009.

[33]

Randy Smith, Cristian Estan, and Somesh Jha. XFA: Faster signature matching with extended automata. In Proceedings of the 2008 IEEE Symposium on Security and Privacy, SP '08, page 187--201, USA, 2008. IEEE Computer Society.

Digital Library

[34]

Snort. Snort - network intrusion detection & prevention system. Available at https://www.snort.org/, 2023. [Online; Accessed 17 July, 2023].

[35]

Ioannis Sourdis, Joao Bispo, Joao MP Cardoso, and Stamatis Vassiliadis. Regular expression matching in reconfigurable hardware. Journal of Signal Processing Systems, 51(1):99--121, 2008.

Digital Library

[36]

Nigel Stephens, Stuart Biles, Matthias Boettcher, Jacob Eapen, Mbou Eyole, Giacomo Gabrielli, Matt Horsnell, Grigorios Magklis, Alejandro Martinez, Nathanael Premillieu, Alastair Reid, Alejandro Rico, and Paul Walker. The arm scalable vector extension. IEEE Micro, 37(2):26--39, 2017.

Digital Library

[37]

Arun Subramaniyan, Jingcheng Wang, Ezhil R. M. Balasubramanian, David Blaauw, Dennis Sylvester, and Reetuparna Das. Cache automaton. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-50 '17, page 259--272, New York, NY, USA, 2017. ACM.

Digital Library

[38]

Suricata. Suricata - open source intrusion detection and prevention engine. Available at https://suricata.io/, 2023. [Online; Accessed 17 July, 2023].

[39]

Prateek Tandon, Faissal M Sleiman, Michael J Cafarella, and Thomas F Wenisch. HAWK: Hardware support for unstructured log processing. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 469--480, New York, NY, USA, 2016. IEEE.

[40]

Ken Thompson. Programming techniques: Regular expression search algorithm. Communications of the ACM, 11(6):419--422, 1968.

Digital Library

[41]

N. Tuck, T. Sherwood, B. Calder, and G. Varghese. Deterministic memory-efficient string matching algorithms for intrusion detection. In IEEE INFOCOM 2004, volume 4, pages 2628--2639 vol.4, New York, NY, USA, 2004. IEEE.

[42]

Lenka Turoňová, Lukáš Holík, Ondřej Lengál, Olli Saarikivi, Margus Veanes, and Tomáš Vojnar. Regex matching with counting-set automata. Proceedings of the ACM on Programming Languages, 4(OOP-SLA), 2020.

[43]

VirusTotal. YARA: The pattern matching swiss knife for malware researchers. Available at https://virustotal.github.io/yara/, 2023. [Online; Accessed 17 July, 2023].

[44]

Jack Wadden, Vinh Dang, Nathan Brunelle, Tommy Tracy II, Deyuan Guo, Elaheh Sadredini, Ke Wang, Chunkun Bo, Gabriel Robins, Mircea Stan, and Kevin Skadron. ANMLZoo: A benchmark suite for exploring bottlenecks in automata processing engines and architectures. In 2016 IEEE International Symposium on Workload Characterization (IISWC), pages 1--12. IEEE, 2016.

[45]

Jack Wadden, Tommy Tracy, Elaheh Sadredini, Lingxi Wu, Chunkun Bo, Jesse Du, Yizhou Wei, Jeffrey Udall, Matthew Wallace, Mircea Stan, and Kevin Skadron. AutomataZoo: A modern automata processing benchmark suite. In 2018 IEEE International Symposium on Workload Characterization (IISWC), pages 13--24, New York, NY, USA, 2018. IEEE.

[46]

Yuguang Wang, Robbie Watling, Junqiao Qiu, and Zhenlin Wang. GSpecPal: Speculation-centric finite state machine parallelization on GPUs. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 481--491, New York, NY, USA, 2022. IEEE.

[47]

Ted Xie, Vinh Dang, Jack Wadden, Kevin Skadron, and Mircea Stan. REAPR: Reconfigurable engine for automata processing. In 2017 27th International Conference on Field Programmable Logic and Applications (FPL), pages 1--8, New York, NY, USA, 2017. IEEE.

[48]

Yi-Hua E. Yang, Weirong Jiang, and Viktor K. Prasanna. Compact architecture for high-throughput regular expression matching on FPGA. In Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS '08, page 30--39, New York, NY, USA, 2008. ACM.

Digital Library

[49]

Fang Yu, Zhifeng Chen, Yanlei Diao, T. V. Lakshman, and Randy H. Katz. Fast and memory-efficient regular expression matching for deep packet inspection. In Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems, ANCS '06, pages 93--102, New York, NY, USA, 2006. ACM.

Digital Library

[50]

Zhipeng Zhao, Hugo Sadok, Nirav Atre, James C. Hoe, Vyas Sekar, and Justine Sherry. Achieving 100gbps intrusion prevention on a single server. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 1083--1100. USENIX Association, November 2020.

[51]

Yuan Zu, Ming Yang, Zhonghu Xu, Lin Wang, Xin Tian, Kunyang Peng, and Qunfeng Dong. GPU-based NFA implementation for memory efficient high speed regular expression matching. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '12, page 129--140, New York, NY, USA, 2012. ACM.

Digital Library

Cited By

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
Mamouras KLe Glaunec ALi WChattopadhyay A(2024)Static Analysis for Checking the Disambiguation Robustness of Regular ExpressionsProceedings of the ACM on Programming Languages10.1145/36564618:PLDI(2073-2097)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656461
Mamouras K(2024)Efficient Offline Monitoring for Dynamic Metric Temporal LogicRuntime Verification10.1007/978-3-031-74234-7_8(128-149)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-74234-7_8
Show More Cited By

Index Terms

BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions

Recommendations

Construction of fuzzy automata from fuzzy regular expressions

Li and Pedrycz have proved fundamental results that provide different equivalent ways to represent fuzzy languages with membership values in a lattice-ordered monoid, and generalize the well-known results of the classical theory of formal languages. In ...
Regular Transducer Expressions for Regular Transformations
LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

Functional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. In this paper, we show that every regular function, either on finite words or on infinite words, ...
Closure properties and descriptional complexity of deterministic regular expressions

We study the descriptional complexity of regular languages that are definable by deterministic regular expressions, i.e., we examine worst-case blow-ups in size when translating between different representations for such languages. As representations of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS '24: Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2

April 2024

1299 pages

ISBN:9798400703850

DOI:10.1145/3620665

General Chairs:
Nael Abu-Ghazaleh,
Rajiv Gupta,
Program Chairs:
Madan Musuvathi,
Dan Tsafrir

Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to 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 the author(s) 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

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 April 2024

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF (National Science Foundation)

Conference

ASPLOS '24

Sponsor:

ASPLOS '24: 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2

April 27 - May 1, 2024

CA, La Jolla, USA

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
208
Total Downloads

Downloads (Last 12 months)208
Downloads (Last 6 weeks)22

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Mamouras KLe Glaunec ALi WChattopadhyay A(2024)Static Analysis for Checking the Disambiguation Robustness of Regular ExpressionsProceedings of the ACM on Programming Languages10.1145/36564618:PLDI(2073-2097)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656461
Mamouras K(2024)Efficient Offline Monitoring for Dynamic Metric Temporal LogicRuntime Verification10.1007/978-3-031-74234-7_8(128-149)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-74234-7_8
Benny AChandran SKalayappan RPhawade RKurur P(2024)faRM-LTL: A Domain-Specific Architecture for Flexible and Accelerated Runtime Monitoring of LTL PropertiesRuntime Verification10.1007/978-3-031-74234-7_7(109-127)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-74234-7_7

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