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 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.