Thu 21 Jun 2018 16:10 - 16:35 at Grand Ballroom CD - Analyzing Probabilistic Programs Chair(s): Eva Darulova

This paper presents a new static analysis for deriving upper bounds on the expected resource consumption of probabilistic programs. The analysis is fully automatic and derives symbolic bounds that are multivariate polynomials in the inputs. The new technique combines manual state-of-the-art reasoning techniques for probabilistic programs with an effective method for automatic resource-bound analysis of deterministic programs. It can be seen as both, an extension of automatic amortized resource analysis (AARA) to probabilistic programs and an automation of manual reasoning for probabilistic programs that is based on weakest preconditions. An advantage of the technique is that it combines the clarity and compositionality of a weakest-precondition calculus with the efficient automation of AARA. As a result, bound inference can be reduced to off-the-shelf LP solving in many cases and automatically-derived bounds can be interactively extended with standard program logics if the automation fails. Building on existing work, the soundness of the analysis is proved with respect to an operational semantics that is based on Markov decision processes. The effectiveness of the technique is demonstrated with a prototype implementation that is used to automatically analyze 39 challenging probabilistic programs and randomized algorithms. Experiments indicate that the derived constant factors in the bounds are very precise and even optimal for some programs.

Thu 21 Jun

Displayed time zone: Eastern Time (US & Canada) change

16:10 - 17:00
Analyzing Probabilistic ProgramsPLDI Research Papers at Grand Ballroom CD
Chair(s): Eva Darulova MPI-SWS
16:10
25m
Talk
Bounded Expectations: Resource Analysis for Probabilistic Programs
PLDI Research Papers
Van Chan Ngo Carnegie Mellon University, Quentin Carbonneaux Yale University, Jan Hoffmann Carnegie Mellon University
Media Attached
16:35
25m
Talk
PMAF: An Algebraic Framework for Static Analysis of Probabilistic Programs
PLDI Research Papers
Di Wang Carnegie Mellon University, Jan Hoffmann Carnegie Mellon University, Thomas Reps University of Wisconsin - Madison and GrammaTech, Inc.
Media Attached