On the satisfiability of authorization requirements in business process

Abstract

Satisfiability problem of authorization requirements in business process asks whether there exists an assignment of users to tasks that satisfies all the requirements, and methods were proposed to solve this problem. However, the proposed methods are inefficient in the sense that a step of the methods is searching all the possible assignments, which is time-consuming. This work proposes a method to solve the satisfiability problem of authorization requirements without browsing the assignments space. Our method uses improved separation of duty algebra (ISoDA) to describe a satisfiability problem of qualification requirements and quantification requirements (Separation of Duty and Binding of Duty requirements). Thereafter, ISoDA expressions are reduced into multi-mutual-exclusive expressions. The satisfiabilities of multi-mutual-exclusive expressions are determined by an efficient algorithm proposed in this study. The experiment shows that our method is faster than the state-of-the-art methods.

Keywords

satisfiability / authorization requirements / separation of duty / binding of duty / business process

References

[1] BeckerJ, Delfmann P, DietrichH-A , SteinhorstM, EggertM. Business process compliance checking —applying and evaluating a generic pattern matching approach for conceptual models in the financial sector. Information Systems Frontiers, 2016, 18(2): 359–405

[2] LyL T, Rinderle-Ma S, KnupleschD , DadamP. Monitoring business process compliance using compliance rule graphs.Lecture Notes in Computer Science, 2011, 7044: 82–99

[3] LyL T, Rinderle S, DadamP . Integration and verification of semantic constraints in adaptive process management systems. Data & Knowledge Engineering, 2008, 64(1): 3–23

[4] LiN H, WangQ H. Beyond separation of duty: an algebra for specifying high-level security policies. Journal of the ACM, 2008, 55(3): 1–46

[5] WolterC, SchaadA. Modeling of task-based authorization constraints in BPMN. In: Proceedings of International Conference on Business Process Management. 2007, 64–79

[6] BertinoE, Ferrari E, AtluriV . An authorization model for supporting the specification and enforcement of authorization constraints in workflow management systems. ACM Transactions on Information System Security, 1999, 2(1): 65–104

[7] CramptonJ, GutinG, Karapetyan. D . Valued workflow satisfiability problem. In: Proceedings of the 20th ACM Symposium on Access Control Models and Technologies. 2015, 3–13

[8] KarapetyanD, Gagarin A, GutinG . Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints. In: Proceedings of the 9th International Workshop on Frontiers in Algorithmics. 2015, 138–149

[9] MaceJ C, Morisset C, Van MoorselA . Modelling user availability in workflow resiliency analysis. In: Proceedings of Symposium and Bootcamp on the Science of Security. 2015, 1–10

[10] CohenD, Crampton J, GagarinA , GutinG, JonesM. Iterative plan construction for the workflow satisfiability problem. Journal of Artificial Intelligence Research, 2014, 51: 555–577

[11] CramptonJ, GutinG, YeoA. On the parameterized complexity and kernelization of the workflow satisfiability problem. ACM Transactions on Information and System Security, 2012, 16(1): 1518–1527

[12] CohenD, Crampton J, GagarinA , GutinG, JonesM. Algorithms for the workflow satisfiability problem engineered for counting constraints. Journal of Combinatorial Optimization, 2015: 1–22

[13] ZhaiZ N, WangG, ZhengZ J. Verification of (≠,＝) constrained workflow robustness based on satisfiability counting. Chinese Journal of Electronics, 2015, 43(11): 2298–2304

[14] BoY, XiaC H, LuoY, Tang Q. Static compliance checking beyond separation of duty constraints. In: Proceedings of the 9th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC). 2014, 171–178

[15] WangQ H, LiN H. Satisfiability and resiliency in workflow authorization systems. ACM Transactions on Information and System Security, 2010, 13(4): 747–759

[16] KohlerM, SchaadA. Avoiding policy-based deadlocks in business processes. In: Proceedings of International Conference on Availability, Reliability and Security. 2008, 709–716

[17] StrembeckM, Mendling J. Generic algorithms for consistency checking of mutual-exclusion and binding constraints in a business process context. Lecture Notes in Computer Science, 2010: 204–221

[18] TanK, Crampton J, GunterC A . The consistency of task-based authorization constraints in workflow systems. In: Proceedings of the 17th IEEE Computer Security Foundations Workshop. 2004, 155–169

[19] ArmandoA, PontaS E. Model checking authorization requirements in business processes. Computers and Security, 2014, 40(2): 1–22

[20] HoffmannJ, WeberI, GovernatoriG . On compliance checking for clausal constraints in annotated process models. Information Systems Frontiers, 2012, 14(2): 155–177

[21] BasinD, BurriS J, KarjothG. Dynamic enforcement of abstract separation of duty constraints. In: Proceedings of the 14th European Symposium on Research in Computer Security. 2009, 250–267

[22] BarlettaM, RaniseS, ViganoL. Verifying the interplay of authorization policies and workflow in service-oriented architectures. In: Proceedings of the 16th International Conference on Computational Science and Engineering. 2009, 289–296

[23] ArmandoA, PontaS E. Model checking of security-sensitive business processes.Lecture Notes in Computer Science, 2009, 5983: 66–80

[24] RodríguezA, Fernández-Medina E, PiattiniM . A BPMN extension for the modeling of security requirements in business processes. IEICE Transactions on Information and Systems, 2007, 90(4): 745–752

[25] CohenD, Crampton J, GagarinA , GutinG, JonesM. Engineering algorithms for workflow satisfiability problem with user-independent constraints. Lecture Notes in Computer Science, 2014, 8497: 48–59

RIGHTS & PERMISSIONS

2016 Higher Education Press and Springer-Verlag Berlin Heidelberg