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

1. A method for adaptive packet filtering, the method comprising:

identifying, from rules in an ordered set of firewall packet filtering rules that defines a firewall policy, disjoint rule groups containing disjoint rules, where disjoint rules are defined as rules whose order can be changed without changing the integrity of the firewall policy, wherein each rule includes n tuples, the n tuples for each rule including at least a first tuple comprising an entire source address, a second tuple comprising an entire destination address, and a third tuple comprising an action, wherein each disjoint rule group contains rules that are disjoint from all other rules in the disjoint rule group wherein each of the rules in the ordered set is classified into a disjoint rule group;

sorting the rules within the disjoint rule groups using a comparison function that considers, for each sort of each rule, the aggregate of the n tuples and the entirety of each of the n tuples in each rule being sorted so that the rules can be searched using a sub-linear search algorithm;

filtering packets at the firewall using the sorted rules in the disjoint rule groups by searching the sorted rules in the disjoint rule groups using the sub-linear search algorithm that uses the comparison function until the packet is allowed or denied and ceasing the searching in response to the packet being allowed or denied; and

consolidating disjoint rule groups having less than a threshold number of rules to form dependent rule groups and refraining from sorting the rules in the dependent rule groups and wherein filtering the packets includes filtering the packets using the disjoint rule groups and the dependent rule groups, thereby achieving sub-linear searching for the disjoint rule groups and achieving linear searching for the dependent rule groups.

2. A system for adaptive packet filtering, the system comprising:

a firewall rule subset identifier/rule sorter for identifying, from rules in an ordered set of firewall packet filtering rules that defines a firewall policy, disjoint rule groups containing disjoint rules, where disjoint rules are defined as rules whose order can be changed without changing integrity of the firewall policy, wherein each rule includes n tuples, the n tuples for each rule including at least a first tuple comprising an entire source address, a second tuple comprising an entire destination address, and a third tuple comprising an action, wherein each disjoint rule group contains rules that are disjoint from all other rules in the disjoint rule group and wherein each of the rules in the ordered set of packet filtering rules is classified into a disjoint rule group and for sorting the rules in the disjoint rule groups using a comparison function that considers, for each sort of each rule, the aggregate of the n tuples and the entirety of each of the n tuples in each rule being sorted so that the rules can be searched using a sub-linear search algorithm;

a packet filter for filtering packets at the firewall using the sorted rules in the disjoint rule groups by searching the sorted rules in the disjoint rule groups using the sub-linear search algorithm that uses the comparison function until the packet is allowed or denied and ceasing the searching in response to the packet being allowed or denied; and

wherein the firewall rule subset identifier/rule sorter merges disjoint rule groups having less than a threshold number of rules to form dependent rule groups and refrains from sorting the rules in the dependent rule groups and wherein the firewall packet filter filters the packets using the disjoint rule groups and the dependent rule groups, thereby achieving sub-linear searching for the disjoint rule groups and achieving linear searching for the dependent rule groups.

3. A method for adaptive packet filtering, the method comprising:

identifying, from rules in an ordered set of firewall packet filtering rules that defines a firewall policy, disjoint rule groups containing disjoint rules, where disjoint rules are defined as rules whose order can be changed without changing the integrity of the firewall policy, wherein each rule includes n tuples, the n tuples for each rule including at least a first tuple comprising an entire source address, a second tuple comprising an entire destination address, and a third tuple comprising an action, wherein each disjoint rule group contains rules that are disjoint from all other rules in the disjoint rule group wherein each of the rules in the ordered set is classified into a disjoint rule group;

sorting the rules within the disjoint rule groups using a comparison function that considers, for each sort of each rule, the aggregate of the n tuples and the entirety of each of the n tuples in each rule being sorted so that the rules can be searched using a sub-linear search algorithm;

filtering packets at the firewall using the sorted rules in the disjoint rule groups by searching the sorted rules in the disjoint rule groups using the sub-linear search algorithm that uses the comparison function until the packet is allowed or denied and ceasing the searching in response to the packet being allowed or denied; and

wherein identifying the disjoint rule groups comprises:

(a) creating a new empty disjoint rule group and placing a first ungrouped rule in the ordered set into the empty disjoint rule group; and

(b) for each ungrouped rule in the ordered set:

(i) placing the rule in the disjoint rule group if the rule is disjoint from all rules in the disjoint rule group; and

(ii) leaving the rule ungrouped if the rule is not disjoint from all of the rules in the disjoint rule group and repeating steps (a) and (b) until all rules in the ordered set of packet filtering rules are grouped into disjoint rule groups.

4. A system for adaptive packet filtering, the system comprising:

a firewall rule subset identifier/rule sorter for identifying, from rules in an ordered set of firewall packet filtering rules that defines a firewall policy, disjoint rule groups containing disjoint rules, where disjoint rules are defined as rules whose order can be changed without changing integrity of the firewall policy, wherein each rule includes n tuples, the n tuples for each rule including at least a first tuple comprising an entire source address, a second tuple comprising an entire destination address, and a third tuple comprising an action, wherein each disjoint rule group contains rules that are disjoint from all other rules in the disjoint rule group and wherein each of the rules in the ordered set of packet filtering rules is classified into a disjoint rule group and for sorting the rules in the disjoint rule groups using a comparison function that considers, for each sort of each rule, the aggregate of the n tuples and the entirety of each of the n tuples in each rule being sorted so that the rules can be searched using a sub-linear search algorithm;

a packet filter for filtering packets at the firewall using the sorted rules in the disjoint rule groups by searching the sorted rules in the disjoint rule groups using the sub-linear search algorithm that uses the comparison function until the packet is allowed or denied and ceasing the searching in response to the packet being allowed or denied; and

wherein identifying the disjoint rule groups comprises:

(a) creating a new empty disjoint rule group and placing a first ungrouped rule in the ordered set into the empty disjoint rule group; and

(b) for each ungrouped rule in the ordered set:

placing the rule in the disjoint rule group if the rule is disjoint from all rules in the disjoint rule group; and

(ii) leaving the rule ungrouped if the rule is not disjoint from all of the rules in the disjoint rule group and repeating steps (a) and (b) until all rules in the ordered set of packet filtering rules are grouped into disjoint rule groups.

5. A non-transitory computer readable medium having stored thereon on executable instructions that when implemented by a processor of a computer controls the computer to perform steps comprising:

identifying, from rules in an ordered set of firewall packet filtering rules that defines a firewall policy, disjoint rule groups containing disjoint rules, where disjoint rules are defined as rules whose order can be changed without changing integrity of the firewall policy wherein each rule includes n tuples, the n tuples including at least a first tuple comprising an entire source address, a second tuple comprising an entire destination address, and a third tuple comprising an action, wherein each disjoint rule group contains rules that are disjoint from all other rules in the disjoint rule group and wherein each of the rules in the ordered set is classified into a disjoint rule group;

sorting the rules within the disjoint rule groups using a comparison function that considers, for each sort of each rule, the aggregate of the n tuples and the entirety of each of the n tuples in each rule being sorted so that the rules can be searched using a sub-linear search algorithm;

filtering packets at the firewall using the sorted rules in the disjoint rule groups by searching the sorted rules in the disjoint rule groups using the sub-linear search algorithm that uses the comparison function until the packet is allowed or denied and ceasing the searching in response to the packet being allowed or denied and thereby achieving sub-linear searching for the packets filtered using the sorted rules in at least one subset; and

wherein identifying the disjoint rule groups comprises:

(a) creating a new empty disjoint rule group and placing a first ungrouped rule in the ordered set into the empty disjoint rule group; and

(b) for each ungrouped rule in the ordered set:

(i) placing the rule in the disjoint rule group if the rule is disjoint from all rules in the disjoint rule group; and

(ii) leaving the rule ungrouped if the rule is not disjoint from all of the rules in the disjoint rule group and repeating steps (a) and (b) until all rules in the ordered set of packet filtering rules are grouped into disjoint rule groups.