Optimizing the Automated Programming Stack

Thesis (Ph.D.)--University of Washington, 2019The scale and pervasiveness of modern software poses a challenge for programmers: software reliability is more important than ever, but the complexity of computer systems continues to grow. Automated programming tools are a powerful way for programmers to tackle this challenge: verifiers that check software correctness, and synthesizers that generate new correct-by-construction programs. These tools are most effective when they apply domain-specific optimizations, but doing so today requires considerable formal methods expertise. This dissertation shows that new abstractions and techniques can empower programmers to build specialized automated programming tools that ensure software reliability. We first demonstrate the importance and effectiveness of automated tools in the context of memory consistency models, which define the behavior of multiprocessor CPUs and whose subtleties often elude even experts. MemSynth is a tool that automatically synthesizes formal descriptions of memory consistency models from examples of CPU behavior, and has found ambiguities and underspecifications in two major computer architectures. We then introduce two new programmer techniques for developing automated programming tools. Metasketches are a new abstraction for building program synthesis tools that integrate search strategy into the problem definition, allowing a metasketch solver to solve synthesis problems that other tools cannot. Symbolic profiling is a technique for systematically identifying and resolving scalability bottlenecks in automated programming tools. Symbolic profiling generalizes across different symbolic evaluation engines and has been used to improve the performance of state-of-the-art automated tools by orders of magnitude. Together, these three contributions demonstrate the value of automated programming tools for building reliable software, and offer guidance on how to build such tools efficiently for new problem domains