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.

Separation-of-Duty (SoD) is a fundamental security principle for prevention of fraud and errors in computer security. It has been studied extensively in traditional access control models. However, the research of SoD policy in the recently proposed usage control (UCON) model has not been well studied. This paper formulates and studies the fundamental problem of static enforcement of static SoD (SSoD) policies in the context of UCONA, a sub-model of UCON only considering authorizations. Firstly, we define a set-based specification of SSoD policies, and the safety checking problem for SSoD in UCONA. Secondly, we study the problem of determining whether an SSoD policy is enforceable. Thirdly, we show that it is intractable (coNP-complete) to direct statically enforce SSoD policies in UCONA, while checking whether a UCONA state satisfies a set of static mutually exclusive attribute (SMEA) constraints is efficient, which provides a justification for using SMEA constraints to enforce SSoD policies. Finally, we introduce a indirect static enforcement for SSoD policies in UCONA. We show how to generate the least restrictive SMEA constraints for enforcing SSoD policies in UCONA, by using the attribute-level SSoD requirement as an intermediate step. The results are fundamental to understanding SSoD policies in UCON.