Towards Optimal Firewall Rule Ordering Utilizing Directed Acyclical Graphs

Firewalls enforce a security policy by inspecting packets arriving or departing a network. This is often 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. 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. Utilizing directed acyclical graphs (DAGs) to represent firewall policy, this paper will introduce a novel rule sorting technique. The technique is capable of considering sub-graphs of rules (inter-related by precedence constraints) and compare the advantage of placing and merging the rules that comprise them. Experimental results using a variety of policies will show that the proposed algorithm is able to find the optimal order in 98% of the example policies, which is substantially higher than other methods.