About

This tool was the result of some work I did on deep packet inspection for firewalls. It can be used to generate a regular expression matching FSM in verilog. The generated FSM has the following ports:

input [7:0] payload;
input en;
input clk;
input reset;
output match;

Data is presented 1 byte per clock on the "payload" lines in ASCII format along with "en" signal held high. The FSM keeps a track of the stream of bytes showing up and asserts the "match" output when it detects a match. The state machine has 1 comparator and 1 flip-flop per symbol. If the regular expression uses numerical ranges, the FSM will also have counters. To estimate max clock frequency, critical path between FFs will typically have an 8-bit comparator plus less than 5 NAND gates.

Regex in Hardware

Regex matching hardware accelerators are costly mainly because they have to support programmability of regular expressions. Typical networking applications, however, do not have to update match rules (including regex definitions) on the fly. For example, with an IDS like snort, match rules are updated once every 10-15 days.

Tailor made FSMs for given set of regex's can be much faster and can cost much less in terms of gate and flop clount as compared to programmable ones. The premise of this project was that if these tailored FSMs can be generated automatically, then the whole process of translating regular expressions to FPGA bitfiles can be automated. These bitfiles can then be uploaded to hardware accelerator cards.

Feedback

Please feel free to provide any suggestion, feedback or comment you may have.
View Devesh Mittal's LinkedIn profileView Devesh Mittal's profile