The firewall is one of the central technologies allowing high-level access control to organization networks. Packet matching in firewalls involves matching on many fields from the TCP and IP packet header. At least five fields (protocol number, source and destination IP addresses, and ports) are involved in the decision which rule applies to a given packet. With available bandwidth increasing rapidly, very efficient matching algorithms need to be deployed in modern firewalls to ensure that the firewall does not become a bottleneck Since firewalls need to filter all the traffic crossing the network perimeter, they should be able to sustain a very high throughput, or risk becoming a bottleneck. Thus, algorithms from computational geometry can be applied. In this paper we consider a classical algorithm that we adapted to the firewall domain. We call the resulting algorithm “Geometric Efficient Matching” (GEM). The GEM algorithm enjoys a logarithmic matching time performance. However, the algorithm’s theoretical worst-case space complexity is O (n4) for a rule-base with n rules. Because of this perceived high space complexity, GEM-like algorithms were rejected as impractical by earlier works. Contrary to this conclusion, this paper shows that GEM is actually an excellent choice. Based on statistics from real firewall rule-bases, we created a Perimeter rules model that generates random, but non-uniform, rulebases. We evaluated GEM via extensive simulation using the Perimeter rules model. The Geometric Efficient Matching Algorithm for Firewalls
Existing algorithms implement the “longest prefix match” semantics, using several different approaches.The IPL algorithm, which is based on results, divides the search space into elementary intervals by different prefixes for each dimension, and finds the best (longest) match for each such interval.
Firewall statefulness is commonly implemented by two separate search mechanisms: (i) a slow algorithm that implements the “first match” semantics and compares a packet to all the rules, and (ii) a fast state lookup mechanism that checks whether a packet belongs to an existing open flow.
In many firewalls, the slow algorithm is a naive linear search of the rule-base, while the state lookup mechanism uses a hash-table or a search-tree
In the field of computational geometry, proposed an algorithm which solves the point location problem for n non-overlapping d-dimensional hyper-rectangles, with a linear space requirement and O ((log n) (d−1)) search time. In our case, we have overlapping d-dimensional hyper-rectangles, since firewall rules can, and often do, overlap each other— making rules overlap is the method firewall administrators use to implement intersection and difference operations on sets of IP addresses or port numbers. These overlapping hyper-rectangles can be decomposed into non-overlapping hyper-rectangles—however, a moment’s reflection shows that the number of resulting non-overlapping hyper-rectangles is (nd), thus the worst case complexity for firewall rules is no better than that of GEM.