Multithreaded programs are notoriously prone to race conditions. Prior work on dynamic race detectors includes fast but imprecise race detectors that report false alarms, as well as slow but precise race detectors that never report false alarms. The latter typically use expensive vector clock operations that require time linear in the number of program threads.

Our new approach to race detection exploits the insight that the full generality of vector clocks is unnecessary in most cases. That is, we can replace heavyweight vector clocks with an adaptive lightweight representation that, for almost all operations of the target program, requires only constant space and supports constant-time operations. This representation change significantly improves time and space performance, with no loss in precision.

Experimental results on Java benchmarks including the Eclipse development environment show that our FastTrack race detector is an order of magnitude faster than a traditional vector-clock race detector, and roughly twice as fast as the high-performance DJIT+ algorithm. FastTrack is even comparable in speed to Eraser on our Java benchmarks, while never reporting false alarms.

This is joint work with Cormac Flanagan (University of California, Santa Cruz).

Modern managed languages, such as Java and C#, derive many of their software engineering benefits from the use of virtual machines, which implement powerful features such as just-in-time compilation, dynamic class loading, and garbage collection. While the performance penalty of VMs has received significant attention, the information penalty has not: this extra layer of virtualization makes program behavior (and misbehavior) much more difficult to understand. The garbage collector, for example, takes over responsibility for freeing objects, eliminating a large class of memory errors. As a result, however, the programmer no longer knows when, or even if, particular objects are reclaimed. Our work explores a solution called VM introspection, which gives programmers an interface for asking the virtual machine specific questions about program behavior at runtime. Our focus is on information that is readily available or can be computed cheaply enough to make this technique suitable for deployed software.

In this talk I will describe GC Assertions, an introspective interface that allows programmers to express expected properties of data structures. Unlike ordinary assertions, GC assertions are checked by the garbage collector, which is in a unique position to gather information and answer questions about the lifetime, volume, and connectivity of objects in the heap. In many cases these heap properties are difficult or impossible to accurately verify by any other means. By piggybacking on existing garbage collector computations, our system is able to check large numbers of assertions with very low overhead – around 3% of total execution time. In addition, our error reporting mechanism provides a detailed explanation of assertion violations, including a complete path through the heap to the offending objects.

In this talk I will describe some of the work we've done in recent years on software reliability. In the first part of the talk, I will ambitiously attempt to cover some principles from our work on the Paraglide (synthesis), SAFE (static analysis), and QVM (Quality-aware VM) projects.

In the second part, I will focus on QVM and how it can be used for finding and fixing defects in deployed systems.

(joint work with Matt Arnold and Martin Vechev)

Sensor networks composed of large numbers of self-organizing embedded devices are an increasingly valuable tool for understanding our world. Deployed networks allow scientists to observe phenomena at a scale and resolution that challenge existing instrumentation. Some call this new instrument the macroscope.

My project uses sensor networks to monitor active volcanoes. Due to the high data rates and stringent fidelity requirements of this application, providing output suitable for scientific analysis requires carefully directing the limited resources available at each node. In this talk I will present Lance, a general approach to bandwidth and energy management targeting reliable data collection for sensor networks.

By combining an application-level determination of value with a system-level estimation of cost, Lance maximizes the value of the data returned to the application by optimally allocating bandwidth and energy devoted to signal collection. Lance's design decouples data collection policy from mechanism, allowing its optimization metrics to be customized to suit a variety of application goals. I will motivate and describe the Lance architecture, present results from the lab and the field, and discuss continuing efforts in this area, including single-node and network-wide architectures for distributed energy management.

Bio:

Geoffrey Challen (né Werner-Allen) is a Ph.D. Candidate in Computer Science at the Harvard University School of Engineering and Applied Sciences, advised by Matt Welsh. His research addresses the systems and networking challenges necessary to enable high-fidelity sensing applications, focusing specifically on maximizing the usage of the limited resources available to sensor network nodes. Working with geoscientists, he has helped perform three sensor network deployments on active Ecuadorean volcanoes. He built and maintains MoteLab, a wireless sensor network testbed used by researchers worldwide, and is a co-editor of a forthcoming book on sensor network deployments. Geoffrey is a 2009 Siebel Fellow, and a Resident Tutor at Eliot House.

Web applications such as Facebook, Google Maps, and Hotmail have become an integral part of everyday life. These modern AJAX web applications are distributed systems with a great deal of inherent complexity. Applications containing 100,000 lines of client-side JavaScript or more are not uncommon and emerging apps such as Office for the Web, Zimbra, and Zoho hint at more complexity still to come. This talk focuses on two projects addressing performance and security of AJAX applications.

Doloto is an optimization tool for Web 2.0 applications. Doloto analyzes application workloads and automatically rewrites the existing application code to introduce dynamic code loading. Doloto reduces the size of application code download by hundreds of kilobytes or as much as 50% of the original download size. The time to download and begin interacting with large applications is reduced by 20-40% depending on the application and wide-area network conditions.

The second project is Ripley, a replication technology for preserving computational integrity of AJAX apps. Once a portion of a web application is moved to the client, a malicious user can subvert the client side of the computation, jeopardizing the integrity of the server-side state. In this paper we propose Ripley, a system that uses replicated execution to automatically preserve the integrity of a distributed computation. Ripley observes results of the computation, both as computed on the client-side and on the server side using the replica of the client-side code. Any discrepancy is flagged as a potential violation of computational integrity. We built Ripley on top of Volta, a distributing compiler that translates .NET applications into JavaScript, effectively providing a measure of security by construction for Volta applications.

Bio:

Ben Livshits is a researcher at Microsoft Research in Redmond, WA. He received a B.A. from Cornell University in 1999, and his M.S. and Ph.D. from Stanford University in 2002 and 2006, respectively. Dr. Livshits' research interests include application of sophisticated static and dynamic analysis techniques to finding errors in programs. He is known for his work on software reliability and especially tools to improve software security, with a primary focus on approaches to finding buffer overruns in C programs and a variety of security vulnerabilities (cross-site scripting, SQL injections, etc.) in Web-based applications. Lately he has been focused on how Web 2.0 application reliability, performance, and security can be improved through a combination of static and runtime techniques.

Device drivers are a major source of complexity, unreliability, and cost for modern operating systems. As evidence, drivers account for the majority of system crashes. We propose two approaches to improving reliability: static analysis to detect insidious bugs, and new programming models to simplify coding.

First, we observe that hardware devices can fail, but many drivers assume they do not: there are many drivers that will crash or hang when a device fails. We present Carburizer, a code-manipulation tool and associated runtime that improves system reliability in the presence of faulty devices. Carburizer analyzes driver source code to find locations where the driver incorrectly trusts the hardware to behave. We identified almost 1000 such bugs in Linux drivers with a false positive rate of less than 8 percent. With the aid of shadow drivers for recovery, Carburizer can automatically repair 840 of these bugs with no programmer involvement.

Second, we observe that the programming environment for drivers, C code written for the kernel, is complex and brittle. We address this problem with Decaf Drivers, a system for incrementally converting existing Linux kernel drivers to Java programs in user mode. With support from programanalysis tools, Decaf separates out performance-sensitive code and generates a customized kernel interface that allows the remaining code to be moved to Java. With tool support, a programmer can incrementally convert driver code in C to a Java decaf driver. The Decaf Drivers system achieves performance close to native kernel drivers and requires almost no changes to the Linux kernel.

Bio: Michael Swift is an assistant professor at the University of Wisconsin, Madison. Before joining the faculty, he received a Ph.D. from the University of Washington working with Hank Levy and Brian Bershad. He previously worked at Microsoft in the Windows NT group on local and distributed security.

The V8 JavaScript compiler developed at Google is much faster than JavaScript interpreters and compilers were two years ago. I will talk about some of the ideas used in V8 to run JavaScript quickly: optimizing "object-oriented" JS code, and fast and scalable exact garbage collection. I will then show some of the compilation techniques we tried, and which ones we abandoned.

Transactional Memory has been widely hailed — and arguably oversold — as a solution to the complexity of parallel programming. Originally proposed in 1993 by Maurice Herlihy and UMass's own Eliot Moss, the idea blossomed a decade later in a burst of innovation fueled by the multicore revolution. As 2009 draws to a close, several major commercial vendors have developed — or are developing — hardware implementations of TM, beta-quality software versions are available from several other vendors, and SIGPLAN is preparing to host its fifth annual workshop on the subject (with Eliot as Chair). The time seems ripe for an assessment of the field.

While the central conclusion is rather dull (TM does not make parallel programming easy, but it is a useful tool for important classes of programs), several aspects of TM development have proven quite surprising. I will argue that the feasible design space for software TM is much larger and more varied -- and its precise behavior much more difficult to specify -- than anyone originally expected. I will also suggest that software TM will remain important even in the (likely) presence of widely available hardware, and that implementation techniques developed for software TM will prove valuable for several non-TM purposes.

Bio:
Michael L. Scott is a Professor and past Chair of the Department of Computer Science at the University of Rochester. His research interests span operating systems, languages, architecture, and tools, with a particular emphasis on parallel and distributed systems. He is best known for work in synchronization algorithms and concurrent data structures, in recognition of which he shared the 2006 Edsger W. Dijkstra Prize and was named a Fellow of the ACM. He is the author of a widely used text on programming language design and implementation, and received the University's top undergraduate teaching award in 2001. In 2003 he served as General Chair for SOSP; more recently he has been Program Chair for TRANSACT'07 and PPoPP'08.