NFA Based Regular Expression Matching on FPGA

Creative Commons License

SERT K., Bazlamacci C. F.

2021 International Conference on Computer, Information, and Telecommunication Systems, CITS 2021, İstanbul, Turkey, 11 - 13 November 2021 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/cits52676.2021.9618426
  • City: İstanbul
  • Country: Turkey
  • Keywords: regular expression matching, regex, string matching, NFA, network intrusion detection, network security, EFFICIENT, HARDWARE, ENGINE
  • Middle East Technical University Affiliated: Yes


© 2021 IEEE.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.