  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 \emph{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 \textsc{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 \textsc{Psi}, an
exact probabilistic symbolic inference engine, and \textsc{Storm}, a
probabilistic model checker, and show that our method significantly outperforms
both tools.
