Active networks accelerate network evolution by permitting the network infrastructure to be programmable, on a per-user, per-packet, or other basis. This programmability must be balanced against the safety and security needs inherent in shared resources.
This paper describes the design, implementation, and performance of a new type of network element, an Active Bridge. The active bridge can be reprogrammed "on the fly", with loadable modules called switchlets. To demonstrate the use of the active property, we incrementally extend what is initially a programmable buffered repeater with switchlets into a self-learning bridge, and then a bridge supporting spanning tree algorithms. To demonstrate the agility that active networking gives, we show how it is possible to upgrade a network from an "old" protocol to a "new" protocol on-the-fly. Moreover, we are able to take advantage of information unavailable to the implementors of either protocol to validate the new protocol and fall back to the old protocol if an error is detected. This shows that the Active Bridge can protect itself from some algorithmic failures in loadable modules.
Our approach to safety and security favors static checking and prevention over dynamic checks when possible. We rely on strong type checking in the Caml language for the loadable module infrastructure, and achieve respectable performance. The prototype implementation on a Pentium-based HP Netserver LS running Linux with 100 Mbps Ethernet LANS achieves ttcp throughput of 16 Mbps between two PCs running Linux, compared with 76 Mbps unbridged. Measured frame rates are in the neighborhood of 1800 frames per second.
EROS (the Extremely Reliable Operating System) is an attractive candidate for resource management in an Active Network node. EROS is a pure capability system which provides complete accountability for persistent, consumable and multiplexed resources. We have implemented a prototype Active Network element on the EROS platform which provides the resource partitioning, quality of service, inter-client protection, and performance required of active networks. This paper presents the architecture, design and performance of this prototype, which is currently running on Intel x86 platforms.
This paper provides an architectural overview of EROS, the Extremely Reliable Operating System. EROS is a persistent capability system which provides complete accountability for persistent, consumable and multiplexed resources. By choosing abstractions to leverage conventional hardware protecgion, and exploiting hardware support in the implementation, a fast pure capability architecture can be demonstrated. This paper describes the system design and the proposed evaluation method for EROS. An implementation of EROS for the x86 platform is currently underway, and we expect to report benchmark results by mid 1998.
Behavioral control has been an effective method for controlling low-level motion for autonomous agents. However, one difficulty is the complexity of designing behaviors and arbitration among behaviors for all but the simplest navigation or motor control tasks. The approach taken here applies reinforcement learning techniques with delayed rewards to behavioral control, building on existing approaches from robotics, computer graphics, and machine learning by dealing with issues specific to autonomous agents for computer animation. In addition, behaviors are assumed to be part of a larger architecture, such as a symbolic reasoner or task-network system, so that the learning can focus on problems for which behavioral control is most appropriate.
Three learning approaches are first considered and compared on two single-agent navigation problems where agents have only local information through simulated sensors. The first uses numerical optimization to find a single configuration of parameters of behaviors. This method is very fast and takes advantage of pre-defined behaviors. However, it is conceptually limited because it does not change parameters over time. The second approach models the problem as a Markov Decision Process (MDP) and finds a policy (a mapping from states to actions) that directly learns behavior from delayed reinforcement without the use the use of pre-defined behaviors. This approach, though conceptually very powerful, is extremely slow even when a generalization method is applied. The third approach, behavior-parameter learning (BP-learning), combines advantages of the first two approaches by learning a policy from perceived state to parameters of pre-defined behaviors using an MDP model: it uses the second approach to schedule rather than optimize the parameters of the first approach. This solution is both powerful, due to varying parameters, and quick to converge because it takes advantage of pre-defined behaviors.
The power of BP-learning for animation is then demonstrated on a group navigation problem which is extremely difficult to solve by hand. Finally, all three methods are found to be applicable in different situations and can apply to other single-agent and group navigation problems for computer animation.
The Collection Programming Language (CPL) is based on a complex value model of data, and has successfully been used for querying, transforming and integrating data from a wide variety of structured data sources -- relational, ACeDB, and ASN.1 among others. However, since there is no notion of objects and classes in CPL, it cannot adequately model recursive types or inheritance, and hence cannot be used to query object-oriented databases (OODBs). By adding a reference type and four operations to CPL -- dereference, method invocation, identity test and class type cast -- it is possible to express a large class of interesting ``safe'' queries against OODBs. As an example of how the extended CPL can be used to query an OODB, we will describe how the extended language has been used as a query interface to Shore databases.
The design of active vision systems requires the integration of action and perception components and therefore involves a range of disciplines, including computer vision, control theory, and mechatronics. Assessments of the performance of the resulting system are needed at all stages of the development. This dissertation addresses the problem of finding both measures and means for evaluating the performance of an active vision system in a systematic and quantitative way. In particular, we examine the performance of a camera pan axis in a monocular fixation task. The work combines model-based analysis with experiments on a real active vision system. We start by constructing models for all components of the system and match the models with the actual hardware through calibration or system identification. For the performance evaluation experiments we built a testbed consisting of two robot manipulators that generate controllable and repeatable target motions. Several factors have been identified that influence the geometry and accuracy of the target motion and its mapping onto the image plane. The first set of experiments tests the linear properties of the active vision system. The experiments measure the frequency response of the system, which is used to identify a linear model of the active vision system. The main problem of linear characterizations of performance is that they cannot model the loss of the target. The second set of experiments explores some of the conditions under which the linear model fails and the system loses the target from its field of view. The knowledge of these performance limits can be used to increase the range of operation of the active vision system by adapting the operating parameters dynamically to the motion characteristics of the target.
In modal subordination, a modal sentence is interpreted relative to a hypothetical scenario introduced in an earlier sentence. In this paper, I argue that this phenomenon reflects the fact that the interpretation of modals is an anaphoric process, precisely analogous to the anaphoric interpretation of tense. Modal morphemes introduce alternative scenarios as entities into the discourse model; their interpretation depends on evoking scenarios for described, reference and speech points, and relating them to one another. Although this account formalizes anaphoric connections using dynamic semantics, it invokes a novel and direct encoding of scenarios as ordinary, static objects (competing analyses take modal referents to be inherently dynamic objects, unlike the referents of pronouns and tenses). The result is a simpler proposal with better empirical coverage.
Modal logics offer natural, declarative representations for describing both the modular structure of logical specifications and the attitudes and behaviors of agents. The results of this paper further the goal of building practical, efficient reasoning systems using modal logics. The key problem in modal deduction is reasoning about the world in a model (or scope in a proof) at which an inference rule is applied---a potentially hard problem. This paper investigates the use of partial-order mechanisms to maintain constraints on the application of modal rules in proof search in restricted languages. The main result is a simple, incremental polynomial-time algorithm to correctly order rules in proof trees for combinations of K, K4, T and S4 necessity operators governed by a variety of interactions, assuming an encoding of negation using a scoped constant ^. This contrasts with previous equational unification methods, which have exponential performance in general because they simply guess among possible intercalations of modal operators. The new, fast algorithm is appropriate for use in a wide variety of applications of modal logic, from planning to logic programming.
To determine the type and magnitude of injuries involved in penetrating trauma from gunshot and stab wounds, a working knowledge of the relationship between human anatomy, physiology, and physical manifestations of injury is required. With ballistic injuries involving multiple entry and exit wounds, determining the extent and type of injuries is made even more difficult as many different trajectories could produce the same external wounds. This work presents a 3D graphical system that allows the user to visualize different bullet path hypotheses as well as stab wound paths in a 3D model of the human body, and to identify the anatomical structures affected for each path. The system also presents the degree of belief that an anatomical structure associated with a given penetration path is injured, expressed as a probability. It is designed to work both with TraumAID (a system for providing decision support in the initial definitive management of trauma) and MediSim (a system that simulates casualties, medics and interactions between them).
This paper describes a framework for the estimation of shape from sparse or incomplete range data. It uses a shape representation called blending, which allows for the geometric combination of shapes into a unified model---selected regions of the component shapes are cut-out and glued together. Estimation of shape using this representation is realized using a physics-based framework, and also includes a process for deciding how to adapt the structure and topology of the model to improve the fit. The blending representation helps avoid abrupt changes in model geometry during fitting by allowing the smooth evolution of the shape, which improves the robustness of the technique. We demonstrate this framework on a series of experiments showing its ability to automatically extract structured representations from range data given both structurally and topologically complex objects.
Integrity is rarely a valid presupposition in many systems architectures, yet it is necessary to make any security guarantees. To address this problem, we have designed a secure bootstrap process, AEGIS, which presumes a minimal amount of integrity, and which we have prototyped on the Intel x86 architecture. The basic principle is sequencing the bootstrap process as a chain of progressively higher levels of abstraction, and requiring each layer to check a digital signature of the next layer before control is passed to it.
A major design decision is the consequence of a failed integrity check. A simplistic strategy is to simply halt the bootstrap process. However, as we show in this paper, the AEGIS bootstrap process can be augmented with automated recovery procedures which preserve the security properties of AEGIS under the additional assumption of the availability of a trusted repository. We describe two means by which such a repository can be implemented, and focus our attention on a network-accessible repository.
We present a class of path constraints of interest in connection with both structured and semistructured databases, and investigate their associated implication problems. These path constraints are capable of expressing natural integrity constraints that are not only a fundamental part of the semantics of the data, but are also important in query optimization. We show that, despite the simple syntax of the constraints, the implication problem for the constraints is r.e. complete and the finite implication problem for the constraints is co-r.e. complete. Indeed, we establish the existence of a conservative reduction of the set of all first-order sentences to the path constraint language.
In [MS-CIS-97-14] we introduced a path constraint language and established the undecidability of its associated implication problems. In this paper, we identify several fragments of the language, and establish the decidability of the implication problems for each of these fragments in semistructured databases. In addition, we demonstrate that each of these fragments suffices to express important semantic information such as inverse relationships and local database constraints commonly found in object-oriented databases.
Path constraints have been studied for semi-structured data. In this paper, we investigate path constraints for structured data. We show that there is interaction between path constraints and type constraints. In other words, results on path constraint implication in semistructured databases may no longer hold in the presence of types. We also investigate the class of word constraints for databases of two practical object-oriented data models. In particular, we present an abstraction of the databases in these models in terms of first-order logic, and establish the decidability of word constraint implication in these models.
Active Networks are a network infrastructure which is programmable on a per-user or even per-packet basis. Increasing the flexibility of such network infrastructures invites new security risks. Coping with these security risks represents the most fundamental contribution of Active Network research. The security concerns can be divided into those which affect the network as a whole and those which affect individual elements. It is clear that the element problems must be solved first, as the integrity of network-level solutions will be based on trust of the network elements.
In this paper, we describe the architecture and implementation of a Secure Active Network Environment (SANE), which we believe provides a basis for implementing secure network-level solutions. We guarantee that a node begins operation in a trusted state with the AEGIS secure bootstrap architecture. We guarantee that the system remains in a trusted state by applying dynamic integrity checks in the network element's run time system, a novel naming system, and applying node-node authentication when needed.
The SANE implementation is for x86 architectures, currently those running one of several varieties of UNIX.
In this paper we study occluding contour artifacts in the area-based stereo
matching. These artifacts are false, although highly correlated responses of
the matching operator to the occlusion boundary and cause the objects to
extend beyond their true boundaries in disparity maps. The effect is so strong
that is cannot be ignored. Current matching methods do not attempt to avoid
the problem. We show what is the physical phenomenon that gives rise to the
artifacts and design a matching criterion that accommodates the presence of
the occlusions as opposite to methods that identify and remove the artifacts.
This approach leads to the problem of measurement contamination studied in
statistics. We show that such problem is
We address the problem of automatically reconstructing m-manifolds of unknown topology from unorganized points in metric p-spaces obtained from a noisy measurement process. The point is first approximated by a collection of oriented primitive fuzzy sets over a range of resolutions. Hierarchical multiresolution representation is then computed based on the relation of relative containment defined on the collection. Finally, manifold structure is recovered by establishing connectivity of position and orientation, and local topological constraints. The method has been successfully applied to the problem of surface reconstruction from polynocularr-stereo data with many outlets.
We characterize the precision of a 3-D reconstruction from stereo: we derive confidence intervals for the components (X,Y,Z) of the reconstructed 3-D points. The precision assessment can be used in data rejection, data reduction, and data fusion of the 3-D points. Also, based on the confidence intervals a bad/failing stereo camera pair can be detected, and discarded from a polynocular stereo system. Experimentally, we have evaluated the performance of the confidence intervals for Z in terms of empirical capture frequencies vs theoretical probability of capture for a test, ground truth, scene. We have tested the interval estimation procedure on more complex scenes (for example, human faces), but since we do not have ground truth models, we have evaluated the performance in such cases only quantitatively. Currently we are developing "ground truth" models for more complex (such as general indoor) scenes, and will evaluate quantitatively the performance of the confidence intervals for the depth of the reconstructed points in the "automatic" rejection of 3-D points which have high degree of uncertainty.
We present results confirming the importance of radiometric correction in multicamera applications. Although, we compensate for systematic noise only, we review all noise sources in the video sensor (systematic and random). We use a simple model for radiometric correction of digital images. The correction procedure is tested on the disparity map computation in stereo matching, particularly in a case where stereo usually fails -- almost textureless white surface. Without correcting radiometricly, the matching algorithm matches systematic noise components in the two images. With the correction, after removing the systematic noise, an improvement of 26% to 59% in relative rms of the disparity map is demonstrated (the higher the intensity of the flat field, the better the improvement).
Optical flow provides a constraint on the motion of a deformable model. We derive and solve a dynamic system incorporating this constraint, producing a model-based least-squares optical flow solution. Our solution also ensures the constraint remains satisfied when edge information is used. Constraint enforcement can be relaxed using a Kalman filter, which permits small constraint violations based on the noise present in the optical flow information, and enables optical flow and edge information to be combined more robustly and effectively. The use of a 3-D model reduces or eliminates problems associated with optical flow computation. We apply this framework to the estimation of face shape and motion. Our 3-D deformable face model uses a small number of parameters to describe a rich variety of face shapes and facial expressions. We present experiments in extracting the shape and motion of a face from image sequences.
This document describes a new animation technique for modeling the turbulent rotational motion that occurs when liquids and gases interact with solid objects and the surrounding medium. Realistic fluid behavior is achieved by using the Navier-Stokes equations for incompressible flow, while computation times are minimized by solving these equations at a relatively low resolution. The result is a stable and efficient animation tool for computer graphics, that can handle effects such as swirling steam, rolling or billowing smoke, gusting wind, ocean wave motion, fountains, and simple explosions. In addition, the numerical method developed provides mechanisms for controlling and specifying particular fluid behavior as well as for incorporating limited interaction with dynamic buoyant objects. Particular emphasis is given to issues of computational efficiency and ease-of-use of the method by an animator. We present the details of the model, together with examples illustrating its use.
In this report minimax and near-minimax nonrandomized decision rules under zero-one loss for a restricted location parameter of an absolutely continuous distribution are obtained. Two types of rules are addressed: monotone and non-monotone. A complete-class theorem is obtained in the monotone case, where the results are an extension of a previous work of Zeytinoglu and Mintz (1984) from the case of MLR sampling distributions to the case of 2e-MLR (defined in the report). It is also proven that every continuous monotone increasing rule is Bayes with respect to nondenumerably many essentially different priors. The construction for generating the priors is presented. Nonmonotone near-minimax almost equalizer rules are derived for problems characterized by non-2e-MLR distributions. The derivation is based on the evaluation of a distribution-dependent function. The methodological importance of this function is that it is used to unify the discrete- and continuous-parameter problems, and to obtain bounds on the minimax risk for the non-2e-MLR case. The results related to the nonmonotone rules are a novel theoretical contribution. This report is based on results from Kamberova, "Robust Location Estimation for MLR and Non-MLR Distributions", Tech. Report MS-CIS-92-93, 1992.
A confined program is one which is unable to leak information to an unauthorized party or modify unauthorized resources. Confinement is an essential feature of any secure component-based system. This paper presents a proof of correctness of the EROS operating system architecture with respect to confinement. We give a formal statement of the requirements, construct a model of the architecture's security policy and operational semantics, and show that the architecture enforces the confinement requirements if a small number of initial static checks on the confined subsystem are satisfied. The mechanism does not rely on the run-time values of user state or analysis of the programs' algorithm(s).
Our verification methodology borrows heavily from techniques developed in the programming languages community. We view the operating system as a programming language whose operations are the kernel calls. This has the advantage that the security requirements of concern can be stated in forms analogous to those of type inference and type soundness -- which programming language techniques are well suited to deal with. The proof identifies a set of necessary fundamental lemmas that any system must observe in order to be able to confine information flow. The method used generalizes to any capability system.