A framework for concrete reputation-systems with applications to history-based access control

ABSTRACT

In a reputation-based trust-management system, agents maintain information about the past behaviour of other agents. This information is used to guide future trust-based decisions about interaction. However, while trust management is a component in security decision-making, many existing reputation-based trust-management systems provide no formal security-guarantees. In this extended abstract, we describe a mathematical framework for a class of simple reputation-based systems. In these systems, decisions about interaction are taken based on policies that are exact requirements on agents' past histories. We present a basic declarative language, based on pure-past linear temporal logic, intended for writing simple policies. While the basic language is reasonably expressive (encoding e.g. Chinese Wall policies) we show how one can extend it with quantification and parameterized events. This allows us to encode other policies known from the literature, e.g., `one-out-of-k'. The problem of checking a history with respect to a policy is efficient for the basic language, and tractable for the quantified language when policies do not have too many variables.

REFERENCES

• 1: M. Bartoletti, P. Degano, and G. L. Ferrari. History-based access control with local policies. In Foundations of Software Science and Computational Structures: 8th International Conference, FOSSACS 2005. Proceedings, pages 316--332. Springer, 2005.
• 2: Matt Blaze , Joan Feigenbaum , John Ioannidis , Angelos D. Keromytis, The role of trust management in distributed systems security, Secure Internet programming: security issues for mobile and distributed objects, Springer-Verlag, London, 2001
• 3: D. F. Brewer and M. J. Nash. The chinese wall security policy. In Proceedings from the 1989 IEEE Symposium on Security and Privacy, pages 206--214. IEEE Computer Society Press, 1989.
• 4: V. Cahill and E. Gray et al. Using trust for secure collaboration in uncertain environments. IEEE Pervasive Computing, 2(3):52--61, 2003.
• 5: V. Cahill and J.-M. Seigneur. The SECURE website. http://secure.dsg.cs.tcd.ie, 2004.
• 6: M. Carbone, M. Nielsen, and V. Sassone. A formal model for trust in dynamic networks. In Proceedings from Software Engineering and Formal Methods (SEFM'03). IEEE Computer Society Press, 2003.
• 7: M. Carbone, M. Nielsen, and V. Sassone. A calculus for trust management. In Proceedings from Foundations of Software Technology and Theoretical Computer Science: 24th International Conference (FSTTCS'04), pages 161--173. Springer, December 2004.
• 8: eBay Inc. The eBay website. http://www.ebay.com.
• 9: Guy Edjlali , Anurag Acharya , Vipin Chaudhary, History-based access control for mobile code, Proceedings of the 5th ACM conference on Computer and communications security, p.38-48, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288102]
• 10: Ú. Erlingsson and F. B. Schneider. SASI enforcement of security policies: A retrospective. In Proceedings from the 2000 DARPA Information Survivability Conference and Exposition, pages 1287--1295. IEEE Computer Society Press, 2000.
• 11: P. W. L. Fong. Access control by tracking shallow execution history. In Proceedings from the 2004 IEEE Symposium on Security and Privacy, pages 43--55. IEEE Computer Society Press, 2004.
• 12: Cédric Fournet , Andrew D. Gordon, Stack inspection: Theory and variants, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.3, p.360-399, May 2003 [doi>10.1145/641909.641912]
• 13: Klaus Havelund , Grigore Rosu, Synthesizing Monitors for Safety Properties, Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.342-356, April 08-12, 2002
• 14: A. Josang and R. Ismail. The beta reputation system. In Proceedings from the 15th Bled Conference on Electronic Commerce, Bled, 2002.
• 15: A. Josang, R. Ismail, and C. Boyd. A survey of trust and reputation for online service provision. Decision Support Systems, (to appear, preprint available online: http://security.dstc.edu.au/staff/ajosang), 2004.
• 16: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 17: K. Krukow, M. Nielsen, and V. Sassone. A framework for concrete reputation-systems. Technical Report RS-05-23, BRICS, University of Aarhus, July 2005.
• 18: Karl Krukow , Andrew Twigg, Distributed Approximation of Fixed-Points in Trust Structures, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.805-814, June 06-10, 2005 [doi>10.1109/ICDCS.2005.23]
• 19: François Laroussinie , Nicolas Markey , Ph. Schnoebelen, Temporal Logic with Forgettable Past, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.383-392, July 22-25, 2002
• 20: Mogens Nielsen , Karl Krukow, Towards a formal notion of trust, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.4-7, August 27-29, 2003, Uppsala, Sweden [doi>10.1145/888251.888253]
• 21: M. Nielsen and K. Krukow. On the formal modelling of trust in reputation-based systems. In J. Karhumäki, H. Maurer, G. Paun, and G. Rozenberg, editors, Theory Is Forever: Essays Dedicated to Arto Salomaa, volume 3113 of Lecture Notes in Computer Science, pages 192--204. Springer Verlag, 2004.
• 22: A. Pnueli. The temporal logic of programs. In Proceedings from the 18th Annual Symposium on Foundations of Computer Science (FOCS'77), pages 46--57. IEEE, New York, 1977.
• 23: Riccardo Pucella , Vicky Weissman, A Logic for Reasoning about Digital Rights, Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW'02), p.282, June 24-26, 2002
• 24: Paul Resnick , Ko Kuwabara , Richard Zeckhauser , Eric Friedman, Reputation systems, Communications of the ACM, v.43 n.12, p.45-48, Dec. 2000 [doi>10.1145/355112.355122]
• 25: Muriel Roger , Jean Goubault-Larrecq, Log Auditing through Model-Checking, Proceedings of the 14th IEEE Workshop on Computer Security Foundations, p.220, June 11-13, 2001
• 26: Fred B. Schneider, Enforceable security policies, ACM Transactions on Information and System Security (TISSEC), v.3 n.1, p.30-50, Feb. 2000 [doi>10.1145/353323.353382]
• 27: Vitaly Shmatikov , Carolyn Talcott, Reputation-based trust management, Journal of Computer Security, v.13 n.1, p.167-190, January 2005
• 28: A. P. Sistla , E. M. Clarke, The complexity of propositional linear temporal logics, Journal of the ACM (JACM), v.32 n.3, p.733-749, July 1985 [doi>10.1145/3828.3837]
• 29: C. Skalka and S. Smith. History effects and verification. In Programming Languages and Systems: Second Asian Symposium, APLAS 2004, Taipei, Taiwan, November 4-6, 2004. Proceedings, pages 107--128. Springer, 2005.
• 30: Glynn Winskel , Mogens Nielsen, Models for concurrency, Handbook of logic in computer science (vol. 4): semantic modelling, Oxford University Press, Oxford, 1995

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

General Terms:
Algorithms, Languages, Security

Keywords:
history-based access control, model checking, reputation, temporal logic, trust management