Quick links

CS Department Colloquium Series

Side Channels and their Mitigation in Cloud Computing Security

Date and Time
Monday, March 1, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Eran Tromer
Host
Jennifer Rexford
Today's computers run numerous processes of different sensitivity and trustworthiness, and often the only boundary between a hostile network and sensitive data relies on flimsy confinement assumptions. The platform purports to protect processes from each other, but side channels arise from lower architectural layers, such as contention for shared hardware resources, and create inadvertent cross-talk. For example, we have shown how observing contention for the CPU cache allows an attacker to steal other users' encryption keys in a few milliseconds.

Confinement violations are especially grievous in the context of cloud computing ("infrastructure as a service"), where users acquire computational capacity in the form of virtual machines running on a service provider's shared hardware pool. Cross-talk between mutually-untrusting virtual machines running on the same hardware creates the risk of information exfiltration across machines and between users, as we have demonstrated on Amazon EC2.

These security vulnerabilities raise the challenge of achieving trustworthy computation on leaky platforms. We discuss potential solutions, including a new work on mitigating side channels using just-in-time dynamic transformation of x86 machine code.

This talk includes joint works with Saman Amarasinghe, Dag Arne Osvik, Thomas Ristenpart, Ron Rivest, Stephan Savage, Hovav Shacham, Adi Shamir and Qin Zhao.

Physical Interfaces For Applications In Music

Date and Time
Wednesday, February 24, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Kenneth Steiglitz
Since the 1960s at the latest, the computer has been capable of digitally synthesizing any perceivable sound. However, in a live context, human-computer interfaces limit the bandwidth and quality of the interaction between the performer and the sound synthesizer. This talk focuses on physical interfaces for music, which operate according to the laws of physics to seamlessly and intimately connect musicians with sound synthesizers. In particular, we study how to design interfaces that assist a performer in making musical gestures. For example, the haptic drum provides a performer's drumstick with an extra push every time that the performer strikes the drum. This device allows the performer to make gestures that would otherwise be very difficult or impossible, such as arbitrarily long one-handed drum rolls and arbitrarily complex rudiments. Next, we explain how to assist a performer in accurately selecting pitches from a continuous range on a Theremin-like haptic interface. We augment it with detents allowing the performer to feel the locations of equal-tempered pitches, yet the performer can still perform arbitrary pitch inflections such as glissandi, falls, and scoops. With the help of a subject test, we demonstrate that traditional detents as well as novel force-sensitive detents can provide accuracy improvements over simpler types of haptic feedback, such as spring feedback. In closing, we relate the work to research in robotics and mixed reality.

Who are your closest relatives? Algorithms for reconciling non-binary species trees

Date and Time
Wednesday, February 17, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Mona Singh
Reconstruction of trees describing relationships among species is of vital importance to evolutionary studies. Species trees not only reveal the history of life, they also provide a framework for understanding the evolution of physiology, morphology, and cellular circuitry. Although gene sequences have proved a powerful source of evidence for inferring species trees, incorrect species trees can result when the histories of the species and the gene differ. Gene duplications, gene losses and transfer of genes from one species to another can all result in a gene tree which disagrees with the species tree. These events can be inferred and corrected for by comparing the gene and species trees, a process called reconciliation.

While reconciling a binary gene tree with a binary species tree is a well-studied, tractable problem, the standard reconciliation algorithm yields incorrect results when applied to non-binary species trees. Binary reconciliation makes simplifying assumptions about genetic variation in ancestral populations that are not justified when the species tree is non-binary. We present the first formal algorithms for reconciling binary gene trees with non-binary species trees. Our algorithms, which combine models from standard reconciliation and population genetics, have been implemented in Notung, a free, publicly available software tool available at http://www.cs.cmu.edu/~durand/Notung. I will discuss the application of these methods to resolving uncertainty in species trees, with examples from species lineages that are currently debated in the evolutionary biology literature.

Show and Tell, Search and Research

Date and Time
Thursday, February 18, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Craig Nevill-Manning, from Google
Host
Jennifer Rexford
Given a query where the answer is sitting on a single web page, search engines do a decent job of identifying that web page. Some queries, however, are difficult to express in text: an image is worth a thousand query terms. At other times, a textual query is sufficient, but it's difficult to type (walking, driving). And some research tasks don't have a simple answer already computed: it's necessary to synthesize an answer from multiple sources. I'll talk about some of the research projects at Google directed at solving these problems, including Google Goggles, Search by Voice, and Google Squared, and some of the other challenges that we're tackling that go beyond returning ten blue links.

Dr. Craig Nevill-Manning joined Google in 2000 as a Senior Research Scientist, responsible for developing new high-precision search techniques for use in the Google search engine. He went on to found Google's first satellite software engineering center, located in New York City, where he is currently an Engineering Director. Nevill-Manning joined Google from the Computer Science Department of Rutgers University, where he conducted research in data compression, information retrieval and computational biology. Prior to Rutgers, Nevill-Manning was a post-doctoral fellow in the Biochemistry Department of Stanford University, where he developed eMOTIF, a software suite used by many pharmaceutical research laboratories to identify the role of particular proteins within cells.

Nevill-Manning has published 41 research papers and received a National Science Foundation Career Grant. A native of New Zealand, Nevill-Manning earned a BS in Computer Science from Canterbury University and a PhD in Computer Science from Waikato University.

Simultaneous Alignment and Phylogenetic Tree Estimation

Date and Time
Wednesday, February 3, 2010 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Mona Singh
Molecular sequences evolve under processes that include substitutions, insertions, and deletions (jointly called "indels"), as well as other mechanisms (e.g., duplications and rearrangements). The inference of the evolutionary history of these sequences has thus been performed in two stages: the first estimates the alignment on the sequences, and the second estimates the tree given that alignment. While such methods seem to work well on relatively small datasets, these two-stage approaches can produce highly incorrect trees and alignments when applied to large datasets, or ones that evolve with many indels. In this talk, I will present a new method, SATe, that my lab has been developing that uses maximum likelihood to estimate the alignment and tree at the same time, and that can be used to analyze datasets with up to 1000 sequences on a desktop in 24 hours. Our study, using both real and simulated data, shows that this method produces much more accurate trees than the current best methods.

Tandy Warnow is Professor of Computer Sciences at the University of Texas at Austin. Her research combines mathematics, computer science, and statistics to develop improved models and algorithms for estimating complex and large-scale evolutionary histories in both biology and historical linguistics. Tandy received her PhD in Mathematics at UC Berkeley under the direction of Gene Lawler, and did postdoctoral training with Simon Tavare and Michael Waterman at USC. She received the National Science Foundation Young Investigator Award in 1994, and the David and Lucile Packard Foundation Award in Science and Engineering in 1996. Tandy is a member of five graduate programs at the University of Texas, including Computer Science; Ecology, Evolution, and Behavior; Molecular and Cellular Biology; Mathematics; and Computational and Applied Mathematics. She is also the director for the multi-disciplinary CIPRES (Cyber-Infrastructure for Phylogenetic Research) Project, currently funded by the NSF under their Information Technology Program.

PlanetLab: From Testbed to Service Deployment Platform

Date and Time
Wednesday, December 9, 2009 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Marc Fiuczynski, from Princeton Computer Science
PlanetLab was originally designed to be a realistic testbed for networking and distributed systems research. It has served that role quite well. More recently, however, it has also become a practical platform for rapidly deploying (and then effectively managing) network services that have value to a wide-range of user communities (and a diverse set of network environments).

This talk describes three such deployments: (1) providing web connectivity to remote villages and schools; (2) capturing gold-standard measurements of broadband connectivity in the US; and (3) supporting high-speed content distribution in a Telco access network.

Smart Assertions for Dumb Provers

Date and Time
Wednesday, December 16, 2009 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
David Naumann, from Stevens Institute of Technology
Host
Andrew Appel
Assertions are widely used for runtime checking of software correctness, and increasingly used for compile time checking of simple properties like array index bounds. Structural integrity of pointer based data structures and design patterns often involves recursively defined properties which are costly to check at runtime and which appear to be unsuited to static checking using fully automated theorem provers. Remarkably, judicious use of ghost state lets programmers express recursive properties in pure first order logic and successfully use fast provers based on SAT solving. In this talk I will introduce the technique in elementary terms, for programmers, who may find it immediately useful in testing. I will also outline research questions about how to use the technique in frame conditions, in refactoring, in foundational proofs, in refinement types, in terms of aspects, and in checking information flow properties.

Establishing Resource Allocation Policies in the PlanetLab Federation

Date and Time
Wednesday, November 11, 2009 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Andrew Bavier, from Princeton Computer Science
Over time PlanetLab has evolved from a centrally-administered testbed to a federation of regional testbeds that are operated independently. The PlanetLab software is also freely available, which has allowed many organizations to bring up their own "private" PlanetLabs. For most private PlanetLabs, a barrier to entering the federation is the inability to express access and allocation policies for their own resources, and the lack of tools to communicate, analyze, and enforce those policies. In the first part of my talk, I will present an overview of the PlanetLab federation. Next I will focus on VINI, a private PlanetLab we have deployed in Internet2 and NLR, and which is intended for evaluating new network architectures. Finally, I will describe a tool ("sfatables") we have built for expressing and enforcing resource allocation policies. Our approach was designed to enable VINI to federate with PlanetLab, but it is general enough to accommodate a diverse collection of computing facilities.

This talk describes joint work with Larry Peterson, Sapan Bhatia, Jennifer Rexford, and Nick Feamster.

Network-Level Spam and Scam Defenses

Date and Time
Thursday, October 29, 2009 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Professor Nick Feamster, from Georgia Tech
Host
Jennifer Rexford
This talk introduces a new class of methods called "behavioral blacklisting", which identify spammers based on their network-level behavior. Rather than attempting to blacklist individual spam messages based on what the message contains, behavioral blacklisting classifies a message based on how the message itself was sent (spatial and temporal traffic patterns of the email traffic itself). Behavioral blacklisting tracks the sending behavior of an email sender from a wide variety of vantage points and establishes "fingerprints" that are indicative of spamming behavior. Behavioral blacklisting can apply not only to email traffic, but also to the network-level behavior of hosting infrastructure for scam or phishing attacks. First, I will present a brief overview of our study of the network-level behavior of spammers. Second, I will describe two behavioral blacklisting algorithms that are based on insights from our study of the network-level behavior of spammers. Finally, I will describe our ongoing work applying similar behavioral detection techniques to detecting both online scam hosting infrastructure and phishing attacks.

Bio
Nick Feamster is an assistant professor in the College of Computing at Georgia Tech. He received his Ph.D. in Computer science from MIT in 2005, and his S.B. and M.Eng. degrees in Electrical Engineering and Computer Science from MIT in 2000 and 2001, respectively. His research focuses on many aspects of computer networking and networked systems, including the design, measurement, and analysis of network routing protocols, network operations and security, and anonymous communication systems. He recently received the Presidential Early Career Award for Scientists and Engineers (PECASE) for his contributions to cybersecurity, notably spam filtering. His honors include a Sloan Research Fellowship, the NSF CAREER award, the IBM Faculty Fellowship, and award papers at SIGCOMM 2006 (network-level behavior of spammers), the NSDI 2005 conference (fault detection in router configuration), Usenix Security 2002 (circumventing web censorship using Infranet), and Usenix Security 2001 (web cookie analysis).

Highway Dimension and Provably Efficient Shortest Path Algorithms

Date and Time
Wednesday, October 14, 2009 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Andrew Goldberg, from Microsoft Research - Silicon Valley
Host
Robert Tarjan
Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, in real time, and with very low storage overhead.

We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms.

Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck

Follow us: Facebook Twitter Linkedin