Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

The Computational Complexity of Enforceability Validation for Generic Access Control Rules

Published

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,

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 April 13, 2024)
Created June 14, 2006, Updated February 19, 2017