On the Notion of Redundancy in Access Control Policies

The evolution of information systems sees an increasing need of flexible and sophisticated approaches for the automated detection of anomalies in security policies. One of these anomalies is redundancy, which may increase the total cost of management of the policies and may reduce the performance of access control mechanisms and of other anomaly detection techniques. We consider three approaches that can remove redundancy from access control policies, progressively reducing the number of authorizations in the policy itself. We show that several problems associated with redundancy are NP-hard. We propose exact solutions to two of these problems, namely the Minimum Policy Problem, which consists in computing the minimum policy that represents the behaviour of the system, and the Minimum Irreducible Policy Problem, consisting in computing the redundancy-free version of a policy with the smallest number of authorizations. Furthermore we propose heuristic solutions to those problems. We also present a comparison between the exact and heuristics solutions based on experiments that use policies derived from bibliographical databases.