Foundations for Deductive Verification of Continuous Probabilistic Programs: From Lebesgue to Riemann and Back
This program is tentative and subject to change.
We lay out novel foundations for computer-aided verification of guaranteed bounds on expected outcomes of imperative probabilistic programs featuring (i) general \emph{loops}, (ii) \emph{continuous} distributions, and (iii) \emph{conditioning}. To handle loops we rely on user-provided quantitative \emph{invariants}, as is well established. However, in the realm of continuous distributions, \emph{invariant verification} becomes extremely challenging due to the presence of \emph{integrals} in expectation-based program semantics. Our key idea is to soundly \emph{under} or \emph{over-approximate} these integrals via \emph{Riemann sums}. We show that this approach enables the SMT-based invariant verification for programs with fairly general control flow structure. On the theoretical side, we prove \emph{convergence} of our Riemann approximations, and establish $\mathsf{coRE}$-completeness of the central verification problems. On the practical side, we show that our approach enables to use existing automated verifiers targeting \emph{discrete} probabilistic programs for the verification of programs involving \emph{continuous sampling}. Towards this end, we implement our approach in the recent quantitative verification infrastructure Caesar by encoding Riemann sums in its intermediate verification language. We present several promising case studies.
This program is tentative and subject to change.
Sat 18 OctDisplayed time zone: Perth change
10:30 - 12:15 | |||
10:30 15mTalk | FO-Complete Program Verification for Heap Logics OOPSLA Adithya Murali University of Illinois at Urbana-Champaign, Hrishikesh Balakrishnan University of Illinois Urbana-Champaign, Aaron Councilman Univ of Illinois Urbana-Champaign, P. Madhusudan University of Illinois at Urbana-Champaign | ||
10:45 15mTalk | Foundations for Deductive Verification of Continuous Probabilistic Programs: From Lebesgue to Riemann and Back OOPSLA Kevin Batz RWTH Aachen University, Joost-Pieter Katoen RWTH Aachen University, Francesca Randone Department of Mathematics, Informatics and Geosciences, University of Trieste, Italy, Tobias Winkler RWTH Aachen University | ||
11:00 15mTalk | Guarding the Privacy of Label-Only Access to Neural Network Classifiers via Formal Verification OOPSLA | ||
11:15 15mTalk | KestRel: Relational Verification Using E-Graphs for Program Alignment OOPSLA Robert Dickerson Purdue University, Prasita Mukherjee Purdue University, Benjamin Delaware Purdue University | ||
11:30 15mTalk | Laurel: Unblocking Automated Verification with Large Language Models OOPSLA Eric Mugnier University of California San Diego, Emmanuel Anaya Gonzalez UCSD, Nadia Polikarpova University of California at San Diego, Ranjit Jhala University of California at San Diego, Zhou Yuanyuan UCSD | ||
11:45 15mTalk | Scaling Instruction-Selection Verification against Authoritative ISA Semantics OOPSLA Michael McLoughlin Carnegie Mellon University, Ashley Sheng Wellesley College, Chris Fallin F5, Bryan Parno Carnegie Mellon University, Fraser Brown CMU, Alexa VanHattum Wellesley College | ||
12:00 15mTalk | Verification of Bit-Flip Attacks against Quantized Neural Networks OOPSLA Yedi Zhang National University of Singapore, Lei Huang ShanghaiTech University, Pengfei Gao ByteDance, Fu Song Institute of Software at Chinese Academy of Sciences; University of Chinese Academy of Sciences; Nanjing Institute of Software Technology, Jun Sun Singapore Management University, Jin Song Dong National University of Singapore |