Structural Abstraction and Refinement for Probabilistic Programs

Explore a novel framework for verifying probabilistic programs through structural abstraction refinement in this 15-minute conference presentation from OOPSLA 2025. Learn how researchers from Tsinghua University, University of Oxford, Beijing Normal University, East China Normal University, and Shanghai Jiao Tong University present an innovative approach to the threshold problem in probabilistic program verification. Discover how their method represents Probabilistic Control-Flow Automaton (PCFA) structures as Markov Decision Processes (MDP) by abstracting away statement semantics, providing structural upper bounds for violation probabilities. Understand the key distinction between this "structural" characterization and traditional "semantical" approaches, where the abstraction focuses solely on probabilistic computation while refinement handles semantic aspects. Examine how this clean separation enables the use of established non-probabilistic program verification techniques without modification. Gain insights into their counterexample-guided abstraction refinement (CEGAR) framework and its instantiations using trace abstraction. Review experimental results demonstrating the method's versatility and ability to handle flexible structures efficiently compared to state-of-the-art tools, with comprehensive artifacts available for replication and further research.