Fonte: “An innovative two-stage algorithm to optimize Firewall rule ordering”, Paper, An innovative two-stage algorithm to optimize Firewall rule ordering – ScienceDirect.
Abstract
Packet classification activity performed by a FireWall (FW) introduces high latency in network communications due to the computation time required to check whether any packet matches one of the FW rules. Such a classification process is done by sequentially checking the list of rules until a match is found or the end of the list is reached. Given the complexity of FW rules in some environments, this latency could become relevant.
This problem is addressed by ordering the list of FW rules to minimize the classification latency, where the rules with higher activation frequencies are placed accordingly starting from the top of the list. This is not always feasible because dependency constraints between rules could exist: swapping the positions of dependent rules results in a loss of the integrity of the implemented security policy. For this reason, the FW rule ordering problem belongs to the realm of constrained combinatorial optimization.
This paper proposes a two-stage algorithm to address this problem. The first stage performs an innovative topological sorting algorithm aimed at finding an optimal ordering for the constrained rules, taking into account the fact that rule activation frequencies are influenced by inter-packet arrival time, which typically obeys Zipf’s law.
The second stage employs a genetic algorithm to find the optimal ordering of all rules within the list. The proposed approach is evaluated using different filtering lists of different complexity provided by ClassBench. A comparison with other state-of-the-art algorithms addressing the same problem is performed. Furthermore, the performance analysis is extended employing an exact optimization method. The results obtained show the effectiveness of the proposed algorithm in minimizing packet classification latency, while a short reordering time is required.
Introduction
Firewalls (FWs) are security devices widely used to monitor inbound and outbound network traffic and filter data packets based on a list of security rules. The usage and correct configuration of these devices are regulated according to the recommendations posed by the national strategy to the companies (Srinivas et al., 2019).
Packet classification performed by an FW plays a key role in computer networks that employ ever-increasing communication bands to realize faster packet exchange (Adiseshaiah and Sailaja, 2023; Tan et al., 2021). However, such a function could require high latency as a result of a sequential search aimed at checking whether any rule matches the packet. In particular, the greater the complexity of the security rules, the longer the resulting rule list, and the higher the latency (Seno et al., 2022). This is a common real-life scenario occurring when a new rule is inserted without considering the position occupied given its activation frequency.
