Lune

OOPSLA2022Top-tier venue

Symbolic execution for randomized programs

Zachary Susag, Sumit Lahiri, Justin Hsu, Subhajit Roy

Abstract

We propose a symbolic execution method for programs that can draw random samples. In contrast to existing work, our method can verify randomized programs with unknown inputs and can prove probabilistic properties that universally quantify over all possible inputs. Our technique augments standard symbolic execution with a new class of probabilistic symbolic variables , which represent the results of random draws, and computes symbolic expressions representing the probability of taking individual paths. We implement our method on top of the KLEE symbolic execution engine alongside multiple optimizations and use it to prove properties about probabilities and expected values for a range of challenging case studies written in C++, including Freivalds’ algorithm, randomized quicksort, and a randomized property-testing algorithm for monotonicity. We evaluate our method against Psi, an exact probabilistic symbolic inference engine, and Storm, a probabilistic model checker, and show that our method significantly outperforms both tools.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Roulette: A Language for Expressive, Exact, and Efficient Discrete Probabilistic Programming cites Scaling exact inference for discrete probabilistic programs
  • Roulette: A Language for Expressive, Exact, and Efficient Discrete Probabilistic Programming cites λPSI: exact inference for higher-order probabilistic programs
  • A Unifying Approach to Product Constructions for Quantitative Temporal Inference cites Scaling exact inference for discrete probabilistic programs
  • A Deductive Verification Infrastructure for Probabilistic Programs cites Data-Driven Invariant Learning for Probabilistic Programs
  • Data-Driven Invariant Learning for Probabilistic Programs cites Central moment analysis for cost accumulators in probabilistic programs
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. A Deductive Verification Infrastructure for Probabilistic ProgramsPhilipp Schröer, Kevin Batz, Benjamin Lucien Kaminski, Joost-Pieter Katoen et al.OOPSLA 2023 · 22 citations
  2. Symbolic Execution for Quantum Error Correction ProgramsWang Fang, Mingsheng YingPLDI 2024 · 16 citations
  3. Roulette: A Language for Expressive, Exact, and Efficient Discrete Probabilistic ProgrammingCameron Moy, Jack Czenszak, John M. Li, Brianna Marshall et al.PLDI 2025 · 3 citations
  4. A Unifying Approach to Product Constructions for Quantitative Temporal InferenceKazuki Watanabe, Sebastian Junges, Jurriaan Rot, Ichiro HasuoOOPSLA 2025 · 1 citation
  5. Empc: Effective Path Prioritization for Symbolic Execution with Path CoverShuangjie Yao, Dongdong SheS&P 2025

Builds on6

  1. Scaling exact inference for discrete probabilistic programsSteven Holtzen, Guy Van den Broeck, Todd D. MillsteinOOPSLA 2020 · 85 citations
  2. λPSI: exact inference for higher-order probabilistic programsTimon Gehr, Samuel Steffen, Martin T. VechevPLDI 2020 · 29 citations
  3. Probabilistic profiling of stateful data planes for adversarial testingQiao Kang, Jiarong Xing, Yiming Qiu, Ang ChenASPLOS 2021 · 21 citations
  4. Data-Driven Invariant Learning for Probabilistic ProgramsJialu Bao, Nitesh Trivedi, Drashti Pathak, Justin Hsu et al.CAV 2022 · 20 citations
  5. Central moment analysis for cost accumulators in probabilistic programsDi Wang, Jan Hoffmann, Thomas W. RepsPLDI 2021 · 18 citations

Related papers

  1. Symbolic Partial-Order Execution for Testing Multi-Threaded ProgramsDaniel Schemmel, Julian Büning, César Rodríguez, David Laprell et al.CAV 2020 · 12 citations
  2. SYMTUNER: Maximizing the Power of Symbolic Execution by Adaptively Tuning External ParametersSooyoung Cha, Myungho Lee, Seokhyun Lee, Hakjoo OhICSE 2022 · 4 citations
  3. Enhancing Symbolic Execution with Self-Configuring ParametersMinjong Kim, Sooyoung ChaICSE 2026
  4. Multiplex Symbolic Execution: Exploring Multiple Paths by Solving OnceYufeng Zhang, Zhenbang Chen, Ziqi Shuai, Tianqi Zhang et al.ASE 2020 · 17 citations
  5. Verifying SystemC TLM peripherals using modern C++ symbolic execution toolsPascal Pieper, Vladimir Herdt, Daniel Große, Rolf DrechslerDAC 2022 · 9 citations
Dusk over the sea between two cliffs drawn in fine vertical lines