896820
A state-transition model of trust management and access control
Abstract: We use a state-transition approach to analyze and compare the core access control mechanisms that are characteristic of a variety of trust management, access control list, and capability-based systems. The framework, which characterizes the set of rights a subject has over an object after any sequence of actions, is based on abstract system states, state transitions, and logical deduction of access control judgments. We present abstract models representing the access control portion of trust management, access control lists, and two versions of capabilities, proving various correspondence and simulation relations between these models. The main results include an equivalence between access control lists (ACLs) and capabilities viewed as rows of the Lampson access matrix and the (proper) subsumption of a form of ACLs by an "unforgeable reference" form of capabilities. The access control mechanism at the heart of distributed trust management systems is formally shown to provide a tractable compromise between unrestricted capability passing from the capability models and easy revocation provided by access control lists. The underlying simulations show how trust management compares with more established access control mechanisms, independent of features such as local name spaces and certificate authorization hierarchies.
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...
18708753
Unification and ML-Type Reconstruction
We study the complexity of type reconstruction for a core fragment of ML with lambda abstraction, function application, and the polymorphic let declaration. We derive exponential upper and lower bounds on recognizing the typable core ML expressions. Our primary technical tool is uniication of succinctly represented type expressions. After observing that core ML expressions, of size n, can be typed in DTIME(2 n), we exhibit two diierent families of programs whose principal types grow exponentially. We show how to exploit the expressiveness of the let-polymorphism in these constructions to derive lower bounds on deciding typability: one leads naturally to NP-hardness and the other to DTIME(2 n k)-hardness for each integer k 1. Our generic simulation of any exponential time Turing Machine by ML type reconstruction may be viewed as a nonstandard way of computing with types. Our worst-case lower bounds stand in contrast to practical experience, which suggests that commonly used algorithms for type reconstruction do not slow compilation substantially.
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.
16397953
Parametricity and Variants of Girard's J Operator
Abstract The Girard–Reynolds polymorphic λ -calculus is generally regarded as a calculus of parametric polymorphism in which all well-formed terms are strongly normalizing with respect to β -reductions. Girard demonstrated that the addition of a simple “non-parametric” operation, J , to the calculus allows the definition of a non-normalizing term. Since the type of J is not inhabited by any closed term, one might suspect that this may play a role in defining a non-normalizing term using it. We demonstrate that this is not the case by giving a simple variant, J′ , of J whose type is otherwise inhabited and which causes normalization to fail. It appears that impredictivity is essential to the argument; predictive variants of the polymorphic λ -calculus admit non-parametric operations without sacrificing normalization.
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
10451656
Matching points into noise regions: combinatorial bounds and algorithms
We consider several cases of the point matching problem in which we are to find a transformation of a set of n points such that each transformed point lies in one of n given pairwisedisjoint “noise regions”. We prove upper and lower bounds on the number of possible matches, under a variety of types of transformations (rotations, translations, similarity, etc.) and noise regions (cmcles, squares, polygons, etc.). We also give efficient algorithms for computing the set of all possible matches, along with a corresponding transformation that realizes each match.
5227025
Curved PN triangles
To improve the visual quality of existing triangle-based art in realtime entertainment, such as computer games, we propose replacing flat triangles with curved patches and higher-order normal variation. At the hardware level, based only on the three vertices and three vertex normals of a given flat triangle, we substitute the geometry of a three-sided cubic Bezier patch for the triangle’s flat geometry, and a quadratically varying normal for Gouraud shading. These curved point-normal triangles, or PN triangles, require minimal or no change to existing authoring tools and hardware designs while providing a smoother, though not necessarily everywhere tangent continuous, silhouette and more organic shapes. CR Categories: I.3.5 [surface representation, splines]: I.3.6— graphics data structures
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.
2431867
New results on shortest paths in three dimensions
We revisit the problem of computing shortest obstacle-avoiding paths among obstacles in three dimensions. We prove new hardness results, showing, e.g., that computing Euclidean shortest paths among sets of "stacked" axis-aligned rectangles is NP-complete, and that computing L1-shortest paths among disjoint balls is NP-complete. On the positive side, we present an efficient algorithm for computing an L1-shortest path between two given points that lies on or above a given polyhedral terrain. We also give polynomial-time algorithms for some versions of stacked polygonal obstacles that are "terrain-like" and analyze the complexity of shortest path maps in the presence of parallel halfplane "walls.
24130262
Geometric Knapsack Problems
We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following “fence enclosure” problem: Given a set S of n points in the plane with values v i ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the “value” of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowing S to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of up to K connected components. When there is an upper bound on the length of fence available, we show that the problem is N P-complete. Additionally we provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.