Trie-based policy representations for network firewalls

Network firewalls remain the forefront defense for most computer systems. These critical devices 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 traffic delays, which is problematic for applications that require strict quality of service (QoS) guarantees. Given this demanding environment, new methods are needed to increase network firewall performance. This paper introduces a new technique for representing a security policy that maintains policy integrity and provides more efficient processing. The policy is represented as an n-ary retrieval tree, also referred to as a trie. The worst case processing requirement for the policy trie is a fraction compared a list representation, which only considers rules individually (1/5 the processing for TCP/IP networks). Furthermore unlike other representations, the n-ary trie developed in this paper can be proven to maintain policy integrity. The creation of policy trie structures is discussed in detail and their performance benefits are described theoretically and validated empirically.