Transcript Traffic-Aware Dynamic Firewall Policy Management: Techniques

Presented by Group 2:
Shan Gao (3412192)
Dayang Yu (3441202)
Jiayu Zhou (3405232)
1
Outline
 Introduction
 Main Techniques


Matching Optimization Techniques
Early Rejection Optimization Techniques
 Comparative Study
 Conclusion
 References
(23 slides in total)
2
Introduction
 Firewall: permit or deny network traffic based on a firewall policy
 Firewall policy: a list of ordered rules  specifies what types of
packets should be allowed from/into the protected network
 Rule: filtering fields & an action field.
 The packet is accepted or denied by a specific rule if the packet
header information matches all the network fields of this rule
 Firewall policy rule management:
1. To reduce the filtering overhead (FCAPS)
2. Security (FCAPS)
3
Main Techniques
Figure 1 Classification of traffic-aware firewall policy techniques
4
Matching Optimization
 Objectives: try to minimize the matching time of normal
network traffic:
 Static techniques (not traffic-aware)

Algorithmic techniques: 1) hardware-based solutions; 2) specialized
data structures; 3) heuristics  improve the search time
 Adaptive techniques (traffic-aware)

Rule-based optimization: 1) common branch tree; 2) offline
statistical-based rule generation; 3) dynamic rule ordering;

Field-based optimization: 1) multifield alphabetic tree; 2)
huffman-tree-based filtering; 3) segment-list-based filtering
5
Adaptive traffic-aware ——
Rule-based optimization
1) Common Branch Tree

Number of rules & number of fields  build common branch
decision trees  good average case performance:

Less memory than binary decision trees

Limitation: decision tree needs to be rebuilt every time the
traffic pattern changes
6
Adaptive traffic-aware ——
Rule-based optimization
2) Offline Statistical-Based Rule Generation
Traffic-aware firewall optimizer (TFO):
 Step 1: pre-optimization (removes redundancies)
 Step 2: a rule-set-based optimizer & a traffic-based
optimizer

The rule-set-based optimizer: Disjoint Set Creator (DSC)
& Disjoint Set Merger (DSM) algorithms
 The traffic-based optimizer: hot caching, default proxy,
total re-ordering, online adaptation

7
Adaptive traffic-aware ——
Rule-based optimization
3) Dynamic Rule Ordering

The optimal rule ordering (ORO) problem is NP-hard
 a heuristic approximation algorithm  achieves nearoptimal results

Compute filtering rule weights based on: matching
frequency & matching recency

Limitation: it is not good for policies with a large
number of overlapping rules.
8
Adaptive traffic-aware ——
Field-based optimization
1) Multifield Alphabetic Tree

Calculates the field value frequency  build the
alphabetic search tree  adaptive packet searching

The alphabetic search tree: improve the overall average
filtering

Limitation: the overhead of updating the tree can be
significant
9
Adaptive traffic-aware ——
Field-based optimization
2) Huffman-Tree-Based Filtering

The Huffman tree: represent the segmentation of traffic
address space in the firewall policy

Number of rules & number of segments  build a Huffman
tree  enhance the performance of searching & good for
policies with a large number of rules

Limitation: the Huffman tree needs to be rebuilt
periodically to reflect changes in network flows.
10
Adaptive traffic-aware ——
Field-based optimization
3) Segment-List-Based Filtering

Number of rules & number of segments  build a policysegment-based search list  get rid of the maintenance
cost of the Huffman tree

A heuristic algorithm  minimize the average search time

Limitation: it has transient behavior until a good order of
segments is obtained
11
Early Rejection Optimization
 Importance
• Protect firewalls from DoS attacks that target the default deny
rule.
• Minimize the filtering overhead.
 Classification
 Online early rejection
• Field value cover-based early rejection
• BDD-based relaxed policy
 Blacklist blocking
• Longest common prefix(LCP)-based blacklist blocking
12
Online Early Rejection——
Field value cover-based early rejection
 Objective
Filter out as many discarded packets as possible with the
lowest overhead.
 Basic idea
 The early rejection rules can be formed as a combination of the
common field values that cover all rules in the policy.
A typical early rejection rule(RR)
The limitation of the technique is that it is not suitable for
large number of rules.
13
Online Early Rejection ——
BDD-Based Relaxed Policy
 Basic idea
• Approximate the current policy with another new policy.
Provided a packet, the technique evaluates it against the policy,
and reaches one of three options: accepted, rejected or more
filtering is needed by the original policy.
• Efficient Boolean expression can be used to represent and
approximate the policy
Each Boolean expression represents the different packets that
match a specific rule, and the variables used for this expression
correspond to the bits of individual packet header fields
14
Online Early Rejection ——
BDD-Based Relaxed Policy
The limitation of the technique is that the overhead to build
the BDD is usually significant.
15
Longest Common Prefix (LCP)-Based
Blacklist Blocking
 Objective
Minimize the impact of malicious sources in the network
using the available network resources.
 Basic idea
Addresses with certain prefixes should be blocked.
 Data structure
LCP tree ----a kind of binary tree.
16
Longest Common Prefix (LCP)-Based
Blacklist Blocking
Leaves of the tree represent the
malicious IP addresses.
All the other nodes represent
the longest common prefixes
between any pair of IPs in the
tree.
Example of LCP tree
The limitation of this technique is that all the malicious IP addresses
must be known before the computation of the optimal solution.
17
Comparative Study
Table 1 . Comparison of the algorithms, data structures, and complexity of traffic-aware dynamic
firewall policy techniques.
18
Comparative Study
 Introduction to Related Terms
 Skewedness: The measure of asymmetry in the probability
distribution of traffic.
Higher

skewedness
Traffic “leans” to
one side of the
mean
Smaller number
of rules required
to match
 Dynamic: An index to measure whether the traffic pattern
has frequent changes or not.
Higher
dynamic
Adapt firewalls
more
dynamically
19
Minimize the
packets’
matching time
Comparative Study
(+ denotes corresponding technique suits this property )
(- denotes corresponding technique doesn’t suit this property)
(N/A denotes this technique is not applicable for this property)
Table 2. Comparison of limitations and application suitability of traffic–aware dynamic
firewall policy techniques.
20
Conclusion
FCAPS
 Fault management
 Configuration management
 Accounting management
 Performance management: The decrease of matching time by
using different techniques can provide high performance packet
filtering.
 Security management: Border device only passes packets that
satisfy rules, block the malicious sources in the network occupy
the available network resources.
21
References
[1] Duan Qi and Ehab Al-Shaer, “Traffic-aware dynamic firewall policy management:
techniques and applications”, Communications Magazine, IEEE, 2013, vol. 51, no. 7.
[2] S. Acharya et al., “Traffic-Aware Firewall Optimization Strategies,” IEEE ICC, 2006.
[3] A. Attar, “Performance Characteristics of BDD-Based Packet Filters”, University of the
Witwatersrand, 2001.
[4] H. Hamed and E. Al-Shaer, “Dynamic Rule Ordering Optimization for High-Speed
Firewall Filtering,” ASIACCS’06, 2006.
[5] H. Hamed, A. El-Atawy, and E. Al-Shaer, “Adaptive Statistical Optimization Techniques
for Firewall Packet Filtering,” IEEE INFOCOM ’06, Apr. 2006.
[6] F. Soldo, A. Markopoulou, and K. J. Argyraki, “Optimal Filtering of Source Address
Prefixes: Models and Algorithms,” IEEE INFOCOM ’09, 2009, pp. 2446–54.
[7] M. Tim, Tele9752 Network Operations and Control, Lecture notes, 2013
22
THANK YOU !
23