NFA Based Regular Expression Matching on FPGA

Date

2021-01-01

Author

Sert, Kamil
Bazlamacci, Cuneyt F.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

87
views

2
downloads

String matching is about finding all occurrences of a string within a given text. String matching algorithms have important roles in various real world areas such as web and security applications. In this work, we are interested in solving regular expression matching hence a more general form of string matching problem targeting especially the field of network intrusion detection systems (NIDS). In our work, we enhance a non-deterministic finite automata (NFA) based method on FPGA considerably. We propose to use a matching structure that processes two consecutive characters instead of one in order to yield better memory utilization and provide a novel mapping of this new architecture onto FPGA. The amount of digital circuitry needed to represent the NFA is reduced due to having less number of states and less number of LUTs in the devised 2-character regex matching process. An evaluation study is performed using the well-known Snort rule set and a sizable performance improvement is demonstrated.

Subject Keywords

network intrusion detection, network security, NFA, regex, regular expression matching, string matching

URI

https://hdl.handle.net/11511/99703

DOI

https://doi.org/10.1109/cits52676.2021.9618426

Conference Name

2021 International Conference on Computer, Information, and Telecommunication Systems, CITS 2021

Collections

Department of Electrical and Electronics Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

NFA based regular expressıon matchıng on FPGA Sert, Kamil; Bazlamaçcı, Cüneyt Fehmi; Department of Electrical and Electronics Engineering (2018) String matching is about finding all occurrences of a string within a given text, which is a classical but still a popular problem. String matching algorithms have important roles in various real world areas, such as web and security applications. In this work, we are interested in solving regular expression and hence string matching problem targeting especially the network intrusion detection systems (NIDS) field. An NIDS engine inspects both the header and the content of the packet and hence performs a ty...
Fast, efficient and dynamically optimized data and hardware architectures for string matching Zengin, Salih; Güran, Hasan Cengiz; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2014) Many fields of computing such as network intrusion detection employ string matching modules (SMM) that search for a given set of strings in their input. An SMM is expected to produce correct outcomes while scanning the input data at high rates. Furthermore, the string sets that are searched for are usually large and their sizes increase steadily. In this thesis, motivated by the requirement of designing fast, accurate and efficient SMMs; we propose a number of SMM architectures that employ Bloom Filters to ...
Shape recognition using attributed string matching with polygon vertices as the primitives Kaygin, S; Bulut, Mehmet Mete (2002-01-01) Attributed string matching has been utilized for polygon matching in various applications, in which line segments are the primitives. Adding a merge operator avoids the segmentation inconsistencies due to the noisy images or distorted shapes, however it is computationally expensive. In this paper, the vertices of the polygons are suggested as the primitives of the attributed strings. Deletion and insertion of a vertex corresponds to merging two consecutive line segments and splitting a line segment, respect...
Local left invertibility for operator tuples and noncommutative localizations Dosiev, Anar (Cambridge University Press (CUP), 2009-01-01) In the paper we propose an operator approach to the noncommutative Taylor localization problem based on the local left invertibility for operator tuples acting on a Frechet space. We prove that the canonical homomorphism U(g) -> O(g) of the universal enveloping algebra U(g) of a nilpotent Lie algebra g into its Arens-Michael envelope O(g) is the Taylor localization whenever g has normal growth.
Hybrid classes of balanced Boolean functions with good cryptographic properties Khan, Mansoor Ahmed; Özbudak, Ferruh (2014-07-20) Cryptographically strong Boolean functions play an imperative role in the design of almost every modern symmetric cipher. In this context, the cryptographic properties of Boolean functions, such as non-linearity, algebraic degree, correlation immunity and propagation criteria, are critically considered in the process of designing these ciphers. More recently, with the emergence of algebraic and fast algebraic attacks, algebraic immunity has also been included as an integral property to be considered. As a r...

Citation Formats

K. Sert and C. F. Bazlamacci, “NFA Based Regular Expression Matching on FPGA,” presented at the 2021 International Conference on Computer, Information, and Telecommunication Systems, CITS 2021, İstanbul, Türkiye, 2021, Accessed: 00, 2022. [Online]. Available: https://hdl.handle.net/11511/99703.