Packet filters are security devices that connect multiple packet-based
networks and provide access control between them. The security policy
enforced by a packet filter is specified as a set of rules, called an
access list, that describes what types of network packets should be
allowed to pass from one network to another, and what types should be
discarded. These rules are expressed in terms of the values of the
fields of the packet headers. The semantics of an access list dictate
that the first rule that matches a packet determines the action taken
by the packet filter.

Traditional packet filters evaluate the rules in an access list
sequentially until a matching rule is found and this process is
repeated for every packet passing through the filter. The latency
incurred by this sequential lookup is proportional to the number of
rules in the list. While this is not a problem for short access lists,
long access lists can cause significant system degradation. Also long
access lists typically occur at high-bandwidth network interfaces such
as on border routers, where fast packet processing is essential.

This research is based on the observation that an alternative internal
representation of an access list can eliminate the need for sequential
lookup and hence provide better filtering performance. The
representation proposed in this research follows from the fact that
the policy of an access list can be expressed as a single Boolean
expression relating the values of bits in the packet headers. Thus
binary decision diagrams (BDDs), capable of providing compact
representations for many Boolean expressions, are used as a basis for
the representation of access lists in this study.

The contribution of this research is an evaluation of the
effectiveness of representing access lists using BDDs for the purposes
of packet filtering performance. Both time and memory issues are
considered. This evaluation contains both analytical and empirical
aspects and shows that the proposed approach provides good time and
space performance for packet filtering on medium to long access
lists. Furthermore, using BDDs for the representation of access lists
provides packet filters with other useful characteristics that makes
this a beneficial approach to filtering in many real and important
situations.