A theory for the design and analysis of firewalls

Firewalls are the most critical and widely deployed intrusion prevention systems. A firewall is a security guard placed at the point of entry between a private network and the outside Internet such that all incoming and outgoing packets have to pass through it. The function of a firewall is to examine every incoming or outgoing packet and decide whether to accept or discard it. This function is conventionally specified by a sequence of rules, where rules often conflict. To resolve conflicts, the decision for each packet is the decision of the first rule that the packet matches. Consequently, the rules in a firewall are order sensitive. Because of the conflicts and order sensitivity of firewall rules, firewalls are difficult to design and analyze correctly. It has been observed that most firewalls on the Internet are poorly designed and have many errors in their rules. Towards the goal of correct firewalls, this dissertation focuses on the following two fundamental problems: first, how to design a new firewall such that the errors introduced in the design phase is reduced; second, how to analyze an existing firewall such that we can detect errors that have been built in. For firewall design, we proposed two methods for designing stateless firewalls, namely the method of structured firewall design and the method of diverse firewall design, and a model for specifying stateful firewalls. For firewall analysis, we proposed two methods, namely firewall queries and firewall redundancy detection. The firewall design and analysis methods presented in this dissertation are not limited to just firewalls. Rather, they are extensible to other rule-based systems such as general packet classification systems and IPsec. This extension is straightforward.