<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T20:17:58Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/8303" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/8303</identifier><datestamp>2017-03-21T14:09:47Z</datestamp><setSpec>com_10012_9900</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9908</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="9f869e8a-f813-45df-bc5b-4b3bf6f1a6b2" confidence="600">Mousavi, Nima</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2014-03-31T19:41:10Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2014-07-30T05:00:14Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2014-03-31</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2014-03-31</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/8303</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Access control is used to provide regulated access&#xd;
to resources by principals. It is an important and foundational&#xd;
aspect of information security. Role-Based Access Control (RBAC) is&#xd;
a popular and widely-used access control model,&#xd;
that, as prior work argues,&#xd;
is ideally suited for enterprise settings. In this dissertation, &#xd;
we address two problems in the context of RBAC.&#xd;
&#xd;
One is the User Authorization Query (UAQ) problem, which relates&#xd;
to sessions that a user creates to exercise permissions. &#xd;
UAQ&amp;apos;s objective is the identification of a&#xd;
set of roles that a user needs to activate such that the session is&#xd;
authorized to all permissions that the user wants to exercise in&#xd;
that session. The roles that are activated must respect&#xd;
a set of Separation of Duty constraints. Such constraints restrict the &#xd;
roles that can be activated together in a session.&#xd;
UAQ is known to be intractable (NP-hard).&#xd;
In this dissertation, we give a precise formulation of UAQ as a&#xd;
joint-optimization problem, and analyze it.&#xd;
We examine the manner in which each input parameter contributes to its&#xd;
intractability.&#xd;
We then propose an approach to mitigate its intractability based on&#xd;
our observation that a corresponding decision version of the problem&#xd;
is in NP. We efficiently&#xd;
reduce UAQ to Boolean satisfiability in conjunctive normal form&#xd;
(CNF-SAT), a well-known&#xd;
NP-complete problem for which solvers exist that are efficient for large&#xd;
classes of instances. We also present results for UAQ posed&#xd;
as an approximation problem; our results&#xd;
suggest that efficient approximation is not promising for UAQ.&#xd;
We discuss an open-source implementation of our approach and a&#xd;
corresponding empirical assessment that we have conducted.&#xd;
&#xd;
The other problem we consider in this dissertation regards&#xd;
an efficient data structure for distributed&#xd;
access enforcement. Access enforcement is the process of validating an access&#xd;
request to a resource.&#xd;
Distributed access enforcement has become important&#xd;
with the proliferation of data, which requires access control systems&#xd;
to scale to tens of thousands of resources and permissions. &#xd;
Prior work has shown the effectiveness of a data structure called&#xd;
the Cascade Bloom Filter (CBF) for this problem.&#xd;
In this dissertation, we study the construction of instances&#xd;
of the CBF.&#xd;
We formulate the problem of finding an optimal instance of a&#xd;
CBF, where optimality refers to the number of false positives&#xd;
incurred and the number&#xd;
of hash functions used. We prove that this problem&#xd;
is NP-hard, and a meaningful decision version is in NP. &#xd;
We then propose an approach to mitigate the intractability of&#xd;
the problem by reducing it to &#xd;
CNF-SAT, that allows us to use a SAT solver for instances that&#xd;
arise in practice.&#xd;
We discuss an open-source implementation of our approach&#xd;
and an empirical assessment based on it.</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="embargoterms" lang="en">4 months</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Access Control</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Role based Access Control</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">User Authorization Query Problem</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Cascade Bloom Filter</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">NP-hard</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Electrical and Computer Engineering (Software Engineering)</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Algorithmic Problems in Access Control</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>