CPA-CPL: Scalable Analysis for Concurrent Programs

University Of California-San Diego, La Jolla CA

Investigators

Abstract

Concurrency is a prevalent feature of almost all critical computing infrastructure, including operating systems, databases, internet-routing tables, and banking systems. Furthermore, several recent trends in technology, such as the widespread adoption of multi-core processors, web-service-oriented architectures, and peer-to-peer systems, are making concurrency more important than ever in mainstream systems. Unfortunately, concurrent systems are hard to build, because programmers have a hard time mentally accounting for the many possible ways in which these concurrent systems can interact. The broad goal of this research is to provide programmers with the tools they need to develop concurrent systems that are reliable, efficient and robust. The investigators will focus their efforts on one particular kind of tool, namely static analysis tools. Indeed, advances in static algorithms for program optimization and error detection have shown that static analysis can dramatically improve the reliability and performance of computer systems. However, most of these algorithmic advances are limited to sequential programs and ignore the challenges introduced by concurrency, where the need for static checking and potential for optimization are the greatest. This research will develop scalable and precise analysis techniques for concurrent programs. Achieving scalability and precision at the same time, however, is difficult because there is a widely acknowledged tension between these two goals. To address this challenge, the general methodology will be to design analyses that are sound and scalable first (likely at the expense of precision), and then to iteratively refine these analyses by empirically identifying the common concurrent programming idioms where our analyses lose precision, and developing analysis techniques targeted at these idioms.