Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-07T03:28:39.646Z Has data issue: false hasContentIssue false
  • English
  • Français

Model checking usage policies†

Published online by Cambridge University Press:  10 November 2014

MASSIMO BARTOLETTI ,
PIERPAOLO DEGANO ,
GIAN LUIGI FERRARI  and
ROBERTO ZUNINO
MASSIMO BARTOLETTI
Affiliation:
Dipartimento di Matematica e Informatica, Università degli Studi di Cagliari, via Ospedale 72, 09124 Cagliari, Italy Email: bart@unica.it
PIERPAOLO DEGANO
Affiliation:
Dipartimento di Informatica, Università di Pisa, Italy
GIAN LUIGI FERRARI
Affiliation:
Dipartimento di Informatica, Università di Pisa, Italy
ROBERTO ZUNINO
Affiliation:
DISI, Università di Trento and COSBI, Italy
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study usage automata, a formal model for specifying policies on the usage of resources. Usage automata extend finite state automata with some additional features, parameters and guards, that improve their expressivity. We show that usage automata are expressive enough to model policies of real-world applications. We discuss their expressive power, and we prove that the problem of telling whether a computation complies with a usage policy is decidable. The main contribution of this paper is a model checking technique for usage automata. The model is that of usages, i.e. basic processes that describe the possible patterns of resource access and creation. In spite of the model having infinite states, because of recursion and resource creation, we devise a polynomial-time model checking technique for deciding when a usage complies with a usage policy.

Information

Type
Special Issue: Objects and Services
Information
Mathematical Structures in Computer Science , Volume 25 , Issue 3 , March 2015 , pp. 710 - 763
Copyright
Copyright © Cambridge University Press 2014 

Footnotes

†

This work has been partially supported by EU under grant FP7-257414 (Project ASCENS), and by Aut. Region of Sardinia under grants L.R.7/2007 CRP2-120 (Project TESLA) and CRP-17285 (Project TRICS).

References

Abadi, M. and Fournet, C. (2003) Access control based on execution history. In: Proceedings of 10th Annual Network and Distributed System Security Symposium, The Internet Society.Google Scholar
Alpern, B. and Schneider, F. B. (1987) Recognizing safety and liveness. Distributed Computing 2 (3)117–126.CrossRefGoogle Scholar
Baier, C. and Katoen, J.-P. (2008) Principles of Model Checking, MIT Press.Google Scholar
Banerjee, A. and Naumann, D. A. (2004) History-based access control and secure information flow. In: Workshop on Construction and Analysis of Safe, Secure and Interoperable Smart Cards (CASSIS). Springer Lecture Notes in Computer Science 3362 27–48.CrossRefGoogle Scholar
Bartoletti, M. (2009) Usage automata. In: Proceedings of the ARSPA-WITS. Springer Lecture Notes in Computer Science 5511 52–69.Google Scholar
Bartoletti, M., Caires, L., Lanese, I., Mazzanti, F., Sangiorgi, D., Vieira, H. T. and Zunino, R. (2011) Tools and verification. In: Wirsing, M. and Hölzl, M. (eds.) Rigorous Software Engineering for Service-Oriented Systems - Results of the Sensoria project on Software Engineering for Service-Oriented Computing. Lecture Notes in Computer Science 6582 408–427.CrossRefGoogle Scholar
Bartoletti, M., Costa, G., Degano, P., Martinelli, F. and Zunino, R. (2009a) Securing Java with local policies. Journal of Object Technology 8 (4)5–32. Tool demonstration at BYTECODE 2009. Electronic Notes in Theoretical Computer Science 253 (5) 145–151. Available at http://jalapa.sourceforge.netGoogle Scholar
Bartoletti, M., Degano, P. and Ferrari, G. (2009b) Planning and verifying service composition. Extended version of Proceedings of 18th Computer Security Foundations Workshop (CSFW'05). Journal of Computer Security 17 (5)799–837.Google Scholar
Bartoletti, M., Degano, P. and Ferrari, G.-L. (2005) History based access control with local policies. In: Proceedings of 8th International Conference on Foundations of Software Science and Computational Structures, (FOSSACS). Springer Lecture Notes in Computer Science 3441 316–332.CrossRefGoogle Scholar
Bartoletti, M., Degano, P. and Ferrari, G.-L. (2006) Types and effects for secure service orchestration. In: Proceedings of 19th CSFW, IEEE Computer Society 57–69.Google Scholar
Bartoletti, M., Degano, P., Ferrari, G.-L. and Zunino, R. (2008a) Model checking usage policies. In: Proceedings of Trustworthy Global Computing (TGC). Springer Lecture Notes in Computer Science 5474 19–35.Google Scholar
Bartoletti, M., Degano, P., Ferrari, G.-L. and Zunino, R. (2008b) Semantics-based design for secure web services. IEEE Transactions on Software Engineering 34 (1)33–49.Google Scholar
Bartoletti, M., Degano, P., Ferrari, G. L. and Zunino, R. (2009c) Local policies for resource usage analysis. Extended version of Proceedings of FOSSACS'07. ACM Transactions on Programming Languages and Systems 31 (6)23:1–23:43.Google Scholar
Bauer, L., Ligatti, J. and Walker, D. (2002). More Enforceable Security Policies. In: More Enforceable Security Policies: proceedings of the FLoC'02 workshop on Foundations of Computer Security. Cervesato, Iliano (editor). Copenhagen, Denmark: DIKU Technical Report, 95–104. Available at http://www.cs.princeton.edu/~jligatti/papers/mesp.pdfGoogle Scholar
Bauer, L., Ligatti, J. and Walker, D. (2005) Composing security policies with Polymer. In: Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), ACM Press 305–314.Google Scholar
Bergstra, J. A. and Klop, J. W. (1985) Algebra of communicating processes with abstraction. Theoretical Computer Science 37 77–121.Google Scholar
Brewer, D. F. C. and Nash, M. J. (1989) The Chinese wall security policy. In: Proceedings of IEEE Symposium on Security and Privacy 206–214.Google Scholar
Christensen, S. (1993) Decidability and Decomposition in Process Algebras, Ph.D. thesis, Edinburgh University.Google Scholar
Ciancia, V. and Tuosto, E. (2009) A novel class of automata for languages on infinite alphabets. Technical Report CS-09-003, Department of Computer Science, University of Leicester.Google Scholar
Degano, P., Ferrari, G. L. and Mezzetti, G. (2011) On quantitative security policies. In: Proceedings of PaCT. Springer Lecture Notes in Computer Science 6873 23–39.Google Scholar
Degano, P., Ferrari, G. L. and Mezzetti, G. (2012) Nominal Automata for Resource Usage Control. CIAA 125–137. Available at http://dx.doi.org/10.1007/978-3-642-31606-7_11Google Scholar
Edjlali, G., Acharya, A. and Chaudhary, V. (1999) History-based access control for mobile code. In: Secure Internet Programming. Lecture Notes in Computer Science 1603 38–48.Google Scholar
Erlingsson, Ú. and Schneider, F. B. (1999) SASI enforcement of security policies: A retrospective. In: Proceedings of 7th New Security Paradigms Workshop 87–95.Google Scholar
Esparza, J. (1994) On the decidability of model checking for several μ-calculi and Petri nets. In: Proceedings of 19th International Colloquium on Trees in Algebra and Programming. Springer Lecture Notes in Computer Science 787 115–129.CrossRefGoogle Scholar
Fournet, C. and Gordon, A. D. (2003) Stack inspection: Theory and variants. ACM Transactions on Programming Languages and Systems 25 (3)360–399.Google Scholar
Grumberg, O., Kupferman, O. and Sheinvald, S. (2010) Variable automata over infinite alphabets. In: Language and Automata Theory and Applications. Springer Lecture Notes in Computer Science 6031 561–572.Google Scholar
Hillston, J. (1996) A Compositional Approach to Performance Modelling, Cambridge University Press.Google Scholar
Igarashi, A. and Kobayashi, N. (2002) Resource usage analysis. In: Proceedings of 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), ACM Press.Google Scholar
Kaminski, M. and Francez, N. (1994) Finite-memory automata. Theoretical Computer Science 134 (2)329–363.Google Scholar
Kwiatkowska, M., Norman, G. and Parker, D. (2009) PRISM: Probabilistic model checking for performance and reliability analysis. ACM SIGMETRICS Performance Evaluation Review 36 (4)40–45.Google Scholar
Martinelli, F. and Mori, P. (2007) Enhancing Java security with history based access control. In: Foundations of Security Analysis and Design (FOSAD) Tutorial Lectures. Springer Lecture Notes in Computer Science 4677 135–159.Google Scholar
Mayr, R. (1998) Decidability and Complexity of Model Checking Problems for Infinite-State Systems, Ph.D. thesis, Technische Universität München.Google Scholar
Milner, R., Parrow, J. and Walker, D. (1992) A calculus of mobile processes, I and II', Information and Computation 100 (1)1–77.Google Scholar
Montanari, U. and Pistore, M. (2005) History-dependent automata: An introduction. In: Proceedings of SFM. Springer Lecture Notes in Computer Science 3465 1–28.Google Scholar
Pandey, R. and Hashii, B. (1999) Providing fine-grained access control for Java programs. In: Proceedings of 13th European Conference on Object-Oriented Programming (ECOOP). Springer Lecture Notes in Computer Science 1628 449–473.Google Scholar
Samarati, P. and de Capitani di Vimercati, S. (2001) Access control: Policies, models, and mechanisms. In: Foundations of Security Analysis and Design (FOSAD) Tutorial Lectures. Springer Lecture Notes in Computer Science 2171 137–196.Google Scholar
Sandhu, R. and Samarati, P. (1994) Access control: Principles and practice. IEEE Communications Magazine 32 40–48.Google Scholar
Schneider, F. B. (2000) Enforceable security policies. ACM Transactions on Information and System Security (TISSEC) 3 (1)30–50.Google Scholar
Segoufin, L. (2006) Automata and logics for words and trees over an infinite alphabet In: Proceedings of 20th International Workshop on Computer Science Logic (CSL). Springer Lecture Notes in Computer Science 4207 41–57.Google Scholar
Shemesh, Y. and Francez, N. (1994) Finite-state unification automata and relational languages. Information and Computation 114 (2)192–213.Google Scholar
Skalka, C. and Smith, S. (2004) History effects and verification. In: Proceedings of Asian Symposium on Programming Languages and Systems (APLAS). Springer Lecture Notes in Computer Science 3302 107–128.Google Scholar
Wallach, D.S., Appel, A.W. and Felten, E.W. (2001) SAFKASI: A security mechanism for language-based systems. ACM Transactions on Software Engineering and Methodology (TOSEM) 9 (4)341–378.Google Scholar