 |
2004 . 2003 . 2002 . 2001 . 2000 . 1999 . 1998 . 1997 . 1996 . 1995 . 1994 . 1993 . 1992 . 1991 . 1990
MS-CIS-97-01
A Scalable Architecture for Bilingual Lexicography
I. Dan Melamed
SABLE is a Scalable Architecture for Bilingual LExicography.
It is designed to produce clean broad-coverage translation lexicons
from raw, unaligned parallel texts. Its black-box functionality
makes it suitable for naive users. The architecture has been
implemented for different language pairs, and has been tested
on very large and noisy input. SABLE does not rely on language-specific
resources such as part-of-speech taggers, but it can take advantage
of them when they
are available.
MS-CIS-97-02
D. Scott Alexander, Marianne Shaw, Scott M. Nettles,
and Jonathan M. Smith
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.
MS-CIS-97-03
J. S. Shapiro, S. J. Muir, J. M. Smith, D. J. Farber
Active Networks provide a network infrastructure which can be
programmed on a per-user or even a per-packet basis. While the
flexibility of such systems is seductive, the safety and security
risks are greatly increased. Active network nodes must provide
programmability while respecting policy constraints of the network
provider and protecting nodes and other users from faulty applications.
In addition, many modern applications demand Quality of Service
guarantees which will require exposing selected portions of the
node resource management policy. As shared infrastructure, reliability
beyond that of general purpose computing systems is required.
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.
MS-CIS-97-04
J. S. Shapiro, J. M. Smith, D. J. Farber
Capabilities define a uniform semantics for system service invocation,
enforce separation of concerns and encapsulation, and allow each
program to be restricted to exactly that set of authority it
requires (the principle of least privilege). Capability
systems therefore readily contain and reduce errors at the application
level and improve component testability. If carefully architected,
a capability system should be both faster and simpler than
a comparable access-control-based system. In practice, implementations
have failed to demonstrate such performance.
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.
MS-CIS-97-05 (IRCS 97-05)
Reinforcement Learning of Reactive Navigation for Computer Animation
of Simulated Agents (Dissertation)
Welton M. Becket
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.
MS-CIS-97-06
Scott Nettles
MS-CIS-97-07
Susan B. Davidson, Carmem Hara, and Lucian Popa
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.
MS-CIS-97-08 (GRASP 413)
Performance Evaluation of an Active Vision System (Dissertation)
Ulf M. Cahn von Seelen
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.
MS-CIS-97-09 (IRCS 97-06)
The Anaphoric Parallel between Modality and Tense
Matthew Stone
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.
MS-CIS-97-10 (IRCS 97-07)
Efficient Constraints on Possible Worlds for Reasoning about Necessity
Matthew Stone
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.
MS-CIS-97-11
Omolola Ogunyemi
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).
MS-CIS-97-12
Douglas DeCarlo and Dimitris Metaxas
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.
MS-CIS-97-13
William A. Arbaugh, Angelos D. Keromytis, David J. Farber and
Jonathan M. Smith
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.
MS-CIS-97-14
Peter Buneman, Wenfei Fan, Scott Weinstein
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.
MS-CIS-97-15
Peter Buneman, Wenfei Fan, Scott Weinstein
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.
MS-CIS-97-16
Peter Buneman, Wenfei Fan, Scott Weinstein
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.
MS-CIS-97-17
D. Scott Alexander, William A. Arbaugh, Angelos D. Keromytis
and Jonathan M. Smith
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.
MS-CIS-97-18 (GRASP LAB 415)
R. Sara, R. Bajcsy
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 hard given finite computational resources, unless
more independent measurements directly related to occluding contours
is available. What can be achieved is the substantial reduction of the
artifacts, especially for large matching templates. Reduced artifacts
allow for easier hierarchical matching and for easy fusion of reconstructions
from different viewpoints into a coherent whole.
MS-CIS-97-19 (GRASP LAB 416)
Radim Sara, Ruzena Bajcsy
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.
MS-CIS-97-20 (GRASP LAB 417)
Precision in 3-D Points Reconstructed from Stereo
Gerda Kamberova, Ruzena Bajcsy
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.
MS-CIS-97-21 (GRASP LAB 418)
The Effect of Radiometric Correction on Multicamera Algorithms
Gerda Kamberova, Ruzena Bajcsy
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).
MS-CIS-97-22 (GRASP LAB 419)
Extending Linear System Models to Characterize the Performance Bounds
of a Fixating Active Vision System
Ulf M. Cahn von Seelen, Ruzena Bajcsy
MS-CIS-97-23
Douglas DeCarlo and Dimitris Metaxas
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.
MS-CIS-97-24
Modeling Fluid Phenomena for Computer Graphics and Special Effect
(Dissertation)
Nicholas D. Foster
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.
MS-CIS-97-25
Almost Equalizer, Bayes and Minimax Rules
Gerda Kamberova
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.
MS-CIS-97-26
Jonathan Shapiro, S. Weber
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.
|
|