back to Aurore Collomb home page.

Aurore Collomb's Thesis

English    Francais

to obtain the postscript in french. [ps.gz]

Extended Automata Verification :

Symbolic Analysis Algorithms and Pratice.

Resume :

Within the framework of telecommunication, the companies develop protocols performing the data transfert between machines. These protocols work on the principle of sending of messages between two prts via unreliable channels. To make sure that all messages were received, the techniques employed consist in re-emitting the lost messages and/or awaiting a lapse of time determined before deciding of the failure from the transmission. Moreover, the systems are often modelized according to parameters.

We worked on a mathematical model allowing the verification of specifications (awaited behaviors of the systems) for protocols handling at the same time counters, queues or clocks, as well as parameters. The goal of the analysis is to calculate the set of the behaviors possible for the system then to check that none them violates an awaited specification. The problem here is that this set is in
finite. Indeed, a behavior is a function of the values taken by the variables of the system during the execution and some are defined on an infinite field. It is then necessary to be able to represent these behaviors in a finished way and to also find methods to calculate in a finished time an infinite set.

More formally, we placed ourselves within the framework of the automatic analysis of the systems (model-checking). The selected representation for the models with counters and clocks parameterized is an extension of the bounded matrices for which we have an exact method of acceleration (calculation in a finished time of sets of infinite behaviors).

Practical side, we established these methods in a tool TReX which is, to our knowledge, only being able to handle in an exact way of the counters, the clocks and the queues. We could check consequent examples such as the bounded retransm ission protocol.

Vérification d'automates étendus :

algorithme d'analyse symbolique et mise en oeuvre.

Résumé (francais) :

Dans le cadre de la télécommunication, les entreprises développent des protocoles gérant le transfert de données entre machines. Ces protocoles fonctionnent sur le principe d'envoi de messages entre deux parties par l'intermédiaire de canaux non fiables. Pour s'assurer que tous les messages ont bien été reçus, les techniques employées consistent à réémettre les messages perdus et/ou à attendre un laps de temps déterminé avant de conclure à l'échec de la transmission. De plus, les systèmes sont souvent modélisés en fonction de paramètres.

Nous avons travaillé sur un modèle mathématique permettant la vérification de spécifications (comportements attendus des systèmes) pour des protocoles manipulant à la fois des compteurs, des files d'attente ou des horloges, ainsi que des paramètres. Le but de l'analyse est de calculer l'ensemble des comportements possibles du système puis de vérifier qu'aucun d'eux ne viole une spécification attendue. Le problème ici est que cet ensemble est infini. En effet, un comportement est fonction des valeurs prises par les variables du système au cours de l'exécution et certaines sont définies sur un domaine infini. Il faut alors pouvoir représenter ces comportements de façon finie et aussi trouver des méthodes pour calculer en un temps fini un ensemble infini.

Plus formellement, nous nous sommes placés dans le cadre de l'analyse automatique des systèmes (model-checking). La représentation choisie pour les modèles à compteurs et horloges paramétrés est une extension des matrices de bornes pour laquelle nous avons une méthode exacte d'accélération (calcul en un temps fini d'ensembles de comportements infinis).

Du côté pratique, nous avons implanté ces méthodes dans un outil TReX qui est, à notre connaissance, le seul pouvant manipuler de manière exacte des compteurs, des horloges et des files d'attente. Nous avons pu vérifier des exemples conséquents tels que le protocole de retransmission bornée.