一句话：提出可处理随机抽样的符号执行方法，能在未知输入下验证随机化程序的概率性质与期望值。
现有概率程序验证工作通常依赖已知输入或特定模型，难以处理带未知输入的随机化程序。本文扩展标准符号执行，引入“概率符号变量”表示随机抽样结果，并计算路径条件对应的取值概率，从而用符号表达式表达路径概率与期望值。作者在 KLEE 上实现该方法并加入多项优化，用 C++ 编写的 Freivalds 算法、随机快速排序和单调性随机性质测试等案例验证概率和期望值性质。与精确概率符号推断引擎 Psi 和概率模型检测器 Storm 相比，该方法显著优于两者。
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.
@article{paperbot1449,
title = {Symbolic execution for randomized programs},
author = {Zachary Susag and Sumit Lahiri and Justin Hsu and Subhajit Roy},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {OOPSLA2},
year = {2022},
doi = {10.1145/3563344}
}