Verification method verifies continuous-time random processes reliably
A Hoare Logic for Continuous-Time Stochastic Processes
Logic in Computer ScienceProgramming Languages
Summary
Programs that include randomness over continuous time are tricky to analyze using usual methods designed for steps in time. The authors develop a new way to treat these continuous-time random processes like normal programs by considering what happens as time steps get really small. They create a set of rules, based on Hoare logic, to prove properties about such processes, including famous examples like Brownian motion. Their approach allows verifying that these processes behave correctly with respect to certain conditions.
What this means in practice
- •For software verification engineers: Check correctness properties of software systems modeled by continuous-time random processes using the new logic rules.
- •For control systems engineers: Verify safety and performance properties of continuous-time stochastic hybrid systems modeled as programs.
Authors
Kei Imada, Justin Hsu
Abstract
Programming language researchers have developed a wide array of tools to reason about probabilistic programs, but it remains unclear how to apply these proof techniques to continuous-time stochastic processes. To bridge this gap, we propose a verification method for properties of continuous-time stochastic processes by reasoning about them as standard programs. To demonstrate our approach, we define a continuous semantics for a probabilistic imperative language $\mathrm{pWhile}^{\mathrm{dt}}$ by taking the Kuratowski limit of the standard semantics, which collects limit points of the standard program semantics as the time-step approaches zero. Then, we present a Hoare-style logic that uses loop invariants and decreasing functions to verify properties of continuous programs. To establish soundness, we identify a broad class of assertions that are preserved from the standard semantics to the continuous semantics. To demonstrate our approach, we verify properties of ten continuous-time stochastic processes modeled in $\mathrm{pWhile}^{\mathrm{dt}}$, including variants of Brownian motion and a stochastic hybrid system.