Trust management is a scalable form of access control that relies heavily on delegation. Different parts of the policy are under the control of different principals in the system. While these two characteristics may be necessary in large or decentralized systems, they make it difficult to anticipate how policy changes made by others will affect whether ones own security objectives are met. Automated analysis tools are needed for assessing this question. The article develops techniques that support the development of tools to solve many analysis problem instances. When an access control policy fails to satisfy desired security objectives, the tools provide information about how and why the failure occurs. Such information can assist policy authors design appropriate policies. The approach to performing the analysis is based on model checking. To assist in making the approach effective, a collection of reduction techniques is introduced. We prove the correctness of these reductions and empirically evaluate their effectiveness. While the class of analysis problem instances we examine is generally intractable, we find that our reduction techniques are often able to reduce some problem instances into a form that can be automatically verified.

Organizations collect personal information from individuals to carry out their business functions. Federal privacy regulations, such as the Health Insurance Portability and Accountability Act (HIPAA), mandate how this collected information can be shared by the organizations. It is thus incumbent upon the organizations to have means to check compliance with the applicable regulations. Prior work by Barth et. al. introduces two notions of compliance, weak compliance (WC) and strong compliance (SC). WC ensures that present requirements of the policy can be met whereas SC also ensures obligations can be met. An action is compliant with a privacy policy if it is both weakly and strongly compliant. However, their definitions of compliance are restricted to only propositional linear temporal logic (pLTL), which cannot feasibly specify HIPAA. To this end, we present a policy specification language based on a restricted subset of first order temporal logic (FOTL) which can capture the privacy requirements of HIPAA. We then formally specify WC and SC for policies of our form. We prove that checking WC is feasible whereas checking SC is undecidable. We then formally specify the property WC entails SC, denoted by Δ, which requires that each weakly compliant action is also strongly compliant. To check whether an action is compliant with such a policy, it is sufficient to only check whether the action is weakly compliant with that policy. We also prove that when a policy ℘ has the Δ-property, the present requirements of the policy reduce to the safety requirements imposed by ℘. We then develop a sound, semi-automated technique for checking whether practical policies have the Δ-property. We finally use HIPAA as a case study to demonstrate the efficacy of our policy analysis technique.

In the current time of the Internet, specifically with the emergence of social networking, people are sharing both sensitive and non-sensitive information among each other without understanding its consequences. Federal regulations exist to mandate how sensitive information (e.g., SSN, health records, etc.) of a person can be shared (or, used) by organizations. However, there are no established norms or practices regarding how information that is deemed to be not sensitive may be used or shared. Furthermore, for the sake of transparency, different organizations reveal small amounts of non-sensitive information (i.e., photos, salaries, work hours, size of the houses, etc.) about their clients or employees. Although such information seems insignificant, the aggregation of it can be used to create a partial profile of a person which can later be used by malicious parties for robbery, extortion, kidnapping, etc. The goal of this work is to create awareness by demonstrating that it is plausible to create such a partial profile of a person just by crawling the Internet. For this, we have developed an open source framework that generates batch crawlers to create partial profiles of individuals. We also show empirical comparisons of the amount of information that can be gathered by using free and also paid websites.

This paper presents a formal, state machine-based specification (stateful specification) of a group-centric secure information sharing (g-SIS) model. The stateful specification given here is a refinement of a prior specification that is given in first-order linear temporal logic (FOTL). Such FOTL specification defines authorization based solely on group operations, but gives little guidance regarding implementation. The current specification is the result of a second step in a multi-step design process that separates concerns and provides multiple opportunities to detect unintended policy characteristics. We show that our stateful specification is consistent with the prior FOTL specification by using a combination of model-checking and manual techniques.

User obligations are actions that the human users are required to perform in some future time. These are common in many practical access control and privacy and can depend on and affect the authorization state. Consequently, a user can incur an obligation that she is not authorized to perform which may hamper the usability of a system. To mitigate this problem, previous work introduced a property of the authorization state, accountability, which requires that all the obligatory actions to be authorized when they are attempted. Although, existing work provides a specific and tractable decision procedure for a variation of the accountability property, it makes a simplified assumption that no cascading obligations may happen, i.e., obligatory actions cannot further incur obligations. This is a strong assumption which reduces the expressive power of past models, and thus cannot support many obligation scenarios in practical security and privacy policies. In this work, we precisely specify the strong accountability property in the presence of cascading obligations and prove that deciding it is NP-hard. We provide for several special yet practical cases of cascading obligations (i.e., repetitive, finite cascading, etc.) a tractable decision procedure for accountability. Our experimental results illustrate that supporting such special cases is feasible in practice.

This paper is part of a project investigating authorization systems that assign obligations to users. We are particularly interested in obligations that require authorization to be performed and that, when performed, may modify the authorization state. In this context, a user may incur an obligation she is unauthorized to perform. Prior work has introduced a property of the authorization system state that ensures users will be authorized to fulfill their obligations. We call this property accountability because users that fail to perform authorized obligations are accountable for their non-performance. While a reference monitor can mitigate violations of accountability, it cannot prevent them entirely. This paper presents techniques to be used by obligation system managers to restore accountability. We introduce several notions of dependence among pending obligations that must be considered in this process. We also introduce a novel notion we call obligation pool slicing, owing to its similarity to program slicing. An obligation pool slice identifies a set of obligations that the administrator may need to consider when applying strategies proposed here for restoring accountability. The paper also presents the system architecture of an authorization system that incorporates obligations that can require and affect authorizations.

Group-Centric Secure Information Sharing (g-SIS) envisions bringing users and objects together in a group to facilitate agile sharing of information brought in from external sources as well as creation of new information within the group. We expect g-SIS to be orthogonal and complementary to authorization systems deployed within participating organizations. The metaphors “secure meeting room” and “subscription service” characterize the g-SIS approach. The focus of this article is on developing the foundations of isolated g-SIS models. Groups are isolated in the sense that membership of a user or an object in a group does not affect their authorizations in other groups. Present contributions include the following: formal specification of core properties that at once help to characterize the family of g-SIS models and provide a “sanity check” for full policy specifications; informal discussion of policy design decisions that differentiate g-SIS policies from one another with respect to the authorization semantics of group operations; formalization and verification of a specific member of the family of g-SIS models; demonstration that the core properties are logically consistent and mutually independent; and identification of several directions for future extensions. The formalized specification is highly abstract. Besides certain well-formedness requirements that specify, for instance, a user cannot leave a group unless she is a member, it constrains only whether user-level read and write operations are authorized and it does so solely in terms of the history of group operations; join and leave for users and add, create, and remove for objects. This makes temporal logic one of the few formalisms in which the specification can be clearly and concisely expressed. The specification serves as a reference point that is the first step in deriving authorization-system component specifications from which a programmer with little security expertise could implement a high-assurance enforcement system for the specified policy.

Many authorization system models include some notion of obligation. Little attention has been given to user obligations that depend on and affect authorizations. However, to be usable, the system must ensure users have the authorizations they need when their obligations must be performed. Prior work in this area introduced accountability properties that ensure failure to fulfill obligations is not due to lack of required authorizations. That work presented inconclusive and purely theoretical results concerning the feasibility of maintaining accountability in practice. The results of the current paper include algorithms and performance analysis that support the thesis that maintaining accountability in a reference monitor is reasonable in many applications.

Simple non-interference is too restrictive for specifying and enforcing information flow policies in most programs. Exceptions to non-interference are provided using declassification policies. Several approaches for enforcing declassification have been proposed in the literature. In most of these approaches, the declassification policies are embedded in the program itself or heavily tied to the variables in the program being analyzed, thereby providing little separation between the code and the policy. Consequently, the previous approaches essentially require that the code be trusted, since to trust that the correct policy is being enforced, we need to trust the source code. In this paper, we propose a novel framework in which declassification policies are related to the source code being analyzed via its I/O channels. The framework supports many of the of declassification policies identified in the literature. Based on flow-based static analysis, it represents a first step towards a new approach that can be applied to untrusted and legacy source code to automatically verify that the analyzed program complies with the specified declassification policies. The analysis works by constructing a conservative approximation of expressions over input channel values that could be output by the program, and by determining whether all such expressions satisfy the declassification requirements stated in the policy. We introduce a representation of such expressions that resembles tree automata. We prove that if a program is considered safe according to our analysis then it satisfies a property we call Policy Controlled Release, which formalizes information-flow correctness according to our notion of declassification policy. We demonstrate, through examples, that our approach works for several interesting and useful declassification policies, including one involving declassification of the average of several confidential values.

In open systems such as cloud computing platforms, delegation transfers privileges among users across different administrative domains and facilitates information sharing. We present an independently verifiable delegation mechanism, where a delegation credential can be verified without the participation of domain administrators. Our protocol, called role-based cascaded delegation (RBCD), supports simple and efficient cross-domain delegation of authority. RBCD enables a role member to create delegations based on the dynamic needs of collaboration; in the meantime, a delegation chain can be verified by anyone without the participation of role administrators. We also describe an efficient realization of RBCD by using aggregate signatures, where the authentication information for an arbitrarily long role-based delegation chain is captured by one short signature of constant size.

In this paper, we propose a conceptual framework for developing a family of models for Group-Centric information sharing. The traditional approach to information sharing, characterized as Dissemination-Centric in this paper, focuses on attaching attributes and policies to an object (sometimes called "sticky policies") as it is disseminated from producers to consumers in a system. In contrast, Group-Centric sharing envisions bringing the subjects and objects together in a group to facilitate sharing. The metaphor is that of a secure meeting room where participants and information come together to "share" information for some common purpose. Another metaphor is that of the subscription model where, depending on policy, joining users may or may not be authorized to access past content. We argue that in such contexts, and in accordance with different application use cases, authorizations are influenced by the temporal ordering of subject and object group membership and by the precise nature of membership operations. For instance some subjects may only get future information added to the group while others may also be able to access previously added information. We develop a lattice of models based on variations of these basic membership operations, and discuss usage scenarios to illustrate practical applications of this lattice. Two principles guide Group-Centric models. First, "share but differentiate" which promotes sharing while differentiating user authorizations depending on temporal aspect of membership. Next, "groups within groups" which advocates relationships (such as a hierarchy) between multiple groups. In this paper, we confine our attention to read accesses in a single group.

Trust management is a scalable and flexible form of access control that relies heavily on delegation techniques. While these techniques may be necessary in large or decentralized systems, stakeholders need an analysis methodology and automated tools for reasoning about who will have access to their resources today as well as in the future. When an access control policy fails to satisfy the policy author's security objectives, tools should provide information that demonstrate how and why the failure occurred. Such information is useful in that it may assist policy authors in constructing policies that satisfy security objectives, which support policy authoring and maintenance. This paper presents a collection of reduction, optimization, and verification techniques useful in determining whether security properties are satisfied by RT policies. We provide proofs of correctness as well as demonstrate the degree of effectiveness and efficiency the techniques provide through empirical evaluation. While the type of analysis problem we examine is generally intractable, we demonstrate that our reduction and optimization techniques may be able to reduce problem instances into a form that can be automatically verified.

The concept of groups is a natural aspect of most collaboration scenarios. Group-Centric Secure Information Sharing models (g-SIS) have been recently proposed in which users and objects are brought together to promote sharing and collaboration. Users may join, leave and re-join and objects may be ad

We develop the foundations for a theory of Group-Centric Secure Information Sharing (g-SIS), characterize a specific family of models in this arena and identify several directions in which this theory can be extended. Traditional approach to information sharing, characterized as Dissemination-Centric, focuses on attaching attributes and policies to an object as it is disseminated from producers to consumers in a system. In contrast, Group-Centric sharing envisions bringing the users and objects together in a group to facilitate sharing. The metaphors "secure meeting room" and "subscription service" characterize the Group-Centric approach where participants and information come together to share for some common purpose. Our focus in this paper is on semantics of group operations: Join and Leave for users and Add and Remove for objects, each of which can have several variations called types.

We introduce the use, monitoring, and enforcement of integrity constraints in trust management-style authorization systems. We consider what portions of the policy state must be monitored to detect violations of integrity constraints. Then, we address the fact that not all participants in a trust-management system can be trusted to assist in such monitoring, and show how many integrity constraints can be monitored in a conservative manner so that trusted participants detect and report if the system enters a policy state from which evolution in unmonitored portions of the policy could lead to a constraint violation.

In automated trust negotiation (ATN), two parties exchange digitally signed credentials that contain attribute information to establish trust and make access control decisions. Because the information in question is often sensitive, credentials are protected according to access control policies. In traditional ATN, credentials are transmitted either in their entirety or not at all. This approach can at times fail unnecessarily, either because a cyclic dependency makes neither negotiator willing to reveal her credential before her opponent because the opponent must be authorized for all attributes packaged together in a credential to receive any of them, or because it is necessary to disclose the precise attribute values, rather than merely proving they satisfy some predicate (such as being over 21 years of age). Recently, several cryptographic credential schemes and associated protocols have been developed to address these and other problems. However, they can be used only as fragments of an ATN process. This article introduces a framework for ATN in which the diverse credential schemes and protocols can be combined, integrated, and used as needed. A policy language is introduced that enables negotiators to specify authorization requirements that must be met by an opponent to receive various amounts of information about certified attributes and the credentials that contain it. The language also supports the use of uncertified attributes, allowing them to be required as part of policy satisfaction, and to place their (automatic) disclosure under policy control.

Early work on security-typed languages required that legal information flows be defined statically. More recently, techniques have been introduced that relax these assumptions and allow policies to change at run-time. For example, the Rx language uses a policy language based on RT, a trust management framework for representing authorization policies. While Rx made significant strides toward the goal of allowing policy updates in security-typed languages, in this paper we observe that certain design choices of Rx violate the privacy and autonomy requirements of principals in trust management systems, thus making decentralized control over information difficult. To address these problems, we propose RTI, a new security-typed language. In addition to avoiding prior pitfalls, RTI's most distinguishing characteristic is that it supports fine-grained specification of security for dynamic policy. We also provide a proof of noninterference for RTI.

There have been two parallel themes in access control research in recent years. On the one hand there are efforts to develop new access control models to meet the policy needs of real world application domains. In parallel, and almost separately, researchers have developed policy languages for access control. This paper is motivated by the consideration that these two parallel efforts need to develop synergy. A policy language in the abstract without ties to a model gives the designer little guidance. Conversely a model may not have the machinery to express all the policy details of a given system or may deliberately leave important aspects unspecified. Our vision for the future is a world where advanced access control concepts are embodied in models that are supported by policy languages in a natural intuitive manner, while allowing for details beyond the models to be further specified in the policy language.

Though a user's privileges are often granted based on the tasks that the user is expected to fulfill, the concept of tasks is usually not explicitly modeled in access control. We propose a system where tasks are the central concept that associates users to privileges. Ideally a user should be able to utilize these privileges and fulfill his tasks, but not to take harmful actions. To ensure this, a system often specifies a high-level security property to restrict the sequence of actions that a user can perform. In this paper, we propose a general model of access control in task-based system. This model considers the permissions a user as well as their temporal availability. Based on this model, we investigate the problem of enforcing security properties both statically (i.e., when tasks are assigned) and dynamically (i.e., when actions are performed). We study the complexity of static enforcement, and design efficient dynamic enforcement algorithms that avoiding unnecessary history tracking.

Specifying and managing access control policies is a challenging problem. We propose to develop formal verification techniques for access control policies to improve the current state of the art of policy specification and management. In this paper, we formalize classes of security analysis problems in the context of Role-Based Access Control. We show that in general these problems are PSPACE-complete. We also study the factors that contribute to the computational complexity by considering a lattice of various subcases of the problem with different restrictions. We show that several subcases remain PSPACE-complete, several further restricted subcases are NP-complete, and identify two subcases that are solvable in polynomial time. We also discuss our experiences and findings from experimentations that use existing formal method tools, such as model checking and logic programming, for addressing these problems.

Security in software is often considered a nonfunctional requirement because it is often interpreted as an emergent feature of the system. Too often it is introduced as a last- minute requirement over an otherwise completed product rather than properly integrated during the early stages of software design and development. One significant aspect of security involves access control. This paper proposes a multi-layer model detailing the integration of trust management access control with an application's model behavior. Our previous work focused on modeling the dynamic changes of a trust management policy for the purpose of verifying security properties using model checking. We are working toward integrating both the trust management policy and the mechanisms that enforce that policy for the purpose of verifying security properties. We focus on the Role-based Trust Management (RT) language and suggest concerns specific to it.

While preventative policy enforcement mechanisms can provide theoretical guarantees that policy is correctly enforced, they have limitations in practice. They are inflexible when unanticipated circumstances arise, and most are either inflexible with respect to the policies they can enforce or incapable of continuing to enforce policies on data objects as they move from one system to another. In this paper we propose an approach to enforcing policies not by preventing unauthorized use, but rather by deterring it. We believe this approach is complementary to preventative policy enforcement. We call our approach APPLE for A-Posteriori PoLicy Enforcement. We introduce APPLE Core, a logical framework for using logs to verify that actions taken by the system were authorized. A trust management system is used to ensure that data objects are provided only to users operating on auditable systems who are subject to penalty should they be found in violation. This combination of audit and accountability provides a deterence that strongly encourages trustworthy behavior, thereby allowing a high level of assurance of end-to-end policy enforcement.

Traditional security policies largely focus on access control requirements, which specify who can access what under what circumstances. Besides access control requirements, the availability of services in many applications often further imposes obligation requirements, which specify what actions have to be taken by a subject in the future as a condition of getting certain privileges at present. However, it is not clear yet what the implications of obligation policies are concerning the security goals of a system.In this paper, we propose a formal metamodel that captures the key aspects of a system that are relevant to obligation management. We formally investigate the interpretation of security policies from the perspective of obligations, and define secure system states based on the concept of accountability. We also study the complexity of checking a state's accountability under different assumptions about a system.

Exchange of attribute credentials is a means to establish mutual trust between strangers wishing to share resources or conduct business transactions. Automated Trust Negotiation (ATN) is an approach to regulate the exchange of sensitive information during this process. It treats credentials as potentially sensitive resources, access to which is under policy control. Negotiations that correctly enforce policies have been called “safe” in the literature. Prior work on ATN lacks an adequate definition of this safety notion. In large part, this is because fundamental questions such as “what needs to be protected in ATN?” and “what are the security requirements?” are not adequately answered. As a result, many prior methods of ATN have serious security holes. We introduce a formal framework for ATN in which we give precise, usable, and intuitive definitions of correct enforcement of policies in ATN. We argue that our chief safety notion captures intuitive security goals. We give precise comparisons of this notion with two alternative safety notions that may seem intuitive, but that are seen to be inadequate under closer inspection. We prove that an approach to ATN from the literature meets the requirements set forth in the preferred safety definition, thus validating the safety of that approach, as well as the usability of the definition.

In automated trust negotiation (ATN), two parties exchange digitally signed credentials that contain attribute information to establish trust and make access control decisions. Because the information in question is often sensitive, credentials are protected according to access control policies. In traditional ATN, credentials are transmitted either in their entirety or not at all. This approach can at times fail unnecessarily, either because a cyclic dependency makes neither negotiator willing to reveal her credential before her opponent, because the opponent must be authorized for all attributes packaged together in a credential to receive any of them, or because it is necessary to fully disclose exact attribute values, rather than merely proving they satisfy some predicate (such as being over 21 years of age). Recently, several cryptographic credential schemes and associated protocols have been developed to address these and other problems. However, they can be used only as fragments of an ATN process. This paper introduces a framework for ATN in which the diverse credential schemes and protocols can be combined, integrated, and used as needed. A policy language is introduced that enables negotiators to specify authorization requirements that must be met by an opponent to receive various amounts of information about certified attributes and the credentials that contain it. The language also supports the use of uncertified attributes, allowing them to be required as part of policy satisfaction, and to place their (automatic) disclosure under policy control.

We introduce the use, monitoring, and enforcement of integrity constraints in trust management-style authorization systems. We consider what portions of the policy state must be monitored to detect violations of integrity constraints. Then we address the fact that not all participants in a trust management system can be trusted to assist in such monitoring, and show how many integrity constraints can be monitored in a conservative manner so that trusted participants detect and report if the system enters a policy state from which evolution in unmonitored portions of the policy could lead to a constraint violation.

We have designed an interactive visualization framework for the automated trust negotiation (ATN) protocol and we have implemented a prototype of the visualizer in Java. This framework provides capabilities to perform the interactive visualization of an ATN session, display credentials and policies, analyze the relations of negotiated components, and refine access control policies and negotiation strategies. We give examples of the visualization of ATN sessions and demonstrate the interactive features of the visualizer for the incremental construction of a trust target graph (TTG). Our prototype, which implements most components of the visualization framework, has played a key role in a research project that has developed working trust negotiation systems in an industrial environment.

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.

We propose role-based cascaded delegation, a model for delegation of authority in decentralized trust management systems. We show that role-based cascaded delegation combines the advantages ofrole-based trust management with those of cascaded delegation. We also present an efficient and scalable implementation of role-based cascaded delegation using Hierarchical Certificate-Based Encryption, where the authentication information for an arbitrarily long role-based delegation chain is captured by one short signature of constant size. This implementation also provides strong privacy protection for delegation participants.

Exchange of attribute credentials is a means to establish mutual trust between strangers wishing to share resources or conduct business transactions. Automated Trust Negotiation (ATN) is an approach to regulate the exchange of sensitive information during this process. It treats credentials as potentially sensitive resources, access to which is under policy control. Negotiations that correctly enforce policies have been called safe in the literature. Prior work on ATN lacks an adequate definition of this safety notion. In large part, this is because fundamental questions such as what needs to be protected in ATN? and what are the security requirements? are not adequately answered. As a result, many prior methods of ATN have serious security holes. We introduce a formal framework for ATN in which we give precise, usable, and intuitive definitions of correct enforcement of policies in ATN. We argue that our chief safety notion captures intuitive security goals under both possibilistic and probabilistic analysis. We give precise comparisons of this notion with two alternative safety notions that may seem intuitive, but that are seen to be inadequate under closer inspection. We prove that an approach to ATN from the literature meets the requirements set forth in the preferred safety definition, thus validating the safety of that approach, as well as the usability of the definition.

Trust management is a form of distributed access control using distributed policy. statements. Since one party may delegate partial control to another party, it is natural to ask what permissions may be granted as the result of policy changes by other parties. We study security properties such as safety, and availability for a family of trust management languages, devising algorithms for deciding the possible consequences of certain changes in policy. While trust management is more powerful in certain ways than mechanisms in the access matrix model, and the security properties considered are more than simple safety, we find that in contrast to the classical HRU undecidability of safety properties, our primary security properties are decidable. In particular, most properties we studied are decidable in polynomial time. Containment, the most complicated security property we studied, is decidable in polynomial time for the simplest TM language in the family. The problem becomes co-NP-hard when intersection or linked roles are added to the language.

We introduce a simple Role-based Trust-management language [Formula: see text] and a set-theoretic semantics for it. We also introduce credential graphs as a searchable representation of credentials in [Formula: see text] and prove that reachability in credential graphs is sound and complete with respect to the semantics of [Formula: see text]. Based on credential graphs, we give goal-directed algorithms to do credential chain discovery in [Formula: see text], both when credential storage is centralized and when credential storage is distributed. A goal-directed algorithm begins with an access-control query and searches for credentials relevant to the query, while avoiding considering the potentially very large number of credentials that are unrelated to the access-control decision at hand. This approach provides better expected-case performance than bottom-up algorithms. We show how our algorithms can be applied to SDSI 2.0 (the ‘SDSI’ part of SPKI/SDSI 2.0). Our goal-directed, distributed chain discovery algorithm finds and retrieves credentials as needed. We prove that the algorithm is correct by proving that the algorithm is sound and complete with respect to the credential graph composed of the credentials it retrieves, and that the algorithm retrieves all credentials that constitute a traversable chain. We further introduce a storage type system for [Formula: see text], which guarantees traversability of chains when credentials are well typed. This type system can also help improve search efficiency by guiding search in the right direction, making distributed chain discovery with large number of credentials feasible.

To effectively participate in modern coalitions, member organizations must be able to share specific data and functionality with coalition partners, while ensuring that their resources are safe from inappropriate access. This requires access control models, policies, and enforcement mechanisms for coalition resources. This paper describes a family of coalition-based access control (CBAC) models, developed to provide a range of expressivity with an accompanying range of implementation complexity. We define the protection state of a system, which provides the semantics of CBAC-based access policies. Finally, we briefly examine some of the issues for coalition access policy development and administration, and them complexity of implementing access enforcement mechanisms in a coalition environment.

We introduce the RT framework, a family of role-based trust management languages for representing policies and credentials in distributed authorization. RT combines the strengths of role-based access control and trust-management systems and is especially suitable for attribute-based access control. Using a few simple credential forms, RT provides localized authority over roles, delegation in role definition, linked roles, and parameterized roles. RT also introduces manifold roles, which can be used to express threshold and separation-of-duty policies, and delegation of role activations. We formally define the semantics of credentials in the RT framework by presenting a translation from credentials to Datalog rules. This translation also shows that this semantics is algorithmically tractable.

We give goal-oriented algorithms for discovering credential chains in RTo, a role-based trust-management language introduced in this paper. The algorithms search credential graphs, a representation of RTo credentials. We prove that evaluation based on reachability in credential graphs is sound and complete with respect to the set-theoretic semantics of RTo . RTo is more expressive than SDSI 2.0, so our algorithms can perform chain discovery in SDSI 2.0, for which existing algorithms in the literature either are not goal-oriented or require using specialized logic-programming inferencing engines. Being goal-oriented enables our algorithms to be used when credential storage is distributed. We introduce a type system for credential storage that guarantees well-typed, distributed credential chains can be discovered.

Standard implementation techniques for single-assignment languages modify a data structure without destroying the original, which may subsequently be accessed. Instead a variant structure is created by using newly allocated cells to represent the changed portion and to replace any cell that references a newly allocated cell. The rest of the original structure is shared by the variant. The effort required to leave the original uncorrupted is unnecessary when the program will never reference the original again. This effort includes allocating and initializing new cells, as well as garbage collecting replaced cells. This article specifies a transformation system that introduces update-in-place operations, making Prolog programs update recursive data structures much as an imperative program would. The article introduces the notion of a reuse map, which formalizes reallocation decisions. Because optimal memory reuse is intractable, a heuristical method is presented that performs well in practice. Small Prolog programs that manipulate recursive data structures have their speed increased up to about five times (naive recurse), not counting any speedup obtained by avoiding garbage collection. Quicksort is about three times as fast, merge-sort about one and a half, matrix transposition about twice, and Gaussian elimination is about 1.2 times as fast.

For the class of applicative programming languages, efficient methods for reclaiming the memory occupied by released data structures constitute an important aspect of current implementations. The present article addresses the problem of memory reuse for logic programs through program analysis rather than by run-time garbage collection. The aim is to derive run-time properties that can be used at compile time to specialize the target code for a program according to a given set of queries and to automatically introduce destructive assignments in a safe and transparent way so that fewer garbage cells are created. The dataflow analysis is constructed as an application of abstract interpretation for logic programs. An abstract domain for describing structure-sharing and liveness properties is developed as are primitive operations that guarantee a sound and terminating global analysis. We explain our motivation for the design of the abstract domain, make explicit the underlying implementation assumptions, and discuss the precision of the results obtained by a prototype analyzer.

The abstract domain Prop for analyzing variable groundness in logic programs is considered. This domain consists of (equivalence classes of) propositional formulas whose propositional variables correspond to program variables with truth assignments indicating which program variables are ground. Some ambiguity remains about precisely which formula should be included in Prop so that all interesting sets of program execution states (substitutions) have a unique representation. This ambiguity is clarified by characterizing, both semantically and syntactically, the appropriate definition of Prop. The use of propositional formulas for representing properties of substitutions of a different type than groundness, such as freeness and independence of variables, is discussed.>