Pattern matching using deterministic finite automata and organization of such automata

• US 7,672,941 B2
• Filed: 02/22/2005
• Issued: 03/02/2010
• Est. Priority Date: 01/21/2005
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Law, David John, Hailichova, Hana, Stack, Eoghan, Furlong, Peter
• Primary Examiner(s): Ehichioya; Fred I
• Application Number:
  US11/064,257
• Publication Number:
  US 20060167915A1
• Time in Patent Office: 1,834 Days
• Field of Search: 707/1, 707/6, 707/100, 707/200, 709/230, 711/104, 375/368, 370/392
• US Class Current: 713/176
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

A deterministic finite state machine is operated to detect any one of a plurality of digital signatures each corresponding to a succession of characters and each defined by a sequence of states in the state machine. The machine is organized such that for each state after the first in any sequence there are not more than two allowed exit transitions of which one is to a default state. Input characters are examined to determine a transition from a current state of the machine to a next state. When the machine responds to an input character to perform a transition to the default state, the input character is re-examined to determine the next state of the state machine. The reduction in transitions saves considerable space in memory.

Claims

1. A method of operating a deterministic finite state machine as implemented in an integrated circuit to detect any one of a plurality of signatures each corresponding to a succession of characters and each defined by a sequence of states in the state machine, the method comprising;

organizing the states of the machine such that for each state after the first in any sequence there are not more than two allowed exit transitions of which one is to a default state;

examining a stream of input characters received from a communications network to determine in response to each input character a transition from a current state of the machine to a next state; and

when the machine responds to an input character to perform a transition to the default state, re-examining that input character to determine the next state of the state machine wherein input characters are held in a memory from which they are automatically read by an incrementing reader and the method further comprises comparing the current state of the machine with the default state and on detection of a match inhibiting for one incrementing cycle the incrementing of the reader.

2. A method as in claim 1 wherein transitions are allowed between the respective first states of at least some of said sequences.

3. A method as in claim 1 wherein for the last state in a sequence there is a single allowed exit transition to the default state.

4. An integrated circuit containing a deterministic finite state machine organized to detect any one of a plurality of signatures each corresponding to a succession of characters and each defined by a sequence of states in the state machine, wherein the machine is organized:

(a) such that for each state after the first in any sequence there are not more than two allowed exit transitions of which one is to a default state;

(b) to examine a stream of input characters received from a communications network to determine in response to each input character a transition from a current state of the state machine to a next state; and

(c) when the state machine responds to an input character to perform a transition to said default state, to re-examine that input character to determine the next state of the state machine wherein the finite state machine comprises;

a memory for holding successively received input characters;

an incrementing reader for reading the input characters; and

a comparator to compare the current state of the machine with the default state and on detection of a match to inhibit for one incrementing cycle the incrementing of the reader.

5. A deterministic finite state machine as in claim 4 wherein for the last state in a sequence there is a single allowed exit transition to the default state.

6. A deterministic finite state machine as in claim 5 wherein transitions are allowed between the respective first states of at least some of said sequences.

7. An integrated circuit implementing a deterministic finite state machine organized to detect any one of a plurality of signatures each corresponding to a succession of characters, said state machine comprising:

a memory table defining a multiplicity of states and allowed transitions between some of said states, said states defining a multiplicity of state sequences each corresponding to one of said signatures, and wherein for each state after the first in any sequence there are not more than two allowed exit transitions of which one is to a default state;

a memory for holding successively received input characters received from a communications network;

an incrementing reader for reading the input characters to determine in response to each input character a transition from a current state of the state machine to a next state; and

a comparator operative, when the state machine responds to an input character to perform a transition to said default state, to compare the current state of the machine with the default state and on detection of a match to inhibit for one incrementing cycle the incrementing of the reader whereby the state machine re-examines that input character to determine the next state of the state machine.

8. A deterministic finite state machine as in claim 7 wherein said memory table allows transitions between the respective first states of at least some of said sequences.