Fri 12 Jan 2018 13:30 - 13:52 at Bunker Hill - Program Analysis II Chair(s): Işıl Dillig

We introduce Refinement Reflection, a new framework for building SMT-based deductive verifiers. The key idea is to reflect the code implementing a user-defined function into the function’s (output) refinement type. As a consequence, at uses of the function, the function definition is instantiated in a precise fashion that permits decidable verification. We show how reflection allows the user to write equational proofs of programs just by writing other programs e.g., using pattern-matching and recursion to perform case-splitting and induction. Thus, via, the propositions-as-types principle we show that reflection permits the specification of arbitrary functional correctness properties. While equational proofs are easy, writing them out can be exhausting. We introduce a proof-search algorithm called Proof by Logical Evaluation that uses techniques from model checking and abstract interpretation, to completely automate equational reasoning. We have implemented reflection in Liquid Haskell and used it to verify that the widely used instances of the Monoid, Applicative, Functor, and Monad typeclasses actually satisfy key algebraic laws required to make the clients safe, and to build the first library that actually verifies assumptions about associativity and ordering that are crucial for safe deterministic parallelism.

Fri 12 Jan

Displayed time zone: Tijuana, Baja California change

13:30 - 15:20
Program Analysis IIResearch Papers at Bunker Hill
Chair(s): Işıl Dillig UT Austin
13:30
10m
Awards
SRC Awards
Research Papers
Benjamin Delaware Purdue University
13:30
22m
Talk
Refinement Reflection: Complete Verification with SMT
Research Papers
Niki Vazou University of Maryland, Anish Tondwalkar UCSD, Vikraman Choudhury , Ryan Scott Indiana University, Ryan R. Newton Indiana University, Philip Wadler University of Edinburgh, UK, Ranjit Jhala University of California, San Diego
14:05
25m
Talk
Non-Linear Reasoning For Invariant Synthesis
Research Papers
Zachary Kincaid Princeton University, John Cyphert University of Wisconsin - Madison, Jason Breck University of Wisconsin - Madison, Thomas Reps University of Wisconsin - Madison and GrammaTech, Inc.
14:30
25m
Talk
A Practical Construction for Decomposing Numerical Abstract Domains
Research Papers
Gagandeep Singh , Markus Püschel ETH Zürich, Martin Vechev ETH Zürich
14:55
25m
Talk
Verifying Equivalence of Database-Driven Applications
Research Papers
Yuepeng Wang University of Texas at Austin, Işıl Dillig UT Austin, Shuvendu K. Lahiri Microsoft Research, William Cook University of Texas at Austin