BFSM-based accelerators

Project description

We have developed a novel hardware-based pattern-matching engine intended for accelerating networking applications that require fast and efficient content scanning of data (packets, messages) against a predetermined list of patterns or signatures. The flexible and modular design of the engine allows us to target a broad spectrum of applications having a variety of performance and cost requirements, ranging from high-end enterprise level network devices that need pattern-matching capabilities at speeds of multiple tens of Gb/s and involving tens of thousands of patterns, to low-end devices for home networks operating at speeds of only a few Mb/s with a modest number of patterns [3]. A key application of the engine is intrusion detection. The core of the engine consists of a scanner unit that is based on a novel programmable state machine technology called BFSM. This technology allows us to implement programmable state machines in hardware that is able to achieve a deterministic performance of one transition per clock cycle for clock frequencies ranging from several hundred MHz (FPGA) into the GHz range (ASIC). One of the key design objectives was to realize very high storage efficiency, as this allows us to fit larger portions of the data structure into fast on-chip caches, with the resulting high hit rates and enhancement of performance.

As a result, the BFSM-based pattern-matching scheme, introduced in [4], is currently one of the most storage-efficient schemes reported in the literature. It is capable of achieving scan rates of multiple tens of gigabits per second in ASIC technology, while scanning input streams against tens of thousands of patterns in parallel. Compared to the original scheme described in [1], recent research has resulted in multiple extensions for improved handling of advanced regular expressions, including direct support for character classes and case-insensitive matches at the transition rule level. This enables substantially more compact representations, and thus higher scan rates, for a broader range of regular expression features. The latter is essential to keep up with the trend of network attacks becoming increasingly sophisticated, requiring more powerful and flexible content-filtering rules to detect them.

diagram of BFSM-based pattern-matching scheme
Block diagram of BFSM-based pattern-matching scheme.