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.

1 . A method comprising:
 determining, by a firewall system, a plurality of rules of a firewall policy;   partitioning the plurality of rules into a plurality of subsets of the plurality of rules comprising at least a first subset of the plurality of rules and a second subset of the plurality of rules, wherein partitioning a given subset of the plurality of rules comprises:
 placing a first ungrouped rule of the plurality of rules into the given subset; 
 determining whether a second ungrouped rule of the plurality of rules is disjoint from other rules in the given subset and whether inclusion of the second ungrouped rule in the given subset will modify the firewall policy; and 
 adding the second ungrouped rule to the given subset of the plurality of rules based on determining that the second ungrouped rule is disjoint from the other rules in the given subset and that inclusion of the second ungrouped rule in the given subset will not modify the firewall policy; 
   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 a first comparison function defined for the first subset of the plurality of rules, 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 a second comparison function defined for the second subset of the plurality of rules, each rule of the second subset of the plurality of rules, wherein the second comparison function is different from the first comparison function; and 
   configuring, by the firewall system, a first firewall processor of a plurality of firewall processors of the firewall system to filter packets in accordance with the sorted first subset of the plurality of rules and a second firewall processor of the plurality of firewall processors to filter packets in accordance with the sorted second subset of the plurality of rules.   
     
     
         2 . The method of  claim 1 , wherein the plurality of subsets of the plurality of rules further comprises a third subset of the plurality of rules, the method further comprising:
 merging, based on determining that a quantity of rules in the third subset of the plurality of rules satisfies a threshold, 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, based on determining that a quantity of rules in the first subset of the plurality of rules satisfies a threshold, 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 firewall 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 firewall processor is configured to use a second 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 firewall 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 firewall processor is configured differently than the second firewall processor.   
     
     
         7 . The method of  claim 1 , wherein partitioning 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 . The method of  claim 1 , wherein the first comparison function is one or more of:
 an integer comparison function; or   a multi-dimensional comparison function.   
     
     
         9 . A 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;   partition the plurality of rules into a plurality of subsets of the plurality of rules comprising at least a first subset of the plurality of rules and a second subset of the plurality of rules, wherein partitioning a given subset of the plurality of rules comprises:
 placing a first ungrouped rule of the plurality of rules into the given subset; 
 determining whether a second ungrouped rule of the plurality of rules is disjoint from other rules in the given subset and whether inclusion of the second ungrouped rule in the given subset will modify the firewall policy; and 
 adding the second ungrouped rule to the given subset of the plurality of rules based on determining that the second ungrouped rule is disjoint from the other rules in the given subset and that inclusion of the second ungrouped rule in the given subset will not modify the firewall policy; 
   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 a first comparison function defined for the first subset of the plurality of rules, 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 a second comparison function defined for the second subset of the plurality of rules, each rule of the second subset of the plurality of rules, wherein the second comparison function is different from the first comparison function; and 
   configure a first firewall processor of a plurality of firewall processors to filter packets in accordance with the sorted first subset of the plurality of rules and a second firewall processor of the plurality of firewall processors to filter packets in accordance with the sorted second subset of the plurality of rules.   
     
     
         10 . The non-transitory computer-readable storage media of  claim 9 , wherein the plurality of subsets of the plurality of rules comprises a third subset of the plurality of rules, and wherein the instructions, when executed by the firewall system, further cause the firewall system to:
 merge, based on determining that a quantity of rules in the third subset of the plurality of rules satisfies a threshold, the third subset of the plurality of rules into the second subset of the plurality of rules.   
     
     
         11 . The non-transitory computer-readable storage media of  claim 9 , wherein the instructions, when executed by the firewall system, cause the firewall system to:
 consolidate, based on determining that a quantity of rules in the first subset of the plurality of rules satisfies a threshold, the first subset of the plurality of rules with a third subset of the plurality of rules.   
     
     
         12 . The non-transitory computer-readable storage media of  claim 9 , wherein the first firewall 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 firewall processor is configured to use a second search algorithm to filter packets in accordance with the sorted second subset of the plurality of rules. 
     
     
         13 . The non-transitory computer-readable storage media of  claim 9 , 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. 
     
     
         14 . The non-transitory computer-readable storage media of  claim 9 , wherein the instructions, when executed by the firewall system, further cause the firewall system to:
 configure the first firewall 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 firewall processor is configured differently than the second firewall processor.   
     
     
         15 . The non-transitory computer-readable storage media of  claim 9 , wherein the instructions, when executed by the firewall system, cause the firewall system to partition 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.   
     
     
         16 . An apparatus comprising:
 one or more first hardware processors; and   memory storing instructions that, when executed by the one or more first hardware processors, cause the apparatus to:
 determine a plurality of rules of a firewall policy; 
 partition the plurality of rules into a plurality of subsets of the plurality of rules comprising at least a first subset of the plurality of rules and a second subset of the plurality of rules, wherein partitioning a given subset of the plurality of rules comprises:
 placing a first ungrouped rule of the plurality of rules into the given subset; 
 determining whether a second ungrouped rule of the plurality of rules is disjoint from other rules in the given subset and whether inclusion of the second ungrouped rule in the given subset will modify the firewall policy; and 
 adding the second ungrouped rule to the given subset of the plurality of rules based on determining that the second ungrouped rule is disjoint from the other rules in the given subset and that inclusion of the second ungrouped rule in the given subset will not modify the firewall policy; 
 
 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 a first comparison function defined for the first subset of the plurality of rules, 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 a second comparison function defined for the second subset of the plurality of rules, each rule of the second subset of the plurality of rules, wherein the second comparison function is different from the first comparison function; and 
 
 configure a first firewall processor of a plurality of firewall processors to filter packets in accordance with the sorted first subset of the plurality of rules and a second firewall processor of the plurality of firewall processors to filter packets in accordance with the sorted second subset of the plurality of rules. 
   
     
     
         17 . The apparatus of  claim 16 , wherein the plurality of subsets of the plurality of rules comprises a third subset of the plurality of rules, and wherein the instructions, when executed by the one or more first hardware processors, further cause the apparatus to:
 merge, based on determining that a quantity of rules in the third subset of the plurality of rules satisfies a threshold, the third subset of the plurality of rules into the second subset of the plurality of rules.   
     
     
         18 . The apparatus of  claim 16 , wherein the instructions, when executed by the one or more first hardware processors, cause the apparatus to:
 consolidate, based on determining that a quantity of rules in the first subset of the plurality of rules satisfies a threshold, the first subset of the plurality of rules with a third subset of the plurality of rules.   
     
     
         19 . The apparatus of  claim 16 , wherein the first firewall 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 firewall processor is configured to use a second search algorithm to filter packets in accordance with the sorted second subset of the plurality of rules. 
     
     
         20 . The apparatus of  claim 16 , wherein ordering each rule of the given subset of the plurality of rules is further based on a hit probability for each rule of the given subset of the plurality of rules. 
     
     
         21 . The apparatus of  claim 16 , wherein the instructions, when executed by the one or more first hardware processors, further cause the apparatus to:
 configure the first firewall 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 firewall processor is configured differently than the second firewall processor.