Binary Decision Diagrams Representations of Firewall and Router
			     Access Lists


	   Scott Hazelhurst, Anton Fatti and Andrew Henwood
		    Department of Computer Science
	    University of the Witwatersrand, Johannesburg
		Private Bag 3, 2050 Wits, South Africa



			       Abstract


Network firewalls and routers can use a rule database to decide which
packets will be allowed from one network onto another. By filtering
packets the firewalls and routers (called collectively here filters)
can improve security and performance -- network packets which may pose
a security risk to a network can be filtered out, and by excluding
packets that are not relevant to a subnet, congestion can be reduced.

A number of schemes exist for specifying the rule databases, typically
as a linear list of rules. When a packet arrives, the filter checks
the packet (using the header and/or content information) against the
rules to determine whether it should be accepted. These rule databases
can become very complex leading to two problems:

- It becomes difficult to understand what the rule database means

- The cost of rule look-up becomes large, which particularly for
  routers may increase latency

Ordered binary decision diagrams (BDDs) are a potential
method of representing the rules. BDDs are a compact, canonical method of
representing and manipulating boolean expressions. The rules are
automatically converted from their conventional format (typically a
proprietary one) to an intermediate BDD representation. The research
being conducted explores the following questions
 - can graphical representations of the BDDs be used to give a
   maintainer of a rule base an intuitive understanding of
   the rule base?
 - can the BDD representation be used to perform consistency
   and integrity checking of the rule base or modifications to
   the rule base, and to validate the rules?
 - can the time for rule look-up (to determine whether a packet should be
   accepted) be reduced by using BDDs?
 - can the BDDs be used to design cheap and effective hardware to 
   reduce look-up times?