Optimal workflow-aware authorizations

Balancing protection and empowerment is a central problem when specifying authorizations. The principle of least privilege, the classical approach to balancing these two conflicting objectives, says that users shall only be authorized to execute the tasks necessary to complete their job. However, when there are multiple authorization policies satisfying least privilege, which one should be chosen? In this paper, we model the tasks that users must execute as workflows, and the risk and cost associated with authorization policies and their administration. We then formulate the balancing of empowerment and protection as an optimization problem: finding a cost-minimizing authorization policy that allows a successful workflow execution. We show that finding an optimal solution for a role-based cost function is NP-complete. We support our results with a series of examples, which we also use to measure the performance of our prototype implementation. Copyright 2012 ACM.