Seminar Archive – Spring 2000

January 10, 2000

Most state-of-the-art speech recognizers output word lattices as a compact representation of a set of alternate hypotheses. We introduce a new framework for distilling information from word lattices to improve the accuracy of the recognition output and obtain a more perspicuous representation of a set of alternative hypotheses. The motivation for our approach comes from the mismatch between the commonly used evaluation method, namely the number of correct words in the output string, and the standard maximum aposteriori probability hypothesis selection paradigm. Our technique is shown to improve the recognition accuracy on two standard corpora.

We then show that our algorithm can be used as an efficient lattice compression technique. Its success comes from the ability to discard low probability words and recombine the remaining ones to create a new set of hypotheses. In essence, our method is an estimator of word posterior probabilities, and as such could benefit a number of other tasks like word spotting and confidence annotation. Also, the new representation of a set of candidate hypotheses provides a new framework for finding linguistic cues and applying them to disambiguating the word-level confusion sets.

February 10, 2000

Visualization of relational information is an important problem in many areas of computer science, including VLSI design, networks, and telecommunications. Visualization of large graphs is particularly difficult given the constraints imposed by the current technology (limited number of pixels on a screen) and the complexity of the graphs to be displayed (millions of nodes and edges). We consider efficient techniques for displaying large graphs based on the hierarchical decomposition approach: the graph is decomposed into a logarithmic number of layers, such that each layer represents the graph in more detail. Using such a recursive clustering scheme, the graph can be displayed in 3 dimensions to convey its global structure; at the same time, clusters can be displayed alongside the hierarchy to show the local structure in an area of interest. We also develop cluster-based algorithms for drawing large planar graphs such that planarity and c-planarity (a stronger condition for planarity of planar graphs) are maintained. These algorithms are space and time efficient and optimize various aesthetic criteria to enhance the quality of the resulting drawings.

February 11, 2000

Many language processing tasks are dependent on large databases of lexical semantic information, such as WordNet. These hand-built resources are a particular domain, both because domain-specific terms are missing and because the lexicon contains many words or meanings which would be extremely rare in that domain.

This talk describes statistical techniques to automatically extract semantic information about words from text. These techniques could be used in the construction of updated or domain-specific semantic resources as needed.

Given a large corpus of text and no additional sources of semantic information, we build a hierarchy of nouns appearing in the text. The hierarchy is in the form of an IS-A tree, where the nodes of the tree contain one or more nouns, and the ancestors of a node contain hypernyms of the nouns in that node. (An English word A is said to be a hypernym of a word B if native speakers of English accept the sentence “B is a (kind of) A.”)

The talk will also include a detailed discussion of a particular subproblem: determining which of a pair of nouns is more specific. We identify numerical measures which can be easily computed from a text corpus and which can answer this question with over 80% accuracy.

February 17, 2000

Many applications require the handling of moving objects. We concentrate on the special case when a query object is moving and we want to repeatedly answer queries throughout the motion. In particular, we examine segment dragging queries, where a query segment is being translated in a collection of two-dimensional points. We also examine a generalization of segment dragging in three dimensions where a query plane moves arbitrarily in a collection of points. In both cases our algorithms report the points hit by the moving object. We exploit the fact that queries are related and therefore the information computed in answering one query can be used when answering the following one. We also present the first non-trivial algorithm for computing silhouettes of polyhedral models, problem that has many practical applications.

February 18, 2000

Language is a sea of uncertainty. Over the past decade, computational linguistics has been learning to navigate this sea by means of probabilities. Given a newspaper sentence that has hundreds of possible parses, for example, recent systems have set their course for the most probable parse. Defining the most probable parse requires external knowledge about the relative probabilities of parse fragments: a kind of soft grammar.

But how could one LEARN such a grammar? This is a higher-level navigation problem — through the sea of possible soft grammars. I will present a clean Bayesian probability model that steers toward the most probable grammar. It is guided by (1) a prior belief that much of a natural-language grammar tends to be predictable from other parts of the grammar, and (2) some evidence about the phenomena of the specific language, as might be available from previous parsing attempts or small hand-built databases.

Optimizing this model naturally discovers common linguistic transformations in the target language. This ability to generalize allows it to make more efficient use of evidence: to achieve an equally good grammar, as measured by cross-entropy, it requires only half as much training data as the best methods from previous literature.

February 25, 2000

The DrScheme programming environment supports a tower of programming language dialects for different needs and levels of expertise. Building and maintaining this tower posed several interesting software engineering challenges. One of the central problems was to arrange the system so languages could be built by composition and extension.

In my talk, I will first present this extensibility problem and my specific solution. I will then show how this problem is an instance of a more general scenario that has been posed repeatedly in the research literature and that system architects frequently encounter. My work focused attention on this problem, and researchers are presenting a growing number of alternate solutions for it.

To compare the programming paradigms and patterns offered as solutions, I also developed a formal theory of extensibility. I applied this theory to some of the proposed solutions. This investigation lead to a deeper understanding of extensibility, which I then harnessed in the construction of several diverse applications, including the next generation of the language layers in DrScheme. I will discuss some of these findings in the last part of my talk.

February 29, 2000

While we are starting to encounter commercial automatic speech recognizers in everyday life, state-of-the-art systems still have trouble with some tasks. When transcribing news reports, current systems misrecognize one word in ten; transcription of human-to-human conversations is even more errorful (30% word error). The foremost reason for poor performance on these tasks is the increased acoustic and linguistic variability found in less constrained conversational situations. Incorporating knowledge about speaking conditions (fast, slow, noisy, reverberant, etc.) into the statistical models of our speech recognizer can compensate in part for this increased variability. In this talk, I describe three projects in which multiple information sources were combined to improve estimation of the speaking rate of an utterance, to increase robustness to noise and reverberation in transcription of television and radio news reports, and to improve prediction of how and when people will pronounce words in a non-standard manner. These studies suggest that integrating disparate information representations into statistical pattern recognizers is a promising direction for future research.

March 6, 2000

We discuss new approaches to the design of approximation algorithms for several NP-hard scheduling problems in which the objective is to minimize the average completion time.

If we schedule a set of jobs on a set of machines, each job j finishes at some time C(j); our goal is to minimize the (weighted) average of all the C(j). Minimizing this metric tends creates schedules with good throughput, i.e. many jobs are completed quickly.

If all the jobs are available at time 0 and there are no precedence constraints between the jobs, this problem is known to be solvable in polynomial time. Once we introduce release dates, or precedence constraints, or add weights to the jobs, the problem becomes NP-hard. Until about five years ago, no non-trivial approximation algorithms were known for even the “simplest” NP-hard average completion time problems. Over the past five years, there has been a flurry of activity in this area, and a large class of scheduling problems now have (small) constant-factor approximation algorithms, and some have polynomial-time approximation schemes.

A few fundamental underlying ideas have driven the work in this area. We will describe these ideas in the context of the “simplest” NP-hard average completion time problem: a set of jobs arrive over time (have release dates), and the objective is to minimize the average completion time. We will give three approximation algorithms for this problem: a 2-approximation which orders jobs based on a preemptive relaxation, a randomized e/(e-1)-approximation algorithm, and a polynomial-time approximation scheme. We will also describe briefly the experimental implications of these algorithms, and show how these ideas apply to more general problems such as those with parallel or unrelated machines, or precedence constraints among the jobs.

The work we discuss is mainly from several papers joint with Chandra Chekuri (Bell Labs), David Karger (MIT), Rajeev Motwani (Stanford), Balas Natarajan (HP), Cynthia Phillips (Sandia National Labs), and Joel Wein (Polytechnic).

March 7, 2000

We live in a dynamic world full of motion. To interact effectively (as man, animal, or machine), it is necessary to distinguish and identify the intentional or meaningful movements of animate creatures, and discard the non-animate movements such as the swaying of trees or falling leaves. Along these lines, many behaviors throughout the animal kingdom consist of performing and recognizing very specialized patterns of oscillatory motion. In this talk I will present a categorical approach to describing and recognizing oscillatory motions using a simple model having very specific and limited parameter values. Additionally, a complexity ordering on the motions determined from parameter specialization and observations of biological motion will be described. The categorical organization is used as a foundation for a machine vision system designed to recognize these motion patterns. Results of the perceptual method employing the constraints will be shown with synthetic and real video data. Lastly, I will describe an interactive system where users perform particular oscillatory motions to reactive virtual hummingbirds embodying the recognition models. This research explores the categorical structures of oscillatory motion to provide a simple, yet compelling, computational strategy for identifying motion patterns using machine vision. Such categorical methods are useful for characterizing structurally related patterns without the necessity of non-informed ad hoc models.

March 8, 2000

Complex distributed applications, including virtual environments, tele-medicine and video-on-demand, require quality of service (QoS) guarantees on the end-to-end transfer of information across a network. To generate, process and transfer such information in a manner satisfactory to each application requires the management of all the resources, both communication and computation-bound, along the ‘path’ from source to destination. The problem is complicated by the fact that: (1) the quality of service requirements of each application can vary with time, and (2) the availability of each resource varies depending on the demands from (a potentially variable number of) competing applications. In many such situations, static resource allocation results in poor resource utilization and, hence, poor scalability of service. In order to support more applications and provide better overall quality of service, multiple resources must be managed in a coordinated manner.

The problem addressed by this work is to provide the necessary system support to maximize, or at least maintain, the quality of service for distributed, real-time applications, in situations where the availability of each resource varies due to varying application requirements. Efficient policies and mechanisms are needed to coordinate, allocate and adapt communication and computation resources at run-time, in order to meet real-time and other quality of service constraints. Consequently, in this talk, I describe: (1) the Dionisys quality of service infrastructure, that monitors and adapts service on behalf of each application via one or more service managers, and (2) Dynamic Window-Constrained Scheduling (DWCS) of communication and computation resources. Algorithms such as DWCS are designed to reside in the service managers of a QoS infrastructure like Dionisys. Moreover, DWCS is designed to support real-time applications like those described above, with explicit loss and delay constraints. In certain situations, DWCS is provably optimal in terms of the service it provides to applications.

March 9, 2000

Genetic mapping experiments discover the location of many sites, or “markers,” on the genome of a species. Some of these experiments are extremely expensive, computationally intense, and time consuming, and involve millions of dollars, tens of thousands of markers, and years of experimental time.

We propose two changes to these experiments: first, to perform much of the experimentation on only a sample of an experimental population, and second, to use a different method when determining the location of new markers. In the first of these changes, we model the problem of selecting a good mapping sample as a discrete optimization problem, based on the k-center problem. We discuss several heuristic methods for choosing good samples, including linear programming with randomized rounding and simpler greedy methods, and show results for several existing experimental populations.

In the second of these changes, we model the problem of placing new markers as the problem of locating them into “bins” of the genome, which are terminated by biological breakpoints. This approach differs markedly from existing methods, which instead try to determine the correct order of all of the new markers from all possible permutations. Our approach has the advantages that it is very accurate and computationally and experimentally feasible. We show preliminary results which demonstrate that our methods are of high quality and highly compatible with the sample selection approaches we present.

Our two changes offer the possibility of more accurate, less expensive, and faster genetic mapping experiments.

Joint work with Todd Vision, David Shmoys, Steve Tanksley and Rick Durrett

March 10, 2000

Computer security is a much-studied area of computer science, unfortunately characterized as much by art as science. This talk describes some steps taken towards engineering rigor, first in a data-driven analysis of where security vulnerabilities occur in “real life”, and second in a new technique, Chaining Layered Integrity Checks, which addresses many of these vulnerabilities.

I begin with a presentation of preliminary results from a study (performed with the Computer Emergency Response Team) of a life cycle model for security vulnerabilities, based on data from incident reports. The results suggest that the security rule of thumb “10% technology, 90% management” has some basis in fact.

I then turn to the issue of computer system integrity. In a computer system, the integrity of lower layers is typically treated as axiomatic by higher layers. Under the presumption that the hardware comprising the machine (the lowest layer) is valid, the integrity of a layer can be guaranteed if and only if: (1) the integrity of the lower layers is checked, and (2) transitions to higher layers occur only after integrity checks on them are complete. The resulting integrity “chain” inductively guarantees system integrity. If the integrity chain is not preserved between one or more layers in a system design, the integrity of the system as a whole cannot be guaranteed. The Chaining Layered Integrity Checks (CLIC) model is used to develop a system architecture with which integrity for an entire system can be guaranteed. I have also demonstrated that CLIC can be realized, by implementing AEGIS a prototype secure bootstrap system for personal computer systems.

March 13, 2000

Automatic motion planning is a fundamental problem for which no general, practical solution has been found. Applications for motion planning include not only robotics, but problem domains such as intelligent CAD (virtual prototyping), virtual and augmented reality systems (training and computer-assisted operation), and computational biology and chemistry (protein folding and drug design).

Recently, a class of randomized planners called probabilistic roadmap methods (PRMs) has gained much attention. Briefly, during preprocessing randomly generated configurations of the moving object are connected to form a graph, or roadmap, that encodes representative feasible paths for the moving object. During query processing, the start and goal are connected to the roadmap and a path between them is extracted from the roadmap. While PRMs have solved many difficult, previously unsolved problems, they have not been very effective when the solution path must pass through narrow passages. In this talk, we describe several PRM variants developed in our group to address this issue: OBPRM (obstacle-based PRM) which generates roadmap nodes near obstacle surfaces, MAPRM (medial-axis PRM) which samples points on the medial axis of the free space, and a PRM which can be used for systems with closed kinematic chains. Since human insight can sometimes greatly decrease the solution time, we describe randomized techniques, inspired by PRMs, for transforming approximate, user-generated paths collected with a PHANToM haptic device into collision-free paths. Finally, we will discuss recent work on the localization problem for mobile robots. We show results for difficult problems arising in complex 3D environments arising in applications such as part removal studies for complex mechanical products and protein folding.

March 14, 2000

State-of-the-art run-time systems are a poor match to diverse, dynamic distributed applications because they are designed to provide support to a wide variety of applications, without much customization to individual specific requirements. As a result, the performance is disappointing. To address this problem, we propose SMART APPLICATIONS. In the executable of smart applications, the compiler will embed most run-time system services, novel speculative run-time adaptive optimization techniques and a performance-optimizing feedback loop that monitors the application’s performance and adaptively reconfigures the application and the OS/hardware platform. The resulting total resource customization for the application’s own performance gain should lead to major speedups.

SmartApps builds on the foundation of our speculative run-time techniques developed in the context of parallelizing, or restructuring, compilers. This talk will present an overview of software run-time techniques for speculatively parallelizing loops, adaptive algorithm selection for reduction parallelization and architectural support. These methods target irregular, dynamic applications which resist traditional static optimization methods. Typical examples include complex simulations such as SPICE for circuit simulation, DYNA-3D for structural mechanics modeling, and CHARMM for molecular dynamics simulation of organic systems. We present experimental results on loops from the PERFECT, HPF and other benchmarks which show that these techniques can indeed yield significant speedups.

March 15, 2000

Today’s network systems offer considerable power to attackers, which can (a) pursue unlimited attempts to compromise network resources; (b) evade detection; and (c) hide their identity and avoid liability. In this talk, I will present the MarketNet technology I developed for my dissertation. MarketNet introduces a novel approach to large-scale network protection that shifts power from attackers to resource owners. MarketNet uses market mechanisms to price resources and to allocate budgets among consumers. A resource owner can (a) tightly control access to a resource and its exposure to attacks; (b) monitor and audit resource access using resource-independent instrumentation and mechanisms; (c) detect attacks by using generic statistical algorithms; and (d) enforce liability and traceability of attackers. I will show how MarketNet technologies have been applied for the protection of software systems and services, such as the Simple Network Management Protocol (SNMP) and the Java Virtual Machine (JVM). Lastly, I will introduce a MarketNet-based intrusion detection system.

March 17, 2000

Distributed systems have the power and resources needed to solve many interesting problems, in areas ranging from physics to market analysis. However, the complexities of distributed systems prevent many who could benefit from making full use of distributed computing’s power.

My research has focused on providing distributed applications with the information they need to make effective use of the resources available to them. Specifically, I have focused on measuring and predicting network capabilities through the use of network-layer information. Obtaining resource information directly from the network components provides the same accurate performance predictions currently obtained through application-level benchmarking. Furthermore, it offers the scalability and topology discovery needed to support emerging distributed systems. Topology discovery is particularly important for providing performance predictions for parallel applications and building models of distributed systems.

In this talk, I will provide an overview of the network-based performance prediction technique. I have experimentally verified the accuracy of this technique, and it has been implemented in the Remos system at Carnegie Mellon. I will discuss its accuracy and factors affecting its usability, as well as several applications that can benefit from the additional information provided by this technique.

March 30, 2000

BACKGROUND: There is increasing wireless support for data networks with the abundance of mobile clients (palm/hand-held computers, smart devices) as well as the rise in wireless “data-centric” applications (traffic information systems, stock/sports tickers and wireless internet access). This requires support infrastructure via data servers such as portable kiosks, infostations, etc. for timely and efficient delivery of information.

QUESTIONS: We focus on efficient scheduling of data delivery to improve responsiveness of wireless data servers. What is the measure of responsiveness for data delivery? Traditional measures are related to response time, but stretch (slowdown) related measures may be more relevant. What is the mechanism for data delivery? Both unicasting and broadcasting are relevant. What is the suitable user request model, such as (dis)allowing multiple requests simultaneously, single or multiple channel, etc.? Many different scheduling problems arise — some are well known in the classical scheduling literature, some are variations thereof, others are quite novel.

TALK: We will present new online and offline algorithms for scheduling problems in this context, mainly focused on the stretch measure for scheduling data delivery. This will be the bulk of the talk. We will also present experimental results comparing the different algorithms on delivering web data. Many open issues need to be understood before an ultimate solution emerges for data delivery in wireless servers. We will also present a list of open scheduling problems that are likely to be very relevant for data delivery in wireless servers.

March 31, 2000

The PRESTO project (“PRESTO” means Paderborn REal-time STOrage network) is a joint project of the computer science and electrical engineering department of the Paderborn University, funded by the German Science Foundation (DFG). The aim of the project is to develop a scalable, resource-efficient, and robust data server that is able to support real-time data requests. Our basic approach is to develop a single type of hardware component that can be connected to a set of disks as well as to a LAN or a server. The components can be interconnected to form a dedicated network that manages the disks connected to it in such a way that they appear to the outside world like a single, giant disk.

In my talk, I will give a survey of the basic concepts we developed to achieve the goals above, focusing on routing, scheduling and data management. For each of these areas, I will present our algorithmic solutions and discuss how these solutions behave in theory and in simulations.

April 6, 2000

The performance of a network of machines improves if they can share computing resources; that is, if a job arriving at one machine can be executed on another. To achieve the best performance, the scheduler that decides which machine executes each incoming job must use an efficient and intelligent strategy. This work proposes three new strategies for job assignment with beneficial theoretical properties, experimentally proven to perform well in practice. It also includes a complete system, the Jini CBF Package, used to perform intelligent job assignment using one of these strategies on a Jini network.

April 11, 2000

The emergence of embedded systems has been impacting system design paradigms, design flows and tools along many dimensions. The goal of my talk is to present techniques that provide solutions to some of the most challenging problems in embedded system design. In particular, I will talk about intellectual property (IP) protection, power minimization using variable voltage and embedded system design for guaranteed quality of service (QoS).

Short time to market and cost sensitivity of the embedded systems imply a strong need for hardware and software reuse. We have developed a technique that embeds robust copyright marks to system building blocks. We impose additional author-specific constraints on the original IP specification during its creation and/or synthesis. The copyright detector checks whether a synthesized IP block satisfies the author-specific constraints. The strength of the proof of authorship is proportional to the likelihood that an arbitrary synthesis tool incidentally satisfies all the added constraints. I will present the theoretical analysis along with the developed concepts and experimental results obtained on several traditional synthesis problems.

As variable voltage systems are rapidly moving from research testbeds to commercial products (e.g. the Crusoe processor by Transmeta), the real-time OS developers are encountering the challenge of modifying traditional OS scheduling primitives for such systems. I will present a task scheduling paradigm for dynamically changing voltage to minimize the power consumption, while satisfying the system’s real-time constraints.

In the third part of my talk, I will present a two-phase design methodology that optimizes the traditional design objectives while providing guaranteed QoS. The QoS requirements will be considered in the early design stages and other design metrics (e.g., silicon area, performance, and power) will be optimized through configuring system components (CPU and cache). I will illustrate this by showing how to determine the minimal chip size to provide latency and synchronization guarantees to multimedia applications.

April 14, 2000

We strain our eyes, cramp our necks, and destroy our hands trying to interact with computers on their terms. At the extreme, we strap on devices and weigh ourselves down with cables trying to re-create a sense of place inside the machine, while cutting ourselves off from the world and people around us.

The alternative is to make the real environment responsive to our actions. When computers start to possess the same perceptual competencies that we use to communicate and interact, amazing things start to happen: computers disappear into the environment, and the things we do naturally suddenly become the interface. Interactions with the environment that were previously only meaningful to us are now also meaningful to the environment.

My doctoral work has involved advancing the state-of-the-art in perceptual technology to provide deeper perceptual sophistication for computer interfaces. This has included both significant work on computer vision technologies and work on a large number of human-computer interface systems utilizing those technologies, as well as speech perception, wearable technology, and other sensing modalities.

The Dyna system, which is the practical embodiment of my thesis work, combines sophisticated models of the dynamics and kinematics of the human body with real-time statistical vision techniques to create a system that can recover from ambiguities in the observations that cause similar systems to fail: making perceptual interfaces applicable to a wider audience. At the same time, the intimate combination of observations and context create new representations that provide a powerful advantage over the ad hoc features sets previously employed in understanding human motion.

April 19, 2000

Internet applications and users have diverse quality of service expectations, making the existing same-service-to-all model inadequate and limiting. There is a widespread consensus that the Internet architecture has to be extended with service differentiation mechanisms, so that certain users and applications get a better service than others at a higher cost.

One approach, referred to as absolute differentiated services, is based on admission control and resource reservations in order to provide guarantees for absolute performance measures, such as a minimum service rate or a maximum end-to-end delay. Another approach, which is simpler in terms of implementation, deployment, and network manageability, is to offer relative differentiated services between a small number of classes of service. These classes are ordered based on their packet forwarding quality, in terms of per-hop metrics for the queueing delays and loss rates, giving the assurance that higher classes are better than lower classes. The applications and users, in this setting, can dynamically select the class that best meets their quality and pricing constraints, without a priori guarantees for the actual performance level of each class.

In the context of relative services, the Proportional Differentiation Model aims to provide the network operator with the `tuning knobs’ for adjusting the quality spacing between classes, independent of the class loads, and even in short timescales. When this quality spacing is feasible, it can lead to predictable (from the user’s perspective) and controllable (from the provider’s perspective) class differentiation, which are two important features for relative services. The proportional differentiation model can be implemented with simple and scalable router mechanisms for packet scheduling and buffer management.

In this talk, I will summarize our work on the proportional differentiation model, on the related router mechanisms for scheduling and buffer management, and on the provisioning of proportional differentiated services.

April 20, 2000

Java programs are commonly transmitted across a network in the compiled bytecode representation and are then executed by a 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 run. These checks include type correctness, and, as illustrated by previous attacks on the Java Virtual Machine, they are critical to maintain system security.

In order to study the process of verification for a language like Java bytecodes, we have developed a precise specification of a statically-correct bytecode language. This specification takes the form of a type system, and the language features examined include classes, interfaces, constructors, methods, exceptions, and bytecode subroutines.

This talk describes the methodology used to develop the formal system and its benefits. In addition, we describe a prototype implementation of a type checker for our system and discuss some applications of this work. For example, we may augment the type system to check for other program properties, such as the correct use of object locks. This work has also helped to clarify the original bytecode verifier specification, uncovered a security flaw in the Sun verifier implementation, and points to ways in which the Java bytecode language may be simplified and extended.

May 5, 2000

Image-based modeling and rendering techniques greatly advanced the level of photorealism in computer graphics. They were originally proposed to accelerate rendering with the ability to vary viewpoint only. My work in this area focused on capturing and modeling real scenes for novel visual interactions such as varying lighting condition and scene configuration in addition to viewpoint. This work can lead to applications such as virtual navigation of a real scene, interaction with the scene, novel scene composition, interior lighting design, and augmented reality.

I will first briefly introduce my work on image-based modeling and rendering for varying viewpoint only. In the next part, I will present the inverse global illumination technique which refers to recovering reflectance models of various materials present in a real mutual illumination environment. The method’s input is a geometric model of the scene and a set of calibrated photographs taken with known light source positions. The result is a lighting-independent model of the scene’s geometry and reflectance properties, which can be rendered under novel lighting conditions using traditional graphics methods. The underlying philosophy is using low-parameter BRDF models and solving optimization problems to recover the parameters. Synthetic images rendered using recovered BRDF models are comparable to real photographs.

In the last part, I will present the techniques to extract an object-level representation of a real scene which can be rendered with modifications to the existing spatial configuration. The key components here involve automatic algorithms to segment the geometry from range images into distinct surfaces, and register texture from radiance images with the geometry. The top-down segmentation algorithm recursively partitions a point set into a binary tree with individual surfaces as leaves. Our image registration technique can automatically find the camera poses for arbitrary position and orientation relative to the geometry. I will demonstrate the effectiveness of these algorithms on real world scenes.

May 24, 2000

Background: Capability systems have long been known to offer reliability advantages over current operating system architectures. Arguments have been made for and against their security advantages. Both Boebert and Karger have argued that unmodified capability systems cannot enforce mandatory access controls. Poor capability system performance has rendered the debate largely academic, and mainstream capability research was largely abandoned in the mid 1970s. Bershad and Chen have suggested that protection domain crossings have a large, intrinsic cache overhead, and have used some apparently supporting measurements to argue that microkernels (which incorporate such domain crossings) must have non-competitive performance for fundamental structural reasons.

Talk Description: In this talk (or talks), I will present two new results. The first shows that capability systems can meet or exceed the performance of conventional operating system architectures. The second is a formal specification of a policy that solves Lampson’s confinement problem and a verification that this policy is enforceable by a broad class of capability architectures. Given a working confinement mechanism, a non-kernel reference monitor can enforce mandatory access controls with only ordinary privileges and access rights.

The first result is demonstrated by EROS (the Extremely Reliable Operating System). EROS is a high-performance, unmodified (in the sense of Boebert and Karger) capability system built at the University of Pennsylvania. It is transparently persistent; all user-mode state, including processes, is periodically saved with low overhead. It is a modular, microkernel-style system. In spite of this, microbenchmarks show that it meets or exceeds the performance of the latest Linux kernel on semantically comparable operations. [This generation of Linux has incorporated significant optimizations in the areas of these microbenchmarks.] Our talk will show how this performance was accomplished.

The second result is joint work with Sam Weber (now at IBM T.J. Watson Research Center). We have modeled a class of capability systems, formally specified a confinement policy in terms of the protection state of the system, defined an operational semantics for the model, and verified that confinement is enforced given a set of initial static preconditions. In the process, we have identified two lemmas that seem of general use in operating system design and a property of capability systems that particularly seems to support successful information flow analysis.