# Worst-Case Analysis is Maximum-A-Posteriori Estimation

arXiv: https://arxiv.org/abs/2310.09774 · HTML: https://mlsanity.com/paper/2310.09774/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 49 references that are in the map.
- First posted on arXiv 15 Oct 2023.

## Builds on (most cited first, 7 of 7)

- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [Neural Adaptive Sequential Monte Carlo](https://mlsanity.com/paper/1506.03338/) (2015)
- [A Lambda-Calculus Foundation for Universal Probabilistic Programming](https://mlsanity.com/paper/1512.08990/) (2015)
- [SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities](https://mlsanity.com/paper/1708.08437/) (2017)
- [Sequential Monte Carlo Learning for Time Series Structure Discovery](https://mlsanity.com/paper/2307.09607/) (2023)
- [Badger: Complexity Analysis with Fuzzing and Symbolic Execution](https://mlsanity.com/paper/1806.03283/) (2018)
- [Towards Automatic Resource Bound Analysis for OCaml](https://mlsanity.com/paper/1611.00692/) (2016)

## Abstract (arXiv)

The worst-case resource usage of a program can provide useful information for many software-engineering tasks, such as performance optimization and algorithmic-complexity-vulnerability discovery. This paper presents a generic, adaptive, and sound fuzzing framework, called DSE-SMC, for estimating worst-case resource usage. DSE-SMC is generic because it is black-box as long as the user provides an interface for retrieving resource-usage information on a given input; adaptive because it automatically balances between exploration and exploitation of candidate inputs; and sound because it is guaranteed to converge to the true resource-usage distribution of the analyzed program. DSE-SMC is built upon a key observation: resource accumulation in a program is isomorphic to the soft-conditioning mechanism in Bayesian probabilistic programming; thus, worst-case resource analysis is isomorphic to the maximum-a-posteriori-estimation problem of Bayesian statistics. DSE-SMC incorporates sequential Monte Carlo (SMC) -- a generic framework for Bayesian inference -- with adaptive evolutionary fuzzing algorithms, in a sound manner, i.e., DSE-SMC asymptotically converges to the posterior distribution induced by resource-usage behavior of the analyzed program. Experimental evaluation on Java applications demonstrates that DSE-SMC is significantly more effective than existing black-box fuzzing methods for worst-case analysis.