# Classifying rules by in-out traffic direction to avoid security policy anomaly.

1. IntroductionThe basic function of a firewall is to screen network communications to prevent unauthorized access to or from a computer network [1]. Firewalls decide whether to deny or allow traffic according to a predefined set of rules. Because firewalls provide fundamental protection for the target network, they play a crucial role in the network traffic management. To cope with increasing attacks and threats for network, most firewalls have a large number of rules. A rule consists of predicates for protocol fields and appropriate action. When all predicates of a rule are matched, firewalls allow or deny the packet based on the action of rules. Firewalls are generally defined by order-sensitive and list-based rule set. Therefore, firewalls find the first rule applied to packets among a set of rules.

As Wool observed [2], most firewalls include various types of configuration errors, because the rule management is a complicated, complex and error-prone tasks for network administrators and system managers. Though firewalls have been improved to handle high speed network traffic and a lot of rules, unnecessary rules may downgrade the performance. If there are rules which have different decisions to the same packet, a minor modification of predicates or orders in a rule set can generate security holes. When new rules are added or existing rules are deleted, unless you carefully consider relationships among the rules, firewalls may deny normal services or permit attack traffic.

Predicates in a rule can be presented by multi-dimensional domain regions. Policy anomalies in a rule set result from the overlap of the domain region among the rules. If no overlap exists in all domain regions of predicates, in other words, if all predicates among the rules are completely disjointed with others, policy anomalies will not happen except wrongly-configured rules. Policy anomalies among the rules occur in both single and multiple devices. Unlike in a single firewall, the overlap of predicates among the rules in distributed firewalls can be normal or abnormal relations according to decision of rules.

With the observation of network traffic and dependency among the rules, we propose a new method to remove policy anomalies in a single firewall and avoid policy anomalies in distributed firewalls. The proposed method classifies rules by in-out traffic as our previous research did [3]. It is similar to our previous research in that the proposed method splits overlapping regions from predicates of rules and generates completely disjointed rules without dependency among the rules. However, instead of comparing rules to find anomaly among firewalls, the proposed method uses the aggressive way which could avoid anomalies by replacing the one's rules with the others. The contributions of this study are as follows:

* We found a new kind of misconfiguration based on communication protocols. When some addresses in a rule set send without receiving or receive without sending traffic under a two-way communication protocol, the network connection cannot be established. We included the way to find and resolve the rules having an asymmetrical communication.

* We reduced the unnecessary cost of rule comparisons to find policy anomalies in firewalls. The proposed method classifies rules of all firewalls into two categories, rules for incoming traffic and rules for outgoing traffic. One firewall's rules for incoming traffic have to be matched the other firewalls' rules for outgoing traffic and vice versa. Therefore, without detecting rule anomalies, we replaced the other firewalls' incoming rules by one firewall's outgoing rules or vice versa.

* We blocked the unnecessary traffic from source devices. The proposed method adopts rules from the other devices. It means that the source devices send the packets as much as the destination devices accept and vice versa.

The remainder of this paper is organized as follows: Chapter 2 briefly outlines related work. Chapter 3 explains anomaly problem in security policy. Chapter 4 describes the proposed method for a single security device. Chapter 5 presents the proposed method for multiple security devices. Chapter 6 presents implemented application and experimental results. In Chapter 7, we summarize our experience.

2. Related Work

A firewall is the network equipment that denies or accepts a packet based on policy. Policy anomalies occur when multiple rules are applied a packet in a single device. In list-based firewalls, since only the first matching rule is applied to the packet, the others are useless. However, policy anomalies in distributed firewall are more complicated than in a single firewall. Both network topologies and data paths should be considered when detecting policy anomalies. There have been many challenges to solving such anomalies and maintaining the configuration integrity of the security policy.

Al-Shaer et al. [4][5][6] analyzed anomalies that can occur in a single firewall or in multiple firewalls. They formalized the relations among the rules and represented the firewall policy by a policy tree. They also devised a state diagram for discovering firewall anomalies. This technique was implemented in a software tool called the Firewall Policy Advisor (FPA). The FPA finds potential problems in legacy firewalls and supports anomaly-free policy editing for insertion, removal, and modification of rules.

Hamed et al. [7] provided the taxonomy of policy anomalies classified into access-list conflicts and map-list conflicts in network security devices. They tried to find policy conflicts in various types of security devices and implemented the Security Policy Advisor (SPA) tool, which used the Ordered Binary Decision Diagram (OBDD) [8] to present and manipulate the policy expressions. The SPA supports automatic discovery of security policy conflicts among firewalls including IPSec devices.

Liu and Gupda [9][10][11] proposed three design principles for a firewall: consistency, which means that the rules are ordered correctly; completeness which means that every packet satisfies at least one rule in the firewall; and compactness which means that the firewall has no redundant rules. They developed the Firewall Decision Diagram (FDD) to implement them. They applied a sequence of five algorithms to FDD to generate, to reduce, and to simplify the target firewall rules for maintaining consistency, compactness, and completeness of the original FDD.

Lu et al. [12] proposed a method of representing the firewall rule table that allows for a comparison of two tables. They compared the similarities between a set of packets that are permitted by the two tables. If the sets of packets are same, the two tables are deemed equivalent. This method can also be used to analyze changes to a rule table and to determine whether desired changes are made correctly by comparing the original rule table and the modified one.

Yuan et al. [13] proposed a system known as the FIREwall Modeling and Analysis (FIREMAN), which applies static analysis techniques to check for misconfigurations or policy anomalies in distributed firewalls as well as in individual firewalls. The FIREMAN discovers the violation of user-specific security policies and inconsistencies among firewall rules. FIREMAN uses the Binary Decision Diagrams (BDDs) that have been used successfully in hardware verification and model checking. The FIREMAN performs symbolic model checking of the firewall configurations for all possible IP packets along all possible data paths. It evaluates the firewall configuration as an entire set that is not just limited to relations between two firewall rules in distributed firewalls.

Alfaro et al proposed the MIsconfiguRAtion manaGer (MIRAGE) [14][15][16], which detects anomalies in a network security policy. They pointed out that some previous research studies were incomplete in their efforts to find all anomalies. They described a set of algorithms to manage policy consistency based on the analysis of relationships between the set of filtering rules. They detected and removed anomalies among rules both in a single device and in multiple devices. In addition, they generated a completely independent rule set that removed correlation among the rules. They compared all rules in firewalls and Intrusion Detection Systems on the network path from the network topology.

Algorithms to find policy anomalies require the high cost because the complexity of comparison among the rules. Pozo et al. [17] proposed the Potential Conflicts Graph (PCG) to diagnose the consistency of the firewall rule set. The PCG isolates all inconsistencies among every pair of rules in an order-independent process and identifies the minimum number of conflicting rules. However, it cannot find all kinds of policy anomalies as they stated. Furthermore, they proposed a diagnostic method to use the Constraint Satisfaction Problem in Artificial Intelligence [18]. Abedin et al. [19] proposed a method to generate a new rule set without anomaly. It simultaneously detects and resolves any anomaly present in the rules by reorder and split operations. Yoon et al. [20] proposed a method to reduce the size of the rule set. The algorithm for the reduction of the rule set finds a group of rules and replaces them with a smaller new group with the same meaning.

Research on policy anomalies mainly finds anomalies based on a set theory. The solution to policy anomalies is to separate or disjoint such rules. Since the separation of rules generates many subsequent rules, it requires the aggregation or the merging of rules. The complexity of this task increases substantially in proportion to the number of rules. The proposed method detects anomalies and generates completely disjointed rules without anomalies. It classifies rules by in-out traffic: rules for incoming traffic and rules for outgoing traffic. Each group has opposite addresses in the source address and the destination address. Since it is unnecessary to compare rules in one group with the other group, the proposed method reduces the number of rules to be compared when finding anomalies among the rules in each firewall. Rule-based packet classification by in-out traffic showed good performance for signature matching an Intrusion Detection System [21].

We devised a unique approach to distributed firewalls. It avoids anomalies by replacing rules with one another among firewalls without anomaly detection. It simply replaces the other firewall's rules with the other firewall's rules that an administrator can trust. If there is no anomaly in each firewall, we can have the rules without anomalies in all distributed firewalls. It also allows as much traffic as the source network and the destination network have to exchange. Therefore, it is a more complete approach in that it blocks the unnecessary traffic from its source. Besides, with the observation of the network protocol and traffic classification, we found a new kind of misconfiguration which had not been found in previous research.

3. Problem of Policy Anomaly

We explain the problem of policy anomaly in a single firewall and among distributed firewalls in this chapter. Policy anomalies occur when one rule has overlapping regions with others in a rule set. In an order-sensitive rules set, when multiple rules are applied to a certain packet, others except the most priority one are abnormal rules. Though all rules are completely disjointed with others, firewalls can have rules which are not relevant to their traffic. Such rules are useless and should thus be removed. We define all kinds of policy anomalies and describe a new anomaly which was found in packet classification by in-out traffic. For the sake of simplicity, we only considered a hierarchical network topology.

3.1 Existing Policy Anomalies

It is very similar to define the terms of policy anomaly [3][4][6][9][10][13]. Based on the previous researches, we explain the types of anomalies in view of set relation. Each rule in firewalls has the form, < predicates > [right arrow] < decision > . < predicates > consists of Boolean expressions over protocol fields, such as source address, destination address, source port number, destination port number, etc. < decision > can be "deny" or "accept". We denote a set of rules by R , i.e., R = {[r.sub.1], [r.sub.2], ... [r.sub.n]}. Let [r.sub.x], [r.sub.y] denote one of the rules respectively and assume that rx has the precedence over [r.sub.y] (x < y). Let [R.sub.C] denote the correlation. We represent the correlation using other terms, such as partial redundancy and partial shadowing because they can be separated into three subsets, as in the following:

[r.sub.x] [R.sub.C] [r.sub.y] = {[r.sub.x] - [r.sub.y]} [universal] {[r.sub.y] - [r.sub.x]} [universal] {[r.sub.y] [intersection] [r.sub.x]} (1)

These three subsets do not have the intersection. Since [r.sub.x] - [r.sub.y] is a subset of [r.sub.x], [r.sub.y] - [r.sub.x] is a subset of [r.sub.y], and [r.sub.y] [intersection] [r.sub.x] is a subset of [r.sub.x] and [r.sub.y] both, [R.sub.C] can be presented by completely disjointed subsets and exactly a matching subset. For the same reason, inclusive relation, [r.sub.x] [subset or equal to] [r.sub.y] or [r.sub.x] [??] [r.sub.y], can be presented with completely disjointed subsets and exactly a matching subset. It means that we can represent all relations only through completely disjointed relations and exactly matching relations if we split them. Therefore, we defined three types of anomalies in a single security device as follows:

Intra-shadowing occurs when any packet which matches the preceding rule [r.sub.x] also matches the subsequent rule [r.sub.y], and [r.sub.x] has a different decision from [r.sub.y].

Intra-redundancy occurs when any packet which matches the preceding rule [r.sub.x] also matches the subsequent rule [r.sub.y], and [r.sub.x] has the same decision with [r.sub.y].

Intra-irrelevance occurs when there is a rule which is irrelevant to the traffic of the device.

Policy anomalies for distributed security devices are more complicated than that in a single security device. To find anomalies among distributed security devices, we have to consider data paths and topologies in the network. We define "zones" as network addresses directly connected to the security device. Let [F.sub.s] denote the security device in source zone and [F.sup.x.sub.s] denote one rule of [F.sub.s]. Let [F.sub.d] denote the security device in destination zone and [F.sup.y.sub.d] denote one rule of [F.sub.d]. We assume that network traffic goes from [F.sub.s] to [F.sub.d]. Unlike a single device, the overlap among rules in multiple firewalls can be normal or abnormal relations depending on their policies. We defined three types of anomalies in multiple security devices as follows:

Inter-shadowing occurs when the source device with a rule [F.sup.x.sub.s] blocks a packet, the destination device with a rule [F.sup.y.sub.d] allows the packet. Since [F.sup.x.sub.s] does not send a packet to [F.sup.y.sub.d], [F.sup.y.sub.d] is unnecessary.

Inter-redundancy occurs when the source device with a rule [F.sup.x.sub.s] blocks a packet, the destination device with a rule [F.sup.y.sub.d] blocks the packet again. Since [F.sup.x.sub.s] does not send a packet to [F.sup.y.sub.d], [F.sup.y.sub.d] is unnecessary.

Inter-spuriousness occurs when the source device with a rule [F.sup.x.sub.s] allows any packet, the destination device with a rule [F.sup.y.sub.d] blocks that packet. Since [F.sup.x.sub.s] sends a packet which is denied by [F.sup.y.sub.d], [F.sup.x.sub.s] is unnecessary.

Inter-redundancy anomaly can be intentionally allowed to enforce the security of a network. For example, a conservative administrator may always block some traffic explicitly out of fear that the upstream firewall may fail. Therefore, though our related works refer to it as an anomaly, it is open to debate whether inter-redundancy anomaly is, in fact, even an anomaly.

3.2 Asymmetry Anomaly

The rules in a firewall generally can be classified by two types as traffic is divided by direction. One type involves the rules for incoming traffic, and the other includes the rules for outgoing traffic. We define them as incoming rules and outgoing rules, respectively. This simple idea greatly reduces the complexity of anomaly detection because we do not need to compare one group with the other group. Also, by classifying them, we can find another misconfiguration. Most network communications require the interactions between hosts or networks. Most of all, when TCP protocol creates a network connection, it requires two-way communication. Therefore, if there is an IP address which only receives or sends a packet in a rule set, it cannot be a normal situation. We define it as an intra-asymmetry anomaly.

Let [R.sub.in] denote a set of incoming rules and [R.sub.out] a set of outgoing rules in rule set R. Also, we denote the set of source addresses and the set of destination addresses used in [R.sub.in] by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively. In the same way, let us denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [R.sub.out]. The asymmetry anomaly occurs in the following situation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Intra-asymmetry occurs when there is a rule which only has a network address for outgoing traffic or for incoming traffic under the protocol of two-way communication.

There are some restrictions in finding an intra-asymmetry anomaly. If the rules do not use a two-way communication, it is unnecessary to find intra-asymmetry anomaly. Also, if there are rules that keep track of currently- established connections in stateful firewalls, such rules do not have the intra-asymmetry because they are used for both incoming traffic and outgoing traffic. Therefore, when parsing the rules, if there is any rule having a connection state in the rule set, we simply skip that rule. The intra-asymmetry anomaly is a new type of misconfiguration which could not be found in previous research.

[FIGURE 1 OMITTED]

3.3 Example of Policy Anomaly

Fig. 1 shows two firewalls deployed in a network. We can find all types of policy anomalies that occur in a single firewall and among multiple firewalls in Fig. 1. The anomalies found in Fig. 1 are listed in Table 1.

[TABLE 1 OMITTED]

For the purpose of simplicity, port numbers are generalized in this example. In [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is partially redundant to [r.sub.1], while [r.sub.3] is completely shadowed with [r.sub.1] x [r.sub.6] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is irrelevant to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] traffic. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] allows receiving packets from IP addresses "2.1.1.1-20", but there is a rule for sending packets to "2.1.1.1-10". Therefore, hosts in "2.1.1.11-20" cannot establish the connection because these rules use TCP. So does [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The asymmetry anomaly can occur partially [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or completely [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] like the others. Among anomalies between two firewalls, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is spurious with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] allows traffic blocked by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is completely redundant with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] because of blocking the same traffic. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is partially shadowed with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] allows traffic blocked by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. A rule with a complete anomaly should be removed from the rule set, while a rule with a partial anomaly requires to be resized to its domain region. We explain how to find all anomalies in the next section.

4. Detecting Anomalies and Rewriting Rules

In this section, we describe a new method not only to find policy anomalies but also to rewrite new rules without anomalies. We classify the rules by in-out traffic to reduce the cost of rule comparisons. If there is a rule not included in two classified groups, the rule has an irrelevance anomaly. To find other anomalies such as shadowing, redundancy, and asymmetry, we devised a bitmap array structure, called the Predicates Bitmap Constructor (PBC). Since correlation and inclusive relation are split by overlapping region and non-overlapping region within a PBC, all the rules have only exactly matching relations or completely disjointed relations. The proposed method uses the PBC to remove all anomalies and rewrite new rules in a firewall.

4.1 PBC (Predicate Bitmap Constructor)

In a firewall, given a set of rules, i.e., R = {[r.sub.1], [r.sub.2], ... [r.sub.n]}, let F = {[f.sub.1], [f.sub.2],...., [f.sub.m]} denote the set of m protocol fields presented in R. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the set of the predicates associated with [f.sub.i] in R. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the set of distinct comparative values extracted from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] used in R in ascending order. We can describe one rule of R, [r.sub.x], such as following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

A predicate used in R can be presented as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [cross product] is an operator used in the predicates ( =, [less than or equal to], [greater than or equal to], etc.). Therefore, Eq. (3) can be described as following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

As seen in Eq. (4), one rule consists of conjunctive predicates of protocol fields. Let dom([f.sub.i]) denote [f.sub.t]'s domain. When f constant values exist, dom([f.sub.i]) can be divided into (2k +1) 's interval regions and constant regions at most. According to predicates' comparative values, domain of protocol field [f.sub.i] can be divided into constant regions and interval regions. That is, dom([f.sub.i]) can be divided into (2k + 1) 's regions, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], such as following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

In Eq. (5), dom([f.sub.i]) can be divided into two subsets, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is constant regions and the same to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which is the set of [f.sub.i]'s comparative values of used in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are interval regions between two constant regions. Based on domain values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is determined. Depending on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we can know that which rules among [r.sub.1], [r.sub.2], ... [r.sub.n] are matched. In one of [f.sub.i]'s domain regions, we denote the domain bitmap to represent the result of each rule in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where n is the number of rules. We denote the set of R's domain bitmap in each region of dom([f.sub.i])by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be pre-computed by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Also, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be obtained by a random value in each interval domain region. Let [alpha] denote one of result bitmaps which shows the result of each rule in R. [alpha] can be obtained from each domain bitmap in corresponding protocol fields' domain region as following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Predicates Bitmap Construct (PBC) is an array data structure holding the result bitmaps according to each domain region of a protocol field [f.sub.i]. We described the structure of the PBC in Fig. 2 and defined the PBC in Definition 1.

Definition 1 (Predicate Bitmap Construct) Given a set of rules R = {[r.sub.1], [r.sub.2], ... [r.sub.n]}, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote a set of distinct comparative values extracted from all predicates of a protocol fields [f.sub.i] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Predicate Bitmap Array for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with k distinct constants is defined as an array of (2k +1) regions. Each PBC has following entries:

* Region identifier (rif): An identifier indicates whether its corresponding region is a constant region or an interval region. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] , is constant, it holds one element of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Otherwise, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], implying that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

* Region domain bitmap (rdb[1..n]): A bitmap stores the pre-computed R's result of its corresponding domain region. In the jth region of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the kth bit of the bitmap is set to 0, i.e., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], if [r.sub.k]'s predicate for [f.sub.i] whose comparative value falls within the region [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] cannot satisfy the predicates for [f.sub.i]. Otherwise, the kth bit is set to 1. i.e., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 2 OMITTED]

4.2 Removing Anomalies

We explain anomaly detection and correction in a rule set using PBCs. In a firewall, incoming rules have external addresses in a source address and internal addresses in a destination address, while outgoing rules have opposite source and destination addresses against incoming rules. If there is a rule not included in two rule groups, an irrelevance anomaly is occurred because the rule is irrelevant to traffic of the device. After classifying rules by in-out traffic, we check the policy integrity in each group, [R.sub.out] and [R.sub.in], respectively. This simple classification reduces the number of rules to be compared in a firewall. Therefore, we create the PBC of each rule group to detect anomalies. For example, there is a rule set which consists of four rules in Table 2. If the firewall having this rule set has 1.1.1.0/24 for its zone address, there are three rules for outgoing traffic ([r.sub.1], [r.sub.2], [r.sub.3]) and one rule for incoming traffic ([r.sub.4]).

We explain how to create the PBC only for the outgoing rules because the other is the same process. Since there is no predicate of source port (SP), three PBCs for a source address (SIP), a destination address (DIP), and a destination port (DP) are created. Algorithm 1 describes how to create PBC for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the interval region between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For PBC for SIP, we extract distinct comparative values from the predicates for source address used in r1, [r.sub.2], and [r.sub.3]. After sorting them in ascending order, we identify constant regions and interval regions between two constant regions as Eq. (5) describes. There are two distinct comparative values, "1.1.1.1" and "1.1.1.4" in [r.sub.1], [r.sub.2], and [r.sub.3]. Since we already know the zone address, the minimum and the maximum addresses of the zone are included. Each rule domain bitmap is set by SetBitmap which returns a bitmap of [R.sub.out] in certain domain regions. In the region of source addresses "1.1.1.1" - "1.1.1.3", since [r.sub.2] and [r.sub.3] except [r.sub.1] are matched, the rule domain bitmap has "011". In order to reduce the array size, the domain regions having the same results are merged. The PBC for DIP and the PBC for DP are created in the same way. Three PBCs in Table 2 are presented in Fig. 3. Since the domain of protocol fields in the PBC are divided by the minimum overlapping region, all rules in the PBC are divided by completely disjointed relations or exactly matching relations without correlations and inclusive relations. We can find which rules apply to which domain regions in domain of the protocol field. When rules share certain domain regions of protocol fields, anomalies occur in a rule set.

Algorithm 1 CreatePBC([f.sub.i], [R.sub.out]) Require: [R.sub.out] = {[r.sub.1], [r.sub.2], ... [r.sub.n]} Ensure: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 1: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 2: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 3: Create PBC having (2k + 1)'s size 4: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 5: for i = 0 to k do 6: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 7: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 8: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 9: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 10: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 11: end if 12: end for Require: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Ensure: NL: linked list of normal rules, AL : linked list of abnormal rules Algorithm 2 ResolveAnomaly([r.sub.x]) 1: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 2: Create m -element of Array, Ardb and VT = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 3: for t = 1 to m do 4: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 5: rbmap [??] rbmap & Ardb[t] 6: end for 7: if GetHighestNonzeroPosition( rbmap) = x then 8: InsertList( NL,VT, rbmap) 9: else 10: InsertList( AL,VT, rbmap) 11: end if

Algorithm 2 shows the process of anomaly detection and the correction of each rule. We search the rule domain bitmap in each PBC with comparative values of corresponding predicates and do & (AND) operation on them as Eq. (6) indicates. In the algorithm, GetHighestNonzeroPosition returns the position of the highest non-zero bit in the result bitmap. If the position of the highest non-zero bit in result bitmap of [r.sub.x] is x , [r.sub.x] is the first rule to be applied to the domain region. Otherwise, the preceding rule is applied in the domain region because of the priority among the rules. When finding the first rule to be applied to that domain region of [r.sub.x], we split [r.sub.x] into a normal domain region and an abnormal domain region. We merge two domain regions when result bitmaps are the same; all domain regions of protocol fields except one are the same, and the exceptional one is consecutive to the other.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

Table 2. Each row in the table, which was split from the original rule, can be a rule. [r.sub.1] Is excluded because it is the highest priority rule. Since the first matched rule is applied, subsequent rules are anomalies. In case of [r.sub.2], we can get two split rules without anomalies and overlaps. In case of [r.sub.3], [r.sub.3] is shadowed by [r.sub.2] in the domain region ([S.sub.1], [D.sub.2], [P.sub.2]) and redundant with [r.sub.1] in the domain region ([S.sub.2], [D.sub.2], [P.sub.2]). Therefore, [r.sub.3] has a complete anomaly because the preceding rules are first applied in all domain regions of [r.sub.3].

The PBC is also used to resolve an asymmetry anomaly. The source addresses for incoming rules must be the same as the destination addresses for outgoing rules and vice versa. Therefore, we compare incoming rules and outgoing rules or vice versa after exchanging the source address and destination address of each group. For the detection of the asymmetry anomaly of incoming rules, we search PBCs for outgoing rules with each rule in incoming rules as described in Algorithm 3. Fig. 4(b) shows how to find the asymmetry anomaly with PBCs for outgoing rules and one rule for incoming rules. We search the PBC with exchanged IP addresses and obtain a combined result bitmap, such as finding a redundancy anomaly and a shadowing anomaly. The asymmetry anomaly occurs when the result bitmap has all "0" bits like ([S.sub.2], [D.sub.3]). The rewriting process for removing the asymmetry anomaly is similar to other anomalies. After finding normal domain regions, we rewrite rules from the original ones.

Algorithm 3 FindAsymmetry([r.sub.x]) Require: [r.sub.x]: a rule in [R.sub.in] 1: CreatePBC(sip, [R.sub.out]) 2: CreatePBC(dip, [R.sub.out]) 3: [p.sub.dip] [??] destination address in [r.sub.x] 4: [p.sub.sip] [??] source address in [r.sub.x] 5: rbmap [??] [PBC.sub.sip][[p.sub.dip]].rdb & [PBC.sub.dip] [[p.sub.sip]].rdb 6: if rbmap = 0 then 7: return true 8: else 9: return false 10: end if

Table 3 shows the final result without anomalies after rule rewriting. Because there is no overlap among the rules, we do not need to keep "accept" rules and "deny" rules at same time. Therefore, we leave only one type of rules having the same decision. Since firewalls have list-base ACLs which have order-sensitive properties, if the blacklisted IP addresses or white-listed IP addresses are in a rule set, these rules are overlapped by subsequent rules. Therefore, subsequent rules have partial redundancy or shadowing with the blacklisted IP addresses or white-listed IP addresses. The proposed method splits them without overlaps, but it generates too many rules. To avoid such a problem, the proposed method allows them. That is, rules having intentional anomalies can be excluded when rules are parsed.

5. Avoiding Anomalies in Distributed Firewalls

Detecting anomalies and rewriting rules for multiple devices is a little more complicated than doing so for a single device, as discussed above. We propose a different approach to solve anomalies in distributed firewalls; namely, we strive to avoid them. The proposed method can be used without removing intra-anomalies. However, for the sake of simplicity, we assumed intra-anomalies of each firewall were removed by adopting our method for intra-anomalies. Therefore, there is no overlap among the rules in each firewall.

We assume that one firewall can have multiple zones, but a zone is allocated to one firewall. Packets are exchanged between the zones. We classify firewalls into two types. One is a gateway firewall which is charged with the entire network traffic between the external network and the internal network. The other is a zone firewall which is charged with the network traffic between its own zone and the other zones or the external zone. Let us denote [z.sub.1], [z.sub.2], ..., [z.sub.n] each zone in the zone firewalls. Also, we denote the set of internal network address by [z.sub.int] and the set of external network address in the gateway firewall by [z.sub.ext]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the set of packets allowed in each zone firewall and [F.sub.gw] be the set of packets allowed in a gateway firewall. To present the direction of packets in each firewall, we denote the set of packets which has [z.sub.j] in their destination address field by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the set of packets which have [z.sub.j] in their source address field by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Network traffic in a zone firewall can be classified by outgoing traffic and incoming traffic, while network traffic in a gateway firewall can be divided by the internal traffic and the external traffic. For example, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which is the traffic heading for [z.sub.j] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], can be outgoing traffic and the external traffic. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which is the traffic heading for [z.sub.i] in [F.sub.gw], can be internal traffic and incoming traffic. The ideal state is that the other firewalls have to permit as many as packets that are accepted by [z.sub.i]. That is, incoming traffic of the zone firewall [z.sub.i] is the same as the other firewalls' traffic heading for [z.sub.i] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

As the same reason, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] outgoing traffic is the same to the other firewalls' traffic started from [z.sub.i] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

The gateway firewall has all the zone firewall's traffic heading for internal and external networks as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

We denote a set of rules in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote a subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] whose source address is [z.sub.i] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote a subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] whose destination address is [z.sub.i]. Eq. (7), (8), and (9) can be represented as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

Algorithm 4 Avoid Anomaly ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) Require: [PROGRAM LISTING NOT REPRODUCIBLE IN ASCII] 1: for j = 1 to n do 2: if i [not equal to] j then 3: for k = 1 to 1... p do 4: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 5: delete [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 6: end if 7: end for 8: for l = 1 to m do 10: if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then 11: insert [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 12: end if 13: end for 14: end if 14: end for

From Eq. (7), (8), and (10), we have two different approaches. One is to replace each firewall's incoming rules with one firewall's rules heading for the corresponding firewall. Therefore, each firewall receives as much traffic as the corresponding firewall sends. The other is to replace each firewall's outgoing rules with one firewall's rules for the traffic starting from the corresponding firewall. Likewise, each firewall sends as much traffic as the corresponding firewall receives. If an administrator ensures the integrity of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] incoming rules, the other firewalls' outgoing rules for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be replaced with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] incoming rules. Therefore, all firewall rules can have the same integrity for such a traffic flow. When [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has m rules, i.e. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], Algorithm 4 describes how to replace one firewall's incoming rules with the other firewalls' outgoing rules. In the algorithm, the proposed method deletes all of the other firewalls' rules whose source address is included in the zone address of a firewall [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] rules into the corresponding firewalls to replace deleted rules. GetZoneAddress() is a function which returns the zone address of parameter. If the algorithm is repeated in all zone firewalls, the proposed method can obtain the consistency among the rules in all zone firewalls because the source zone firewalls send as much traffic as the destination zone firewalls receive. In case of the gateway firewall, from Eq. (9) and (11), it is possible to replace the gateway firewall's rules with each firewall's outgoing rules and incoming rules for the external traffic or vice versa.

[FIGURE 5 OMITTED]

Fig. 5 shows the simple example of the network diagram deployed with three zone firewalls and one gateway firewall. For the sake of simplicity, we generalized port predicates. All rules have "accept" decisions. If an administrator trusts in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] rules for incoming traffic, we call [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a trusted firewall. As the algorithm describes, the administrator simply replaces outgoing rules of the other firewalls for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with incoming rules in[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In this example, the administrator replaces rules of [F.sub.z2], [F.sub.z3], [F.sub.gw] with corresponding rules in [F.sub.z1] (a trusted firewall). For example, if incoming rules in [F.sub.z1] are right, they can be propagated to the other firewalls, (a) is propagated to (b). When the rules in a trusted firewall have different decisions from the rules of the other firewalls, it seems undesirable to replace the "deny" rules of the other firewalls with the "accept" rules of the trusted firewall. However, if all firewalls are in a single administrator's domain and the administrator trusts in the rules of the target firewall, it does not matter to substitute the rules of the trusted firewall for the rules of the other firewalls. By propagating these rules to corresponding firewalls, the other firewalls send or deny packets as the rules of the trusted firewall do.

The proposed method was devised to avoid detection of policy anomalies and comparison of rules and to obtain the consistency among all firewalls. Since the proposed method is based on an administrator's trust in rules, the administrator has to verify the rules before propagating them. Although the administrator trusts the "accept" rules of the target firewall, the administrator may not want to replace the "deny" rules of the other firewall with the "accept" rules of the trusted firewall. We define such a case as an inter-shadowing anomaly because the trusted firewall denies traffic which cannot flow in its zone. Before propagating the rules of target firewall, the administrator has to consider that problem. Trust of the rules includes that there is no policy anomaly in the rules of the trusted firewall. However, if an administrator does not have confidence in the rules of the trusted firewall or if an administrator want to keep the "deny" rules of other firewalls, the administrator can insert the rules of the trusted firewall into other firewall without deleting "deny" rules from other firewalls. In such a case, the rules of other firewalls can deny the traffic which they want to deny but other firewalls may have intra-anomalies, which can be solved by the proposed method for intra-anomalies.

Since there could be some conflicts among rules between two firewalls, some methods have been proposed to detect such anomalies. For that purpose, we also proposed a method to detect and correct policy anomalies among multiple firewalls in our previous paper [3]. After removing policy anomalies among firewalls using such methods, we can adopt the proposed method which replaces the rules of other firewalls with the rules of the trusted firewall.

6. Implementation and Experiments

The proposed method was implemented in a software prototype called the Policy Anomaly Resolver (PAR). The PAR has been coded by [C.sup.++]. The PAR parses rule sets and creates four PBCs, as described above. The PAR can detect overlaps among the rules and rewrite completely disjointed rules without anomalies and overlaps. The size of each PBC for protocol fields depends on the distinct number of comparative values of corresponding predicates. The size of the PBC does not have a great influence on detecting and rewriting performance. However, the overlapping relation among the rules has a great effect on performance. Therefore, the Rule Overlap Count (ROC) was introduced to present how many rules are overlapped. In R = {[r.sub.1], [r.sub.2], ..., [r.sub.n]}, ROC([r.sub.i]) indicates how many rules are overlapped between [r.sub.i] and [r.sub.1], [r.sub.2], ..., [r.sub.i-1]. For example, ROC([r.sub.i]) = 3 indicates that there are three rules having overlaps between [r.sub.i] and [r.sub.i]'s preceding rules.

For the experiments, we used two types of rule sets. One involves four different ACL rules from the internal network switches, which were deployed in one Korean online game company. Table 4 shows the detailed characteristics of three ACL rule sets. "#SIP," "#SP," "#DIP," and "#DP" are the numbers of distinct comparative values used in each predicate of a source address, a source port, a destination address, and a destination port, respectively. "Avg. ROC" is the average of ROC in each rule. "ACL3" has few overlaps among the rules, while "ACL4" has a lot of overlaps among the rules. Since the overlap among the rules makes an anomaly, "ACL3" is much better managed compared to "ACL1," "ACL2," and "ACL4." The other one, "SNT" was made from the VRT Certified Rules for Snort, version 2.7. [22]. We classified Snort rules for TCP and grouped them by source address, destination address, source port, destination port, and in-out traffic. Then, we chose 150 rules for outgoing traffic which have specific port numbers in the destination port.

Fig. 6 shows the processing time of the PAR on each rule set. The PAR was executed on a personal computer with 1Gbyte memory and a Core 2 2.13GHz CPU. The cost of rule rewriting increased exponentially according to the number of rules. The major factor for the processing time is the average ROC, as shown in Figure 15. On average, in "ACL4," one rule is overlapped with three preceding rules. In addition, "ACL4" has a lot of predicates that have "any" type of predicates in the rule set. That is the reason for the rapid increase of execution time. "ACL1," "ACL2," and "ACL3," which have low ROC values show a linear increase in the cost of rule rewriting. Though "ACL3" has more rules than "ACL2," "ALC3" shows a better execution time than "ACL2" because of the low ROC value.

[FIGURE 6 OMITTED]

[FIGURE 7 OMITTED]

Also, Fig. 7 shows the effect of ROC in "SNT" rules. Keeping the number of rules, we changed the average ROC by replacing rules with other rules having "any" destination port in Snort rules. As ROC increases, the execution time and number of rewritten rules are linearly increase. In Table 5, after executing the PAR with each rule set, we analyzed the result. The PAR searched policy anomalies in each rule set. For example, the poorly-managed rule set, "ACL4," with an average ROC of 2.77, has 34% complete redundancy and 65% partial redundancy of total rules, while the well-managed rule set, "ACL3," with an average ROC of 0.01, has little complete redundancy and partial redundancy.

The PAR not only finds policy anomalies but also it removes them as Table 5 shows. Rules with complete redundancy or shadowing are useless in a rule set. Therefore, they have to be removed from the rule set. Likewise, rules with partial redundancy or shadowing can be rewritten without overlaps. Rewritten rules by the PAR do not have policy anomalies.

7. Conclusions

The policy maintenance is a complex and error-prone task. The policy anomaly problem arises from the overlaps among the rules and results in security holes for attackers. In this paper, classifying rules by the network direction, the proposed method reduced the unnecessary cost of rule comparisons to find policy anomalies. Also, we found a new kind of anomaly which can occur under a two-way communication protocol. The proposed method for a single security device not only removes overlapping relations among the rules, but it also rewrites the rules without the anomalies and overlapping relations. In multiple security devices, we proposed a new way to avoid the anomaly, not to find the anomalies. The proposed method can reduce the overhead to compare rules for finding anomaly and block the unnecessary traffic from the source communication node.

We implemented the proposed method into a window application called the Policy Anomaly Resolver (PAR) and tested it with real rule sets. The PAR converts original rules to non-overlapping and anomaly-free rules without change of original policy. Therefore, it makes tasks for rule management simple and clear. The PAR has disadvantages in the processing overhead for a large scale rules like other methods. Therefore, we are trying to find more efficient method to perform this process.

This work was supported by the MKE (Ministry of Knowledge Economy), Korea, under the ITRC program supervised by the NIPA (National IT Industry Promotion Agency) (NIPA-2009-(C1090-0902-0016)) and the IT R&D program of MKE/KEIT (KI001863, The Development of Active Detection and Response Technology against Botnet). Additionally supported by the National IT Industry Promotion Agency (NIPA) under the program of Software Engineering Technologies Development.

DOI: 10.3837/tiis.2010.08.013

Received February 11, 2010; revised May 7 and July 18, 2010; accepted July 23, 2010; published August 27, 2010

References

[1] Strasberg, Gondek and Rollies, "The Complete Reference Firewalls," MacGrawHill, 2002.

[2] Avishai Wool, "A quantitative study of firewall configuration errors," IEEE Computer, vol.37, no.6, pp.62-67, Jun. 2004.

[3] Sunghyun Kim and Heejo Lee, "Abnormal policy detection and correction using overlapping transition," IEICE Transactions on Information and Systems, vol.E93-D, no.5, pp.1053-1061, 2010.

[4] Ehab S. Al-Shaer and H. Hamed, "Modeling and management of firewall policies," IEEE eTransactions on Network and Service Management, vol.44, no.3, pp.134-141, Apr. 2004.

[5] E. S. Al-Shaer, H. Hamed, R. Boutaba, and M. Hasan, "Conflict classification and analysis of distributed firewall policies," IEEE Journal on Selected Areas in Communications, vol.23, no.10, pp.2069-2084, Oct. 2005.

[6] E. S. Al-Shaer and H. Hamed, "Discovery of policy anomalies in distributed firewalls," inproc. of IEEEINFOCOM, pp. 2605-2616, Mar. 2004.

[7] H. Hamed and E. Al-Shaer, "Taxonomy of conflicts in network security policies," IEEE Communications Magazine, vol.44, pp.134-141, 2006.

[8] R. Bryant, "Graph-Based algorithms for Boolean function manipulation," IEEE Transactions on Computers, vol.35, no.8, pp.677-691, Aug. 1986.

[9] M. G. Gouda and A. X. Liu, "Firewall design: consistency, completeness, and compactness," in proc. of 24th International Conf. on Distributed Computing Systems (ICDCS), 2004.

[10] M. G. Gouda and A. X. Liu, "Structured firewall design," Computer Networks Journal, vol.51, no.4, pp.1106-1120, 2007.

[11] A. X. Liu, and M. G. Gouda, "Diverse firewall design," IEEE Transactions on Parallel and Distributed Systems, vol.19, no.6, pp.1237-1251, 2008.

[12] L. Lu, R. Safavi-Naini, J. Horton and W. Susilo, "Comparing and debugging firewall rule tables," International Journal of Information Security, vol.1, no.4, pp.143-151, 2007.

[13] L. Yuan, H. Chen, J. Mai, C.-N. Chuah, Z. Su, and P. Mohapatra, "FIREMAN: A Toolkit for FIREwall Modeling and Analysis," IEEE Symposium on Security and Privacy, pp.199-213, 2006.

[14] J. G. Alfaro, N. Cuppens-Boulahia, and F. Cuppens, "Complete analysis of configuration rules to guarantee reliable network security policies," International Journal of Information Security, vol.7, no.5, pp.103-122, 2008.

[15] F. Cuppens, N. Cuppens-Boulahia, and J.G. Alfaro, "Detection and removal of firewall misconfiguration," in proc. of 2005 IASTED International Conf. on Communication, Network and Information Security, pp.154-162, 2005.

[16] J.G. Alfaro, F. Cuppens, and N. Cuppens-Boulahia, "Aggregating and deploying network access control policies," in proc. of Third International Conf. on Availability, Reliability and Security, 2007

[17] S. Pozo, R. Ceballos, and R. M. Gasca, "Fast algorithms for consistency-based diagnosis of firewall Rule Sets," in proc. of Second International Conf. on Availability, Reliability and Security, 2006.

[18] S. Pozo, R. Ceballos, and R. M. Gasca, "CSP-based firewall rule set diagnosis using security policies," in proc. of Third International Conf. on Availability, Reliability and Security, 2007.

[19] M. Abedin, S. Nessa, L. Khan, and B. Thuraisingham, "Detection and resolution of anomalies in firewall policy rules," in proc. of 20th Annual IFIP WG 11.3 Working Conf. on Data and Applications Security (DBSec), 2006.

[20] M. Yoon, S. Chen, and Z. Zhang, "Reducing the size of rule set in a Firewall," in Proc. of IEEE International Conf. on Communications, 2007.

[21] Sunghyun Kim and Heejo Lee, "Reducing payload inspection cost using rule classification for fast attack signature matching," IEICE Transactions on Information and Systems, Vol.E92-D, no.10, pp.1971-1978, 2009.

[22] Snort: Open source Network Intrusion Detection System, http://www.snort.org.

Sunghyun Kim and Heejo Lee

Dept. of Computer Science and Engineering, Korea University Seoul, Korea [e-mail: afshkim, heejo@korea.ac.kr]

* Corresponding author: Heejo Lee

Sunghyun Kim received the B.S. degree in Computer Science from Pukyung University, Korea, in 1994, and the M.S. degree in Computer Science from Yonsei University, Korea, in 2006. Currently, he is a Ph.D. candidate in Computer Science and Engineering, Korea University. His research interest includes network security and security policy.

Heejo Lee is an Associate Professor at the Division of Computer and Communication Engineering, Korea University, Seoul, Korea. Before joining Korea University, he was at AhnLab, Inc. as a CTO from 2001 to 2003. From 2000 to 2001, he was a Postdoctorate Researcher at the Department of Computer Science and the security center CERIAS at Purdue University. Dr. Lee received his B.S., M.S., Ph.D. degree in Computer Science and Engineering from POSTECH, Pohang, Korea. Dr. Lee serves as an editor of the Journal of Communications and Networks. He worked on constructing the National CERT in the Philippines (2006) and consulted for the CERTs in Uzbekistan (2007) and Vietnam (2009). He is a visiting professor at CyLab/CMU until December 2010.

Table 2. Example of firewall rules ID SIP SP DIP DP Act. [r.sub.1] 1.1.1.4 * 2.1.1.[1-10] * A [r.sub.2] * * 2.1.1.4 * A [r.sub.3] 1.1.1.[1-4] * 2.1.1.4 80 D [r.sub.4] 2.1.1.[1-20] * 1.1.1.4 * A Table 3. Rewritten rules after removing anomalies ID SIP SP DIP DP Act. [r.sub.1] 1.1.1.4 * 2.1.1.[1-10] * A [r.sub.2] 1.1.1.[1-3] * 2.1.1.4 * A 1.1.1.[5-255] * 2.1.1.4 * A [r.sub.3] Removed [r.sub.4] 2.1.1.1-10 * 1.1.1.4 * A Table 4. Characteristics of rule set Type #Rules #SIP #SP #DIP #DP Avg.ROC ACL1 101 12 9 79 14 1.03 ACL2 278 38 45 95 13 0.95 ACL3 388 191 15 62 21 0.01 ACL4 632 106 23 171 26 2.77 SNT 150 2 12 2 146 0.57 Table 5. Results of rule rewriting # Complete # Partial # Rewritten # Max. Type # Rules Redundancy Redundancy Rules split rules ALC1 101 3 7 251 66 ALC2 278 41 70 439 13 ALC3 388 1 8 395 2 ALC4 632 218 413 1277 381 SNT 150 4 41 220 4

Printer friendly Cite/link Email Feedback | |

Author: | Kim, Sunghyun; Lee, Heejo |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Aug 1, 2010 |

Words: | 8972 |

Previous Article: | Reversible watermarking method using optimal histogram pair shifting based on prediction and sorting. |

Next Article: | Subtree-based XML storage and XPath processing. |

Topics: |