A firewall configuration defines which packets are legitimate and which are illegitimate. An error in a firewall configuration, i.e., a wrong definition of being legitimate or illegitimate for some packets, means that the firewall either accepts some malicious packets, which consequently creates security holes on the firewall, or discards some legitimate packets, which consequently disrupts normal businesses. Given the importance of firewalls, such errors are not acceptable. Unfortunately, it has been observed that most firewalls on the Internet are poorly designed and have many errors in their configurations [Wool (2004)]. Therefore, how to design a new firewall configuration and how to analyze an existing firewall configuration become important issues.