Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking
International audience 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...
Main Authors: | , , , , |
---|---|
Other Authors: | , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01583324 https://hal.inria.fr/hal-01583324/document https://hal.inria.fr/hal-01583324/file/978-3-642-21461-5_5_Chapter.pdf https://doi.org/10.1007/978-3-642-21461-5_5 |
id |
ftifiphal:oai:HAL:hal-01583324v1 |
---|---|
record_format |
openpolar |
spelling |
ftifiphal:oai:HAL:hal-01583324v1 2023-05-15T16:50:15+02:00 Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking Braitling, Bettina Wimmer, Ralf Becker, Bernd Jansen, Nils Ábrahám, Erika Albert-Ludwigs-Universität Freiburg Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH) Roberto Bruni Juergen Dingel TC 6 WG 6.1 Reykjavik,, Iceland 2011-06-06 https://hal.inria.fr/hal-01583324 https://hal.inria.fr/hal-01583324/document https://hal.inria.fr/hal-01583324/file/978-3-642-21461-5_5_Chapter.pdf https://doi.org/10.1007/978-3-642-21461-5_5 en eng HAL CCSD Springer info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-21461-5_5 hal-01583324 https://hal.inria.fr/hal-01583324 https://hal.inria.fr/hal-01583324/document https://hal.inria.fr/hal-01583324/file/978-3-642-21461-5_5_Chapter.pdf doi:10.1007/978-3-642-21461-5_5 http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess Lecture Notes in Computer Science 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE) https://hal.inria.fr/hal-01583324 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. pp.75-89, ⟨10.1007/978-3-642-21461-5_5⟩ [INFO]Computer Science [cs] [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftifiphal https://doi.org/10.1007/978-3-642-21461-5_5 2023-03-21T20:40:06Z International audience 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. Conference Object Iceland IFIP Open Digital Library (International Federation for Information Processing) 75 89 |
institution |
Open Polar |
collection |
IFIP Open Digital Library (International Federation for Information Processing) |
op_collection_id |
ftifiphal |
language |
English |
topic |
[INFO]Computer Science [cs] [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] |
spellingShingle |
[INFO]Computer Science [cs] [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] Braitling, Bettina Wimmer, Ralf Becker, Bernd Jansen, Nils Ábrahám, Erika Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking |
topic_facet |
[INFO]Computer Science [cs] [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] |
description |
International audience 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. |
author2 |
Albert-Ludwigs-Universität Freiburg Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH) Roberto Bruni Juergen Dingel TC 6 WG 6.1 |
format |
Conference Object |
author |
Braitling, Bettina Wimmer, Ralf Becker, Bernd Jansen, Nils Ábrahám, Erika |
author_facet |
Braitling, Bettina Wimmer, Ralf Becker, Bernd Jansen, Nils Ábrahám, Erika |
author_sort |
Braitling, Bettina |
title |
Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking |
title_short |
Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking |
title_full |
Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking |
title_fullStr |
Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking |
title_full_unstemmed |
Counterexample Generation for Markov Chains Using SMT-Based Bounded Model Checking |
title_sort |
counterexample generation for markov chains using smt-based bounded model checking |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/hal-01583324 https://hal.inria.fr/hal-01583324/document https://hal.inria.fr/hal-01583324/file/978-3-642-21461-5_5_Chapter.pdf https://doi.org/10.1007/978-3-642-21461-5_5 |
op_coverage |
Reykjavik,, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Lecture Notes in Computer Science 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE) https://hal.inria.fr/hal-01583324 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. pp.75-89, ⟨10.1007/978-3-642-21461-5_5⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-21461-5_5 hal-01583324 https://hal.inria.fr/hal-01583324 https://hal.inria.fr/hal-01583324/document https://hal.inria.fr/hal-01583324/file/978-3-642-21461-5_5_Chapter.pdf doi:10.1007/978-3-642-21461-5_5 |
op_rights |
http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1007/978-3-642-21461-5_5 |
container_start_page |
75 |
op_container_end_page |
89 |
_version_ |
1766040423541768192 |