Methods and systems for using keywords preprocessing, Boyer-Moore analysis, and hybrids thereof, for processing regular expressions in intrusion-prevention systems

Patent metadata

Field	Value
Publication number	US-9270641-B1
Application number	US-18239108-A
Country	US
Kind code	B1
Filing date	Jul 30, 2008
Priority date	Jul 31, 2007
Publication date	Feb 23, 2016
Grant date	Feb 23, 2016

Abstract

Methods and systems are provided for using keyword preprocessing, Boyer-Moore analysis, and hybrids thereof, in intrusion-prevention systems. In one embodiment, a state-transition table representative of a data pattern is provided. The table has a plurality of states, each having egress events that define transitions to other states. The data pattern is parsed to identify character strings. A subject is received for evaluation, and preprocessed to find any instances of those character strings. A keyword table is populated with the character strings found during preprocessing. While using the table to evaluate the subject, a first state having a first one of the character strings as an egress event is transitioned into. The keyword table is checked for the first character string, and, responsive to finding the first character string in the keyword table, a transition is taken from the first state to the second state.

First claim

The invention claimed is:

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;
parsing the predetermined data pattern to identify a set of character strings therein;
receiving a subject to be evaluated for the presence of the predetermined data pattern, and preprocessing the subject to find therein any instances of the identified character strings;
populating a keyword table with a subset of the identified character strings, the subset consisting of those character strings found in the subject during preprocessing;
while using the state-transition table to evaluate the subject for a presence of the predetermined data pattern, transitioning into a first state having a first one of the identified character strings as a first egress event thereof, the first egress event defining a transition from the first state to a second state; and
responsive to transitioning into the first state, checking, by a processing unit, the keyword table for the first character string, and, responsive to finding the first character string in the keyword table, transitioning, by the processing unit, from the first state to the second state.

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 identified set of character strings in the predetermined data pattern consists of those character strings in the predetermined data pattern that (a) include at least two distinct characters and (b) have a string length that is greater than a threshold number.

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

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

8. The method of claim 1 , wherein preprocessing the subject comprises using a keyword-tree search.

9. The method of claim 1 , wherein preprocessing the subject comprises identifying positions in the subject where the instances of the identified character strings are located, the method further comprising populating the keyword table with the identified positions.

10. The method of claim 9 , further comprising calculating a first-state range, the first-state range being a range of positions in the subject in which to search for the presence of at least one of the first state's egress events, wherein:
checking the keyword table for the first character string comprises checking the keyword table for an instance of the first character string at a position within the first-state range; and
finding the first character string in the keyword table comprises finding in the keyword table an instance of the first character string at a position within the first-state range.

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

12. The method of claim 11 , wherein transitioning into the first state comprises transitioning from a previous state into the first state according to a previous-state egress event, wherein the previous state has an associated previous-state range in the subject, and wherein calculating the first-state range comprises:
setting a start of the first-state range equal to the cursor;
starting at the cursor, and extending no further than an end of the previous-state range, determining that the subject includes a number of consecutive instances of the previous-state egress event, the consecutive instances ending at a first position in the subject; and
setting an end of the first-state range based on the first position.

13. The method of claim 12 , further comprising determining that the first state does not have a character-class loop transition.

14. The method of claim 12 , further comprising calculating the previous-state range.

15. The method of claim 11 , wherein calculating the first-state range comprises:
determining that the first state has a character-class loop transition;
setting a start of the first-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 first-state range based on the first position.

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

17. 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 processing unit; 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 processing unit to:
parse the predetermined data pattern to identify a set of character strings therein;
receive a subject to be evaluated for a presence of the predetermined data pattern, and preprocess the subject to find therein any instances of the identified character strings;
populate a keyword table with a subset of the identified character strings, the subset consisting of those character strings found in the subject during preprocessing;
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 first one of the identified character strings as a first egress event thereof, the first egress event defining a transition from the first state to a second state; and
responsive to transitioning into the first state, check the keyword table for the first character string, and, responsive to finding the first character string in the keyword table, transition from the first state to the second state.

18. 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 a presence of the predetermined data pattern;
while using the state-transition table to evaluate the subject for the presence of the predetermined data pattern, transitioning into a first state having a first character string as a first egress event thereof, the first egress event defining a transition from the first state to a second state; and
responsive to transitioning into the first state, performing, by a processing unit, a Boyer-Moore search for the first character string in the subje

Assignees

• Preston Jason D
• Tomlinson Alexander I
• Hewlett Packard Entpr Dev Lp

Inventors

• Preston Jason D
• Tomlinson Alexander I

Classifications

• H04L63/1416

  Event detection, e.g. attack signature detection · CPC title

• G06F21/55

  Detecting local intrusion or implementing counter-measures · CPC title

• H04L63/145

  the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms · CPC title

• H04L63/0245 Primary

  Filtering by information in the payload · CPC title