La vérification de systèmes est aujourd’hui un sujet de recherche récurrent et différentes techniques permettent de vérifier formellement des systèmes critiques dont il faut impérativement garantir la correction. Nous consacrons ce mémoire à l’une des techniques les plus utilisées et les plus efficaces, l’évaluation de modèle. Schématiquement, pour vérifier un système par évaluation de modèle, on abstrait d’abord son comportement sous la forme d’un système de transitions appelé modèle. Ensuite, on formule une propriété désirée du système dans une logique temporelle. Enfin, on utilise un outil logiciel appelé vérificateur pour vérifier automatiquement si le modèle satisfait la propriété. Dans ce mémoire, nous voulons vérifier des propriétés d’atteignabilité dans des modèles probabilistes appelés processus de Markov étiquetés (en anglais, LMP pour Labelled Markov processes) et qui ont possiblement un ensemble d’états non dénombrable. Malheureusement, le vérificateur CISMO dédié à une famille de LMP ne gère pas les propriétés d’atteignabilité et aucun autre outil ne peut vérifier les LMP. Pour améliorer CISMO et atteindre notre objectif, nous avons rendu d’abord plus expressive sa logique de spécification de propriétés pour qu’elle exprime les propriétés d’atteignabilité sur les LMP. Ces propriétés expriment le fait qu’un état souhaité dans un système peut être atteint avec une certaine probabilité. Ensuite, nous avons implémenté dans CISMO une nouvelle approche de vérification d’une famille de propriétés d’atteignabilité qui contribue à l’évolution de la vérification probabiliste. Nous utilisons le théorème de la moyenne pour prouver que, pour tout LMP acceptable par CISMO et toute propriété d’atteignabilité, il existe une chaîne de Markov à temps discret (en anglais, DTMC pour Discrete Time Markov Chains) équivalent au LMP de point de vue atteignabilité moyenne et auquel on peut appliquer les algorithmes connus pour les systèmes probabilistes finis. Le DTMC est construit de telle sorte que nous inférons que le LMP satisfait la propriété d’atteignabilité, si et seulement si le DTMC la satisfait. Théoriquement, notre approche donne un résultat ultime exact et nous l’avons prouvé. À l’implémentation, nous utilisons une méthode d’intégration numérique pour déterminer les probabilités de transition dans le DTMC. Malgré les imprécisions numériques qui peuvent nuire au résultat d’une vérification, nous avons prouvé que notre approche a du sens en quantifiant les erreurs. Nous avons démontré d’une part que les erreurs numériques sont toujours bornées supérieurement dans le DTMC et avons montré d’autre part, qu’il existe une relation de bisimulation entre le LMP et le DTMC. Notre méthode est originale et repousse les limites de l’évaluation de modèle, notamment l’explosion combinatoire de l’espace d’états ou de chemins dans la vérification de systèmes probabilistes infinis. / Systems verification is nowadays a major issue and various techniques verify formally critical systems for which correction must be ensured. The focus of this master’s thesis is on one of the most used and most effective systems verification techniques, modelchecking. Conceptually, to apply model-checking to a system, we first abstract its behavior in the form of a transitions system, the model. Then, we formulate a system property of interest in a temporal logic. Finally, a software called model-checker is used to verify automatically if the model satisfies the property. In this paper, we want to check reachability property in the probabilistic models called labelled Markov process (LMP) and which have possibly an uncountable set of states. Unfortunately, the model-checker CISMO dedicated to a family of LMP does not handle reachability properties and no other tool can verify LMP. To improve CISMO and achieve our goal, we first made more expressive its properties specification logic so that it can express reachability property on LMP. These properties express the fact that a desired state in a system can be reached with a certain probability. Secondly, we implemented in CISMO a new approach for the verification of a family of reachability properties. This is a contribution to the evolution of the probabilistic verification. We use the mean theorem to prove that, for any LMP acceptable by CISMO and for any reachability property, there is a discrete time process (DTMC) equivalent to the LMP according to the average reachability and on which we can apply known algorithms for probabilistic systems which have a countable set of states. The DTMC is constructed in such a way that we can infer the LMP satisfies the reachability property, if and only if the DTMC also satisfies it. Theoretically, our approach gives a precise final result and we prove it. At implementation, since the DTMC is subjected to numerical errors the result can be false, as expected. We use a numerical integration method to determine the transitions probabilities in the DTMC. Despite the errors that can affect the outcome of a verification, we have shown that our approach makes sense at implementation by quantifying the errors. We have shown on one hand that numerical errors are always bounded from above in the DTMC and we established, on the other hand, bisimulation relations between LMP, DTMC constructed theoretically, and DTMC generated algorithmically with errors. Our method is original and pushes the limits of model-checking, especially combinatorial explosion of the states space or paths in the verification of infinite probabilistic systems.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/25013 |
| Date | 20 April 2018 |
| Creators | Kouko, Gildas Syla Déo |
| Contributors | Laviolette, François, Desharnais, Josée |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | mémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise |
| Format | 1 ressource en ligne (xiii, 111 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.003 seconds