FSM Circuits Design for Approximate String Matching in Hardware Based Network Intrusion Detection Systems

In this paper we present a logical circuits design for approximate content matching implemented as finite state machines (FSM). As network speed increases the software based network intrusion detection and prevention systems (NIDPS) are lagging behind requirements in throughput of so called deep package inspection - the most exhaustive process of finding a pattern in package payloads. Therefore, there is a demand for hardware implementation. Approximate content matching is a special case of content finding and variations detection used by "evasion" techniques. In this research we will enhance the k-differentiate problem with "ability" to detect a generalized Levensthein edit distance i.e. transposition of two neighboring characters. The proposed designs are based on automata theory using the concept of state reduction and complexity minimization. The main objective is to present the feasibility of the hardware design and the trade-off between the simple next state and output functions of NFA and reduced number of required memory elements (flip-flops) of DFA.