Central moment analysis for cost accumulators in probabilistic programs

Di Wang, Jan Hoffmann, Thomas W. RepsPLDI 2021 · DOI · OpenReview

TL;DR

This paper introduces a novel method for analyzing probabilistic programs by automatically deriving bounds on higher-order "central moments" (like variance) of cost accumulators. This allows for tighter tail-bound analyses of program properties, outperforming existing methods that rely solely on expected values.

What Problem Does This Paper Address?

Probabilistic programs are powerful for modeling uncertainty, but precisely analyzing their behavior (e.g., the probability of a cost exceeding a certain threshold) is computationally challenging. Existing static analysis techniques often approximate these behaviors using "raw moments" like expected values. However, these approximations can be loose, leading to less precise bounds. The paper addresses the challenge of deriving tighter bounds by leveraging "central moments" (e.g., variance, skewness, kurtosis), which capture more information about a distribution's shape and tail behavior, but are significantly harder to analyze automatically.

Methods

The core innovation is an algebraic abstraction called "moment semirings" that generalizes existing techniques for analyzing expected values to handle higher-order central moments. This framework allows for:

  • Simultaneous Analysis: It analyzes upper and lower bounds on moments together, which is crucial for non-monotone costs.
  • Moment-Polymorphic Recursion: A novel technique to handle recursive functions by composing moment analyses of different recursive calls.
  • Template-Based Inference: Using polynomial templates for potential functions, the problem of inferring bounds is reduced to solving linear programs (LPs).
  • Soundness Guarantee: The analysis is proven sound using a recent extension of the Optional Stopping Theorem, ensuring that the derived bounds are correct.

Datasets

Not discussed in the paper. The paper focuses on developing an analysis technique and evaluating it on synthetic benchmarks and examples from related work.

Key Insights and Ideas

  • Central Moments are Powerful: Moving beyond just expected values to analyze variance, skewness, and kurtosis provides richer information about program behavior, especially for tail probabilities.
  • Algebraic Abstraction is Key: Moment semirings provide a principled way to compose and combine moment information, enabling compositional and interprocedural analysis.
  • Moment-Polymorphism Solves Recursion: Handling recursive functions with moment-polymorphic analysis is crucial for analyzing real-world programs.
  • LP Reduction is Efficient: Reducing the complex problem of moment bound inference to linear programming makes the analysis practical and automatable.

Key Results

  • The developed analyzer obtains tighter tail bounds than existing systems that use only raw moments (expectations). This is demonstrated through experiments on various benchmarks, including coupon-collector and random-walk programs.
  • The tool successfully infers upper bounds on higher central moments (up to the 4th moment) for program runtimes.
  • The analysis scales well, with running times exhibiting an almost linear relationship with program size (number of recursive functions).
  • A case study on a timing-attack vulnerability shows how the derived bounds can quantify the success probability of an attack, demonstrating the practical utility of the analysis.

Limitations and Future Work

  • Soundness Conditions: The soundness of the analysis relies on satisfying certain conditions related to the Optional Stopping Theorem, which are checked automatically. However, the paper notes that the expected-potential method is not always sound without these conditions.
  • Bounded Updates: The analysis assumes a "bounded-update property" for program variables, which is common in practice but might not hold for all programs.
  • Future Work: The authors plan to extend the analysis to handle more data types (e.g., Booleans, lists) and to apply it to higher-order functional programs.

Summary updated

Abstract

For probabilistic programs, it is usually not possible to automatically derive exact information about their properties, such as the distribution of states at a given program point. Instead, one can attempt to derive approximations, such as upper bounds on tail probabilities. Such bounds can be obtained via concentration inequalities, which rely on the moments of a distribution, such as the expectation (the first raw moment) or the variance (the second central moment). Tail bounds obtained using central moments are often tighter than the ones obtained using raw moments, but automatically analyzing central moments is more challenging. This paper presents an analysis for probabilistic programs that automatically derives symbolic upper and lower bounds on variances, as well as higher central moments, of cost accumulators. To overcome the challenges of higher-moment analysis, it generalizes analyses for expectations with an algebraic abstraction that simultaneously analyzes different moments, utilizing relations between them. A key innovation is the notion of moment-polymorphic recursion, and a practical derivation system that handles recursive functions. The analysis has been implemented using a template-based technique that reduces the inference of polynomial bounds to linear programming. Experiments with our prototype central-moment analyzer show that, despite the analyzer’s upper/lower bounds on various quantities, it obtains tighter tail bounds than an existing system that uses only raw moments, such as expectations.
BibTeX
@inproceedings{wang2021central,
  author = {Di Wang and Jan Hoffmann and Thomas W. Reps},
  title = {{Central moment analysis for cost accumulators in probabilistic programs}},
  booktitle = {PLDI},
  year = {2021},
  doi = {10.1145/3453483.3454062},
}
Figure