Write a Blog >>
Sun 20 - Fri 25 October 2019 Athens, Greece
Thu 24 Oct 2019 14:00 - 14:22 at Olympia - Specification and Certification Chair(s): Colin Gordon

Relational verification aims to prove properties that relate a pair of programs or two different runs of the same program. While relational properties (e.g., equivalence, non-interference) can be verified by reducing them to standard safety, there are typically many possible reduction strategies, only some of which result in successful automated verification. Motivated by this problem, we propose a novel relational verification algorithm that learns useful reduction strategies using reinforcement learning. Specifically, we show how to formulate relational verification as a Markov Decision Process (MDP) and use reinforcement learning to synthesize an optimal policy for the underlying MDP. The learned policy is then used to guide the search for a successful verification strategy. We have implemented this approach in a tool called Coeus and evaluate it on two benchmark suites. Our evaluation shows that Coeus solves significantly more problems within a given time limit compared to multiple baselines, including two state-of-the-art relational verification tools.

Thu 24 Oct
Times are displayed in time zone: (GMT+03:00) Beirut change

14:00 - 15:30: OOPSLA - Specification and Certification at Olympia
Chair(s): Colin GordonDrexel University
splash-2019-oopsla14:00 - 14:22
Jia ChenUniversity of Texas at Austin, Jiayi WeiUniversity of Texas at Austin, Yu FengUniversity of California, Santa Barbara, Osbert BastaniUniversity of Pennsylvania, Isil DilligUniversity of Texas Austin
splash-2019-oopsla14:22 - 14:45
Timos AntonopoulosYale University, Eric KoskinenStevens Institute of Technology, Ton Chanh LeStevens Institute of Technology
splash-2019-oopsla14:45 - 15:07
Aleksandar NanevskiIMDEA Software Institute, Anindya BanerjeeIMDEA Software Institute, Germán Andrés DelbiancoIRIF - Université de Paris, Ignacio FábregasIMDEA Software Institute
Link to publication DOI
splash-2019-oopsla15:07 - 15:30
Shengyi WangNational University of Singapore, Qinxiang CaoShanghai Jiao Tong University, Anshuman MohanNational University of Singapore, Aquinas HoborNational University of Singapore
DOI Pre-print