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 complex. 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 geometry-based 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 topology-based conflict detection system that computes the topological relationship of the filters to detect the conflicts. Second, we propose a systematic implementation method called BISCAL (a bit-vector-based spatial calculus) to implement the proposed system and remove irrelevant data from the conflict detection computation. We perform a mathematical analysis as well as experimental evaluations and find that the amount of data needed for topology is only one-fourth of that needed for geometry.
The FreeBSD Documentation Project, Ipfw, http://freebsd.org/doc/enUS.ISO88591/books/handbook/firewalls-ipfw.html
A. Wool, “A Quantitative Study of firewall Configuration Errors,” Computer, Vol. 37, No. 6, 2004, pp. 62-67. doi:10.1109/MC.2004.2
H. Hamed and A. I. Shaer, “Taxonomy of Conflicts in Network Security Policies,” IEEE Communications Maga- zine, Vol. 44, No. 3, 2006, pp. 134-141. doi:10.1109/MCOM.2006.1607877
A. Mayer, A. Wool and E. Ziskind, “FANG: A Firewall Analysis Engine,” 2000 IEEE Symposium on Security and Privacy, Oakland, 14-17 May 2000, pp. 177-187.
A. Wool, “Architecting the Lumeta Firewall Analyzer,” Proceedings of the 10th conference on USENIX Security Symposium, Berkeley, August 2001, pp. 85-97.
M. Yoon, S. Chen and Z. Zhang, “Minimizing the Maximum Firewall Rule Set in a Network with Multiple Firewalls,” IEEE Transactions on Computers, Vol. 59, No. 2, 2010, pp. 218-230. doi:10.1109/TC.2009.172
D. Eppstein and S. Muthukrishnan, “Internet Packet Filter Management and Rectangle Geometry,” Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algo- rithms, Washington, 2001, pp. 827-835.
Y. Yin, Y. Katayama and N. Takahashi, “Detection of Conflicts Caused by a Combinations of Filters Based on Spatial Relationships,” The Information Processing Soci- ety of Japan, Vol. 49, 2008, pp. 3121-3135.
Y. Yin, R. S. Bhuvaneswaran, Y. Katayama and N. Ta- kahashi, “Implementation of Packet Filter Configurations Anomaly Detection System with SIERRA,” International Conference on Information and Communication Security, Beijing, 2005, pp. 467-480.
T. Subana, Y. Yin, Y. Tateiwa, Y. Katayama and N. Takahashi, “A Topological Approach to Detect Conflicts in Firewall Policies,” 2009 IEEE International Symposium on Parallel & Distributed Processing, Rome, May 2009.
T. Subana, Y. Yin, Y. Tateiwa, Y. Katayama and N. Ta- kahashi, “BISCAL: A Bit-Vector Based Spatial Calculus for Analyzing the Mis-Configurations in Firewall Poli- cies,” IEICE Technical Report, Vol. 108, No. 409, 2009, pp. 101-106.
E. Al-Shaer and H. Hamed, “Conflict Classification and Analysis of Distributed Firewall Policies,” IEEE Journal on Selected Areas in Communications, Vol. 23, No. 10, 2005, pp. 2069-2084. doi:10.1109/JSAC.2005.854119
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. 22-30.
H. K. Verizon and K. A. Ahmat, “Fast and Scalable Method for Resolving Anomalies in Firewall Policies,” 14th IEEE Global Internet Symposium 2011, Shanghai, 15 April 2011, pp. 839-844.
H. Hu, G. J. Ahn and K. Kulkarni, “FAME: A Firewall Anomaly Management Environment,” 3rd ACM Work- shop on Assurable and Usable Security Configuration, Chicago, October 2010, pp. 17-26.
A. X. Liu and M. G. Goudam, “Complete Redundancy Detection in Firewalls,” Proceeding of 19th Annual IFIP Conference on Data and Applications Security, Storrs, 2005, pp. 196-209.
K. Matsuda, “A Packet Filtering Rules Compression by Decomposing into Matrixes,” in Japanese, The Informa- tion Processing Society of Japan, Vol. 48, No. 10, 2007, pp. 3357-3364.
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, 3-7 April 2006, pp. 305-315.
L. Yuan, J. Mai, Z. Su, H. Chen and P. Mohapatra, “FIREMAN: A Toolkit for Firewall Modeling and Analysis,” Proceeding of 2006 IEEE Symposium on Se- curity and Privacy, Oakland, 21-24 May 2006, pp. 199-213.
B. Zhang, E. AI. Shaer, R. Jagadeesan, J. Riely and C. Pitcher, “Specifications of a High-Level Conflict-Free Firewall Policy Language for Multi-Domain Networks,” Proceedings of the 12th ACM symposium on Access control Models and Technologies, Sophia Antipolis, 20- 22 June 2007, pp. 185-194.
A. Hari, S. Suri and G. Parulkar, “Detecting and Resolv- ing Packet Filter Conflicts,” Proceeding of 19th Annual Joint Conference of the IEEE Computer and Communi- cations Societies, Tel Aviv, 26-30 March 2000, pp. 1203-1212.
F. Baboescu and G. Varghese, “Fast and Scalable Con- flict Detection for Packet Classifiers,” 10th IEEE Inter- national Conference on Network Protocols, Paris, 12-15 November 2002, pp. 270-279. doi:10.1109/ICNP.2002.1181414
N. Takahashi, “A Systolic Sieve Array for Real-Time Packet Classification,” The Information Processing Soci- ety of Japan, Vol. 42, No. 2, 2001, pp. 146-166.
T. Srinivasan, N. Dhanasekar, M. Nivedita, R. Dhivya- krishnan and A. A. Azeezunnisa, “Scalable and Parallel Aggregated Bitvector Packet Classification Using Prefix Computation Model,” Proceedings of the international symposium on Parallel Computing in Electrical Engi- neering, Bialystok, 13-17 September 2006, pp. 139-144.
T. V. Lakshman, “High-Speed Policy Based Packet For- warding Using Efficient Multi-Dimensional Range Matching,” Proceedings of the ACM SIGCOMM’98 Conference on Applications, Technologies, Architectures, and Protocols For Computer Communication, Vancouver, 2-4 September 1998, pp. 203-214.
S. Singh, F. Baboescu, G. Varghese and J. Wang, “Packet Classification Using Multidimensional Cutting,” Proceed- ings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communica- tions, Karsruhe, 7 February 2003, pp. 213-224.
M. Buddhikot, S. Suri and M. Waldvogel, “Space De- composition Techniques for Fast Layer-4 Switching,” Proceedings: Protocols for High-Speed Networks, Salem, August 1999, pp. 25-42.
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. 65-70.
Max J. Egenhofer, “A Formal Definition of Binary Topological Relationships,” 3rd International Conference on Foundations of Data Organization and Algorithms, Vol. 367, 1989, pp. 457-472.