  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.
