×

Abstraction refinement for probabilistic software. (English) Zbl 1206.68090

Jones, Neil D. (ed.) et al., Verification, model checking, and abstract interpretation. 10th international conference, VMCAI 2009, Savannah, GA, USA, January 18–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-540-93899-6/pbk). Lecture Notes in Computer Science 5403, 182-197 (2009).
Summary: We present a methodology and implementation for verifying ANSI-C programs that exhibit probabilistic behaviour, such as failures or randomisation. We use abstraction-refinement techniques that represent probabilistic programs as Markov decision processes and their abstractions as stochastic two-player games. Our techniques target quantitative properties of software such as “the maximum probability of file-transfer failure” or “the minimum expected number of loop iterations” and the abstractions we construct yield lower and upper bounds on these properties, which then guide the refinement process. We build upon state-of-the-art techniques and tools, using SAT-based predicate abstraction, symbolic implementations of probabilistic model checking and components from GOTO-CC, SATABS and PRISM. Experimental results show that our approach performs very well in practice, successfully verifying actual networking software whose complexity is significantly beyond the scope of existing probabilistic verification tools.
For the entire collection see [Zbl 1155.68009].

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)

Software:

PRISM
PDFBibTeX XMLCite
Full Text: DOI