Towards Robust Firewalls Using Approximate Packet Classification

Abstract

During the past decade or two, the Internet has witnessed an ever escalating demand for protection against unwanted traffic, including those carrying out malicious attacks. Packet filtering has been universally deployed in firewalls to serve as the first defense frontier against such unwanted traffic. Thus far in practice, packet filtering in firewalls has followed the conventional paradigm of exact packet classification, in which every packet has to be classified exactly conforming to the complete set of defined rules. However, under heavy traffic load due to unusually large traffic bursts or malicious attacks, performing exact packet classification sometimes incurs load that far exceeds the firewall?s capacity. It is not rare for firewalls to crash under such circumstances, causing considerable loss of important data and extended periods of service disruption. In this paper, we propose the first robust scheme for approximate packet classification, which dynamically adjusts the rules to be evaluated at runtime as a function of system load, so as to reduce the drop rate and delay of legitimate packets at the firewall while still being conservative enough in filtering all unwanted packets. Through extensive simulations based on firewall rule sets and traffic logs managed by a large tier-1 ISP, we demonstrate that our proposed solution can reduce legitimate packet drop rate by as much as an order of magnitude and hence significantly improve the robustness of the firewall, especially under high traffic loads.