An Extended Automata to Efficiently Match Counting Constraints Patterns

Regular expression matching is an important application in the area of network security. In this paper, we analyse the limitation of the existing methods and show the classification of counting constraints patterns. We then present a new representation for deterministic finite automata, called Bitmap Shift Finite Automata (Bs-FA), which introduces condition function and bitmap structure. Bs-FA handles counting constraints patterns effectively and considerably reduces memory space requirement of states by evaluating this method on signature sets used in Snort. Overall, for all signature sets and compression methods evaluated of counting constraints patterns, Bs-FA offers the best memory reduction.