Network Firewall Policy Tries

Network firewalls remain the forefront defense for most computer systems. These criticaldevices filter traffic by comparing arriving packets to a list of rules, or security policy, in a sequential manner. Unfortunately packet filtering in this fashion can result in significant trafficdelays, which is problematic for applications that require strict Quality of Service (QoS) guarantees. Furthermore, as network speeds and capacities continue to increase, the processing timeassociated with filtering only compounds these delays. Given this demanding environment, new methods are needed to increase network firewall performance.This paper introduces a new technique for representing a security policy in software that maintains policy integrity and provides more efficient processing. The policy is represented asan n-ary retrieval tree, also referred to as a trie. This structure is able to quickly reach decisionsbased on the security policy by simultaneously eliminating multiple rules with few comparisons. As a result, the worst case processing requirement for the policy trie is a fraction compareda list representation, which only consider rules individually (1 /5 the processing for TCP/IPnetworks). Furthermore unlike other representations, the n-ary trie developed in this paper isproven to maintain policy integrity. The creation of policy trie structures is discussed in detail and their performance benefits are proven theoretically and validated empirically.