Access control is used to provide regulated access
to resources by principals. It is an important and foundational
aspect of information security. Role-Based Access Control (RBAC) is
a popular and widely-used access control model,
that, as prior work argues,
is ideally suited for enterprise settings. In this dissertation,
we address two problems in the context of RBAC.
One is the 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 that the user wants to exercise in
that session. The roles that are activated must respect
a set of Separation of Duty constraints. Such constraints restrict the
roles that can be activated together in a session.
UAQ is known to be intractable (NP-hard).
In this dissertation, we give a precise formulation of UAQ as a
joint-optimization problem, and analyze it.
We examine the manner in which each input parameter contributes to its
intractability.
We then propose an approach to mitigate its intractability based on
our observation that a corresponding decision version of the problem
is in NP. We efficiently
reduce UAQ to Boolean satisfiability in conjunctive normal form
(CNF-SAT), a well-known
NP-complete problem for which solvers exist that are efficient for large
classes of instances. We also present results for UAQ posed
as an approximation problem; our results
suggest that efficient approximation is not promising for UAQ.
We discuss an open-source implementation of our approach and a
corresponding empirical assessment that we have conducted.
The other problem we consider in this dissertation regards
an efficient data structure for distributed
access enforcement. Access enforcement is the process of validating an access
request to a resource.
Distributed access enforcement has become important
with the proliferation of data, which requires access control systems
to scale to tens of thousands of resources and permissions.
Prior work has shown the effectiveness of a data structure called
the Cascade Bloom Filter (CBF) for this problem.
In this dissertation, we study the construction of instances
of the CBF.
We formulate the problem of finding an optimal instance of a
CBF, where optimality refers to the number of false positives
incurred and the number
of hash functions used. We prove that this problem
is NP-hard, and a meaningful decision version is in NP.
We then propose an approach to mitigate the intractability of
the problem by reducing it to
CNF-SAT, that allows us to use a SAT solver for instances that
arise in practice.
We discuss an open-source implementation of our approach
and an empirical assessment based on it.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/8303 |
| Date | 29 July 2014 |
| Creators | Mousavi, Nima |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0019 seconds