L’intérêt porté aux algorithmes probabilistes est, entre autres,dû à leur simplicité. Cependant, leur analyse peut devenir très complexeet ce particulièrement dans le domaine du distribué. Nous mettons en évidencedes algorithmes, optimaux en terme de complexité en bits résolvantles problèmes du MIS et du couplage maximal dans les anneaux, qui suiventle même schéma. Nous élaborons une méthode qui unifie les résultatsde bornes inférieures pour la complexité en bits pour les problèmes duMIS, du couplage maximal et de la coloration. La complexité de ces analysespouvant facilement mener à l’erreur et l’existence de nombreux modèlesdépendant d’hypothèses implicites nous ont motivés à modéliserde façon formelle les algorithmes distribués probabilistes correspondant ànotre modèle (par passage de messages, anonyme et synchrone), en vuede prouver formellement des propriétés relatives à leur analyse. Pour cela,nous développons une bibliothèque, RDA, basée sur l’assistant de preuveCoq. / Probabilistic algorithms are simple to formulate. However, theiranalysis can become very complex, especially in the field of distributedcomputing. We present algorithms - optimal in terms of bit complexityand solving the problems of MIS and maximal matching in rings - that followthe same scheme.We develop a method that unifies the bit complexitylower bound results to solve MIS, maximal matching and coloration problems.The complexity of these analyses, which can easily lead to errors,together with the existence of many models depending on implicit assumptionsmotivated us to formally model the probabilistic distributed algorithmscorresponding to our model (message passing, anonymous andsynchronous). Our aim is to formally prove the properties related to theiranalysis. For this purpose, we develop a library, called RDA, based on theCoq proof assistant.

La validation des systèmes critiques réalistes nécessite d'être capable de modéliser et de vérifier formellement des données complexes, du parallélisme asynchrone, et du temps-réel simultanément. Des langages de haut-niveau, comme ceux qui héritent des fondations théoriques des algèbres de processus, ont une syntaxe concise et une grande expressivité pour représenter ces aspects. Cependant, ils disposent de peu d'outils logiciels permettant d'appliquer des algorithmes efficaces du model-checking. Néanmoins, de tels outils existent pour des modèles graphiques, de niveau plus bas, tels que les automates temporisés (par exemple UPPAAL) et les réseaux de Petri temporisés (par exemple TINA). Les modèles intermédiaires sont un moyen pour combler le fossé qui sépare les langages des modèles graphiques. Par exemple, NTIF (New Technology Intermediate Format) a été proposé pour représenter des processus séquentiels non temporisés qui manipulent des données complexes. Dans cette thèse, nous proposons un nouveau modèle nommé ATLANTIF, qui enrichit NTIF de constructions temps-réel et de compositions parallèles de processus séquentiels. Leur synchronisation est exprimée d'une manière simple et intuitive par la nouvelle notion de synchroniseur. Nous montrons qu'ATLANTIF est capable d'exprimer les constructions principales des langages de haut niveau. Nous présentons aussi des traducteurs d'ATLANTIF vers des automates temporisés (pour la vérification avec UPPAAL) et vers des réseaux de Petri temporisés (pour la vérification avec TINA). Ainsi, ATLANTIF étend la classe des systèmes qui peuvent en pratique être vérifiés formellement, ce que nous illustrons par un exemple.

Les offres de l’informatique en nuage augmentent de plus en plus et les clients ne sont pas capables de lescomparer afin de choisir la plus adaptée à leurs besoins. De plus, les garanties de sécurité proposées parles fournisseurs restent incompréhensibles pour les clients. Cela représente un frein pour l'adoption dessolutions de l’informatique en nuage.Dans cette thèse, nous proposons un mécanisme de courtage des services de l’informatique en nuage quiprend en compte les besoins du client en termes de sécurité.Les besoins exprimés par le client sont de deux natures. Les besoins fonctionnels représentent lesressources et leurs performances. Les besoins non-fonctionnels représentent les propriétés de sécurité etles contraintes de placement des ressources dans le nuage informatique. Nous utilisons le langage Alloypour décrire les offres et les besoins. Nous utilisons l'analyseur Alloy pour l'analyse et la vérification desspécifications du client. Le courtier sélectionne les fournisseurs qui satisfont les besoins fonctionnels et nonfonctionnelsdu client. Il vérifie ensuite, que la configuration du placement des ressources chez lesfournisseurs respecte toutes les propriétés de sécurité exigées par le client.Toutes ces démarches sont effectuées avant le déploiement des ressources dans le nuage informatique.Cela permet de détecter les erreurs et conflits des besoins du client tôt. Ainsi, on réduit les vulnérabilités desressources du client une fois déployées. / The number of cloud offerings increases rapidly. Therefore, it is difficult for clients to select the adequate cloud providers which fit their needs. In this thesis, we introduce a cloud service brokerage mechanism that considers the client security requirements. We consider two types of the client requirements. The amount of resources is represented by the functional requirements. The non-functional requirements consist on security properties and placement constraints. The requirements and the offers are specified using the Alloy language. To eliminate inner conflicts within customers requirements, and to match the cloud providers offers with these customers requirements, we use a formal analysis tool: Alloy. The broker uses a matching algorithm to place the required resources in the adequate cloud providers, in a way that fulfills all customer requirements, including security properties. The broker checks that the placement configuration ensures all the security requirements. All these steps are done before the resources deployment in the cloud computing. This allows to detect the conflicts and errors in the clients requirements, thus resources vulnerabilities can be avoided after the deployment.

Nous avons commencé la thèse par la littérature d'enquête sur les approches SPLE et CbyC dans l'état de l'art. Sur la base de l'aperçu et des connaissances obtenues, nous avons analysé les problèmes existants et suggéré des moyens de les résoudre pour notre objectif principal. Nous avons proposé dans le chapitre 2 une méthodologie pour développer des lignes de produits afin que les produits générés soient corrects par construction. Notre intention principale est qu'un utilisateur n'a pas besoin de connaître le processus de génération de produit mais peut recevoir un produit final correct en sélectionnant une configuration de fonctionnalité. En utilisant la méthodologie, les produits finaux sont générés automatiquement et leur exactitude est garantie. À la suite de cette proposition, nous sommes passés au chapitre 3 pour définir la langue de FFML qui est utilisé pour l'écriture de modules. Le mécanisme de réutilisation et de modification, défini pour la langue et appliqué à toutes sortes d'artefacts (spécification, code et preuve de précision) réduit l'effort de programmation. Au chapitre 4, nous nous sommes concentrés sur la définition des mécanismes de composition pour la composition des modules FFML et les intégrons à l'outil FFML Product Generator. L'évaluation de notre méthodologie est réalisée par le développement de deux lignes de produits logiciels, le compte bancaire SPL et le SPL de poker, ce dernier étant un peu plus complexe que le premier. Dans l'évaluation, nous avons souligné les avantages et la limitation de notre méthodologie. / We began the thesis by survey literature on SPLE and CbyC approaches in the State of the Art. Based on the overview and the insights obtained, we have analyzed the existing problems and suggested ways to solve them for our main goal. We have proposed in Chapter 2 a methodology to develop product lines such that the generated products are correct-by-construction. Our main intention is that a user does not need to know the product generation process but can receive a correct final product from selecting a configuration of features. Using the methodology, the final products are generated automatically and their correctness is guaranteed. Following this proposal, we have moved in Chapter 3 to define the FFML language that is used for writing modules. The reuse and modification mechanism, defined for the language and applied to all kinds of artifacts (specification, code and correctness proof), reduce the programming effort. In Chapter 4, we have focused on defining the composition mechanisms for composing FFML modules and embedded them into the FFML Product Generator tool. The evaluation of our methodology is performed through the development of two software product lines, the Bank Account SPL and the Poker SPL, the latter being a bit more complex than the former. In the evaluation, we have highlighted the advantages and the limitation of our methodology.

This thesis is aimed to specify and implement multi-purpose framework able to deal with graphical real-time system specification. This tool allows to use arbitrary verification approach to resulting system model check. Description of basic formal specification methods based on mathematic logic is done. Some well-known hierarchical graphical specifications for real-time systems are depictured. Author proposed suitable cases for functionality examination of resulting framework.

No description available.

<p>An interest has been established in the identification, documentation and classifi- cation of the environmental assumptions that are missing from the original PACE- MAKER System Specification. This thesis addresses the presented challenge and documents the procedure used to identify, classify, and document these missing en- vironmental assumptions.</p> <p>In summary, this thesis answers the following questions: <ol> <li></p> <p>What can be done in order to improve the original PACEMAKER System</p> <p>Specification with respect to environmental assumptions? </li> <li></p> <p>Why is it beneficial, in terms of enhancing software quality, to include the doc- umentation of environmental assumptions – which sometimes are (wrongfully) perceived as being collateral and optional – as part of the software requirements document? </li> <li></p> <p>How should such environmental assumptions be documented? </li> </ol></p> <p>More specifically, this thesis • Presents an abstract model for the PACEMAKER system. • Identifies system boundaries and interfaces in the PACEMAKER model. • Identifies environmental assumptions for the PACEMAKER system.</p> <p>• Presents a classification system for the environmental assumptions identified for the PACEMAKER system based on the proposed model.</p> <p>• Proposes a process for identifying environmental assumptions.</p> <p>Furthermore, the research findings presented in this thesis are not limited to the PACEMAKER system. The documentation convention proposed in this thesis is meant to be generalized and can be extended to address similar documentation needs posed by all kinds of software systems. Additionally, the process of environmental assumptions elicitation described in this thesis provides a useful reference for con- ducting similar assumption identification projects. Lastly, the classification system presented in this thesis for the environmental assumptions exhibits one facet of a grander conceptual system – one that incorporates multiple ‘views’ of the same set of assumptions, with each view being distinguished by a unique set of classification criteria.</p> / Master of Applied Science (MASc)

La recherche de la sûreté de fonctionnement des systèmes complexes impose une démarche de conception rigoureuse. Les travaux de cette thèse s’inscrivent dans le cadre la modélisation formelle des systèmes de contrôle autonomes tolérants aux fautes. Le premier objectif a été de proposer une formalisation d’une architecture générique en couches fonctionnelles qui couvre toutes les activités essentielles du système de contrôle et qui intègre des mécanismes de sécurité. Le second objectif a été de fournir une méthode et des outils pour évaluer qualitativement les exigences de sécurité. Le cadre formel de modélisation et d’évaluation repose sur le formalisme Event-B. La modélisation Event-B proposée tire son originalité d’une prise en compte par raffinements successifs des échanges et des relations entre les couches de l’architecture étudiée. Par ailleurs, les exigences de sécurité sont spécifiées à l’aide d’invariants et de théorèmes. Le respect de ces exigences dépend de propriétés intrinsèques au système décrites sous forme d’axiomes. Les preuves que le principe d’architecture proposé satisfait bien les exigences de sécurité attendue ont été réalisées avec les outils de preuve de la plateforme Rodin. L’ensemble des propriétés fonctionnelles et des propriétés relatives aux mécanismes de tolérance aux fautes, ainsi modélisées en Event-B, renforce la pertinence de la modélisation adoptée pour une analyse de sécurité. Cette approche est par la suite mise en œuvre sur un cas d’étude d’un drone ONERA. / The study of complex system safety requires a rigorous design process. The context of this work is the formal modeling of fault tolerant autonomous control systems. The first objective has been to provide a formal specification of a generic layered architecture that covers all the main activities of control system and implement safety mechanisms. The second objective has been to provide tools and a method to qualitatively assess safety requirements. The formal framework of modeling and assessment relies on Event-B formalism. The proposed Event-B modeling is original because it takes into account exchanges and relations betweenarchitecture layers by means of refinement. Safety requirements are first specified with invariants and theorems. The meeting of these requirements depends on intrinsic properties described with axioms. The proofs that the concept of the proposed architecture meets the specified safety requirements were discharged with the proof tools of the Rodin platform. All the functional properties and the properties relating to fault tolerant mechanisms improve the relevance of the adopted Event-B modeling for safety analysis. Then, this approach isimplemented on a study case of ONERA UAV.

La modélisation informatique et la simulation sont des activités de plus en plus répandues lors de la conception de systèmes complexes et critiques tels que ceux embarqués dans les avions. Une proposition pour la conception et réalisation d'abstractions compatibles avec les objectifs de simulation est présentée basés sur la théorie de l'informatique, le contrôle et le système des concepts d'ingénierie. Il adresse deux problèmes fondamentaux de fidélité dans la simulation, c'est-à-dire, pour une spécification du système et quelques propriétés d'intérêt, comment extraire des abstractions pour définir une architecture de produit de simulation et jusqu'où quel point le comportement du modèle de simulation représente la spécification du système. Une notion générale de cette fidélité de la simulation, tant architecturale et comportementale, est expliquée dans les notions du cadre expérimental et discuté dans le contexte des abstractions de modélisation et des relations d'inclusion. Une approche semi-formelle basée sur l'ontologie pour construire et définir l'architecture de produit de simulation est proposée et démontrée sur une étude d'échelle industrielle. Une approche formelle basée sur le jeu théorique et méthode formelle est proposée pour différentes classes de modèles des systèmes et des simulations avec un développement d'outils de prototype et cas des études. Les problèmes dans la recherche et implémentation de ce cadre de fidélité sont discutées particulièrement dans un contexte industriel. / In using Modeling and Simulation for the system Verification & Validation activities, often the difficulty is finding and implementing consistent abstractions to model the system being simulated with respect to the simulation requirements. A proposition for the unified design and implementation of modeling abstractions consistent with the simulation objectives based on the computer science, control and system engineering concepts is presented. It addresses two fundamental problems of fidelity in simulation, namely, for a given system specification and some properties of interest, how to extract modeling abstractions to define a simulation product architecture and how far does the behaviour of the simulation model represents the system specification. A general notion of this simulation fidelity, both architectural and behavioural, in system verification and validation is explained in the established notions of the experimental frame and discussed in the context of modeling abstractions and inclusion relations. A semi-formal ontology based domain model approach to build and define the simulation product architecture is proposed with a real industrial scale study. A formal approach based on game theoretic quantitative system refinement notions is proposed for different class of system and simulation models with a prototype tool development and case studies. Challenges in research and implementation of this formal and semi-formal fidelity framework especially in an industrial context are discussed.

No description available.