To see the other types of publications on this topic, follow the link: Vérification de modèles bornés.
Dissertations / Theses on the topic 'Vérification de modèles bornés'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Vérification de modèles bornés.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Kheireddine, Anissa. "Contribution to SAT-based Bounded Model Checking." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS566.
Full textAbstract:
Les systèmes informatiques sont devenus omniprésents dans notre vie quotidienne. Garantir la fiabilité et la robustesse de ces systèmes est une nécessité absolue. La Vérification de Modèles (Model-Checking) est l'une des approches dédiées à cette fin. Son objectif est de prouver l'absence de défaillances ou d'identifier d'éventuelles erreurs. La Vérification de Modèles se décline en plusieurs techniques. Parmi celles-ci, on trouve la Vérification de Modèles Bornée (Bounded Model Checking - BMC), une technique qui repose sur la satisfaisabilité booléenne (SAT). L'idée centrale derrière le BMC est de vérifier qu'un modèle, limité à des exécutions bornées par un entier k, satisfait sa spécification, souvent définie comme un ensemble d'expressions logiques temporelles. Dans cette approche, les comportements du système sont exprimés sous forme de problèmes SAT. Contrairement à d'autres méthodes de vérification formelle, le BMC basé sur SAT n'est généralement pas sensible au problème de l'explosion de l'espace d'états, ce qui peut poser problème lors de la conception de systèmes impliquant des millions de variables et de contraintes. Cependant, le compromis réside dans la complexité temporelle, car les problèmes SAT sont connus pour être NP-complets. Au cours des dernières décennies, d'importantes avancées ont été réalisées dans la résolution séquentielle de problèmes SAT. Ces développements se sont principalement concentrés sur l'utilisation d'informations dynamiques, acquises lors du processus de résolution (par exemple, l'apprentissage de clauses binaires) ou d'informations statiques, extraites de la structure inhérente du problème SAT (par exemple, la structure communautaire). Cependant, moins d'attention a été accordée aux informations structurelles intégrées dans le problème initial. Par exemple, lorsque qu'un problème BMC est réduit à SAT, des informations cruciales sont perdues dans la traduction. Comme le souligne cette thèse, la réintégration de ces informations perdues peut considérablement améliorer le processus de résolution. Ce travail explore des moyens d'améliorer la résolution de problèmes BMC basés sur SAT, tant dans des contextes séquentiels que parallèles, en exploitant et en valorisant les informations pertinentes extraites des caractéristiques inhérentes du problème. Cela peut impliquer l'amélioration d'heuristiques génériques existantes ou la décomposition efficace de la formule en partitions<br>Computer systems have become omnipresent in our daily lives. Ensuring the reliability and robustness of these systems is an absolute necessity. Model-Checking is one of the approaches dedicated to this purpose. Its objective is to either prove the absence of failures or identify potential ones. Model-Checking is declined into several technique. Among these, there is Bounded Model Checking (BMC), a technique that relies on Boolean satisfiability (SAT). The core idea behind BMC is to verify that a model, restricted to executions bounded by some integer k, satisfies its specification, often defined as a set of temporal logic expressions. In this approach, system behaviors are expressed as SAT problems. Unlike other formal verification methods, SAT-based BMC is generally not prone to the state space explosion problem, which can be problematic when dealing with designs involving millions of variables and constraints. However, the trade-off lies in the time complexity, as SAT problems are known to be NP-complete. Over the past few decades, significant advancements have been made in sequential SAT solving. These developments have mainly focused on utilizing dynamic information, acquired during the solving process (e.g., Learning Binary Clauses), or static information, extracted from the inherent structure of the SAT problem (e.g., community structure). However, less attention has been given to the structural information embedded within the original problem. For instance, when a BMC problem is reduced to SAT, critical information is lost in the translation. As this thesis emphasizes, reintegrating this lost information can greatly enhance the solving process. This work explores ways to improve SAT-based BMC problem-solving, both in sequential and parallel settings, by harnessing and leveraging pertinent information extracted from the problem's inherent characteristics. This may involve improving existing generic heuristics or effectively breaking down the formula into partitions
2
Duclos, Mathilde. "Méthodes pour la vérification des protocoles cryptographiques dans le modèle calculatoire." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAM002/document.
Full textAbstract:
Les échanges des informations confidentielles ou critiques dans un environnement public, et donc potentiellement hostile, nécessitent l'emploi de techniques cryptographiques (protocoles et primitives). Malheureusement, l'expérience montre qu'une mauvaise conception, ou une expression peu claire des propriétés et hypothèses de sécurité attendues conduisent à des attaques, et qu'il faut parfois des années avant que celles-ci soient découvertes et corrigées. D'où l'adoption croissante de la sécurité prouvable, où on donne une définition rigoureuse des objectifs de sécurité et des démonstrations mathématiques que ceux-ci sont remplis. Par ailleurs, la complexité et la diversité des systèmes cryptographiques croît également. Il est donc largement admis qu'il n'est plus viable d'écrire ou vérifier manuellement des démonstrations cryptographiques (Bellare& Rogaway 2004, Shoup 2004, Halevi 2005) et qu'il faut développer des méthodes de vérification des systèmes cryptographiques assistées par ordinateur. L'objectif de cette thèse est d'effectuer des progrès significatifs dans cette direction. Plus précisement on s'interesse à la preuve formelle de protocoles cryptographiques. Vérifier des protocoles cryptographiques requiert le développement d'un cadre théorique qui doit permettre: - une modélisation précise des protocoles cryptographiques et des propriétés de sécurité qu'on veut prouver dans le modèle calculatoire. - mise en place de stratégies d'automatisation de preuves. - prise en compte des modèles plus réalistes pour l'adversaire (canaux cachés, ressources de calcul). A la fin de la thèse on a obtenu un cadre formel et un ensemble de méthodes logicielles capable d'aider à la vérification des protocoles cryptographiques<br>Critical and private information are exchanged on public environment. To protect it from dishonest users, we use cryptographic tools. Unfortunately, bad conception, poorly written security properties and required security hypothesis lead to attacks, and it may take years before one discover the attack and fix the security schemes involved. In this context, provable security provides formal definitions for security objectives and implied mathematical proofs that these objectives are fullfilled. On another hand, complexity and variety of cryptographic systems are increasing, and proofs by hand are too complicated to write and to verify (Bellare& Rogaway 2004, Shoup 2004, Halevi 2005). Thus, we need computer-assisted verification methods for cryptographic systems. The aim of this thesis is to progress in this direction. More precisely we want significant progress over formal proofs on cryptographic protocols. To verify cryptographic protocols we need to develop a theoritical framework providing: - a precise modelisation for cryptographic protocols and security properties we want to prove in the computationnal model, - designing tactics to automate proofs, - taking into account realistic models for adversary (side-channels...). By the end of the thesis we have enhanced a theoretical framework and computing tools helping verifying cryptographic protocols
3
Harrou, Fouzi. "Détection d'anomalies en présence de paramètres de nuisance bornés." Troyes, 2010. http://www.theses.fr/2010TROY0002.
Full textAbstract:
Dans le cadre de la détection d’anomalies à base de modèles dans des systèmes complexes, les anomalies à détecter sont souvent associées à des paramètres de nuisances qui sont indésirables mais physiquement inévitables. En absence d'informations a priori fiables et précises sur la valeur de ces paramètres de nuisance, leur élimination devient nécessaire, ce qui peut considérablement diminuer les performances de la procédure de détection et même rendre indétectables certaines anomalies. Dans de nombreux cas, la nature physique des paramètres de nuisance est connue, ce qui permet de fixer des bornes sur les valeurs prises par ces paramètres. Dans cette thèse, on a étudié d'un point de vue statistique les problèmes de la détection d'anomalies dans un système linéaire en présence de paramètres de nuisance bornés. On a proposé une méthodologie statistique du rapport de vraisemblance généralisé avec contraintes permettant de prendre en compte des paramètres de nuisance bornés. Les propriétés statistiques de la méthode proposée ont été étudiées. On a montré que la prise en compte des informations de bornes dont on dispose sur les paramètres de nuisance permet d'améliorer la détection d'anomalies par rapport au test optimal UPPC invariant. Des applications au contrôle d’intégrité des systèmes de localisation GPS sont exposées dans le cas de la navigation ferroviaire. Enfin, les développements théoriques proposés dans cette thèse permettent la détection de mesures d'ozone anormales au moyen d'un réseau régionale de surveillance<br>Anomaly detection is addressed within a statistical framework. Often the statistical model is composed of two types of parameters: the informative parameters and the nuisance ones. The nuisance parameters are of no interest for detection but they are necessary to complete the model. In the case of unknown, non-random and non-bounded nuisance parameters, their elimination is unavoidable. Unfortunately, this can lead to a serious degradation of the detector capacity because some anomalies are masked by nuisance parameters. Nevertheless, in many cases, the physical nature of nuisance parameter is known, and this may allow set bounds to the values taken by this parameter. In this work, the problem of anomaly detection with bounded nuisance parameters has been addressed from the statistical point of view in the context of linear model. The con-strained generalized likelihood ratio test has been studied. It has been shown that the performances of anomaly detector can be drastically improved by taking into account the lower and upper bounds, naturally imposed on the nuisance parameters. Some applications to integrity control of GPS positioning systems are developed in fields of train navigation. Finally, the detection of abnormal ozone measurements by using a regional ozone surveillance network has been used to illustrate the theoretical findings and to show the relevance of the proposed method
4
El, Smaily Mohammad. "Equations de réaction-diffusion dans des milieux hétérogènes non bornés." Aix-Marseille 3, 2008. http://www.theses.fr/2008AIX30010.
Full textAbstract:
L'objet de cette thèse est l'étude de certains phénomènes de propagation de fronts pulsatoires pour des problèmes de réaction-advection-diffusion. La thèse se compose de trois parties qui correspondent à trois articles soumis à des revues internationales avec comité de lecture. En fait, l'existence de fronts progressifs pulsatoires dépend fortement du type de la nonlinéarité. Si la nonlinéarité f est de type "KPP", il existe une vitesse minimale c*. La première partie porte sur les comportements asymptotiques de la vitesse minimale c* de propagation des ondes progressives dans le cas "KPP" (utilisant une formule variationnelle de c* donnée par Berestycki, Hamel, et Nadirashvili en 2002). Dans la seconde partie, on donne des formules min-max et max-min pour les vitesses de propagation selon le type de la réaction. La troisième partie concerne la dépendance de la vitesse par rapport à la période spatiale dans un cadre plus général (concernant la diffusion et la nonlinéarité) que celui de la première partie, mais en dimension N = 1 seulement<br>In this thesis, we study some propagation phenomena related to the heterogenous reaction-advection-diffusion. This thesis is composed of three parts. If the nonlinearity f is of "KPP", there exists a minimal speed c*. In the first part, we study the asymptotics and some homogenization regimes of the minimal speed c* with respect to the factors of reaction and diffusion and with respect to the parameter of periodicity. In the second part, we give several min-max and max-min formulae for the speeds of pulsating travelling fronts according to the type of the nonlinearity. The third part is concerned with the variation of the minimal speed with respect to the periodicity parameter L and also with the homogenized speed of a reaction-diffusion equation in the one dimensional case, but in a setting more general than that of the first part
5
Lacresse, Hervé. "Détection de pannes en présence de paramètres de nuisance non-linéaires bornés." Troyes, 2004. http://www.theses.fr/2004TROY0001.
Full textAbstract:
Les schémas de détection applicables en présence de paramètres de nuisance visent souvent à l'élimination de ces paramètres au sein du processus de décision. Cependant, il est souvent possible de déterminer des limitations (bornes) pour l'évolution de ces paramètres, en se fondant sur des considérations physiques. Ne pas prendre en compte ces bornes peut constituer une perte d'informations pertinentes pour l'élaboration d'un schéma de détection. En s'appuyant sur la structure de tests statistiquement optimaux obtenus dans le cas de nuisances linéaires, une méthodologie de détection adaptée à des modèles comportant des paramètres de nuisance non linéaires et bornés est proposée. Elle s'appuie sur l'utilisation d'approximations linéaires dont l'originalité est de permettre l'évaluation de l'impact des approximations réalisées sur les performances des tests utilisés, par comparaison avec les performances optimales obtenues dans le cas linéaire. Cette comparaison est formulée en termes de modifications potentielles des probabilités de fausse alarme et de non détection des tests utilisés, du fait de la " non linéarité " du modèle. Des applications au contrôle d'intégrité des systèmes de localisation GPS/GNSS sont exposées dans le cas de la navigation aérienne et de la navigation ferroviaire<br>Fault detection schemes usually aim at eliminating nuisance parameters from the decision process upon wich they rely. However, it is often possible to determine some bounds to the variations ot these parameters, taking into account physical considerations. Neglecting these bounds is a potential loss of relevant information. A fault detection methodology for models with non-linear bounded nuisance parameters is suggested. This methodology is based upon the design of the optimal staistical tests obtained in the linear nuisance case. This detection scheme uses non conventional linear approximations, whose impact on the performances of the tests can be assessed through a comparison to the optimal results of the linear case. This comparison is expressed in terms of modifications in the false-alarm and non-detection probabilities of the tests, reflecting the "non linearity" of the model. Some applications to integrity control of GPS/GNSS positioning systems are developed in the fields of plane and train navigation
6
Bouyer-Decitre, Patricia. "Modèles et algorithmes pour la vérification des systèmes temporisés." Cachan, Ecole normale supérieure, 2002. http://www.theses.fr/2002DENS0008.
Full text
7
Beaudenon, Vincent. "Diagrammes de décision de données pour la vérification de systèmes matériels." Paris 6, 2006. http://www.theses.fr/2006PA066337.
Full textAbstract:
Avec la complexité croissante des systèmes informatiques se pose la question de la mise en oeuvre de méthodes automatiques pour leur vérification formelle. Parmi ces méthodes, le model-checking se fonde sur l'exploration exhaustive du comportement d'un système. Plus celui-ci sera complexe, plus cette exploration se traduira par une explosion combinatoire de l'espace des états du système. Diverses approches ont été proposées pour résoudre ce problème, notamment les méthodes symboliques qui sont bases sur une représentation compacte d'ensembles d'états. Depuis les travaux de R. E. Bryant et la définition des Diagrammes de Décision Binaires (BDD), de nombreuses représentations en DAG d'espaces d'états ont vu le jour, parmi celles-ci, on trouve les Diagrammes de Décision de Données (DDD), qui procurent une représentation compacte d'ensemble d'états et sont pourvus de mécanismes de parcours définis localement pour la réalisation des modifications sur ces états et des opérations ensemblistes. Parallélement, les travaux de G. J. Holzmann ont abouti à la création de l'outil de vérification SPIN, basé sur des méthodes énumératives explicites, pour des systèmes décrits en langage Promela. Ces systèmes sont proches de ceux qui sont utilisés pour la synthèse de haut niveau. Nous proposons une approche de vérification symbolique de systèmes matériels décrits dans un sous-ensemble du langage Promela. La représentation symbolique d'ensembles d'états est basée sur les Diagrammes de Décision de Données qui évitent de d'écrire le système au niveau booléen. Nous présentons d'abord la sémantique du langage Promela ainsi que les DDD puis les mécanismes mis en oeuvre pour la vérification de propriétés de logique CTL. Les conclusions tirées de cette première étape conduisent à proposer l'utilisation des Diagrammes de Décision d'Ensembles (SDD) pour améliorer les performances de la vérification automatique. Nous montrons que, bien que pourvus d'une implémentation et d'une terminologie différentes, il se prévalent du même formalisme que les DDD tout en procurant un étiquetage symbolique des arcs de la structure. Nous expérimentons ensuite cette approche sur des systèmes académiques et sur des systèmes issus d'applications industrielles. Ces expérimentations corroborent nos premiers résultats : les SDD couplés aux méthodes de saturation constituent une alternative sérieuse pour la vérification de systèmes à fort degré de concurrence. Nous proposons des perspectives de recherche pour améliorer encore la vérification de tels systèmes mais également pour introduire le concept de hiérarchie dans la description du système
8
Jacquemard, Florent. "Modèles d'automates d'arbres étendus pour la vérification de systèmes infinis." Habilitation à diriger des recherches, École normale supérieure de Cachan - ENS Cachan, 2011. http://tel.archives-ouvertes.fr/tel-00643595.
Full textAbstract:
Ce document présente l'étude de plusieurs modèles de machines à états finis qui étendent tous le même formalisme: les automates d'arbres classiques, et leur application dans différentes tâches telles que l'analyse statique de programmes ou de systèmes, la typage, la vérification de la cohérence de spécifications, le model checking... Les arbres sont une structure naturelle de données, très répandue en informatique, par exemple pour la représentation des structures de données hiérarchiques ou imbriquées, pour des algorithmes spécifiques (arbres binaires de recherche, algorithmes distribués), comme modèle abstrait pour des données semi-structurées utilisées pour l'échange d'information dans le Web, pour une présentation algébrique de processus récursifs, comme les termes en logique... Lorsqu'il s'agit de raisonner sur des systèmes manipulant des arbres, ou modelisés par des arbres, il est crucial d'avoir une représentation finie d'ensembles infinis d'arbres. Les automates d'arbres sont des machines à états finis permettant une telle représentation. Ils ont fait la preuve de leur adéquation à des tâches de raisonnement: ils ont un modèle théorique bien établi, en étroite relation avec la logique, ils bénéficient de bonnes propriétés de composition et d'algorithmes de décision efficaces. En particulier, les automates d'arbres sont utilisées au coeur de systèmes de vérification formelle d'outils de déduction automatique. Toutefois, les automates d'arbres ont des limitations sévères en expressivité. Par exemple, ils sont incapables de faire du filtrage non-linéaire ou d'exprimer des contraintes d'intégrité tels que les clés dans les bases de données. Certaines extensions ont été proposées afin d'améliorer le modèle en essayant de conserver de bonnes propriétés. Nous présentons dans ce document de plusieurs de telles extensions, leurs propriétés et leur utilisation en vérification symbolique de systèmes et de programmes.
9
Colin, Séverine. "Procédures de recherche en génération de testes à partir de modèles de spécifications." Besançon, 2005. http://www.theses.fr/2005BESA2042.
Full textAbstract:
Les travaux présentés dans cette thèse proposent des procédures de recherche opérationnelle dans le cadre de la génération automatique de tests fonctionnels à partir de modèles de spécifications. Les opérations du modèle sont réécrites sous la forme de graphes. Les chemins de ces graphes représentent les comportements du modèle. L'animation contrainte -c'est-à-dire la simulation d'exécution- des comportements du modèle est réalisée au moyen du solveur logico-ensembliste CLPS-BZ. L'objectif général de la méthode de génération consiste à produire un ensemble de tests permettant de couvrir des cibles de test spécifiques. Ces cibles de test sont calculées à partir des comportements du modèle et en fonction de critères de couverture. La partie la plus délicate de la génération d'un test consiste à trouver un chemin, nommé préambule, permettant d'atteindre la cible de test à partir de l'état initial du système. La partie du test, nommée postambule, qui permet de réinitialiser le système pour enchaîner les tests, présente une problématique similaire. Cette thèse propose différentes procédures pour la génération du préambule et du postambule. Un algorithme en largeur se fondant sur les comportements du système est proposé pour le calcul du préambule. D'autre part, différents algorithmes de type best-first ont été évalués dans le cadre d'animation en chaînage avant et chaînage arrière. Les algorithmes proposés ont été implantés et adaptés pour différentes notations de spécifications : B et statechart Statemate. Ces algorithmes ont été mis en oeuvre sur plusieurs applications industrielles, et optimisés afin de permettre le passage à l'échelle<br>The works introduced in this thesis give operational research procedures in the context of automatic functional test generation from specification models. The operations of the model are transformed into graphs. The paths of these graphs represent the behaviors of the model. The constraint animation (i. E. The simulation of the execution) of the behaviors is performed by the set constraint solver CLPS-BZ. The main goal of the generation method is to produce a set of tests designed to cover a specific set of test targets. These targets are computed from the model behaviors and in accordance with coverage criteria. The most delicate part of a test generation is to find a path, called preamble, that allows to reach a test target from the initial state of the system. The part of the test called postamble resets the system in a state that allows to resume the test procedure and comes under a similar problem. This PhD thesis gives several procedures in order to generate the preamble and postamble. A breadth search algorithm based on the system behaviors is given for the preamble computation. Besides, several Best-First search procedures are evaluated in the context of forward and backward chaining animations to compute the preamble and postamble. These algorithms have been implemented and adapted to several notations of specifications: B and Statemate statecharts. These algorithms have been used on many industrial projects and are optimized to go large scale
10
Cortier, Véronique. "Analyse des protocoles cryptographiques: des modèles symboliques aux modèles calculatoires." Habilitation à diriger des recherches, Institut National Polytechnique de Lorraine - INPL, 2009. http://tel.archives-ouvertes.fr/tel-00578816.
Full textAbstract:
Les protocoles de sécurité sont des programmes informatiques qui définissent des règles d'échange entre les points d'un réseau et permettent de sécuriser les communications. Ils sont utilisés par exemple dans les distributeurs de billets, les abonnements aux chaînes de télévision payantes, la téléphonie mobile, le commerce électronique. Leur objectif est de garantir le secret d'une donnée, d'authentifier un des participants, de garantir l'anonymat ou la non-répudiation, etc. Ces programmes sont exécutés sur des réseaux ouverts facilement accessibles (comme internet). Aussi, pour démontrer qu'ils remplissent bien leurs objectifs, il est nécessaire de prendre en compte les attaques dont ils peuvent faire l'objet. L'objet de mon mémoire d'habilitation à diriger des recherches est de montrer que les méthodes formelles peuvent être utilisées avec succès pour entreprendre une analyse fine des protocoles cryptographiques, à travers une palette variée d'outils. Nous présentons des procédures pour déterminer de façon automatique si un protocole est sûr. Nous avons proposés différents algorithmes en fonction des propriétés de sécurité considérées ainsi que des primitives cryptographiques utilisées (chiffrement, signature, hachage, ou exclusif, etc.). D'autre part, nous caractérisons des conditions qui permettent de combiner les résultats précédents et de concevoir les protocoles de façon modulaire. Ces résultats se basent sur des modèles symboliques, très différents de ceux utilisés en cryptographie où la notion de sécurité est basée sur la théorie de la complexité. Cette notion de sécurité est mieux adaptée pour identifier toutes les attaques possibles dans la réalité mais, en contrepartie, les (lourdes) preuves de sécurité sont effectuées à la main et semblent difficilement automatisables. Nous avons identifié des hypothèses cryptographiques qui permettent de relier les approches cryptographiques et symboliques. Il est alors possible d'obtenir des preuves de sécurité à un niveau cryptographique, directement à partir des preuves établies (automatiquement) dans un cadre symbolique.
11
Jovanovic, Aleksandra. "Vérification parametrée de systèmes temporisés." Ecole centrale de Nantes, 2013. http://www.theses.fr/2013ECDN0036.
Full textAbstract:
Dans cette thèse, nous étudions la vèrification formelle des systèmes avec des contraintes temporelles. Comme formalisme pour la modélisation et l’analyse de ces systèmes, nous utilisons les automates temporisés. Le model-checking est une méthode de vérification formelle qui vérifie automatiquement si un modèle d’un système donné satisfait une propriété. Cependant, cette méthode nécessite une connaissance complète du système, ce qui est souvent difficile dans les premiers stades de la conception. L’approche paramétrique est un moyen de résoudre ce problème et d’augmenter la robustesse de la conception. Nous étudions les automates temporisés paramétrés, un modèle qui permet l’utilisation d’expressions paramétriques au lieu de valeurs temporelles concrètes dans le modèle. Nous offrons de nouveaux résultats de décidabilité négatifs concernant les propriétés d’accessibilité et d’inévitabilité. Nous proposons alors une nouvelle approche, dans laquelle nous limitons les valeurs des paramètres à des entiers bornés et nous proposons des algorithmes symboliques pour la synthèse de paramètres basée sur le calcul de l’enveloppe entière des états symboliques. Ces algorithmes sont implémentés dans notre outil Roméo. Nous étudions ensuite les jeux temporisés, un modèle utilisé pour les problèmes de contrôle sur des systèmes temps réel et proposons leur paramétrisation. Nous offrons une sous-classe pour laquelle le jeu d’accessibilité est décidable et un algorithme pour le calcul des états gagnants et la synthèse des paramètres<br>In this thesis we are studying formal verification of systems with timing constraints. As a formalism for modeling and analyzing such systems, we are using timed automata. Model-checking is a formal verification method that automatically verifies whether the model of the system satisfies some property. This method, however, requires complete knowledge of the system, which is often difficult to provide in the early design stages. Parametric approach is a way to address this issue and to increase the robustness of the design. We study parametric timed automata, a model that allows the use of parametric expressions instead of concrete timing values in the model. We offer new negative decidability results concerning reachability and unavoidability properties. We then propose a novel approach, we restrict parameter values to bounded integers and offer symbolic algorithms for parameter synthesis based on the computation of the integer hull of symbolic states. These algorithms are implemented in our tool Roméo. We then study timed game automata, a model used for control problems on real-times systems and propose its parametrization. We offer a subclass for which the reachability game is decidable and an algorithm for the computation of winning states and parameter synthesis. Finally, we study a parametric version of interrupt timed automata, a subclass of hybrid automata that uses stopwatches. We prove that the reachability problem is decidable without any restrictions and we give the complexity bounds
12
Mazo, Peña Raúl. "Modèle générique pour la vérification de modèles de lignes de produits." Paris 1, 2011. http://www.theses.fr/2011PA010075.
Full textAbstract:
La production de masse n'est pas un phénomène nouveau : depuis le 12ème siècle à Venise, jusqu'à nos jours, les industries du navire, du coton et de la voiture utilisent ce concept pour accroître l'efficacité et réduire les pertes, deux facteurs clés pour améliorer les bénéfices. Cependant, le consumérisme de nos jours rend la production de masse insuffisante pour satisfaire les nouvelles exigences où la personnalisation est essentielle. Un nouveau paradigme de production était nécessaire pour soutenir ces nouvelles exigences, en gardant des coûts de production raisonnables, des besoins de main d'œuvre et des délais de commercialisation. Comme réponse à ce besoin, l'ingénierie des lignes de produits surgit comme un nouveau paradigme de développement conduit par la réutilisation qui permet la gestion de composants réutilisables. Dans cette thèse, une ligne de produits est définie comme un groupe d'applications similaires au sein d'un secteur de marché et qui partage un ensemble commun d’exigences, mais aussi présente une variabilité importante des exigences (Bosch 2000, Clements & Northrop 2001).
13
Vergamini, Didier. "Vérification de réseaux d'automates finis par équivalences observationnelles : le système AUTO." Nice, 1987. http://www.theses.fr/1987NICE4142.
Full textAbstract:
Pour modéliser les systèmes parallèles et communicants, on utilise les algèbres de processus introduites par R. Milner permettant de donner la sémantique de termes représentant de tels systèmes sous forme de systèmes de transitions. Pour vérifier des programmes, on utilise la notion d'équivalence observationnelle associée à un critère d'observation. Le système AUTO issu du système ECRINS qui permet de manipuler des algèbres de processus est utilisé pour la mise en œuvre du principe de vérification. On donne une description complète du système et de son implantation en LE LISP. Son utilisation est illustrée par des exemples très classiques dans le domaine de la vérification des systèmes parallèles. On traite ensuite des exemples plus complexes d'algorithmes distribués
14
Lepiller, Julien. "Vérification d'isolation de fautes logicielle." Thesis, Rennes 1, 2019. http://www.theses.fr/2019REN1S067.
Full textAbstract:
Nous sommes habitués à utiliser des ordinateurs sur lesquels coopèrent des programmes d'origines diverses. Chacun de ces programmes a besoin d'accéder à de la mémoire vive pour fonctionner correctement, mais il ne faudrait pas qu'un programme accède ou modifie la mémoire d'un autre programme. Si cela ce produisait, les programmes ne pourraient plus faire confiance à la mémoire et pourraient se comporter de manière erratique. Les programmeurs n'ont pourtant pas besoin de se mettre d'accord à l'avance sur les zones mémoire qu'ils pourront ou non utiliser. Le matériel s'occupe d'allouer des zones de mémoire distinctes pour chaque programme. Tout cela est transparent pour le programmeur. Un programme malveillant ne pourrait d'ailleurs pas non plus accéder ou modifier la mémoire d'un autre programme pour l'attaquer directement. Mais il existe une catégorie de programmes qui ne bénéficient pas de cette protection : les modules qui étendent les fonctionnalités d'autres programmes, comme un module complémentaire de navigateur. Cette thèse repose sur une technique d'isolation de faute logicielle, et non matérielle et en propose deux sémantiques, l'une parallèle et pas l'autre, ainsi qu'un analyseur statique basé sur l'interprétation abstraite. Elle présente aussi une preuve de correction de l'analyseur<br>We are used to use computers on which programs from diverse origins are installed and running at the same time. Each of these programs need to access memory for proper operation, but none of them should access or modify the memory of another. If this happened, programs would not be able to trust their memory and could start behaving erratically. Still, programmers do not need to coordinate and agree in advance on what parts of the memory they are allowed to use or not. Hardware takes care of allocating distinct memory zones for each program. This is completely transparent to the programmer. A malware cannot access or modify the memory of another program to attack it directly either. However, there exists a category of programs that do not benefit from this protection: modules that extend the features of other programs, such as plugins in a web browser. This thesis is based on a software (and not hardware) fault isolation technique, and proposes two semantics for it, single-threaded and multi-threaded, as well as a static analyzer based on abstract interpretation. We also present a proof of correctness for the analyzer
15
Larcher, Anthony. "Modèles acoustiques à structure temporelle renforcée pour la vérification du locuteur embarquée." Phd thesis, Université d'Avignon, 2009. http://tel.archives-ouvertes.fr/tel-00453645.
Full textAbstract:
La vérification automatique du locuteur est une tâche de classification qui vise à confirmer ou infirmer l'identité d'un individu d'après une étude des caractéristiques spécifiques de sa voix. L'intégration de systèmes de vérification du locuteur sur des appareils embarqués impose de respecter deux types de contraintes, liées à cet environnement : - les contraintes matérielles, qui limitent fortement les ressources disponibles en termes de mémoire de stockage et de puissance de calcul disponibles ; - les contraintes ergonomiques, qui limitent la durée et le nombre des sessions d'entraînement ainsi que la durée des sessions de test. En reconnaissance du locuteur, la structure temporelle du signal de parole n'est pas exploitée par les approches état-de-l'art. Nous proposons d'utiliser cette information, à travers l'utilisation de mots de passe personnels, afin de compenser le manque de données d'apprentissage et de test. Une première étude nous a permis d'évaluer l'influence de la dépendance au texte sur l'approche état-de-l'art GMM/UBM (Gaussian Mixture Model/ Universal Background Model). Nous avons montré qu'une contrainte lexicale imposée à cette approche, généralement utilisée pour la reconnaissance du locuteur indépendante du texte, permet de réduire de près de 30% (en relatif) le taux d'erreurs obtenu dans le cas où les imposteurs ne connaissent pas le mot de passe des clients. Dans ce document, nous présentons une architecture acoustique spécifique qui permet d'exploiter à moindre coût la structure temporelle des mots de passe choisis par les clients. Cette architecture hiérarchique à trois niveaux permet une spécialisation progressive des modèles acoustiques. Un modèle générique représente l'ensemble de l'espace acoustique. Chaque locuteur est représenté par une mixture de Gaussiennes qui dérive du modèle du monde générique du premier niveau. Le troisième niveau de notre architecture est formé de modèles de Markov semi-continus (SCHMM), qui permettent de modéliser la structure temporelle des mots de passe tout en intégrant l'information spécifique au locuteur, modélisée par le modèle GMM du deuxième niveau. Chaque état du modèle SCHMM d'un mot de passe est estimé, relativement au modèle indépendant du texte de ce locuteur, par adaptation des paramètres de poids des distributions Gaussiennes de ce GMM. Cette prise en compte de la structure temporelle des mots de passe permet de réduire de 60% le taux d'égales erreurs obtenu lorsque les imposteurs prononcent un énoncé différent du mot de passe des clients. Pour renforcer la modélisation de la structure temporelle des mots de passe, nous proposons d'intégrer une information issue d'un processus externe au sein de notre architecture acoustique hiérarchique. Des points de synchronisation forts, extraits du signal de parole, sont utilisés pour contraindre l'apprentissage des modèles de mots de passe durant la phase d'enrôlement. Les points de synchronisation obtenus lors de la phase de test, selon le même procédé, permettent de contraindre le décodage Viterbi utilisé, afin de faire correspondre la structure de la séquence avec celle du modèle testé. Cette approche a été évaluée sur la base de données audio-vidéo MyIdea grâce à une information issue d'un alignement phonétique. Nous avons montré que l'ajout d'une contrainte de synchronisation au sein de notre approche acoustique permet de dégrader les scores imposteurs et ainsi de diminuer le taux d'égales erreurs de 20% (en relatif) dans le cas où les imposteurs ignorent le mot de passe des clients tout en assurant des performances équivalentes à celles des approches état-de-l'art dans le cas où les imposteurs connaissent les mots de passe. L'usage de la modalité vidéo nous apparaît difficilement conciliable avec la limitation des ressources imposée par le contexte embarqué. Nous avons proposé un traitement simple du flux vidéo, respectant ces contraintes, qui n'a cependant pas permis d'extraire une information pertinente. L'usage d'une modalité supplémentaire permettrait néanmoins d'utiliser les différentes informations structurelles pour déjouer d'éventuelles impostures par play-back. Ce travail ouvre ainsi de nombreuses perspectives, relatives à l'utilisation d'information structurelle dans le cadre de la vérification du locuteur et aux approches de reconnaissance du locuteur assistée par la modalité vidéo
16
Nguyên, Duy-Tùng. "Vérification symbolique de modèles à l'aide de systèmes de ré-écriture dédiés." Phd thesis, Université d'Orléans, 2010. http://tel.archives-ouvertes.fr/tel-00579490.
Full textAbstract:
Cette thèse propose un nouveau type de systèmes de ré-écriture, appelé les systèmes de réécriture fonctionnels. Nous montrons que notre modèle a la puissance d'expression des systèmes de ré-écriture et qu'il est bien adapté à l'étude de propriétés de sûreté et de propriétés de logique temporelle de modèles.Nous avons mis en évidence une sous classe de systèmes fonctionnels, les élémentaires et les élémentaires à droite, préservant la puissance d'expression des systèmes fonctionnels et des techniques d'accélération des calculs aboutissant à un outil de vérification symbolique efficace.Dans la partie expérimentale, nous avons comparé notre outil, d'une part avec des outils de ré-écriture tels que Timbuk, Maude et TOM, d'autre part avec des outils de vérification tels que SPIN, NuSMV, SMART, HSDD. Nos benchmarks démontrent l'efficacité des systèmes fonctionnels élémentaires pour la vérification de modèles.
17
Trojet, Mohamed Wassim. "Approche de vérification formelle des modèles DEVS à base du langage Z." Aix-Marseille 3, 2010. http://www.theses.fr/2010AIX30040.
Full textAbstract:
Le cadre général dans lequel se situe cette thèse concerne l’amélioration de la vérification et la validation des modèles de simulation par l'intégration des méthodes formelles. Notre approche consiste à doter les modèles DEVS d’une approche de vérification formelle basée sur le langage Z. DEVS est un formalisme qui permet la description et l'analyse du comportement des systèmes à évènements discrets, c'est à dire, les systèmes dont le changement d'état dépend de l'occurrence d'un évènement. Un modèle DEVS est essentiellement validé par la simulation qui permet de vérifier si celui ci décrit bien le comportement du système. Cependant, la simulation ne permet pas de détecter la présence d’une éventuelle inconsistance dans le modèle (un conflit, une ambiguïté ou une incomplétude). Pour cela, nous avons intégré un langage de spécification formelle dans le formalisme DEVS connu sous le nom de Z. Cette intégration consiste à: (1) transformer un un modèle DEVS vers une spécification Z équivalente et (2) vérifier la consistance de la spécification résultante utilisant les outils développés par la communauté Z. Ainsi un modèle DEVS est soumis à une vérification formelle automatique avant son passage à la phase de simulation<br>The general framework of the thesis consists in improving the verification and the validation of simulation models through the integration of formal methods. We offered an approach of formal verification of DEVS models based on Z language. DEVS is a formalism that allows the description and analysis of the behavior of discrete event systems, ie systems whose state change depends on the occurrence of an event. A DEVS model is essentially validated by the simulation which permits to verify if it correctly describes the behavior of the system. However, the simulation does not detect the presence of a possible inconsistency in the model (conflict, ambiguity or incompleteness). For this reason, we have integrated a formal specification language, known as Z, in the DEVS formalism. This integration consists in: (1) transforming a DEVS model into an equivalent Z specification and (2) verifying the consistency of the resulting specification using the tools developed by the Z community. Thus, a DEVS model is subjected to an automatic formal verification before its simulation
18
Contet, Jean-Michel. "Modèles multi-agents réactifs pour la navigation multi-véhicules : spécification formelle et vérification." Phd thesis, Université de Technologie de Belfort-Montbeliard, 2009. http://tel.archives-ouvertes.fr/tel-00472415.
Full textAbstract:
Cette thèse propose des modèles multi-agents réactifs fondés sur un cadre formel pour la vérification de propriétés et les valider par la simulation et l'expérimentation en considérant la navigation multi-véhicules comme domaine d'application. La navigation multi-véhicules soulève plusieurs problématiques : perception de l'environnement, communication inter-véhicule, évitement d'obstacle, ... Dans ce contexte, nous avons abordé plus particulièrement les aspects suivants : - Concernant la navigation multi-véhicules nous avons abordé deux problèmes spécifiques : la conduite en convoi ou platooning et la navigation autonome. En ce qui concerne la navigation autonome, nous avons mis l'accent sur l'évitement d'obstacles. - Concernant l'approche proposée : nous adoptons les systèmes multi-agents réactifs, dont les interac- tions sont inspirée de la physique. Pour la conduite en convoi, nous proposons un modèle d'interaction basé sur la physique classique. En ce qui concerne l'évitement d'obstacles, nous adoptant un modèle inspiré de la physique statistique. - Nous plaçons les systèmes multi-agents réactifs dans un cadre formel pour la vérification des pro- priétés, compte-tenu des contraintes de sécurité imposées par la classe d'applications cible. Pour faire face à la complexité des modèles, nous proposons une règle et une méthode de vérification compositionnelle. Cela nous a permis de vérifier la satisfaction d'une propriété de sûreté essentielle : la non-collision entre véhicules lors de la conduite en convoi. - Nous abordons également la question de la validation du système multi-agents par la simulation et l'expérimentation : nous avons contribué au développement d'un simulateur de la conduite en convoi et la navigation autonome. Le simulateur prend en compte les caractéristiques physiques des véhicules et est couplé à un outil de visualisation 3D. Nous avons aussi expérimenté nos modèles sur des véhicules tels que le Cycab et le GEM Car.
19
Chapurlat, Vincent. "Vérification et validation de modèles de systèmes complexes: application à la Modélisation d'Entreprise." Habilitation à diriger des recherches, Université Montpellier II - Sciences et Techniques du Languedoc, 2007. http://tel.archives-ouvertes.fr/tel-00204981.
Full textAbstract:
Cette Habilitation à Diriger des Recherches est le fruit des résultats, tant en recherche qu'en enseignement ou en transfert, de mon activité d'enseignant chercheur. Initiée au sein du Laboratoire d'Informatique, de Microélectronique et de Robotique de Montpellier (LIRMM, UMR CNRS/UM2) de 1991 à 1994, cette activité s'est ensuite concrétisée au sein du Laboratoire de Génie Informatique et d'Ingénierie de Production (LGI2P) de l'Ecole des Mines d'Alès où j'exerce depuis 1994.<br />Le travail de recherche entrepris depuis le début du Doctorat en 1991 relève de la thématique de la modélisation de systèmes complexes puis de la vérification et de la validation de ces modèles. Ceci a pour objectif d'assurer, ou à défaut de rassurer, le modeleur sur la qualité des modèles, sur leur pertinence vis-à-vis du système considéré et sur le respect d'exigences qui ont présidé à leur construction. La recherche a donc consisté au développement d'approches de modélisation, de spécification formelle de propriétés, de vérification par preuve de propriétés au moyen de Graphes Conceptuels et de simulation comportementale. Les domaines d'application privilégiés ont été les systèmes de contrôle commande répartis, puis plus largement la modélisation d'entreprise et tentent aujourd'hui d'intégrer une dimension risque dans la modélisation d'entreprise et de s'ouvrir plus largement à l'ingénierie des systèmes complexes. Les résultats sont des langages et un cadre de modélisation intégré, un langage de spécification baptisé LUSP, une suite de mécanismes de preuve formelle et de simulation qui ont donné lieu à divers encadrements de thèses, de travaux et à des transferts vers l'industrie. <br />Enfin, l'activité d'enseignement a tenté de rester cohérente avec le profil de compétence à la fois de producticien et d'ingénierie système acquis ou inspiré par la thématique de recherche. Elle s'est déroulée dans le cadre de diverses Universités, Ecoles d'Ingénieurs ou de cursus spécialisés. Les résultats sont des propositions et l'accompagnement de thématiques nouvelles, une activité d'ingénierie pédagogique et une implication dans diverses responsabilités administratives.
20
Dreyfus, Alois. "Contributions à la vérification et à la validation efficaces fondées sur des modèles." Thesis, Besançon, 2014. http://www.theses.fr/2014BESA2076/document.
Full textAbstract:
Les travaux de cette thèse contribuent au développement de méthodes automatiques de vérification et de valida-tion de systèmes informatiques, à partir de modèles. Ils sont divisés en deux parties : vérification et générationde tests.Dans la partie vérification, pour le problème du model-checking régulier indécidable en général, deux nouvellestechniques d’approximation sont définies, dans le but de fournir des (semi-)algorithmes efficaces. Des sur-approximations de l’ensemble des états accessibles sont calculées, avec l’objectif d’assurer la terminaison del’exploration de l’espace d’états. Les états accessibles (ou des sur-approximations de cet ensemble d’états)sont représentés par des langages réguliers, ou automates d’états finis. La première technique consiste à sur-approximer l’ensemble des états atteignables en fusionnant des états des automates, en fonction de critèressyntaxiques simples, ou d’une combinaison de ces critères. La seconde technique d’approximation consisteaussi à fusionner des états des automates, mais à l’aide de transducteurs. De plus, pour cette seconde technique,nous développons une nouvelle approche pour raffiner les approximations, qui s’inspire du paradigme CEGAR(CounterExample-Guided Abstraction Refinement). Ces propositions ont été expérimentées sur des exemplesde protocoles d’exclusion mutuelle.Dans la partie génération de tests, une technique qui permet de combiner la génération aléatoire avec un critèrede couverture, à partir de modèles algébriques (des grammaires algébriques, des automates à pile) est définie.Générer les tests à partir de ces modèles algébriques (au lieu de le faire à partir de graphes) permet de réduirele degré d’abstraction du modèle et donc de générer moins de tests qui ne sont pas exécutables dans le systèmeréel. Ces propositions ont été expérimentées sur la grammaire de JSON (JAvaScript Object Notation), ainsi quesur des automates à pile correspondant à des appels de fonctions mutuellement récursives, à une requête XPath,et à l’algorithme Shunting-Yard<br>The thesis contributes to development of automatic methods for model-based verification and validation ofcomputer systems. It is divided into two parts: verification and test generation.In the verification part, for the problem of regular model checking undecidable in general, two new approxi-mation techniques are defined in order to provide efficient (semi-)algorithms. Over-approximations of the setof reachable states are computed, with the objective of ensuring the termination of the exploration of the statespace. Reachable states (or over-approximations of this set of states) are represented by regular languages or,equivalently, by finite-state automata. The first technique consists in over-approximating the set of reachablestates by merging states of automata, based on simple syntactic criteria, or on a combination of these criteria.The second approximation technique also merges automata states, by using transducers. For the second tech-nique, we develop a new approach to refine approximations, inspired by the CEGAR paradigm (for Counter-Example-Guided Abstraction Refinement). These proposals have been tested on examples of mutual exclusionprotocols.In the test generation part, a technique that combines the random generation with coverage criteria, fromcontext-free models (context-free grammars, pushdown automata) is defined. Generate tests from these mo-dels (instead of doing from graphs) reduces the model abstraction level, and therefore allows having moretests executable in the real system. These proposals have been tested on the JSON grammar (JavaScript ObjectNotation), as well as on pushdown automata of mutually recursive functions, of an XPath query, and of theShunting-Yard algorithm
21
Kmimech, Mourad. "Vérification d’assemblages de composants logiciels : Application aux modèles de composants UML2.0 et Ugatze." Pau, 2010. http://www.theses.fr/2010PAUU3017.
Full textAbstract:
L'approche par composants vise la réutilisation par assemblage aisé et cohérent des composants. Mais l’obtention d’un assemblage de composants cohérent n’est pas un exercice facile. Pour y parvenir, nous préconisons une approche contractuelle distinguant divers contrats syntaxiques, structurels, sémantiques, de synchronisation et de qualité de services. Nous avons appliqué avec succès cette approche contractuelle sur deux modèles de composants semi-formels : UML2. 0 et Ugatze. En effet, nous proposons deux démarches VerifComponentUML2. 0 et VerifComponentUgatze. La démarche VerifComponentUML2. 0 vise la vérification des contrats syntaxiques, structurels, de synchronisation et de qualité de services sur une assemblage de composants UML2. 0 en passant par les deux modèles de composants formels Acme/Armani et Wright. VerifComponentUML2. 0 est équipé de deux outils : Wr2fdr et Wright2Ada. L’outil Wr2fdr permet de traduire des Wright vers CSP afin de vérifier les contrats de synchronisation en utilisant le model-checker FDR. L’outil Wright2Ada est un outil IDM permettant de transformer de Wright en Ada afin d’ouvrir UML2. 0 sur les outils d’analyse statique et dynamique associés à Ada. La démarche VerifComponentUgatze offre un cadre permettant de vérifier les contrats syntaxiques et structurels d’un assemblage de composant Ugatze en passant par Acme/Armani<br>The component approach aims for the reuse by a coherent and easy components assembly. But obtaining a coherent components assembly is not an easy exercise. To achieve this, we advocate a contractual approach distinguishing different syntactic, structural, semantic, synchronization and service quality contracts. We have successfully applied this approach on two models of semi-formal contractual components: UML2. 0 and Ugatze. Indeed, we propose two approaches: VerifComponentUML2. 0 and VerifComponentUgatze. The VerifComponentUML2. 0 approach aims the verification of syntactic, structural, synchronization and quality service contracts on a UML2. 0 component assembly through two formal component models Acme/Armani and Wright. VerifComponentUML2. 0 has two tools: Wr2fdr and Wright2Ada. The tool Wr2fdr allows translating Wright to CSP contracts in order to verify synchronization using the model checker FDR. It is a IDM tool Wright2Ada which allow is transforming Wright to Ada, in order to open UML2. 0 on static analysis and dynamic tools associated with Ada. VerifComponentUgatze approach provides a frame allowing to check syntactic and structural contracts of an Ugatze component assembly through Acme/Armani
22
Lewicki, Alexandre. "Conception de modèles haut niveau pour l'optimisation et la vérification de systèmes Bluetooth." Nice, 2008. http://www.theses.fr/2008NICE4110.
Full textAbstract:
Les différents travaux de recherche présentés dans cette thèse portent sur la conception de modèles fonctionnels à haut niveau d’abstraction ainsi que leur utilisation dans un flot de conception de systèmes sans fil. La Méthodologie de Conception des Systèmes Embarqués (MCSE) a été expérimentée pour la conception des circuits et systèmes dédiés à la technologie Bluetooth. La première partie de la thèse présente la méthodologie MCSE et son application dans la conception d’un système comportant un capteur de température distant et relié par Bluetooth. A partir des spécifications de l’application, les modèles fonctionnels ont été élaborés et raffinés après différentes étapes successives. Les modèles ont ensuite été traduits à l’aide de SystemC, une librairie C++ permettant de décrire les systèmes aux niveaux matériels et logiciels. Les modèles ont ensuite été exploités dans le cadre de simulation de réseaux sans fil. Ces résultats peuvent être utilisés suivant 3 différents axes : l’analyse de protocole, l’analyse de performances et l’exploration d’architecture. La deuxième partie du travail a été d’introduire les modèles fonctionnels dans le cadre d’un environnement de vérification matérielle avant fabrication. Deux environnements ont été mis en place pour les concepteurs du circuit ainsi que pour les ingénieurs de vérification. Cette technique permet de simuler et stresser le circuit de manière plus avancée, notamment grâce à la possibilité d’écrire des tests plus complets<br>The different works conducted in this thesis were to design high level functional models that were used in a wireless system design flow. The MCSE methodology was followed to design those models and the results have been used for Bluetooth technology system design and verification. The first part of the work presents the MCSE methodology that has been used for the design of the models. Starting from the specification of a concrete use case, a temperature sensor, we designed a functional model of the system with successive refinement steps. The models were then translated in SystemC, a C++ library that allows describing both hardware and software parts of a system. The results of the exploitation of the models in a wireless network simulation can be used for protocol analysis, performance analysis and performance exploration. The second part of the work was to introduce the functional models in a hardware verification environment. Two different techniques for design engineers and verification engineers have been settled. This technique brings enhanced verification features with the possibility to write complex tests
23
Declerck, David. "Vérification par model-checking de programmes concurrents paramétrés sur des modèles mémoires faibles." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS336/document.
Full textAbstract:
Les multiprocesseurs et microprocesseurs multicœurs modernes mettent en oeuvre des modèles mémoires dits faibles ou relâchés, dans dans lesquels l'ordre apparent des opérations mémoire ne suit pas la cohérence séquentielle (SC) proposée par Leslie Lamport. Tout programme concurrent s'exécutant sur une telle architecture et conçu avec un modèle SC en tête risque de montrer à l'exécution de nouveaux comportements, dont certains sont potentiellement des comportements incorrects. Par exemple, un algorithme d'exclusion mutuelle correct avec une sémantique par entrelacement pourrait ne plus garantir l'exclusion mutuelle lorsqu'il est mis en oeuvre sur une architecture plus relâchée. Raisonner sur la sémantique de tels programmes s'avère très difficile. Par ailleurs, bon nombre d'algorithmes concurrents sont conçus pour fonctionner indépendamment du nombre de processus mis en oeuvre. On voudrait donc pouvoir s'assurer de la correction d'algorithmes concurrents, quel que soit le nombre de processus impliqués. Pour ce faire, on s'appuie sur le cadre du Model Checking Modulo Theories (MCMT), développé par Ghilardi et Ranise, qui permet la vérification de propriétés de sûreté de programmes concurrents paramétrés, c'est-à-dire mettant en oeuvre un nombre arbitraire de processus. On étend cette technologie avec une théorie permettant de raisonner sur des modèles mémoires faibles. Le résultat ce ces travaux est une extension du model checker Cubicle, appelée Cubicle-W, permettant de vérifier des propriétés de systèmes de transitions paramétrés s'exécutant sur un modèle mémoire faible similaire à TSO<br>Modern multiprocessors and microprocesseurs implement weak or relaxed memory models, in which the apparent order of memory operation does not follow the sequential consistency (SC) proposed by Leslie Lamport. Any concurrent program running on such architecture and designed with an SC model in mind may exhibit new behaviors during its execution, some of which may potentially be incorrect. For instance, a mutual exclusion algorithm, correct under an interleaving semantics, may no longer guarantee mutual exclusion when implemented on a weaker architecture. Reasoning about the semantics of such programs is a difficult task. Moreover, most concurrent algorithms are designed for an arbitrary number of processus. We would like to ensure the correctness of concurrent algorithms, regardless of the number of processes involved. For this purpose, we rely on the Model Checking Modulo Theories (MCMT) framework, developed by Ghilardi and Ranise, which allows for the verification of safety properties of parameterized concurrent programs, that is to say, programs involving an arbitrary number of processes. We extend this technology with a theory for reasoning about weak memory models. The result of this work is an extension of the Cubicle model checker called Cubicle-W, which allows the verification of safety properties of parameterized transition systems running under a weak memory model similar to TSO
24
Sánchez-Soto, Eduardo. "Réseaux bayésiens dynamiques pour la vérification du locuteur." Paris, ENST, 2005. http://www.theses.fr/2005ENST0032.
Full textAbstract:
Cette thèse est concernée avec la modélisation statistique du signal de parole appliqué à la vérification du locuteur (VL) en utilisant des réseaux bayésiens (RBs). L'idée principale de ce travail est d'employer les RBs comme un outil mathématique afin de combiner plusieurs sources d'information obtenues à partir du signal de parole en gardant ses relations. Elle combine de travail théorique et expérimental. Une différence fondamentale entre les systèmes de VL et les humains est la quantité et la qualité de l'information utilisée ainsi que la relation entre les sources d'information employées pour prendre des décisions. L'identité d'un locuteur est codée dans plusieurs sources d'information qui peuvent être modélisées par des RBs. La première partie de cette thèse passe en revue les modules principaux des systèmes de VL, les sources possibles d'information aussi bien que les concepts de base des modèles graphiques. La deuxième partie de cette thèse aborde le module de modélisation du système de VL proposé. On propose une nouvelle façon d approcher les problèmes liés aux systèmes de VL. Il est décrit comment apprendre les relations d'indépendance conditionnelle parmi les variables directement à partir des données. Enfin, nous proposons une technique pour adapter les RBs basée sur certaines caractéristiques mathématiques des relations d'indépendance conditionnelles. Cette adaptation est basée sur une mesure entre les distributions de probabilité conditionnelles entre des variables discrètes, et de la même façon, sur la matrice de régression pour des variables continues. A l'issue de nos recherches, l'intérêt d'employer les RBs dans les systèmes de VL est clairement montré<br>This thesis is concerned with the statistical modeling of speech signal applied to Speaker Verification (SV) using Bayesian Networks (BNs). The main idea of this work is to use BNs as a mathematical tool to model pertinent speech features keeping its relations. It combines theoretical and experimental work. The difference between systems and humans performance in SV is the quantity of information and the relationships between the sources of information used to make decisions. A single statistical framework that keeps the conditional dependence and independence relations between those variables is difficult to attain. Therefore, the use of BNs as a tool for modeling the available information and their independence and dependence relationships is proposed. The first part of this work reviews the main modules of a SV system, the possible sources of information as well as the basic concepts of graphical models. The second part deals with Modeling. A new approach to the problems associated with the SV systems is proposed. The problem of inference and learning (parameters and structure)in BNs are presented. In order to obtain an adapted structure the relations of conditional independence among the variables are learned directly from the data. These relations are then used in order to build an adapted BN. In particular, a new model adaptation technique for BN has been proposed. This adaptation is based on a measure between Conditional Probability Distributions for discrete variables and on Regression Matrix for continuous variables used to model the relationships. In a large database for the SV task, the results have confirmed the potential of use the BNs approach
25
Kaliche, Keltoum. "Méthode des éléments finis inversés pour des domaines non bornés." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLV014.
Full textAbstract:
La méthode des éléments finis inversés est une méthode sans troncature qui a été introduite pour résoudre des équations aux dérivées partielles en domaines non bornés. L’objective de cette thèse est d’analyser, d’adapter puis d’implémenter cette méthode pour résoudre quelques problèmes issus de la physique, notamment lorsque le domaine géométrique est l’espace R3 tout entier. Dans un premier temps, nous présentons de manière détaillée les aspects et les principes fondamentaux de la méthode. Ensuite, nous adapterons la méthode à des problèmes de type div-rot et de potentiels vecteurs posés dans R3. Après avoir analysé la convergence de la méthode, on montrera quelques résultats numériques obtenus avec un code tridimensionnel. On s’intéresse ensuite au problème de calcul de l’énergie magnétostatique dans des problèmes de micromagnétisme, où on développe avec succès une approche numérique utilisant les éléments finis inversés. Dans la dernière partie, on adapte la méthode à un problème provenant de la chimie quantique (modèle de continuum polarisable) pour lequel on prouve qu’elle donne des résultats numériques très prometteurs. La thèse comporte beaucoup de résultats numériques issus de codes tridimensionnels écrits ou co-écrits, notamment lorsque le domaine est l’espace tout entier. Elle comporte aussi des résultats théoriques liés à l’utilisation des espaces de Sobolev à poids comme cadre fonctionnel. On apporte en particulier une preuve constructive de quelques inégalités de type div-rot dans des domaines non bornés<br>Inverted finite element method (IFEM) is a non runcature method which was introduced for solving partial differential equations in unbounded domains. The objective of this thesis is to analyze, to adapt and to implement IFEM for solving several problems arising in physics, especially when the domain is the whole space R3. We first give a presentation in which we detail the principles and the main features of the method. Then, we adapt IFEM for solving some div-curl systems and vector potential problems in the whole space. In a second part, we successfully develop an IFEM based approach for computing the stray-field energy in micromagnetism. In the last part, we are interested in the study of the polarizable continuum model arising in quantum chemistry. The manuscript contains a large number of numerical results obtained with some 3D codes, especially when the domain is the whole space R3. It also contains some theoretical results in relation with weighted Sobolev spaces. We give in particular a constructive proof of some div-curl inequalities in unbounded domains
26
Herbreteau, Frédéric. "Automates à file réactifs embarqués : application à la vérification de systèmes temps-réel." Nantes, 2001. http://www.theses.fr/2001NANT2090.
Full textAbstract:
Nous considérons dans notre thèse la vérification des programmes ELECTRE et des systèmes à file réactifs embarqués(SFR Embarqués). Ces formalismes permettent la modélisation des systèmes réactifs avec mémorisation, ainsi que leur environnement. L'une des propriétés étudiées est la bornitude de la file de mémorisation, indispensable pour la correction des applications vérifiées. Nous prouvons l'indécidabilité de ce problème pour une classe très large de SFR Embarqués, et en conséquence, nous proposons une méthode de test pour ce problème. Nous prouvons par ailleurs que l'accessibilité est décidable pour les Lossy SFR Embarqués, une extension classique du modèle standard. Ce résultat nous permet d'envisager la vérification de propriétés de sûreté pour les SFR Embarqués : les propriétés satisfaites pour un Lossy SFR Embarqué le sont aussi par le SFR Embarqué correspondant. Puis, nous examinons la classe des applications temps-réel pour lesquelles nous proposons le modèle des SFR Hybrides Linéaires, obtenu depuis le modèle basique par l'ajout du temps qualitatif. Le problème de la bornitude étant indécidable, nous adaptons notre test à ce nouveau contexte. Finalement, même lorsque le modèle est borné, il est souvent trop gros pour pouvoir être vérifié en pratique. Nous introduisons donc une méthode de réduction, drastique lorsqu'elle s'applique, qui préserve la majorité des propriétés de logique temporelle<br>We are concern in our thesis by the verification of ELECTRE programs and Embedded Reactive Fiffo Systems (Embedded RFS). These two formalisms allow to model asynchronous reactive systems with event memorisation, along with their environment. Particularly, we focus on the boundedness problem which is seen as a correctness criterion for reactive systems. We prove that this problem is undeciable, thus we provide a testing method as a partial solution
27
Roux, Mattias. "Extensions de l’algorithme d’atteignabilité arrière dans le cadre de la vérification de modèles modulo théories." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS582.
Full textAbstract:
Cette thèse se propose de présenter plusieurs extensions ayant été ajoutées au vérificateur de modèles Cubicle.Cubicle est un logiciel permettant de vérifier automatiquement la sûreté de systèmes paramétrés au moyen de techniques de vérification de modèles modulo théories.La première contribution apportée par cette thèse consiste en l'implémentation d'un nouvel algorithme d'atteignabilité baptisé FAR (pour Forward Abstracted Reachabilty). FAR est un algorithme faisant intervenir à la fois des techniques de l'analyse d'atteignabilité en arrière déjà implémentée dans Cubicle ainsi que des techniques d'analyse d'atteignabilité en avant.La seconde contribution est constituée de multiples ajouts inspirés de méthodes de l'intelligence artificielle afin d'améliorer la génération automatique d'invariants de Cubicle.Enfin, la dernière contribution a permis d'augmenter l'expressivité de Cubicle afin de prouver des propriétés faisant intervenir des quantificateurs universels. Cette contribution a été mise en œuvre en associant Cubicle à Why3, une plateforme de vérification déductive<br>This thesis proposes to present several extensions that have been added to the Cubicle model checker.Cubicle is a software allowing to automatically check the safety of parameterized systems using model checking modulo theory techniques.The first contribution made by this thesis consists in the implementation of a new reachability algorithm called FAR (for Forward Abstracted Reachabilty). FAR is an algorithm involving both backward reachability analysis techniques already implemented in Cubicle as well as forward reachability analysis techniques.The second contribution consists of multiple additions inspired by artificial intelligence methods to improve the automatic generation of Cubicle invariants.Finally, the last contribution has increased Cubicle's expressiveness in order to prove properties involving universal quantifiers. This contribution was implemented by associating Cubicle with Why3, a deductive verification platform
28
Bertrand, Nathalie. "Modèles stochastiques pour les pertes de messages dans les protocoles asynchrones, et techniques de vérification automatique." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2006. http://tel.archives-ouvertes.fr/tel-00132080.
Full textAbstract:
Les protocoles de communication asynchrones sont naturellement modélisés par des automates communicants via des canaux FIFO non bornés. Dans cette thèse nous nous intéressons aux variantes des Lossy Channel Systems pour lesquelles les pertes de messages dans les canaux sont probabilistes. Plus précisément, on considère des sémantiques sous forme de chaînes de Markov et de processus de décision markoviens. Un théorème général de convergence de points fixes dans les systèmes de transition bien structurés, permet de prouver pour les PLCS et NPLCS de nombreux résultats de décidabilité pour la vérification de propriétés du temps linéaire. Nous donnons également les limites des modèles par l'intermédiaire de résultats d'indécidabilité. Un prototype a fait l'objet de l'implémentation des algorithmes développés dans la thèse. Malgré la grande complexité des problèmes cet outil a permis de prouver des propriétés de vivacité sur des protocoles tels que le Bit Alterné et le protocole de Pachl.
29
Ben, Ezzine Radhouane. "Application de la méthode de vérification de modèles sur des protocoles de communication JAVA." Mémoire, Université de Sherbrooke, 2002. http://savoirs.usherbrooke.ca/handle/11143/4492.
Full textAbstract:
La vérification par exploration d'espace d'états (model-checking) est une technique efficace pour vérifier des propriétés sur des systèmes. Plusieurs outils de vérification utilisent cette technique par l'intermédiaire de spécifications exprimant le comportement des systèmes considérés. Ces spécifications représentent des modèles sur lesquels nous pouvons vérifier certaines propriétés. D'autres outils de vérification, utilisant la même technique, opèrent sur la description des systèmes en agissant directement sur le code source. Notre travail est généralement inspiré de la technique de vérification proposée par Godefroid dans son outil de vérification VERISOFT. Nous proposons l'application de cette technique sur des systèmes parallèles en agissant sur le code source décrivant ces systèmes. Pour ce faire, il faut préalablement adopter une technique permettant de construire l'espace d'états d'un système à partir de sa description dans le langage de programmation. Ensuite, nous appliquons un algorithme de recherche dans l'espace d'états permettant de vérifier certaines propriétés. Dans notre cas, les systèmes à vérifier ainsi que l'outil de vérification sont écrits dans le langage de programmation JAVA.
30
Dumitrescu, Emil. "Construction de modèles réduits et vérification symbolique de circuits industriels décrits au niveau RTL." Université Joseph Fourier (Grenoble), 2003. http://www.theses.fr/2003GRE10101.
Full text
31
Cartier-Michaud, Thomas. "Vérification de codes et réduction de modèles : Application au transport dans les plasmas turbulents." Thesis, Aix-Marseille, 2015. http://www.theses.fr/2015AIXM4020.
Full textAbstract:
L'étude numérique est un outil de recherche qui est devenu incontournable, en particulier pour la compréhension et le contrôle des systèmes complexes. La simulation des plasmas de fusion par confinement magnétique s'inscrit parfaitement dans cette démarche. Les larges rapports d'échelle en temps et espace, la nature chaotique des plasmas et les très fortes anisotropies imposent l'utilisation de méthodes numériques avancées. C'est dans ce cadre que les deux volets de ma thèse s'inscrivent.Le premier volet est l’originalité de ma thèse, la mise en place la méthode PoPe, une procédure générale de vérification de codes et réduction de modèles. Le principe de cette méthode est de déterminer les équations qui ont permis de générer un ensemble de données : si les données sont issues d'un code de simulation, retrouver ces équations et les comparer au modèle théoriquement implémenté est équivalent à vérifier le code. La précision de la procédure permet de caractériser l'erreur commise jusqu'à retrouver l'ordre des schémas numériques employés, même en régime chaotique.Le second volet de ma thèse se consacre à l’étude du transport turbulent qui détermine la performance des plasmas de fusion. L’étude du transport sous forme d’avalanches dans un modèle de bord fluide est entreprise en quantifiant l’impact du chaos sur l’auto-organisation. Pour un modèle cinétique restreint aux instabilités basse fréquence, la capacité de se bloquer dans deux régimes exclusifs, l’un isolant, l’autre conducteur, est étudiée. Ce modèle est amélioré pour permettre des relaxations entre ces deux états. Pour ces modèles fluide et cinétique, des modèles réduits obtenus avec la méthode PoPe sont proposés<br>Numerical analysis is now a key component of research, especially for the understanding and the control of complex systems. Simulations of magnetic confinement plasmas fall within this approach. One of the difficulties of this field is the wide range of spatial scales, time scales, the chaotic nature of plasmas and the strong anisotropies require advanced numerical methods. Each of the two parts of my thesis takes place in this frame of numerical simulation and fusion plasmas.The first part of my thesis is dedicated to the method PoPe, a general method for code verification and model reduction. The principle of this method is to determine the equations which have generated a set of data. If the data was produced by a simulation tool, finding these equations and comparing them to the ones theoretically implemented is equivalent to verifying this simulation tool. The accuracy of this procedure allows to characterize the numerical error and to recover the order of each numerical scheme used.The second part of my thesis deals with the study of turbulent transport which determines the efficiency of fusion plasma. The chaotic avalanches of a fluid model are studied considering the impact of the chaos on the self-organization. For a kinetic model restricted to the low frequency instabilities, the ability to block itself in two regimes, one insulating and the other conducting, is studied. Upgrades of this model are undertaken in order to introduce the possibility of relaxations between the two previous states. For both the fluid and the kinetic model, reduce models are proposed thank to the PoPe method
32
Kamsu-Foguem, Bernard. "Modélisation et vérification des propriétés de systèmes complexes : Application aux processus d'entreprise." Montpellier 2, 2004. http://www.theses.fr/2004MON20050.
Full text
33
Finot, Olivier. "Oracles du test de transformations de modèles." Nantes, 2014. http://archive.bu.univ-nantes.fr/pollux/show.action?id=2069ea58-6610-4161-8bef-5c993ad30652.
Full textAbstract:
L’Ingénierie Dirigée par les Modèles place les modèles au coeur du cycle de développement logiciel. Ces modèles évoluent par le biais de diverses transformations. Dans cette thèse nous nous sommes intéressés à la validation de ces transformations de modèles par le test, et en particulier à l’oracle de ce test. Nous proposons deux approches pour assister le testeur dans la création de ces oracles. Tout d’abord, nous offrons une assistance passive en fournissant au testeur une nouvelle fonction d’oracle. Cette dernière lui permet de créer des oracles qui ne contrôlent qu’une partie des modèles obtenus. Nous avons défini la notion de verdict partiel, explicité les situations où un verdict partiel est plus avantageux et proposé un protocole global du test de transformations dans ce contexte. Nous avons mis en oeuvre cette première proposition dans un outillage avec lequel nous l’avons expérimentée. Ensuite, nous offrons au testeur une assistance active en étudiant la qualité d’un ensemble d’oracles. Nous considérons la qualité d’un ensemble d’oracles selon sa capacité à détecter des fautes dans la transformation sous test. Nous proposons une méthode qui corrige en partie les insuffisances de l’analyse de mutation, utilisée dans ce contexte ; nous mesurons la couverture du méta-modèle de sortie par l’ensemble d’oracles considéré. Nous montrons que notre approche est indépendante du langage utilisé pour la mise en oeuvre de la transformation sous test, et fournit au testeur des informations pour l’amélioration des oracles. Nous avons défini une démarche pour mesurer la couverture et qualifier des oracles. Nous avons développé un outil pour expérimenter et valider notre proposition<br>With Model Driven Engineering models are the heart of software development. These models evolve through transformations. In this thesis our interest was the validation for these model transformations by testing, and more precisely the test oracles. We propose two approaches to assist the tester to create these oracles. With the first approach this assistance is passive; we provide the tester with a new oracle function. The test oracles created with this new oracle function control only part of the model produced by the transformation under test. We defined the notion of partial verdict, described the situations where having a partial verdict is beneficial for the tester and how to test a transformation in this context. We developed a tool implementing this proposal, and ran experiments with it. With the second approach, we provide a more active assistance about test oracles’ quality. We study the quality of a set of model transformation test oracles. We consider that the quality of a set of oracles is linked to its ability to detect faults in the transformation under test. We show the limits of mutation analysis which is used for this purpose, then we propose a new approach that corrects part of these drawbacks. We measure the coverage of the output meta-model by the set of oracles we consider. Our approach does not depend on the language used for the transformation under test’s implementation. It also provides the tester with hints on how to improve her oracles. We defined a process to evaluate meta-model coverage and qualify test oracles. We developed a tool implementing our approach to validate it through experimentations
34
Hymans, Charles. "Vérification de composants VHDL par interprétation abstraite." Palaiseau, Ecole polytechnique, 2004. https://pastel.archives-ouvertes.fr/pastel-00000875.
Full text
35
Sangnier, Arnaud. "Vérification de systèmes avec compteurs et pointeurs." Cachan, Ecole normale supérieure, 2008. http://www.theses.fr/2008DENS0051.
Full textAbstract:
Au cours des dernières années, les méthodes formelles se sont avérées être une approche prometteuse pour garantir que le comportement d’un système informatique respecte une spécification donnée. Parmi les différentes techniques développées, le model-checking a été récemment étudié et appliqué avec succès à un grand nombre de modèles comme les systèmes à compteurs, les automates communicants (avec perte), les automates à pile, les automates temporisés, etc. Dans cette thèse, nous considérons deux modèles particuliers dans l’objectif de vérifier des programmes manipulant des variables entières et des variables de pointeurs. Dans une première partie, nous nous intéressons aux systèmes à compteurs. Nous commençons par définir ce modèle ainsi que ses différentes restrictions. Nous introduisons ensuite une sous-classe de systèmes à compteurs, appelée les machines à compteurs reversal-bornées, pour lesquelles de nombreux problèmes d’accessibilité sont décidables. Nous montrons que cette classe peut être étendue tout en gardant les résultats de décidabilité et nous prouvons qu’il est possible de décider si un Système d’Addition de Vecteurs avec États est reversal-borné, alors que cela n’est pas possible si l’on considère les systèmes à compteurs dans leur généralité. Nous finissons cette partie sur les systèmes à compteurs par l’étude de problèmes de model-checking de logiques temporelles. Les logiques temporelles que nous prenons en compte permettent de parler des données manipulées par le système. En particulier, nous montrons que le model-checking d’automates à un compteur déterministes avec des formules de la logique LTL avec registres est décidable, mais que cela n’est plus vrai lorsque l’hypothèse sur le déterminisme est supprimée. Dans une deuxième partie, nous introduisons le modèle des systèmes à pointeurs, qui est utilisé pour représenter des programmes manipulant des listes simplement chaînées. Nous donnons un algorithme qui traduit tout système à pointeurs en un système à compteurs qui lui est bisimilaire. Ceci nous permet de réutiliser les méthodes existantes pour l’analyse de systèmes à compteurs pour vérifier des programmes avec listes. Nous présentons ensuite une extension de la logique CTL* pour vérifier des propriétés temporelles sur de tels programmes, et nous étudions la décidabilité du problème de model-checking pour cette nouvelle logique. Finalement, dans une dernière partie, nous donnons une description de l’outil TOPICS (Translation of Programs Into Counter Systems) qui traduit un programme écrit dans un fragment syntaxique du langage C en un système à compteurs<br>In the past years, formal methods have shown to be a succesfull approach to ensure that the behavior of an informatic system will respect some properties. Among the different existing techniques, model-checking have been recently studied and successfully applied to a lot of models like counter systems, lossy channel systems, pushdown automata, timed automata, etc. In this thesis, we consider two different models to verify programs which manipulate integer variables and pointer variables. In a first part, we deal with counter systems. We define the model and the different restrictions which have been proposed. We then introduce a restricted class of counter systems, called the reversal-bounded counter machines, for which many reachability problems are decidable. We show that this class can be extended keeping the decidability results and we prove that we can decide whether a Vector Addition System with States is reversal-bounded or not, which is not possible for general counter systems. We then study the problem of model-checking counter systems with different temporal logics. The temporal logics we consider allow to speak about the data manipulated by the system. In particular, we show that the model-checking of deterministic one-counter automata with formulae of LTL with registers is decidable, and becomes undecidable when considering non deterministic one-counter automata and two counter automata. In a second part, we introduce the model of pointer systems, which is used to represent programs manipulating single linked lists. We propose an algorithm to translate any pointer system into a bisimilar counter system. This allows us to reuse existing techniques over counter systems to analyze these programs. We then propose an extension of CTL* to verify temporal properties for such programs, and we study the decidability of the model-checking problem for this new logic. Finally we present the tool TOPICS (Translation of Programs Into Counter Systems) which translates a C-like program with pointers and integer variables into a counter system
36
Sbihi, Mohammed. "Analyse spectrale de modèles neutroniques." Phd thesis, Université de Franche-Comté, 2005. http://tel.archives-ouvertes.fr/tel-00011072.
Full textAbstract:
Cette thèse porte principalement sur l'étude spectrale de divers modèles neutroniques. Elle consiste en trois parties complémentaires. La première partie est consacrée aux problèmes d'applications spectrales dans les domaines non bornés, où faute de compacité les méthodes usuelles n'opèrent plus. A l'aide d'arguments d'analyse fonctionnelle sur le spectre critique des semigroupes perturbés nous cernons une large classe de paramètres liés à l'équation pour lesquels le théorème d'application spectrale a lieu. Dans la deuxième partie, nous apportons une nouvelle approche, dite résolvante, de la stabilité des spectres essentiel et critique des semigroupes perturbés dans les espaces de Hilbert. En neutronique, par le biais de cette approche, nous retrouvons des résultats classiques de stabilité de spectre essentiel dans les domaines bornés et nous améliorons certains résultats de la première partie dans les domaines non bornés. La troisième partie traite d'un modèle de collision partiellement élastique introduit par E.W. Larsen et P.F. Zweifel. Afin de dégager le comportement asymptotique en temps grands du semigroupe gouvernant ce modèle nous ferons sa théorie spectrale. Nous étudions les propriétés de compacité à la base de cette théorie, ce qui nous permettra notamment d'obtenir des résultats de stabilité du type essentiel. Nous examinons ensuite les incidences de la positivité : irréductibilité, propriétés de monotonie stricte de la valeur propre principale, réalité du spectre périphérique
37
Benmerzoug, Djamel. "Modèles et outils formels pour l'intégration d'applications d'entreprises." Paris 6, 2009. http://www.theses.fr/2009PA066344.
Full textAbstract:
L'intégration d'applications dépeint les interactions dans lesquelles les processus engagés participent afin d'atteindre un objectif commun, ainsi que les dépendances entre les interactions. En conséquence, cette thèse concerne l'intégration des applications par les processus à l'aide des systèmes multi-agents dits communiquants, c'est-à-dire dont les agents interagissent par l'envoi de messages, en utilisant un langage de communication de haut niveau. Dans ce travail de recherche, nous proposons un cadre conceptuel et une démarche méthodologique couvrant les principales phases pour la modélisation de l'intégration d'applications basée sur les protocoles d'interaction. Cette démarche est basée conjointement sur l'utilisation de la notation AUML, et aussi sur le langage BPEL4WS. Nous définissons par la suite un guide permettant de passer à partir de descriptions semi-formelles des protocoles d'interaction, vers des spécifications formelles de réseaux de Petri colorés (RdPC) tout en mettant l'accent sur le contrôle et la dynamicité des interactions. Le modèle de RdPC permet de couvrir les aspects de modélisation et de validation des protocoles.
38
Dragomir, Iulia. "Conception et vérification d'exigences de sûreté temporisées à base de contrats dans les modèles SysML." Toulouse 3, 2014. http://thesesups.ups-tlse.fr/2510/.
Full textAbstract:
De nos jours, les systèmes informatiques croissent en taille et en complexité. Intégrés dans des dispositifs de différents domaines tels que l'avionique, l'aéronautique, l'électronique grand public, etc. , ils sont souvent considérés comme critiques à l'égard de la vie humaine, des coûts et de l'environnement. Concevoir des systèmes embarqués temps-réel critiques sûrs et fiables est une tâche difficile, étant donné que leurs modèles sont souvent source d'erreurs. Une façon pour les concepteurs de contourner cette difficulté consiste à s'appuyer sur la modélisation compositionnelle de composants logiciels pilotée par les exigences. Le raisonnement à base de contrats permet de construire des composants sûrs à partir des exigences globales du système en interposant des spécifications abstraites et partielles entre les besoins du système et les composants eux-mêmes. Informellement, un contrat modélise le comportement abstrait d'un composant du point de vue de l'exigence à satisfaire (c. A. D garantie) dans un contexte donné (c. A. D. Hypothèse). Les contrats peuvent être exploités pour décomposer et tracer les exigences au cours d'un développement itératif, mais aussi pour effectuer une vérification compositionnelle de la satisfaction des exigences. Dans cette thèse, nous présentons une méthodologie de raisonnement à base de contrats pour la conception et la vérification de systèmes sûrs développés en SysML. Ainsi, nous définissons en UML/SysML la syntaxe des contrats et des relations de raffinement entre contrats et/ou composants qui sont utilisées pour prouver la correction du système par rapport aux exigences. Ensuite, nous proposons un cadre formel qui modélise la sémantique d'un modèle UML/SysML étendu par des contrats selon une variante d'automates temporisés entrée/sortie et nous définissons la correspondance entre ces concepts. Nous formalisons les relations de raffinement par la relation d'inclusion de traces et nous prouvons leurs propriétés compositionnelles ce qui assure la correction de la méthodologie. L'approche est instanciée pour le profil OMEGA et la boîte à outils IFx2 qui génère partiellement les obligations de preuve. Finalement, plusieurs études de cas dont une issue de l'industrie complètent la théorie pour évaluer l'approche à base de contrats et ses résultats et les comparer aux méthodes classiques de model-checking<br>Nowadays computer systems grow larger in size and more complex. Embedded in devices from different domains like avionics, aeronautics, consumer electronics, etc. , they are often considered critical with respect to human life, costs and environment. A development that results in safe and reliable critical real-time embedded systems is a challenging task, considering that errors are accidentally inserted in the design. A way for system designers to tackle this issue is to use a compositional design technique based on components and driven by requirements: it allows to infer from global requirements, component properties that must locally hold. Contract-based reasoning allows to compositionally derive correct components from global system requirements by interposing abstract and partial specifications for components. Informally, a contract models the abstract behavior a component exhibits from the point of view of the requirement to be satisfied (i. E. Guarantee) in a given context (i. E. Assumption). Contracts can be used to decompose and trace requirements during iterative design, but also to perform compositional verification of requirement satisfaction. In this thesis, we present a methodology for reasoning with contracts during system design and verification within SysML. Thus, we define the syntax for contracts in UML/SysML, as well as a set of refinement relations between contracts and/or components in order to prove the system's correctness with respect to requirements. Next, we provide a formal framework that models the semantics of a UML/SysML model extended with contracts as a mapping of the language concepts to a variant of Timed Input/Output Automata. The refinement relations are formalized based on the trace inclusion relation and compositional properties are proved to hold which ensures the soundness of the methodology. The approach is instantiated for the OMEGA Profile and IFx2 toolset with partial automatic generation of proof obligations. Finally, the approach is applied on several case studies, including an industry-grade system model, which show its efficiency by comparative verification results
39
Rasse, Alban. "Une Approche Orientée Modèles pour la Spécification, la Vérification et l’Implantation des Systèmes Logiciels Critiques." Mulhouse, 2006. https://www.learning-center.uha.fr/opac/resource/une-approche-orientee-modeles-pour-la-specification-la-verification-et-limplantation-des-systemes-lo/BUS3944436.
Full textAbstract:
La conception des applications logicielles est une tâche délicate qui requiert la prise en compte d'un ensemble d’aspects (concurrence, communication, comportement hybride,…) et l’intégration d’un ensemble d’activités particulières. Le travail présenté dans ce manuscrit, tire partie de l'Ingénierie Dirigée par les Modèles (IDM), d'UML, des méthodes formelles, des systèmes multi-agents et des frameworks afin de proposer un processus de conception intégrant des aspects de spécification, de vérification et d'implantation. Il se fonde sur la réalisation de trois modèles adaptés à chacune de ces activités : le modèle de spécification, le modèle de vérification et le modèle d'implantation (Figure 1). Dans ce contexte, l’Ingénierie Dirigée par les Modèles offre les concepts (métamodélisation et transformations de modèles) nécessaires à l’intégration et à la manipulation de ces trois modèles au sein de l'approche proposée. En outre, les transformations de modèles permettent de réaliser la projection d'un modèle source vers différents domaines afin de profiter de leurs avantages respectifs; à partir du modèle de spécification, il est alors possible d'obtenir les modèles de vérification et d'implantation. Le modèle de spécification permet de représenter une abstraction des systèmes logiciels réactifs concurrents ; il est décrit à l’aide d’un Langage Spécifique de Domaine (ou DSL) inspiré des ADL et des diagrammes de composants d’UML 2. 0. Il repose sur l'utilisation d'agents concurrents, qui communiquent à l'aide d'actions partagées et d'objets partagés ; leur comportement est conforme à une sémantique d’exécution hybride (événementiel asynchrone et continu synchrone). Le modèle de vérification permet au concepteur d’utiliser des méthodes et des techniques de vérification qui garantissent que le modèle obtenu durant la phase de spécification est conforme au comportement souhaité. En effet, dans le cas de systèmes critiques, les aspects de vivacité et de sûreté de fonctionnement sont primordiaux. Pour garantir ces aspects, nous proposons de recourir à des spécifications formelles et à des techniques formelles de vérification en modélisant le modèle de vérification à l’aide d’une algèbre de processus nommée Finite State Processes (ou FSP) pouvant être exploitée par l'outil de model-checking LTSA. Le modèle d’implantation est exprimé à l'aide de classes et de configurations d’objets; il repose sur l’utilisation d’un framework Java qui fournit un ensemble de concepts et une sémantique d’exécution proches de ceux utilisés dans le modèle de spécification. Ce faisant il permet de réduire l’écart sémantique entre la réalisation et la conception précédemment vérifiée.
40
Constant, Camille. "Génération automatique de tests pour modèles avec variables ou récursivité." Rennes 1, 2008. ftp://ftp.irisa.fr/techreports/theses/2008/constant.pdf.
Full textAbstract:
Nous nous intéressons dans ce document à la génération automatique de tests de conformité pour des implémentations réactives. Nous nous attachons dans un premier temps à étendre la méthode de génération de tests, basée sur la théorie du test de conformité à la ioco, en reliant trois niveaux de description (propriétés, spécification et implémentation). Nous combinons pour cela vérification formelle et test de conformité. Nous obtenons ainsi, lors de l'exécution du cas de test sur l'implémentation, des verdicts pouvant indiquer la non-conformité de l'implémentation, mais également la satisfaction/violation de la propriété par l'implémentation et/ou la spécification. Nous étendons dans un deuxième temps la génération de tests par l'expressivité du modèle de spécification en nous intéressant aux spécifications interprocédurales récursives. Notre méthode est basée sur une analyse exacte de co-accessibilité permettant de décider si et comment un objectif de test pourra être atteint. Cependant, l'incapacité des cas de test récursifs à connaître leur propre pile d'exécution ne permet pas d'utiliser la totalité des résultats de l'analyse. Nous discutons de ce problème d'observation partielle et de ses conséquences puis nous proposons un moyen de minimiser son impact. Enfin, nous expérimentons ces méthodes de génération de tests sur quelques exemples et une étude de cas<br>This thesis adresses the problem of automatic test case generation for testing the conformance of a reactive implementation. We first propose a methodology which extends the testing theory based on the ioco conformance relation by distinguishing three levels of description: properties, specification and implementation. The methogology integrates verification and conformance testing. The execution of the generated test cases on the implementation allows detecting conformance violations between implementation and specification, but also violation/satisfaction of the properties by the implementation or the specification. Secondly, we introduce a more expressive specification model: recursive interprocedural specifications. The test generation method we propose is based on coreachability analysis, which allows deciding whether and how the test purpose can still be satisfied. However, although it is possible to carry out an exact analysis, the inability of test cases to inspect their own stack prevents them from fully using the coreachability information. We discuss this partial observation problem, its consequences, and how to minimise its impact. Finally, we experiment these methods of test generation on several examples and a case study
41
Gascard, Eric. "Méthodes pour la vérification formelle de systèmes matériels et logiciels à architecture régulière." Aix-Marseille 1, 2002. http://www.theses.fr/2002AIX11047.
Full textAbstract:
Le cadre de cette thèse est l'utilisation des méthodes formelles pour la spécification et la validation de systèmes matériels et logiciels. Nos travaux se sont concentrés sur la validation formelle de systèmes à architecture régulière et paramétrable, circuits combinatoires itératifs d'une part, et applications distribuées s'exécutant sur des réseaux d'interconnexion symétriques d'autre part. La première partie de cette thèse est consacrée à la vérification formelle automatique de circuits à structure répétitive régulière. Un modèle de fonctions récursives est utilisé, le processus de preuve mettant en jeu des techniques inductives permet un raisonnement générique sur la taille du circuit. Le résultat présenté ici est une heuristique de généralisation de théorèmes inductifs spécialisée pour les modèles fonctionnels considérés. Cette méthode permet de produire les théorèmes généralisés ainsi que certains lemmes intermédiaires et d'automatiser ainsi le processus de vérification. La seconde partie propose une méthode de modélisation et de validation de programmes distribués sur les réseaux d'interconnexion symétriques. Les preuves sont ici paramétrées sur l'ordre du réseau (nombre de processeurs). Le modèle formel choisi pour la représentation des réseaux dans l'environnement de démonstration automatique est basé sur le concept de graphe de Cayley. Notre méthode prend en compte les opérations de communications collectives (diffusion, distribution, réduction) utilisées par les applications distribuées. La modélisation et la méthode de preuve développées permettent entre autres de s'abstraire du problème des communications point à point, et de raisonner au niveau du processeur. De plus, elle permet d'obtenir automatiquement les invariants nécessaires au preuves.
42
Magnier, Nicolas. "Validation des transactions dans les bases de données : classes décidables et vérification automatique." Bordeaux 1, 1998. http://www.theses.fr/1998BOR10506.
Full textAbstract:
Dans cette these, on introduit un modele de donnees relationnel pour etudier le probleme de valider des transactions. Dans notre contexte, valider une transaction c'est demontrer qu'elle preserve la coherence par rapport a une specification statique, et au premier ordre, de l'integrite des bases de donnees. Nous avons defini et implante un systeme, base sur une extension de la construction de plus faible precondition, pour valider des transactions de ce modele de facon automatique. La principale originalite de ce modele reside dans son langage de transactions. Il permet en effet d'exprimer des mises a jours de domaine de bases de donnees. En plus de leur interet pour definir simplement les transformations de graphes, nous avons montre qu'elles permettent d'exprimer simplement des creations ou des suppressions d'objets dans des modeles semantiques. L'autre contribution de ce travail est la mise en evidence de quatre nouvelles classes decidables du probleme de preservation dans le cadre de notre modele relationnel. Aucune de ces classes n'est incluse dans l'une des autres. En particulier, une de ces classes generalise la classe mise en evidence par abiteboul et vianu. De plus, nous avons montre que la presence de transactions qui peuvent modifier le domaine affecte peu la decidabilite du probleme. En effet, toutes les classes que nous avons etablies contiennent ce type de transactions. De plus, on montre que notre systeme de validation experimental decide (en particulier) toutes ces classes. Cette propriete est un atout majeur par rapport aux systemes existants. En effet, dans les systemes proposes, aucune caracterisation de ce type n'est etablie.
43
Ait-Cheik-Bihi, Wafaa, and Wafaa Ait-Cheik-Bihi. "Approche orientée modèles pour la vérification et l'évaluation de performances de l'interopérabilité et l'interaction des services." Phd thesis, Université de Technologie de Belfort-Montbeliard, 2012. http://tel.archives-ouvertes.fr/tel-00720657.
Full textAbstract:
De nos jours, les services Web sont très utilisés notamment par les entreprises pour rendre accessibles leurs métiers, leurs données et leurs savoir-faire via le Web. L'émergence des services Web a permis aux applications d'être présentées comme un ensemble de services métiers bien structurés et correctement décrits, plutôt que comme un ensemble d'objets et de méthodes. La composition automatique de services est une tâche complexe mais qui rend les services interopérables, ainsi leur interaction permet d'offrir une valeur ajoutée dans le traitement des requêtes des utilisateurs en prenant en compte des critères fonctionnels et non fonctionnels de la qualité de service. Dans ce travail de thèse, nous nous intéressons plus précisément aux services à base de localisation (LBS) qui permettent d'intégrer des informations géographiques, et de fournir des informations accessibles depuis des appareils mobiles via, les réseaux mobiles en faisant usage des positions géographiques de ces appareils. L'objectif de ce travail est de proposer une approche orientée modèles pour spécifier, valider et mettre en œuvre des processus de composition automatique de services à des fins de sécurité routière dans les transports. Cette approche est basée sur deux outils formels à savoir les Réseaux de Petri (RdP) et l'algèbre (max,+). Pour cela, nous préconisons l'utilisation des workflow patterns dans la composition, où chaque pattern est traduit par un modèle RdP et ensuite par une équation mathématique dans l'algèbre (max,+). Les modèles formels développés ont conduits, d'une part, à la description graphique et analytique des processus considérés, et d'autre part, à l'évaluation et la vérification quantitatives et qualitatives de ces processus. Une plateforme, appelée TransportML, pour la collaboration et l'interopérabilité de services à base de positionnement a été implémentée. Les résultats obtenus par la simulation des modèles formels sont comparés à ceux issus des simulations du fonctionnement de la plateforme et des expérimentations sur le terrain.Cette thèse est effectuée dans le cadre des projets Européens FP7 ASSET (2008-2011) et TeleFOT (2008-2012).
44
Santos, Laurent. "Contribution à la validation et à la vérification des modèles conceptuels d'expertise : application au projet SACHEM." Aix-Marseille 3, 1998. http://www.theses.fr/1998AIX30102.
Full textAbstract:
L'evolution de la technologie et l'apparition des premiers ordinateurs ont fait germer dans l'esprit des scientifiques l'idee que la machine pourrait un jour posseder une caracteristique propre a l'homme : l'intelligence. Afin de modeliser les processus de raisonnement porteur de cette <single high-reversed-9 quotation mark>intelligence<right single quotation mark>, la communaute i. A a developpe plusieurs methodologie d'acquisition et de structuration de la connaissance organisee au sein de modeles conceptuels d'expertise premier pas dans la conception des systemes a base de connaissances (sbc). Les industriels qui ont utilise ces methodologies dans des cas concrets ont montre qu'une meilleure comprehension des processus de raisonnement apportee par la classification de la connaissance ne suffisait pas a construire des sbc robustes et sans erreurs. En effet, la phase d'implementation etait difficile et generatrice d'erreurs de codage a cause de l'imprecision dans la description des modeles du systeme. Pour palier ces inconvenients, nous proposons une approche basee sur l'operationnalisation des modeles conceptuels d'expertise (mce). L'operationnalisation permet l'obtention d'un modele operationnel (executable) a partir du mce permettant ainsi la simulation de la dynamique des processus de raisonnement avant la phase de codage. Le modele operationnel que nous avons developpe repose sur le formalisme des reseaux de petri hierarchiques, interpretes et temporels. Ce dernier permet la detection des incoherences, ambiguites et incompletudes des modeles des processus de raisonnement. Nous avons conclus nos travaux en appliquant nos developpements theoriques au cas concret du systeme d'aide a la conduite en temps reel des hauts-fourneaux du groupe usinor concu par sollac : sachem.
45
Muroor, Nadumane Ajay Krishna. "Modèles et vérification pour la composition et la reconfiguration d'applications basées sur le web des objets." Thesis, Université Grenoble Alpes, 2020. http://www.theses.fr/2020GRALM067.
Full textAbstract:
Les applications de l'Internet des objets (IoT) sont construites en interconnectant les objets du quotidien en réseau. Les objets connectés collaborent ensemble, afin d'observer l'environnement les entourant, et agir sur celui-ci. Pour le grand public, l'un des moyens de créer des applications IoT consiste à combiner différents objets à l'aide de règles d'action conditionnelle (ECA). Ces règles se présentent généralement sous la forme « SI quelque chose se produit, ALORS faire quelque chose ». Le web des objets (Web of Things ou WoT) est un ensemble de normes et de principes qui intègrent les capacités du web et les styles architecturaux à l'IoT. Bien que l'architecture WoT associée aux règles de la ECA simplifie dans une large mesure la construction d'applications IoT, il reste des défis à relever afin que les utilisateurs finaux puissent développer aisément des applications avancées et correctes, en raison de la nature dynamique, réactive et hétérogène des systèmes IoT.L'objectif général de ce travail est de tirer parti des méthodes formelles pour fournir un certain niveau de garantie aux utilisateurs finaux des applications IoT. Cela permet, au moment de la conception, d'assurer que l'application conçue se comportera comme prévu lorsque celle-ci sera déployée. Dans ce contexte, nous proposons un cadre de développement formel basé sur le WoT. Les objets sont décrits à l'aide d'un modèle dérivé de la spécification Thing Description du WoT. Ensuite, les applications sont conçues non seulement en spécifiant les règles individuelles ECA, mais aussi en associant ces règles à l'aide d'un langage de composition. Ce langage permet aux utilisateurs de construire des scénarios d'automatisation plus expressifs. La description des objets et leur composition sont traduites dans une spécification formelle à partir de laquelle le comportement complet de l'application est identifié. Afin de garantir une conception correcte de l'application avant le déploiement, cette thèse propose de valider un ensemble de propriétés génériques et spécifiques sur le comportement complet de l'application. En outre, les applications déployées peuvent être reconfigurées au cours de leur cycle de vie. Le travail supporte la reconfiguration en spécifiant des propriétés de reconfiguration qui permettent de comparer qualitativement le comportement de la nouvelle configuration avec la configuration d'origine. La mise en œuvre de toutes les propositions est réalisée en étendant la plate-forme Mozilla WebThings. Un nouvel ensemble d'interfaces utilisateur est construit pour prendre en charge la composition des règles et la reconfiguration de l’application. Un composant permettant de transformer automatiquement les modèles WoT en modèles formels, pleinement intégré au sein d’une boite à outils de vérification formelle a été développé. Enfin, un moteur de déploiement est construit en étendant les API de WebThings. Il dirige le déploiement des applications et des reconfigurations en respectant la sémantique de leur composition<br>The Internet of Things (IoT) applications are built by interconnecting everyday objects over a network. These objects or devices sense the environment around them, and their network capabilities allow them to communicate with other objects to perform utilitarian tasks. One of the popular ways to build IoT applications in the consumer domain is by combining different objects using Event-Condition-Action (ECA) rules. These rules are typically in the form of IF something-happens THEN do-something. The Web of Things (WoT) are a set of standards and principles that integrate architectural styles and capabilities of web to the IoT. Even though WoT architecture coupled with ECA rules simplifies the building of IoT applications to a large extent, there are still challenges in making end-users develop advanced applications in a simple yet correct fashion due to dynamic, reactive and heterogeneous nature of IoT systems.The broad objective of this work is to leverage formal methods to provide end-users of IoT applications certain level of guarantee at design time that the designed application will behave as intended upon deployment. In this context, we propose a formal development framework based on the WoT. The objects are described using a behavioural model derived from the Thing Description specification of WoT. Then, the applications are designed not only by specifying individual ECA rules, but also by composing these rules using a composition language. The language enables users to build more expressive automation scenarios. The description of the objects and their composition are encoded in a formal specification from which the complete behaviour of the application is identified. In order to guarantee correct design of the application, this work proposes a set of generic and application-specific properties that can be validated on the complete behaviour before deployment. Further, the deployed applications may be reconfigured during their application lifecycle. The work supports reconfiguration by specifying reconfiguration properties that allow one to qualitatively compare the behaviour of the new configuration with the original configuration. The implementation of all the proposals is achieved by extending Mozilla WebThings platform. A new set of user interfaces are built to support the composition of rules and reconfiguration. A model transformation component which transforms WoT models to formal models and an integration with formal verification toolbox are implemented to enable automation. Finally, a deployment engine is built by extending WebThings APIs. It directs the deployment of applications and reconfigurations respecting their composition semantics
46
Ait-Cheik-Bihi, Wafaa. "Approche orientée modèles pour la vérification et l'évaluation de performances de l'interopérabilité et l'interaction des services." Thesis, Belfort-Montbéliard, 2012. http://www.theses.fr/2012BELF0182/document.
Full textAbstract:
De nos jours, les services Web sont très utilisés notamment par les entreprises pour rendre accessibles leurs métiers, leurs données et leurs savoir-faire via le Web. L'émergence des services Web a permis aux applications d'être présentées comme un ensemble de services métiers bien structurés et correctement décrits, plutôt que comme un ensemble d'objets et de méthodes. La composition automatique de services est une tâche complexe mais qui rend les services interopérables, ainsi leur interaction permet d’offrir une valeur ajoutée dans le traitement des requêtes des utilisateurs en prenant en compte des critères fonctionnels et non fonctionnels de la qualité de service. Dans ce travail de thèse, nous nous intéressons plus précisément aux services à base de localisation (LBS) qui permettent d'intégrer des informations géographiques, et de fournir des informations accessibles depuis des appareils mobiles via, les réseaux mobiles en faisant usage des positions géographiques de ces appareils. L'objectif de ce travail est de proposer une approche orientée modèles pour spécifier, valider et mettre en œuvre des processus de composition automatique de services à des fins de sécurité routière dans les transports. Cette approche est basée sur deux outils formels à savoir les Réseaux de Petri (RdP) et l'algèbre (max,+). Pour cela, nous préconisons l'utilisation des workflow patterns dans la composition, où chaque pattern est traduit par un modèle RdP et ensuite par une équation mathématique dans l'algèbre (max,+). Les modèles formels développés ont conduits, d'une part, à la description graphique et analytique des processus considérés, et d'autre part, à l'évaluation et la vérification quantitatives et qualitatives de ces processus. Une plateforme, appelée TransportML, pour la collaboration et l'interopérabilité de services à base de positionnement a été implémentée. Les résultats obtenus par la simulation des modèles formels sont comparés à ceux issus des simulations du fonctionnement de la plateforme et des expérimentations sur le terrain.Cette thèse est effectuée dans le cadre des projets Européens FP7 ASSET (2008-2011) et TeleFOT (2008-2012)<br>Web services are widely used by organizations to share their knowledge over the network and facilitate business-to-business collaboration. The emergence of Web services enabled applications to be presented as a set of business services well structured and correctly described. However, combining Web services and making them interoperable, to satisfy user requests taking into account functional and non-functional quality criteria, is a complex process. In this work, we focus specifically on location-based services (LBS) that integrate geographic information and provide information reachable from mobile devices, through wireless network by making use of the geographical positions of the devices. The aim of this work is to develop a model driven approach to specify, validate and implement service composition process in an automatic fashion for road security. This approach is based on two formal tools namely Petri nets (PN) and (max, +) algebra used to model, to verify and to evaluate the performance of service composition process. Workflow patterns are used to represent service composition processes. The behavior of each pattern is modeled by a PN model and then by a (max,+) state equation. The developed formal models allow the graphical and analytical description of the considered processes. Also, these models enable to evaluate some quantitative and qualitative properties of the considered processes. A platform, called TransportML, has been developed for collaboration and interoperability of different LBS. The obtained simulation results from the formal models are compared, on one hand, to those obtained from trials of the platform, and on the other hand, to those obtained from the real experimentations on the field.This work is a part of the FP7 European projects ASSET (2008-2011) and TeleFOT (2008-2012)
47
Boulifa, Rabea. "Génération de modèles comportemementaux des applications des applications réparties." Phd thesis, Université de Nice Sophia-Antipolis, 2004. http://tel.archives-ouvertes.fr/tel-00008927.
Full textAbstract:
Dans notre travail nous nous sommes intéressés à la vérification<br /> automatique de propriétés comportementales d'applications réparties par des<br /> méthodes fondées sur les<br />modèles. En particulier, nous étudions le problème de<br />génération de modèles <br />à partir de programmes Java répartis et représentés par des systèmes de transitions<br />communiquants.<br /><br />Pour ce faire, nous définissons une sémantique comportementale de programmes ProActive, une<br />librairie Java pour la programmation parallèle, distribuée et<br />concurrente. À partir de cette sémantique nous construisons des modèles<br />comportementaux pour<br />des abstractions finies d'applications écrites dans ce langage. Ces<br />modèles sont basés sur la sémantique des algèbres de<br />processus et peuvent donc être construits de manière compositionnelle et<br />hiérarchique.<br />La construction de modèles finis n'est pas toujours possible. Pour<br />pouvoir traiter des problèmes prenant en compte des données, ainsi que<br />des problèmes concernant des topologies non bornées d'objets<br />répartis, nous définissons une nouvelle notion de modèleles<br />hiérarchiques, à base de systèmes de transitions paramétrés et de<br />réseau de synchronisation paramétrés. Moyennant des abstractions ces modèles permettent de<br />spécifier des applications possiblement infinies par des représentations<br />expressives, finies, et plus proche de la structure du code. <br />Par ailleurs, nous définissons un système de règles sémantiques<br />permettant de générer automatiquement ces modèles (finis ou<br />paramétrés) à partir d'une forme intermédiaire, obtenue par analyse statique,<br />des programmes analysés.<br />Les modèles ainsi générés sont exploitables directement ou après<br />instantiation par des outils de vérification.
48
El, Baida Rami. "Les composants logiciels réutilisables : méthode de vérification." Toulouse 3, 2004. http://www.theses.fr/2004TOU30066.
Full textAbstract:
La programmation orientée objet est de plus en plus utilisée dans le développement des systèmes complexes. Une des caractéristiques principales de ce type de programmation est de favoriser la réutilisation. Quelques échecs retentissants (comme la panne du réseau téléphonique aux États-Unis en 1989) ont prouvé la nécessité de vérifier ce type de systèmes. Plusieurs méthodes de vérifications existent, comme la vérification par preuves et la vérification par modèles (ou model-checking). Dans cette thèse, nous présentons un langage de modélisation pour les systèmes à objets concurrents ainsi que la logique temporelle associée (TLCO). Les deux types de vérification sont ensuite abordés. D'abord, la vérification par preuve est effectuée en VSE (Visual Support Environment). Ensuite, la vérification automatique est effectuée en SPIN. Finallement, une méthode des tableaux permettant la vérification des formules de TLCO est aussi présentée<br>The object oriented programming is more and more used in the development of complex systems. One of the principal characteristics of this type of programming is to favor the reusability. Some resounding failures (like the breakdown of the telephone network in the United-States of America in 1989) proved the necessity of the verification phase for such type of systems. Several verification's methods exist, like the verification by proof and the model-checking. In this thesis, we present a modeling language for the concurrent object systems as well as the associated temporal logic (temporal logic for concurrent object or TLCO). The two types of verification are then approached. First, the verification by proof is carried out in VSE (Visual Support Environment). Afterwards, the automatic checking is carried out in the model checker of SPIN. Finally, a tableau method allowing the verification of TLCO's formulas is presented
49
Aït-Sadoune, Idir. "Modélisation et vérification formelles de compositions de services." Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2010. http://www.theses.fr/2010ESMA0016.
Full textAbstract:
La possibilité de composer des services préexistants pour offrir des fonctionnalités plus complexes est l'un des apports principaux des architectures SOA. Ce processus de composition de services, en particulier les services Web, est généralement défini par une chorégraphie ou une orchestration de services atomiques. Ces compositions sont vues comme un système états-transitions exprimant le protocole de communication entre les services participants. Les langages de description de Workflows de services, exprimant ces compositions, souffrent de l'absence de sémantique formelle et de la présence d'ambiguïtés dans la définition de leurs constructeurs au sein des standards définissant ces langages. Les outils associés à ces langages n'offrent pas la possibilité de vérifier et de valider formellement le comportement et les propriétés des services composés obtenus. Cette thèse s'intéresse à la modélisation et à la vérification formelles de la composition de services web décrite avec le standard BPEL en utilisant la méthode B Evénementiel. L'approche proposée modélise les parties statique et dynamique de BPEL et se base sur le raffinement pour la structuration du développement d'un processus BPEL. La technique de la preuve de théorème est utilisée pour l'établissement des propriétés. Un lien un-à-un est garanti entre les éléments de BPEL et leur correspondant B Evénementiel. Cette correspondance offre un assistance aux développeurs pour l'amélioration de la qualité du processus BPEL. Cette approche a été implémentée dans l'outil BPEL2B<br>The ability to compose existing services to provide more complex functionality is one of the main benefits of SOA architecture. This services compositions process, especially Web services, is generally defined by a choreography or an orchestration of atomic services. These compositions are seen as a states-transitions systems expressing the communication protocol between the participating services. Services Workflows description languages, expressing these compositions, suffer from the lack of formal semantics and the presence of ambiguities in their constructors definitions in standards defining these languages. The associated tools do not offer the possibility to formally verify and validate the behaviour and the obtained services compositions properties. This thesis focuses on modelling and formal verification of the Web services composition described with the BPEL standard using the B event method. The proposed approach models the static and dynamic parts of BPEL and is based on refinement for structuring the BPEL process development. The theorem proving technique is used for setting properties. One-to-one link is guaranteed between the BPEL elements and their B Event corresponding. This correspondence provides assistance to developers to improve the quality of the BPEL process. This approach has been implemented in the BPEL2B tool
50
Pétin, Jean-François. "Méthodes et modèles pour un processus sûr d'automatisation." Habilitation à diriger des recherches, Université Henri Poincaré - Nancy I, 2007. http://tel.archives-ouvertes.fr/tel-00202431.
Full textAbstract:
Les travaux développés dans ce mémoire concernent la formalisation d'un processus sûr d'automatisation en vue de maîtriser la complexité induite par l'intégration de plus en plus importante de technologies de l'information et de la communication au cœur même des processus de production et des produits. Plus précisément, notre travail porte sur l'intégration d'approches méthodologiques, issues du Génie Automatique, et de modèles formels, issus du Génie Informatique et de l'Automatique des Systèmes à Evénements Discrets afin de garantir, a priori, le respect des exigences formulées par les utilisateurs. Notre contribution porte sur deux axes. Le premier concerne l'intégration de techniques de synthèse de la commande dans un processus d'automatisation, incluant les phases de modélisation et de génération d'un code implantable, et leur application à la reconfiguration de systèmes manufacturiers contrôlés par le produit. Le second est basé sur le raffinement formel ou semi-formel de modèles pour identifier et structurer les exigences exprimées à un niveau " système " puis les allouer et les projeter sur une architecture de fonctions, de composants ou d'équipements. Ces travaux ont été initiés dans le cadre de notre thèse en réponse aux besoins de R&D industriels de la Direction des Etudes & Recherche d'EDF, puis ont été poursuivis avec une cible relative aux systèmes manufacturiers et validés dans le cadre de collaborations industrielles variées.