Firewall Policy Optimization and Management

Abstract

Firewalls enforce a security policy by inspecting packets arriving or departing a network. This is accomplished by sequentially comparing the policy rules with the header of an arriving packet until the first match is found. This process becomes time consuming as policies become larger and more complex. For example, a firewall connecting two high speed networks is responsible for processing heavy network load and can easily become a bottleneck. Therefore determining the appropriate action for arriving packets must be done as quickly as possible.

The process of packet header matching can be improved if more popular rules appear earlier in the policy. Unfortunately, a simple sorting algorithm is not possible, since the relative order of certain rules must be maintained in order to preserve the original policy intent. Using directed acyclical graphs to represent the firewall policy, this thesis shows that determining the best order of firewall rules is equivalent to job-shop scheduling, a known NP-Hard problem. The sorting techniques are novel in that they consider sub-graphs of rules (inter-related by precedence constraints) and compare the advantage of placing and merging the nodes that comprise them. For policy management, a shadow detection algorithm is presented to detect anomalies.