Optimized memory based accelerator for scalable pattern matching

One of the most promising techniques to detect and thwart a network attack in a network intrusion detection system is to compare each incoming packet with pre-defined attack patterns. This comparison can be performed by a pattern matching engine which has several key requirements including scalability to line rates of network traffic and easy updating of new attack patterns. Memory-based deterministic finite automata meet these requirements, however their storage requirement will grow exponentially with the number of patterns which makes it impractical for implementation. In this paper, we propose a customized memory-based pattern matching engine, whose storage requirement linearly increases' with the number of patterns. The basic idea is to allocate one memory slot for each state instead of each edge of the deterministic finite automaton. To demonstrate this idea, we have developed two customized memory decoders. We evaluate them by comparing with a traditional approach in terms of programmability and resource requirements. We also examine their effectiveness for different optimized deterministic finite automata. Experimental results are presented to demonstrate the validity of our proposed approach. (C) 2009 Elsevier B.V. All rights reserved.