Int. J. Communications, Network and System Sciences, 2011, 4, 683695 doi:10.4236/ijcns.2011.411084 Published Online November 2011 (http://www.SciRP.org/journal/ijcns) Copyright © 2011 SciRes. IJCNS A TopologyBased Conflict Detection System for Firewall Policies Using BitVectorBased Spatial Calculus Subana Thanasegaran, Yi Yin, Yuichiro Tateiwa, Yoshiaki Katayama, Naohisa Takahashi Department of C om put er Science and Engineering, Nagoya Institute of Technology, Nagoya, Japan Email: {subana, katayama, tateiwa, naohisa}@moss.elcom.nitech.ac.jp, yi837@hotmail.com Received September 1, 2011; revised Septem b er 30, 2011; accepted October 12, 2011 Abstract Firewalls use packet filtering to either accept or deny packets on the basis of a set of predefined rules called filters. The firewall forms the initial layer of defense and protects the network from unauthorized access. However, maintaining firewall policies is always an error prone task, because the policies are highly com plex. Conflict is a misconfiguration that occurs when a packet matches two or more filters. The occurrence of conflicts in a firewall policy makes the filters either redundant or shadowed, and as a result, the network does not reflect the actual configuration of the firewall policy. Hence, it is necessary to detect conflicts to keep the filters meaningful. Even though geometrybased conflict detection provides an exhaustive method for error classification, when the number of filters and headers increases, the demands on memory and computation time increase. To solve these two issues, we make two main contributions. First, we propose a topol ogybased conflict detection system that computes the topological relationship of the filters to detect the con flicts. Second, we propose a systematic implementation method called BISCAL (a bitvectorbased spatial calculus) to implement the proposed system and remove irrelevant data from the conflict detection computa tion. We perform a mathematical analysis as well as experimental evaluations and find that the amount of data needed for topology is only onefourth of that needed for geometry. Keywords: Packet Filtering, Misconfiguration, Network Security, Spatial Analysis 1. Introduction A firewall protects the network from unauthorized access and provides secure access to the outside world. Packet filtering techniques in a firewall provide an initial level of security and operate on the network layer or the inter net layer. Packet filtering controls the network traffic with a predefined, ordered set of filters called a firewall policy (FP). Every filter f in the FP has a condition and an action. If a filter matches a packet P the filter action is carried out on packet P. The action can be either accept or deny the packet. Many packet filtering schemes such as IPFW or IPFIREWALL in FreeBSD is a first match ing filtering scheme [1]. IPFW is a FreeBSD sponsored firewall software application enables use of sophisticated filtering capabilities. Managing and maintaining firewall policies is an ex tremely complicated job for the network administrator because the policies are constantly subject to modifica tion. For example, while examining 37 firewalls in pro duction enterprise networks, Wool found that all the firewalls were misconfigured and vulnerable [2]. When the network behavior is different from the ac tual configuration of a policy, potential security holes are created. For example, if an IP address is mistaken in an FP, it allows unintended traffic in the network and can cause security holes. A conflict is a type of misconfigu ration that occurs when a packet P matches two or more filters. It is a common misconfiguration in firewalls. Hamed et al. found that there is a high probability of even expert system administrators and network practi tioners creating conflicts [3]. Conflicts render the filters redundant or shadowed, and as a result, the actual con figuration of the firewall policy is not reflected in the network. Various techniques have been developed to manage firewall policies [322]. Among these are firewall analy sis tools [4,5] and techniques that focus on minimizing the firewall rules [6]. Other related works detect conflicts by using geometrical analysis [79]. Yin et al. developed a conflict detection technique based on geometrical analysis, which provides systematic conflict classifica
S. THANASEGARAN ET AL. 684 tion [8]. However, this technique becomes very de manding in terms of memory and computation time when the number of header fields and filters increases. To solve this problem, we have presented a topological approach to detect conflicts [10,11]. In this approach, we introduced a bitvector based spatial calculus named BISCAL and constructed a new conflict detection frame work through BISCAL which analyzes the topological relationship of the filters to detect and classify conflicts. This paper extends and strengthens that framework by describing the design and implementation of the topol ogybased conflict detection system that shows how ef fectively the BISCAL can be adopted for conflict de tection and by presenting quantitative evaluations of the system. In this paper, our main contributions are as fol lows: 1) We have presented a systematic implementation method based on BISCAL to construct a conflict detec tion system that efficiently classifies conflicts by treating with topological relationships between filters effectively, and can remove the irrelevant data from the conflict de tection in the intermediate stage of computation. 2) We have performed comparative studies through mathematical and experimental analysis to show that the topological approach requires much less computation time and storage than geometrical approach in conflict detection. We implement the topological approach using BIS CAL to extract the conflicting filters from the firewall policy. The main advantage of BISCAL is that the opera tions on the filter sets become easier. The rest of the pa per is organized as follows. In Section 2, we discuss re lated works. In Section 3, we explain the firewall policy used in the conflict detection system. Section 4 discusses the spatial relationship of the filters, and Section 5 ex plains the conflict classification in detail. The operators and supporting vectors of BISCAL are explained in Sec tion 6. Section 7 gives an overview of the proposed sys tem and its computational steps. The evaluation and comparative analysis of our approach are discussed in Section 8. And finally, in Section 9, we present the con clusions and discuss future research directions. 2. Related Work Over the past few years, research and analysis of firewall policies has received considerable attention [228]. Al Share et al. proposed an algorithm to detect conflicts caused by one filter on another in a firewall policy on the basis of the relationship between the two filters [12]. This relationship was defined according to their predi cates such that they satisfied the conditions in {⊂ ⊃ =}. However, the problem with this algorithm is that when the corresponding predicates of two filters overlap, the relationship between the two filters cannot be deter mined, because overlapping predicates do not satisfy any of the conditions in{⊂ ⊃ =}. Therefore, the algorithm for detecting conflicts also does not work when overlap ping predicates appear between two filters. V. Capretta et al. proposed a formalization of conflict detection for firewalls. They defined conflict for the rules if and only if the actions of the rules are different [13]. In such conflict detection, redundancy cannot be detected, as the redundant filters have the same action, but our system analyzes the filters with both the same and dif ferent actions, and conflicts are classified in detail. Mayer et al. developed a firewall analysis tool Fang to perform customized queries on a set of filters and to ex tract the filters in a firewall policy [4]. Wool et al. im proved the usability of Fang [5]. These tools and meth ods help administrators to manually verify the correct ness of a firewall policy. Unfortunately, they require a high degree of user expertise to write proper queries and identify the problems in firewall policies. H. G. Verizon et al. proposed a fast and scalable method for resolving the anomalies in firewall policies [14], which can be useful for largescale firewall policies. H. Hu et al. proposed a firewall anomaly management and resolution environment: FAME, and developed a gridbased visualization of the firewall policy [15]. Liu et al. used firewall decision trees to detect and remove the redundant filters [16]. K. Matsuda proposed a model called matrix decomposition to analyze the filters in the firewall policy with a few compression methods [17]. If for some reason, an administrator needs to intentionally embed redundant filters, which will conflict with the other filters in a firewall policy, we will inform the ad ministrator of the presence of conflicts instead of re moving these redundant filters. This also helps the ad ministrators to add, delete, or modify the existing filters according to their own intentions, as we have classified the conflict contents in detail. T. Srinivasan et al. proposed a scalable and parallel packet classification method using an aggregated bit vector [24]. Lakshman et al. proposed highspeed pol icybased packet forwarding using bitlevel parallelism [25]. Both the above methods yield good results by using the bitvector data structure for packet classification schemes. Baboescu et al. proposed a fast and scalable conflict detection technique for packet classifiers using a bitvector. It detects the conflicting pairs, but it does not classify the conflicts explicitly [22]. Our method effi ciently utilizes the bitvector in our conflict detection system through BISCAL and explicitly classifies as er rors and warnings, which helps administrators to recon figure the policies more easily. Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL.685 3. Background An FP consists of an ordered set of m filters, and it is expressed as follows: 01 1 FP :,,,m ff f where if two filters, i and ,0,1and , j ij mij are such that i < j, filter i is placed before in the FP. We follow the first matching filter scheme, and therefore, i has a higher priority than during exe cution. Each filter 0,1 i fi nconsists of n key fields, called predicates 01 1 and an action. The filter , ii in pp p i is expressed as shown below: 01 1 :,, action iii in fpp p The commonly used matching keys in a header are protocol (represented as Pro), source IP (SrcIP), destina tion IP (DesIP), source port (SrcPort), and destination port (DesPort). Each predicate 0,1,0,1 ik pim kn can be represented as an exact value, a prefix, a range value, or a list in many firewall systems. However, in this paper, we use range value for the sake of simplicity and because a filter with predicates in other forms can be easily con verted into one or multiple filters with range values. Each predicate 0,1,0,1 ik pim kn aub is rep resented as ikkik , by using a uniform range value and the value in the kth key field of the packet header, uk. The default filter is the lowest priority filter that denies access to all the packets when no other filter matches the packet. , ik ab ik We represent a filter in the form called internal form, which includes the range values instead of the predicates in n key fields. An internal form filter fi is represented as follows: 00111 1 :,, ,,,action iii iiinin fababa b Assume that the values of the header of packet P are represented as . A packet P matches fi if and 01 1 ,n uu u ,auba only if . An example policy consisting of internal form filters is shown in Table 1, where f5 is the default filter. 00 000 011iiiiinn ubau b 1in 4. Spatial Relationship of Filters According to Max J. Egenhofer, we can classify the spa tial relationships on the basis of the spatial concepts [29]. The three relationships are 1) topological relationships, 2) spatial and strict order relationships, and 3) metric (geo metric) relationships. Here, we focus on geometric and topological relationships and analyze how they differ in terms of conflict detection. Table 1. A sample firewall policy FP1. SrcIP DesIP Action f0 [0,3) [3,7) Accept f1 [0,3) [3,7) Deny f2 [1,5) [1,5) Accept f3 [3,5) [1,3) Deny f4 [5,7) [1,3) Accept f5 [0,232) [0,232) Deny 4.1. Geometric Relationship of Filters Max J. Egenhofer stated that metric relationships are based on parameters such as distance and directions of the objects [29]. Finding the metrics of an object has many applications in the field of telecommunication, medical imaging, robot motion planning, etc. For example, multi dimensional packet classification is viewed as a point location problem in computational geometry. Finding the geometric location of a packet in an ndimensional space is necessary to classify a packet in packet classifi cation techniques [2326]. The ndimensional space is otherwise called as packet space. When the number of key fields in a packet is n, the packet can be represented as a point in ndimensional space or packet space. A filter is represented as a subspace of a packet space, called the filter space FS, which in cludes all the points of the packet that match the filter. The geometric shape of the filters in a twodimensional space is a rectangle, and in an ndimensional space, it is a hy percube or ncube. The sample firewall policy in Table 1 is represented spatially in Figure 1. We perform a spatial decomposition of the ndimen sional space until dividing the filter boundaries reaches its last dimension. The final decomposed space is called a subspace Si. The packet classification techniques in [2326] preserve the subspaces and their locations in the ndimensional space in various data structures to classify the packet in n key fields. In packet classification, the location of a subspace in the ndimensional space is es sential for finding which filter matches which packet. However, conflict detection techniques that find con flicting filters preserve the same data as packet classifi cation techniques [79]. D. Eppstein et al. used orthogonal range searching techniques and proposed techniques for the packet classification problem and the conflict detec tion problem simultaneously [7]. Yin et al. detected the conflicting filters that appear in [8] by dividing the filter space using SIERRA, a systolic filter sieve array used in highspeed packet classifiers [23]. Both the above techniques detect the conflicting filters based on packet classification analysis. However, when Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL. 686 the number of key fields and filters increases, the con ventional methods used in [79] are extremely demand ing in terms of memory and computation time, as they depend on geometrybased packet classification tech niques. As far as conflicts are concerned, rather than us ing packet classification, we should focus on filter classi fication. Therefore, in our paper, we propose to focus only on filter classification and therefore solve the drawbacks of the previous approaches based on the geometrical relationship of the filters. 4.2. Topological Relationship of Filters According to Max J. Egenhofer, topological relationships are a subset of spatial relationships [29]. Topological notations include the concepts of continuity, closure, interior, and boundary, and are defined in terms of neigh borhood relations. Topological equivalence is a crucial criterion when comparing the relationships between ob jects. Topological equivalence does not preserve distances and directions. Topology refers to the way in which the filters are connected to each other. Therefore, filter clas sification can be performed by identifying the topologi cal relationship of the filters, which is the basic require ment for conflict detection. In our approach, as we have discussed earlier, we per form the ndimensional spatial decomposition, and then further analyze the filters in the subspaces to find the topological relationships of the filters. The difference between the number of subspaces required for conflict detection using topology and geometry is explained be low. Geometrybased systems consider all the subspaces for conflict detection, as the location of all the subspace is important for packet classification techniques. In a topologybased system, the location is discarded, and concentrates only on the uniqueness of the subspace. In other words, it only selects the subspaces with different filter sets by removing subspaces with the same filter sets. Therefore, the number of subspaces (the amount of data required for conflict detection) is smaller for topol ogybased systems than for geometrybased systems. For example, in Figure 1, the number of subspaces considered in the geometrical approach is thirteen. In the topological approach, it is five, because there are only five unique subspaces with different filter sets, namely 01 012223 4 ,,,,, ,,, ffffffff. As a result, when the number of filters and key fields increase, the difference in the number of subspaces considered for conflict detection varies drastically between the topo logical and geometrical approaches. Therefore, we can say that identifying only the topological relationships improves the efficiency of the conflict detection system by removing the irrelevant data from the conflict com putation. In this way, we can achieve our target of solv ing the two issues, namely, large memory usage and computation time. We use experiments to verify this in later sections. Conflict detection is performed by finding the topo logical relationship of the filters. There are nine possible topological relations between any two objects, as they appeared in [29]. We have extracted five topological relationships (TR) to identify conflicts between any pair of filters, i and . In other words, TR (fi, fj) = {dis joint, inside, contains, equal, overlap}. The relations are shown in two dimensions in Figure 2, and can be gener alized for higher dimensions. The filter space of a filter f is represented by FS (f). Disjoint: TR , ij f = disjoint when the intersection of the filters spaces is empty or FS FS ij ff, as shown in Figure 2(a). Inside: TR , ij f = inside when fj is completely enclosed by fi or FSFS i f, as shown in Figure 2(b). Contains: Wheni is enclosed by filter , or FS FS i f, then we say that there exists a rela tion TR , ij f = contains between filters fi and fj, as shown in Figure 2(c). Contains is the converse of the inside relation. Equal: TR , ij f = equal when i and are equal, or FS FS ii f, as shown in Figure 2(d). f 0 ,f 1 f 2 f 3 f 4 SrcIP DesIP 2 32 2 32 01 375 1 3 5 f 5 7 S 0 S 1 S 4 S 5 S 8 S 11 S 3 S 7 S 10 S 2 S 6 S 9 S 12 Figure 1. Spatial decomposition of filters of FP1 defined in Table 1. f i f j f i f j f i f j f i f j f i f j (a) (b) (c) (d) (e) Figure 2. Topological Relationships. (a) Disjoint; (b) Inside; (c) Contains; (d) Equal; (e) Overlap. Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL.687 Overlap: When i and do not satisfy any one of the above four relationships, then we can say that TR , ij f = overlap, as shown in Figure 2(e). 5. Classification of Conflicts Conflicts are classified in filter pairs, , ij f, where i < j and filter fj has an error or warning caused by fi. The errors and warnings of the filter fj can be classified ex clusively by the type of topology between fj and fi and the actions of fj and fi as follows. 1) Shadowing error: A filter fj has a shadowing error caused by fi when a) TR (fi, fj) = equal, fi·action ≠ fj·action, b) TR (fi, fj) = inside, fi·action ≠ fj·action. In this case, the filter fj is never executed, as fi prevents fj from matching all the packets. 2) Redundancy error: A filter fj has a redundancy error caused by fi when a) TR (fi, fj) = equal, fi·action = fj·action, b) TR (fi, fj) = inside, fi·action = fj·action. In this case, the filter fj is never executed, as the filter fi prevents fj from matching all the packets that fj can match. The redundant filters in the FP unnecessarily increase the size of the FP, and even removing fj does not change the semantics of FP. 3) Correlation warning: A filter fj has a correlation warning caused by fi when TR (fi, fj) = overlap, fi·action ≠ fj·action. If filter fj has a correlation warning caused by fi, fj is sometimes not executed for the packets that match the filter fi. 4) Generalization warning: A filter fj has a generali zation warning caused by fi when TR (fi, fj) = contains, fi·action ≠ fi·action. The filter fj is executed only when packets arrive that does not satisfy fi. 5) Redundancy warning: A filter fj has a redundancy warning caused by fi when a) TR (fi, fj) = contains, fi·action = fj·action, b) TR (fi, fj) = overlap, fi·action = fj·action The filter fj is sometimes executed, as fi prevents fj from matching some packets that can match fj. However, if a filter fj is disjoint to the other filters, then it does not fall within any of the above conflict classifications. In this case, we refer to it as a neither error nor warning filter. 6. BISCAL BISCAL operates on the filter sets to extract the topo logical relationship of the filters. It treats the filter sets in a bitvector format and uses seven primitive operators to find the topological relationship of the filters and three special vectors called characterization vectors to preserve the intermediate results. The main advantage of BISCAL is that it finds the disjoint filters in the intermediate stage of computation and removes those filters from the con flict computation. This is because a filter that is disjoint in any dimension is always disjoint in n dimensions. 6.1. Data Structure: BitVector An FP which consists of m filters is represented by a bitvector 0 bb 1m, where a bit bi in the bitvector represents the filter fi. If a filter is selected from the FP, then the value of the corresponding bit is 1, and if not, then the value of the bit is 0. For example, let FP0 con sist of 0123 ,, ,, 4 ffff . If filters 134 ,, ff are se lected from FP0, then the bitvector is [01011]. Because this paper focuses on bitvectors, hereinafter we will re fer to a bitvector as simply vector. The main reason for choosing the bitvector representation is that it makes easier to apply logical operations to find the topological relationships between the filters. We introduce a function V2S that transforms the 1 s in the vector to its corre sponding filters. For example, V2S ([11100]) = {f0, f 1, f2}. 6.2. Primitive Operators There are seven primitive operators in BISCAL that compute the topological relationships of the filters. They are explained with example vectors v1 and v2, where v1= [1010] and v2 = [1011]. 1) AND Operator (AND): This operator computes a bitwise AND for a set of vectors. For example, AND ({v1, v2}) = AND ({[1010], [1011]}) = [1010]. 2) CartesianAND Operator (CAND): It computes the Cartesian product of two sets of vectors A and B and then computes the logical AND for the resulting vectors. CAND (A, B) = {AND ((a, b)),  (a, b) ∈ A × B}. 3) OR Operator (OR): This operator computes a bitwise OR for a set of vectors. For example, OR (v1, v2) = OR ({[1010], [1011]}) = [1011]. 4) Counting one Operator (C1): This operator counts the number of 1s in an input vector. For example, C1 (v1) = C1 ([1010]) = 2. 5) NOT Operator (NOT): This operator returns the complement of an input vector. For example, NOT (v1) = NOT ([1010]) = [0101]. 6) Pairfilters Operator (PF): This operator returns a set from two filter sets that contain the possible combi nations of the two filters in each of the input vectors. For example, PF ([1010], [1011]) = {{f0, f2}, {f0, f2}, {f0, f3}, {f2 f3}}. Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL. 688 5 7) Permutation Operator (PO): This operator returns a set from two filter sets in which each filter is a filter selected from each of two input filter sets. For example, PO ({f0}, {f1, f2}) = {{f0, f1}, {f0, f2}}. 6.3. Characterization Vectors Characterization vectors are the vectors that characterize the topological relationship of the filters. There are two types of characterization vectors: 1) vectors characterize ing the topological relationship of the filters in the packet space, called CV and, 2) vectors characterizing the topo logical relationship of the filters projected on each axis of the packet space, called PCV. 6.3.1. Char a ct eri zation Vectors for Filters i n the Packet Spa ce CVs characterize the topological relationship of the fil ters in ndimensional packet space. They consist of the following three kinds of vectors. 1) CoExistence Vectors Set (OVS): OV is a vector in which a bit of the vector is 1 if the corresponding filter coexists with another filter in some subspace of the packet space. OVS is a set of all OVs. For example, in Figure 1, f0, f1 and f2 coexist in S4, therefore the vector representation is, OV = [11100]. 2) Fully Covered Vector (FV): FV is vector in which the value of bi is 1, if fi is fully covered in ndimensional space. For example, in Figure 1, f0, f1 and f3 are fully covered in twodimension and therefore, FV = [11010]. 3) Disjoint Vector (DV): If a filter fi is disjoint from all other filters in ndimensional space, then the value of bit bi is set to 1 in DV. For example, in Figure 1, f4 is a disjoint filter and therefore DV = [00001]. 6.3.2. Char act eri zation Vectors for Projections of Filters on Each Axis of the Pac ket Space PCVs are computed by using the projection of the filters on each axis of the packet space. The 1m is an ordered set of the ith predicates of the filters in FP and the projection of the filters on the ith axis of the packet space corresponding to the ith key, Xi. All the pro jected filters except for the default filter are decomposed in the boundaries specified by their ith predicate. As a result of the decomposition, the axis is divided into mul tiple intervals. Figure 3 shows an example of the spatial division for the projection of the filters in FP1 on the 0th axis corresponding to the 0th key X0 or SrcIP and shows that six intervals, 0 ,, i Xff 0 ,, I ,, , are made by the decomposi tion of 00 5 ff. Each interval has a set of filters, called subdomain filter set, in which ith predicate of the filter is always true within the interval. The subdomain filter sets for all the f 0 f 1 f 3 f 2 f 4 {f 0 ,f 1 }{f 0 ,f 1 ,f 2 }{f 2 }{f 2 ,f 3 }{f 4 } SrcIP ( 0 ) 012345 I 0 I 1 I 2 I 3 I 4 I 5 {} Figure 3. Spatial division for the projection of the filters in FP1 on the 0th key X0 or SrcIP . intervals on the ith axis except the empty sets form a set, named SFSi. Each subdomain filter set is transformed into a vector, and as a result, the SFSi is transformed into a set of vectors, SVSi. If a filter fi exists in a subdomain filter set, the corresponding bit of the vector bi is set to 1. For example, SFS0 = 01 012223 ,,,,, ,,, fffffff 4 and SVS0 = 11000,11100,00100,00110, 00001 for the spatial division for the projection of the filters in FP1 mentioned in the above. PCVi characterizes the topological relationship of the projected filters on the ith axis and consists of the fol lowing three kinds of vectors. 1) POVSi: POVi is a vector in which a bit of the vec tor is 1 if the corresponding projected filter coexists with another projected filter in some interval on the ith axis of the packet space. POVSi is a set of all POVSis. For example, in Figure 3, POVS0 = {[11000], [11100], [00110]}. 2) PFVi: PFVi is vector in which the value of bit bi is 1 if the projection of fi is fully covered on ith axis of the packet space. For example, in Figure 3, the projections of {f0, f1} and {f3} are fully covered and therefore, PFV0 = [11010]. 3) PDVi: If a filter fi is disjoint from all other filters projected on ith axis of the packet space, then the value of bi is set to 1 in PDVi. For example, in Figure 3, f4 is dis joint and therefore PDV0 = [00001]. 7. Implementation of TopologyBased Conflict Detection System 7.1. System Overview The proposed system detects and classifies the conflicts in the given firewall policy, FP, which consists of m fil ters and n key fields. The default filter is the least prior ity filter fm–1 and is not considered for conflict detection Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL. Copyright © 2011 SciRes. IJCNS 689 1m 7.2. PCV Extractor as it always conflicts with the remaining filters. Our sys tem computes the topological relation of each filter pair (fi, fj), where fj is the conflicting filter and fi is the conflict causing filter. It then decides the errors and warnings for fj according to the topological relation based on the con flict classification described in Section 4. The PCV extractors calculate POVSs, PDVs and PFVs by the following steps. STEP 31: POVSi is computed as follows: Initialize POVSi = {Ø}; For all v ∈ SVSi, if C1 (v) > 1, POVSi = POVSi ∪ v; The overview of the proposed system is shown in Figure 4 and consists of a vertical decomposer, spatial divisors, PCV extractors, a CV extractor, and a TR ex tractor. For example, POVS0 = 11000 ,11100 , 00110 for the SVS0 calculated above. STEP 32: PDVi is calculated as follows: PDVi = NOT (OR (POVSi)); The system receives the FP, and follows the procedure given below. For example, when POVS0 is the value calculated above, PDV0 = NOT 11110 00001. STEP 1: The vertical decomposer divides the FP into n sequences. Each sequence includes the ith predicate of the filters in FP and represents projections of the filters in FP on the ith axis of the packet space, , where i is from 0 to n – 1. 0 ,, i Xff STEP 33: In the calculation of PFVi, the nonfully covered filters on the ith axis of the packet space are computed initially and lastly the fully covered filters are computed. The nonfully covered filters are identified in NFi by finding a vector in SVSi with a single 1, because the nonfully covered filters are somehow alone in any subspace. For example, in Figure 3, f2 is a nonfully covered filter, because f2 is alone in I2. In this way, the corresponding bits of nonfully covered filters are made 0, and the fully covered vector PFVi is derived. STEP 2: The spatial divisor makes SFSi by the spatial division of the projection 1m on the ith axis in the way as described in the Section 6.3.2 for each projection where i is from 0 to n – 1. 0 ,, i Xff STEP 3: The PCVi extractor transforms SFSi into SVSi in the way as described in the Section 6.3.2 and calculates PCVi by applying the BISCAL to the vectors in the SVSi where i is from 0 to n – 1. Initialize NFi = {Ø}; For all v ∈ SVSi, if C1 (v) =1, NFi = NFi ∪ v; PFVi = NOT (OR (NFi)); STEP 4: The CV extractor calculate the CVs by com bining the results of PCVs with the BISCAL. For example, in X0, SVS0 = {[11000], [11100], [00100], [00110], [00001]}, as mentioned above, NF0 = {[00100], [00001]}, and PFV0 = NOT ([00101]) = [11010]. STEP 5: The TR extractor calculates the topological relationship among all combinations of two filters in the FP using BISCAL and classifies them into two types of errors, three types of warnings and others (neither errors nor warnings), as explained in Section 5. 7.3. CV Extractor CV Extractor calculates the CVs using the PCVi The computation of the last three steps is taken over by BISCAL. It extracts the topological relationships for all the combinations of two filters from the CVs, and classifies them into five types of conflicts and others (neither error nor warning filters). The last three steps are explained in detail in the following subsections. 0, ,1 in, calculated in the previous subsection. Before the computation of the CVs, we remove the al ready computed disjoint filters from POVSi 0, ,1 in and PFVi . Using this technique, we improve our system efficiency, as unnecessary computations are removed by discarding 0, ,1in Input FP Vertical Decomposer Spatial Divisor CV Extracto r PCV 0 Extracto r TR Extractor . . PCV 0 SFS 0 X 0 (f 0 ….f m1 ) X n1 (f 0… f m1 ) . . PCV n1 CV SFS n1 O utput 1. Shadowing error 2. Redundancy error 3. Generalization warning 4. Correlation warning 5. Redundancy warning 6. Neither error nor warning filters . . . . Spatial Divisor Spatial Divisor PCV i Extracto r SFS i PCV i PCV n1 Extracto r X 0 (f 0 ··· f m–1 ) X n1 (f 0 ··· f m–1 ) Figure 4. System overview of topologybased conflict detection system.
S. THANASEGARAN ET AL. 690 possibilities to make a filter pair with disjoint filters dur ing the computation. We introduce a vector DV , in which the value of a bit of the vector is 1 if the sponding filter is disjoint in an corre simiy one dimension. It is lar to DV because a bit in DV is 1 if the corresponding filter is disjoint on the n dimensional space, but is different from DV in that a bit in might be 0 if the corresponding filter is disjoint on the ndimensional space. The POVSi and PFVi calculated previous subsection are replaced with i OVS DV in the and FV, respectively. Here, a bit becomes “0” if the corre sponding filter is shown to be a disjoint filter in DV , in r to improve the efficiency of the computation. STEP 41: DV, i OVS and FV are calculated as follows. In this step, the disjoint filters are removed orde from For each i = 0 to, = CAN (NOT ), POVS), and NOT (DV’), PFV); is lculate llow whi re i VS and F the possibility of a disjoint filter in the upcoming conflict detection steps. 0i 1 DVPDVPDVPDV n OR ; OV todiscard 1n FV = i OVS AND ( D (DVi i STEP 42: The OVScad according to the foing substeps, ch calculate the intermediate sults, IR, and then finally, the OVS. OVS ; 0 1 IR OVSCAND 1 ; For i = 2 to , repeat i1 For all , if ∪v; STEP ension on it is fulvered in all one dimend th ,OVS 1 n IR AND ii OVS ,OVSC; 1n vIR 43: A v1, OVSOSC1 filter is fully covered in an n dim V ly whenly cosions, an erefore FV is computed as follows: NF n; For all , if ∪v; 1 vIR n v 1NF n C1 , NF 0 n FV 1 FVFV,NF n ANDNOT OR; STEP 44: DV is calculated in the same way as the vectors of onedimension. For example, the CVs for FP1, shown in Table 1, are computed for two dimension (SrcIP, DesIP), as follows: DV OVSNOT OR; VS11000, 11100,00110, FV = [11010] and DV = [00001]. 7.4. TR Extra O ctor ulates the sets of filter pairs, CCTP and CCTPtopology, so that we can obtain the topological relationships for all the filter pairs in the firewall policy The TR Extractor calc from the above sets, and apply the rules for conflict clas sification defined in Section 5. Filter pairs that have the conflict causing topology are defined in CCTP as fol lows: CCTP,TR ,inside,contains,equal, ij ij ff ff overla p. Two filter pairs that have the same topological rela tionship adefined in CCTPtopology in more detail, as follows: re topology CCTP,, topology ij ij ff TRff, where “topology” is one of inside, contains, equal, or overlap. For example: CCTP,, overlapff TRff. overlap ij ij putation of disjoint filters The disjoint filters are computed in the DF as follows: whic 4 Step 52: Compu P ∪ PF (v); For example, the CCTP of FP1 is as follows: Step 51: Com DF = V2S (DV); For example, for FP1, DF = V2S ([00001]) = {f4}, h shows that fFP1. is a disjoint filter of tation of CCTP CCTP ; For each v ∈ OVS, CCTP = CCT OVS11000 ,11100 , 00110, 01 02 1223 CCTP,,,,,, , fffffff . STEP 53: Classification of topology betwn filter pairs Initially, we calculate the fully covered filter pairs and th P 531: Computation of fully covered filter pa SP, where S is a set of al d filter pairs. If f is a fully covered filter in S, and f ( ee , en lastly, each CCTPtopology. STE irs We introduce two sets, S and l fully covered filters in FP, and SP is a set of fully covere j ii < j) is some filter in FP, a filter pair (fi, fj) is in either one of CCTPinside, CCTPcontains, or CCTPequal. The com putational steps for S and SP are as follows: Initialize SP ; S = V2S (FV); for each fk { of S, do FF k = 11 1 f or each v O ; VS, if b k of v is 1, FFk = AND (FFk, v); Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL.691 0 in FF (FFk));} OVS= {[11000], [1 [00110]. Set b k to k; SP = SP ∪PO ({fk}, V2S For example, the SP for FP1 is calculated as follows: S= V2S ([11010]) = {f0, f1, f3} and [11100], [00110]}. Then, FF0 = AND {[11111], [11000], 1100]} = [11000]. Similarly, FF1 and FF3 are calculated as follows: FF1 = AND ([11111], [11000], [11100]) = [11000], FF3 = AND ([11111], [00110]) = Set fk bit to 0 in FFk, and therefore, FF0 = [01000], FF1 = [10000] and FF3 = [00100]. 01 1032 01 32 , ,, ,,, . SP fffff ff ff PO PO PO STEP532: C omputation of CCT Ptopology All the combinations of filter pairs are classified using the values calculated above, according to their topologi ca l relationships. equal CCTP,,, ,SP ij ijij ff ffSff; inside CCTP,,, ,SP ij ijij ff f SfSff ; contain CCTP,,, ,SP ij ijij ff f SfSff; The CCTPoverlap is calculated as follows: CCTPoverlap = CCTP ∩ SP; For example, the SP for FP1 calculated in the STEP 531 leads us to the following two sets: equal0 1 CCTP , f and inside2 3 CCTP , f and overlap021 2 CCTP,, , ff . f Step 54: Conflict Classifica tion By using the sets of filter pairs calculated in the pre vious steps, we can determine the topological relation sh filters fi and fj, and ac ing caused by f0, and a correlation warn in We have evaluated our proposed system using a mathe ith a special case. We have developed e efficiency of the con flict detection system is decided by the number of sub space with a numerical digit. The sub sp times the value of m in to ips TR (fi, fj) between any pair of cording to the rules described in Section 5, any filter fj is classified. For example, the filters in FP1 are classified as fol lows: f1 has a shadowing error caused by f0, f2 has a re dundancy warn g caused by f1, f3 has a shadowing error caused by f2 and f0 and f4 have neither errors nor warnings. 8. Evaluation matical analysis w a prototype of our system in JAVA programming lan guage and then performed an experimental analysis to evaluate the efficiency of the proposed system. 8.1. Mathematical Analysis As we have discussed earlier, th spaces required to find the relationship between the fil ters. The basic difference in geometry and topology is that topology considers only the unique subspaces, whereas geometry considers all the subspaces. Therefore, the computation time and memory requirements for a topologybased approach are less than that of a geome trybased approach. But in general, it is difficult to mathematically analyze the difference between the com putation time and memory requirements in geometry and topologybased approaches. Therefore, we selected an example policy, FPA, which includes a lot of conflicts, with each and every filter is symmetrical to each other, and every filter conflicting with all the other filters. The twodimensional spatial representation of FPA with 3 filters is shown in Figure 5(a) and m + 1 filter is shown in Figure 5(b). In Figure 5(a), for sake of simplicity, we have repre sented each sub aces with the same filter sets (nonunique subspaces) are represented by a single numerical digit. For example, the number zero refers the subspace of filter f0, and the number four represents the subspace with filters {f1, f2}. Firstly, we compare the difference between the number of subspaces in Figure 5(a). The computation of con flicts through topological approach requires only six subspaces, whereas the geometrical approach requires all thirteen subspaces for conflict detection. Likewise, if new filters are added by preserving the symmetrical structure, as shown in Figure 5(b), we derived the dif ference in subspaces required for the topology and ge ometry approaches for Figure 5. When an m + 1th filter is added in FPA, the number of new subspaces increases by four tal and there exists m + 1 number of unique subspaces following the sum of natural number series. Therefore in topological approach, when the m + 1th filter is added, the number of subspaces considered for conflict detec tion is m + 1. However, in the geometrical approach, when the m + 1th filter is added, the total number of sub spaces considered is four times the value of m. We can derive the following equations for the number of sub spaces NSi for both approaches. Topology: 2 S2mm im Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL. Copyright © 2011 SciRes. IJCNS 692 f 0 f 1 f 2 X 0 X 1 0 0 2 1 5 2 1 443 3 11 f 0 f 1 X 0 X 1 f m+ 1 f m .. . (a) (b) Figu and re 5. FPA in two dimensions. (a) 3 filters; (b) m + 1 filters. tional geometrybased approaches [79]. Our experiments were performed on Intel (R) Core (TM) i5 750 @ 2.6 2.67 GHz w00GM RAM g on Winprofession con FPA FPB. ii NS1 NS1mmm. CPU7 GHzith 4. runnindows 7 al. We and Geometry: ducted experiments with two policies, FPA is the policy discussed in the previo 2 2 i S1mm m us subsection, and FPB is a synthetic firewall policy, which is gener ated by adding a large number of filters to a small prac tical firewall. We have developed FPB based on the practical firewall policy being used in our lab. It consists of 99 packet filters of 5 dimensions, with 32bit SrcIP, DesIP addresses, 16bit SrcPort, DesPort numbers, and an 8bit protocol. The synthetic firewall policy (FPB) ranges in size from 100 to 1000. In this paper, like other firewall management techniques [322], we did not con sider the stateful filters for experimental evaluation. The treatment of conflict detection in stateful firewalls is a topic for future work. We conducted three experiments with both FPA and FPB. Exp.1: Comparative performance analysis of topology and geometry [79] using FPA. Exp.2: Evaluation of the system behavior in different scenarios by varying the ratio of wildcards in FPB. Exp.3: Evaluation of and ii NS1 NS4 mm. m We have substituted different values of, and tabu lated the number of subspaces in Table 2. Our mathe m xperimental Analysis y performing a compara tive analysis between the proposed system and conven Numby m atical analysis shows that the number of subspaces for the topology approach is nearly onefourth of the geo metrical approach in twodimensional space. The differ ence between the topology approach and the geometry approach is much larger when the dimension increases. In practical firewall policies, the efficiency of the topol ogy approach is extremely high, because BISCAL re moves the disjoint filters in the intermediate computation itself. We verify these using experiments in the next sec tion. 8.2. Esystem behavior in practical firewall policies by varying the number of filters in FPB. In the three experiments, we h We have evaluated our system b ave measured parame ters such as memory and computation time. Memory is compared by examining the number of subspaces Table 2. Results of mathematical analysis. (NS) required for conflict computation. Computation time is the measure of the program execution time until conflict er of filters Geometry Topolog 2 5 3 5 41 15 1 15 1000 1,998,001 500,500 009801 050 classification. We conducted three experiments, as shown above, and plotted graphs showing the number of filters on the xaxis, and the computation time expressed in seconds and memory expressed in KB and MB on the yaxis. The results of Exp.1 are shown in Figure 6. It is clear from the graph that our proposed topologybased
S. THANASEGARAN ET AL.693 0 20 40 60 80 100 120 140 160 180 y (KB) 51015202530 Mem ro Number of filters TOPOLOGY GEOMETRY Figure 6. Comparison of topology and geometry. system performs better than the geometrical approach. Exp.2 is performed by varying the ratio of the wild cards of the input filters, as shown in Figures 7(a) nd (b). Tsys m behaves with different kinds of polices used in vari y va a his analysis is performed to examine how the te ous environments. We have synthesized various FPs b rying the distribution of wildcards in FPB. We found that the computation time is less when the ratio of wildcards is in two extremes. When the ratio of wildcards is high, most of the filters occupy the ndimensional space. As a result, there are only a few unique subspaces for conflict detection, as most of the subspaces have the same set of filters. When the ratio of wildcards is too low, most of the filters become disjoint to the others, and therefore the number of conflicting subspaces is less. Therefore the memory and computa tion time is less for lower and higher percentages of wildcards. Exp.3 is performed using FPB to examine the system behavior with practical firewall policies. When the num ber of filters is increased, the system requires a reason able computation time and memory when detecting con flicts, as shown in Figures 8(a) and (b). For example, the system takes only 100 seconds to detect and classify the conflicts for m = 500. 9. Conclusions and Future Work Our proposed topologybased conflict detection system detects the conflicts in FP and classifies them efficiently. It performs well as compared to conventional geometri 0.001 0.01 0.1 1 10 100 100 200 300 400 500600 700800 9001000 Memory (MB) Number of filters 10% 30% 50% 70% 90% (a) (b) Figure 7. Performance analysis by changing the ratio of wildcard in FPB. (a) Computation time; (b) Memory. 0.1 1 10 100 1000 100 200 300 400 500600 700 Computation time (s) Number of filters 0.01 0.1 1 10 100 100 200 300 400 500 600 700 Memory ) Number of filters (MB (a) (b) Figure 8. Performance analysis of system using FPB. (a) Computation time; (b) Memory. Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL. 694 cal approaches and efficiently utilizes the two important resources: computation time and memory. Our future research plan focuses on the detection of conflicts caused by combinations of filters in firewall policies and con flict detection in stateful firewalls [28]. 10. Acknowledgements This research was partially supported by JSPS KAKENHI 23500085 and by the Hori Science and Art Foundation. 11. References [1] The FreeBSD http://freebsd Documentation Project, Ipfw, .org/doc/enUS.ISO88591/books/handbook/f irewallsipfw.html [2] A. Wool, “A Quantitative Study of firewall Configuration Errors,” Computer, Vol. 37, No. 6, 2004, pp. 6267. doi:10.1109/MC.2004.2 [3] H. Hamed and A. I. Shaer, “Taxonomy of Conflicts in Network Security Policies,” IEEE Communications Maga . 134141. 607877 zine, Vol. 44, No. 3, 2006, pp doi:10.1109/MCOM.2006.1 itecting the Lumeta Firewall Analyzer,” the 10th conference on USENIX Security Symposium, Berkeley, August 2001, pp. 8597. ransactions on Computers, Vol. 59, [4] A. Mayer, A. Wool and E. Ziskind, “FANG: A Firewall Analysis Engine,” 2000 IEEE Symposium on Security and Privacy, Oakland, 1417 May 2000, pp. 177187. [5] A. Wool, “Arch Proceedings of [6] M. Yoon, S. Chen and Z. Zhang, “Minimizing the Max imum Firewall Rule Set in a Network with Multiple Firewalls,” IEEE T No. 2, 2010, pp. 218230. doi:10.1109/TC.2009.172 [7] D. Eppstein and S. Muthukrishnan, “Internet Packet Fi Management and Rectang lter le Geometry,” Proceedings i, “Detection of of Filters Based on a Security n Firewall Poli Analysis of Distributed Firewall Policies,” IEEE Journal on Selected Areas in Communications, Vol. 23, No. 10, 2005, pp. 20692084. doi:10.1109/JSAC.2005.854119 [13] V. Capretta, B. Stepien, A. Felty and S. Matwin, “Formal Correctness of Conflict Detection for Firewalls,” Pro ceedings of the 2007 ACM Workshop on Formal Methods in Security Engineering, Virginia, November 2007, pp. 2230. [14] H. K. Verizon and K. A. Ahmat, “Fast and Scalable Me thod for Resolving Anomalies in Firewall Policies,” 14th IEEE Global Internet Symposium 2011, Shanghai, 15 April 2011, pp. 839844. lkarni, “FAME: A Firewall vironment,” 3rd ACM Work ity Configuration, Redundancy ,” in Japanese, The Informa A Toolkit for Firewall Modeling and Ana ee , S. Suri and G. Parulkar, “Detecting and Resolv of the 12th Annual ACMSIAM Symposium on Discrete Algo rithms, Washington, 2001, pp. 827835. [8] Y. Yin, Y. Katayama and N. Takahash Conflicts Caused by a Combinations Spatial Relationships,” The Information Processing Soci ety of Japan, Vol. 49, 2008, pp. 31213135. [9] Y. Yin, R. S. Bhuvaneswaran, Y. Katayama and N. T kahashi, “Implementation of Packet Filter Configurations Anomaly Detection System with SIERRA,” International Conference on Information and Communication, Beijing, 2005, pp. 467480. [10] T. Subana, Y. Yin, Y. Tateiwa, Y. Katayama and N. Ta kahashi, “A Topological Approach to Detect Conflicts in Firewall Policies,” 2009 IEEE International Symposium on Parallel & Distributed Processing, Rome, May 2009. [11] T. Subana, Y. Yin, Y. Tateiwa, Y. Katayama and N. Ta kahashi, “BISCAL: A BitVector Based Spatial Calculus for Analyzing the MisConfigurations i cies,” IEICE Technical Report, Vol. 108, No. 409, 2009, pp. 101106. [12] E. AlShaer and H. Hamed, “Conflict Classification and [15] H. Hu, G. J. Ahn and K. Ku Anomaly Management En shop on Assurable and Usable Secur Chicago, October 2010, pp. 1726. [16] A. X. Liu and M. G. Goudam, “Complete Detection in Firewalls,” Proceeding of 19th Annual IFIP Conference on Data and Applications Security, Storrs, 2005, pp. 196209. [17] K. Matsuda, “A Packet Filtering Rules Compression by Decomposing into Matrixes tion Processing Society of Japan, Vol. 48, No. 10, 2007, pp. 33573364. [18] K. Golnabi, R. K. Min, L. Khan, and E. Al. Shaer, “Analysis of Firewall Policy Rules Using Data Mining Techniques,” 10th IEEE/IFIP Network Operations and Management Symposium, Vancouver, 37 April 2006, pp. 305315. [19] L. Yuan, J. Mai, Z. Su, H. Chen and P. Mohapatra, “FIREMAN: lysis,” Proceeding of 2006 IEEE Symposium on Security and Privacy, Oakland, 2124 May 2006, pp. 199213. [20] B. Zhang, E. AI. Shaer, R. Jagadeesan, J. Riely and C. Pitcher, “Specifications of a HighLevel ConflictFr Firewall Policy Language for MultiDomain Networks,” Proceedings of the 12th ACM Symposium on Access con trol Models and Technologies, Sophia Antipolis, 20 22 June 2007, pp. 185194. [21] A. Hari ing Packet Filter Conflicts,” Proceeding of 19th Annual Joint Conference of the IEEE Computer and Communi cations Societies, Tel Aviv, 2630 March 2000, pp. 12031212. [22] F. Baboescu and G. Varghese, “Fast and Scalable Con flict Detection for Packet Classifiers,” 10th IEEE Inter national Conference on Network Protocols, Paris, 1215 November 2002, pp. 270279. doi:10.1109/ICNP.2002.1181414 [23] N. Takahashi, “A Systolic Sieve Array for RealTime Packet Classification,” The Information Processing Soci ety of Japan, Vol. 42, No. 2, 2001, pp. 146166. del,” Proceedings of the international symposium on Parallel Computing in Electrical Engi [24] T. Srinivasan, N. Dhanasekar, M. Nivedita, R. Dhivya krishnan and A. A. Azeezunnisa, “Scalable and Parallel Aggregated Bitvector Packet Classification Using Prefix Computation Mo Copyright © 2011 SciRes. IJCNS
S. THANASEGARAN ET AL.695 ations, Technologies, Architectures, and Pro ed , Binary Topo neering, Bialystok, 1317 September 2006, pp. 139144. [25] T. V. Lakshman, “HighSpeed Policy Based Packet For warding Using Efficient MultiDimensional Range Match ing,” Proceedings of the ACM SIGCOMM’98 Conference on Applic Augu tocols for Computer Communication, Vancouver, 24 September 1998, pp. 203214. [26] S. Singh, F. Baboescu, G. Varghese and J. Wang, “Packet Classification Using Multidimensional Cutting,” Proce ings of the 2003 Confe rence on Applications, Technologies, Architectures, and Protocols for Computer Communica tions, Karsruhe, 7 February 2003, pp. 213224. [27] M. Buddhikot, S. Suri and M. Waldvogel, “Space De composition Techniques for Fast Layer4 Switching,” Proceedings: Protocols for HighSpeed Networks, Salem st 1999, pp. 2542. [28] K. Hida, Y. Katayama and N. Takahashi, “A Filter Re verse Search System for LANs with Stateful Firewalls,” IEICE Technical Report, Vol. 107, No. 483, 2007, pp. 6570. [29] Max J. Egenhofer, “A Formal Definition of logical Relationships,” 3rd International Conference on Foundations of Data Organization and Algorithms, Vol. 367, 1989, pp. 457472. Copyright © 2011 SciRes. IJCNS
