Probabilistic Program Abstractions

Steven Holtzen, Todd D. Millstein, Guy Van den Broeck

Abstract

This paper introduces a foundational theory for probabilistic program abstractions, bridging the gap between formal program verification and probabilistic modeling. By replacing the non-deterministic "choices" in traditional abstractions with quantified random variables, the authors create a framework that can reason not just about what might happen in a program, but how likely it is to happen. We establish the semantics of probabilistic abstraction, define sound over-approximation, and demonstrate how complex probabilistic queries can be lifted into simpler abstract spaces while maintaining accuracy.

Introduction

In software verification, program abstraction is a standard technique to make complex code manageable. Instead of tracking every possible integer value, an abstraction might only track whether a variable satisfies certain predicates (e.g., $x < 0$). This creates a simpler "abstract" program that serves as an over-approximation: if a property holds in the abstraction, it is guaranteed to hold in the original code.

However, traditional abstractions are inherently non-deterministic. When an abstraction lacks sufficient information to decide a branch, it simply allows for either path. While effective for proving absolute safety (e.g., "this program will never crash"), this approach is insufficient for modern probabilistic queries. If a developer needs to know the probability of a crash or the expected value of a sensor reading, traditional non-deterministic tools remain silent. This research addresses the critical need for a formal method to build abstractions that preserve probabilistic information.

Methods

The authors extend the classical theory of Abstract Interpretation into the probabilistic domain through several key innovations:

  1. The BERN Language: A minimalist probabilistic language including Boolean variables, assignments, if statements, and two critical operators: flip(θ) (a Bernoulli random variable) and observe(φ) (which conditions the distribution).
  2. Probabilistic Semantics: The relationship between "concrete" states (the real program) and "abstract" states (the simplified version) is redefined. Instead of mapping a concrete state to a set of possible abstract states, the framework uses concretization distributions to describe the probability of transitioning between domains.
Figure 1: Mapping between concrete states $\mathcal{C}$ and abstract states $\mathcal{A}$ via concretization $\gamma$ and abstraction $\alpha$.
  1. Sound Over-approximation: A probabilistic abstraction is defined as "sound" if the support of the abstract distribution contains all possible concrete executions.
  2. Probabilistic Predicate Abstraction: This generalizes the well-known "predicate abstraction" technique. In non-deterministic versions, unknown values are handled by a choose operator; here, they are replaced by flip(θ), where $\theta$ represents the conditional probability of that predicate being true given the available information.

Key Insights and Ideas

A central contribution of this work is the concept of Concretization Invariance. The authors prove that if a query can be perfectly represented by abstract states, the probability calculated in the abstract domain is identical regardless of the specific concretization distribution chosen. This justifies "lifting" complex probabilistic analysis into a simpler abstract space.

Figure 2: Relationship between probability distributions in the concrete domain $\mathcal{C}$ and the abstract domain $\mathcal{A}$ using concretization distributions.

Furthermore, the framework treats the loss of information not as a "don't know" (non-determinism), but as a source of quantified randomness. This allows the abstraction to function as a surrogate model for the original program. To maintain efficiency, the authors propose "structurally dependent" abstractions that update predicates sequentially, maintaining local semantics and simplifying inference.

Key Results

The primary result is a rigorous mathematical bridge between abstract interpretation and probabilistic programming. The paper demonstrates that the hard problem of probabilistic inference can be decomposed into two more manageable tasks:

  1. Parameter Calculation: Computing $\theta$ parameters for small, local fragments of the concrete program.
  2. Weighted Model Counting (WMC): Performing inference on the resulting abstract Boolean program.

In a walkthrough example, the authors show that an abstraction using only three Boolean predicates can perfectly recover the marginal probability ($11/32$) of a property in a more complex concrete program, validating the theoretical framework.

Limitations and Future Work

While foundational, the current theory has limitations:

  • Control Flow: The BERN language does not yet handle loops or complex control flow (e.g., while loops), which are essential for real-world software.
  • Predicate Selection: The framework assumes predicates are provided. Adapting techniques like "counterexample-guided abstraction refinement" (CEGAR) to the probabilistic context is a key area for future research.
  • Scalability: Computing optimal $\theta$ parameters for every assignment in a large program may be computationally expensive, necessitating the development of efficient approximation methods.

Summary updated

Abstract

ion is a fundamental tool for reasoning about complex systems. Program abstraction has been utilized to great effect for analyzing deterministic programs. At the heart of program abstraction is the relationship between a concrete program, which is difficult to analyze, and an abstract program, which is more tractable. Program abstractions, however, are typically not probabilistic. We generalize non-deterministic program abstractions to probabilistic program abstractions by explicitly quantifying the non-deterministic choices. Our framework upgrades key definitions and properties of abstractions to the probabilistic context. We also discuss preliminary ideas for performing inference on probabilistic abstractions and general probabilistic programs.
BibTeX
@inproceedings{holtzen2017probabilistic,
  author = {Steven Holtzen and Todd D. Millstein and Guy Van den Broeck},
  title = {{Probabilistic Program Abstractions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=BperLl2vG2S},
}
Figure