Firewall verification and redundancy checking are equivalent

A firewall is a packet filter that is placed at the entrance of a private network. It checks the header fields of each incoming packet into the private network and decides, based on the specified rules in the firewall, whether to accept the packet and allow it to proceed or to discard the packet. To validate the correctness and effectiveness of the rules in a firewall, the firewall rules are usually subjected to two types of analysis: verification and redundancy checking. Verification is used to verify that the rules in a firewall accept all packets that should be accepted and discard all packets that should be discarded. Redundancy checking is used to check that no rule in a firewall is redundant (i.e. can be removed from the firewall without changing the sets of packets accepted and discarded by the firewall). In this paper we show that, contrary to the conventional wisdom, these two types of analysis are in fact equivalent. In particular, we show that (1) every verification algorithm can be also used to check whether a rule in a firewall is redundant, and (2) every redundancy checking algorithm can be also used to verify whether the rules in a firewall accept or discard an intended set of packets.