Methods and systems for multi-pattern searching
First Claim
1. A method for searching for search patterns in a text sequence using a state transition table of a state machine algorithm in an intrusion detection system, comprising:
- reading a character from the text sequence;
reading an element of a current state vector of the state transition table that corresponds to the character;
when the element has a nonzero value, checking a pattern matching element of the current state vector for a matching pattern flag;
when the matching pattern flag is set, processing the matched patterns in the text sequence in an intrusion detection system to detect an intrusion;
selecting the current state vector corresponding to the nonzero value of the element;
reading a next character from the text sequence;
checking an element of the current state vector that identifies a format; and
when the format is banded, determining whether the character is in a band from an element of the current state vector identifying a number of elements in the band, an element of the current state vector identifying an index of a first element of the band, and elements of the band;
then, when the character is in the band, selecting the current state vector corresponding to the nonzero value of the element;
otherwise when the character is not in the band, returning the current state vector to an initial state;
otherwisehandling the character in accordance with a full vector format.
3 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 systems using the Aho-Corasick algorithm.
-
Citations
8 Claims
-
1. A method for searching for search patterns in a text sequence using a state transition table of a state machine algorithm in an intrusion detection system, comprising:
-
reading a character from the text sequence; reading an element of a current state vector of the state transition table that corresponds to the character; when the element has a nonzero value, checking a pattern matching element of the current state vector for a matching pattern flag; when the matching pattern flag is set, processing the matched patterns in the text sequence in an intrusion detection system to detect an intrusion; selecting the current state vector corresponding to the nonzero value of the element; reading a next character from the text sequence; checking an element of the current state vector that identifies a format; and when the format is banded, determining whether the character is in a band from an element of the current state vector identifying a number of elements in the band, an element of the current state vector identifying an index of a first element of the band, and elements of the band;
then, when the character is in the band, selecting the current state vector corresponding to the nonzero value of the element;
otherwise when the character is not in the band, returning the current state vector to an initial state;
otherwisehandling the character in accordance with a full vector format. - View Dependent Claims (2, 3, 4)
-
-
5. 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 transition table of a state machine algorithm in an intrusion detection system, the instructions for implementing the steps of:
-
reading a character from the text sequence; reading an element of a current state vector of the state transition table that corresponds to the character; when the element has a nonzero value, checking a pattern matching element of the current state vector for a matching pattern flag; when the matching pattern flag is set, processing the matched patterns in the text sequence in an intrusion detection system to detect an intrusion; selecting the current state vector corresponding to the nonzero value of the element; reading a next character from the text sequence; checking an element of the current state vector that identifies a format; and when the format is banded, determining whether the character is in a band from an element of the current state vector identifying a number of elements in the band, an element of the current state vector identifying an index of a first element of the band, and elements of the band;
then, when the character is in the band, selecting the current state vector corresponding to the nonzero value of the element;
otherwise when the character is not in the band, returning the current state vector to an initial state;
otherwisehandling the character in accordance with a frill vector format. - View Dependent Claims (6, 7, 8)
-
Specification