Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking

Abstract : Generation of counterexamples is a highly important task in the model checking process. In contrast to, e.,g., digital circuits where counterexamples typically consist of a single path leading to a critical state of the system, in the probabilistic setting counterexamples may consist of a large number of paths. In order to be able to handle large systems and to use the capabilities of modern SAT-solvers, bounded model checking (BMC) for discrete-time Markov chains was established.In this paper we introduce the usage of SMT-solving over linear real arithmetic for the BMC procedure. SMT-solving, extending SAT with theories in this context on the one hand leads to a convenient way to express conditions on the probability of certain paths and on the other hand allows to handle Markov reward models. We use the former to find paths with high probability first. This leads to more compact counterexamples. We report on some experiments, which show promising results.
Type de document :
Communication dans un congrès
Roberto Bruni; Juergen Dingel. 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik,, Iceland. Springer, Lecture Notes in Computer Science, LNCS-6722, pp.75-89, 2011, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-21461-5_5〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01583324
Contributeur : Hal Ifip <>
Soumis le : jeudi 7 septembre 2017 - 11:10:24
Dernière modification le : lundi 11 septembre 2017 - 10:47:54

Fichier

978-3-642-21461-5_5_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Bettina Braitling, Ralf Wimmer, Bernd Becker, Nils Jansen, Erika Ábrahám. Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking. Roberto Bruni; Juergen Dingel. 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik,, Iceland. Springer, Lecture Notes in Computer Science, LNCS-6722, pp.75-89, 2011, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-21461-5_5〉. 〈hal-01583324〉

Partager

Métriques

Consultations de la notice

40

Téléchargements de fichiers

7