Cost analysis of nondeterministic probabilistic programs

Peixin Wang, Hongfei Fu, Amir Kafshdar Goharshady, Krishnendu Chatterjee, Xudong Qin, Wenjun Shi

Abstract

Automated cost analysis for programs combining randomness and nondeterminism is a critical challenge in formal verification. Existing methods often struggle with negative costs (rewards) or unbounded resource consumption. This paper introduces a framework that extends the Optional Stopping Theorem (OST) to handle polynomial growth, enabling the calculation of tight polynomial bounds on expected costs. By leveraging Handelman’s Theorem, the search for cost martingales is reduced to a scalable Linear Programming problem. Evaluation on diverse benchmarks, including Bitcoin mining and queuing networks, demonstrates the framework's ability to handle complex, real-world scenarios that were previously out of reach.

Introduction

In software verification, "cost analysis" refers to predicting the consumption of resources such as time, memory, energy, or even financial assets. For nondeterministic probabilistic programs—which model systems with both random behavior (e.g., coin flips) and environmental uncertainty—this task is particularly complex. Traditional tools often impose restrictive assumptions, such as requiring costs to be strictly non-negative or bounded by a constant at each step. These constraints prevent the analysis of economic protocols involving rewards or systems like queuing networks where costs can grow proportionally to an unbounded state variable.

Methodology: Extending the Optional Stopping Theorem

The core contribution of this work is a theoretical extension of the Optional Stopping Theorem (OST), a fundamental result in martingale theory. While classical OST requires "bounded differences" in martingales, the authors prove a version allowing these differences to grow polynomially over time, provided the program's termination time exhibits specific concentration properties.

Program representation as a control flow graph with probabilistic and nondeterministic transitions.

To automate the discovery of these bounds, the authors define Polynomial Upper Cost Supermartingales (PUCS) and Polynomial Lower Cost Submartingales (PLCS). These serve as mathematical templates that provide guaranteed upper and lower bounds on expected total costs. The synthesis of these templates is achieved by applying Handelman’s Theorem from semi-algebraic geometry, which transforms the search into a standard Linear Programming (LP) problem. This ensures that the analysis remains computationally efficient and sound.

Benchmarks and Experimental Results

The framework was evaluated against a suite of 15 standard benchmarks and several new, challenging models designed to test the limits of current cost analysis tools. These include:

  • Bitcoin Mining and Pool Mining: Modeling the trade-off between constant electricity costs and rare, large block rewards.
  • Fork-Join Queuing Networks: Modeling parallel processing systems where costs depend on unbounded queue lengths.
  • Species Fight: A stochastic linear recurrence modeling ecological competition with unbounded population growth.
A fork-join queuing network model used as a benchmark for unbounded cost analysis.

Experimental results show that the tool matches or exceeds the performance of state-of-the-art methods on standard tasks. For complex models like the fork-join queuing network, it synthesized tight polynomial bounds in under five minutes. For simpler models like Bitcoin mining, it provided results in less than ten seconds. In several instances, the synthesized upper and lower bounds converged, providing the exact expected cost.

Conclusion and Future Work

This research significantly advances the state-of-the-art in cost analysis by enabling the handling of negative and unbounded costs. While limitations remain—such as the requirement for program termination and the current inability to handle general costs and unbounded updates simultaneously—the reduction of martingale synthesis to Linear Programming provides a scalable path forward. Future research may explore the synthesis of non-polynomial bounds, such as exponential or logarithmic functions, to capture an even broader range of program behaviors.

Summary updated

BibTeX
@inproceedings{wang2019cost,
  author = {Peixin Wang and Hongfei Fu and Amir Kafshdar Goharshady and Krishnendu Chatterjee and Xudong Qin and Wenjun Shi},
  title = {{Cost analysis of nondeterministic probabilistic programs}},
  booktitle = {PLDI},
  year = {2019},
  doi = {10.1145/3314221.3314581},
}
Figure