Methods and systems for multi-pattern searching

• US 20060020595A1
• Filed: 07/26/2004
• Published: 01/26/2006
• 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,539,681 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 systems using the Aho-Corasick algorithm.

Claims

1. A method for building a state table of a state machine algorithm in a pattern matching application, comprising:

identifying at least one search pattern;

creating a search pattern trie;

adding the at least one search pattern to the search pattern trie;

building a non-deterministic finite automata from the search pattern trie;

building a deterministic finite automata from the non-deterministic finite automata;

converting the deterministic finite automata into separate data structures comprising a state transition table, an array of per state matching pattern lists, and a separate failure pointer list for each state for the non-deterministic finite automata; and

using the separate data structures as the state table.

2. The method of claim 1, the search pattern trie comprising a list of all valid characters for each state, each element of the list of all valid characters comprising a valid character and a next valid state, the at least one search pattern being added one character at a time, the non-deterministic finite automata replacing the search pattern trie with the non-deterministic finite automata in a list format, and the deterministic finite automata replacing the non-deterministic finite automata with the deterministic finite automata in a list format.

3. The method of claim 1, further comprising converting the characters of the at least one search pattern to uppercase.

4. The method of claim 1, the list of all valid characters for each state comprising a list of all valid uppercase characters for each state.

5. The method of claim 1, the state machine algorithm comprising Aho-Corasick.

6. The method of claim 1, 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.

7. The method of claim 1, the converting of the deterministic finite automata into a state transition table comprising:

allocating a state vector for each state, wherein there is a state transition element of the state vector for the each element of the list of all valid characters; and

copying the next valid state of the each element of the list of all valid characters into the each state transition elements of the state vector.

8. The method of claim 7, the state vector having two-hundred and fifty-six state transition elements.

9. The method of claim 7, each element of the state vector being sixteen bits.

10. The method of claim 7, an element of the state vector identifying the format of the state vector.

11. The method of claim 10, the format comprising full.

12. The method of claim 7, an element of the state vector identifying if the state vector comprises a matching pattern state.

13. The method of claim 1, the converting of the deterministic finite automata into a state transition table comprising:

defining as a band a list of elements from a first nonzero next valid state from the list of all valid characters to a last nonzero next valid state from the list of all valid characters;

allocating a state vector for each state, wherein there is a state transition element of the state vector for each element of the band;

creating an element of the state vector to identify an index of the first nonzero next valid state from the list of all valid characters;

creating an element of the state vector to identify a number of elements in the band; and

copying a next valid state of each element of the band into the each state transition element of the state vector.

14. The method of claim 13, each element of the state vector being sixteen bits.

15. The method of claim 13, an element of the state vector identifying the format of the state vector.

16. The method of claim 15, the format comprising banded.

17. The method of claim 16, an element of the state vector identifying if the state vector comprises a matching pattern state.

18. A method for searching for search patterns in a text sequence using a state transition table of a state machine algorithm in a pattern matching application, 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;

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, logging a pattern match;

selecting the current state vector corresponding to the nonzero value of the element; and

reading a next character from the text sequence.

19. The method of claim 18, further comprising converting the character to uppercase.

20. The method of claim 18, further comprising:

checking an element of the current state vector that identifies a format;

if the format is banded, 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;

if the format is banded and if the character is in the band, selecting the current state vector corresponding to the nonzero value of the element; and

if the format is banded and if the character is not in the band, returning the current state vector to an initial state.

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, logging the case sensitive version of the pattern match.

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

23. The method of claim 18, 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.

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.