[Kwi07]
M. Kwiatkowska.
Quantitative Verification: Models, Techniques and Tools.
In Proc. 6th joint meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE), pages 449-458, ACM Press.
September 2007.
[pdf]
[bib]
[Overview of probabilistic model checking and PRISM, with a particular emphasis on DTMCs.]
|
Notes:
Copyright: ACM, 2007. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version is at
http://portal.acm.org/citation.cfm?doid=1287624.1287688
|
Links:
[Google]
[Google Scholar]
|
Abstract.
Automated verification is a technique for establishing if certain
properties, usually expressed in temporal logic, hold for
a system model. The model can be defined using a high-level
formalism or extracted directly from software using methods
such as abstract interpretation. The verification proceeds
through exhaustive exploration of the state-transition
graph of the model and is therefore more powerful than testing.
Quantitative verification is an analogous technique for
establishing quantitative properties of a system model, such
as the probability of battery power dropping below minimum,
the expected time for message delivery and the expected
number of messages lost before protocol termination.
Models analysed through this method are typically variants
of Markov chains, annotated with costs and rewards that
describe resources and their usage during execution. Properties
are expressed in temporal logic extended with probabilistic
and reward operators. Quantitative verification involves
a combination of a traversal of the state-transition
graph of the model and numerical computation.
This paper gives a brief overview of current research in
quantitative verification, concentrating on the potential of
the method and outlining future challenges. The modelling
approach is described and the usefulness of the methodology
illustrated with an example of a real-world protocol standard
– Bluetooth device discovery – that has been analysed using
the PRISM model checker (www.prismmodelchecker.org).
|