Institute of Information Science, Academia Sinica



Press Ctrl+P to print from browser


Synthesizing Proofs for Program Verification

  • LecturerDr. Grigory Fedyukovich (Princeton University, USA)
    Host: Yu-Fang Chen
  • Time2018-10-16 (Tue.) 15:30 – 17:30
  • LocationAuditorium 106 at IIS new Building

State-of-the-art techniques for automated program verification are required to certify each decision with a formal proof. When verifying program safety, a proof is an inductive invariant, when proving program termination, a proof is a ranking function, and when proving program non-termination, a proof is a recurrence set. Synthesis of these proofs necessitates exploring a usually large search space and relies on off-the-shelf constraint solvers. In this talk, I will present new methods that bias the search space with an extensive use of the program’s source code. We build on an intuition that the source code often gives useful information, e.g., of occurrences of variables, constants, arithmetic and comparison operators. Thus, we use the source code to automatically construct a formal grammar and iteratively sample the desired proofs from it. We have designed and implemented an extensible verification framework and applied it for proving safety, termination, and non-termination of programs. The experimental evaluation has shown that although the formal grammar is limited to the syntax of the program, in the majority of cases our algorithms are effective and fast.


Grigory Fedyukovich is a postdoc at Princeton University, USA, working with Prof. Aarti Gupta. His main research interests are in automated formal verification, constraint solving, and functional synthesis. He completed my PhD at the University of Lugano, Switzerland, under the supervision of Prof. Natasha Sharygina, and then he was a postdoc at the University of Washington, Seattle, USA, with Prof. Rastislav Bodik.