Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T04:50:46.407Z Has data issue: false hasContentIssue false

GEM: A distributed goal evaluation algorithm for trust management

Published online by Cambridge University Press:  03 December 2012

DANIEL TRIVELLATO
Affiliation:
Eindhoven University of Technology, Eindhoven, The Netherlands (e-mail: [email protected], [email protected])
NICOLA ZANNONE
Affiliation:
Eindhoven University of Technology, Eindhoven, The Netherlands (e-mail: [email protected], [email protected])
SANDRO ETALLE
Affiliation:
Eindhoven University of Technology, Eindhoven, The Netherlands and University of Twente, Enschede, The Netherlands (e-mail: [email protected])

Abstract

Trust management is an approach to access control in distributed systems where access decisions are based on policy statements issued by multiple principals and stored in a distributed manner. In trust management, the policy statements of a principal can refer to other principals' statements; thus, the process of evaluating an access request (i.e., a goal) consists of finding a “chain” of policy statements that allows the access to the requested resource. Most existing goal evaluation algorithms for trust management either rely on a centralized evaluation strategy, which consists of collecting all the relevant policy statements in a single location (and therefore they do not guarantee the confidentiality of intensional policies), or do not detect the termination of the computation (i.e., when all the answers of a goal are computed). In this paper, we present GEM, a distributed goal evaluation algorithm for trust management systems that relies on function-free logic programming for the specification of policy statements. GEM detects termination in a completely distributed way without disclosing intensional policies, thereby preserving their confidentiality. We demonstrate that the algorithm terminates and is sound and complete with respect to the standard semantics for logic programs.

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2012 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alves, M., Damasio, C. V., Nejdl, W. and Olmedilla, D. 2006. A distributed tabling algorithm for rule based policy systems. In Proc. of International Workshop on Policies for Distributed Systems and Networks. IEEE Computer Society, Washington, DC, 123132.Google Scholar
Apt, K. R. 1990. Logic programming. In Handbook of Theoretical Computer Science (vol. B): Formal Models and Semantics. MIT Press, Cambridge, MA, 493574.Google Scholar
Apt, K. R., Blair, H. A. and Walker, A. 1988. Towards a Theory of Declarative Knowledge. Morgan Kaufmann, San Francisco, CA, 89148.Google Scholar
Apt, K. R. and Bol, R. N. 1994. Logic programming and negation: A survey. Journal of Logic Programming 19–20, 971.CrossRefGoogle Scholar
Apt, K. R. and Marchiori, E. 1994. Reasoning about Prolog programs: From modes through types to assertions. Formal Aspects of Computing 6, 6A, 743765.Google Scholar
Becker, M. Y. 2005. Cassandra: Flexible Trust Management and Its Application to Electronic Health Records. PhD thesis, Computer Laboratory, University of Cambridge, UK.Google Scholar
Becker, M. Y., Fournet, C. and Gordon, A. D. 2010. SecPAL: Design and semantics of a decentralized authorization language. Journal of Computer Security 18 , 619665.Google Scholar
Becker, M. Y., Mackay, J. F. and Dillaway, B. 2009. Abductive authorization credential gathering. In Proc. of the 10th International Conference on Policies for Distributed Systems and Networks. Ieee Press, Piscataway, NJ, 18.Google Scholar
Blaze, M., Feigenbaum, J. and Lacy, J. 1996. Decentralized trust management. In Proc. of the IEEE Symposium on Security and Privacy. IEEE Computer Society, 164173.Google Scholar
Böhm, K., Etalle, S., den Hartog, J., Hütter, C., Trabelsi, S., Trivellato, D. and Zannone, N. 2010. Flexible architecture for privacy-aware trust management. Journal of Theoretical and Applied Electronic Commerce Research 5, 7796.Google Scholar
Bradshaw, R. W., Holt, J. E. and Seamons, K. E. 2004. Concealing complex policies with hidden credentials. In Proc. of the 11th Conference on Computer and Communications Security, Atluri, V., Pfitzmann, B. and McDaniel, P. D., Eds. ACM, New York, 146157.Google Scholar
Bry, F. 1990. Query evaluation in recursive databases: Bottom-up and top-down reconciled. Data Knowl. Eng. 5, 4, 289312.Google Scholar
Chen, Y. 1997. Magic sets and stratified databases. International Journal of Intelligent Systems 12, 3, 203231.3.0.CO;2-T>CrossRefGoogle Scholar
Chen, W. and Warren, D. S. 1996. Tabled evaluation with delaying for general logic programs. Journal of the ACM 43, 1, 2074.CrossRefGoogle Scholar
Costantini, S. 2001. Comparing different graph representations of logic programs under the Answer Set semantics. In Proc. of the 1st International Workshop on Answer Set Programming, Provetti, A. and Son, T. C., Eds. AAAI Press. Available at http://www.cs.nmsu.edu/~tson/ASP2001/7.ps Google Scholar
Czenko, M. and Etalle, S. 2007. Core TuLiP logic programming for trust management. In Proc. of the 23rd International Conference on Logic Programming, Dahl, V. and Niemelä, I., Eds. LNCS, vol. 4670. Springer-Verlag, Berlin, 380394.Google Scholar
Czenko, M., Tran, H., Doumen, J., Etalle, S., Hartel, P. and den Hartog, J. 2006. Nonmonotonic trust management for P2P applications. Electronic Notes in Theoretical Computer Science 157, 3 (May), 113130.Google Scholar
Damásio, C. V. 2000. A distributed tabling system. In Proc. of the 2nd Conference on Tabulation in Parsing and Deduction. 65–75.Google Scholar
Di Marzo Serugendo, G., Foukia, N., Hassas, S., Karageorgos, A., Mostéfaoui, S. K., Rana, O. F., Ulieru, M., Valckenaers, P. and van Aart, C. 2004. Self-organisation: Paradigms and applications. Engineering Self-Organising Systems 2977, 119.Google Scholar
Dong, C. and Dulay, N. 2010. Shinren: Non-monotonic trust management for distributed systems. In Proc. of the 4th International Conference on Trust Management, Nishigaki, M., Jøsang, A. Murayama, Y. and Marsh, S., Eds. IFIP, vol. 321. Springer, Boston, MA, 125140.Google Scholar
Ellison, C., Frantz, B., Lampson, B., Rivest, R., Thomas, B. and Ylonen, T. 1999. SPKI Certificate Theory, RFC Editor, United States.Google Scholar
Fitting, M. 1985. A Kripke–Kleene semantics for general logic programs. Journal of Logic Programming 2, 4, 295312.Google Scholar
Frikken, K., Atallah, M. and Li, J. 2006. Attribute-based access control with hidden policies and hidden credentials. IEEE Transactions on Computers 55, 12591270.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of the 5th International Conference and Symposium on Logic Programming, (ICLP'88), Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, Cambridge, MA, 10701080.Google Scholar
Guo, H.-F. and Gupta, G. 2001. A simple scheme for implementing tabled logic programming systems based on dynamic reordering of alternatives. In Proc. of the 17th International Conference on Logic Programming, Codognet, P., Ed. Springer-Verlag, London, 181196.Google Scholar
Hoch, J. and Shamir, A. 2008. On the strength of the concatenated hash combiner when all the hash functions are weak. In Automata, Languages and Programming, Aceto, L., Damgård, I., Goldberg, L. A., Halldórsson, M. M., Ingólfsdóttir, A. and Walukiewicz, I., Eds. LNCS, vol. 5126. Springer-Verlag, Berlin, 616630.CrossRefGoogle Scholar
Hu, R. 1997. Efficient Tabled Evaluation of Normal Logic Programs in a Distributed Environment. PhD thesis, State University of New York at Stony Brook.Google Scholar
Hulin, G. 1989. Parallel processing of recursive queries in distributed architectures. In Proc. of the 15th International Conference on Very Large Data Bases, Apers, P. M. G. and Wiederhold, G., Eds. Morgan Kaufmann Publishers Inc., San Francisco, CA, 8796.Google Scholar
Jim, T. and Suciu, D. 2001. Dynamically distributed query evaluation. In Proc. of the 20th Symposium on Principles of database systems, Buneman, P., Ed. ACM, New York, 2839.Google Scholar
Koshutanski, H. and Massacci, F. 2008. Interactive access control for autonomic systems: From theory to implementation. ACM Transactions on Autonomous and Adaptive Systems 3, 3, 131.Google Scholar
Kowalski, R. 1974. Predicate logic as a programming language. Information Processing 74, 556574.Google Scholar
Lee, A. J., Minami, K. and Borisov, N. 2009. Confidentiality-preserving distributed proofs of conjunctive queries. In Proc. of the 4th International Symposium on Information, Computer, and Communications Security, Li, W., Susilo, W., Tupakula, U. K., Safavi-Naini, R. and Varadharajan, V., Eds. ACM, New York, 287297.Google Scholar
Lee, A. J., Minami, K. and Winslett, M. 2010. On the consistency of distributed proofs with hidden subtrees. ACM Transactions on Information and System Security 13, 3, 132.Google Scholar
Leuschel, M., Martens, B. and Sagonas, K. 1998. Preserving termination of tabled logic programs while unfolding. In Proc. of the 7th International Workshop on Logic Program Synthesis and Transformation, Fuchs, N. E., Ed. LNCS, vol. 1463. Springer-Verlag, Berlin, 189205.Google Scholar
Li, N. and Mitchell, J. C. 2003. Datalog with constraints: A foundation for trust management languages. In Proc. of the 5th International Symposium on Practical Aspects of Declarative Languages, Dahl, V. and Wadler, P., Eds. LNCS, vol. 2562. Springer-Verlag, London, 5873.Google Scholar
Li, N., Winsborough, W. H. and Mitchell, J. C. 2003. Distributed credential chain discovery in trust management. Journal of Computer Security 11, 1, 3586.Google Scholar
Minami, K., Borisov, N., Winslett, M. and Lee, A. J. 2011. Confidentiality-preserving proof theories for distributed proof systems. In Proc. of the 6th Symposium on Information, Computer and Communications Security, Cheung, B. S. N., Hui, L. C. K., Sandhu, R. S. and Wong, D. S., Eds. ACM, New York, 145154.Google Scholar
Park, D. 1969. Fixpoint induction and proofs of program properties. Machine Intelligence 5, 5978.Google Scholar
Przymusinska, H. and Przymunsinski, T. C. 1990. Weakly stratified logic programs. Fundamenta Informaticae 13, 1, 5165.CrossRefGoogle Scholar
Przymusinski, T. C. 1988. On the Declarative Semantics of Deductive Databases and Logic Programs. Morgan Kaufmann, San Francisco, CA, 193216.Google Scholar
Przymusinski, T. 1990. The well-founded semantics coincides with three-valued stable semantics. Fundamenta Informaticae 13, 4, 445463.Google Scholar
Ramakrishnan, R. 1991. Magic templates: A spellbinding approach to logic programs. Journal of Logic Programming 11, 189216.Google Scholar
Rocha, R., Silva, F. and Costa, V. S. 2005. On applying or-parallelism and tabling to logic programs. Theory and Practice of Logic Programming 5, 1–2, 161205.Google Scholar
Seamons, K. E., Winslett, M. and Yu, T. 2001. Limiting the disclosure of access control policies during automated trust negotiation. In Proc. of the Network and Distributed System Security Symposium. The Internet Society, San Diego, CA.Google Scholar
Shen, Y.-D., Yuan, L.-Y., You, J.-H. and Zhou, N.-F. 2001. Linear tabulated resolution based on Prolog control strategy. Theory and Practice of Logic Programming 1, 71103.Google Scholar
Stine, K., Kissel, R., Barker, W. C., Lee, A. and Fahlsing, J. 2008. Guide for Mapping Types of Information and Information Systems to Security Categories. Special Publication SP 800-60 Rev. 1, National Institute of Standards and Technology (NIST), Gaithersburg, MD.Google Scholar
Swift, T. and Warren, D. S. 2012. XSB: Extending prolog with tabled logic programming. Theory and Practice of Logic Programming 12, 1–2, 157187.Google Scholar
Tamaki, H. and Sato, T. 1986. OLD resolution with tabulation. In Proc. of the 3rd International Conference on Logic Programming, Shapiro, E. Y., Ed. Springer-Verlag, London, 8498.Google Scholar
Trivellato, D., Zannone, N. and Etalle, S. 2011. A security framework for systems of systems. In Proc. of the 12th International Conference on Policies for Distributed Systems and Networks. IEEE Computer Society, Piscataway, NJ.Google Scholar
Van Gelder, A., Ross, K. A. and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of the ACM 38, 619649.CrossRefGoogle Scholar
Vieille, L. 1987. A database-complete proof procedure based on SLD-resolution. In Proc. of the 4th International Conference on Logic Programming, Lassez, J. L., Ed. MIT Press, Cambridge, MA, 74103.Google Scholar
Winsborough, W. H. and Li, N. 2002. Protecting sensitive attributes in automated trust negotiation. In Proc. of Workshop on Privacy in the Electronic Society, Jajodia, S. and Samarati, P., Eds. ACM, New York, 4151.Google Scholar
Winsborough, W. H., Seamons, K. E. and Jones, V. E. 2000. Automated trust negotiation. In Proc. of the DARPA Information Survivability Conference and Exposition. Vol. 1. IEEE Computer Society, Los Alamitos, CA, 88102.Google Scholar
Winslett, M. 2003. An introduction to trust negotiation. In Proc. of International Conference on Trust Management, Nixon, P. and Terzis, S., Eds. LNCS, vol. 2692. Springer-Verlag, Berlin, 275283.Google Scholar
Yu, T. and Winslett, M. 2003. A unified scheme for resource protection in automated trust negotiation. In Proc. of the IEEE Symposium on Security and Privacy. IEEE Computer Society, Washington, DC, 110122.Google Scholar
Zhang, C. C. and Winslett, M. 2008. Distributed authorization by multiparty trust negotiation. In Proc. of the 13th European Symposium on Research in Computer Security, Jajodia, S. and López, J., Eds. LNCS, vol. 5283. Springer-Verlag, Berlin, 282299.Google Scholar
Zhou, N.-F. and Sato, T. 2003. Efficient fixpoint computation in linear tabling. In Proc. of the 5th International Conference on Principles and Practice of Declarative Programming, Sagonas, K. and Miller, D., Eds. ACM, New York, 275283.Google Scholar
Supplementary material: PDF

Daniel Trivellato Supplementary Material

Appendix

Download Daniel Trivellato Supplementary Material(PDF)
PDF 255.2 KB