**Firewall Design:**

**Consistency, Completeness, and Compactness**

### Mohamed G. Gouda and Xiang-Yang Alex Liu Department of Computer Sciences

### The University of Texas at Austin Austin, Texas 78712-1188, U.S.A.

### {gouda, alex}@cs.utexas.edu

**Abstract**

*A firewall is often placed at the entrance of each pri-* *vate network in the Internet. The function of a firewall is* *to examine each packet that passes through the entrance* *and decide whether to accept the packet and allow it to* *proceed or to discard the packet. A firewall is usually de-* *signed as a sequence of rules. To make a decision concern-* *ing some packets, the firewall rules are compared, one by* *one, with the packet until one rule is found to be satisfied* *by the packet: this rule determines the fate of the packet.*

*In this paper, we present the first ever method for design-* *ing the sequence of rules in a firewall to be consistent, com-* *plete, and compact. Consistency means that the rules are or-* *dered correctly, completeness means that every packet satis-* *fies at least one rule in the firewall, and compactness means* *that the firewall has no redundant rules. Our method starts* *by designing a firewall decision diagram (FDD, for short)* *whose consistency and completeness can be checked sys-* *tematically (by an algorithm). We then apply a sequence of* *five algorithms to this FDD to generate, reduce and sim-* *plify the target firewall rules while maintaining the consis-* *tency and completeness of the original FDD.*

**1. Introduction**

### A firewall is often placed at each entry point of private network in the Internet. The function of this firewall is to provide secure access to and from the private network. In particular, any packet that attempts to enter or leave the pri- vate at some entry point is first examined by the firewall lo- cated at that point, and depending on the different fields of the packet, the firewall decides either to accept the packet and allow it to proceed in its way, or to discard the packet.

### To perform its function, a firewall consists of a sequence of rules; each rule is of the form

### hpredicatei → hdecisioni

### where the hpredicatei is a boolean expression over the dif- ferent fields of a packet, and the hdecisioni is either “a”

### (for accept) or “d” (for discard). To reach a decision con- cerning a packet, the rules in the sequence are examined one by one until the first rule, whose hpredicatei is satis- fied by the packet fields, is found. The hdecisioni of this rule is applied to the packet.

### Designing the sequence of rules for a firewall is not any easy task. In fact, the sequence of rules for any firewall needs to be consistent, complete, and compact as we illus- trated by the next (admittedly simple) example.

**Example: Figure 1 shows a private network that con-** tains a mail server s and a host h. The private network is connected to the firewall via interface 1, whereas the rest of the Internet is connected to the firewall via interface 0. The rest of the Internet has a malicious host m.

### Host

CISCOSYSTEMS

### 0 1 ^{Internet} Mail Server Host

**Figure 1. A firewall in a simple network**

### In this example, we assume that each packet has five fields named as follows:

**I is the interface on which the packet reaches the firewall** **S is the original source of the packet**

**D is the ultimate destination of the packet**

**P is the transport protocol of the packet**

**T is the destination port of the packet**

### The firewall in this example consists of the following se- quence

### ( I = 0 ∧ S = any ∧ D = s ∧ P = tcp ∧ T = 25 → a, I = 0 ∧ S = any ∧ D = s ∧ P = any ∧ T = any → d, I = 0 ∧ S = m ∧ D = any ∧ P = any ∧ T = any → d, I = 1 ∧ S = h ∧ D = any ∧ P = any ∧ T = any → a, I = 1 ∧ S = any ∧ D = any ∧ P = any ∧ T = any → a)

### We refer to these five rules as r 0 through r 4 , respectively.

### Rule r 0 accepts each incoming SMTP packet whose ulti- mate destination is a mail server s. Rule r 1 discards each incoming non-SMTP packet whose ultimate destination is s. Rule r 2 discards each incoming packet whose original source is a malicious host m. Rule r 3 accepts each outgo- ing packet whose original source is a host h. Rule r 4 accepts each outgoing packet. Next, we argue that this sequence of five rules suffers from three types of errors: consistency er- rors, completeness errors, and compactness errors.

### The two rules r 0 and r 2 are conflicting because there are packets whose fields satisfy the predicates of both r 0 and r 2 (for example, a packet where I = 0, S = m, D = s, P = tcp, and T = 25 satisfies the predicates of both r 0 and r 2 ) and these two rules have different decisions. Therefore, the relative order of these two rules with respect to one an- other in the sequence of rules becomes very critical. For ex- ample, by placing rule r 2 behind rule r 0 in the above rule sequence, the firewall accepts all incoming SMTP packets even those that originated at the malicious host m. This rel- ative order of rules r 0 and r 2 *is likely a consistency error.*

### This error can be corrected by placing rule r 2 at the begin- ning of the sequence of rules ahead of rule r 1 . This correc- tion will cause the firewall to discard all incoming packets, including SMTP packets, that originated at the malicious host m.

### The second error in the above rule sequence is that any packet where I = 0, S 6= m, and D 6= s does not satisfy the predicate of any of the five rules r 0 through r 5 . We re- *fer to such an error as a completeness error. This error can* be corrected by adding the following new rule immediately before rule r 3

### I = 0 ∧ S = any ∧ D = any ∧ P = any ∧ T = any → a The third error in the above rule sequence is that rule r 3

### is redundant; i.e., this rule can be removed without affect- ing the set of all packets accepted by the rule sequence and without affecting the set of all packets discarded by the rule *sequence. We refer to such an error as a compactness er-* *ror. This error can be corrected by removing rule r* 3 from the above rule sequence.

### After we preform these corrections, we end up with the following sequence of rules.

### ( I = 0 ∧ S = m ∧ D = any ∧ P = any ∧ T = any → d, I = 0 ∧ S = any ∧ D = s ∧ P = tcp ∧ T = 25 → a, I = 0 ∧ S = any ∧ D = s ∧ P = any ∧ T = any → d, I = 0 ∧ S = any ∧ D = any ∧ P = any ∧ T = any → a, I = 1 ∧ S = any ∧ D = any ∧ P = any ∧ T = any → a)

### In this paper, we present a method for designing the se- quence of rules of a firewall to be consistent, complete, and compact. According to this method, a firewall designer starts by specifying what we call a firewall decision dia- gram whose consistency and completeness can be checked systematically (by an algorithm). Then, the designer applies a sequence of five algorithm to this firewall decision dia- gram to generate a compact sequence of firewall rules while maintaining the consistency and completeness of the origi- nal diagram.

**2. Related Work**

### Design errors in existing firewalls have been reported in [3]. Yet, most of the research in the area of firewalls and packet classifiers was not dedicated to the problem of how to design correct firewalls. Rather, most of the research in this area was dedicated to developing efficient data struc- tures that can speed up the checking of firewall rules when a new packet reaches a firewall. Examples of such data structures are the trie data structures in [12], area-based quadtrees [6], fat inverted segment trees [8]. A good sur- vey of these data structures is presented in [9].

### Another research direction in the area of firewall design has been dedicated to the development of high-level spec- ification languages that can be used in specifying firewall rules. Examples of such languages are the simple model definition language in [3], the Lisp-like language in [10], the declarative predicate language in [4], and the high level firewall language in [1]. However, none of these specifica- tion languages is able to simplify the task of ensuring con- sistency, completeness, and compactness of the firewalls be- ing specified.

### Perhaps the research direction that is closest to the spirit of the current papers is reported in [11], [7], [2]. This re- search direction is dedicated to detecting every pair of con- flicting rules in a firewall. Each detected pair of conflict- ing rules is then presented to the firewall designer who de- cides whether the two rules need to be swapped or a new rule need to be added. However, these methods do not deal with the completeness and compactness errors of a firewall.

### According to the firewall design method in the current

### paper, firewalls are first specified as firewall decision dia-

### grams. These decision diagrams are similar, but not iden-

### tical, to other types of decision diagrams such as the Bi-

### nary Decision Diagrams in [5] and the Interval Decision Di-

### agrams in [13].

**3. Firewall Decision Diagrams (FDDs)**

*A field F* i is a variable whose value is taken from a pre- *defined interval of nonnegative integers, called the domain* of F i and denoted by D(F i ).

*A packet over the fields F* 0 , · · · , F n−1 is an n-tuple (p 0 , · · · , p n−1 ) where each p i is taken from the domain D(F i ) of the corresponding field F i .

*A firewall decision diagram f (or FDD f, for short) over* the fields F 0 , · · · , F n−1 is an acyclic and directed graph that satisfies the following five conditions:

### 1. f has exactly one node that has no incoming edges, *called the root of f, and has two or more nodes that* *have no outgoing edges, called the terminal nodes of* f .

### 2. Each nonterminal node v in f is labelled with a field, denoted by F (v), taken from the set of fields F 0 , · · · , F n−1 . Each terminal node v in f is la- belled with a decision that is either accept (or “a” for short) or discard (or “d” for short).

### 3. A directed path from the root to a terminal node in f *is called a decision path. No two nodes on a decision* path in f have the same label.

### 4. Each edge e, that is outgoing of a node v in f, is la- belled with an integer set I(e), where I(e) is a subset of the domain of field F (v).

### 5. Let v be any terminal node in f. The set E(v) of all outgoing edges of node v satisfies the following two conditions:

*(a) Consistency: For any distinct e* i and e j in E(v), I(e i ) ∩ I(e j ) = ∅

*(b) Completeness:* S

### e∈E(v) I(e) = D(F (v)) where ∅ is the empty set and D(F (v)) is the domain of the field F (v).

### Figure 2 shows an FDD over two fields F 0 and F 1 . The domain of each field is the interval [0, 9]. Each edge in this FDD is labelled with a set of integers that is represented by one or more non-overlapping intervals (that cover the set of integers). For example, one outgoing edge of the root is la- belled with the two intervals [0, 3] and [8, 9] that represent the set {0, 1, 2, 3, 8, 9}.

### Let f be an FDD over the fields F 0 , · · · , F n−1 . A deci- sion path in f is denoted (v 0 e 0 · · · v k−1 e k−1 v k ) where v 0 is the root node in f, v k is a terminal node in f, and each e i is a directed edge from node v i to node v i+1 in f.

### Each decision path (v 0 e 0 · · · v k−1 e k−1 v k ) in an FDD f over the packet fields F 0 , · · · , F n−1 can be represented as a rule of the form:

### F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 → hdecisioni

### a [6,7]

### d [2,3]

### [0,3]

### [4,5] [8,9]

### [5,7] [0,1]

### [4,4]

### [8,9]

### [8,9]

### d a

### [2,3] [0,1]

### [4,4]

### [5,7]

### d d

### [0,4] [5,9]

### PSfrag replacements

### F 0

### F 1

### F 1 F 1

**Figure 2. An FDD**

### where hdecisioni is the label of the terminal node v k in the decision path and each field F i satisfies one of the following two conditions:

### 1. No node in the decision path is labelled with field F i

### and S i is the domain of F i .

### 2. There is one node v j in the decision path that is la- belled with field F i and S i is the label of edge e j in the decision path.

### An FDD f over the fields F 0 , · · · , F n−1 can be repre- sented by a sequence of rules, each of them is of the form

### F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 → hdecisioni such that the following two conditions hold. First, each rule in the sequence represents a distinct decision path in f. Sec- ond, each decision path in f is represented by a distinct rule in the sequence. Note that the order of the rules in the se- quence is immaterial.

### We refer to a sequence of rules that represents an FDD f *as a firewall of f.*

### A packet (p 0 , · · · , p n−1 ) over the fields F 0 , · · · , F n−1 is *said to be accepted by an FDD f over the same fields iff a* firewall of f has a rule

### F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 → accept such that the condition p 0 ∈ S 0 ∧ · · · ∧ p n−1 ∈ S n−1 holds.

### Similarly, a packet (p 0 , · · · , p n−1 ) over the fields F 0 , · · · , F n−1 *is said to be discarded by an FDD f over the* same fields iff a firewall of f has a rule

### F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 → discard such that the condition p 0 ∈ S 0 ∧ · · · ∧ p n−1 ∈ S n−1 holds.

### Let Σ denote the set of all packets over the fields F 0 , · · · , F n−1 , and let f be an FDD over the same fields.

*The accept set of f, denoted f.accept, is the subset of* Σ that contains all the packets accepted by f. Simi- *larly, the discard set of f, denoted f.discard, is the subset* of Σ that contains all the packets discarded by f.

**Theorem 1 (Theorem of FDDs) For any FDD f over the**

### fields F 0 , · · · , F n−1 ,

### 1. f.accept ∩ f.discard = ∅, and 2. f.accept ∪ f.discard = Σ

### where ∅ is the empty set and Σ is the set of all packets over

### the fields F 0 , · · · , F n−1 . 2

### Two FDDs f and f ^{0} over the same fields are said to be *equivalent iff they have identical accepts sets and identical* discard sets, i.e.,

### f.accept = f ^{0} .accept , and f.discard= f ^{0} .discard .

**4. Reduction of FDDs**

### As discussed in the precious section, the number of rules in a firewall of an FDD f equals the number of decision paths in f. Thus, it is advantageous to reduce the number of decision paths in an FDD without changing its semantics, i.e., without changing its accept and discard sets. The pro- cedure for reducing the number of decision paths in an FDD *without changing its accept and discard sets is called a re-* *duction of this FDD. This procedure is discussed in this sec-* tion. But before we introduce the concept of a reduced FDD, we need to introduce the concept of isomorphic nodes in an FDD.

### Two nodes v 0 and v 1 *in an FDD f are called isomorphic* in f iff v 0 and v 1 satisfy one of the following two condi- tions:

### 1. Both v 0 and v 1 are terminal nodes with identical labels in f.

### 2. Both v 0 and v 1 are nonterminal nodes and there is a one-to-one correspondence between the outgoing edges of v 0 and the outgoing edges of v 1 such that ev- ery pair of corresponding edges have identical labels and are incoming of the same node in f.

*An FDD f is called reduced iff it satisfies the following* three conditions:

### 1. f has no node with exactly one outgoing edge.

### 2. f has no two edges that are outgoing of one node and are incoming of another node.

### 3. f has no two distinct isomorphic nodes.

### The reduction procedure of FDDs is presented next.

**Algorithm 1: (Reduction of FDDs)** **input : an FDD f**

**output: a reduced FDD that is equivalent to f** **steps:**

### Repeatedly apply the following three reductions to f until none of them can be applied any further.

### 1. If f has a node v 0 with only one outgoing edge e and if e is incoming of another node v 1 , then remove

### v 0 and e from f and make the incoming edges of v 0 incoming of v 1 .

### 2. If f has two edges e 0 and e 1 that are outgoing of node v 0 and incoming of node v 1 , then remove e 0 and make the label of e 1 be the integer set I(e 0 ) ∪ I(e 1 ), where I(e 0 ) and I(e 1 ) are the integer sets that labelled edges e 0 and e 1 respectively.

### 3. If f has two isomorphic nodes v 0 and v 1 , then remove node v 1 and its outgoing edges, and make the incoming edges of v 0 incoming of v 1 .

### Applying Algorithm 1 to the FDD in Figure 2 yields the reduced FDD in Figure 3. Note that a firewall of the FDD in Figure 2 consists of six rules, whereas a firewall of the FDD in Figure 3 consists of three rules.

### a d

### [2,3]

### [5,7]

### [0,3]

### [4,7]

### [8,9]

### [0,1]

### [8,9]

### [4,4]

### PSfrag replacements

### F 0

### F 1

**Figure 3. A reduced FDD**

**5. Marking of FDDs**

### In section 8, we describe an algorithm for replacing each rule in the firewall of a reduced FDD f by a sequence of

### “simple” rules. The total number of the resulting simple rules in the firewall equals the “degree” of a “marked ver- sion” of f. Next, we define what we mean by a marked ver- sion of an FDD and its degree.

*A marked version f* ^{0} of a reduced FDD f is the same as f except that exactly one outgoing edge of each nontermi- nal node in f ^{0} is marked “ALL”. We adopt the convention:

### f.accept = f ^{0} .accept , and f.discard= f ^{0} .discard . We sometimes refer to f ^{0} *as a marked FDD.*

### Figure 4 shows two marked versions f ^{0} and f ^{00} of the reduced FDD in Figure 3. In f ^{0} , the edge labelled [4, 7]

### and the edge labelled [0, 1][4, 4][8, 9] are both marked ALL.

### In f ^{00} , the edge labelled [0, 3][8, 9] and the edge labelled [0, 1][4, 4][8, 9] are both both marked ALL.

*The degree of a set of integers S, denoted deg(S),*

### is the smallest number of non-overlapping integer in-

### tervals that cover S. For example, the degree of the set

### a d [2,3]

### [5,7]

### [0,3]

### [4,7]

### [8,9]

### [0,1]

### [4,4]

### [8,9]

### ALL

### a d

### [2,3]

### [5,7]

### [0,3]

### [4,7]

### [8,9]

### [0,1]

### [4,4]

### [8,9]

### ALL ALL PSfrag replacements ALL

### (a) f ^{0} (b) f ^{00}

### F 0 F 0

### F 1 F 1

**Figure 4. Two marked FDDs**

### {0, 1, 2, 4, 7, 8, 9} is 3 because this set is covered by the three integer intervals [0, 2], [4, 4] and [7, 9].

*The degree of an edge e in a marked FDD, denoted* deg(e), is defined as follows. If e is marked ALL, then deg(e) = 1. If e is not marked ALL, then deg(e) = deg(S) where S is the set of integers that labels edge e.

*The degree of a node v in a marked FDD, denoted* deg(v), is defined recursively as follows. If v is a termi- nal node, then deg(v) = 1. If v is a nonterminal node with k outgoing edges e 0 , · · · , e k−1 that are incoming of nodes v 0 , · · · , v k−1 respectively, then

### deg(v) =

### k−1 X

### i=0

### deg(e i ) × deg(v i )

*The degree of a marked FDD f, denoted deg(f), equals* the degree of the root node of f.

### For example, deg(f ^{0} ) = 5 where f ^{0} is the marked FDD in Figure 4(a), and deg(f ^{00} ) = 4 where f ^{00} is the marked FDD in Figure 4(b).

### From the above examples, a reduced FDD may have many marked versions, and each marked version may have a different degree. As mentioned earlier, the number of sim- ple rules in the firewall of a marked FDD equals the degree of the marked FDD. Thus, it is advantageous, when gener- ating a marked version of a reduced firewall, to generate the marked version with the smallest possible degree. This is achieved by the following algorithm.

**Algorithm 2: (Marking of FDDs)** **input : a reduced FDD f**

**output: a marked version f** ^{0} of f such that for every marked version f ^{00} of f, deg(f ^{0} ) ≤ deg(f ^{00} ) **steps:**

### 1. Compute the degree of each terminal node v in f as follows:

### deg(v) = 1

### 2. **while f has a node v whose degree has not yet been** computed and v has k outgoing edges e 0 , · · · , e k−1

### that are incoming of the nodes v 0 , · · · , v k−1 , respec- tively, whose degrees have already been computed **do**

### (1) Find an outgoing edge e j of v whose quantity (deg(e j ) − 1) × deg(v j )

### is larger than or equal to the corresponding quantity of every other outgoing edge of v.

### (2) Mark edge e j with “ALL”.

### (3) Compute the degree of v as follows:

### deg(v) = P k−1

### i=0 (deg(e i ) × deg(v i )) **end**

### If Algorithm 2 is applied to the reduced FDD in Figure 3, we obtain the marked FDD in Figure 4(b).

**6. Firewall Generation**

### In this section, we present an algorithm, Algorithm 3, for generating a firewall of a marked FDD f, which is gen- erated by Algorithm 2 in section 5. The generated firewall is a sequence of rules where each rule corresponds to a deci- sion path in the marked FDD f. Algorithm 3 computes for each rule in the generated firewall a binary number, called *rank of the rule, and two predicates, called exhibited and* *original predicates of the rule. The rule ranks are used to* order the computed rules in the generated firewall. The ex- hibited and original predicates of the rules are used in the next section to make the generated firewall “compact”.

*A firewall r over the fields F* 0 , · · · , F n−1 is a sequence of rules r 0 , · · · , r m−1 where each rule is of the form

### F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 → hdecisioni Each S i is either the mark ALL or a nonempty set of inte- gers taken from the domain of field F i (which is an interval of consecutive nonnegative integers). The hdecisioni is ei- ther a (for accept) or d (for discard). The last rule, r m−1 , in firewall r is of the form:

### F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 → hdecisioni where each S i is either the mark ALL or the entire domain of field F i .

### A packet (p 0 , · · · , p n−1 ) over the fields F 0 , · · · , F n−1 is *said to match a rule r* i in a firewall over the same fields iff rule r i is of the form

### F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 → hdecisioni and the predicate (p 0 ∈ S 0 ∧ · · · ∧ p n−1 ∈ S n−1 ) holds.

### A packet over the fields F 0 , · · · , F n−1 *is said to be ac-* *cepted by a firewall r over the same fields iff r has a rule r* i

### that satisfies the following three conditions:

### 1. The packet matches r i .

### 2. The packet does not match any rule that precedes r i .

### 3. The hdecisioni of r i is a.

### Similarly, a packet over the fields F 0 , · · · , F n−1 is said *to be discarded by a firewall r over the same fields iff r has* a rule r i that satisfies the following three conditions:

### 1. The packet matches r i .

### 2. The packet does not match any rule that precedes r i . 3. The hdecisioni of r i is d.

### Let r be a firewall over the fields F 0 , · · · , F n−1 . The set of all packets accepted by r is denoted r.accept, and the set of all packets discarded by r is denoted r.discard. The next theorem follows from these definitions.

**Theorem 2 (Theorem of Firewalls) For any firewall r** over the fields F 0 , · · · , F n−1 ,

### 1. r.accept ∩ r.discard = ∅, and 2. r.accept ∪ r.discard = Σ

### where ∅ is the empty set and Σ is the set of all packets over

### the fields F 0 , · · · , F n−1 . 2

**Algorithm 3: (Firewall Generation)**

**input : a marked FDD f over the fields F** 0 , · · · , F n−1

### and assume that along each directed path in f, if a field F i appears before field F j then i < j.

**output: a firewall r over the same fields such that** r.accept = f.accept , and r.accept = f.accept

### and for each rule r i in r, the algorithm computes a binary number of n bits, called the rank of r i , and two predicates, called the exhibited and original predicates of r i .

**steps:**

### 1. For each decision path in f, compute a rule r i , its rank, its exhibited predicate ep i and its original predicate op i as follows:

### F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 → hdecisioni rank = b 0 · · · b n−1

### ep _{i} = (F 0 ∈ S 0 ∧ · · · ∧ F n−1 ∈ S n−1 ) op _{i} = (F 0 ∈ T 0 ∧ · · · ∧ F n−1 ∈ T n−1 ) where each b i , S i , and T i is computed according to the following three cases:

**Case 1:(The decision path has no nodes labelled F** i ) b i = 0

**Case 1:(The decision path has no nodes labelled F**

### S i =the domain [a i , b i ] of F i

### T i =the domain [a i , b i ] of F i

**Case 2:(The decision path has a node labelled F** i *,* *and its outgoing edge e has no mark)* b i = 0

**Case 2:(The decision path has a node labelled F**

### S i =the integer set that labels e T i =the integer set that labels e

**Case 3:(The decision path has a node labelled F** i *,* *and its outgoing edge e has an ALL mark)* b i = 1

**Case 3:(The decision path has a node labelled F**