SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Wed 20 Oct 2021 15:55 - 16:10 at Zurich G - OOPSLA 2020 Papers 3 Chair(s): Anders Miltner

Formally verifying software correctness is a highly manual process. However, because verification proofs often share structure, it is possible to learn from existing proofs to fully automate some formal verification. The goal of this paper is to improve proof synthesis and enable fully automating more verification. Interactive theorem provers, such as the Coq proof assistant, allow developers to write partial proofs, observe the semantics of the proof state thus far, and then attempt more progress. Knowing the proof state semantics is a significant aid. Recent research has shown that the proof state can help predict the next step. In this paper, we present TacTok, the first technique that attempts to fully automate proof synthesis by modeling proofs using both the partial proof written thus far and the semantics of the proof state. Thus, TacTok more completely models the information the developer has access to when writing proofs manually. TacTok is open-source. We evaluate TacTok on a benchmark of 26 software projects in Coq, consisting of over 10 thousand theorems. We compare our approach to two tools, CoqHammer, the state-of-the-art proof synthesis technique, and ASTactic, a proof synthesis technique that models proof state. We find that TacTok is complementary to CoqHammer and ASTactic: for 24 out of the 26 projects, TacTok can synthesize proofs for some theorems prior tools cannot. Together with TacTok, 11.5% more theorems can be proven automatically than by CoqHammer alone, and 20.0% than by ASTactic alone. Compared to a combination of CoqHammer and ASTactic, TacTok can prove an additional 3.6% more theorems, proving 115 theorems no tool could previously prove. Overall, our experiments provide evidence that partial proof and proof state semantics, together, provide useful information for proof modeling.

Wed 20 Oct

Displayed time zone: Central Time (US & Canada) change

15:40 - 17:00
OOPSLA 2020 Papers 3SIGPLAN Papers at Zurich G
Chair(s): Anders Miltner The University of Texas at Austin, Texas, USA
15:40
15m
Talk
DynamiTe: Dynamic Termination and Non-termination Proofs
SIGPLAN Papers
Ton Chanh Le Stevens Institute of Technology, Timos Antonopoulos Yale University, Parisa Fathololumi Stevens Institute of Technology, Eric Koskinen Stevens Institute of Technology, ThanhVu Nguyen George Mason University
15:55
15m
Talk
TacTok: Semantics-Aware Proof Synthesis
SIGPLAN Papers
Emily First University of Massachusetts at Amherst, Yuriy Brun University of Massachusetts Amherst, Arjun Guha Northeastern University
Link to publication DOI Pre-print
16:10
15m
Talk
Towards A Unified Proof Framework for Automated Fixpoint Reasoning Using Matching Logic
SIGPLAN Papers
Xiaohong Chen University of Illinois at Urbana-Champaign, Minh-Thai Trinh Advanced Digital Sciences Center, Nishant Rodrigues University of Illinois at Urbana-Champaign, Lucas Peña University of Illinois at Urbana-Champaign, Grigore Roşu University of Illinois at Urbana-Champaign
16:25
15m
Talk
Verifying and Improving Halide’s Term Rewriting System with Program Synthesis
SIGPLAN Papers
Julie L. Newcomb University of Washington, Andrew Adams Adobe, Steven Johnson Google, Rastislav Bodík University of Washington, Shoaib Kamil Adobe Research
16:40
20m
Live Q&A
Discussion, Questions and Answers
SIGPLAN Papers