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: peter_cheng@csu.edu.cn. ∙ Weiping Wang and Jianxin Wang are with the School of Information Science and Engineering, Central South University, Changsha 410083, China. E-mail: jxwang@mail.csu.edu.cn. ∙ Haodong Wang is with the Department of Electrical Engineering and Computer Science, Cleveland State University, Cleveland, OH 44115, USA. E-mail: hwang@eecs.csuohio.edu.

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.

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.

Fig. 8 An example of digraph for the spatial relations of the grid cells in Dim ${F}_{\text{\U0001d7cf}}$ and Dim ${F}_{\text{\U0001d7d0}}$, respectively.

Fig. 9 An example of rectilinear polygon covering in the two-dimensional space. (a) To cover ${c}_{\text{\U0001d7cf}}$, ${c}_{\text{\U0001d7d0}}$, ${c}_{\text{\U0001d7d1}}$, and ${c}_{\text{\U0001d7d2}}$ with ${c}_{\text{\U0001d7cf}}$ as the initial grid cells; (b) Remove the convex grid cells ${c}_{\text{\U0001d7cf}}$, ${c}_{\text{\U0001d7d0}}$, and ${c}_{\text{\U0001d7d3}}$; (c) To cover ${c}_{\text{\U0001d7d1}}$, ${c}_{\text{\U0001d7d2}}$, ${c}_{\text{\U0001d7d4}}$, and ${c}_{\text{\U0001d7d5}}$ with ${c}_{\text{\U0001d7d1}}$ as the initial grid cells; and (d) Remove all the convex grid cells.

Fig. 10 Performance comparison of FDM, Diplomat, and FPC.

Rules set

FDM (%)

Diplomat (%)

FPC (%)

Small (20–80)

51.13

54.94

46.88

Medium (100–400)

53.83

55.5

49.33

Large (500–5000)

63.47

63.0

61.15

Mean

56.14

57.81

52.45

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.