R.M.: A Heuristic Polynomial Algorithm for Local Inconsistecy Diagnosis

Abstract: Firewall ACLs can contain inconsistencies. There is an inconsistency if different actions can be taken on the same flow of traffic, depending on the ordering of the rules. Inconsistent rules should be notified to the system administrator in order to remove them. Minimal diagnosis and characterization of inconsistencies is a combinatorial problem. Although many algorithms have been proposed to solve this problem, all reviewed ones work with the full ACL with no approximate heuristics, giving minimal and complete results, but making the problem intractable for large, real-life ACLs. In this paper we take a different approach. First, we deeply analyze the inconsistency diagnosis in firewall ACLs problem, and propose to split the process in several parts that can be solved sequentially: inconsistency detection, inconsistent rules identification, and inconsistency characterization. We present polynomial heuristic algorithms for the first two parts of the problem: detection and identification (diagnosis) of inconsistent rules. The algorithms return several independent clusters of inconsistent rules that can be characterized against a fault taxonomy. These clusters contains all inconsistent rules of the ACL (algorithms are complete), but the algorithms not necessarily give the minimum number of clusters. The main advantage of the proposed heuristic diagnosis process is that optimal characterization can be now applied to several smaller problems (the result of the diagnosis process) rather than to the whole ACL, resulting in an effective computational complexity reduction at the cost of not having the minimal diagnosis. Experimental results with real ACLs are given.