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.

Linear Time Algorithms to Restrict Insider Access using Multi-Policy Access Control Systems



Peter M. Mell, James Shook, Richard Harang, Serban I. Gavrila


An important way to limit malicious insiders from distributing sensitive information is to as tightly as possible limit their access to information. This has always been the goal of access control mechanisms, but individual approaches have been shown to be inadequate. Ensemble approaches of multiple methods instantiated simultaneously have been shown to more tightly restrict access, but approaches to do so have had limited scalability (resulting in exponential calculations in some cases). In this work, we take the Next Generation Access Control (NGAC) approach standardized by the American National Standards Institute (ANSI) and demonstrate its scalability. The existing publicly available reference implementations all use cubic algorithms and it was widely viewed as not scalable. The primary NGAC reference implementation took, for example, several minutes to simply display the set of files accessible to a user on a moderately sized system. In our approach, we take these cubic algorithms and make them linear. We do this by reformulating the set theoretic approach of the NGAC standard into a graph theoretic approach and then apply standard graph algorithms. We thus can answer important access control decisions (e.g., which files are available to a user and which users can access a file) using linear time graph algorithms. We also provide a default linear time mechanism to visualize and review user access rights for an ensemble of access control mechanisms. The visualization appears to be a simple file directory hierarchy but in reality is an automatically generated structure abstracted from the underlying access control graph that works with any set of simultaneously instantiated access control policies. It also provide an implicit mechanism for symbolic linking that provides a powerful access capability. Our work thus provides the first efficient implementation of NGAC while enabling user privilege review through a novel visualization approach.
Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications


ABAC, access control, algorithms, complexity, computer security, graph theory, insider, NIST, NGAC, Policy Machine, simultaneous instantiation, XaCML


Mell, P. , Shook, J. , Harang, R. and Gavrila, S. (2017), Linear Time Algorithms to Restrict Insider Access using Multi-Policy Access Control Systems, Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications, [online], (Accessed April 18, 2024)
Created April 13, 2017