approvability
Consider a set of users who collectively perform a sequence of actions to complete a task. Separation of duty constraints hold when there are restrictions which are intended to require that not all actions are performed by the same user.The approvability graph is introduced to describe the sequences of actions which correspond to one or more tasks. The graph can represent multiple possible outcomes (different completions from the same starting point) as well as allowing for repeated actions. Hence, the graph describes a set of sequences, not necessarily finite, which define when a task is complete.The graph-based mechanism also describes separation of duty constraints between different actions, ensuring that different actions are performed by different users. (It can also require different actions to be performed by the same user.)Algorithms are presented to analyze the number of users needed to ensure that any such sequence can be completed, even in the presence of loops or alternative outcomes. The various properties that arise in approval sequences are then explored to characterize well formed systems and to examine their complexity. In particular, we show how to achieve bounds on the number of users which must be members of each role.Determining the minimum number of users to complete a dynamic separation of duty task is proven to be NP-Complete.
separation of duty authorization authorization properties