Fri 12 Jan 2018 14:55 - 15:20 at Bunker Hill - Program Analysis II Chair(s): Isil Dillig

This paper addresses the problem of verifying equivalence between a pair of programs that operate over databases with different schemas. This problem is particularly important in the context of web applications, which typically undergo database refactoring either for performance or maintainability reasons. While the web application should have the same externally observable behavior before and after schema migration, there are no existing tools for proving equivalence of such programs. This paper takes a first step towards solving this problem by formalizing the equivalence and refinement checking problems for database-driven applications. We then propose a proof methodology based on the notion of bisimulation invariants over a new logic called the theory of relational algebra with updates. We also present a fully automated technique for synthesizing such bisimulation invariants and automatically verify their correctness. We have implemented the proposed technique in a tool called Mediator and show that it can verify the equivalence of real-world web applications containing hundreds of transactions.

Fri 12 Jan

Displayed time zone: Tijuana, Baja California change

13:30 - 15:20
Program Analysis IIResearch Papers at Bunker Hill
Chair(s): Isil 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, Isil Dillig UT Austin, Shuvendu Lahiri Microsoft Research, William Cook University of Texas at Austin