Using IDDs for Packet Filtering

Mikkel Christiansen
Emmanuel Fleury

October 2002

Abstract:

Firewalls are one of the key technologies used to control the traffic going in and out of a network. A central feature of the firewall is the packet filter. In this paper, we propose a complete framework for packet classification. Through two applications we demonstrate that both performance and security can be improved.

We show that a traditional ordered rule set can always be expressed as a first-order logic formula on integer variables. Moreover, we emphasize that, with such specification, the packet filtering problem is known to be constant time ($O(1)$). We propose to represent the first-order logic formula as Interval Decision Diagrams. This structure has several advantages. First, the algorithm for removing redundancy and unnecessary tests is very simple. Secondly, it allows us to handle integer variables which makes it efficient on a generic CPUs. And, finally, we introduce an extension of IDDs called Multi-Terminal Interval Decision Diagrams in order to deal with any number of policies.

In matter of efficiency, we evaluate the performance our framework through a prototype toolkit composed by a compiler and a packet filter. The results of the experiments shows that this method is efficient in terms of CPU usage and has a low storage requirements.

Finally, we outline a tool, called Network Access Verifier. This tool demonstrates how the IDD representation can be used for verifying access properties of a network. In total, potentially improving the security of a network

Available as PostScript, PDF.

Last modified: 2003-06-08 by webmaster.