9031501
Design of a role-based trust-management framework
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.
3062362
Managing Digital Rights using Linear Logic
Digital music players protect songs by enforcing licenses that convey specific rights for individual songs or groups of songs. For licenses specified in industry, we show that deciding whether a license authorizes a sequence of actions is NP-complete, with a restricted version of the problem solvable efficiently using a reduction to maximum network flow. The authorization algorithm used in industry is online, deciding which rights to exercise as actions occur, but we show that all online algorithms are necessarily non-monotonic: each allows actions under one license that it does not allow under a more flexible license. In one approach to achieving monotonicity, we exhibit the unique maximal set of licenses on which there exists a monotonic online algorithm. This set of well-behaved licenses induces an approximation algorithm by replacing each license with a well-behaved license. In a second approach, we consider allowing the player to revise its past decisions about which rights to exercise while still ensuring compliance with the license. We propose an efficient algorithm based on linear logic, with linear negation used to revise past decisions. We prove our algorithm monotonic, live, and sound with respect to the semantics of licenses
215952437
Beyond proof-of-compliance: security analysis in trust management
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 an...
7541818
A type system for object initialization in the Java bytecode language
In the standard Java implementation, a Java language program is compiled to Java bytecode. This bytecode may be sent across the network to another site, where it is then interpreted by the Java Virtual Machine. Since bytecode may be written by hand, or corrupted during network transmission, the Java Virtual Machine contains a bytecode verifier that performs a number of consistency checks before code is interpreted. As illustrated by previous attacks on the Java Virtual Machine, these tests, which include type correctness, are critical for system security. In order to analyze existing bytecode verifiers and to understand the properties that should be verified, we develop a precise specification of statically-correct Java bytecode, in the form of a type system. Our focus in this paper is a subset of the bytecode language dealing with object creation and initialization. For this subset, we prove that for every Java bytecode program that satisfies our typing constraints, every object is initialized before it is used. The type system is easily combined with a previous system developed by Stata and Abadi for bytecode subroutines. Our analysis of subroutines and object initialization reveals a previously unpublished bug in the Sun JDK bytecode verifier.
452980
On Abstraction and the Expressive Power of Programming Languages
We present a tentative theory of programming language expressiveness based on reductions (language translations) that preserve observational equivalence. These are called “abstraction-preserving” because of a connection with a definition of “abstraction” or “information-hiding” mechanism. If there is an abstraction-preserving reduction from one language to another, then essentially every function on natural numbers that is definable in the first is also definable in the second. Moreover, regardless of the set of first-order functions definable in either language, no programming language with an abstraction mechanism can be reduced to a language without. Since Lisp with user-defined special forms does not have an abstraction mechanism, it is therefore not “universal” in this theory, in spite of the ability to define every partial recursive function on the natural numbers. Several examples and counter-examples to abstraction-preserving reductions are given. We do not know whether there is a natural universal language with respect to abstraction-preserving reduction.
2716961
Standard ML-NJ weak polymorphism and imperative constructs
Standard ML of New Jersey (SML-NJ) uses weak-type variables to restrict the polymorphic use of functions that may allocate reference cells, manipulate continuations, or use exceptions. However, the type system used in the SML-NJ compiler has not been presented in a form other than source code and has not been proved correct. A type system, in the form of typing rules and an equivalent algorithm, that appears to subsume the implemented algorithm is presented. Both use type variables of only a slightly more general nature than the compiler. One insight in the analysis is that the indexed type of a free variable is used in two ways, once in describing the applicative behavior of the variable itself and once in describing the larger term containing the variable. Taking this into account, an application rule that is more general than SML-NJ is formulated for applications of polymorphic functions to imperative arguments. The soundness of the type system is proved for imperative code using operational semantics.<<ETX>>
8077305
k-Link Shortest Paths in Weighted Subdivisions
We study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, k, on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these results to obtain approximation algorithms that yield a path having O(k) links and weighted length at most (1+e) times the weighted length of an optimal k-link path, for any fixed e>0. Some of our results make use of a new solution for the 1-link case, based on computing optimal solutions for a special sum-of-fractionals (SOF) problem. We have implemented a system, based on the CORE library, for computing optimal 1-link paths; we experimentally compare our new solution with a previous method for 1-link optimal paths based on a prune-and-search scheme.
2490428
A maximumb-matching problem arising from median location models with applications to the roommates problem
We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
7468814
Coupled optimization in protein docking
Here, we introduce a new approach to macromolecular docking which combines the continuous global optimization algorithm CGU [6, 21] with the grid-based conformational search engine DOT [23]. We also detail the use of this method to dock acetylcholine into the fasciculin-acetylcholinesterase complex. Fasciculin blocks access to the long, narrow pathway leading to the active site, which is located in the interior of the acetylcholinesterase. For this reason, flnding the location computationally is rather non-trivial. We not only successfully identifled the optimal docking conflguration, but were able to do so in a matter of hours.
16064699
Minimum-link watchman tours
We consider the problem of computing a watchman route in a polygon with holes. We show that the problem of finding a minimum-link watchman route is NP-complete, even if the holes are all convex. The proof is based on showing that the related problem of finding a minimum-link tour on a set of points in the plane is NP-complete. We provide a provably good approximation algorithm that achieves an approximation factor of O(log n ).
42803318
File Servers
This chapter discusses file servers that are accessible via some form of local network or internetwork. It characterizes file services from the client point of view along a number of dimensions; distributivity of the service itself, the network environment of the service, the file model supported by the service, the kind(s) of atomic update provided by the service, the techniques used for controlling the allocation of files. It then describes the client interfaces to three existing file services. Finally, the impact of these features on design and implementation is discussed. An appendix contains characterizations of a variety of existing network-based file services using the criteria developed in the chapter.