A New Conflict Detection Tree Structure in the Firewall Rule Set

Vũ Duy Nhất, Nguyễn Mạnh Hùng


Firewall is a network security device that uses rules to control incoming and outgoing network traffic. Configuring firewall rules is a very difficult task even for network security experts, especially for complex networks. Mistakes made in the configuration process will cause two damaging effects: (i) affecting the security of the network that needs protection, and (ii) reducing the performance of the firewall device. This article will introduce a Conflict Detection Tree (CDT) structure that effectively detects all conflicts in a firewall rule set. The accuracy and effectiveness of the CDT structure is presented and substantiated in the article. The proposed CDT structure has been implemented and tested with real data.

DOI: 10.32913/rd-ict.vol3.no40.478


Firewall, network security, firewall rules, conflict, security policy.


E. S. Al-Shaer and H. H. Hamed, “Modeling and management of firewall policies,” IEEE Transactions on Network and Service Management, vol. 1, no. 1, pp. 2–10, 2004.

A. Hari, S. Suri, and G. Parulkar, “Detecting and resolving packet filter conflicts,” in Proceedings of the Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM 2000), vol. 3, 2000, pp. 1203–1212.

H. Lu and S. Sahni, “Conflict detection and resolution in two-dimensional prefix router tables,” IEEE/ACM Transactions on Networking, vol. 13, no. 6, pp. 1353–1363, 2005.

A. Kwok and C. K. Poon, “Two-dimensional packet classification and filter conflict resolution in the internet,” Theory of Computing Systems, vol. 44, no. 3, pp. 289–303, 2009.

C. Maindorfer, “Algorithms and data structures for IP lookup, packet classification and conflict detection,” Ph.D. dissertation, University of Freiburg, Germany, 2009.

S. Thanasegaran, Y. Yin, Y. Tateiwa, Y. Katayama, and N. Takahashi, “A topology-based conflict detection system for firewall policies using bit-vector-based spatial calculus,” International Journal of Communications, Network and System Sciences, vol. 4, no. 11, pp. 683–695, 2011.

C.-L. Lee, G.-Y. Lin, and Y.-C. Chen, “An efficient conflict detection algorithm for packet filters,” IEICE Transactions on Information and Systems, vol. 95, no. 2, pp. 472–479, 2012.

C.-Y. Lai and P.-C. Wang, “Fast and complete conflict detection for packet classifiers,” IEEE Systems Journal, vol. 11, no. 2, pp. 1137–1148, 2017.

Vũ Duy Nhất and Nguyễn Mạnh Hùng, “Đề xuất thuật toán phát hiện xung đột giữa các luật hai chiều trong các thiết bị mạng,” in Kỷ yếu Hội thảo Quốc gia lần thứ XIX: Một số vấn đề chọn lọc của Công nghệ Thông tin và Truyền thông, Oct. 2016.

E. 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, 2005.

L. Yuan, H. Chen, J. Mai, C.-N. Chuah, Z. Su, and P. Mohapatra, “Fireman: A toolkit for firewall modeling and analysis,” in IEEE Symposium on Security and Privacy (S&P’06). IEEE, 2006, pp. 15–pp.

M. Abedin, S. Nessa, L. Khan, and B. Thuraisingham, “Detection and resolution of anomalies in firewall policy rules,” in Proceedings of the IFIP Annual Conference on Data and Applications Security and Privacy. Springer, 2006, pp. 15–29.

H. Hu, G.-J. Ahn, and K. Kulkarni, “Detecting and resolving firewall policy anomalies,” IEEE Transactions on Dependable and Secure Computing, vol. 9, no. 3, pp. 318–331, 2012.

T. Abbes, A. Bouhoula, and M. Rusinowitch, “Detection of firewall configuration errors with updatable tree,” International Journal of Information Security, vol. 15, no. 3, pp. 301–317, 2016.

N. B. Neji and A. Bouhoula, “NAF conversion: an efficient solution for the range matching problem in packet filters,” in Proceedings of the 12th International Conference on High Performance Switching and Routing, 2011, pp. 24–29.

Full Text: PDF

Giấp phép số 69/GP-TTĐT cấp ngày 26/12/2014.
Tổng biên tập: Vũ Chí Kiên
Tòa soạn: 110-112, Bà Triệu, Hà Nội; Điện thoại: 04. 37737136; Fax: 04. 37737130; Email: chuyensanbcvt@mic.gov.vn
Ghi rõ nguồn “Tạp chí Công nghệ thông tin và truyền thông” khi phát hành lại thông tin từ website này