Fast RE set matching for network content inspection

There is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems perform content inspection in the use of regular expression-based pattern matching, since regular expressions offer superior expressive power and flexibility. The regular expression searching algorithms that use filtration are in general much faster searching. The effectiveness of this method depends basically on two factors, l_min and Pref (RE). l_min is the shortest length from the initial state to final states of the NFA and Pref (RE) is the prefixes of length l_min for all the strings in the language of the regular expression. The search speed is faster for longer l_min and less prefixes. In this paper a regular expression searching method based on bloom filter is proposed. It makes the searching speed notable fast and immune from the size of Pref (RE). Especially, if multiple bloom filter engines are used, the shift distance may be larger than l_min. Experiments showed that the method can achieve much higher speed than currently known algorithms and the acceleration is especially remarkable for set of regular expression matching.