Catherine Rosenberg, FIEEE, FCAE

Tuesday, August 27, 2013 2:00 pm - 2:00 pm EDT (GMT -04:00)

Speaker

Nima Mousavi

Title

Mitigating the Intractability of the User Authorization Query Problem in Role-Based Access Control

Abstract

We address the User Authorization Query problem (UAQ) in Role-Based Access Control (RBAC) which relates to sessions that a user creates to exercise permissions. Prior work has shown that UAQ is intractable (NP-hard).
We give a precise formulation of UAQ as a joint optimization problem, and take a finer look at the complexity of UAQ. We study the computational complexity of each of four subcases of UAQ, and their approximation variants.
Our results show how  each input parameter contributes into the complexity of UAQ. We also prove that in general, UAQ remains in NP. We then investigate two techniques to mitigate its intractability.

(1) 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 point out that a prior attempt is not a reduction, is inefficient, and provides only limited support for joint optimization.

 
(2) We show that UAQ is fixed-parameter polynomial in the upper-bound set of permissions under reasonable assumptions.
We discuss an open-source implementation of (1) and (2), based on which we have conducted an empirical assessment.

Supervisor

Mahesh Tripunitara