{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T08:03:59Z","timestamp":1772784239906,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2005,5,1]],"date-time":"2005-05-01T00:00:00Z","timestamp":1114905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,5]]},"abstract":"<jats:p>Trust management is a form of distributed access control that allows one principal to delegate some access decisions to other principals. While the use of delegation greatly enhances flexibility and scalability, it may also reduce the control that a principal has over the resources it owns. Security analysis asks whether safety, availability, and other properties can be maintained while delegating to partially trusted principals. We show that in contrast to the undecidability of classical Harrison--Ruzzo--Ullman safety properties, our primary security properties are decidable. In particular, most security properties we study are decidable in polynomial time. The computational complexity of containment analysis, the most complicated security property we study, varies according to the expressive power of the trust management language.<\/jats:p>","DOI":"10.1145\/1066100.1066103","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"474-514","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":100,"title":["Beyond proof-of-compliance: security analysis in trust management"],"prefix":"10.1145","volume":"52","author":[{"given":"Ninghui","family":"Li","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, Indiana"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John C.","family":"Mitchell","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William H.","family":"Winsborough","sequence":"additional","affiliation":[{"name":"George Mason University, Fairfax, Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,5]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"On SDSI's linked local name spaces","volume":"6","author":"Abadi M.","year":"1998","unstructured":"Abadi , M. 1998 . On SDSI's linked local name spaces . J. Comput. Sec. 6 , 1 -- 2 , 3--21.]] Abadi, M. 1998. On SDSI's linked local name spaces. J. Comput. Sec. 6, 1--2, 3--21.]]","journal-title":"J. Comput. Sec."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/155183.155225"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Apt K. R. Blair H. A. and Walker A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming J. Minker Ed. Morgan Kaufmann Los Altos Calif. 89--148.]]   Apt K. R. Blair H. A. and Walker A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming J. Minker Ed. Morgan Kaufmann Los Altos Calif. 89--148.]]","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Blaze M. Feigenbaum J. Ioannidis J. and Keromytis A. D. 1999a. The KeyNote trust-management system version 2. IETF RFC 2704.]]   Blaze M. Feigenbaum J. Ioannidis J. and Keromytis A. D. 1999a. The KeyNote trust-management system version 2. IETF RFC 2704.]]","DOI":"10.17487\/rfc2704"},{"key":"e_1_2_1_5_1","volume-title":"Secure Internet Programming. Lecture Notes in Computer Science","volume":"1603","author":"Blaze M.","unstructured":"Blaze , M. , Feigenbaum , J. , Ioannidis , J. , and Keromytis , A. D . 1999b. The role of trust management in distributed systems . In Secure Internet Programming. Lecture Notes in Computer Science , vol. 1603 . Springer-Verlag, New York, 185--210.]] Blaze, M., Feigenbaum, J., Ioannidis, J., and Keromytis, A. D. 1999b. The role of trust management in distributed systems. In Secure Internet Programming. Lecture Notes in Computer Science, vol. 1603. Springer-Verlag, New York, 185--210.]]"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 1996 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 164--173","author":"Blaze M.","unstructured":"Blaze , M. , Feigenbaum , J. , and Lacy , J . 1996. Decentralized trust management . In Proceedings of the 1996 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 164--173 .]] Blaze, M., Feigenbaum, J., and Lacy, J. 1996. Decentralized trust management. In Proceedings of the 1996 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 164--173.]]"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of CONCUR'97","volume":"1256","author":"Bouajjani A.","unstructured":"Bouajjani , A. , Esparza , J. , and Maler , O . 1997. Reachability analysis of pushdown automata: Application to model-checking . In Proceedings of CONCUR'97 . Lecture Notes in Computer Science , vol. 1256 . Springer-Verlag, New York, 135--150.]] Bouajjani, A., Esparza, J., and Maler, O. 1997. Reachability analysis of pushdown automata: Application to model-checking. In Proceedings of CONCUR'97. Lecture Notes in Computer Science, vol. 1256. Springer-Verlag, New York, 135--150.]]"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 14th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos, Calif., 27--43","author":"Chander A.","unstructured":"Chander , A. , Dean , D. , and Mitchell , J. C . 2001. A state-transition model of trust management and access control . In Proceedings of the 14th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos, Calif., 27--43 .]] Chander, A., Dean, D., and Mitchell, J. C. 2001. A state-transition model of trust management and access control. In Proceedings of the 14th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos, Calif., 27--43.]]"},{"key":"e_1_2_1_9_1","first-page":"285","article-title":"Certificate chain discovery in SPKI\/SDSI","volume":"9","author":"Clarke D.","year":"2001","unstructured":"Clarke , D. , Elien , J.-E. , Ellison , C. , Fredette , M. , Morcos , A. , and Rivest , R. L. 2001 . Certificate chain discovery in SPKI\/SDSI . J. Comput. Sec. 9 , 4, 285 -- 322 .]] Clarke, D., Elien, J.-E., Ellison, C., Fredette, M., Morcos, A., and Rivest, R. L. 2001. Certificate chain discovery in SPKI\/SDSI. J. Comput. Sec. 9, 4, 285--322.]]","journal-title":"J. Comput. Sec."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","article-title":"Linear-time algorithms for testing the satisfiability of propositional horn formulae","volume":"1","author":"Dowling W. F.","year":"1984","unstructured":"Dowling , W. F. , and Gallier , J. H. 1984 . Linear-time algorithms for testing the satisfiability of propositional horn formulae . J. Logic Prog. 1 , 3, 267 -- 284 .]] Dowling, W. F., and Gallier, J. H. 1984. Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Logic Prog. 1, 3, 267--284.]]","journal-title":"J. Logic Prog."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Ellison C. Frantz B. Lampson B. Rivest R. Thomas B. and Ylonen T. 1999. SPKI certificate theory. IETF RFC 2693.]]   Ellison C. Frantz B. Lampson B. Rivest R. Thomas B. and Ylonen T. 1999. SPKI certificate theory. IETF RFC 2693.]]","DOI":"10.17487\/rfc2693"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 12th International Conference on Computer Aided Verification (CAV","volume":"1855","author":"Esparza J.","year":"2000","unstructured":"Esparza , J. , Hansel , D. , Rossmanith , P. , and Schwoon , S . 2000. Efficient algorithms for model checking pushdown systems . In Proceedings of the 12th International Conference on Computer Aided Verification (CAV 2000 ). Lecture Notes in Computer Science , vol. 1855 . Springer-Verlag, New York, 232--247.]] Esparza, J., Hansel, D., Rossmanith, P., and Schwoon, S. 2000. Efficient algorithms for model checking pushdown systems. In Proceedings of the 12th International Conference on Computer Aided Verification (CAV 2000). Lecture Notes in Computer Science, vol. 1855. Springer-Verlag, New York, 232--247.]]"},{"key":"e_1_2_1_13_1","unstructured":"Garey M. R. and Johnson D. J. 1979. Computers And Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.]]   Garey M. R. and Johnson D. J. 1979. Computers And Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.]]"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the AFIPS Spring Joint Computer Conference.","volume":"40","author":"Graham G. S.","unstructured":"Graham , G. S. , and Denning , P. J . 1972. Protection --- principles and practice . In Proceedings of the AFIPS Spring Joint Computer Conference. Vol. 40 . AFIPS Press, 417--429.]] Graham, G. S., and Denning, P. J. 1972. Protection --- principles and practice. In Proceedings of the AFIPS Spring Joint Computer Conference. Vol. 40. AFIPS Press, 417--429.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200012)30:15%3C1609::AID-SPE334%3E3.0.CO;2-5"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"A logic for SDSI's linked local name spaces","volume":"9","author":"Halpern J.","year":"2001","unstructured":"Halpern , J. , and van der Meyden , R. 2001 . A logic for SDSI's linked local name spaces . J. Comput. Sec. 9 , 1 - 2 , 47--74.]] Halpern, J., and van der Meyden, R. 2001. A logic for SDSI's linked local name spaces. J. Comput. Sec. 9, 1-2, 47--74.]]","journal-title":"J. Comput. Sec."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/360303.360333"},{"key":"e_1_2_1_18_1","first-page":"2","article-title":"On the equivalence, containment, and covering problems for the regular and context-free languages","volume":"12","author":"Hunt H. B.","year":"1976","unstructured":"Hunt , H. B. , Rosenkrantz , D. J. , and Szymanski . 1976 . On the equivalence, containment, and covering problems for the regular and context-free languages . J. Comput. Syst. Sci. 12 , 2 (April), 222--268.]] Hunt, H. B., Rosenkrantz, D. J., and Szymanski. 1976. On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. Syst. Sci. 12, 2 (April), 222--268.]]","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 15th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos, Calif., 129--144","author":"Jha S.","unstructured":"Jha , S. , and Reps , T . 2002. Analysis of SPKI\/SDSI certificates using model checking . In Proceedings of the 15th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos, Calif., 129--144 .]] Jha, S., and Reps, T. 2002. Analysis of SPKI\/SDSI certificates using model checking. In Proceedings of the 15th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos, Calif., 129--144.]]"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 2001 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 106--115","author":"Jim T.","year":"2001","unstructured":"Jim , T. 2001 . SD3: A trust management system with certified evaluation . In Proceedings of the 2001 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 106--115 .]] Jim, T. 2001. SD3: A trust management system with certified evaluation. In Proceedings of the 2001 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 106--115.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/138873.138874"},{"key":"e_1_2_1_22_1","volume-title":"Protection. In Proceedings of the 5th Princeton Conference on Information Sciences and Systems. (Reprinted in ACM Operating Systems Review, 8(1):18--24","author":"Lampson B. W.","year":"1971","unstructured":"Lampson , B. W. 1971 . Protection. In Proceedings of the 5th Princeton Conference on Information Sciences and Systems. (Reprinted in ACM Operating Systems Review, 8(1):18--24 , Jan. 1974.)]] 10.1145\/775265.775268 Lampson, B. W. 1971. Protection. In Proceedings of the 5th Princeton Conference on Information Sciences and Systems. (Reprinted in ACM Operating Systems Review, 8(1):18--24, Jan. 1974.)]] 10.1145\/775265.775268"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 13th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos Calif., 2--15","author":"Li N.","year":"2000","unstructured":"Li , N. 2000 . Local names in SPKI\/SDSI . In Proceedings of the 13th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos Calif., 2--15 .]] Li, N. 2000. Local names in SPKI\/SDSI. In Proceedings of the 13th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos Calif., 2--15.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/605434.605438"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages (PADL","volume":"2562","author":"Li N.","year":"2003","unstructured":"Li , N. , and Mitchell , J. C . 2003a. Datalog with constraints: A foundation for trust management languages . In Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages (PADL 2003 ). Lecture Notes in Computer Science , vol. 2562 , Springer-Verlag, New York, 58--73.]] Li, N., and Mitchell, J. C. 2003a. Datalog with constraints: A foundation for trust management languages. In Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages (PADL 2003). Lecture Notes in Computer Science, vol. 2562, Springer-Verlag, New York, 58--73.]]"},{"key":"e_1_2_1_26_1","volume-title":"RT: A role-based trust-management framework. In The Third DARPA Information Survivability Conference and Exposition (DISCEX III)","author":"Li N.","year":"2003","unstructured":"Li , N. , and Mitchell , J. C . 2003 b. RT: A role-based trust-management framework. In The Third DARPA Information Survivability Conference and Exposition (DISCEX III) . IEEE Computer Society Press , Los Alamitos , Calif.]] Li, N., and Mitchell, J. C. 2003b. RT: A role-based trust-management framework. In The Third DARPA Information Survivability Conference and Exposition (DISCEX III). IEEE Computer Society Press, Los Alamitos, Calif.]]"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 2002 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 114--130","author":"Li N.","unstructured":"Li , N. , Mitchell , J. C. , and Winsborough , W. H . 2002. Design of a role-based trust management framework . In Proceedings of the 2002 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 114--130 .]] Li, N., Mitchell, J. C., and Winsborough, W. H. 2002. Design of a role-based trust management framework. In Proceedings of the 2002 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 114--130.]]"},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"Distributed credential chain discovery in trust management","volume":"11","author":"Li N.","year":"2003","unstructured":"Li , N. , Winsborough , W. H. , and Mitchell , J. C. 2003 b. Distributed credential chain discovery in trust management . J. Comput. Sec. 11 , 1 (Feb.), 35--86.]] Li, N., Winsborough, W. H., and Mitchell, J. C. 2003b. Distributed credential chain discovery in trust management. J. Comput. Sec. 11, 1 (Feb.), 35--86.]]","journal-title":"J. Comput. Sec."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322017.322025"},{"key":"e_1_2_1_30_1","volume-title":"Foundations of Logic Programming","author":"Lloyd J. W.","unstructured":"Lloyd , J. W. 1987. Foundations of Logic Programming , Second Edition. Springer-Verlag , New York .]] Lloyd, J. W. 1987. Foundations of Logic Programming, Second Edition. Springer-Verlag, New York.]]"},{"key":"e_1_2_1_31_1","unstructured":"Rivest R. L. and Lampson B. 1996. SDSI---A simple distributed security infrastructure. Available at http:\/\/theory.lcs.mit.edu\/~rivest\/sdsi11.html.]]  Rivest R. L. and Lampson B. 1996. SDSI---A simple distributed security infrastructure. Available at http:\/\/theory.lcs.mit.edu\/~rivest\/sdsi11.html.]]"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42286"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 1992 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 122--136","author":"Sandhu R. S.","year":"1992","unstructured":"Sandhu , R. S. 1992 . The typed access matrix model . In Proceedings of the 1992 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 122--136 .]] Sandhu, R. S. 1992. The typed access matrix model. In Proceedings of the 1992 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 122--136.]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.485845"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of 2001 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 94--105","author":"Weeks S.","year":"2001","unstructured":"Weeks , S. 2001 . Understanding trust management systems . In Proceedings of 2001 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 94--105 .]] Weeks, S. 2001. Understanding trust management systems. In Proceedings of 2001 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 94--105.]]"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1066100.1066103","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1066100.1066103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:17Z","timestamp":1750262897000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1066100.1066103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["10.1145\/1066100.1066103"],"URL":"https:\/\/doi.org\/10.1145\/1066100.1066103","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5]]},"assertion":[{"value":"2005-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}