Weighted Pushdown Systems and Trust-Management Systems

Somesh Jha, Stefan Schwoon, Hao Wang, Thomas W. Reps

Abstract

The authorization problem is to decide whether, according to a security policy, some principal should be allowed access to a resource. In the trust-management system SPKI/SDSI, the security policy is given by a set of certificates, and proofs of authorization take the form of certificate chains. The certificate-chain-discovery problem is to discover a proof of authorization for a given request. Certificate-chain-discovery algorithms for SPKI/SDSI have been investigated by several researchers. We consider a variant of the certificate-chain discovery problem where the certificates are distributed over a number of servers, which then have to cooperate to identify the proof of authorization for a given request. We propose two protocols for this purpose. These protocols are based on distributed model-checking algorithms for weighted pushdown systems (WPDSs). These protocols can also handle cases where certificates are labeled with weights and where multiple certificate chains must be combined to form a proof of authorization. We have implemented these protocols in a prototype and report preliminary results of our evaluation.
BibTeX
@inproceedings{jha2006weighted,
  author = {Somesh Jha and Stefan Schwoon and Hao Wang and Thomas W. Reps},
  title = {{Weighted Pushdown Systems and Trust-Management Systems}},
  booktitle = {TACAS},
  year = {2006},
  doi = {10.1007/11691372\_1},
}

Loading related content...

Figure