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:
 identifying, from among a plurality of rules that define a packet filtering policy, one or more groups of disjoint rules, wherein each of the one or more groups of disjoint rules comprises at least two rules that when applied to a packet either allow the packet to continue toward its destination or prevent the packet from continuing towards its destination irrespective of an order in which the at least two rules are applied to the packet, a first of the at least two rules specifying a set of network addresses for which packets should be allowed to continue toward their respective destinations, and a second of the at least two rules specifying a set of network addresses for which packets should be prevented from continuing toward their respective destinations;   receiving a plurality of packets;   applying the first of the at least two rules to a first portion of the plurality of packets, the first portion of the plurality of packets having network addresses in the set of network addresses for which packets should be allowed to continue toward their respective destinations;   applying the second of the at least two rules to a second portion of the plurality of packets, the second portion of the plurality of packets having network addresses in the set of network addresses for which packets should be prevented from continuing toward their respective destinations;   allowing the first portion of the plurality of packets to continue toward their respective destinations; and   preventing the second portion of the plurality of packets from continuing toward their respective destinations.