Share this page
Share this page E-mail this page Print this page RSS feeds
Home > Groups > Runtime Analysis and Design
Runtime Analysis and Design

Runtime Analysis and Design

Overview

The Runtime Analysis and Design (RAD) research group investigates data-centric program analysis technologies and tools for improving software performance, energy-efficiency and security. We emphasize data structure and data access analysis since these play a central role in many performance/energy and security problems. We apply program analysis and statistical techniques to efficiently monitor and measure program execution since many data related properties and behaviors are best observed while a program is running. We also investigate static heap analysis techniques, such as shape analysis, to supplement our dynamic observations and analysis. We believe a combination of static and dynamic program analysis techniques are required to address interesting problems in this space. We are currently focused on improving performance, energy-efficiency and security of web services both from a client and data center perspective.

Current opportunities we are pursuing include:

  • Hybrid Static-Dynamic Frameworks. Runtime analysis offers precision and scalability while static analysis provides strong guarantees. Current attempts at combining the two typically use static analysis as a preprocessor to filter what must be monitored and analyzed at runtime. We are exploring more effective ways to combine these techniques and obtain the best of both worlds.
  • Heap Data. Static techniques have difficulty efficiently analyzing the program heap making it well suited to runtime analyses or hybrid approaches. This presents several opportunities. The processor-memory performance gap combined with the poor inherent locality of heap data makes the heap a prime target for performance/energy optimization. In addition, specification, inference, checking, and enforcement of properties related to heap data has been neglected, despite its importance, since many analyses have a code and control-centric bias.
  • Energy-efficient computing. The move to web services has driven the construction of an increasing number of large data centers. Power considerations impact facilty location and design, limit the number of machines that can be placed in the facility, and constitute a large fraction of the operating cost. We are interested in rethinking the entire computing stack with energy-efficiency as the primary goal.
  • Web application security and performance. New kinds of distributed applications on the Web (e.g., highly interactive AJAX sites with user-provided content, social networks, mash-ups, etc.) have quickly become very popular. Unfortunately, the rise of these applications has been accompanied by new forms of security threats, like cross-site scripting, request forgery, and JavaScript worms. We have been working on both static and runtime techniques to combat such vulnerabilities. We are also interested in making it easier to program the so-called Web 2.0, while making security the default, rather than the exception. Similarly, we have been working on techniques to make Web 2.0 applications faster and more responsive on different types of network connections and devices.
People




Projects

  • SPEED (Sumit Gulwani)
    Software performance is traditionally measured using profiling, which is often too little (only certain inputs are profiled) or too late (to make requisite changes to address the root cause before shipping). The SPEED project attempts to address these limitations by static estimation of symbolic computational complexity of programs. It builds over recent advances in static program analysis, which has traditionally been used for checking correctness as opposed to measuring performance.
  • LAI (Sumit Gulwani)
    This project develops algorithms for performing abstract interpretation over new abstract domains whose elements are logical formulas over some theory and the partial order relationship is the implication relationship. The theorem proving community has studied decision procedures for several theories. For performing abstract interpretation over logical formulas in a theory, we need more than a decision procedure. For example, we need a join algorithm that can over-approximation disjunction, and a widen algorithm that guarantees convergence during the fixed-point computation process.
  • VS3 (Sumit Gulwani)
    SMT Solvers (or Theorem Provers) have traditionally been used for verifying correctness of systems that have been annotated with relevant inductive invariants. Such an annotation usually is an undesirable burden on the user. This project explores techniques for using SMT solvers to automatically discover inductive invariants for proving given safety properties of systems. Additionally, this project also explores techniques for using SMT solvers to synthesize systems in the first place given enough specifications.
  • Doloto (Ben Livshits)
    Doloto is a code rewriting approach for optimizing Web 2.0 applications. It analyzes application workloads and automatically performs code splitting of existing large Web 2.0 applications. After being processed by Doloto, an application will initially transfer only the portion of code necessary for application initialization. The rest of the application's code is replaced by short stubs -- their actual function code is transferred lazily in the background or, at the latest, on-demand on first execution. Since code download is interleaved with application execution, users can start interacting with the Web application much sooner, without waiting for the code that implements extra, unused features, leading to significant time and bandwidth savings.
  • Spectator (Ben Livshits)
    Spectator is the first automatic detection and containment solution for JavaScript worms. Spectator is a proxy that performs distributed data tainting by observing and tagging the traffic between the browser and the Web application. When a piece of data propagates "too far", a potential worm is reported. To prevent worm propagation, subsequent upload attempts performed by the same worm are blocked. Spectator is able to detect fast and slow moving, monomorphic and polymorphic worms with a low rate of false positives. In addition to our detection and containment solution, we propose a range of deployment models for Spectator, ranging from simple intranet-wide deployments to a scalable load-balancing scheme appropriate for large Web sites.
  • AjaxScope (Ben Livshits)
    AjaxScope is a dynamic instrumentation platform for Web 2.0 applications. AjaxScope enables cross-user monitoring and just-in-time control of web application behavior on end-user desktops. AjaxScope is a proxy that performs on-the-fly parsing and instrumentation of JavaScript code as it is sent to users’ browsers. AjaxScope provides facilities for distributed and adaptive instrumentation in order to reduce the client-side overhead, while giving fine-grained visibility into the code-level behavior of web applications. We present a variety of policies demonstrating the power of AjaxScope, ranging from simple error reporting and performance profiling to more complex memory leak detection and optimization analyses. We also apply our prototype to analyze the behavior of over 90 Web 2.0 applications and sites that use large amounts of JavaScript.
  • NinjaWare (Trishul Chilimbi)
    NinjaWare is a project investigating lightweight continuous monitoring and analysis of software. Our implementation allows us to gather fine-grain temporal information about high frequency events such as program data accesses with very low overhead (< 5%). We are exploring leveraging this infrastructure to build a wide variety of always-on runtime tools ranging from memory leak and data race detectors to program specification/invariant checkers and security monitors.
  • Daedalus (Trishul Chilimbi)
    With the growing processor-memory performance gap, understanding and optimizing a program's data accesses is becoming increasingly important. Recent research has proposed several techniques that improve a program's cache performance by changing its data layout or its data access pattern. This project proposes to build a system that incorporates profile information and combines these techniques into an integrated framework for performing whole program data locality optimizations. It investigates techniques that efficiently analyze a program's data reference stream to identify and isolate data abstractions that can serve as a basis for data locality optimizations. Once identified these data abstractions can be exploited by providing data restructuring recommendations to a programmer, generating specialized allocators, and inserting data prefetches.
  • PPP (Trishul Chilimbi)
    PPP is a novel scheme for efficiently profiling paths in programs. PPP enables path profiling at extremely low overheads by observing that most consumers of path profiles are usually interested in profiling a small number of paths that are known a priori, even though the number of potential paths in functions can be quite large. We are investigating the use of PPP in residual path profiling, which seeks to identify all paths executed by deployed software that were untested during software development.
  • Trace Visualization Tools - ( George Robertson and Trishul Chilimbi)
    We have developed a couple of trace animation visualization tools called MemRay and AllocRay that perform sophisticated memory performance analysis on large traces. The tools and more details are here (MS Internal only)
  • Gargoyle: Energy-Efficient Computing for Data Centers (Trishul Chilimbi) We are investigating innovations in software (languages, runtimes, tools) and hardware (system and micro-architecture)for improving the energy-efficiency of data centers by an order of magnitude.

Selected Publications

Opportunities

We are hiring. If you are interested in seeking job opportunities in the Runtime Analysis and Design research group, please send your resume (Microsoft Word, HTML, PDF, postscript, or ASCII text format) via email to: trishulcATmicrosoft.com. Also, see the Recruiting Web Page for the Programming Languages and Tools area.

We are always looking for exceptional PhD candidates to join us as interns, especially during the summer months. For more information about becoming an intern, please visit our internship website.

Visitors, Collaborators, and Interns

  • Faculty
  • Summer Interns (2000)
  • Summer Interns (2001)
  • Summer Interns (2002)
  • Summer Interns (2003)
  • Summer Interns (2004)
    • Vinod Ganapathy (University of Wisconsin, Madison)
    • A.J. Shankar (University of California, Berkeley)
  • Summer Interns (2005)
    • Stephen McCamant (MIT)
    • Kapil Vaswani (Indian Institute of Science, Bangalore)
    • Ting Yang (University of Massachusetts, Amherst)

Overview