Speed and memory optimization of intrusion detection system (IDS) and intrusion prevention system (IPS) rule processing
First Claim
1. A method, performed in an intrusion detection/prevention system in a computer system, for evaluating network traffic against rules, comprising:
- receiving network traffic;
checking for a matching pattern in a packet in the network traffic using a state machine and a fast pattern matcher based on attack signatures, in which matching patterns being searched each corresponds to one or more attacks;
adding, to an array of matching end states, a matching end state corresponding to the matching pattern found in the packet, when the matching pattern is found in the network traffic by the fast pattern matcher;
the checking and adding being performed until the fast pattern matcher has completed a full pass over data in the packet or the array is full of matching end states;
creating a list of rule trees that correspond to the matching end states in the array of matching end states, when the fast pattern matcher has completed the full pass over data in the packet or when the array is full;
evaluating the packet in the network traffic with the matching pattern against each rule tree in the list of rule trees that correspond to the matching end states, wherein each of the rule trees corresponds to a different one of the matching patterns, wherein one of the matching patterns in the network traffic corresponds to plural rules, wherein references to rule options are represented in the rule trees and the rule options are stored separately from the rule trees, the rule tree representing each unique rule by each unique path from a root of the tree to each of the leaf nodes, and the rule tree representing a rule option as a non-leaf node of the rule tree, the evaluating of the network traffic including;
processing, against the network traffic, the rule options in the rule tree beginning at the root of the rule tree;
wherein processing of all of the rules represented by the subtrees of nodes with rule options that do not match are eliminated,wherein the network traffic is evaluated against rules terminating in leaf nodes only for combinations of rule options which match the network traffic.
3 Assignments
0 Petitions
Accused Products
Abstract
In an intrusion detection/prevention system, network traffic is received and checked for a matching pattern. Upon identifying the matching pattern, the network traffic with the matching pattern is evaluated against rules that are represented by a rule tree. References to rule options are represented in the rule tree and are stored separately from the rule tree. The rule tree represents unique rules by unique paths from a root of the tree to the leaf nodes, and represents rule options as non-leaf nodes of the rule tree. Evaluating the network traffic includes processing, against the network traffic, the rule options in the rule tree beginning at the root. Processing of the rules represented by subtrees of nodes with rule options that do not match is eliminated. The network traffic is evaluated against rules terminating in leaf nodes only for combinations of rule options that match the network traffic.
226 Citations
23 Claims
-
1. A method, performed in an intrusion detection/prevention system in a computer system, for evaluating network traffic against rules, comprising:
-
receiving network traffic; checking for a matching pattern in a packet in the network traffic using a state machine and a fast pattern matcher based on attack signatures, in which matching patterns being searched each corresponds to one or more attacks; adding, to an array of matching end states, a matching end state corresponding to the matching pattern found in the packet, when the matching pattern is found in the network traffic by the fast pattern matcher; the checking and adding being performed until the fast pattern matcher has completed a full pass over data in the packet or the array is full of matching end states; creating a list of rule trees that correspond to the matching end states in the array of matching end states, when the fast pattern matcher has completed the full pass over data in the packet or when the array is full; evaluating the packet in the network traffic with the matching pattern against each rule tree in the list of rule trees that correspond to the matching end states, wherein each of the rule trees corresponds to a different one of the matching patterns, wherein one of the matching patterns in the network traffic corresponds to plural rules, wherein references to rule options are represented in the rule trees and the rule options are stored separately from the rule trees, the rule tree representing each unique rule by each unique path from a root of the tree to each of the leaf nodes, and the rule tree representing a rule option as a non-leaf node of the rule tree, the evaluating of the network traffic including; processing, against the network traffic, the rule options in the rule tree beginning at the root of the rule tree; wherein processing of all of the rules represented by the subtrees of nodes with rule options that do not match are eliminated, wherein the network traffic is evaluated against rules terminating in leaf nodes only for combinations of rule options which match the network traffic. - View Dependent Claims (2, 3, 4, 5, 6, 7, 21)
-
-
8. A non-transitory computer-readable storage medium comprising instructions being executed by a computer in connection with an intrusion detection/prevention system, the instructions including a computer-implemented method for evaluating network traffic against rules, the instructions for implementing:
-
receiving network traffic; checking for a matching pattern in a packet in the network traffic using a state machine and a fast pattern matcher based on attack signatures, in which matching patterns being searched each corresponds to one or more attacks; adding, to an array of matching end states, a matching end state corresponding to the matching pattern found in the packet, when the matching pattern is found in the network traffic by the fast pattern matcher; the checking and adding being performed until the fast pattern matcher has completed a full pass over data in the packet or the array is full of matching end states; creating a list of rule trees that correspond to the matching end states in the array of matching end states, when the fast pattern matcher has completed the full pass over data in the packet or when the array is full; evaluating the packet in the network traffic with the matching pattern against each rule tree in the list of rule trees that correspond to the matching end states, wherein each of the rule trees corresponds to a different one of the matching patterns, wherein one of the matching patterns in the network traffic corresponds to plural rules, wherein references to rule options are represented in the rule trees and the rule options are stored separately from the rule trees, the rule tree representing each unique rule by each unique path from a root of the tree to each of the leaf nodes, and the rule tree representing a rule option as a non-leaf node of the rule tree, the evaluating of the network traffic including; processing, against the network traffic, the rule options in the rule tree beginning at the root of the rule tree; wherein processing of all of the rules represented by the subtrees of nodes with rule options that do not match are eliminated, wherein network traffic is evaluated against rules terminating in leaf nodes only for combinations of rule options which match the network traffic. - View Dependent Claims (9, 10, 11, 12, 13, 22)
-
-
14. A computer system for evaluating network traffic against rules in connection with an intrusion detection/prevention system, comprising:
-
(A) a transceiver operable to receive or transmit network traffic; and (B) a processor cooperatively operable with the memory and the transceiver, and configured to facilitate; obtaining network traffic to be transmitted on the transceiver or which was received by the transceiver; checking for a matching pattern in a packet in the network traffic using a state machine and a fast pattern matcher based on attack signatures, in which matching patterns being searched each corresponds to one or more attacks; adding, to an array of matching end states, a matching end state corresponding to the matching pattern found in the packet, when the matching pattern is found in the network traffic by the fast pattern matcher; the checking and adding being performed until the fast pattern matcher has completed full pass over data in the packet or the array is full of matching end states; creating a list of rule trees that correspond to the matching end states in the array of matching end states, when the fast pattern matcher has completed the full pass over data in the packet or when the array is full; evaluating the packet in the network traffic with the matching pattern against each rule tree in the list of rule trees that correspond to the matching end states, wherein each of the rule trees corresponds to a different one of the matching patterns, wherein one of the matching patterns in the network traffic corresponds to plural rules, wherein references to rule options are represented in the rule trees and the rule options are stored separately from the rule trees, the rule tree representing each unique rule by each unique path from a root of the tree to each of the leaf nodes, and the rule tree representing a rule option as a non-leaf node of the rule tree, the evaluating of the network traffic including; processing, against the network traffic, the rule options in the rule tree beginning at the root of the rule tree; wherein processing of all of the rules represented by the subtrees of nodes with rule options that do not match are eliminated, wherein network traffic is evaluated against rules terminating in leaf nodes only for combinations of rule options which match the network traffic. - View Dependent Claims (15, 16, 17, 18, 19, 20, 23)
-
Specification