Firewall Rule Set Inconsistency Characterization by Clustering

Abstract

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 definitions to characterize one-to-many inconsistencies. We identify the combinatorial part of the problem that causes exponential complexity in combined diagnosis and characterization algorithms proposed by other researchers. The problem is divided in several smaller combinatorial ones, which effectively reduces its complexity. Finally, we propose a heuristic to solve the problem in worst case polynomial time as a proof of concept.