Methods and systems for multi-pattern searching
2 Assignments
0 Petitions
Accused Products
Abstract
Embodiments of the present invention relate to systems and methods for optimizing and reducing the memory requirements of state machine algorithms in pattern matching applications. Memory requirements of an Aho-Corasick algorithm are reduced in an intrusion detection system by representing the state table as three separate data structures. Memory requirements of an Aho-Corasick algorithm are also reduced by applying a banded-row sparse matrix technique to the state transition table of the state table. The pattern matching performance of the intrusion detection system is improved by performing a case insensitive search, where the characters of the test sequence are converted to uppercase as the characters are read. Testing reveals that state transition tables with sixteen bit elements outperform state transition tables with thirty-two bit elements and do not reduce the functionality of intrusion detection system using the Aho-Corasick algorithm.
-
Citations
37 Claims
-
1-17. -17. (canceled)
-
18. A method for searching for search patterns in a text sequence using a state table of a state machine algorithm in an intrusion detection system, wherein the state table includes a state transition table and an array of per state pattern matching lists, comprising:
-
reading a character from the text sequence; reading an element of a current state vector of a current state of the state transition table that corresponds to the character; if the element has a nonzero value, checking a pattern matching element of the current state vector for a matching pattern flag; if the matching pattern flag is set, processing the patterns in the text sequence that match pattern matching lists of the current state; selecting the current state vector corresponding to the nonzero value of the element; and reading a next character from the text sequence, wherein the state transition table and the array of per state pattern matching lists are separate data structures, the state transition table has a list of pointers to state vectors, each state vector representing valid transitions for the state. - View Dependent Claims (19, 20, 21, 22, 30, 31, 32)
-
-
23. (canceled)
-
24. A state table for a state machine algorithm used in a pattern matching application, comprising:
-
a state transition table; an array of per state matching pattern lists; and a failure pointer list for each state for a non-deterministic finite automata. - View Dependent Claims (25, 26, 27, 28, 29)
-
-
33. A computer-readable medium comprising instructions being executed by a computer, the instructions including a computer-implemented method for searching for search patterns in a text sequence using a state table of a state machine algorithm in an intrusion detection system, wherein the state table includes a state transition table and an array of per state pattern matching lists, the instructions for implementing the steps of:
-
reading a character from the text sequence; reading an element of a current state vector of a current state of the state transition table that corresponds to the character; if the element has a nonzero value, checking a pattern matching element of the current state vector for a matching pattern flag; if the matching pattern flag is set, processing the patterns in the text sequence that match pattern matching lists of the current state; selecting the current state vector corresponding to the nonzero value of the element; and reading a next character from the text sequence, wherein the state transition table and the array of per state pattern matching lists are separate data structures, the state transition table has a list of pointers to state vectors, each state vector representing valid transitions for the state. - View Dependent Claims (34, 35, 36, 37)
-
Specification