Methods and systems for multi-pattern searching

• US 20080133523A1
• Filed: 01/31/2008
• Published: 06/05/2008
• Est. Priority Date: 07/26/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Sourcefire Incorporated (Cisco Systems, Inc.)
• Inventors: Roelker, Daniel J., Norton, Marc A.
• Granted Patent: US 7,996,424 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/922 Communications
• CPC Class Codes: Y10S 707/99939 Privileged access

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.

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.

19. The method of claim 18, further comprising converting the character to uppercase before the reading of the element of the state transition table and before the reading of the next character.

20. The method of claim 18, wherein each state vector further includes an indicator that identifies a storage format of the element of the state transition table as being in a full vector form where a state vector with a predetermined full number of elements or in a banded-row form where a state vector has a variable number of elements reduced from the predetermined full number, further comprising:

checking the indicator of the current state vector that identifies the storage format;

if the storage format is banded-row form, determining if 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, if the character is in the band, selecting the current state vector corresponding to the nonzero value of the element;

otherwise if the character is not in the band, returning the current state vector to an initial state;

otherwise

handling the character in accordance with a full vector format.

21. The method of claim 19, further comprising:

if the matching pattern flag is set, comparing a case sensitive version of the pattern match from the text sequence and a case sensitive version of a search pattern; and

if the matching pattern flag is set and if the case sensitive version of the pattern match from the text sequence and the case sensitive version of a search pattern match, processing the case sensitive version of the pattern match.

22. The method of claim 18, the state machine algorithm comprising Aho-Corasick.

30. The method of claim 18, wherein:

the state transition table is stored in is stored in cache memory,

the array of per state pattern matching lists is stored in a memory different from the cache memory,

the reading of the element of the current state vector of the state transition table is done from the state transition table in the cache memory, and

the processing with the pattern matching lists is done from the per state pattern matching lists in the memory different from the cache memory.

31. The method of claim 18, wherein each of the elements in the state transition table has a size of two bytes.

32. The method of claim 20, wherein the state vector in full vector form holds two hundred fifty six transition elements.

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.

25. The state table of claim 24, the state transition table comprising a state vector for each state.

26. The state table of claim 25, the state vector being stored in a sparse vector format.

27. The state table of claim 25, the sparse vector format comprising one of compressed sparse vector format, sparse-row format, and banded-row format.

28. The state table of claim 24, the state machine algorithm comprising Aho-Corasick.

29. The state table of claim 24, the pattern matching application comprising one of an intrusion detection system, a passive network monitor, an active network monitor, a protocol analyzer, and a search engine.

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.

34. The computer-readable medium of claim 33, further comprising converting the character to uppercase before the reading of the element of the state transition table and before the reading of the next character.

35. The computer-readable medium of claim 34, further comprising:

if the matching pattern flag is set, comparing a case sensitive version of the pattern match from the text sequence and a case sensitive version of a search pattern; and

if the matching pattern flag is set and if the case sensitive version of the pattern match from the text sequence and the case sensitive version of a search pattern match, processing the case sensitive version of the pattern match.

36. The computer-readable medium of claim 33, wherein each state vector further includes an indicator that identifies a storage format of the element of the state transition table as being in a full vector form where a state vector with a predetermined full number of elements, or in a banded-row form where a state vector has a variable number of elements reduced from the predetermined full number, further comprising:

checking the indicator of the current state vector that identifies the storage format;

if the storage format is banded-row form, determining if 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, if the character is in the band, selecting the current state vector corresponding to the nonzero value of the element;

otherwise if the character is not in the band, returning the current state vector to an initial state;

otherwise

handling the character in accordance with a full vector format.

37. The computer-readable medium of claim 33, wherein:

the state transition table is stored in is stored in cache memory,

the array of per state pattern matching lists is stored in a memory different from the cache memory,

the reading of the element of the current state vector of the state transition table is done from the state transition table in the cache memory, and

the processing with the pattern matching lists is done from the per state pattern matching lists in the memory different from the cache memory.