Compact state machines for high performance pattern matching

Pattern matching is essential to a wide range of applica-tions such as network intrusion detection, virus scanning, etc. Pattern matching algorithms normally rely on state ma-chines to detect predefined patterns. Recently, parallel pat-tern matching engines, based on ASICs, FPGAs or network processors, perform matching with multiple state machines. The state migration in the matching procedure incurs in-tensive memory accesses. Thus, it is critical to minimize the storage of state machines such that they can be fit in on-chip or other fast memory modules to achieve high-speed pattern matching. This paper proposes novel optimization techniques, namely state re-labeling and memory partition, to reduce state machine storage. The paper also presents ar-chitectural designs based on the optimization strategy. We evaluate our design using realistic pattern sets, and the re-sults show state machine memory reduction up to 80.1%. Categories and Subject Descriptors C.3 [Special-purpose and Application-based Systems]: microprocessor/microcomputer applications; C.4 [Perform