Methods and systems for using lambda transitions for processing regular expressions in intrusion-prevention systems

1. A method for examining network traffic in an intrusion prevention system and identifying therein the presence of signature data patterns, the 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;

evaluating, by a processor, the subject using the state-transition table for the presence of the predetermined data pattern, wherein the evaluating further includes transitioning into a first state having (a) a first egress event defining a transition to a second state, (b) a state count corresponding to a number of times the first state has been transitioned into, (c) a state-count threshold, and (d) a state-count condition; and

after transitioning into the first state, incrementing the state count, and determining whether the state-count condition is satisfied by comparing the incremented state count with the state-count threshold;

upon determining that the state-count condition is satisfied, transitioning to the second state; and

upon determining that the state-count condition is not satisfied, returning a no-match result from the first state and decrementing the state count.

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, the cursor having a first value upon transitioning into the first state, and wherein the first state has an associated first-state range in the subject, the first-state range having a first-state-range start and a first-state range end.

8. The method of claim 7 , wherein the state-count condition is whether the incremented state count is equal to the state-count threshold.

9. The method of claim 8 , wherein transitioning to the second state comprises setting the cursor equal to the first value plus the state-count threshold.

10. The method of claim 8 , wherein the second state has an associated second-state range in the subject, the second-state range having a second-state-range start and a second-state-range end, the method further comprising (a) setting the second-state-range start equal to the first-state-range start plus the state-count threshold minus one and (b) setting the second-state-range end equal to the lesser of (i) the first-state-range end plus the state-count threshold minus one and (ii) an end position of the subject.

11. The method of claim 7 , wherein transitioning to the second state comprises leaving the cursor equal to the first value.

12. The method of claim 7 , wherein the second state has an associated second-state range in the subject, the second-state range having a second-state-range start and a second-state-range end, the method further comprising (a) setting the second-state-range start equal to the cursor and (b) setting the second-state-range end equal to the lesser of (i) the cursor plus the state-count threshold minus one and (ii) the first-state-range end.

13. The method of claim 1 , wherein the state-count condition is whether the incremented state count is less than or equal to the state-count threshold.

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

15. 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, transition into a first state having (a) a first egress event defining a transition to a second state, (b) a state count corresponding to a number of times the first state has been transitioned into, (c) a state-count threshold, and (d) a state-count condition;

after transitioning into the first state, increment the state count, and determine whether the state-count condition is satisfied by comparing the incremented state count with the state-count threshold,

upon a determination that the state-count condition is satisfied, transition to the second state; and

upon a determination that the state-count condition is not satisfied, return a no-match result from the first state and decrement the state count.

16. A method for examining network traffic in an intrusion prevention system and identifying therein the presence of signature data patterns, the 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;

evaluating, by a processor, the subject using the state-transition table for the presence of the predetermined data pattern, wherein the evaluating further includes transitioning into a first state having (a) a first egress event defining a transition to a second state, (b) a state count corresponding to a number of times the first state has been transitioned into, (c) a state-count threshold, and (d) a state-count condition; and

after transitioning into the first state, incrementing the state count, and determining whether the state-count condition is satisfied by comparing the incremented state count with the state-count threshold and transitioning to the second state in response to the state-count threshold being reached;

wherein a cursor corresponds to a location in the subject that is currently being evaluated, the cursor having a first value upon transitioning into the first state, and wherein the first state has an associated first-state range in the subject, the first-state range having a first-state-range start and a first-state range end; and

wherein the second state has an associated second-state range in the subject, the second-state range having a second-state-range start and a second-state-range end, the method further comprising (a) setting the second-state-range start equal to the cursor and (b) setting the second-state-range end equal to the lesser of (i) the cursor plus the state-count threshold minus one and (ii) the first-state-range end.