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.
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...
14904191
Games and the Impossibility of Realizable Ideal Functionality
A cryptographic primitive or a security mechanism can be specified in a variety of ways, such as a condition involving a game against an attacker, construction of an ideal functionality, or a list of properties that must hold in the face of attack. While game conditions are widely used, an ideal functionality is appealing because a mechanism that is indistinguishable from an ideal functionality is therefore guaranteed secure in any larger system that uses it. We relate ideal functionalities to games by defining the set of ideal functionalities associated with a game condition and show that under this definition, which reflects accepted use and known examples, bit commitment, a form of group signatures, and some other cryptographic concepts do not have any realizable ideal functionality.
52847645
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. >
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
12997315
PER models of subtyping, recursive types and higher-order polymorphism
We relate standard techniques for solving recursive domain equations to previous models with types interpreted as partial equivalence relations (per's) over a Dm lambda model. This motivates a particular choice of type functions, which leads to an extension of, such models to higher-order polymorphism. The resulting models provide natural interpretations for function spaces, records, recursively defined types, higher-order type functions, and bounded polymor-phic types Y-X <: Y. A where the bound may be of a higher kind. In particular, we may combine recursion and polymorphism in a way that allows the bound Y in VX <: Y. A to be recursive y defined. The model may also be used to interpret so-called " F-bounded polymorphism. " Together, these features allolv us to represent several forms of type and type functions that seem to arise naturally in typed object-oriented programming. 1 Introduction In type systems aimed towards object-oriented programming , several typing ideas naturally arise. The most basic are subtyping, the fact that values of one type may be treated as values of another, polymor-phism, and recursively defined types. the Powell Foundation. t s~lpported in part by an NSF PYI Award, matching funds from Digital Equipment Corporation, the Powell Foundation, and Xerox Corporation NSF grant CCR-881 4921 and the Wal-lace F. and Lucille M. Davis Faculty Scholarship. Pennksion to copy without fee all or part of this material is granted provided that tie copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of tbe publication and its date appear, and notice is given that copying is by permission of tbe Association for Computing Machinery. To copy otherwise , or to republish, requires a fee sad/or specific permission. the existing, implemented type systems for object-oriented languages have notable errors (see, [CO089]), it is important to prove the soundness of these type systems. The primary technique for doing so is by constructing a selmantic model. A class of semantic models for languages with subtyp-ing, polymorphism and recursion are developed in [Cop85, Ama91, Car89, AP90]. These models all interpret types as partial equivalence relations (per's) over suitable Dm structures obtained by the so-called " inverse limit') construction. The main contributions of this paper are to provide a general framework for understanding type recursion in these models and to extend per models to higher-order type functions and additional forms of polymorphism. Since the use of per's over …
9120385
Algorithms for two-box covering
We study the problem of covering a set of points or polyhedra in R3 with two axis-aligned boxes in order to minimize a function of the measures of the two boxes, such as the sum or the maximum of their volumes. This 2-box cover problem arises naturally in the construction of bounding volume hierarchies, as well as in shape approximation and clustering. Existing algorithms solve the min-max version of the exact problem in quadratic time. Our results are more general, addressing min-max, min-sum and other versions. Our results give the first approximation schemes for the problem, which run in nearly linear time, as well as some new exact algorithms. We give (1+ε)-approximation algorithms for minimizing the maximum or sum of volumes (or surface areas, diameters, widths, or girths) of the two boxes in R3. We investigate also the problem of computing balanced coverings, in which each box covers at least a fraction of the input objects, and we discuss the application to constructing provably-good bounding volume hierarchies of polyhedra. We also generalize our results to higher dimension.
8377397
Boundary recognition in sensor networks by topological methods
Wireless sensor networks are tightly associated with the underlying environment in which the sensors are deployed. The global topology of the network is of great importance to both sensor network applications and the implementation of networking functionalities. In this paper we study the problem of topology discovery, in particular, identifying boundaries in a sensor network. Suppose a large number of sensor nodes are scattered in a geometric region, with nearby nodes communicating with each other directly. Our goal is to find the boundary nodes by using only connectivity information. We do not assume any knowledge of the node locations or inter-distances, nor do we enforce that the communication graph follows the unit disk graph model. We propose a simple, distributed algorithm that correctly detects nodes on the boundaries and connects them into meaningful boundary cycles. We obtain as a byproduct the medial axis of the sensor field, which has applications in creating virtual coordinates for routing. We show by extensive simulation that the algorithm gives good results even for networks with low density. We also prove rigorously the correctness of the algorithm for continuous geometric domains.
120248919
Hamiltonian triangulations for fast rendering
High-performance rendering engines are often pipelined; their speed is bounded by the rate at which triangulation data can be sent into the machine. An ordering such that consecutive triangles share a face, which reduces the data rate, exists if and only if the dual graph of the triangulation contains a Hamiltonian path. We (1) show that any set of n points in the plane has a Hamiltonian triangulation; (2) prove that certain nondegenerate point sets do not admit a sequential triangulation; (3) test whether a polygon P has a Hamiltonian triangulation in time linear in the size of its visibility graph; and (4) show how to add Steiner points to a triangulation to create Hamiltonian triangulations that avoid narrow angles.
207132060
Terrain Decomposition and Layered Manufacturing
We consider a problem that arises in generating three-dimensional models by methods of layered manufacturing: How does one decompose a given model P into a small number of sub-models each of which is a terrain polyhedron? Terrain polyhedra have a base facet such that, for each point of the polyhedron, the line segment joining the point to its orthogonal projection on the base facet lies within the polyhedron. Terrain polyhedra are exactly the class of polyhedral models for which it is possible to construct the model using layered manufacturing (with layers parallel to the base facet), without the need for constructing "supports" (which must later be removed). In order to maximize the integrity of a prototype, one wants to minimize the number of individual sub-models that are manufactured and then glued together. We show that it is NP-hard to decide if a three-dimensional model P of genus 0 can be decomposed into k terrain polyhedra. We also prove a two-dimensional version of this theorem, for the case in which P is a polygonal region with holes. Both results still hold if we are restricted to isothetic objects and/or axis-parallel layering directions.
6478208
Chemistry in Bioinformatics
AbstractChemical information is now seen as critical for most areas of life sciences. But unlike Bioinformatics, where data is openly available and freely re-usable, most chemical information is closed and cannot be re-distributed without permission. This has led to a failure to adopt modern informatics and software techniques and therefore paucity of chemistry in bioinformatics. New technology, however, offers the hope of making chemical data (compounds and properties) free during the authoring process. We argue that the technology is already available; we require a collective agreement to enhance publication protocols.