Recent work has shown that many problems of satisfiability and resiliency in
workflows may be viewed as special cases of the authorization policy existence
problem (APEP), which returns an authorization policy if one exists and ‘No’
otherwise. However, in many practical settings it would be more useful to
obtain a ‘least bad’ policy than just a ‘No’, where ‘least bad’ is
characterized by some numerical value indicating the extent to which the policy
violates the base authorization relation and constraints. Accordingly, we
introduce the Valued APEP, which returns an authorization policy of minimum
weight, where the (non-negative) weight is determined by the constraints
violated by the returned solution. We then establish a number of results
concerning the parameterized complexity of Valued APEP. We prove that the
problem is fixed-parameter tractable (FPT) if the set of constraints satisfies
two restrictions, but is intractable if only one of these restrictions holds.
(Most constraints known to be of practical use satisfy both restrictions.) We
also introduce a new type of resiliency for workflow satisfiability problem,
show how it can be addressed using Valued APEP and use this to build a set of
benchmark instances for Valued APEP. Following a set of computational
experiments with two mixed integer programming (MIP) formulations, we
demonstrate that the Valued APEP formulation based on the user profile concept
has FPT-like running time and usually significantly outperforms a naive
formulation.

By admin