An innovative two-stage algorithm to optimize Firewall rule ordering

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.