SSS Abstracts  Spring 2007

Presented by Nikos Hardavellas, CSD

Prior research shows that database system performance is dominated by off-chip data stalls, resulting in a concerted effort to bring data into on-chip caches. At the same time, high levels of integration have enabled the advent of chip multiprocessors and increasingly large (and slow) on-chip caches. These two trends pose the imminent technical and research challenge of adapting high-performance data management software to a shifting hardware landscape. In this talk we characterize the performance of a commercial database server running on emerging chip multiprocessor technologies. We find that the major bottleneck of current software is data cache stalls, with L2 hit stalls rising from oblivion to become the dominant execution time component in some cases. We analyze the source of this shift and derive a list of features for future database designs to attain maximum performance.

Culture and Environment as Determinants of Women's Participation in Computer Science

Friday, February 9^th, 2007 from 12-1 pm in NSH 1507.

Presented by Carol Frieze, SCS

Most of us know that the numbers of women entering the computer science (CS) major have dropped dramatically over the past few years. Huge amounts of energy, research, money and good intentions have gone into trying to find out why this is happening and what can be done to change the situation. Yet the problem persists and is getting worse. Many gender and CS studies (including the one done here at Carnegie Mellon 1995-1999), conclude that the reasons for women's low participation in CS are based in gender --and particularly in gender differences in how men and women relate to the field. Such studies tend to focus on finding gender differences and then accommodating (what are perceived to be) women's different ways of relating to CS. This is often interpreted as contextualizing the curriculum to make it "female-friendly" to increase women's participation in the field. In this talk we argue that some of these strategies may not be necessary, indeed the traditional approach, and "female friendly" strategies generally, may have become part of the problem itself. We suggest the need for a new approach to how we think about and act on these issues. The alternative approach that we propose is based on a cultural perspective arguing that many of the reasons for women entering --or not entering-- CS programs have little to do with gender and a lot to do with environment and culture. Evidence for this argument comes primarily from qualitative research which shows the effects of changes in the CS micro-culture at Carnegie Mellon, and also draws on studies of other cultural contexts that illustrate a "Women-CS fit".

An Attack Surface Metric

Friday, February 16^th, 2007 from 12-1 pm in NSH 1507.

Presented by Pratyusa K. Manadhata, CSD

Quantitative measurement of security has been a long standing challenge to the research community and is of practical import to industry today. Given two similar software systems, we propose a metric to determine whether one is more secure than another with respect to their attack surfaces. We measure a system's attack surface in terms of three kinds of resources used in attacks on the system: methods, channels, and data. The larger the attack surface, the more insecure the system. This talk describes our attack surface measurement method and the results of applying our method to two IMAP servers and two FTP daemons.

In Partial Fulfillment of the Speaking Requirement

Tactic-Based Motion Modeling and Multi-Sensor Tracking

Friday, March 23^rd, 2007 from 12-1 pm in NSH 1507.

Presented by Yang Gu, CSD

Tracking in essence consists of using sensory information combined with a motion model to estimate the position of a moving object. Tracking efficiency completely depends on the accuracy of the motion model and of the sensory information. For a vision sensor like a camera, the estimation is translated into a command to guide the camera where to look. In this talk, we propose a method to achieve efficient tracking through using a tactic-based motion model, combined vision and infrared sensory information. We present the probabilistic algorithms in detail and present empirical results both in simulation experiment and from their effective execution in a Segway RMP robot.

Joint work with Manuela Veloso

In Partial Fulfillment of the Speaking Requirement

Surviving BGP Attacks: Don't Secure Routing, Secure Data Delivery

Friday, March 30^th, 2007 from 12-1 pm in NSH 1507.

Presented by Dan Wendlandt, CSD

Internet routing and forwarding are vulnerable to attacks and misconfigurations that compromise secure communications between end-systems. Secure routing protocols have been extensively pursued as the means to counter these threats. We argue that merely creating a secure routing protocol does not solve the core problems of secure communication, i.e., end-to-end confidentiality, integrity, and availability. We instead examine the underlying problem of creating a routing system that ensures availability, finding that the goals of secure routing can be better solved by a routing system that relies on multipath routing, end-to-end cryptography, availability monitoring, and path selection algorithms that redistribute traffic to circumvent routing failures. We term this system Availability-Centric Routing, or ACR. Our results demonstrate that even in limited deployment scenarios, ACR achieves significant resilience under powerful attacks without a secure control plane.

In partial fulfillment of the speaking requirement

Joint work with David Andersen, Adrian Perrig, Jennifer Rexford, and Ioannis Avramopoulos

Proof Producing Algorithms

Friday, April 6^th, 2007 from 12-1 pm in NSH 1507.

Presented by Sean McLaughlin, CSD

The design and implementation of algorithms is a fundamental task in computer science. But the process is error-prone, and historically many important programs and algorithms have contained serious errors. While often we can live with the bugs lurking in our algorithms and code, in some domains it is essential that the programs we write be error-free.

In this talk I will survey strategies for designing algorithms that, in addition to computing a result, produce a proof of the correctness of that result. I will then focus on the application of these strategies to a number of areas, such as automated reasoning, programming language semantics, and formalized mathematics.

In partial fulfillment of the speaking requirement.

Reasoning About the Performance of Parallel Programs

Friday, April 13^th, 2007 from 12-1 pm in WeH 5409.

Presented by Daniel Spoonhower, CSD

Parallelism abounds! Taking advantage of this parallelism is a critical challenge for programmers, and even more so, for programming language implementors. While declarative programming languages offer an elegant way to express parallel algorithms, the performance of programs in these languages can be difficult to predict. Changes in the run-time configuration, particularly the scheduler, can have a dramatic effect on performance.

In this talk, I'll give an introduction to cost semantics, a formal mechanism for specifying how a program will perform. A cost semantics serves both as a guide to the programmer and as a contract for the language implementor. I'll give some examples from previous work and explain how I use a cost semantics to reason about the space use of parallel programs. My approach has two parts: first, the semantics yields a profile for each source program, and second, that profile can be used to reconstruct the space usage of the program for any scheduling algorithm. I'll show that for some programs, the choice of scheduler has an asymptotic effect on space usage.

This is joint work with Guy Blelloch and Robert Harper.

In Partial Fulfillment of the Speaking Requirement

Animating Virtual Characters with Motion Planning Techniques

Friday, April 20^th, 2007 from 12-1 pm in WeH 5409.

Presented by Manfred Lau, CSD

Generating realistic motion for animated characters is a difficult problem. The motions that we see in digital animations produced by Pixar, Dreamworks, and other production studios are mostly generated and/or post-processed by hand by many skilled engineers and artists. In this talk, I present two related pieces of work that use motion planning techniques to autonomously and efficiently create realistic animations.

We present a Behavior Planning approach to generate natural motions for animated characters. We show results of synthesized animations involving up to one hundred human and animal characters planning simultaneously in both static and dynamic environments. We then introduce an approach called Precomputed Search Trees that can be used to interactively synthesize these motions. The runtime phase of this method is more than two orders of magnitude faster than existing planning methods or traditional motion synthesis techniques.

In Partial Fulfillment of the Speaking Requirement

Towards Probabilistic Plan Management

Friday, April 27^th, 2007 from 12-1 pm in NSH 1507.

Presented by Laura Hiatt, CSD

In complex, multi-robot domains, replanning when execution deviates from schedule is prohibitively expensive and should be avoided when possible. Myopically avoiding replanning, however, is also undesirable, as it can lead to irreparable conflicts and missed deadlines. Similarly, considering all tasks while repairing is wasteful, as tasks far in the future are repaired again and again as tasks in the present go wrong. On the other hand, narrowly limiting the scope of tasks to be considered for repair can decrease both the completeness and optimality of the system. To address these issues, we have developed a general framework of probabilistic plan management, which manages a schedule during execution by repairing tasks in the near future as necessary, replanning only when the probability of a conflict occurring is high. We have implemented a preliminary, single-agent version of our approach, which in simulation affords large savings in the time spent on plan repair.

In Partial Fulfillment of the Speaking Requirement

This is joint work with Reid Simmons

Encoding Probability Distributions in the Visual Cortex of the Brain

Friday, May 4^th, 2007 from 12-1 pm in NSH 1507.

Presented by Yan Karklin, CSD

Our visual system excels at solving difficult problems, such as finding subtle edges or recognizing complex textures. These computations are carried out by neurons in the visual cortex of the brain; a common description of processing in this area is a hierarchy of increasingly sophisticated feature detectors. However, I will argue that in order to solve these computational problems, visual neurons should encode patterns in the distribution of input images, rather than the presence of particular features in the image. To test this claim, we have developed a hierarchical statistical model whose internal representations explicitly encode probability distributions over its inputs. Trained on images of natural scenes, the model learns a compact code for describing common distributions of images. Units in the model replicate complex properties of visual neurons and exhibit novel behavior that might aid characterization and analysis of poorly understood brain areas.

Joint work with Mike Lewicki

In partial fulfillment of the Speaking Requirement

Hidden Process Models for Analyzing fMRI Data

Friday, May 11^th, 2007 from 12-1 pm in NSH 1507.

Presented by Rebecca Hutchinson, CSD

Functional Magnetic Resonance Imaging (fMRI) is a technique with which we can acquire images of brain activity about once per second at the resolution of a few millimeters while human subjects perform cognitive tasks in the scanner. This data can be helpful to psychologists in forming theories of cognitive behavior, but fMRI data is difficult to analyze because it is high-dimensional, sparse, and noisy. In this talk, I will discuss a class of probabilistic models for multivariate time series data called Hidden Process Models (HPMs) that have been designed for the challenges of the fMRI domain. HPMs can leverage certain types of prior knowledge present in fMRI data to counter the difficult learning setting. I will present background on fMRI, the HPM framework, and experimental results on new kinds of questions that HPMs allow us to address.

Joint work with Tom Mitchell.

In partial fulfillment of the Speaking Requirement.

Web contact: sss+www@cs