Patent ID: 8495725

Claim:
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.