Towards complexity analysis of User Authorization Query problem in RBAC

The User Authorization Query (UAQ) problem for RBAC is to determine whether there exists an optimum set of roles to be activated to provide a particular set of permissions requested by a user. It is a key issue related to efficiently handling users' access requests. Previous definitions of the...

Full description

Saved in:
Bibliographic Details
Published in:Computers & security 2015-02, Vol.48, p.116-130
Main Authors: Lu, Jianfeng, Joshi, James B.D., Jin, Lei, Liu, Yiding
Format: Article
Language:English
Subjects:
Access control
Algorithms
Authentication protocols
Complexity
Complexity theory
Computation
Computational complexity
Computer information security
Operations research
Optimization
Optimization algorithms
Permission-cardinality constraint
Preprocessing
Pruning
Query processing
RBAC
Role-cardinality constraint
Running
Studies
User Authorization Query
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The User Authorization Query (UAQ) problem for RBAC is to determine whether there exists an optimum set of roles to be activated to provide a particular set of permissions requested by a user. It is a key issue related to efficiently handling users' access requests. Previous definitions of the UAQ problem have considered only the optimization objective for the number of permissions whereas the optimization objective for the number of roles, which is also equally important, has been largely ignored. Moreover, little attention has been given to the computational complexity of the UAQ problem that considers the optimization objectives for both the numbers of permissions and roles. In this paper, we propose a more comprehensive definition of the UAQ problem, which includes irreducibility, role-cardinality and permission-cardinality constraints, and consider both these optimization objectives together. In particular, we study the computational complexity of the UAQ problem by dividing it into three subcases: exact match, safe match and available match, and show that many instances in each subcase with additional constraints are intractable. We also propose an approach for solving the intractable cases of the UAQ problem; the proposed approach incorporates static pruning, preprocessing and the depth-first search based algorithm to significantly reduce the running time.
ISSN:0167-4048
1872-6208
DOI:10.1016/j.cose.2014.10.003