摘要：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. 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.
