Verifying Concurrent Programs by Controlling Alias Interference

Thesis (Ph.D.)--University of Washington, 2014This dissertation proposes a family of techniques for static verication of sequential and concurrent imperative programs by leveraging fine-grained characterizations of mutation. The key idea is that by attaching to each reference in a program (1) a restriction on mutations permitted using that reference, and (2) a characterization of possible interference through other aliases, a type system can reason about what properties are preserved by all mutations in a program. This thesis develops four variations on this idea: (1) We adapt reference immutability to support data-race-free concurrent programming. (2) We generalize reference immutability to rely-guarantee references, allowing two-state invariants to express usage restrictions between read-only and arbitrary mutation. (3) We extend rely-guarantee references to prove invariants and functional correctness of lock-free concurrent data structures. (4) We evaluate rely-guarantee references' utility for existing Haskell programs. Together these variations show that reasoning about aliasing and reasoning about concurrent (imperative) programs are the same fundamental challenge, and that by taking the right foundational approach to reasoning about sequential programs, the gap to reasoning about concurrent programs is signicantly reduce