Back to search

University of Waterloo

The Hardness of Learning Access Control Policies

Abstract

dc:description.abstract

The problem of learning access control policies is gaining significant attention in research. We contribute to the foundations of this problem by posing and addressing meaningful questions on computational hardness. Our study focuses on learning access control policies within three different models: the access matrix, Role-Based Access Control (RBAC), and Relationship-Based Access Control (ReBAC), as described in existing literature. Our approach builds upon the well-established concept of Probably Approximately Correct (PAC) theory, with careful adaptations for our specific context. In our setup, the learning algorithm receives data or examples associated with access enforcement, which involves deciding whether an access request for resource should be accepted or denied. For the access matrix, we pose a learning problem that turns out to be computationally easy, and another that we prove is computationally hard. We generalize the former result so we have a sufficient condition for establishing other problems to be computationally easy. Building upon these findings, we examine five learning problems in the context of RBAC, of which three are identified as computationally easy and two are proven to be computationally hard. Finally, we consider four learning problems in the context of ReBAC, all of which are found to be computationally easy. Every proof for a problem that is computationally easy is constructive, in that we propose a learning algorithm for the problem that is efficient, and probably, approximately correct. As such, our work makes contributions at the foundations of an important, emerging aspect of access control, and thereby, information security.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lei, Xiaomeng
Advisor dc:contributor.advisor
  • Tripunitara, Mahesh

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/19803

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Lei, Xiaomeng. The Hardness of Learning Access Control Policies. University of Waterloo, 2023. http://hdl.handle.net/10012/19803