Fast Algorithms for Local Inconsistency Detection in Firewall ACL Updates

Filtering is a very important issue in next generation networks. These networks consist of a relatively high number of resource constrained devices with very special features, such as managing frequent topology changes. At each topology change, the access control policy of all nodes of the network must be automatically modified. In order to manage these access control requirements, firewalls have been proposed by several researchers. However, many of the problems of traditional firewalls are aggravated due to these networks particularities. In this paper we deeply analyze the local consistency problem in firewall rule sets, with special focus on automatic frequent rule set updates, which is the case of the dynamic nature of next generation networks. We propose a rule order independent local inconsistency detection algorithm to prevent automatic rule updates that can cause inconsistencies. The proposed algorithms have very low computational complexity as experimental results will show, and can be used in real time environments.