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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abadi, M.: On SDSI’s linked local name spaces. Journal of Computer Security 6(1-2), 3–21 (1998)
Appel, A.W., Felten, E.W.: Proof-carrying authentication. In: Conf. on Comp. and Commun. Sec., (November 1999)
Bauer, L., Garriss, S., Reiter, M.K.: Distributed proving in access-control systems. In: Proceedings of the 2005 IEEE Symposium on Security and Privacy, May 2005, pp. 81–95 (2005)
Blaze, M., Feigenbaum, J., Ioannidis, J., Keromytis, A.D.: The role of trust management in distributed systems security. In: Vitek, J. (ed.) Secure Internet Programming. LNCS, vol. 1603, pp. 185–210. Springer, Heidelberg (1999)
Blaze, M., Feigenbaum, J., Ioannidis, J., Keromytis, A.D.: The KeyNote Trust-Management System Version 2. RFC 2704 (September 1999)
Bouajjani, A., Esparza, J., Maler, O.: Reachability analysis of pushdown automata: Application to model-checking. In: Mazurkiewicz, A., Winkowski, J. (eds.) CONCUR 1997. LNCS, vol. 1243, pp. 135–150. Springer, Heidelberg (1997)
Bouajjani, A., Esparza, J., Touili, T.: A generic approach to the static analysis of concurrent programs with procedures. In: Proceedings of POPL 2003 (2003)
Clarke, D., Elien, J.-E., Ellison, C.M., Fredette, M., Morcos, A., Rivest, R.L.: Certficate chain discovery in SPKI/SDSI. Journal of Computer Security 9(1/2), 285–322 (2001)
Ellison, C.M., Frantz, B., Lampson, B., Rivest, R., Thomas, B., Ylönen, T.: RFC 2693: SPKI Certificate Theory. The Internet Society (September 1999)
Esparza, J., Hansel, D., Rossmanith, P., Schwoon, S.: Efficient algorithms for model checking pushdown systems. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 232–247. Springer, Heidelberg (2000)
Finkel, A., Willems, B., Wolper, P.: A direct symbolic approach to model checking pushdown systems. Elec. Notes in Theor. Comp. Sci. 9 (1997)
Halpern, J.Y., van der Meyden, R.: A logical reconstruction of SPKI. In: Proceedings of the 14th IEEE Computer Security Foundations Workshop, pp. 59–70. IEEE Computer Society Press, Los Alamitos (2001)
Howell, J., Kotz, D.: A formal semantics for SPKI. Technical Report 2000-363, Department of Computer Science, Dartmouth College, Hanover, NH (March 2000)
Jha, S., Reps, T.: Analysis of SPKI/SDSI certificates using model checking. In: Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW), pp. 129–146. IEEE Computer Society Press, Los Alamitos (2002)
Jha, S., Reps, T.: Model checking SPKI/SDSI. Journal of Computer Security 12(3–4), 317–353 (2004)
Jim, T.: SD3: A trust management system with certified evaluation. In: SP 2001: Proceedings of the IEEE Symposium on Security and Privacy, p. 106. IEEE Computer Society Press, Los Alamitos (2001)
Jim, T., Suciu, D.: Dynamically distributed query evaluation. In: PODS 2001: Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 28–39. ACM Press, New York (2001)
Lampson, B., Abadi, M., Burrows, M., Wobber, E.: Authentication in distributed systems: Theory and practice. ACM Transactions on Computer Systems 10(4), 265–310 (1992)
Li, N., Mitchell, J.C.: Understanding SPKI/SDSI using first-order logic. In: Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW). IEEE Computer Society Press, Los Alamitos (2003)
Li, N., Winsborough, W.H., Mitchell, J.C.: Distributed credential chain discovery in trust management. Journal of Computer Security 11(1), 35–86 (2003)
Pfenning, F., Schürmann, C.: System Description: Twelf - A Meta-Logical Framework for Deductive Systems. In: Ganzinger, H. (ed.) CADE 1999. LNCS (LNAI), vol. 1632, pp. 202–206. Springer, Heidelberg (1999)
Reps, T., Schwoon, S., Jha, S.: Weighted pushdown systems and their application to interprocedural dataflow analysis. In: Proceedings of the 10th Internation Static Analysis Symposium (SAS), San Diego, CA, June 11-13 (2003)
Reps, T., Schwoon, S., Jha, S., Melski, D.: Weighted pushdown systems and their application to interprocedural dataflow analysis. Science of Computer Programming 58(1-2), 206–263 (2005)
Schwoon, S., Jha, S., Reps, T., Stubblebine, S.: On generalized authorization problems. In: Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW), pp. 202–218. IEEE Computer Society, Los Alamitos (2003)
Weeks, S.: Understanding trust management systems. In: Proceedings of the IEEE Symposium on Research in Security and Privacy, Oakland, CA, May 2001, p. 1. IEEE Computer Society,Technical Committee on Security and Privacy. IEEE Computer Society Press, Los Alamitos (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jha, S., Schwoon, S., Wang, H., Reps, T. (2006). Weighted Pushdown Systems and Trust-Management Systems. In: Hermanns, H., Palsberg, J. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2006. Lecture Notes in Computer Science, vol 3920. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11691372_1
Download citation
DOI: https://doi.org/10.1007/11691372_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33056-1
Online ISBN: 978-3-540-33057-8
eBook Packages: Computer ScienceComputer Science (R0)