anomalies in firewall policy

318

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,

VOL. 9,

NO. 3,

MAY/JUNE 2012

Detecting and Resolving
Firewall Policy Anomalies
Hongxin Hu, Student Member, IEEE,
Gail-Joon Ahn, Senior Member, IEEE, and Ketan Kulkarni
Abstract—The advent of emerging computing technologies such as service-oriented architecture and cloud computing has enabled
us to perform business services more efficiently and effectively. However, we still suffer from unintended security leakages by
unauthorized actions in business services. Firewalls are the most widely deployed security mechanism to ensure the security of private
networks in most businesses and institutions. The effectiveness of security protection provided by a firewall mainly depends on the
quality of policy configured in the firewall. Unfortunately, designing and managing firewall policies are often error prone due to the
complex nature of firewall configurations as well as the lack of systematic analysis mechanisms and tools. In this paper, we represent
an innovative policy anomaly management framework for firewalls, adopting a rule-based segmentation technique to identify policy
anomalies and derive effective anomaly resolutions. In particular, we articulate a grid-based representation technique, providing an
intuitive cognitive sense about policy anomaly. We also discuss a proof-of-concept implementation of a visualization-based firewall
policy analysis tool called Firewall Anomaly Management Environment (FAME). In addition, we demonstrate how efficiently our
approach can discover and resolve anomalies in firewall policies through rigorous experiments.
Index Terms—Firewall, policy anomaly management, access control, visualization tool.

Ç
1

INTRODUCTION

A

S one

of essential elements in network and information attention [1], [3], [4], [5]. Corresponding policy analysis tools,
system security, firewalls have been widely deployed such as Firewall Policy Advisor [1] and FIREMAN [5], with
in defending suspicious traffic and unauthorized access to the goal of detecting policy anomalies have been introduced.
Internet-based enterprises. Sitting onhttp://ieeexploreprojects.blogspot.com
the border between a Firewall Policy Advisor only has the capability of detecting
private network and the public Internet, a firewall examines pairwise anomalies in firewall rules. FIREMAN can detect
all incoming and outgoing packets based on security rules. anomalies among multiple rules by analyzing the relationTo implement a security policy in a firewall, system ships between one rule and the collections of packet spaces
administrators define a set of filtering rules that are derived
derived from all preceding rules. However, FIREMAN also
from the organizational network security requirements.
has limitations in detecting anomalies [3]. For each firewall
Firewall policy management is a challenging task due to
the complexity and interdependency of policy rules. This is rule, FIREMAN only examines all preceding rules but
further exacerbated by the continuous evolution of network ignores all subsequent rules when performing anomaly
and system environments. For instance, Al-Shaer and analysis. In addition, each analysis result from FIREMAN
Hamed [1] reported that their firewall policies contain can only show that there is a misconfiguration between one
anomalies even though several administrators including rule and its preceding rules, but cannot accurately indicate all
nine experts maintained those policies. In addition, Wool [2] rules involved in an anomaly.
On the other hand, due to the complex nature of policy
recently inspected firewall policies collected from different
organizations and indicated that all examined firewall anomalies, system administrators are often faced with a more
policies have security flaws.
challenging problem in resolving anomalies, in particular,
The process of configuring a firewall is tedious and error resolving policy conflicts. An intuitive means for a system
prone. Therefore, effective mechanisms and tools for policy administrator to resolve policy conflicts is to remove all
management are crucial to the success of firewalls. Recently, conflicts by modifying the conflicting rules. However,
policy anomaly detection has received a great deal of changing the conflicting rules is significantly difficult, even
impossible, in practice from many aspects. First, the number
of conflicts in a firewall is potentially large, since a firewall
. H. Hu and G.-J. Ahn are with the Security Engineering for Future
Computing (SEFCOM) Laboratory, and the Ira A. Fulton School of policy may consist of thousands of rules, which are often
Engineering, Arizona State University, PO Box 878809, Tempe, AZ logically entangled with each other. Second, policy conflicts
85287. E-mail: {hxhu, gahn}@asu.edu.
are often very complicated. One rule may conflict with
. K. Kulkarni is with the Emerson Network Power and the Ira A. Fulton
School of Engineering, Arizona State University, PO Box 878809 Tempe, multiple other rules, and one conflict may be associated with
several rules. Besides, firewall policies deployed on a
AZ 85287. E-mail: [email protected].
Manuscript received 8 Apr. 2011; revised 5 Jan. 2012; accepted 10 Jan. 2012; network are often maintained by more than one adminispublished online 30 Jan. 2012.
trator, and an enterprise firewall may contain legacy rules
Recommended for acceptance by M. Singhal.
that are designed by different administrators. Thus, without a
For information on obtaining reprints of this article, please send e-mail to:
[email protected], and reference IEEECS Log Number TDSC-2011-04-0097. priori knowledge on the administrators’ intentions, changing
rules will affect the rules’ semantics and may not resolve
Digital Object Identifier no. 10.1109/TDSC.2012.20.
1545-5971/12/$31.00 ß 2012 IEEE

Published by the IEEE Computer Society

HU ET AL.: DETECTING AND RESOLVING FIREWALL POLICY ANOMALIES

319

conflicts correctly. Furthermore, in some cases, a system
TABLE 1
administrator may intentionally introduce certain overlaps in
An Example Firewall Policy
firewall rules knowing that only the first rule is important. In
reality, this is a commonly used technique to exclude specific
parts from a certain action, and the proper use of this
technique could result in a fewer number of compact rules [5].
In this case, conflicts are not an error, but intended, which
would not be necessary to be changed.
Since the policy conflicts in firewalls always exist and are
hard to be eliminated, a practical resolution method is to
identify which rule involved in a conflict situation should implement a visualization-based firewall anomaly managetake precedence when multiple conflicting rules (with ment environment (FAME) based on our approach. To
different actions) can filter a particular network packet evaluate the practicality of our tool, our extensive experisimultaneously. To resolve policy conflicts, a firewall ments deal with a set of real-life firewall policies.
This paper is organized as follows: Section 2 overviews
typically implements a first-match resolution mechanism
based on the order of rules. In this way, each packet processed the anomalies in firewall policies. Section 3 presents an
by the firewall is mapped to the decision of the first rule that anomaly representation technique based on packet space. In
the packet matches. However, applying the first-match Section 4, we articulate our policy anomaly management
strategy to cope with policy conflicts has limitations. When framework. In Section 5, we address the implementation
a conflict occurs in a firewall, the existing first matching rule details and evaluations of FAME. Section 6 describes
may not be a desired rule that should take precedence with several important issues followed by the related work in
respect to conflict resolution. In particular, the existing first
Section 7. Section 8 concludes this paper.
matching rule may perform opposite action to the rule which
should be considered to take precedence. This situation can
cause severe network breaches such as permitting harmful 2 OVERVIEW OF ANOMALIES IN FIREWALL POLICIES
packets to sneak into a private network, or dropping legal
A firewall policy consists of a sequence of rules that define the
traffic which in turn could encumber the availability and
actions performed on packets that satisfy certain conditions.
utility of network services. Obviously, it is necessary to seek a
way to bridge a gap between conflict detection and conflict The rules are specified in the form of hcondition; actioni. A
condition in a rule is composed of a set of fields to identify a
resolution with the first-match mechanism in firewalls.
In this paper, we represent a novelhttp://ieeexploreprojects.blogspot.com
anomaly management certain type of packets matched by this rule. Table 1 shows an
framework for firewalls based on a rule-based segmentation example of a firewall policy, which includes five firewall

technique to facilitate not only more accurate anomaly rules r1 , r2 , r3 , r4 , and r5 . Note that the symbol “ ” utilized in
detection but also effective anomaly resolution. Based on this firewall rules denotes a domain range. For instance, a single

technique, a network packet space defined by a firewall policy “ ” appearing in the IP address field represents an IP address
can be divided into a set of disjoint packet space segments. range from 0.0.0.0 to 255.255.255.255.
Several related work has categorized different types of
Each segment associated with a unique set of firewall rules
firewall
policy anomalies [1], [5]. Based on following
accurately indicates an overlap relation (either conflicting or
classification,
we articulate the typical firewall policy
redundant) among those rules. We also introduce a flexible
conflict resolution method to enable a fine-grained conflict anomalies:
resolution with the help of several effective resolution
1. Shadowing. A rule can be shadowed by one or a set of
strategies with respect to the risk assessment of protected
preceding rules that match all the packets which also
networks and the intention of policy definition. Besides, a
match the shadowed rule, while they perform a
more effective redundancy elimination mechanism is prodifferent action. In this case, all the packets that one
vided in our framework, and our experimental results show
rule intends to deny (accept) can be accepted
that our redundancy discovery mechanism can achieve
(denied) by previous rule(s); thus, the shadowed
approximately 70 percent improvement compared to tradirule will never be taken effect. In Table 1, r4 is
tional redundancy detection approaches [1], [6]. Moreover,
shadowed
by r3 because r3 allows every TCP packet
the outputs of prior policy analysis tools [1], [5] are mainly a
coming
from
any port of 10.1.1. to the port 25 of
list of possible anomalies, which does not give system

192.168.1. , which is supposed to be denied by r4 .
administrators a clear view of the origination of policy
2. Generalization. A rule is a generalization of one or a
anomalies. Since information visualization technique [7]
set of previous rules if a subset of the packets
enables users to explore, analyze, reason, and explain
matched by this rule is also matched by the
abstract information by taking advantage of their visual
preceding rule(s) but taking a different action. For
cognition, our policy analysis tool adopts an information
example, r5 is a generalization of r4 in Table 1. These
visualization technique to facilitate policy analysis. A gridtwo rules indicate that all the packets from 10.1.1.
based visualization approach is introduced to represent
are allowed, except TCP packets from 10.1.1. to the
policy anomaly diagnosis information in an intuitive way,
port 25 of 192.168.1. . Note that, as we discussed
enabling an efficient anomaly management.1 In addition, we
earlier, generalization might not be an error.
3. Correlation. One rule is correlated with other rules, if a
1. Our proposed methodology can be also extended to deal with the
anomalies in other kinds of policies, such as XACML-based policies [8].
rule intersects with others but defines a different

320

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,

action. In this case, the packets matched by the
intersection of those rules may be permitted by one
rule, but denied by others. In Table 1, r2 correlates
with r5 , and all UDP packets coming from any port of
10.1.1. to the port 53 of 172.32.1. match the
intersection of these rules. Since r2 is a preceding
rule of r5 , every packet within the intersection of these
rules is denied by r2 . However, if their positions are
swapped, the same packets will be allowed.
4. Redundancy. A rule is redundant if there is another
same or more general rule available that has the same
effect. For example, r1 is redundant with respect to r2
in Table 1, since all UDP packets coming from any
port of 10.1.2. to the port 53 of 172.32.1. matched
with r1 can match r2 as well with the same action.
Anomaly detection algorithms and corresponding tools
were introduced by [1], [5] as well. However, existing
conflict classification and detection approaches only treat a
policy conflict as an inconsistent relation between one rule
and other rules. Given a more general definition on policy
conflict as shown in Definition 1, we believe that identifying
policy conflicts should always consider a firewall policy as a
whole piece, and precise indication of the conflicting
sections caused by a set of overlapping rules is critical for
effectively resolving the conflicts.

VOL. 9,

NO. 3,

MAY/JUNE 2012

purpose of firewall policy anomaly analysis. Algorithm 1
shows the pseudocode of generating packet space segments
for a set of firewall rules R.2 This algorithm works by
adding a network packet space s derived from a rule r to a
packet space set S. A pair of packet spaces must satisfy one
of the following relations: subset (line 5), superset (line 10),
partial match (line 13), or disjoint (line 17). Therefore, one can
utilize set operations to separate the overlapped spaces into
disjoint spaces.

Definition 1 (Policy Conflict). A policy conflict pc in a firewall
F is associated with a unique set of conflicting firewall rules
cr ¼ fr1 ; . . . ; rn g, which can derive a common network packet
A set of segments S : fs1 ; s2 ; . . . ; sn g from firewall rules
space. All packets within this space can match exactly the same
http://ieeexploreprojects.blogspot.com
set of firewall rules, where at least two rules have different has the following two properties:
actions: Allow and Deny.
1. All segments are pairwise disjoint: si \ sj ¼ ;;
where 1  i 6¼ j  n; and
Similarly, we give a general definition for rule redun2. Any two different network packets p and p0 within
dancy in firewall policies as follows, which serves as a
the same segment (si ) are matched by the exact same
foundation of our redundancy elimination approach.
set of rules: GetRuleðpÞ ¼ GetRuleðp0 Þ; 8p 2 si ; p0 2
Definition 2 (Rule Redundancy). A rule r is redundant in a
si ; p 6¼ p0 , where GetRuleðÞ is a function to return all
firewall F iff the network packet space derived from the resulting
matched rules of a network packet.
policy F 0 after removing r is equivalent to the network space
To facilitate the correct interpretation of analysis results,
defined by F . That is, F and F 0 satisfy following equations: a concise and intuitive representation method is necessary.
SFA ¼ SFA0 and SFD ¼ SFD0 , where S A and S D denote allowed and For the purposes of brevity and understandability, we
denied network packet spaces, respectively.
employ a two-dimensional geometric representation for
each packet space derived from firewall rules. Note that a
3 ANOMALY REPRESENTATION BASED ON PACKET firewall rule typically utilizes five fields to define the rule
condition; thus, a complete representation of packet space
SPACE
should be multidimensional. Fig. 1a gives the two-dimen3.1 Packet Space Segmentation and Classification
sional geometric representation of packet spaces derived
As we discussed in Section 2, existing anomaly detection from the example policy shown in Table 1. We utilize
methods could not accurately point out the anomaly colored rectangles to denote two kinds of packet spaces:
portions caused by a set of overlapping rules. In order to allowed space (white color) and denied space (gray color),
precisely identify policy anomalies and enable a more respectively. In this example, there are two allowed spaces
effective anomaly resolution, we introduce a rule-based representing rules r and r , and three denied spaces
3
5
segmentation technique, which adopts a binary decision depicting rules r , r , and r .
1
2
4
diagram (BDD)-based data structure to represent rules
Two spaces overlap when the packets matching two
and perform various set operations, to convert a list of rules corresponding rules intersect. For example, r5 overlaps with
into a set of disjoint network packet spaces. This technique r2 , r3 , and r4 , respectively. An overlapping relation may
has been recently introduced to deal with several research involve multiple rules. In order to clearly represent all
problems such as network traffic measurement [9], firewall identical packet spaces derived from a set of overlapping
testing [10] and optimization [11]. Inspired by those
successful applications, we leverage this technique for the
2. Similar partitioning functionalities were addressed in [9], [10] as well.

HU ET AL.: DETECTING AND RESOLVING FIREWALL POLICY ANOMALIES

321

Fig. 1. Packet space representation derived from the example policy.

rules, we adopt the rule-based segmentation technique axis of the matrix, rules are shown along the vertical axis,
addressed in Algorithm 1 to divide an entire packet space and the intersection of a segment and a rule is a grid that
into a set of pairwise disjoint segments. We classify the displays a rule’s subspace covered by the segment.
policy segments as follows: nonoverlapping segment and
Fig. 2 shows a grid representation of policy anomalies for
overlapping segment, which is further divided into conflicting our example policy. We can easily determine which rules
overlapping segment and nonconflicting overlapping segment. are covered by a segment, and which segments are
Each nonoverlapping segment associates with one unique associated with a rule. For example, as shown in Fig. 2,
rule and each overlapping segment is related to a set of rules, we can notice that a conflicting segment (CS) s5 , which
which may conflict with each other (conflicting overlapping points out a conflict, is related to a rule set consisting of
segment) or have the same action (nonconflicting overlapping three conflicting rules r3 , r4 , and r5 (highlighted with a
segment). Fig. 1b demonstrates the segments of packet horizontal red rectangle), and a rule r3 is involved in three
spaces derived from the example policy. Since the size of segments s5 , s6 , and s7 (highlighted with a vertical red
segment representation does not give any specific benefits rectangle). Our grid representation provides a better underin resolving policy anomalies, we further present a uniform standing of policy anomalies to system administrators with
representation of space segments in Fig. 1c. We can notice an overall view of related segments and rules.
that seven unique disjoint segments are generated. Three
policy segments s2 , s4 , and s7 are nonoverlapping segments.
Other policy segments are overlapping segments, including 4 ANOMALY MANAGEMENT FRAMEWORK
two conflicting overlapping segmentshttp://ieeexploreprojects.blogspot.com
s3 and s5 , and two Our policy anomaly management framework is composed of
nonconflicting overlapping segments s1 and s6 .
two core functionalities: conflict detection and resolution, and
redundancy discovery and removal, as depicted in Fig. 3. Both
3.2 Grid Representation of Policy Anomaly
functionalities are based on the rule-based segmentation
To enable an effective anomaly resolution, complete and technique. For conflict detection and resolution, conflicting
accurate anomaly diagnosis information should be repre- segments are identified in the first step. Each conflicting
sented in an intuitive way. When a set of rules interacts, one segment associates with a policy conflict and a set of
overlapping relation may be associated with several rules. conflicting rules. Also, the correlation relationships among
Meanwhile, one rule may overlap with multiple other rules conflicting segments are identified and conflict correlation
and can be involved in a couple of overlapping relations groups (CG) are derived. Policy conflicts belonging to
(overlapping segments). Different kinds of segments and different conflict correlation groups can be resolved sepaassociated rules can be viewed in the uniform representation rately; thus, the searching space for resolving conflicts is
of anomalies (Fig. 1c). However, it is still difficult for an reduced by the correlation process. The second step
administrator to figure out how many segments one rule is generates an action constraint for each conflicting segment
involved in. To address the need of a more precise anomaly
by examining the characteristics of each conflicting segment.
representation, we additionally introduce a grid representaA strategy-based method is introduced for generating action
tion that is a matrix-based visualization of policy anomalies,
in which space segments are displayed along the horizontal

Fig. 2. Grid representation of policy anomaly.

Fig. 3. Policy anomaly management framework.

322

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,

VOL. 9,

NO. 3,

MAY/JUNE 2012

Fig. 4. Example of segment correlation.

constraints. The third step utilizes a reordering algorithm,
which is a combination of a permutation algorithm and a
greedy algorithm, to discover a near-optimal conflict resolution solution for policy conflicts. Regarding redundancy
discovery and removal, segment correlation groups are first
identified. Then, the process of property assignment is
performed to each rule’s subspaces. Consequently, redundant rules are identified and eliminated.

Fig. 5. Strategy-based conflict resolution.

4.2 Conflict Resolution
Each conflicting segment indicates a policy conflict as well
as a set of conflicting rules involved in the conflict. Once
4.1 Correlation of Packet Space Segment
Technically, one rule may get involved in multiple policy conflicts are identified, a possible way for a system
anomalies. In this case, resolving one anomaly in an isolated administrator to resolve conflicts is to manually change
manner may cause the unexpected impact on other the conflicting rules. However, as we addressed in Section 1,
anomalies. Similarly, we cannot resolve a conflict individu- resolving all conflicts manually is a tedious task and even
ally by only reordering conflicting rules associated with one impractical due to the complicated nature of policy
conflict without considering possible impacts on other conflicts. Thus, a practical and effective method to resolve
conflicts. On the other hand, it is also
inefficient to deal a policy conflict is to determine which rule should take
http://ieeexploreprojects.blogspot.com
with all conflicts together by reordering all conflicting rules precedence when a network packet is matched by a set of
rules involved in the conflict. In order to utilize the existing
simultaneously. Therefore, it is necessary to identify the
first-match conflict resolution mechanism implemented in
dependency relationships among packet space segments for
common firewalls, the rule expected to take precedence
efficiently resolving policy anomalies.
needs to be moved to the first-match rule.
3
Fig. 4 shows an example of segment correlation. Suppose
Our conflict resolution mechanism introduces that an
we add three new rules r6 , r7 , and r8 in the example policy
action constraint is assigned to each conflicting segment. An
shown in Table 1. Several rules in this firewall policy are action constraint for a conflicting segment defines a desired
involved in multiple anomalies. For example, r2 is associated action (either Allow or Deny) that the firewall policy
with three segments s1 , s2 , and s3 . Also, we can identify r3 , r5 , should take when any packet within the conflicting segment
r6 , and r7 are also associated with multiple segments. Assume comes to the firewall. Then, to resolve a conflict, we only
we need to resolve the conflict related to a conflicting segment assure that the action taken for each packet within the
s3 by reordering associated conflicting rules, r2 and r5 . The conflicting segment can satisfy the corresponding action
position change of r2 and r5 would also affect other segments, constraint. A key feature of this solution is that we do not
s1 , s2 , s4 , s5 , and s6 . Thus, a dependency relationship among need to move a rule expected to take precedence to the firstthose segments can be derived. We cluster such segments match rule at all times. Any rule associated with the conflict
with a dependency relationship as a group called correlation on the same action (as a rule with the precedence) can be
group. Consequently, two correlation groups, group1 and moved to the first-match rule, guaranteeing the same effect
group2, can be identified in our example as shown in Fig. 4: with respect to the conflict resolution. Thus, it is doable to
group1 contains seven segments and a rule set with five obtain an optimal solution for conflict resolution.
elements (r1 , r2 , r3 , r4 , and r5 ); and group2 includes three
4.2.1 Action Constraint Generation
segments and three associated rules, r6 , r7 , and r8 .
The major benefit of generating correlation groups for To generate action constraints for conflicting segments, we
the anomaly analysis is that anomalies can be examined propose a strategy-based conflict resolution method, which
within each group independently, because all correlation generates action constraints with the help of effective
resolution strategies based on the minimal interaction with
groups are independent of each other. Especially, the
system administrators. Fig. 5 shows the main processes of
searching space for reordering conflicting rules in conflict
this method, which incorporates both automated and manual
resolution can be significantly lessened and the efficiency of
strategy selections.
resolving conflicts can be greatly improved.
Once conflicts in a firewall policy are discovered and
conflict correlation groups are identified, the risk assessment
3. Note that for conflict resolution we only need to examine the
correlation relations among conflicting segments.
for conflicts is performed. The risk levels (RL) of conflicts are

HU ET AL.: DETECTING AND RESOLVING FIREWALL POLICY ANOMALIES

323

in turn utilized for both automated and manual strategy value needs to be calculated as the risk level of a conflicting
selections. A basic idea of automated strategy selection is that segment. In order to accommodate both requirements for
a risk level of a conflicting segment is used to directly risk evaluation of a conflicting segment, we introduce a
determine the expected action taken for the network packets generic equation for the risk level calculation as follows:
in the conflicting segment. If the risk level is very high, the
P
v2V ðcsÞ ðCV SSðvÞ  IV ðsÞÞ
expected action should deny packets considering the protec;
ð2Þ
RLðcsÞ ¼
  jV ðcsÞj
tion of network perimeters. On the contrary, if the risk level is
quite low, the expected action should allow packets to pass
where V ðcsÞ is a function to return all vulnerabilities that are
through the firewall so that the availability and usage of
contained in a conflicting segment cs; CV SSðvÞ is a function
network services cannot be affected. Thus, conflict resolution
to
return the CVSS base score of vulnerability v; and IV ðsÞ is a
strategies (RS) can be generated automatically for partial
function
to return the importance value (with the range from
conflict segments by comparing the risk levels with two
0.0
to
1.0)
of service s. Also, we incorporate a coefficient factor
thresholds, upper threshold (UT ) and lower threshold (LT ),
1

(

  1) that allows system administrators to
jV ðcsÞj
which can be set by system administrators in advance based
express
their
preferences in choosing average or overall risk
on the different situations of protected networks. If a risk
value
to
measure
the risk of each conflicting segment. The
level of a conflicting segment is between the upper threshold
value
of

can
be
decreased,
in which case an administrator
and the lower threshold, system administrators need to
cares
more
about
the
overall
risk
value. Otherwise, she/he can
examine the characteristics of each conflict, and manually
increase
the
value
of

until
it
reaches
an average risk value.
select appropriate strategies for resolving the conflict,
Some
general
conflict
resolution
strategies for access
considering both network situations (e.g., risk levels of
conflicts) and contexts associated with conflicting rules control have been introduced [16], [17], [18]. We classify
(e.g., priorities, creation time, authors, and so on). Thus, a conflict resolution strategies for firewall policies into two
fine-grained conflict resolution can be carried out with categories: network situation-aware strategy and policyhuman cognition via the interaction facility with system oriented strategy. Note that other user-defined strategies [19]
administrators. Since some strategies may be nondetermi- can be implied in our conflict resolution mechanism as well.
Network situation-aware strategy. A system adminisnistic and could not generate a concrete action constraint
when applying to a conflict, system administrators need to trator adopts this strategy to resolve policy conflicts based
adjust the strategy assignments accordingly. As long as all on the results of risk assessment of the network covered by
conflicts within a conflict correlation group are associated corresponding conflicting segments
with desired action constraints, these
conflicts will be
http://ieeexploreprojects.blogspot.com
. Deny-overrides. This strategy indicates that “deny”
ultimately resolved by reordering conflicting rules to satisfy
rules take precedence over “allow” rules. In general,
corresponding action constraints.
a system administrator may directly take this
Risk (security) levels are determined based on the
strategy to harden his network if the risk level of a
vulnerability assessment of the protected network. We have
conflict is very high.
recently seen a number of attempts for qualitatively
. Allow-overrides. This strategy states that “allow”rules
measuring risks in a network [12], [13], [14]. In our work,
take precedence over “deny” rules. A system
we adopt the Common Vulnerability Scoring System (CVSS)
administrator may apply this strategy to resolve a
[15] as an underlying security metrics for risk evaluation.
Two major factors, exploitability of vulnerability (reflecting the
conflict, which has a lower risk level.
likelihood of exploitation) and severity of vulnerability
Policy-oriented strategy. This strategy considers the
(representing the potential damage of exploitation), are factors related to the policy definition, such as when was
utilized to evaluate the risk level of a network system. Beside the rule defined? what was the rule defined for? and who
those two factors, another important factor in determining
defined the rule?
the criticality of an identified security problem is asset
importance value. Normally, system administrators place a
. Recency-overrides. This strategy indicates that rules
higher priority on defending critical servers than noncritical
take precedence over rules specified earlier. As the
PCs. Similarly, some machines are more valuable than
security requirements may change over a period of
others. We use asset importance value to represent a service’s
time, an administrator may define new rules along
inherent value to network attackers or system administrawith his evolving security requirements which may
tors. Since the CVSS base score can cover both exploitability of
be in conflict with previous security requirements.
vulnerability and severity of vulnerability factors, we incorpoObviously, in this case, newer rules should take
rate the CVSS base score and asset importance value to compute
precedence over older rules.
the risk value for each vulnerability as follows:
. Specificity-overrides. This strategy states that a more
specific rule overrides more general rules. In a
Risk V alue ¼ ðCV SS Base ScoreÞ  ðImportance V alueÞ:
firewall policy, shadowing and generalization conð1Þ
flicts can be identified by conflict detection tools. In
To calculate the risk level of each conflicting segment, we
our solution, we treat shadowing and generalization
accumulate all risk values of the vulnerabilities covered by
conflicts as the same case, since we resolve them
a conflicting segment. In practice, system administrators
through rule reordering.
may mainly concern about the security risk (SR) of each
. High-majority-overrides. This strategy allows (denies,
vulnerability in their network. In this case, an average risk
respectively) a packet if the number of rules taking

324

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,

VOL. 9,

NO. 3,

MAY/JUNE 2012

TABLE 2
Constraint Generation from Conflict Resolution Strategy

“allow” (“deny,” respectively) action is greater than
the number of rules taking “allow” (“deny,” respec- Fig. 7. Example of position indicators for a rule.
tively) action.
. First-match-overrides. This strategy states that the first third action constraint. We can easily observe that all action
matched rule takes precedence over others. This constraints cannot be satisfied simultaneously by any
strategy can be directly converted to the existing permutation of conflicting rules in this scenario.
firewall implementation.
A naive way to find an optimal solution is to exhaus. High-authority-overrides. This strategy states that a tively search all permutations of correlated conflicting
rule defined by an administrator with a higher rules. We then compute a resolving score for each
authority level takes precedence.
permutation by counting how many action constraints can
Since some strategies are nondeterministic and adopting be satisfied, and select the permutation with the maximum
only one strategy may not guarantee solving the conflict, it resolving score as the best solution for a conflict resolution.
is desirable to combine multiple strategies together to fulfil However, a key limitation of using the permutation
the requirements of conflict resolution posed by a policy. algorithm is its computational complexity which is Oðn!Þ.
Our previous work in [20], [21] proposed a strategy chain to Even though the search space can be significantly reduced
address this issue and we incorporate such a strategy chain by applying our correlation scheme, the number of
in our firewall conflict resolution mechanism. Once each correlated conflicting rules may still be large, leading to
conflicting segment has been assigned to appropriate the permutation algorithm unapplicable. Since the permuconflict resolution strategies, action constraints can be tation algorithm is time intensive and can be only used to
generated based on the assignedhttp://ieeexploreprojects.blogspot.com
strategies. Table 2 identify an optimal reordering for a small set of correlated
summarizes the constraint generation from those strategies. conflicting rules, an approximation algorithm is more
desirable. Although approximation algorithms can only
find a near-optimal solution, they are more efficient in
4.2.2 Rule Reordering
The most ideal solution for conflict resolution is that all finding a solution comparing to the permutation algorithm.
action constraints for conflicting segments can be satisfied To address this issue, we introduce a greedy algorithm,
by reordering conflicting rules. In other words, if we can which can be employed to resolve the conflicts containing a
find out conflicting rules in order that satisfies all action larger number of correlated conflicting rules.
A greedy algorithm makes the locally optimal choice at
constraints, this order must be the optimal solution for the
each
stage with the hope of finding the global optimum. For
conflict resolution. Unfortunately, in practice action conall
conflicting
rules in a correlation group, our greedy
straints for conflicting segments can only be satisfied
conflicting resolution algorithm first calculates a resolving
partially in some cases.
Fig. 6 illustrates a scenario representing that action score for each conflicting rule individually. Then, the rule
constraints cannot be fully satisfied. In this scenario, four with the greatest resolving score is selected to solve the
rules intersect with each other in different conflicting conflicts: a position range with the best conflict resolution is
segments. The existing order of rules cannot satisfy the identified for the selected rule; and moving the selected rule
fourth action constraint. In order to make the fourth action to the new position achieves a locally optimal conflicting
constraint satisfied, r4 needs to be moved in front of r1 . resolution. Applying the same processes to the remaining
However, this situation causes the violation against the rules recursively until all rules in the correlation group are
processed, the final order of the correlated conflicting rules
is a solution of the conflict resolution. Note that the
resolving scores for the remainder of rules should be
recalculated, since moving a rule may change the original
conflicting situation of a policy.
In our greedy algorithm, a critical process is to calculate
the resolving score for each conflicting rule within a conflict
correlation group. This process contains four steps as follows:
1.

Fig. 6. Partial satisfaction of action constraints.

Generating position indicators for each conflicting segment. A position indicator of a rule for a conflicting
segment indicates a position range in which this rule
can stay so that the action constraint of the conflicting
segment is satisfied. Fig. 7 gives an example, which

HU ET AL.: DETECTING AND RESOLVING FIREWALL POLICY ANOMALIES

325

demonstrates the generation of position indicators for
a rule r8 . The rule r8 in this example involves in four
conflicts. In order to fulfill the action constraint of the
first conflicting segment (cs1 ), r8 should stay after r2 .
Thus, a position indicator (pi1 ) can be generated as:
P ositionðr8 Þ > 2. To satisfy the action constraint of
the second conflicting segment, r8 needs to be moved
in front of r5 . Another position indicator (pi2 ) is
generated as: P ositionðr8 Þ  5.
2. Generating position ranges. Based on the position
indicators generated for a rule, we sort the range
bounds in an ascending order, and then employ a
plane sweeping technique [22] to obtain the disjoint
position ranges (pr) for the rule. Using the same
example in Fig. 7, two position indicators pi1 and pi2 Fig. 8. Example of property assignment.
can identify three ranges for the selected rule:
pr1 : ½1; 2, pr2 : ½2; 5, and pr3 : ½5; 8.
on the original packet space of an associated policy. Strong
3. Calculating a resolving score for each position range. irremovable property means that a rule subspace cannot be
The resolving score of a position range represents removed because the action of corresponding policy
the impact of resolving conflicts when moving the
segment can be decided only by this rule. Weak irremovable
selected rule to this position range. Moving the
property is assigned to a rule subspace when any subspace
selected rule to a position range satisfies some
action constraints, but may also violate some other belonging to the same rule has strong irremovable property.
action constraints. Thus, the resolving score for a That means a rule subspace becomes irremovable due to the
position range with respect to the selected rule can reason that other portions of this rule cannot be removed.
be calculated by subtracting the number of violated Correlated property is assigned to multiple rule subspaces
action constraints from the number of satisfied covered by a policy segment, if the action of this policy
action constraints. For example, if we move r8 to the segment can be determined by any of these rules. We next
range pr1 . The resolving score in this case is equal to introduce three processes to perform the property assign0, since the action constraint of cs1 will be satisfied ments to all of rule subspaces within the segments of a
but the action constraint of cs
firewall policy, considering different categories of policy
2 will be violated in
http://ieeexploreprojects.blogspot.com
such a particular situation.
segments discussed in Section 3.1
4. Choosing the maximum range score as the resolving score
1. Property assignment for the rule subspace covered by a
of selected rule. Since one rule may have multiple
nonoverlapping segment. A nonoverlapping segment
associated position ranges. In order to achieve the
contains only one rule subspace. Thus, this rule
effectiveness of conflict resolution, it is necessary to
subspace is assigned with strong irremovable propmove the rule to a position in the range with the
erty. Other rule subspaces associated with the same
maximum resolving score. Thus, we use the maxrule are assigned with weak irremovable property,
imum resolving score of a position range to
except
for the rule subspaces that already have
represent the resolving score of selected rule.
strong
irremovable
property.
In order to achieve the objective of resolving conflicts
2.
Property
assignment
for rule subspaces covered by a
effectively and efficiently, our conflict resolution mechanism
conflicting
segment.
The
first rule subspace covered
4
adopts a combination algorithm incorporating features
by
the
conflicting
segment
is assigned with strong
from both permutation and greedy algorithms. A threshold
irremovable property. Other rule subspaces in the
N for selecting a suitable rule reordering algorithm to
same segment are assigned with removable property.
resolve a conflict can be predefined in the combination
Meanwhile, other rule subspaces associated with
algorithm. When the number of conflicting rules is less than
the first rule are assigned with weak irremovable
N , the permutation algorithm is utilized for resolving
property except for the rule subspaces with strong
conflicts. Otherwise, the greedy algorithm is applied to
irremovable property.
resolve conflicts.
3. Property assignment for rule subspaces covered by a
nonconflicting overlapping segment. If any rule sub4.3 Redundancy Elimination
space has been assigned with weak irremovable
In this step, every rule subspace covered by a policy
property, other rule subspaces without any irremosegment is assigned with a property. Four property values,
vable property are assigned with removable property.
removable (R), strong irremovable (SI), weak irremovable (WI),
Otherwise, all subspaces within the segment are
and correlated (C), are defined to reflect different characterassigned with correlated property.
istics of each rule subspace. Removable property is used to
Fig. 8 illustrates the result of applying our property
indicate that a rule subspace is removable. In other words,
assignment approach, which performs three property assignremoving such a rule subspace does not make any impact
ment processes in sequence, to a firewall policy with eight
rules. We can easily identify that three rules, r3 , r5 , and r8 , are
4. The pseudocode of conflict resolution algorithm is omitted in this
paper due to the space limitation.
removable rules, where the removable property is assigned to

326

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,

VOL. 9,

NO. 3,

MAY/JUNE 2012

identified, FAME further identifies different kinds of
segments and corresponding correlation groups. In risk
assessment module, Nessus [26] is utilized as a vulnerability
scanner to identify the vulnerabilities within a conflicting
segment. Network address space of each conflicting
segment is fed into Nessus to get the vulnerability
information of a given address space. Nessus produces
the vulnerability information in a “nbe” format. The risk
assessment module utilizes tissynbe script [27] to parse the
Nessus results and store the vulnerability information to a
vulnerability database. A risk calculator retrieves vulnerability
information, such as CVSS base score and asset importance
value, to calculate the risk level of each conflicting segment.

5.2

Implementation of Visualization Interfaces in
FAME
FAME provides two policy viewers to visualize the outputs
Fig. 9. Architecture of FAME.
of policy conflict analysis and policy redundancy analysis.
all subspaces. In addition, by examining the correlated rules Each viewer offers two kinds of visualization interfaces: one
r2 , r4 , and r7 , which contain some subspaces with correlated interface shows an entire snapshot of all anomalies; another
property, r2 and r7 can be identified as redundant rules and interface shows a partial snapshot only containing anomaremoved from the policy. However, if we leverage traditional lies within one correlation group.
Fig. 10 depicts interfaces of FAME conflict viewer. The
redundancy detection method [1], [6], which is limited to
detect pairwise redundancies, to this example, only two grid representation shows accurately how a set of rules
interacts with each other. FAME conflict viewer has the
redundant rules r2 and r7 can be discovered.
ability to show an overview of the entire conflicts as well as
portions of the policy conflicts, that need to be examined in
5 IMPLEMENTATION AND EVALUATION
depth for conflict resolution, based on correlation groups.
Our framework is realized as a proof-of-concept prototype As illustrated in Fig. 10a, all conflicting segments and
http://ieeexploreprojects.blogspot.com
called Firewall Anomaly Management
Environment. Fig. 9 conflict correlation groups are displayed along the horshows a high-level architecture of FAME with two levels. izontal axis at the top of the interface. All conflicting rules
The upper level is the visualization layer, which visualizes are shown along the vertical axis at the left of the interface.
the results of policy anomaly analysis to system admin- Each grid cell represents a rule’s subspace. In our interface,
istrators. Two visualization interfaces, policy conflict viewer the icons for conflicting segments indicate four different
and policy redundancy viewer, are designed to manage states with respect to conflicting resolution. One icon
policy conflicts and redundancies, respectively. The lower represents a conflicting segment with the state of strategy
level of the architecture provides underlying functional- unassigned. Two other icons indicate conflicting segments
ities addressed in our policy anomaly management with the state of strategy assigned with “Allow” action
framework and relevant resources including rule informa- constraint and strategy assigned with “Deny” action
tion, strategy repository, network asset information, and constraint, respectively. The fourth icon indicates a convulnerability information.
flicting segment with the state of conflict unresolved. In
addition, this interface allows an administrator to set the
5.1 Implementation of Anomaly Management
risk level thresholds for automatically assigning strategies.
Framework in FAME
Clicking on a group name box of the interface in Fig. 10a,
FAME was implemented in Java. Based on our policy
another
window as shown in Fig. 10b is displayed with the
anomaly management framework, it consists of six compotargeted
conflicts that an administrator needs to examine
nents: segmentation module, correlation module, risk
assessment module, action constraint generation module, and resolve. In this interface, the number of visible entities
rule reordering module, and property assignment module. is reduced to only display conflicting segments in one
The segmentation module takes firewall policies as an input correlation group and a list of conflicting rules associated
and identifies the packet space segments by partitioning the with this group. This significantly eliminates administrapacket space into disjoint subspaces. FAME utilizes tors’ workloads in resolving conflicts by highlighting
Ordered Binary Decision Diagrams5 to represent firewall conflicts within a group. For resolution strategy selection,
rules and perform various set operations, such as unions the administrator needs to further examine rule information
([), intersections (\), and set differences (n), required by the for selecting suitable strategies for each conflicting segment.
segmentation algorithm. A BDD library called JavaBDD When the administrator clicks the icon of a conflicting
[24], which is based on BuDDy package [25], is employed segment, the detailed information related to the conflict is
by FAME. Once the segmentation of packet space is displayed in a window as shown in Fig. 10c.6
5. BDD has been demonstrated as an efficient data structure to deal with
a variety of network configuration analysis [5], [23].

6. FAME redundancy viewer was also developed in a similar fashion.
We elide the discussion of redundancy viewer in this paper.

HU ET AL.: DETECTING AND RESOLVING FIREWALL POLICY ANOMALIES

327

Fig. 10. Interface of FAME conflict viewer.

5.3 Evaluation of FAME
For FAME evaluation, we utilized a number of firewall
policies and associated information required by our tool
from different resources. Most of them are from campus
networks and some are from major ISPs. Our experiments
were performed on Intel Core 2 Duo CPU 3.00 GHz with
3.25 GB RAM running on Linux kernel 2.6.16.

5.3.2 Evaluation of Conflicting Rule Reordering
Algorithm
We have addressed that permutation and greedy algorithms
can be used for reordering conflicting rules, and our conflict
resolution mechanism utilizes a combination algorithm
incorporating the features of both permutation and greedy
algorithms to achieve a more effective and efficient conflict
resolution. In order to evaluate our proposed method, we
5.3.1 Evaluation of Conflicting Segment Generation and
measured the effectiveness and efficiency of three algoCorrelation
rithms implemented in the rule reordering module of FAME
Table 3 shows the evaluation results
generated by the using two metrics, resolved conflicts (RC) and resolving time.
http://ieeexploreprojects.blogspot.com
segmentation and correlation engine of FAME. The number
Table 4 summarizes our evaluation results. It shows that
of conflicting segments, the number of conflict correlation the permutation algorithm can always achieve an optimal
groups, the number of large conflict correlation groups (the conflict resolution for all policies except policy H. We were
rule number is greater than six) and the number of unable to resolve the conflicts in policy H using the
conflicting rules in the largest correlation group are given permutation algorithm, because there exist a larger size of
in this table, which also contains the execution time conflicting rules in some correlation groups. From Table 3,
required by the segmentation module of FAME for we can notice that the number of the largest group member
identifying conflicting segments (i.e., detecting conflicts), of policy H is eighteen. Also, it shows that the resolving time
as well as the one required by the correlation module of required by the permutation algorithm increases exponenFAME for identifying correlation groups among conflicting tially as the number of conflicting segments increases.
segments. Note that all measurements were based on the Hence, the permutation algorithm is infeasible to the
system time stamps in our experiments.
policies with a large size of conflicting rules, although it
In Table 3, the number of large conflict correlation can achieve an optimal solution.
groups and the number of conflicting rules in the largest
Regarding the greedy algorithm, Table 4 shows that it
correlation group give us the evidences that manual conflict can only achieve a near-optimal conflict resolution for all
resolution for a large size of firewall policies is almost firewall policies. However, as the size of conflicting rules
impossible. Also, we can observe that the segmentation and increases, the time taken by the greedy algorithm increases
correlation processes are efficient enough to handle a larger almost linearly as opposed to an exponential increase in
size of firewall policies, such as policy G and policy H in case of using the permutation algorithm.
the table.
TABLE 3
Segmentation and Correlation Evaluation

TABLE 4
Rule Reordering Algorithm Evaluation

328

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,

VOL. 9,

NO. 3,

MAY/JUNE 2012

Fig. 11. Evaluation of conflict resolution.

For the combination algorithm with the default threshold
(N ¼ 6), the results in Table 4 show that the number of
resolved conflicts by the combination algorithm is greater
than the greedy algorithm and almost equal to the optimal
solution achieved by the permutation algorithm. The
computation time is acceptable for all policies as well.
Therefore, it represents higher efficiency and effectiveness
in conflict resolution.

We evaluated each policy described in Table 3 based on the
risk values caused by corresponding conflicts, considering
four situations: worst case, best case, original policy, and resolved
policy. The security risk value of a policy (p) can be calculated
by aggregating the risk levels of conflicting segments that take
“allow” action to any matched packets as follows:
X
RLðcsi Þ:
ð3Þ
SRðpÞ ¼
csi 2CSðpÞ:isAllowedðÞ

5.3.3 Evaluation of the Effectiveness of Conflict
Note that CS(p) returns all conflicting segments of a
Resolution Approach
policy (p) and the function isAllowed() is used to identify all
Three metrics, resolution rate, risk reduction, and availability conflicting segments taking “allow” actions. From Fig. 11b,
improvement, were adopted to evaluate the quality of we noticed that the security risk values of the conflictconflict-resolved policies generated by our conflict resolu- resolved policies are always reduced, compared to the
tion approach. We adopted average risk
value (from 0.0 to security risk value of the original policies. Our experiments
http://ieeexploreprojects.blogspot.com
10.0) as the risk level of each conflict segment, and fixed showed that FAME could achieve an average 45 percent of
upper and lower thresholds as 8.0 and 2.0, respectively, in risk reduction. We could also notice that the security risk
our experiments.
values of the conflict-resolved policies are very close to the
First, we evaluated the conflict resolution rate of our security risk values of the best case. It further indicates that
strategy-based approach, which is reflected by the number FAME can achieve a higher rate of conflict resolution.
of resolved conflicts (i.e., satisfied action constraints). We
To measure the impact of conflict resolution on network
compared the results of applying our strategy-based availability, we were able to calculate an availability loss (AL)
approach with the results of directly applying the existing value for each policy. Computing the availability loss value
first-match mechanism for conflict resolution. As shown in for a policy only need to consider the conflicting segments of
Fig. 11a, we could observe that directly applying the
the policy whose action constraints are “allow,” but carrying
existing first-match mechanism can only solve an average
out “deny” action to all matched network packets. Suppose
63 percent of conflicts. However, when applying our
strategy-based approach, an average 92 percent of conflicts these conflicting segments can be returned by a function
could be resolved in our experiments. Moreover, for some isForceDenied() and we utilize the equation ð10  RLðcsÞÞ to
small-scale policies, we noticed that FAME was capable of derive the availability value of a conflicting segment cs. The
availability loss value of a policy is calculated as follows:
resolving all policy conflicts.
X
In general, when conflicts in a policy are resolved, the
ALðpÞ ¼
ð10  RLðcsi ÞÞ:
ð4Þ
risk value of the resolved policy should be reduced and the
csi 2CSðpÞ:isF orceDeniedðÞ
availability of protected network should be improved
comparing with the situation prior to conflict resolution.
Evaluation results depicted in Fig. 11c clearly show that
To evaluate the risk reduction and availability improvement the availability loss value for each conflict-resolved policy is
of our conflict resolution approach, we compared the
lower than that of corresponding original policy, which
results of conflict-resolved policies with the original policies
supports our hypothesis that resolving policy conflicts can
as well as the best case and worst case with respect to the
always improve the availability of protected network.
conflict resolution. The best case of a conflict resolution is
achieved when all action constraints assigned to the
conflicting segments can be satisfied. The worst case
considering the security risk is that all packets covered by
conflicting segments are allowed to pass through a firewall.
And the worst case considering the availability is that all
packets covered by conflicting segments assigned with
“allow” action constraints are denied.

5.3.4 Evaluation of the Effectiveness of Redundancy
Removal Approach
We also evaluated our redundancy analysis approach based
on those experimental firewall policies. We conducted the
evaluation of effectiveness by comparing our redundancy
analysis approach with traditional redundancy analysis

HU ET AL.: DETECTING AND RESOLVING FIREWALL POLICY ANOMALIES

Fig. 12. Evaluation of redundancy removal.

approach [1], [6], which can only identify redundancy
relations between two rules. Fig. 12 depicts the results of
our comparison experiments. From Fig. 12, we observed that
FAME could identify an average of 6.5 percent redundant
rules from the whole rules. However, traditional redundancy
analysis approach could only detect an average 3.8 percent of
total rules as redundant rules. Therefore, the enhancement
for redundancy elimination was clearly observed by our
redundancy analysis approach compared to traditional
redundancy analysis approach in our experiments.

329

adjust the thresholds to a lower value to enable the firewall to
fortify the security of the network perimeter. Otherwise, if the
network situation ameliorates, such as fixing significant bugs
or vulnerabilities of the protected network or services, the
thresholds can be tuned to a higher value to improve the
availability and utility of the network services. Moreover, it is
possible to carry out this process in an automated fashion by
teaming up with other network security measures such as
intrusion detection systems. Thus, such a conflict resolution
mechanism can be also considered as an important step
toward adaptive security management in which networks can
be evaluated and legitimately hardened by continuously
monitoring dynamic changes in the network and service
vulnerabilities.

7

RELATED WORK

There exist a number of algorithms and tools designed to
assist system administrators in managing and analyzing
firewall policies. Lumeta [30] and Fang [31] allow user
queries for the purpose of analysis and management of
firewall policies. Essentially, they introduced lightweight
firewall testing tools but could not provide a comprehensive
examination of policy misconfigurations. Gouda et al. [32]
devised a firewall decision diagram (FDD) to support
consistent, complete, and compact firewall policy generation.
Bellovin et al. [33] introduced a distributed firewall model
6 DISCUSSIONS
that supports centralized policy specification. Several other
The main limitation of CVSS is that it treats vulnerabilities approaches presenting policy analysis tools with the goal of
individually without considering attack interdependencies detecting policy anomalies are closely related to our work.
http://ieeexploreprojects.blogspot.com
on target networks. Therefore, it may
be insufficient to Al-Shaer and Hamed [1] designed a tool called Firewall
evaluate overall security of a network configuration run- Policy Advisor to detect pairwise anomalies in firewall rules.
ning multiple services by counting the number of vulner- Yuan et al. [5] presented FIREMAN, a toolkit to check for
abilities or adding up the CVSS scores. Attack graphs can be misconfigurations in firewall policies through static analysis.
used to model causal relationships among vulnerabilities As we discussed previously, our tool, FAME, overcomes the
and capture security interactions within an enterprise limitations of those tools by conducting a complete anomaly
network [28], [29]. There have been some attempts at detection and providing more accurate anomaly diagnosis
calculating quantitative metrics by attack graphs [14]. It is a information. In particular, the key distinction of FAME is its
promising direction to combining CVSS metrics with attack capability to perform an effective conflict resolution, which
graphs to achieve a more fine-grained risk assessment for the has been ruled out in other firwall policy analysis tools.
protected network when performing conflict resolutions in
Hari et al. [34] provided an algorithm for detecting and
firewall policies.
resolving conflicts in a general packet filter. However, they
Our experimental results show that around 92 percent of can only detect a specific correlation conflict, and resolve
conflicts can be resolved by using our FAME tool. There the conflict by adding a resolving filter, which is not
may still exist requirements for a complete conflict resolution, suitable for resolving conflicts identified recently in firewall
especially for some firewalls in protecting crucial networks. policies. Fu et al. [35] examined conflict detection and
We believe our FAME tool can help achieve this challenging resolution issues in IPSec policies, which is not directly
goal. First, FAME provides a grid-based visualization applicable in firewall policy analysis. Also, there exist other
technique to accurately represent conflict diagnostic in- related work to deal with a set of conflict resolution
formation and the detailed information for unresolved strategies for access control including Fundulaki and Marx
conflicts, that are very useful, even for manual conflict [16], Jajodia et al. [17] and Li et al. [19]. These conflict
resolution. Second, FAME resolves conflicts in each conflict resolution mechanisms can be accommodated in our finecorrelation group independently. That means a system grained conflict resolution framework.
administrator can focus on analyzing and resolving conThere are several interfaces that have been developed to
flicts belonging to a conflict correlation group individually. assist users in creating and manipulating security policies.
We may have another way to adjust the thresholds for Expandable Grid is a tool for viewing and authoring access
conflict resolution with respect to the network situation control policies [36]. The representation in Expandable Grids
change based on the risk analysis of entire network protected is a matrix with subjects shown along the rows, resources
by the firewall. When the network situation deteriorates, shown along the columns, and effective accesses for the
such as discovering some severe vulnerabilities within the combinations of subjects and resources in the matrix cells.
protected network or services, the system administrator may The SPARCLE Policy Workbench allows policy authors to

330

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,

VOL. 9,

NO. 3,

MAY/JUNE 2012

[10] A. El-Atawy, K. Ibrahim, H. Hamed, and E. Al-Shaer, “Policy
Segmentation for Intelligent Firewall Testing,” Proc. First Workshop
Secure Network Protocols (NPSec ’05), 2005.
[11] G. Misherghi, L. Yuan, Z. Su, C.-N. Chuah, and H. Chen, “A
General Framework for Benchmarking Firewall Optimization
Techniques,” IEEE Trans. Network and Service Management, vol. 5,
no. 4, pp. 227-238, Dec. 2008.
[12] M. Frigault, L. Wang, A. Singhal, and S. Jajodia, “Measuring
Network Security Using Dynamic Bayesian Network,” Proc.
8 CONCLUDING REMARKS
Fourth ACM Workshop Quality of Protection, 2008.
In this paper, we have proposed a novel anomaly manage- [13] M. Sahinoglu, “Security Meter: A Practical Decision-Tree Model to
Quantify Risk,” IEEE Security and Privacy, vol. 3, no. 3, pp. 18-24,
ment framework that facilitates systematic detection and
May 2005.
resolution of firewall policy anomalies. A rule-based [14] R. Sawilla and X. Ou, “Identifying Critical Attack Assets in
segmentation mechanism and a grid-based representation
Dependency Attack Graphs,” Proc. 13th European Symp. Research in
Computer Security (ESORICS), 2008.
technique were introduced to achieve the goal of effective
and efficient anomaly analysis. In addition, we have [15] P. Mell, K. Scarfone, and S. Romanosky, “A Complete Guide to the
Common Vulnerability Scoring System Version 2.0,” Published by
described a proof-of-concept implementation of our anomFIRST—Forum of Incident Response and Security Teams, June 2007.
aly management environment called FAME and demon- [16] I. Fundulaki and M. Marx, “Specifying Access Control Policies for
strated that our proposed anomaly analysis methodology is
XML Documents with Xpath,” Proc. Ninth ACM Symp. Access
Control Models and Technologies, pp. 61-69, 2004.
practical and helpful for system administrators to enable an
[17] S. Jajodia, P. Samarati, and V.S. Subrahmanian, “A Logical
assurable network management.
Language for Expressing Authorizations,” Proc. IEEE Symp.
Our future work includes usability studies to evaluate
Security and Privacy, pp. 31-42, May 1997.
functionalities and system requirements of our policy [18] T. Moses, “Extensible Access Control Markup Language
visualization approach with subject matter experts. Also,
(XACML), Version 2.0, Oasis Standard,” Internet, http://
docs.oasis-open.org/xacml/2.0/accesscontrol-xacml-2.0-corewe would like to extend our anomaly analysis approach to
spec-os.pdf, 2005.
handle distributed firewalls. Moreover, we would explore
[19] N. Li, Q. Wang, W. Qardaji, E. Bertino, P. Rao, J. Lobo, and D. Lin,
how our anomaly management framework and visualiza“Access Control Policy Combining: Theory Meets Practice,” Proc.
tion approach can be applied to other types of access
14th ACM Symp. Access Control Models and Technologies, pp. 135144, 2009.
control policies.
[20] J. Jin, G. Ahn, H. Hu, M. Covington, and X. Zhang, “PatientCentric Authorization Framework for Sharing Electronic Health
Records,” Proc. 14th ACM Symp. Access Control Models and
ACKNOWLEDGMENTS
Technologies, pp. 125-134, 2009.
This work was partially supported by
the grants from the [21] J. Jin, G. Ahn, H. Hu, M. Covington, and X. Zhang, “Patienthttp://ieeexploreprojects.blogspot.com
Centric Authorization Framework for Electronic Healthcare
US National Science Foundation (NSF-IIS-0900970 and
Services,” Computers and Security, vol. 30, no. 2, pp. 116-127, 2011.
NSF-CNS-0831360) and US Department of Energy (DOE)
[22] J. Bentley and T. Ottmann, “Algorithms for Reporting and
(DE-SC0004308). All correspondence should be addressed
Counting Geometric Intersections,” IEEE Trans. Computers,
vol. 28, no. 9, 1979.
to: Dr. Gail-Joon Ahn, ASU, PO Box 878809, Tempe,
[23] E. Al-Shaer, W. Marrero, A. El-Atawy, and K. ElBadawi,
Arizona 85287.
“Network Configuration in a Box: Towards End-to-End Verification of Network Reachability and Security,” Proc. Int’l Conf.
Network Protocols (ICNP ’09), pp. 123-132, 2009.
REFERENCES
[24] “Java BDD,” http://javabdd.sourceforge.net, 2012.
[1] E. Al-Shaer and H. Hamed, “Discovery of Policy Anomalies in
[25] “Buddy Version 2.4,” http://sourceforge.net/projects/buddy,
Distributed Firewalls,” IEEE INFOCOM ’04, vol. 4, pp. 2605-2616,
2012.
2004.
[26] “TENABLE Network Security,” http://www.nessus.org/nessus,
[2] A. Wool, “Trends in Firewall Configuration Errors: Measuring the
2012.
Holes in Swiss Cheese,” IEEE Internet Computing, vol. 14, no. 4, [27] “Tissynbe.py,” http://www.tssci-security.com/projects/
pp. 58-65, July/Aug. 2010.
tissynbe_py, 2012.
[3] J. Alfaro, N. Boulahia-Cuppens, and F. Cuppens, “Complete
[28] K. Ingols, R. Lippmann, and K. Piwowarski, “Practical Attack
Analysis of Configuration Rules to Guarantee Reliable Network
Graph Generation for Network Defense,” Proc. 22nd Ann.
Security Policies,” Int’l J. Information Security, vol. 7, no. 2, pp. 103Computer Security Applications Conf. (ACSAC), 2006.
122, 2008.
[29] X. Ou, W. Boyer, and M. McQueen, “A Scalable Approach to
[4] F. Baboescu and G. Varghese, “Fast and Scalable Conflict
Attack Graph Generation,” Proc. 13th ACM Conf. Computer and
Detection for Packet Classifiers,” Computer Networks, vol. 42,
Comm. Security, pp. 336-345, 2006.
no. 6, pp. 717-735, 2003.
[30] A. Wool, “Architecting the Lumeta Firewall Analyzer,” Proc. 10th
[5] L. Yuan, H. Chen, J. Mai, C. Chuah, Z. Su, P. Mohapatra, and C.
Conf. USENIX Security Symp., vol. 10, p. 7, 2001.
Davis, “Fireman: A Toolkit for Firewall Modeling and Analysis,”
[31] A. Mayer, A. Wool, and E. Ziskind, “Fang: A Firewall Analysis
Proc. IEEE Symp. Security and Privacy, p. 15, 2006.
Engine,” Proc. IEEE Symp. Security and Privacy, pp. 177-189, 2000.
[6] E. Lupu and M. Sloman, “Conflicts in Policy-Based Distributed
Systems Management,” IEEE Trans. Software Eng., vol. 25, no. 6, [32] M. Gouda and X. Liu, “Firewall Design: Consistency, Completeness, and Compactness,” Proc. 24th Int’l Conf. Distributed Computpp. 852-869, Nov./Dec. 1999.
ing Systems (ICDCS ’04), p. 327, 2004.
[7] I. Herman, G. Melanc¸on, and M. Marshall, “Graph Visualization
and Navigation in Information Visualization: A Survey,” IEEE [33] S. Ioannidis, A. Keromytis, S. Bellovin, and J. Smith, “Implementing a Distributed Firewall,” Proc. Seventh ACM Conf. Computer and
Trans. Visualization and Computer Graphics, vol. 6, no. 1, pp. 24-43,
Comm. Security, p. 199, 2000.
Jan.-Mar. 2000.
[8] H. Hu, G. Ahn, and K. Kulkarni, “Anomaly Discovery and [34] A. Hari, S. Suri, and G. Parulkar, “Detecting and Resolving Packet
Filter Conflicts,” Proc. IEEE INFOCOM, pp. 1203-1212, 2000.
Resolution in Web Access Control Policies,” Proc. 16th ACM Symp.
[35] Z. Fu, S. Wu, H. Huang, K. Loh, F. Gong, I. Baldine, and C. Xu,
Access Control Models and Technologies, pp. 165-174, 2011.
“IPSec/VPN Security Policy: Correctness, Conflict Detection and
[9] L. Yuan, C. Chuah, and P. Mohapatra, “ProgME: Towards
Resolution,” Proc. Int’l Workshop Policies for Distributed Systems and
Programmable Network Measurement,” ACM SIGCOMM ComNetworks (POLICY ’01), pp. 39-56, 2001.
puter Comm. Rev., vol. 37, no. 4, p. 108, 2007.

construct policies in a natural language interface, which are
in turn translated into machine-readable policies [37]. Even
though these tools are useful for authoring access control
policies, they cannot effectively represent the results of
policy analysis for firewalls.

HU ET AL.: DETECTING AND RESOLVING FIREWALL POLICY ANOMALIES

[36] R. Reeder, L. Bauer, L. Cranor, M. Reiter, K. Bacon, K. How, and
H. Strong, “Expandable Grids for Visualizing and Authoring
Computer Security Policies,” Proc. 26th Ann. SIGCHI Conf. Human
Factors in Computing Systems, pp. 1473-1482, 2008.
[37] C. Brodie, C. Karat, and J. Karat, “An Empirical Study of Natural
Language Parsing of Privacy Policy Rules Using the SPARCLE
Policy Workbench,” Proc. Second Symp. Usable Privacy and Security,
pp. 8-19, 2006.
Hongxin Hu is currently working toward the
PhD degree from the School of Computing,
Informatics, and Decision Systems Engineering,
Ira A. Fulton School of Engineering, Arizona
State University, Tempe. He is also a member of
the Security Engineering for Future Computing
Laboratory, Arizona State University. His current
research interests include access control models and mechanisms, security and privacy in
social networks, and security in distributed and
cloud computing, network and system security and secure software
engineering. He is a student member of the IEEE.

331

Ketan Kulkarni received the master’s degree in
computer science from Arizona State University.
He was also a member of the Security Engineering for Future Computing Laboratory, Arizona
State University. He is currently working as a
software engineer at Emerson Network Power.

. For more information on this or any other computing topic,
please visit our Digital Library at www.computer.org/publications/dlib.

Gail-Joon Ahn received the PhD degree in
information technology from George Mason
University, Fairfax, Virginia, in 2000. He is an
associate professor in the School of Computing,
Informatics, and Decision Systems Engineering,
Ira A. Fulton Schools of Engineering and the
director of Security Engineering for Future
Computing Laboratory, Arizona State University.
His research interests include information and
systems security, vulnerability and risk management, access control, and security architecture for distributed systems,
which has been supported by the US National Science Foundation
(NSF), National Security Agency, US Department of Defense, US
Department of Energy (DOE), Bank of America, Hewlett Packard,
Microsoft, and Robert Wood Johnson Foundation. He is the recipient of
the US Department of Energy CAREER Award and the Educator of the
http://ieeexploreprojects.blogspot.com
Year Award from the Federal Information Systems
Security Educators
Association. He was an associate professor at the College of Computing
and Informatics, and the founding director of the Center for Digital
Identity and Cyber Defense Research and Laboratory of Information
Integration, Security, and Privacy, University of North Carolina,
Charlotte. He is a senior member of the IEEE.