Efficient run-time solving of RBAC user authorization queries: pushing the envelope.

The User Authorization Query (UAQ) Problem for Role- Based Access Control (RBAC) amounts to determining a set of roles to be activated in a given session in order to achieve some permissions while satisfying a collection of authorization constraints governing the activation of roles. Techniques ranging from greedy algorithms to reduction to (variants of) the propositional satisfiability (SAT) problem have been used to tackle the UAQ problem. Unfortunately, available techniques su er two major limitations that seem to question their practical usability. On the one hand, authorization constraints over multiple sessions or histories are not considered. On the other hand, the experimental evaluations of the various techniques are not satisfactory since they do not seem to scale to larger RBAC policies. In this paper, we describe a SAT-based technique to solve the UAQ problem which overcomes these limitations. First, we show how authorization constraints over multiple sessions and histories can be supported. Second, we carefully tune the reduction to the SAT problem so that most of the clauses need not to be generated at run-time but only in a pre-processing step. Finally, we present an extensive experimental evaluation of an implementation of our techniques on a significant set of UAQ problem instances that show the practical viability of our approach; e.g., problems with 300 roles are solved in less than a second.