International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 289

ISSN 2229-5518

An Efficient screening Control for enhanced


Vijay Venkat Raaj.S, Kavitha.M

Abstract— Today, network based security is one of the important concerns for both organizations and individuals. They are needed to monitor and control the traffic that crosses into and out of their networks to prevent attacks from both the network as well as organization perspective. Thus, firewall forms a crucial component in the defense mechanisms of every private network connected to the internet. Thus, it can be considered the first filtering device that sees IP packets that attempt to enter a network from outside and the last device to let out packets as well. It’s like a security system that uses policies to make filtering decision on every packet that crosses it: whether to let it or drop it. Packet matching in firewalls involves matching on many fields from the TCP, UDP and IP packet header like, packet’s source and destination IP address, protocol and source, destination port numbers. This paper proposes an algorithm of computational geometry which solves the point location problem, with a linear space requirement and a reduced search time. In such situation, usage of overlapping hyper-rectangles is done, firewall administrators uses intersection and difference operations on sets of IP addresses or port numbers and then implement over the incoming and outgoing packets, since firewall rules often overlap each other, which is the solution for the problem so that it would be faster and efficient in nature.

Index TermsFirewall, Hyper rectangles, Internet Packets, Network security, Packet filtering, Point Location Problem, Packet matching.


—————————— ——————————
raditionally, a firewall has been a dedicated piece of hardware meant to allow two networks to communicate in a secured way. It acts as a gateway that can restricts
and controls the flow of traffic between networks, typically between an internal corporate network and the Internet. In recent years, software firewalls have come into use, and they pose a cost effective solution for many users, such as those with home or small office broadband networks.
Information that is transmitted on networks is in the form of ‘packets’. The firewall examines relevant parts of a packet and only allows those that comply with its configuration to be successfully delivered. In the case of a proxy firewall, traffic never flows directly between the networks. Instead, the proxy repackages request and responses. No internal host is directly accessible from the external network and no external host is directly accessible by an internal host.The major work of a firewall is Packet filtering, which controls access by examining packets based on the content of packet headers.
The information of the header, such as IP address or port number is being examined to determine whether a packet should be forwarded or rejected, based on a rule set. Further, stateful packet filter forwards or rejects traffic based on the con- tents of a state table maintained by a firewall.


Vijay Venkat Raaj.S is currently pursuing masters degree program in Information Technology in SRM University, India, PH-9566515864.

Kavitha.M is currently working as an Assistant Proffessor in the Depart- ment of Information Technology in SRM University, India,

When stateful filtering is used, packets are only forwarded if they belong to a connection that has already been estab- lished and that is being tracked in a state table. Thus, firewall is for enforcing a security policy that benefits organization and
a PC by creating a security perimeter that helps in identifying and remove the threats very effectively, thereby increasing the security at every level possible.


2.1 Packet Classification

First thing before the filtering, any firewall has to classify the packets.Packet classification is an enabling function for operat- ing on a variety of Internet applications including parameters like quality of service, security, monitoring, and effective communications. The main reason for the success of the fire- wall is that, it allows centralized filtering of traffic entering and exiting the protected network or the demilitarized zone.
Fig. 1. Header Fields for classifying a given packet
In order to classify a packet as belonging to a particular flow or a set of flows, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. Individual entries for classifying a packet are called rules.

IJSER © 2013

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 290

ISSN 2229-5518

The packet classification context determine first matching rule for each incoming message at a router. The classifier or rule database in a router consists of a finite set of rules. Each rule is a combination of a set of values, one for each header field in the packet. Each field in a rule is allowed three kinds of match: exact match, prefix match, or range match.
In an exact match, the header field of the packet should exactly match the rule field. For instance, this is useful for pro- tocol and flag fields. In a prefix match, the rule field should be a prefix of the header field- this could be useful for blocking access from a certain sub network. In a range match, the head- er values should lie in the range specified by the rule-this can be useful for specifying port number ranges.
A packet matches a rule, if all the header fields of the packet match the corresponding fields in that rule. If a packet matches multiple rules, the matching rule with the smallest index is returned. Thus, packet classification acts as a base towards large scale packet filtering.

2.2 Packet Filtering

The major work of the firewall lies in its packet filter. It can operate by identifying a policy i.e. a document defining ac- ceptable access to protected, DMZ, and unprotected networks and set general guidelines for what is and is not acceptable for network access by the legitimate users.
The security policy is the set of rules that can help keeping systems secure. Any system connected to the internet, directly or indirectly, should have a security policy. For a typical home system, this doesn't have to be very complicated, and it doesn't have to exist as a formal document, just a set of rules that set out what you are trying to accomplish, and what any- body using computers is expected to do to protect them in an effective way.
Thus, a packet filtering is first-level firewall technology that analyses network traffic at the network layer. It is a mech- anism used to provide a level of security by examining some key information in packet headers. A packet filter is the one that determines if the packets are allowed to go through a giv- en point, based on the control policies set by the network ad- ministrator.

Fig. 2. Concept of filtering a packet by firewall rules
Each packet is examined to see if it matches with set of rules defining what data flows are allowed. These rules identi- fy whether communication is allowed based upon information contained within the internet and transport layer headers and the direction in which the packet is destined.
This is done by comparing the protocol header fields of a packet with a filter specification. The process of controlling access by examining packets based on the content of packet headers. Header information, such as IP address or port num- ber, is examined to determine whether a packet should be al- lowed, based on a rule set i.e. a collection of access control rules that determines which packets are forwarded or dropped.
Most of the modern and commercial firewalls are stateful. These ones are stateful in nature and do the process of for- warding or rejecting traffic based on the contents of a state table maintained by a firewall. When stateful filtering is used, packets are only forwarded if they belong to a connection that has already been established and that is being tracked in a state table. Thus, connection state is considered another factor for filtering in the Stateful firewalls and so used in complex connections and is less vulnerable to threats. These things are implemented by major firewall vendors like Cisco, Check Point and Juniper. Thus, every firewall requires of their own algorithms and corresponding rule sets.

2.3 Packet Matching

The major scenario behind the working of the stateful filtering mechanism enters the concept of packet matching. It involves matching the specific fields of a packet towards an existing rule-set of the firewall and then if positive, accepts or rejects the packet if negative. There are various approaches used here. For example, the first match semantics matches a packet if the first rule of the firewall rule-set matches the packet.
Commercial firewall vendors like Cisco has come up with the concept of flexible packet matching, against notable worms and viruses. . It specifies arbitrary bits and bytes between the entire packets, classify them and set up custom filters using XML-based policy language. The main advantages of packet matching are that, administrator need not define specific rules for return traffic or on the outgoing packets and thus proving

IJSER © 2013

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 291

ISSN 2229-5518

to be more secure and robust in filtering the packets.


There have been extensive researches for developing a secure firewall that identifies and filters the wrong ones. This can be done an effective packet matching algorithm. Based on the literature survey done, there exist two types of algorithms for developing stateful firewalls.
These are based on the searching the right rule for the right packet sent during the flow.They include: 1) slow algorithm that implements the “first match” semantics and compares a packet to all the rules and 2) fast state lookup mechanism that checks whether a packet belongs to an exist- ing open flow.
In many firewalls like IP tables, an open source, Linux based firewall, the slow algorithm is used, and linear search is done for finding the matching rule-base, while the state lookup mechanism uses a hash table or a search tree, which effectively searches the rule base matching the packet.

Fig. 3. Sample rule-set forming a Firewall Configuration


On analysis of various existing firewalls, it is found that the matching rule for the packet is not actually that much feasible for the incoming and outgoing packets that this single phe- nomenon acts as a vulnerability for various threats towards the computing systems like distributed denial of service in the case of servers and denial of service attacks in to the home computers.
These types of attack can be done as an attempt to make a machine or network resource unavailable to its intend- ed users, making Acknowledgment loss that can cause a situa- tion where a port may remain open for a time interval long enough for an eavesdropping attacker to identify and launch a directed attack to it.


In the paper we propose a mechanism based on the fast state look up, that will effectively match the incoming packets based on the valid rule that can best match the packet. Further it retains the reduced time complexity of O (log n) and reduces the space complexity to O (n).

The scenario of packet matching uses a solution taken for the point location problem that is finding the right point at the right place. For this, the concept of hyper rectangles is used.
Fig. 4. Block Diagram of overall mechanism
Here, the incoming packets are being checked by the internal firewall for matching packets and if everything went ok, then packets are sent inside to the internal network on the first case. In the second one on the right, the outgoing packets are searched for searched for the right fields and parameters and sent to the web servers.

4.1 Point Location Problem

The problem can be considered as follows. Each packet is a point in d-dimensional space: each header field corresponds to a dimension. Each rule is now a d-dimensional “box”, and we have N such boxes (rules), that may overlap each other, with a higher priority given to boxes (rules) which are listed first. Under this interpretation, the matching problem is now: find the highest priority box that contains a given d-dimensional point.

Fig. 5. Point location problem
It is difficult for people to visualize three-dimensional space. But in two dimensions the analogy is quite natural. be especially confusing. Think of a plane, with the X-axis corre- sponding to the source IP address, and the Y-axis correspond- ing to the destination IP address. . In this view, a rule is a rec- tangle: all points whose X value is in some range and whose Y value is in some other range. If one of the fields is a “don’t- care”, we just end up with a very wide (or very tall) rectangle.

IJSER © 2013

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 292

ISSN 2229-5518

A rule-base with N rules now becomes a collection of overlap- ping rectangles.
When 2 rectangles overlap, one hides parts of the other. Now think of all the “PASS” rules as having a white color, and all the “DROP” rules as having a black color. Viewed from above, the full set of N rectangles subdivides the plane into a patchwork of rectangles, and rectangle fragments (that are just smaller rectangles) – some white and some black. Given a particular point, with some X/Y coordinates (source/destination IP addresses), finding which rectangle does it belong to, and what color is that rectangle, is called a point location problem.

4.2 The Solution

We can consider the algorithm proposed as the solution for the problem, by having the hyper rectangles in hand. We find the first rule that matches a given packet on one or more fields from its header. Every rule consists of set of ranges for a set of values, where each range corresponds to that particular field in a packet header. Every rule consists of set of ranges for a set of values, where each range corresponds to that particular field in a packet header. The field values are in the range of 0 to N, where N is the maximum value for all the protocol sys- tems. Then, we can give the packet-matching problem a geo- metric analogy or an interpretation.

Each packet is a point in d-dimensional space: each header field corresponds to a dimension. Each rule is now a d- dimensional “box”, and we have N such boxes (rules), that may overlap each other, with a higher priority given to boxes (rules) which are listed first. But Under this interpretation, the matching problem is now: find the highest priority box that contains a given d-dimensional point.
Fig. 6. Block Diagram of overall mechanism
Thus, the rightful rule is found for the corresponding packet as the rectangle containing the point(s).

4.3 The Search Structure and Build Algorithm

The data structure is the background process that work on behind the solution for the point location problem. It is like a binary tree structure taking three major fields into our consid- eration like protocol number, source and destination port numbers.

Fig. 7. The Search Data Structure
As shown in Fig. 6, we consider protocol number as a source and construct a binary search tree and find the matching one i.e. of the packet. For each and every packet we deploy corre- sponding binary search technique and find for the correct val- ues. This is repeated over a number of times for the source and destination port numbers to get the best result with a time complexity of O (log n).
In order to impart the full result from the partial search work, they must be combined together. This is accom- plished by using the build algorithm. This is done one for each protocol. This consists of rule-base plus field order to use. This can be started by setting critical points over each level and run sweep-line over them and calculate the active rules for every level.

4.4 The Results

The algorithm was being imparted on isolation over c#.NET and data taken from SQL server management studio, with Windows 7 as the operating system. Then, testing was done over uniformly-generated rules: for every rule, each endpoint of each of the fields (IP address ranges and port ranges) was selected uniformly at random from its domain.

Fig. 8. Rules Reduction Representation

IJSER © 2013

On analysis with sample data over the inbound and

International Journal of Scientific & Engineering Research, Volume 4, Issue 4, April-2013 293

ISSN 2229-5518

outbound rules, we could achieve the following graphical re- sults as the number of packets increases, the number of rules decreases to a considerable range marking the efficiency of the algorithm.

Fig. 9. Rules versus the processing time

Further, the data structure was built for increasing numbers of such rules and then used the resulting structure to match randomly generated packets; a single packet match took around 1μsec, since it only required 4 executions of a bi- nary search in memory.On the other hand, the data structure size grew rapidly—and thus, the order of fields had little or no effect on this size and so the processing time of the firewall or the algorithm decreases as the rules increases.
Fig. 9. Occurrence of corrupted packets over filtered ones
Finally, on careful manipulation, we get the correct rule that matches the packet with lowest number of active rules in hand, with a space complexity of O (n) and time complexity of O(log n) thereby, reducing the number of cor- rupted packets occurring in the network


The analysis of the packet screening algorithm is an efficient and practical algorithm for firewall packet matching. It is im- plemented successfully and tested with packet matching speeds. Its matching speed is far better than the naïve linear search, and is able to increase the throughput by the order of magnitude. On rule-bases generated according to realistic sta-
tistics, its space complexity is well within the capablities over the modern hardware.


We specially thank our HOD and the staff members of SRM University for rendering us valuable information and encouraging us throughout our research.


[1] D.E. Taylor, “Survey and Taxonomy of Packet Classification,” ACM Compu- ting Surveys, Vol. 37, pp. 238-275, 2005.

[2] P. Gupta and N.McKneown, “Algorithms for Packet Classification”.

IEEE Network, Vol. 15, pp. 24-32, Mar. /Apr. 2001.

[3] V.Srinivasan, “A Packet Classification and Filter management Sys- tem,” Proc. IEEE INFOCOM, pp. 1464-1473, 2001.

[4] A. Wool, “Packet Filtering and Stateful Firewall," Handbook of In- formation Security, Vol III, Threats, Vulnerablities, Preven- tion,Detection and Management, H.Bidgoli, ed., chapter 171, pp. 526-

536, John Wiley and sons, 2006 .

[5] P.Gupta and N.McKneown, "Packet Classification on Multiple

Fields," Proc,. ACM SIGCOMM, as on pp. 147-160, 1999.

[6] D. Eppstein and S. Muthukrishnan, “Internet Packet Filtering Man- agement and Rectangle Geometry” Proc.ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 827-835, 2001.

[7] S. Singh, F.Baboescu, G.Varghese and J. Wang, "Packet Filtering us-

ing multi-dimensional cutting," Proc. ACM-SIGCOMM, 2003.

[8] Mikkel Christiansen, Emmanuel Fleury, “Using IDD’s for Packet Filtering,” Depaertement of Computer Science, Aalborg University, Proc.BRICS 2002.

[9] D.Rovigniagin and A.Wool, “Geometric Efficient Algorithm for Firewalls” Report EES 2003-6, Dept of Electrical Engineering systems, Tel Aviv Univ.,,ps.2009.

[10] Firewall Wizards, Electronic Mailing List,,


IJSER © 2013