Cyansemi Regex Pattern Match on Xilinx Alveo U50

Background

Increasing network speeds drive network intrusion detection systems to demand ever greater throughputs. New applications such as text analytics for business intelligence are emerging that also rely increasingly on deep inspection of packet contents.

Regular-expression (shorten as RegEx) matching algorithms are important facilities in above applications. Although the basic research in the field has existed for many decades, some new and fast software solutions like RE2 and hyperscan have been developed and widely adopted, but the new requirements imposed by fast growing network link speeds and for supporting larger and more complex pattern sets are still calling for innovative approaches.

Implementation

We developed a hardware accelerator for Regex Pattern Match. It is implemented in Xilinx Vitis platform, as a RTL Kernel. It has been tested on Alveo U50 card. The working scheme is:

• Host application (software) compiles the input regular expressions to a "pattern db" and calls DMA device driver (or the build-in XRT buffer object mover) to transfer it to Pattern Memory. Pattern Memory uses Alveo U50 HBM for this implementation, but it can also be stored in BRAM or DDR.
• Host application (software) transfers the Packets from Host memory to FPGA card. In the demo, it opens Packet file, loads the content into a buffer allocated in Host memory, and calls XRT buffer object mover to transfers it to Alveo U50 HBM (different ranks to the Pattern area). When the data transfer completes, host application starts the kernel and waits for the kernel interrupt which indicates its completion. When a kernel completes, host application reads the match results back to the result buffer in host memory and compares with software reference model to verify the correctness.
• On FPGA hardware, Regex Kernel is a RTL Kernel and be embedded into Vitis Shell. It adopts the standard Kernel interface which includes a AXI-Lite configuration port and AXI Memory mapped ports to fetch data from HBM memory.
• The Regex Kernel has two parts: The Kernel wrapper(shim) and the Regex core. Kernel wrapper implements the register layout and also converts AXI-MM data flow to AXI-Stream flow by two directions. It interprets the data header (The 16Bytes header has the information of Packet Length, ID and a header indicator) and composes the matching result (The matching result has the information of Packet ID, Pattern ID and matching offset). Kernel wrapper reads the Text packets and Regex patterns from HBM, and writes the matching results back to HBM. It also updates the status bits in Control registers so the host application knows when to move the results back.

• The Regex core uses a parallel and pipelined structure to accept the Packet AXI4-Stream and Pattern AXI4-Stream and process them. It has several state-transition tables and a chained comparators for input characters and regex characters. It implements a NFA (Non-deterministic Finite Automaton) scheme for the regular expressions.

Features:

• The demo instanced 3 kernels with at frequency of 180MHz.
• It supports parsing 8 patterns in parallel. (It also supports more than 8 patterns, but the throughput will drop proportionally)
• Each Kernel's data bus width is 128bits. When the pattern number is 8 or less, it supports theriodical bandwidth of 128b*Frequency. The overall data thoughput calculation is: BW = 128b * Freq * Kernel_number
• The Regex core can be configured by parameters to determin the hardware limitation to regular expressions (like maximum characters of a Regex pattern, max number of the states, length of the data packets, etc).

Introduction Video (with subtitles):

Demo:

https://github.com/cyansemi/csre-demo-v1

The detailed steps are introduced in its README.md

Demo Video (in Chinese):

https://v.youku.com/v_show/id_XNDk5NDYxNTQwOA==.html

https://v.youku.com/v_show/id_XNDk5NTQ4NjUwNA==.html

https://v.youku.com/v_show/id_XNDk5NTQ4NzUwOA==.html