The Computational Complexity of Enforceability Validation for Generic Access Control Rules

Published

June 14, 2006

Author(s)

Chung Tong Hu, David R. Kuhn, David F. Ferraiolo

Abstract

In computer security, many researches have tackled on the possibility of a unified model of access control, which could enforce any access control policies within a single unified system. One issue that must be considered is the efficiency of such systems, i.e., what is the computational complexity for the enforceability validation of access control rules of a system that is capable of implementing any access control policy? We investigate this question by arguing that two fundamental requirements exist for any such system: satisfiability of access rules and ensuring absence of deadlock among rules. We then show that both of these problems are NP-Complete by using some basic computational theorems applied to the components of the generic access control process.

Proceedings Title

Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing -Vol 1 (SUTC'06) - Volume 01

Conference Dates

June 5-7, 2006

Conference Location

Taichung,

Pub Type

Conferences

Download Paper

Local Download

Keywords

access control, computational complexity, enforceability validation

Citation

, C. , Kuhn, D. and Ferraiolo, D. (2006), The Computational Complexity of Enforceability Validation for Generic Access Control Rules, Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing -Vol 1 (SUTC'06) - Volume 01, Taichung, , [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50452 (Accessed October 2, 2025)