Product Details
Module for hash-based pattern matching using approximate computing techniques
Created: 2021
Kořenek Jan, doc. Ing., Ph.D. (DCSY)
Košař Vlastimil, Ing., Ph.D. (DCSY)
Matoušek Jiří, Ing., Ph.D. (DCSY)
Kekely Lukáš, Ing., Ph.D. (DCSY)
Iša Radek, Ing.
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.