Methods and systems for multi-pattern searching

• US 20070192286A1
• Filed: 04/19/2007
• Published: 08/16/2007
• 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: Norton, Marc, Roelker, Daniel
• Granted Patent: US 7,756,885 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 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 table with sixteen bit elements outperform state transition table 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-29. -29. (canceled)