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

Published

Author(s)

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

Abstract

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.
Citation
Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications
Volume
8

Keywords

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

Citation

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], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=922390 (Accessed November 21, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created April 13, 2017