Diverse Firewall Design

Time: 12:30pm-1:30pm, October 29th, 2004

Place: Nueces Conference Room

Abstract:

Firewalls are safety-critical systems that secure most private
networks. An error in a firewall either leaks secret information
from its network or disrupts legitimate communication between its
network and the rest of the Internet. How to design a correct
firewall is therefore an important issue. In this paper, we
propose the method of diverse firewall design, which is inspired
by the well-known method of design diversity for building
fault-tolerant software. Our method consists of two phases: a
design phase and a comparison phase. In the design phase, the same
requirement specification of a firewall is given to multiple teams
who proceed independently to design different versions of the
firewall. In the comparison phase, the resulting multiple versions
are compared with each other to find out all the discrepancies
between them, then each discrepancy is further investigated and a
correction is applied if necessary. The technical challenge in the
method of diverse firewall design is how to discover all the
discrepancies between two given firewalls. We present a series of
three efficient algorithms for solving this problem: (1) a
construction algorithm for constructing an equivalent ordered
firewall decision diagram from a sequence of rules, (2) a shaping
algorithm for transforming two ordered firewall decision diagrams
to become semi-isomorphic without changing their semantics, and
(3) a comparison algorithm for detecting all the discrepancies