Candidate
Nima Mousavi
Title
Algorithmic Problems in Access Control
Abstract
Access control is used to provide regulated access to resources by principals. It is one of the most important and foundational areas of research in information security. Role-Based Access Control (RBAC) is one of the most popular and widely-used access control models. In particular, it has been argued that RBAC is ideally suited for enterprise settings. In this dissertation, we address two problems in the context of RBAC.
The first problem is User Authorization Query (UAQ) problem, which relates to sessions that a user creates to exercise permissions. UAQ's objective is the identification of a set of roles that a user needs to activate such that the session is authorized to all permissions in a set, while there exists a set of Separation of Duty constrains on roles. UAQ is known to be intractable ( NP-hard). In this dissertation, we give a precise formulation of UAQ as a joint optimization problem. We present a detailed analysis of the complexity of UAQ. We take a finer look at the source of complexity of UAQ by identifying the role of each input parameter in the intractability of UAQ. We then proposed an approach to mitigate its intractability based on our observation that in general, UAQ remains in NP; we efficiently reduce UAQ to Boolean satisfiability in conjunctive normal form, a well-known NP-complete problem for which solvers exist that are efficient for large classes of instances. We also present results for the approximate variants of UAQ that suggest that this approach is not promising for UAQ; Assuming P \neq NP, no efficient approximation algorithm exists for UAQ. We discuss an open-source implementation of our approach, based on which we have conducted an empirical assessment.
Next, the problem of finding an efficient data structure for distributed access enforcement. Access enforcement is the process of validating an access request to a resource. The distributed access enforcement has become important with proliferation of data, which requires access control system to scale to tens of thousands of resources and permissions. Prior work have proved the effectiveness of a data structure called cascade Bloom filter for distributed access enforcement applications. In this dissertation, we study the cascade Bloom filter. We formulate the problem of finding an optimal instance of Cascade Bloom Filter (CBF), where optimality refers to the number of false positives and the number of hash functions used in the cascade Bloom filter. We prove that the CBF problem is NP-complete. We then propose an approach to mitigate the intractability of CBF, i.e., we reduce CBF to Boolean satisfiability in conjunctive normal form, and use a SAT solver to solve it. We discuss an open-source implementation of our approach, based on which we have conducted an empirical assessment.