Designs Of A Compiler For Hardware Circuits Of Regular Expression Matching Engines Based On NFA

Regular expression(regex)is widely used in field of computer.In many application scenarios of the pattern matching,using regexes as matching petterns is a usual method to match a character of a string.A regex can match an arbitrary character or string conforming to the rule pre-defined by a simple pettern.Regular expression matching has many application scenarios.In Unix/Linux system,regexes matching is used as a tool for the text recognition and matching.Nowadays,with the rapid development of the information technology(IT),the internet is widely used throughout the world,and a full link society is forming with the interconnection of all things.While the network technology brings convenience to human society,it also comes with a lot of unsafe information,which brings danger to the life of individual and the society.When facing the huge amount of data for the internet,in order to identify and filter the dangerous information,it is difficult to guarantee the safety of the network by the inefficient way of simply marking the specific elements of the dangerous information.Using regexes in intrusion detection systems(IDSs)to represent some dangerous payload contents is a more efficient way than using invariant patterns.Modern network security systems,such as IDSs,adopt the method of regex matching by constructing a software-based regex matching engine to filter dangerous information with known characteristics.However,with the rapid expansion of the data on the network and the rise of the artificial intelligence(AI),the mainstream approach of software-based regex matching engine based on the of CPU computing capability is not able to meet the requirement of real applications,especially in application scenarios of the server-side or data center which requires high data throughput.How to improve the efficiency of regular matching has become an urgent issue,which is needed to be solved in the network IDSs.With the development of some computer science based on heavy data stream,such as machine learning,many scholars have put forward the hardware transformation of the existing software platform,to improve the ability of data processing by hardware acceleration.Hardware acceleration technologies based on GPU,FPGA,even ASIC have drawn tremendous attention in recent years by many scholars.For each regular expression in regex rules set a unique Nondeterministic Finite Automaton(NFA)structure is needed to be converted.It is crucial to implement a fast NFA construction.As early as the last century,some scholars have conducted preliminary research on the corresponding hardware circuits of regular expressions matching modules.Hardware circuit models of some common regex matching units have been established.Some foreign companies have even released special regular matching hardware products.Until now,the research of regular expression hardware matching is still at a relatively blank stage in China.Some researchers have studied the basic algorithm of regular matching,but have not made breakthroughs in application.With the advent of the large data age,the demand for dedicated regular expression hardware circuits is increasing gradually.Based on the above situation in this paper,we improve the marking method of the original algorithm(MY algorithm)based on the previous research on the regular matching algorithm and design a compiler which can construct regular expression matching engine based of NFA quickly.We largely enrich the rules supported by the compiler making it a full-featured tool.The compiler covers all common rules and can be added specific rules easily due to the independence between differnent blocks.This paper presents a novel method for compiling large-scale regular expression matching(REM)on FPGA based on an NFA.We build an intelligent compiler for automatic converting regular expressions into codes of Verilog hardware description language(HDL)at the register transfer level(RTL),utilizing only logic slice available on FPGA because of the simplest architecture used in the back-end of our compiler.Due to the independent converting method between the converting flow and the block structure,the compiler can easily change the single pattern structure to build the most advanced regular expression-matching engine(REME)which can fit the realistic demand.On a personal computer(PC)with a 3.3 GHz Intel i5-4590 processor and 4 GB memory,our compiler can convert more than one thousand regular expressions in less than 15 seconds.During the converting flow,the compiler provides an arbitrary match string and corresponding test bench file in Verilog HDL as a part of the final output result.