TacTok: Semantics-Aware Proof Synthesis
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 OctDisplayed 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 15mTalk | 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 15mTalk | 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 15mTalk | 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 15mTalk | 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 20mLive Q&A | Discussion, Questions and Answers SIGPLAN Papers |