Fast Dynamic Pattern Matching for Deep Packet Inspection

High-speed packet content inspection and filtering devices rely on a fast multi-pattern matching algorithm which is used to detect predefined keywords or signatures in the packets. These signature sets are large (e.g., thousands) and complex. Multi-pattern matching is known to require intensive memory accesses and is often a performance bottleneck. Another problem is how to update the inconstant rule set from new attacks without halting the inspection. Hence, specialized fast dynamic pattern matching algorithms scalable for long rules are required for on-line speed deep packet inspection. We proposed a fast dynamic deep packet inspection algorithm using two pipelines which was flexible loosely coupled framework. In the fast pipeline, multiple parallel Counting Bloom filter engines which can perform fast dynamic query were adopted to achieve high throughput. Based on the principle of locality of programs, we set a threshold length for the scalability for long rules. In the relatively slow pipeline, we adopted dynamic pattern matching algorithm to distinguish the suspicious packet came from the fast pipeline. The analysis and the evaluation show that the high throughput of the algorithm can satisfy the wire speed dynamic inspection requirement when the low resource consumption further improves the scalability.