Beyond Proof-of-compliance: Safety and Availability Analysis in Trust Management

Ninghui Li, William H. Winsborough, and John C. Mitchell


Trust management is a form of distributed access control using distributed policy statements. Since one organization may delegate partial control to another organization, it is natural ask what permissions may be granted as the result of policy changes by other organizations. We study security properties such as safety and availability for a family of trust management languages, devising algorithms for deciding the possible consequences of certain changes in policy. While trust management is more powerful in certain ways than mechanisms based on access control lists, and the security properties considered are more than simple safety, we find that in contrast to the classical HRU undecidability of safety properties, our primary security properties are decidable. In particular, most properties we studied are decidable in polynomial time. Containment, the most complicated security property we studied, is decidable in polynomial time for the simplest TM langauge in the family. The problem becomes intractable (co-NP-hard) when intersection or linked roles is added to the language.

To appear in IEEE Symposium on Security and Privacy, Berkeley, California, May 2003.

Paper: (Paper in PDF)

Back to Ninghui's publications, Ninghui's home page.