Binary state machine system and method for REGEX processing of a data stream in an intrusion detection system

• US 6,880,087 B1
• Filed: 10/08/1999
• Issued: 04/12/2005
• Est. Priority Date: 10/08/1999
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Carter, Earl T.
• Primary Examiner(s): Barroń , Gilberto
• Assistant Examiner(s): NOBAHAR, ABDULHAKIM
• Application Number:
  US09/415,293
• Time in Patent Office: 2,013 Days
• Field of Search: 713/164, 713/188, 713/201, 713/200, 714/39, 714/819, 382/181, 382/182
• US Class Current: 726/23
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: H04L 63/02 for separating internal from external traffic, e.g. firewalls
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

A binary state machine system and method for REGEX processing of a data stream in an intrusion detection system are disclosed. The method comprises maintaining a state table. The state table is indexed such that inputs comprising a current state and a current character yield an output of a new state. The new state is related to an indication of an attack on a computer network. The method further includes maintaining the current state. An input stream comprising a plurality of characters is received. A first character of the input stream is selected as the current character. The current character and the current state are compared to the state table to generate a new state.

Claims

1. A method for using a binary state machine for processing a data stream in an intrusion detection system, the method comprising:

maintaining a state table, the state table indexed such that inputs comprising a current state and a current character yield an output of a new state, the new state related to an indication of an attack on a computer network;

maintaining the current state;

receiving an input stream comprising a first plurality of characters, a second plurality of characters, and at least one variable character between the first plurality and the second plurality of characters, wherein the first plurality and the second plurality of characters together constitute a REGEX signature;

processing the first plurality of characters using the state table;

after processing the first plurality of characters, for each one of the at least one variable character;

selecting the variable character as the current character;

generating a state for the current character that is independent of the current character;

after generating the state, selecting a first character of the second plurality of characters as the current character; and

after selecting the first character, comparing the current character and the current state to the state table to generate a new state.

2. The method of claim 1, further comprising initializing the current state to an initial state.

3. The method of claim 1, further comprising:

setting the current state equal to the new state;

selecting a next character of the second plurality of characters as the current character, the next character appearing subsequent to the first character; and

repeating the comparing step.

4. The method of claim 1, further comprising recognizing the new state as indicative of an attack upon the computer network.

5. The method of claim 1, further comprising sounding an alarm.

6. The method of claim 1, further comprising generating the state table from a REGEX command.

20. The method of claim 1, and further comprising:

setting the current state equal to the new state;

selecting a next character of the second plurality of characters as the current character, the next character appearing subsequent to the first character;

repeating the comparing step; and

wherein each character in the input stream is selected only once.

7. A system for use as a binary state machine for processing a data stream in an intrusion detection system, the system comprising:

a state table indexed such that inputs comprising a current state and a current character yield an output of a new state, the new state related to an attack on a computer network; and

a state machine communicatively coupled to the state table, the state machine operable to;

maintain the current state;

receive an input stream, the input stream comprising a first plurality of characters, a second plurality of characters, and at least one variable character between the first plurality and the second plurality of characters, wherein the first plurality and the second plurality of characters together constitute a REGEX signature

process the first plurality of characters using the state table;

after processing the first plurality of characters, for each one of the at least one variable character;

select the variable character as the current character;

generate a state for the current character that is independent of the current character;

after generating the state, select a first character of the second plurality of characters as the current character; and

after selecting the first character compare the current character and the current state to the state table to generate a new state.

8. The system of claim 7 further comprising a computer readable medium, wherein the state table is stored upon the computer readable medium.

9. The system of claim 8, wherein the state machine comprises software code stored upon the computer readable medium, the software code further operable to be executed by a computer processor.

10. The system of claim 7, wherein the state machine is further operable to initialize the current state to an initial state.

11. The system of claim 7, wherein the state machine is further operable to:

set the current state equal to the new state;

select a next character of the second plurality of characters as the current character, the next character appearing subsequent to the first character; and

repeat the comparing step.

12. The system of claim 7, wherein the state machine is further operable to recognizing the new state as indicative of an attack upon the computer network.

13. A system for use as an intrusion detection system, the system comprising:

a computer readable medium;

a network interface for receiving an input stream comprising a first plurality of characters, a second plurality of characters, and at least one variable character between the first plurality and the second plurality of characters, wherein the first plurality and the second plurality of characters together constitute a REGEX signature;

a processor communicatively coupled to the computer readable medium and the network interface;

a state table stored upon the computer readable medium, the state table indexed such that inputs comprising a current state and a current character yield an output of a new state, the new state related to an attack on a computer network; and

a state machine comprising instructions stored upon the computer readable medium and executable by the processor, the state machine communicatively coupled to the state table, the state machine operable to;

maintain the current state;

process the first plurality of characters using the state table;

after processing the first plurality of characters, for each one of the at least one variable character;

select the variable character as the current character;

generate a state for the current character that is independent of the current character;

after generating the state, select a first character of the second plurality of characters as the current character; and

after selecting the first character, compare the current character and the current state to the state table to generate a new state.

14. A logic for using a binary state machine for processing a data stream in an intrusion detection system, the logic embodied in a computer-readable medium and operable to:

maintain a state table, the state table indexed such that inputs comprising a current state and a current character yield an output of a new state, the new state related to an indication of an attack on a computer network;

maintain the current state;

receive an input stream comprising a first plurality of characters, a second plurality of characters, and at least one variable character between the first plurality and the second plurality of characters, wherein the first plurality and the second plurality of characters together constitute a REGEX signature

process the first plurality of characters using the state table;

after processing the first plurality of characters, for each one of the at least one variable character;

select the variable character as the current character;

generate a state for the current character that is independent of the current character;

after generating the state, select a first character of the second plurality of characters as the current character; and

after selecting the first character, compare the current character and the current state to the state table to generate a new state.

15. The logic of claim 14, further operable to initialize the current state to an initial state.

16. The logic of claim 14, further operable to:

set the current state equal to the new state;

select a next character of the second plurality of characters as the current character, the next character appearing subsequent to the first character; and

repeat the comparing step.

17. The logic of claim 14, further operable to recognize the new state as indicative of an attack upon the computer network.

18. The logic of claim 14, further operable to generate the state table from a REGEX command.

19. An intrusion detection system, comprising:

means for maintaining a state table, the state table indexed such that inputs comprising a current state and a current character yield an output of a new state, the new state related to an indication of an attack on a computer network;

means for maintaining the current state;

means for receiving an input stream comprising a first plurality of characters, a second plurality of characters, and at least one variable character between the first plurality and the second plurality of characters, wherein the first plurality and the second plurality of characters together constitute a REGEX signature;

means for processing the first plurality of characters using the state table;

means for selecting, after the first plurality of characters has been processed, each one of the at least one variable character as the current character and generating, for each selected variable character, a state for the current character that is independent of the current character;

means for selecting a first character of the second plurality of characters as the current character; and

means for comparing the current character and the current state to the state table to generate a new state; and

means for transmitting the copy of the input stream to the first network device if an attack on the computer network is not detected.