Polynomial Heuristic Algorithms for Inconsistency Characterization in Firewall Rule Sets

Abstract

Firewalls provide the first line of defence of nearly all networked institutions today. However, Firewall ACLs could have inconsistencies, allowing traffic that should be denied or vice versa. In this paper, we analyze the inconsistency characterization problem as a separate problem of the diagnosis one, and propose formal definitions in order to characterize one-to-many inconsistencies. We identify the combinatorial part of the problem that generates exponential complexities in combined diagnosis and characterization algorithms proposed by other authors. Then we propose a decomposition of the combinatorial problem in several smaller combinatorial ones, which can effectively reduce the complexity of the problem. Finally, we propose an approximate heuristic and algorithms to solve the problem in worst case polynomial time. Although many algorithms have been proposed to address this problem, all of them are combinatorial. The presented algorithms are an heuristic way to solve the problem with polynomial complexity. There are no constraints on how rule field ranges are expressed.