×

Methods and systems for multi-pattern searching

  • US 7,996,424 B2
  • Filed: 01/31/2008
  • Issued: 08/09/2011
  • Est. Priority Date: 07/26/2004
  • Status: Expired due to Fees
First Claim
Patent Images

1. 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 as a search pattern;

    reading an element of a current state vector of a current state of the state transition table that corresponds to the character, the state transition table and the array of per state pattern matching lists being separate data structures;

    checking a pattern matching element of the current state vector for a matching pattern flag, when the element of the current state vector of the current state of the state transition table that corresponds to the character has a nonzero value, the state transition table and the array of per state pattern matching lists being separate data structures;

    processing, in an intrusion detection processor device, the patterns in the text sequence that match pattern matching lists of the current state to detect an intrusion, when the matching pattern flag is set;

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

    reading a next character from the text sequence, wherein the state transition table has a list of pointers to state vectors, each state vector representing valid transitions for the state, 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;

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

    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, when the storage format is banded-row form;

    then,selecting the current state vector corresponding to the nonzero value of the element, when the character is in the band and the storage format is banded-row form;

    returning the current state vector to an initial state, when the character is not in the band and the storage format is banded-row form; and

    handling the character in accordance with a non-banded row format, when the storage format is not banded row form.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×