A formal foundation for XrML

ABSTRACT

XrML is becoming a popular language in industry for writing software licenses. The semantics for XrML is implicitly given by an algorithm that determines if a permission follows from a set of licenses. We focus on a fragment of the language and use it to highlight some problematic aspects of the algorithm. We then correct the problems, introduce formal semantics, and show that our semantics captures the (corrected) algorithm. Next, we consider the complexity of determining if a permission is implied by a set of XrML licenses. We prove that the general problem is undecidable, but it is polynomial-time computable for an expressive fragment of the language. We extend XrML to capture a wider range of licenses by adding negation to the language. Finally, we discuss the key differences between XrML and MPEG-21, an international standard based on XrML.

REFERENCES

• 1: Moritz Y. Becker , Peter Sewell, Cassandra: Flexible Trust Management, Applied to Electronic Health Records, Proceedings of the 17th IEEE workshop on Computer Security Foundations, p.139, June 28-30, 2004 [doi>10.1109/CSFW.2004.7]
• 2: ContentGuard. 2001. XrML: The digital rights language for trusted content and services. Available at http://www.xrml.org/.
• 3: John DeTreville, Binder, a Logic-Based Security Language, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.105, May 12-15, 2002
• 4: C. Ellison , B. Frantz , B. Lampson , R. Rivest , B. Thomas , T. Ylonen, SPKI Certificate Theory, RFC Editor, 1999
• 5: Ellison, C., Frantz, B., Lampson, B., Rivest, R., Thomas, B., and Ylonen, T. 1999b. Simple public key certificate. Available at http://world.std.com/~cme/spki.txt. Internet RFC 2693.
• 6: Joseph Y. Halpern , Ron van der Meyden, A logical reconstruction of SPKI, Journal of Computer Security, v.11 n.4, p.581-613, July 2003
• 7: Halpern, J. Y., and Weissman, V. 2003. Using first-order logic to reason about policies. In Proceedings of the 16th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos, CA, 187--201.
• 8: Joseph Y. Halpern , Vicky Weissman, A Formal Foundation for XrML, Proceedings of the 17th IEEE workshop on Computer Security Foundations, p.251, June 28-30, 2004 [doi>10.1109/CSFW.2004.2]
• 9: Iannella, R. 2001. ODRL: The open digital rights language initiative. Available at http://odrl.net/.
• 10: Sushil Jajodia , Pierangela Samarati , V. S. Subrahmanian, A Logical Language for Expressing Authorizations, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.31, May 04-07, 1997
• 11: Trevor Jim, SD3: A Trust Management System with Certified Evaluation, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.106, May 14-16, 2001
• 12: Ninghui Li , Benjamin N. Grosof , Joan Feigenbaum, Delegation logic: A logic-based approach to distributed authorization, ACM Transactions on Information and System Security (TISSEC), v.6 n.1, p.128-171, February 2003 [doi>10.1145/605434.605438]
• 13: Ninghui Li , C. Mitchell, Understanding SPKI/SDSI using first-order logic, International Journal of Information Security, v.5 n.1, p.48-64, January 2006 [doi>10.1007/s10207-005-0073-0]
• 14: Ninghui Li , John C. Mitchell , William H. Winsborough, Design of a Role-Based Trust-Management Framework, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.114, May 12-15, 2002
• 15: Moses, T. 2005. XACML: The extensible access control markup language, version 2.0. Available at http://www.xacml.org.
• 16: MPEG. 2004. Information technology---Multimedia framework (MPEG-21)---Part 5: Rights expression language (ISO/IEC 21000-5:2004). Available at http://www.iso.ch/iso/en/.
• 17: Anil Nerode , Richard Shore, Logic for Applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 18: Post, E. 1946. A variant of a recursively unsolvable problem. Bull. AMS 52, 264--268.
• 19: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

General Terms:
Languages, Security

Keywords:
Digital rights management