DFA-based and SIMD NFA-based Regular Expression Matching on Cell BE for Fast Network Traffic Filtering

摘要

Regular expression matching is the heart of many data processing routines, such as string search, network traffic filtering, etc. The traditional way of regexp matching is building and execution of a deterministic finite automaton (DFA), that provides O(1) processing time per 1 input symbol for any regular expression. But this technique almost always forces many modern SIMD-processors to perform regexp search in scalar mode, thus it doesn't use the most part of their computational power.This paper represents traditional straightforward DFA along with another regexp implementation, based on nondeterministic finite automata (NFA) SIMD-simulation on Cell Broadband Engine processor. Software implementation of NFA-based SIMD algorithm achieves as much as 10 Gbit/s per one Cell BE processor with 512 NFA states, thus it is feasible for preliminary network traffic filtering of suspicious objects, while DFA-based scalar one gains up to 60 Gbit/s with 60-state automaton. One Cell BE processor can maintain NFA of 6000..7000 overall states simultaneously, so if one wants to use signatures with more that 512 states, it's possible with linear performance-to-signatures tradeoff.