Product Details
Module for hash-based pattern matching using approximate computing techniques
Created: 2021
Kořenek Jan, doc. Ing., Ph.D. (DCSY FIT BUT)
Košař Vlastimil, Ing., Ph.D. (DCSY FIT BUT)
Matoušek Jiří, Ing., Ph.D. (DCSY FIT BUT)
Kekely Lukáš, Ing., Ph.D. (DCSY FIT BUT)
Iša Radek, Ing. (DCSY FIT BUT)
FPGA, patten match, hash, approximate computing, regular expression
This software package contains an acceleration component for regular expression matching. To reduce the hardware resource requirements, approximate computing techniques are used. The standard pattern matching is replaced by matching only short strings derived from the original regular expression set. Hardware resources are significantly reduced at the cost of a slight decrease in matching accuracy. The approximation allows only false-positive matches, which are subsequently removed in detailed software processing. The Acceleration components are fully configurable and support processing of input data at throughputs in the order of hundreds of Gb/s for large rule sets. In addition, the rule set can be dynamically modified on the fly.
The package also includes a tool for deriving short strings from the original regular expression set. Using graph algorithms, significant strings are extracted from the regular expressions. Using the input data (network traffic) model, the strings are derived to keep their probability in the input data as low as possible to maximize search accuracy.