Towards an Efficient Approximate Solution for the Weighted User Authorization Query Problem

Jianfeng LU  Zheng WANG  Dewu XU  Changbing TANG  Jianmin HAN  

IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.8   pp.1762-1769
Publication Date: 2017/08/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016ICP0002
Type of Manuscript: Special Section PAPER (Special Section on Information and Communication System Security)
Category: Access Control
role-based access control,  user authorization query,  weight,  constraint,  genetic algorithm,  

Full Text: PDF>>
Buy this Article

The user authorization query (UAQ) problem determines whether there exists an optimum set of roles to be activated to provide a set of permissions requested by a user. It has been deemed as a key issue for efficiently handling user's access requests in role-based access control (RBAC). Unfortunately, the weight is a value attached to a permission/role representing its importance, should be introduced to UAQ, has been ignored. In this paper, we propose a comprehensive definition of the weighted UAQ (WUAQ) problem with the role-weighted-cardinality and permission-weighted-cardinality constraints. Moreover, we study the computational complexity of different subcases of WUAQ, and show that many instances in each subcase are intractable. In particular, inspired by the idea of the genetic algorithm, we propose an algorithm to approximate solve an intractable subcase of the WUAQ problem. An important observation is that this algorithm can be efficiently modified to handle the other subcases of the WUAQ problem. The experimental results show the advantage of the proposed algorithm, which is especially fit for the case that the computational overhead is even more important than the accuracy in a large-scale RBAC system.