Please wait a minute...
Tsinghua Science and Technology  2019, Vol. 24 Issue (1): 65-76    doi: 10.26599/TST.2018.9010003
FPC: A New Approach to Firewall Policies Compression
Yuzhu Cheng, Weiping Wang*, Jianxin Wang, Haodong Wang
∙ Yuzhu Cheng is with the School of Information Science and Engineering, Central South University, Changsha 410083, and the School of Software, Changsha Social work College, Changsha 410004, China. E-mail:
∙ Weiping Wang and Jianxin Wang are with the School of Information Science and Engineering, Central South University, Changsha 410083, China. E-mail:
∙ Haodong Wang is with the Department of Electrical Engineering and Computer Science, Cleveland State University, Cleveland, OH 44115, USA. E-mail:
Download: PDF (2024 KB)      HTML
Export: BibTeX | EndNote (RIS)       Supporting Info


Firewalls are crucial elements that enhance network security by examining the field values of every packet and deciding whether to accept or discard a packet according to the firewall policies. With the development of networks, the number of rules in firewalls has rapidly increased, consequently degrading network performance. In addition, because most real-life firewalls have been plagued with policy conflicts, malicious traffics can be allowed or legitimate traffics can be blocked. Moreover, because of the complexity of the firewall policies, it is very important to reduce the number of rules in a firewall while keeping the rule semantics unchanged and the target firewall rules conflict-free. In this study, we make three major contributions. First, we present a new approach in which a geometric model, multidimensional rectilinear polygon, is constructed for the firewall rules compression problem. Second, we propose a new scheme, Firewall Policies Compression (FPC), to compress the multidimensional firewall rules based on this geometric model. Third, we conducted extensive experiments to evaluate the performance of the proposed method. The experimental results demonstrate that the FPC method outperforms the existing approaches, in terms of compression ratio and efficiency while maintaining conflict-free firewall rules.

Key wordsfirewall      firewall policy      network security      firewall rules compression     
Received: 13 July 2017      Published: 29 April 2019
Corresponding Authors: Weiping Wang   
About author:

Haodong Wang is an associate professor in the Department of Electrical Engineering and Computer Science at Cleveland State University. He received the PhD degree in computer science from College of William and Mary. His research interests focus on information assurance in cyber-physical systems, privacy preserving and user access control in sensor networks, efficient information storage, search and retrieval in pervasive computing, and mobile system security and computing.

Cite this article:

Yuzhu Cheng, Weiping Wang, Jianxin Wang, Haodong Wang. FPC: A New Approach to Firewall Policies Compression. Tsinghua Science and Technology, 2019, 24(1): 65-76.

URL:     OR

r𝟏:F𝟏[1, 2]Λ F𝟐[4, 7] accept, r𝟐: F𝟏[3, 4]ΛF𝟐[2, 8]accept,?and r𝟑: F𝟏[5, 7]Λ F𝟐[4, 7] accept.">
Fig. 1 A compressing example, r𝟏:F𝟏[1, 2]Λ F𝟐[4, 7] accept, r𝟐: F𝟏[3, 4]ΛF𝟐[2, 8]accept,?and r𝟑: F𝟏[5, 7]Λ F𝟐[4, 7] accept.
Fig. 2 Rectangular covers of a rectilinear polygon. (a) Non-overlapping cover (size = 3) and (b) overlapping cover (size = 2).
FDMFirewall design matrix model
MOCMinimal overlapping cover
MNCMinimal non-overlapping cover
Fii-th dimension
D?(Fi)Domain of Fi
MkA k-dimensional matrix
u,vUnit space
R(u,v,Fi)Spatial relation between u and v in Fi
ciGrid cell
LkLinked list
Table 1 Notations used in this paper.
r1– r4.">
Fig. 3 An intuitive example of mapping and the corresponding grid cells, r1– r4.
Fig. 4 Spational relation between two unit spaces u and v in dimension F1.
Fig. 5 An example of rectangle covering process.
Fig. 6 An example of firewall f with five rules.
Fig. 7 An intuitive example of cutting unit spaces into grid cells.
F𝟏 and Dim F𝟐, respectively.">
Fig. 8 An example of digraph for the spatial relations of the grid cells in Dim F𝟏 and Dim F𝟐, respectively.
c𝟏, c𝟐, c𝟑, and c𝟒 with c𝟏 as the initial grid cells; (b) Remove the convex grid cells c𝟏, c𝟐, and c𝟓; (c) To cover c𝟑, c𝟒, c𝟔, and c𝟕 with c𝟑 as the initial grid cells; and (d) Remove all the convex grid cells.">
Fig. 9 An example of rectilinear polygon covering in the two-dimensional space. (a) To cover c𝟏, c𝟐, c𝟑, and c𝟒 with c𝟏 as the initial grid cells; (b) Remove the convex grid cells c𝟏, c𝟐, and c𝟓; (c) To cover c𝟑, c𝟒, c𝟔, and c𝟕 with c𝟑 as the initial grid cells; and (d) Remove all the convex grid cells.
Fig. 10 Performance comparison of FDM, Diplomat, and FPC.
Rules setFDM (%)Diplomat (%)FPC (%)
Small (20–80)51.1354.9446.88
Medium (100–400)53.8355.549.33
Large (500–5000)63.4763.061.15
Table 2 Compression ratios of firewall rules.
Fig. 11 Rules compression example of FDM, FPC, and Diplomat.
Fig. 12 Running time with different sizes of firewall rules.
[1]   Meiners C. R., Liu A. X., and Torng E., Bit weaving: A non-prefix approach to compressing packet classifiers in tcams, IEEE/ACM Transactions on Networking (ToN), vol. 20, no. 2, pp. 488-500, 2012.
[2]   Cheng Y., Wang W., Min G., and Wang J., A new approach to designing firewall based on multidimensional matrix, Concurrency and Computation: Practice and Experience vol. 27, no. 12, pp. 3075-3088, 2015.
[3]   Divekar D. A. and Dowell R. I., Corner stitching: A data-structuring technique for VLSI layout tools, IEEE Transactions on Computer-Aided Design, vol. 3, no. 1, p. 87, 1984.
[4]   Wu S. Y. and Sahni S., Covering rectilinear polygons by rectangles, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 9, no. 4, pp. 377-388, 1990.
[5]   Applegate D. A., Calinescu G., Johnson D. S., Karloff H., Ligett K., and Wang J., Compressing rectilinear pictures and minimizing access control lists, in Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, New Orleans, LA, USA, 2007, pp. 1066-1075.
[6]   Liu A. X., Torng E., and Meiners C. R., Firewall compressor: An algorithm for minimizing firewall policies, in Proc. 27th Conf. Computer Communications, Phoenix, AZ, USA, 2008, pp. 176-180.
[7]   Daly J., Liu A. X., and Torng E., A difference resolution approach to compressing access control lists, IEEE/ACM Transactions on Networking, vol. 24, no. 1, pp. 610-623, 2016.
[8]   Draves R. P., King C., Venkatachary S., and Zill B. D., Constructing optimal IP routing tables, in Proc. 18th Ann. Joint Conf. IEEE Computer and Communications Societies, New York, NY, USA, 1999, pp. 88-97.
[9]   Wang J., Tan P., Yao J., Feng Q., and Chen J., On the minimum link-length rectilinear spanning path problem: Complexity and algorithms, IEEE Transactions on Computers, vol. 63, no. 12, pp. 3092-3100, 2014.
[10]   Kumar V. S. A. and Ramesh H., Covering rectilinear polygons with axis-parallel rectangles, in Proc. 31st Annu. ACM Symp. Theory of Computing, Atlanta, GA, USA, 1999, pp. 445-454.
[11]   Berman P. and DasGupta B., Complexities of efficient solutions of rectilinear polygon cover problems, Algorithmica, vol. 17, no. 4, pp. 331-356, 1997.
[12]   Liou W., Tan J. M., and Lee R. C., Minimum rectangular partition problem for simple rectilinear polygons, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 9, no. 7, pp. 720-733, 1990.
[13]   Karp R. M. and Wigderson A., A fast parallel algorithm for the maximal independent set problem, J. ACM, vol. 32, no. 4, pp. 762-773, 1985.
[14]   Suri S., Sandholm T., and Warkhede P., Compressing twodimensional routing tables, Algorithmica, vol. 35, no. 4, pp. 287-300, 2003.
[15]   Taylor D. E. and Turner J. S., Classbench: A packet classification benchmark, IEEE/ACM Transactions on Networking (ToN), vol. 15, no. 3, pp. 499-511, 2007.
[16]   Liu A. X. and Gouda M. G., Diverse firewall design, IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 9, pp. 1237-1251, 2008.
[17]   Wang M., Liu J., Mao J., Cheng H., Chen J., and Qi C., Routeguardian: Constructing secure routing paths in software-defined networking, Tsinghua Science and Technology, vol. 22, no. 4, pp. 400-412, 2017.
[18]   Ye X., Privacy preserving and delegated access control for cloud applications, Tsinghua Science and Technology, vol. 21, no. 1, pp. 40-54, 2016.
[19]   Li W., Cao Y., Chen J., and Wang J., Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, Information and Computation, vol. 252, pp. 187-200, 2017.
[20]   Chen J. E., Xu C., and Wang J. X., Dealing with 4-variables by resolution: An improved maxsat algorithm, Theor. Comput. Sci., vol. 670, pp. 33-44, 2017.
[21]   You J., Wang J., and Cao Y., Approximate association via dissociation, Discrete Applied Mathematics, vol. 219, pp. 202-209, 2017.
[1] Mengmeng Wang,Jianwei Liu,Jian Mao,Haosu Cheng,Jie Chen,Chan Qi. RouteGuardian: Constructing Secure Routing Paths in Software-Defined Networking[J]. Tsinghua Science and Technology, 2017, 22(4): 400-412.
[2] Donglai Fu,Xinguang Peng. TPM-Based Remote Attestation for Wireless Sensor Networks[J]. Tsinghua Science and Technology, 2016, 21(3): 312-321.
[3] Zhen Chen,Yuhao Wen,Junwei Cao,Wenxun Zheng,Jiahui Chang,Yinjun Wu,Ge Ma,Mourad Hakmaoui,Guodong Peng. A Survey of Bitmap Index Compression Algorithms for Big Data[J]. Tsinghua Science and Technology, 2015, 20(1): 100-115.
[4] Chen Lin, Chen Xingshu, Jiang Junfang, Yin Xueyuan, Shao Guolin. Research and Practice of Dynamic Network Security Architecture for IaaS Platforms[J]. Tsinghua Science and Technology, 2014, 19(5): 496-507.
[5] Chen Zhen, Dong Wenyu, Li Hang, Zhang Peng, Chen Xinming, Cao Junwei. Collaborative Network Security in Multi-Tenant Data Center for Cloud Computing[J]. Tsinghua Science and Technology, 2014, 19(1): 82-94.