Open Access Open Access  Restricted Access Subscription or Fee Access

Validating the Rule set with BDD & Usage with GEM for Improving Efficiency of Firewalls

M. Kasi Viswanadh, Dr.P. Harini


World is running on internet in real sense since all the important and major tasks of life are carried out through internet. All the major and huge businesses depend on internet but at the same time internet is a big threat for these conglomerates. Because hackers and scams can ruin the online businesses and they could face great deal of data loss. In order to avoid such sort of internet corruption, firewalls are designed as to protect the networks from hackers and scams. Firewall is basically a blockade which restricts the outside forces from accessing your network and attacking your data. By filtering packets the firewalls can improve security and performance. However, as the size of the rule list increases, it becomes difficult to maintain and validate the rules. Ordered binary decision diagrams (BDDs) – a compact method of representing and manipulating Boolean expressions – are a potential method of representing the rules. Geometric Efficient Matching Algorithm (GEM) uses near-linear space, and only needs approximately 13 MB of space for rule-bases of 5,000 rules. Moreover, with use of additional space improving heuristics, the space requirement can be reduced to 2-3 MB for 5,000 rules. This paper presents a new approach not only to analyze and to validate rule sets and also resultant rule sets are passed as an input for Geometric Efficient Matching Algorithm for improving the efficiency of firewalls.


Firewall, BDDs, Internet Corruption, GEM

Full Text:



Dmitry Rovniagin and Avishai Wool, ―The Geometric Efficient Matching Algorithm for Firewalls,‖ IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 8, NO. 1

Scott Hazelhurst, ―Algorithms for Analysing Firewall and Router Access Lists‖ Programme for Highly Dependable Systems, Department of Computer Science, 16 July 1999

M. de Berg, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications, second ed. Springer-Verlag,2000.

Cisco Systems Inc. Configuring IP Systems. Published at the Cisco web site, 1997. /univercd /cc /td /doc /product /software.

S Hazelhurst, A Fatti, and A Henwood. ‗Binary Decision Diagram Representations of Firewall and Router Access Lists‘. Technical Report TR-Wits-CS-1998-3, Department of Computer Science, University of the Witwatersrand, (October 1998). Proceedings of SAICSIT ‘98

A. Wool, ―Packet Filtering and Stateful Firewalls,‖ Handbook of Information Security, vol. III: Threats, Vulnerabilities, Prevention, Detection and Management, H. Bidgoli, ed., chapter 171, pp. 526-536. John Wiley & Sons, 2006

D.P. Dobkin and R.J. Lipton, ―Multidimensional Searching

Problems,‖ SIAM J. Computing, vol. 5, no. 2, pp. 181-186, 1976.

J. Matou_sek, ―Geometric Range Searching,‖ ACM Computing Surveys, vol. 26, no. 4, pp. 422-461, 1994.

D. Eppstein and S. Muthukrishnan, ―Internet Packet Filter Management and Rectangle Geometry,‖ Proc. ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 827-835, 2001.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.