Parallel Proofs for Parallel Programs

This dissertation addresses the problem of automated reasoning about multi-threaded programs. Multi-threaded programs are notoriously prone to error, making them an attractive target for formal methods which can be used to \emph{guarantee} that programs satisfy desirable properties. \emph{Automated} formal methods lift the burden of reasoning about concurrency from software developers onto the shoulders of machines. However, concurrency raises some significant algorithmic challenges for formal methods, particularly in reasoning about complex interactions between threads. This dissertation aims to tame this problem by developing \emph{parallel} logical foundations for multi-threaded programs. Classical approaches to reasoning about multi-threaded programs are based on developing clever ways to reason about them as if they were sequential. There are two prototypical examples of this approach: the \emph{interleaving model} and the \emph{thread-modular model}. In the interleaving model, a multi-threaded program is \emph{compiled} into a sequential program that interleaves the behaviour of all threads, after which we may reason about the program using classical techniques for sequential programs. In the thread-modular model, we reason about each thread independently as a sequential program, subject to side-conditions that enforce that the reasoning about each thread is robust under interference from the others. This dissertation takes a different tack: rather than devise a way to apply sequential reasoning to multi-threaded programs, we develop foundations for reasoning about parallelism directly. On these foundations, we build static analysis and software model checking algorithms for verifying and refuting properties of multi-threaded programs. We show that direct and explicit representation of parallelism enables tractable and precise automated reasoning.Ph.D