Structured firewall design

Citation

• Mohamed G. Gouda, Alex X. Liu. Computer Networks 51 (2007) 1106-1120.

Abstract

A firewall is a security guard placed at the point of entry between a private network and the outside Internet such thatall incoming and outgoing packets have to pass through it. The function of a firewall is to examine every incoming or out-going 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 packetmatches. The current practice of designing a firewall directly as a sequence of rules suffers from three types of major prob-lems: (1) the consistency problem, which means that it is difficult to order the rules correctly; (2) the completeness problem,which means that it is difficult to ensure thorough consideration for all types of traffic; (3) the compactness problem, whichmeans that it is difficult to keep the number of rules small (because some rules may be redundant and some rules may becombined into one rule).To achieve consistency, completeness, and compactness, we propose a new method called structured firewall design,which consists of two steps. First, one designs a firewall using a firewall decision diagram instead of a sequence of oftenconflicting rules. Second, a program converts the firewall decision diagram into a compact, yet functionally equivalent,sequence of rules. This method addresses the consistency problem because a firewall decision diagram is conflict-free. Itaddresses the completeness problem because the syntactic requirements of a firewall decision diagram force the designerto consider all types of traffic. It also addresses the compactness problem because in the second step we use two algorithms(namely FDD reduction and FDD marking) to combine rules together, and one algorithm (namely firewall compaction)to remove redundant rules. Moreover, the techniques and algorithms presented in this paper are extensible to otherrule-based systems such as IPsec rules.Ó 2006 Elsevier B.V. All rights reserved.

Annotation

Problem:

• designing a firewall directly on top of a sequence of rules suffers from 3 problems:
• Consistency problem: order correctly
  • conflict <==> overlap + different decisions
• Completeness problem: consider all types of traffic
• Compactness problem: keep rule set small
  • redundancy <==> subset + same decision

Use High-level language to specify firewall rules --> vendor specific language

Structured firewall design – use firewall decision diagram (FDD) instead of a sequence of rules.

• Node = field
• Edge = non-overlapping integer intervals
• Leave node = decision
• Decision path = root to leave

1. FDD Reduction

• reduce decision paths

2. FDD Marking

• exactly one edge of each node is marked “all”
• reduce the load of some edges

3. Firewall Generation

• generate a sequence of rules
• Depth-first search in DAG

4. Firewall Compaction

• remove redundant rules
• e.g. F2->d in Fig.6
• why after step 3? Can further reduce DAG to tree?

5. Firewall Simplification

• simple = consecutive integer interval

Alg. 1,2,4 reduce the number of rules.