Scaling Up Automated Verification and Synthesis

The 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 powerful weapons 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.

In this talk, I present our recent work on rapidly building domain-specific automated programming tools. I will demonstrate the importance of these tools in the context of memory consistency models, which define the behavior of multiprocessor CPUs and whose subtleties often elude even experts. Our new tool, MemSynth, automatically synthesizes formal descriptions of memory consistency models from examples of CPU behavior. We have used MemSynth to synthesize descriptions of the x86 and PowerPC memory models, each of which previously required person-years of effort to describe by hand, and found several ambiguities and underspecifications in both architectures.

I will then present symbolic profiling, a new technique we designed and implemented to help programmers identify the scalability bottlenecks in automated programming tools. These tools use symbolic evaluation, which evaluates all paths through a program, and is an execution model that defies both human intuition and standard profiling techniques. Symbolic profiling diagnoses scalability bottlenecks using a novel performance model for symbolic evaluation that accounts for all-paths execution. We have used symbolic profiling to find and fix performance issues in 8 state-of-the-art automated tools, improving their scalability by orders of magnitude, and our techniques have been adopted in industry.

 

Biography

James Bornholt received a Ph.D. from the University of Washington in 2019, and will be an Assistant Professor of Computer Science at the University of Texas at Austin in 2020. His research interests are in programming languages and formal methods, with a focus on automated program verification and synthesis. His work has received an ACM SIGPLAN Research Highlight, two IEEE Micro Top Picks selections, an OSDI best paper award, and a Facebook Ph.D. fellowship. He holds an MS from the University of Washington and a BPhil from the Australian National University.

 

Date & time

10–11am 9 Jul 2019

Location

Room:Seminar Room 1.33

Speakers

James Bornholt

Contacts

02 6125 2394

Updated:  1 June 2019/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing