Speed and memory optimization of intrusion detection system (IDS) and intrusion prevention system (IPS) rule processing

• US 20090262659A1
• Filed: 08/28/2008
• Published: 10/22/2009
• Est. Priority Date: 04/17/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Sourcefire Incorporated (Cisco Systems, Inc.)
• Inventors: Sturges, Steven, Norton, Marc
• Granted Patent: US 8,474,043 B2
• Time in Patent Office: Days
• US Class Current: 370/253
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

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.

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 the network traffic;

upon identifying the matching pattern in the network traffic, evaluating the network traffic with the matching pattern against rules specific to the matching pattern, wherein the rules specific to the matching pattern are represented by a rule tree, wherein references to rule options are represented in the rule tree and the rule options are stored separately from the rule tree, 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.

2. The method according to claim 1, wherein

if a rule option in a node of the rule tree does not match the network traffic, then not evaluating the options in the subtree of the node with the rule option that does not match;

for the rule options which match the network traffic, then continuing to process rule options in the subtree of the nodes with the rule options that match the network traffic, and adding an event for the rule if the rule represented by one of the leaf nodes matches the traffic.

3. The method according to claim 1, wherein the root of the tree begins all rules that include the same rule option of the root, a branch in the tree is where a rule option of the rules diverges, and the rule options beyond the divergence are stored as a linear subtree after the point of divergence.

4. The method according to claim 1, further comprising receiving a rule, checking whether the rule options in the rule are new and unique, and if new and unique, then inserting the rule option into the tree where the path of the rule diverges from existing rules in the rule tree.

5. The method according to claim 4, wherein the inserting of the rule option into the tree includes creating a rule option reference to the rule option, storing the rule option reference in a hash table, and inserting the rule option reference into the tree at a branch point where the rule options in the rule diverge from previous rule options in the rule tree.

6. The method according to claim 1, wherein the rule options are stored separately in a rule option storage, wherein the references to the rule options in the nodes of the rule tree are references into a hash table of the rule option storage.

7. The method according to claim 1, wherein the rules and the rule options are prepared in accordance with SNORT™

rule structure.

8. A 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 the network traffic;

upon identifying the matching pattern in the network traffic, evaluating the network traffic with the matching pattern against rules specific to the matching pattern, wherein the rules specific to the matching pattern are represented by a rule tree, wherein references to rule options are represented in the rule tree and the rule options are stored separately from the rule tree, 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.

9. The computer-readable storage medium according to claim 8, wherein

if a rule option in a node of the rule tree does not match the network traffic, then not evaluating the options in the subtree of the node with the rule option that does not match;

for the rule options which match the network traffic, then continuing to process rule options in the subtree of the nodes with the rule options that match the network traffic, and adding an event for the rule if the rule represented by one of the leaf nodes matches the traffic.

10. The computer-readable storage medium according to claim 8, the root of the tree begins all rules that include the same rule option of the root, a branch in the tree is where a rule option of the rules diverges, and the rule options beyond the divergence are stored as a linear subtree after the point of divergence.

11. The computer-readable storage medium according to claim 8, further comprising instructions for receiving a rule, checking whether the rule options in the rule are new and unique, and if new and unique, then inserting the rule option into the tree where the path of the rule diverges from existing rules in the rule tree.

12. The computer-readable storage medium according to claim 11, wherein the inserting of the rule option into the tree includes creating a rule option reference to the rule option, storing the rule option reference in a hash table, and inserting the rule option reference into the tree at a branch point where the rule options in the rule diverge from previous rule options in the rule tree.

13. The computer-readable storage medium according to claim 8, wherein the rule options are stored separately in a rule option storage, wherein the references to the rule options in the nodes of the rule tree are references into a hash table of the rule option storage.

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 the network traffic;

upon identifying the matching pattern in the network traffic, evaluating the network traffic with the matching pattern against rules specific to the matching pattern, wherein the rules specific to the matching pattern are represented by a rule tree, wherein references to rule options are represented in the rule tree and the rule options are stored separately from the rule tree, 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.

15. The computer system according to claim 14, wherein

if a rule option in a node of the rule tree does not match the network traffic, then not evaluating the options in the subtree of the node with the rule option that does not match;

for the rule options which match the network traffic, then continuing to process rule options in the subtree of the nodes with the rule options that match the network traffic, and adding an event for the rule if the rule represented by one of the leaf nodes matches the traffic.

16. The computer system according to claim 14, wherein the root of the tree begins all rules that include the same rule option of the root, a branch in the tree is where a rule option of the rules diverges, and the rule options beyond the divergence are stored as a linear subtree after the point of divergence.

17. The computer system according to claim 14, further comprising receiving a rule, checking whether the rule options in the rule are new and unique, and if new and unique, then inserting the rule option into the tree where the path of the rule diverges from existing rules in the rule tree.

18. The computer system according to claim 17, wherein the inserting of the rule option into the tree includes creating a rule option reference to the rule option, storing the rule option reference in a hash table, and inserting the rule option reference into the tree at a branch point where the rule options in the rule diverge from previous rule options in the rule tree.

19. The computer system according to claim 17, wherein the rule options are stored separately in a rule option storage, wherein the references to the rule options in the nodes of the rule tree are references into a hash table of the rule option storage.

20. The computer system according to claim 17, wherein the rules and the rule options are prepared in accordance with SNORT™

rule structure.