\title{Algorithms for Analysing Firewall and Router Access Lists}

\author{Scott Hazelhurst\\
Programme for Highly Dependable Systems, Department of Computer Science,\\
University of the Witwatersrand, Johannesburg,Private Bag 3, 2050 Wits,
scott@cs.wits.ac.za}

\date{16 July 1999}



\begin{abstract}\noindent
  Network firewalls and routers use a rule database to decide
  which packets will be allowed from one network onto another. By
  filtering packets the firewalls and routers can improve security and
  performance.  However, as the size of the
  rule list increases, it becomes difficult to maintain and validate
  the rules, and lookup latency may increase significantly.
  Ordered binary decision diagrams (BDDs) -- a compact
  method of representing and manipulating boolean expressions -- are a
  potential method of representing the rules. This paper presents
  a new algorithm for representing such lists as a BDD and then
  shows how the resulting boolean expression can be used to analyse
  rule sets.
\end{abstract}