Jason Crampton
Gregory Gutin
Abstract
A workflow specification defines a set of steps and the order in which these steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of these steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications and for the construction of runtime reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li [2010] using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this article, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely accepted complexity-theoretical assumption holds.
- American National Standards Institute. 2004. ANSI INCITS 359-2004 for Role Based Access Control. American National Standards Institute.Google Scholar
- Armando, A., Giunchiglia, E., and Ponta, S. E. 2009. Formal specification and automatic analysis of business processes under authorization constraints: An action-based approach. In Proceedings of the 6th International Conference on Trust, Privacy and Security in Digital Business. S. Fischer-Hubner, C. Lambrinoudakis, and G. Pernul Eds., Lecture Notes in Computer Science, vol. 5695, Springer, 63--72. Google ScholarDigital Library
- Basin, D. A., Burri, S. J., and Karjoth, G. 2011. Obstruction-free authorization enforcement: Aligning security with business objectives. In Proceedings of 24th IEEE Symposium on Computer Security Foundations. IEEE Computer Society, 99--113. Google ScholarDigital Library
- Basin, D. A., Burri, S. J., and Karjoth, G. 2012. Optimal workflow-aware authorizations. In Proceedings of the 17th ACM Symposium on Access Control Models and Technologies (SACMAT’12). V. Atluri, J. Vaidya, A. Kern, and M. Kantarcioglu Eds., ACM Press, New York, 93--102. Google ScholarDigital Library
- Bell, D. and LaPadula, L. 1976. Secure computer systems: Unified exposition and multics interpretation. Tech. rep. MTR-2997, Mitre Corporation, Bedford, MA.Google Scholar
- Bertino, E., Ferrari, E., and Atluri, V. 1999. The specification and enforcement of authorization constraints in workflow management systems. ACM Trans. Inf. Syst. Secur. 2, 1, 65--104. Google ScholarDigital Library
- Bertino, E., Bonatti, P. A., and Ferrari, E. 2001. TRBAC: A temporal role-based access control model. ACM Trans. Inf. Syst. Secur. 4, 3, 191--233. Google ScholarDigital Library
- Björklund, A., Husfeldt, T., and Koivisto, M. 2009. Set partitioning via inclusion-exclusion. SIAM J. Comput. 39, 2, 546--563. Google ScholarDigital Library
- Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. 2009. On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 8, 423--434. Google ScholarDigital Library
- Bodlaender, H. L., Jansen, B. M. P., and Kratsch, S. 2011a. Cross-composition: A new technique for kernelization lower bounds. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS’11). T. Schwentick and C. Durr Eds., LIPIcs Series, vol. 9, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 165--176.Google Scholar
- Bodlaender, H. L., Thomassé, S., and Yeo, A. 2011b. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412, 35, 4570--4578. Google ScholarDigital Library
- Brewer, D. F. C. and Nash, M. J. 1989. The chinese wall security policy. In Proceedings of the IEEE Symposium on Security and Privacy. IEEE Computer Society, 206--214.Google Scholar
- Crampton, J. 2005. A reference monitor for workflow systems with constrained task execution. In Proceedings of the 10th ACM Symposium on Access Control Models and Technologies (SACMAT’05). E. Ferrari and G.-J. Ahn Eds., ACM Press, New York, 38--47. Google ScholarDigital Library
- Crampton, J. and Gutin, G. 2013. Constraint expressions and workflow satisfiability. http://arxiv.org/abs/1301.3402. Google ScholarDigital Library
- Crampton, J., Gutin, G., and Yeo, A. 2012. On the parameterized complexity of the workflow satisfiability problem. In Proceedings of the ACM Conference on Computer and Communications Security. T. Yu, G. Danezis, and V. D. Gligor Eds., ACM Press, New York, 857--868. Google ScholarDigital Library
- Crowston, R., Gutin, G., Jones, M., Raman, V., and Saurabh, S. 2012. Parameterized complexity of maxsat above average. In Proceedings of the 10th Latin American International Conference on Theoretical Informatics (LATIN’12). D. Fernandez-Baca Ed., Lecture Notes in Computer Science, vol. 7256, Springer, 184--194. Google ScholarDigital Library
- Dom, M., Lokshtanov, D., and Saurabh, S. 2009. Incompressibility through colors and ids. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP’09). S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, and W. Thomas Eds., Lecture Notes in Computer Science, vol. 5555, Springer, 378--389. Google ScholarDigital Library
- Downey, R. G. and Fellows, M. R. 1999. Parameterized Complexity. Springer. Google ScholarDigital Library
- Fellows, M. R., Friedrich, T., Hermelin, D., Narodytska, N., and Rosamond, F. A. 2011. Constraint satisfaction problems: Convexity makes all different constraints tractable. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11). T. Walsh Ed., AAAI, 522--527. Google ScholarDigital Library
- Flum, J. and Grohe, M. 2006. Parameterized Complexity Theory. Springer. Google ScholarDigital Library
- Impagliazzo, R., Paturi, R., and Zane, F. 2001. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 4, 512--530. Google ScholarDigital Library
- Joshi, J., Bertino, E., Latif, U., and Ghafoor, A. 2005. A generalized temporal role-based access control model. IEEE Trans. Knowl. Data Engin. 17, 1, 4--23. Google ScholarDigital Library
- Kaufman, T., Krivelevich, M., and Ron, D. 2004. Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput. 33, 6, 1441--1483. Google ScholarDigital Library
- Kohler, M. and Schaad, A. 2008. Proactive access control for business process-driven environments. In Proceedings of the Annual Computer Security Applications Conference (ACSAC’08). IEEE Computer Society, 153--162. Google ScholarDigital Library
- Li, N., Tripunitara, M. V., and Bizri, Z. 2007. On mutually exclusive roles and separation-of-duty. ACM Trans. Inf. Syst. Secur. 10, 2. Google ScholarDigital Library
- Moffett, J. D. and Lupu, E. 1999. The uses of role hierarchies in access control. In Proceedings of the ACM Workshop on Role-Based Access Control. ACM Press, New York, 153--160. Google ScholarDigital Library
- Sandhu, R. S., Coyne, E. J., Feinstein, H. L., and Youman, C. E. 1996. Role-based access control models. IEEE Comput. 29, 2, 38--47. Google ScholarDigital Library
- Simon, R. T. and Zurko, M. E. 1997. Separation of duty in role-based environments. In Proceedings of the 10th Computer Security Foundations Workshop (CSFW’97). IEEE Computer Society, 183--194. Google ScholarDigital Library
- Szeider, S. 2004. Minimal unsatisfiable formulas with bounded clause-variable difference are fixed parameter tractable. J. Comput. Syst. Sci. 69, 4, 656--674. Google ScholarDigital Library
- Tsang, E. P. K. 1993. Foundations of Constraint Satisfaction. Academic Press.Google Scholar
- van der Aalst, W. M. P., Ter Hofstede, A. H. M., Kiepuszewski, B., and Barros, A. P. 2003. Workflow patterns. Distrib. Parallel Databases 14, 1, 5--51. Google ScholarDigital Library
- Wang, Q. and Li, N. 2010. Satisfiability and resiliency in workflow authorization systems. ACM Trans. Inf. Syst. Secur. 13, 4, 40. Google ScholarDigital Library
Index Terms
- On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem
Recommendations
Kernelization Lower Bounds Through Colors and IDs
In parameterized complexity, each problem instance comes with a parameter k, and a parameterized problem is said to admit a polynomial kernel if there are polynomial time preprocessing rules that reduce the input instance to an instance with size ...
Parameterized complexity dichotomy for Steiner Multicut
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...
On the parameterized complexity of the workflow satisfiability problem
CCS '12: Proceedings of the 2012 ACM conference on Computer and communications securityA workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of those steps. A workflow specification is said ...
Comments