Search papers, labs, and topics across Lattice.
This paper introduces a deductive verification framework for weighted programming that utilizes a weighted assertion language and an intermediate verification language to reason about programs with trace weights from semirings. By establishing weakest-preweighting semantics and proving sound translations for core commands, the authors enable the expression of verification conditions that articulate both lower- and upper-bound obligations. The framework is validated through a prototype in the Caesar verifier, which successfully checks various case studies, demonstrating its applicability in complex scenarios like probabilistic queueing and recursive database provenance.
A novel deductive verification framework for weighted programming reveals how to express and automate verification conditions for complex quantitative models.
Weighted programs extend guarded commands with trace weights drawn from a semiring, or more generally a monoid-module. Varying this algebra gives one programmatic syntax for a variety of quantitative and symbolic models. Weakest-preweighting semantics provides a compositional basis for reasoning about those programs. We present a deductive verification framework based on a weighted assertion language and an intermediate verification language. Its weight domains are ordered structures with implication and coimplication, which let verification conditions express lower- and upper-bound obligations internally. We prove sound translations of core commands and reusable encodings for various proof rules applying to procedure calls and loops. To facilitate automation, we prove soundness of a quantifier elimination procedure for our assertion language. A prototype in the Caesar verifier checks case studies for probabilistic queueing costs, recursive database provenance with cyclic dependencies, clearance bounds for networks of arbitrary size, and formal-language reasoning about lock-freedom of a compare-and-swap counter.
