Specification Based Firewall Testing




Ma, Huibo Heidi

Journal Title

Journal ISSN

Volume Title



Firewalls are crucial elements in network security, and have been widely deployed in most businesses and institutions for securing private networks. A firewall consists of a sequence of rules. The function of a firewall is to examine each incoming and outgoing packet and decide to either accept the packet (i.e., allow it to proceed) or discard the packet based on the sequence of rules. The decision made by a firewall for a packet is the decision of the first rule that the packet matches. As a safety-critical system, a firewall needs to be correctly implemented by a sequence of rules according to its specification. However, since the number of rules in a firewall may be large and the rules may conflict, a firewall often contains errors that make the firewall inconsistent with its specification. To check whether the firewall implementation of a sequence of rules is consistent with its specification or not, a firewall designer usually need to figure out the answers to the queries such as “which computers in the private network can receive BOOTP packets from the outside Internet?”. We call the process of testing a firewall by issuing such test queries specification based firewall testing. The technical challenge in specification based firewall testing is how to answer the test queries based on a firewall specification. To solve this problem, in this thesis, we propose a firewall testing algorithm based on a data structure called Firewall Decision Diagram proposed in [11]. Given a firewall of a sequence of rules, we at first construct an equivalent firewall decision diagram from the sequence of rules by the construction algorithm in Chapter 3. Then given each firewall testing query, the firewall decision diagram is used as the core data structure for answering the query by the firewall testing algorithm in Chapter 4. The experimental results show that our firewall testing algorithm is very efficient. Even given a firewall of 5000 rules, it takes less than 4 seconds for the firewall testing algorithm to answer a firewall testing query.



firewalls, computer security


Ma, H. H. (2004). Specification based firewall testing (Unpublished thesis). Texas State University-San Marcos, San Marcos, Texas.


Rights Holder

Rights License

Rights URI