With a very large number of information sources and services on the web, software agents face difficult problem of knowing what information source (agents, documents, or web pages) to trust. Which agents can be taken as reliable source of accurate and timely information about a given topic and which agent can be authorized to perform a requested service. Further, the web will be evolving over time, make these problems even more difficult to solve. The proposed work will extend our current work [GLC99, HSF98, TC00, CT00] on distributed trust in e-business scenarios in which authentication, authorization, and delegation information and policy is shred among agents in a multi-agent system.
Public Key Infrastructure (PKI) is an enabling infrastructure for current internet-based commerce. A similar infrastructure will be required for the next generation internet for agent-based information systems for (i) issuing certificates to indicate the legitimacy of an agent to perform certain tasks; (ii) managing certificates and handling revocations. We propose to develop the theories and protocols that will be part of the foundation for such as “PKI for agents”.
We assume that people will manage the trust knowledge used by agents. Therefore there must be an easy to use and sufficiently rich representation language with precisely defined declarative semantics and operational semantics. By declarative semantics, we mean that the intended authorizations and trust relationships for a given declared relationship must be unambiguous. Operational semantics means that rules for derivation and revocation must be unambiguously defined. Further more, distributed management protocols must be developed for a multi-agent environment. There has been a large body of research on the representation of authorization information. Since, trust and authorization are very closely related concepts, we will restrict to discuss authorizations relationships in this the proposal due to space limitations.
Declarative semantics for authorization
At least two entities are involved in expressing an authorization relationship: a subject (e.g. a person, or an agent), and (operational) privileges on an object (e.g. read a file). A user-oriented representation is to organize subjects into role hierarchies (e.g. an organizational hierarchy), and express authorization relationships in terms of roles and privileges (e.g. academic advisors can read student academic information) [SCFY96, FBK99].
However, past works have not adequately accounted for the hierarchical nature of information objects. For example, there are multiple types of student academic information (e.g. individual course grades, GPA, honors, disciplinary information), an academic advisor may be allowed to read all types of academic information, a financial officer, on the other hand, may be authorized to read all types of academic information except for individual course grades. Analyzing semantics of such relationship is non-trivial as multiple inheritance and exceptions must be carefully examined. Furthermore, conditions are often needed; for example, disciplinary information can only be printed with the authorization from the vice-chancellor and a court order. Such conditions may also be based on a threshold (e.g. two out three must be true) [AU99]
We propose to develop a representation language that will allow people to naturally express authorization relationships across role hierarchies and object hierarchies. We plan to approach this problem based on our past work of semantics for causal relationships across hierarchies [CR89a, CR89b] and recent developments in courteous logic [GR97].
Operational semantics for authorization
There has been a lot of work on verifying authorization-based policies represented as logic expressions, e.g. [BFL96, BFIK99, JSS97, LFG99, LG00]. However, generic policy compliance checking is computationally expensive [BFS98] and extremely difficult when authorization knowledge is distributed across a number of agents. A reasonable strategy to reduce the computational complexity is to “pre-compute” authorizations and capture them as attributed digital certificates [TC00, CT00]. Agents would agents exchange such certificates [AU99, HMMNR00]. Rivest and Lampson have proposed a trust infrastructure as an alternative to the current deployed PKIs [RL96]. We have extended this idea and applied it to e-business applications [TC00, CT00].
An example of deriving new authorizations from existing assertions is illustrated in the following figure. Suppose there is UNCC policy that “UNCC services can be charged to UNCC accounts if there is an agreement between the student and a parent”. Suppose Jack and his farther have signed an agreement with UNCC, then a digital attribute certificate can be issued (part a of the figure). Suppose there is a UNCC hospital policy that “hospital charges can be charged to UNCC if there is a charge authorization from UNCC, and acceptable medical insurance”. The graphs represent derivations that are kept by different agents. For example, part a may be kept on a server at the university’s student account office. When Jack first visits the UNCC hospital, part b may be generated, working with a software agent representing UNCC student account office, and cached by an agent at the UNCC hospital.
The explicit representation of the authorization process also helps with revocations. Suppose that Jack stops attending UNCC. The revocation of his student certificate will cause the termination of his ability to charge to UNCC, which in term will terminate his ability to charge to UNCC when using UNCC hospital.
As part of the proposed research, operational semantics of authorizations will be systematically defined and formally described. Such a system will include roles and their hierarchies, objects and rights and their hierarchies, and policies across different hierarchies. Our work will build upon related work in this area, e.g. [AU00, SCFY96, JSS97]. However, the issue of revocation in the context of attribute certificates has not been studied. We have started analyzing revocation semantics in [TC00, CT00]. At the conceptual level, the distributed revocation problem is related to distributed truth maintenance, e.g., [MJ89, DGB97]. However, distributed trust management is different from generic truth maintenance because unique semantic issues for information security and authorization control must be carefully examined. We will leverage previous work wherever appropriate and focus on developing a distributed trust management protocol.
Protocols for the management of distributed authorizations
Many issues need to be examined in designing protocols to implement distributed trust management. For example, how to propagate revocation events in a way that avoid inconsistencies in trust relationships? At least two strategies, push and pull, are possible. In a push strategy, as soon as an agent revokes a certificate, it will tell all other agents to whom the certificate has been sent, possibly triggering further revocations. In a pull strategy, an agent will verify the conditions upon which a given certificate is generated triggering the verification of their conditions in turn. In both cases, one must make sure that certificate generation and revocation do not interfere with one another.
A reasonable approach to start the protocol development is to impose the assumption that each agent will not generate and revoke certificates at the same time. For example, under a push strategy, an agent revoking a certificate will not generate certificates until the effect of the revocation has been fully propagated to all affected agents (or quiescence). Dijkstra and Scholten’s algorithm can be used to detect quiescence in a distributed network of agents [DS80, LY96]. Under certain assumption, quiescence may be achievable for revocation (e.g. if the total number of certificates is finite). Similarly under certain conditions (e.g. if the total number of possible certificates is finite, given finite subjects and privileges) the certificate generation process may also reach quiescence. Global quiescence is, of course, unrealistic for large distributed systems. We plan to explore ways to relax the quiescence assumption to allow more parallelism for each agent in a way that can either avoid or minimize the chance of inconsistencies.
Schedule and milestones
Academic year / 2000-2001 / 2001-2002 / 2002-2003 / 2003-2004 / 2004-2005Research on distributed trust management / · Define semantics for authorization and trust relationships across role and object hierarchies
· Start the operational semantics. / · Complete the semantics of the authorization and trust relationships
· Continue the work on operational semantics
· Define distributed protocol under the simplifying assumption
· Publications / · Complete the operational semantics
· Identifying ways to relax the quiescence assumption
· Start implementation efforts
· Publications / · Continue to work on distributed protocols
· Formalize algorithms and proofs
· Continue implementations
· Publications / · Complete protocols and formalizations
· Complete implementations
· Publications
Integration / · Participate in the definition of the overall architecture and applications for prototyping
· Elaborate details of relationships with other parts of the research project
· Define evaluation criteria / · Integrate with other parts of the research project
· Define prototyping implementation strategy.
· Elaborate evaluation criteria / · Start the development of an integrated set of languages and protocols
· Coordinate implementation efforts
· Elaborate evaluation criteria / · Development of integrated set of languages and protocols
· Coordinate implementation efforts
· Evaluate results / · Complete implications
· Evaluate results
· Summarize results and lessons learned.
References
[AU99] Tuomas Aura. Distributed access-rights management with delegation certificates. In Security Internet Programming J. Vitec and C. Jensen (Eds.) pp. 211-235 Springer: Berlin, 1999.
[FBK99] D. Ferraiolo, J. Barkley, and D. Kuhn. A role-based access control model and reference implementation with a corporate intranet. In ACM transactions on Information and System Security 2(1) February 1999.
[BFL96] M. Blaze, J. Faigenbaum, and J. Lacy. Decentralized trust management. In IEEE Symposium on Security and Privacy May 1996.
[BFIK99] M. Blaze, J. Feigenbaum, J. Ioannidis, and A. Keromytis. The role of trust management in distributed system security. In Security Internet Programming J. Vitec and C. Jensen (Eds.) pp. 185-210 Springer: Berlin, 1999.
[BFS98] M. Blaze, J. Feigenbaum, M. Stauss. Compliance checking in the policy maker trust management system. In Proceedings of the financial crypto’98. Lecture Notes in Computer Science, vol 1465, Springer: Berlin pp. 254-274, 1998.
[CR91a] B. Chu and J. Reggia,. Modeling Diagnosis at Multiple Levels of Abstraction I. Representing Causal Relations at Multiple Levels of Abstraction. In International Journal of Intelligent Systems V.6, pp.617-644, 1991.
[CR91b] B. Chu and J. Reggia, Modeling Diagnosis at Multiple Levels of Abstraction II. Diagnostic Reasoning at Multiple Levels of Abstraction. In International Journal of Intelligent Systems V.6, pp.645-671, 1991.
[CT00] B. Chu and K. Tan. Distributed trust management for business-to-business e-commerce security" In ACME 2000 International Conference, Aug. 2000.
[DGB97] A.F. Dragoni, P. Giorgini, M. Baffetti, "Distributed Belief Revision vs. Belief Revision in a Multi-Agent Environment" , in Magnus Boman and Walter Van de Velde (Eds.) "Multi-agent Rationality" LNCS no1237, Springer-Verlag, 1997.
[DS80] E.W. Dijkstra and C.S. Scholten. Termination detection for diffusing computations. In Information Processing Letters 11(1-4), 1980.
[GLC99] Benjamine Grosof, Yannis Labrou, and Hoi Chan. A declearative apoproach to business rules in contracts: Couteous logic programs in xml. In First ACM Conference on Electronic Commerce, November 1999.
[GR97] Benjamin N. Grosof. Prioritized conflict handling for logic programs. In Jan Maluszynski, editor, Logic Pro-gramming:Proceedings of the International Symposium (ILPS-97), MIT Press, 1997.
[HMMNR00] Amir Herzberg, Joris Mihaeli, Yosi Mass, Dalit Naor, and Yifach Ravid. Access Control Meets Public Key Infrastructure, or: assigning roles to strangers.” In IEEE Symposium on Security and Privacy May 2000.
[HSF 98] Qi He, Katia Sycara, and Tim Finin. Personal security agent: Kqml-based public key infrastructure. In Proceedings of the ACM Conference in Autonomous Agents (Agents ’98) ACM Press, May 1998.
[JSS97] Sushil Jajodia, Pierangela Samarati and V. S. Subrahmanian A Logical Language for Expressing Authorizations. In IEEE Symposium on Security and Privacy May 1997.
[LFG99] Ninghui Li, Joan Feigenbaum, and Benjamin N. Grosof. A logic-based knowledge representation for authorization with delegation (extended abstract). In Proc. 12th Intl. IEEE Computer Security Foundations Workshop, 1999. Extended version is IBM Research Report RC 21492.
[LG00] Ninghui Li and Benjamin Grosof A practically implementable and tractable delegation logic. In IEEE Symposium on Security and Privacy May 2000.
[LY96] Nancy Lynch. Distributed Algorithms. Morgan Kaufmann: CA. 1996.
[MJ89] Cindy Mason and Rowland Johnson DATMS: A Framework for distributed assumption based reasoning. In Distributed Artificial Intelligence 2, L. Gasser and M.N. Huhns (Eds) Morgan Kaufmann: London, pp293-318, 1989
[RL96] R.L. Rivest and B. Lampson. A Simple Distributed Security Infrastructure. http://theory.lcs.mit.edu/~rivest/sdsi10.html, 1996.
[SCFY96] R. Sandhu, E. Coyne, H. Feinstein, and C. Youman. Role-based access control models. In IEEE Computer, 29(2) February 1996.
[TC00] K. Tan and B. Chu. Distributed trust management architecture for integrated supplier chain security. Submitted to the 23rd National Information System Security Conference, Oct. 2000.