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

An important way to limit malicious insiders from distributing sensitive information is to restrict access as tightly as possible. This has always been the goal in the design of access control mechanisms, but individual approaches can be inadequate. Approaches that instantiate multiple methods simultaneously have been shown to restrict access with more precision. However, those approaches have had limited scalability (resulting in exponential calculations in some cases). In this work, we provide an implementation of the Next Generation Access Control (NGAC) standard from the American National Standards Institute (ANSI) and demonstrate that it scales. The existing publicly available reference implementations all use cubic algorithms for policy decisions, and thus NGAC was widely viewed as not scalable. Our approach provides an easy to understand graph algorithm that performs policy decision in linear time at the worst. However, in practice the algorithm runs considerably faster. We also provide a default linear time mechanism to visualize and review user access rights for an ensemble of access control mechanisms. Our 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 provides an implicit mechanism for symbolic linking that provides a powerful access capability. Our work has thus lead to the first efficient implementation of NGAC while enabling user privilege review through a novel visualization approach.