I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Weighted Pushdown Systems and Trust-Management Systems

Reference:

Somesh Jha, Stefan Schwoon, Hao Wang, and Thomas Reps. Weighted pushdown systems and trust-management systems. In Holger Hermanns and Jens Palsberg, editors, Proceedings of the 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), volume 3920 of Lecture Notes in Computer Science, pages 1–26, Vienna, Austria, 2006. Springer. Invited paper.

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.

Suggested BibTeX entry:

@inproceedings{JSWR06,
    address = {Vienna, Austria},
    author = {Somesh Jha and Stefan Schwoon and Hao Wang and Thomas Reps},
    booktitle = {Proceedings of the 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)},
    editor = {Holger Hermanns and Jens Palsberg},
    note = {Invited paper},
    pages = {1--26},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {Weighted Pushdown Systems and Trust-Management Systems},
    volume = {3920},
    year = {2006}
}

PDF (357 kB)
Tech report version