Methods and systems for using state ranges for processing regular expressions in intrusion-prevention systems

1. In an intrusion-prevention system for examining network traffic and identifying therein the presence of signature data patterns, a method comprising:

providing a state-transition table representative of a predetermined data pattern, the state-transition table comprising a plurality of states, each state having a set of egress events, each egress event defining a transition from a current state to a next state;

receiving a subject to be evaluated for the presence of the predetermined data pattern;

while using the state-transition table to evaluate the subject for the presence of the predetermined data pattern, detecting in the subject the presence of a first egress event of a first state, the first egress event defining a transition from the first state to a second state, and responsively transitioning from the first state to the second state;

calculating, by a processor, a second-state range, the second-state range being a range of positions in the subject in which to search for the presence of at least one of the second state's egress events; and

searching, by the processor, the subject within the second-state range for the presence of at least one of the second state's egress events.

2. The method of claim 1 , wherein the state-transition table is representative of a state diagram, the state diagram representative of the predetermined data pattern.

3. The method of claim 1 , wherein the predetermined data pattern is representative of a regular expression.

4. The method of claim 1 , wherein each egress event is either a character class or a character string.

5. The method of claim 1 , wherein the subject comprises a payload of one or more packets.

6. The method of claim 1 , wherein the presence of the predetermined data pattern is indicative of a potential security threat.

7. The method of claim 1 , wherein a cursor corresponds to a location in the subject that is currently being evaluated.

8. The method of claim 7 , wherein the first state has an associated first-state range in the subject, and wherein calculating the second-state range comprises:

setting a start of the second-state range equal to the cursor;

starting at the cursor, and extending no further than an end of the first-state range, determining that the subject includes a number of consecutive instances of the first egress event, the consecutive instances ending at a first position in the subject; and

setting an end of the second-state range based on the first position.

9. The method of claim 8 , further comprising determining that the second state does not have a character-class loop transition.

10. The method of claim 8 , further comprising calculating the first-state range.

11. The method of claim 7 , wherein calculating the second-state range comprises:

determining that the second state has a character-class loop transition;

setting a start of the second-state range equal to the cursor;

starting at the cursor, determining that the subject includes a number of consecutive characters that satisfy the character-class loop transition, the consecutive instances ending at a first position in the subject; and

setting an end of the second-state range based on the first position.

12. The method of claim 7 , wherein the first state has an associated first-state range in the subject, the method further comprising:

determining that none of the second state's egress events are present in the subject within the second-state range, and responsively returning to the first state; and

upon returning to the first state, advancing the cursor to an end of the second-state range; and

searching the subject after the advanced cursor and within the first-state range for the presence of at least one of the first state's egress events.

13. The method of claim 1 , wherein searching the subject within the second-state range for the presence of at least one of the second state's egress events comprises:

sequentially searching the subject within the second-state range for the presence of each of the second state's egress events, and, when the presence of such an egress event is found, responsively transitioning from the second state to that egress event's next state.

14. The method of claim 13 , wherein transitioning from one state to another state comprises recursively calling a state-search function.

15. The method of claim 1 , wherein transitioning from one state to another state comprises recursively calling a state-search function.

16. An intrusion-prevention network device for examining network traffic and identifying therein the presence of signature data patterns, the network device comprising:

a network interface;

a processor; and

data storage comprising:

a state-transition table representative of a predetermined data pattern, the state-transition table comprising a plurality of states, each state having a set of egress events, each egress event defining a transition from a current state to a next state; and

instructions executable by the processor to:

receive a subject to be evaluated for the presence of the predetermined data pattern;

while using the state-transition table to evaluate the subject for the presence of the predetermined data pattern, detect in the subject the presence of a first egress event of a first state, the first egress event defining a transition from the first state to a second state, and responsively transition from the first state to the second state;

calculate a second-state range, the second-state range being a range of positions in the subject in which to search for the presence of at least one of the second state's egress events; and

search the subject within the second-state range for the presence of at least one of the second state's egress events.

17. The intrusion-prevention network device of claim 16 , wherein the first state has an associated first-state range in the subject, and wherein the data storage further comprises instructions executable by the processor to:

set a start of the second-state range equal to the cursor;

start at the cursor, and extending no further than an end of the first-state range, determining that the subject includes a number of consecutive instances of the first egress event, the consecutive instances ending at a first position in the subject; and

set an end of the second-state range based on the first position to calculate the second-state range.

18. A non-transitory computer readable storage medium on which is embedded a computer program, said computer program implementing a method examining network traffic and identifying therein the presence of signature data patterns, said computer program comprising a set of instructions to:

provide a state-transition table representative of a predetermined data pattern, the state-transition table comprising a plurality of states, each state having a set of egress events, each egress event defining a transition from a current state to a next state;

receive a subject to be evaluated for the presence of the predetermined data pattern;

while using the state-transition table to evaluate the subject for the presence of the predetermined data pattern, detect in the subject the presence of a first egress event of a first state, the first egress event defining a transition from the first state to a second state, and responsively transition from the first state to the second state;

calculate a second-state range, the second-state range being a range of positions in the subject in which to search for the presence of at least one of the second state's egress events; and

search the subject within the second-state range for the presence of at least one of the second state's egress events.

19. The non-transitory computer readable storage medium of claim 18 , wherein the first state has an associated first-state range in the subject, said computer program comprises a further set of instructions to:

set a start of the second-state range equal to the cursor;

start at the cursor, and extending no further than an end of the first-state range, determining that the subject includes a number of consecutive instances of the first egress event, the consecutive instances ending at a first position in the subject; and

set an end of the second-state range based on the first position to calculate the second-state range.

20. The non-transitory computer readable storage medium of claim 18 , said computer program comprises a further set of instructions to:

determine that the second state has a character-class loop transition;

set a start of the second-state range equal to the cursor;

start at the cursor, determining that the subject includes a number of consecutive characters that satisfy the character-class loop transition, the consecutive instances ending at a first position in the subject; and

set an end of the second-state range based on the first position to calculate the second-state range.