Weighted Pushdown Systems and Trust-Management Systems
Somesh Jha, Stefan Schwoon, Hao Wang, and Thomas Reps
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.
(Click here to access the paper:
PDF;
(c) Springer-Verlag.)