Methods, systems, and computer readable media for adaptive packet filtering

Abstract

Methods, systems, and computer readable media for adaptive packet filtering are disclosed. One method includes identifying at least one subset of rules and an ordered set of firewall packet filtering rules that defines a firewall policy such that the subset contains disjoint rules. Disjoint rules are defined as rules whose order can be changed without changing integrity of the firewall policy. Rules in the subset are sorted to statistically decrease the number of comparisons that will be applied to each packet that a firewall encounters. Packets are filtered at the firewall using the sorted rules in the subset by comparing each packet to each of the sorted rules in the subset until the packet is allowed or denied and ceasing the comparing for the packet in response to the packet being allowed or denied and thereby achieving sub-linear searching for packets filtered using the sorted rules in the subset.

What is claimed is: 
     
         1 . A method comprising:
 determining, by a firewall system, a plurality of rules of a firewall policy;   determining a first subset of the plurality of rules and a second subset of the plurality of rules based on:
 a hit probability of each rule of the plurality of rules; 
 a first aggregate hit probability of the first subset of the plurality of rules; 
 a second aggregate hit probability of the second subset of the plurality of rules; 
 a determination that the first subset of the plurality of rules, when applied to a packet, result in a same first action taken on the packet irrespective of an order in which the rules in the first subset of the plurality of rules are applied to the packet; and 
 a determination that the second subset of the plurality of rules, when applied to the packet, result in a same second action taken on the packet irrespective of an order in which the rules in the second subset of the plurality of rules are applied to the packet; 
   sorting, by the firewall system, the first subset of the plurality of rules by:
 determining a first plurality of keys, wherein each key of the first plurality of keys corresponds to a respective rule of the first subset of the plurality of rules and indicates one or more of: a source address that corresponds to matching criteria of the respective rule, or a destination address that corresponds to the matching criteria of the respective rule; and 
 ordering, using the first plurality of keys and in a first order, each rule of the first subset of the plurality of rules; and 
   sorting, by the firewall system, the second subset of the plurality of rules by:
 determining a second plurality of keys, wherein each key of the second plurality of keys corresponds to a second respective rule of the second subset of the plurality of rules and indicates one or more of: a source address that corresponds to second matching criteria of the second respective rule, or a destination address that corresponds to the second matching criteria of the second respective rule; and 
 ordering, using the second plurality of keys and in a second order, each rule of the second subset of the plurality of rules; and 
   configuring, by the firewall system, a first processor of a one or more processors of the firewall system to filter packets in accordance with the sorted first subset of the plurality of rules and a second processor of the one or more processors to filter packets in accordance with the sorted second subset of the plurality of rules.   
     
     
         2 . The method of  claim 1 , further comprising:
 determining, based on the plurality of rules, a third subset of the plurality of rules by determining that the third subset of the plurality of rules, when applied to the packet, result in a same third action taken on the packet irrespective of an order in which the rules in the third subset of the plurality of rules are applied to the packet; and   merging, based on determining that a quantity of rules in the third subset of the plurality of rules satisfies a threshold and based on determining that the third subset of the plurality of rules and the second subset of the plurality of rules are order-independent, the third subset of the plurality of rules into the second subset of the plurality of rules.   
     
     
         3 . The method of  claim 1 , further comprising:
 consolidating the first subset of the plurality of rules with a third subset of the plurality of rules.   
     
     
         4 . The method of  claim 1 , wherein the first processor is configured to use a first search algorithm to filter packets in accordance with the sorted first subset of the plurality of rules, and wherein the second processor is configured to use a second search algorithm, different from the first search algorithm, to filter packets in accordance with the sorted second subset of the plurality of rules. 
     
     
         5 . The method of  claim 1 , wherein ordering each rule of the first subset of the plurality of rules is further based on a hit probability for each rule of the first subset of the plurality of rules. 
     
     
         6 . The method of  claim 1 , further comprising:
 configuring the first processor based on determining that a first quantity of rules in the sorted first subset of the plurality of rules is greater than a second quantity of rules in the sorted second subset of the plurality of rules, wherein the first processor is configured differently than the second processor.   
     
     
         7 . The method of  claim 1 , wherein determining the first subset of the plurality of rules and the second subset of the plurality of rules comprises:
 determining, by the firewall system and for each rule in the first subset of the plurality of rules, a first plurality of tuples for the first subset of the plurality of rules;   determining, by the firewall system and for each rule in the second subset of the plurality of rules, a second plurality of tuples for the second subset of the plurality of rules; and   determining, by the firewall system, that each tuple of the first plurality of tuples either matches exactly or does not overlap one or more tuples in the second plurality of tuples.   
     
     
         8 . One or more non-transitory computer-readable storage media comprising instructions that, when executed by a firewall system, cause the firewall system to:
 determine a plurality of rules of a firewall policy;   determine a first subset of the plurality of rules and a second subset of the plurality of rules based on:
 a hit probability of each rule of the plurality of rules; 
 a first aggregate hit probability of the first subset of the plurality of rules; 
 a second aggregate hit probability of the second subset of the plurality of rules; 
 a determination that the first subset of the plurality of rules, when applied to a packet, result in a same first action taken on the packet irrespective of an order in which the rules in the first subset of the plurality of rules are applied to the packet; and 
 a determination that the second subset of the plurality of rules, when applied to the packet, result in a same second action taken on the packet irrespective of an order in which the rules in the second subset of the plurality of rules are applied to the packet; 
   sort the first subset of the plurality of rules by:
 determining a first plurality of keys, wherein each key of the first plurality of keys corresponds to a respective rule of the first subset of the plurality of rules and indicates one or more of: a source address that corresponds to matching criteria of the respective rule, or a destination address that corresponds to the matching criteria of the respective rule; and 
 ordering, using the first plurality of keys and in a first order, each rule of the first subset of the plurality of rules; and 
   sort the second subset of the plurality of rules by:
 determining a second plurality of keys, wherein each key of the second plurality of keys corresponds to a second respective rule of the second subset of the plurality of rules and indicates one or more of: a source address that corresponds to second matching criteria of the second respective rule, or a destination address that corresponds to the second matching criteria of the second respective rule; and 
 ordering, using the second plurality of keys and in a second order, each rule of the second subset of the plurality of rules; and 
   configure a first processor of a one or more processors of the firewall system to filter packets in accordance with the sorted first subset of the plurality of rules and a second processor of the one or more processors to filter packets in accordance with the sorted second subset of the plurality of rules.   
     
     
         9 . The non-transitory computer-readable storage media of  claim 8 , wherein the instructions, when executed by the firewall system, further cause the firewall system to:
 determining, based on the plurality of rules, a third subset of the plurality of rules by determining that the third subset of the plurality of rules, when applied to the packet, result in a same third action taken on the packet irrespective of an order in which the rules in the third subset of the plurality of rules are applied to the packet; and   merge, based on determining that a quantity of rules in the third subset of the plurality of rules satisfies a threshold and based on determining that the third subset of the plurality of rules and the second subset of the plurality of rules are order-independent, the third subset of the plurality of rules into the second subset of the plurality of rules.   
     
     
         10 . The non-transitory computer-readable storage media of  claim 8 , wherein the instructions, when executed by the firewall system, cause the firewall system to:
 consolidate the first subset of the plurality of rules with a third subset of the plurality of rules.   
     
     
         11 . The non-transitory computer-readable storage media of  claim 8 , wherein the first processor is configured to use a first search algorithm to filter packets in accordance with the sorted first subset of the plurality of rules, and wherein the second processor is configured to use a second search algorithm, different from the first search algorithm, to filter packets in accordance with the sorted second subset of the plurality of rules. 
     
     
         12 . The non-transitory computer-readable storage media of  claim 8 , wherein ordering each rule of the first subset of the plurality of rules is further based on a hit probability for each rule of the first subset of the plurality of rules. 
     
     
         13 . The non-transitory computer-readable storage media of  claim 8 , wherein the instructions, when executed by the firewall system, further cause the firewall system to:
 configure the first processor based on determining that a first quantity of rules in the sorted first subset of the plurality of rules is greater than a second quantity of rules in the sorted second subset of the plurality of rules, wherein the first processor is configured differently than the second processor.   
     
     
         14 . The non-transitory computer-readable storage media of  claim 8 , wherein the instructions, when executed by the firewall system, cause the firewall system to determine the first subset of the plurality of rules and the second subset of the plurality of rules by:
 determining, by the firewall system and for each rule in the first subset of the plurality of rules, a first plurality of tuples for the first subset of the plurality of rules;   determining, by the firewall system and for each rule in the second subset of the plurality of rules, a second plurality of tuples for the second subset of the plurality of rules; and   determining, by the firewall system, that each tuple of the first plurality of tuples either matches exactly or does not overlap one or more tuples in the second plurality of tuples.   
     
     
         15 . An apparatus comprising:
 one or more processors; and   memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
 determine a plurality of rules of a firewall policy; 
 determine a first subset of the plurality of rules and a second subset of the plurality of rules based on:
 a hit probability of each rule of the plurality of rules; 
 a first aggregate hit probability of the first subset of the plurality of rules; 
 a second aggregate hit probability of the second subset of the plurality of rules; 
 a determination that the first subset of the plurality of rules, when applied to a packet, result in a same first action taken on the packet irrespective of an order in which the rules in the first subset of the plurality of rules are applied to the packet; and 
 a determination that the second subset of the plurality of rules, when applied to the packet, result in a same second action taken on the packet irrespective of an order in which the rules in the second subset of the plurality of rules are applied to the packet; 
 
 sort the first subset of the plurality of rules by:
 determining a first plurality of keys, wherein each key of the first plurality of keys corresponds to a respective rule of the first subset of the plurality of rules and indicates one or more of: a source address that corresponds to matching criteria of the respective rule, or a destination address that corresponds to the matching criteria of the respective rule; and 
 ordering, using the first plurality of keys and in a first order, each rule of the first subset of the plurality of rules; and 
 
 sort the second subset of the plurality of rules by:
 determining a second plurality of keys, wherein each key of the second plurality of keys corresponds to a second respective rule of the second subset of the plurality of rules and indicates one or more of: a source address that corresponds to second matching criteria of the second respective rule, or a destination address that corresponds to the second matching criteria of the second respective rule; and 
 ordering, using the second plurality of keys and in a second order, each rule of the second subset of the plurality of rules; and 
 
 configure a first processor of the one or more processors of the apparatus to filter packets in accordance with the sorted first subset of the plurality of rules and a second processor of the one or more processors to filter packets in accordance with the sorted second subset of the plurality of rules. 
   
     
     
         16 . The apparatus of  claim 15 , wherein the instructions, when executed by the one or more processors, further cause the apparatus to:
 determine, based on the plurality of rules, a third subset of the plurality of rules by determining that the third subset of the plurality of rules, when applied to the packet, result in a same third action taken on the packet irrespective of an order in which the rules in the third subset of the plurality of rules are applied to the packet; and   merge, based on determining that a quantity of rules in the third subset of the plurality of rules satisfies a threshold and based on determining that the third subset of the plurality of rules and the second subset of the plurality of rules are order-independent, the third subset of the plurality of rules into the second subset of the plurality of rules.   
     
     
         17 . The apparatus of  claim 15 , wherein the instructions, when executed by the one or more processors, cause the apparatus to:
 consolidate the first subset of the plurality of rules with a third subset of the plurality of rules.   
     
     
         18 . The apparatus of  claim 15 , wherein the first processor is configured to use a first search algorithm to filter packets in accordance with the sorted first subset of the plurality of rules, and wherein the second processor is configured to use a second search algorithm, different from the first search algorithm, to filter packets in accordance with the sorted second subset of the plurality of rules. 
     
     
         19 . The apparatus of  claim 15 , wherein ordering each rule of the first subset of the plurality of rules is further based on a hit probability for each rule of the first subset of the plurality of rules. 
     
     
         20 . The apparatus of  claim 15 , wherein the instructions, when executed by the one or more processors, further cause the apparatus to:
 configure the first processor based on determining that a first quantity of rules in the sorted first subset of the plurality of rules is greater than a second quantity of rules in the sorted second subset of the plurality of rules, wherein the first processor is configured differently than the second processor.