Research On Key Techniques Of Firewall Rule Set

With the rapid development of the Internet, the number of firewall rules is increasing. This usually leads two problems. First, the increasing of the number of rules challenges the performance of the packet classification that has already become a performance bottleneck in firewalls. Second, with the increasing of the number of rules, it is more and more difficult to efficiently manage firewall rules. These two problems can be addressed by four key techniques: packet classification, rule conflict detection, rule conflict resolving and rule deployment. To solve the problems, researchers recently proposed many algorithms, but most of them still have a few drawbacks and need to be improved. Therefore, it is still necessary to do further research on these key techniques of firewall rule set.This dissertation studies the problems coming from the increasing of the number of firewall rules, thoroughly analyzes and summarizes related works on firewall rule set, and proposes new algorithms to improve the performance in some sub-topics. The major contributions of this dissertation are as follows.First, this dissertation proposes a rapid and multi-dimensional algorithm for packet classification based on BSOL (Binary Search On Leaves), which is named MCBF (Multi Cuttings and Bloom Filters). Different from BSOL, MCBF cuts all dimensions at the same time to decompose rule spaces and stores leaf spaces into hash tables; MCBF constructs a Bloom Filter for every hash table and Bloom Filters are stored into embedded SRAM. When classifying a packet, MCBF performs parallel queries on Bloom Filters and decides how to visit hash tables according to the results. Algorithm analysis and the results of simulations show: when classifying a packet, the average number of hash-table lookups of MCBF is 1, which is much smaller than that of BSOL; at the worst case, the number of hash-table lookups of MCBF is O(log(w_max) + 1), which is smaller than that of BSOL in multi-dimensional environment, where w_max is the length, in bits, of the dimension whose length is the longest.Second, this dissertation proposes a new algorithm for detecting rule conflict named DBBV (Double Binary Bit Vectors), which is based on ASBV (Aggregated S Bit Vectors). Similar with ASBV, DBBV employs the divided-and-conquer method and bit vectors. Different from ASBV, DBBV only needs to calculate the intersection of bit vectors once in the course of every dimensional processing, while ASBV needs to compute the union of bit vectors many times. Also, DBBV does not set any restriction on rules, while ASBV limits every field of rules to be a prefix. Algorithm analysis and the results of simulations show that the performance of DBBV is better than that of ASBV.Third, this dissertation proposes a rule conflict resolving algorithm named RCBCM (Resolving Conflicts Based on Cutting Mapping). The algorithm resolves rule conflicts according to the classification of conflicts. It treats two rules as the basic object and sequentially cuts every dimension of the rules with lower priority. Algorithm analysis and the results of simulations show that RCBCM can thoroughly resolve conflicts at the cost of increasing a few rules.Fourth, for rule deployment, this dissertation proposes a rule set comparing algorithm for diverse firewall design named RSCBRI (Rule Sets Comparing Based on Rules Intersection). First, RCBCM is employed in the pre-processing stage of RSCBRI. Then the problem of rule set comparing is transformed into the problem of graph comparing in multi-dimensional space. At last, RSCBRI compares the areas and the color of graphs to decide whether the rule sets are equal or not by employing rules intersection. Algorithm analysis and the results of simulations not only show that the algorithm can find out all discrepancies among rule sets, but also verify that the performance of the algorithm is better than that of the existing algorithm.