Le protocole Pastry réalise une table de hachage distribué sur un réseau pair à pair organisé en un anneau virtuel de noeuds. Alors qu'il existe plusieurs implémentations de Pastry, il n'y a pas encore eu de travaux pour décrire formellement l'algorithme ou vérifier son bon fonctionnement. Intégrant des structures de données complexes et de la communication asynchrone entre des noeuds qui peuvent rejoindre ou quitter le réseau, ce protocole représente un intérêt certain pour la vérification formelle. La thèse se focalise sur le protocole Join de Pastry qui permet à un noeud de rejoindre le réseau. Les noeuds ayant intégré le réseau doivent avoir une vue du voisinage cohérente entre eux. La propriété principale de correction, appelée CorrectDelivery, assure qu'à tout moment il y a au plus un noeud capable de répondre à une requête pour une clé, et que ce noeud est le noeud le plus proche numériquement à ladite clé. Il n'est pas trivial de maintenir cette propriété en présence de churn. Ce travail nous a permis de découvrir des violations inattendues de la propriété dans les versions publiées de l'algorithme. Sur la base de cette analyse, le protocole IdealPastry est conçu et vérifié en utilisant l'assistant interactif à la preuve TLAPS pour TLA+. Le protocole LuPastry est obtenu en assouplissant certaines hypothèses de IdealPastry. Il est montré formellement que LuPastry vérifie CorrectDelivery sous l'hypothèse qu'aucun noeud ne quitte le réseau. Cette hypothèse ne peut être relâchée à cause du risque de perte de connexion du réseau dans le cas où plusieurs noeuds quittent le réseau en même temps / Pastry is a structured P2P algorithm realizing a Distributed Hash Table over an underlying virtual ring of nodes. Several implementations of Pastry are available, but no attempt has so far been made to formally describe the algorithm or to verify its properties. Since Pastry combines complex data structures, asynchronous communication, and concurrency in the presence of spontaneous join and departure of nodes, it makes an interesting target for verification. This thesis focuses on the Join protocol of Pastry that integrates new nodes into the ring. All member nodes must have a consistent key mapping among each other. The main correctness property, named CorrectDelivery, states that there is always at most one node that can deliver an answer to a lookup request for a key and this node is the numerically closest member node to that key. This property is non-trivial to preserve in the presence of churn. In this thesis, unexpected violations of CorrectDelivery in the published versions of Pastry are discovered and analyzed using the TLA+ model checker TLC. Based on the analysis, the protocol IdealPastry is designed and verified using the interactive theorem prover TLAPS for TLA+. By relaxing certain hypotheses, IdealPastry is further improved to LuPastry, which is again formally proved correct under the assumption that no nodes leave the network. This hypothesis cannot be relaxed in general due to possible network separation when particular nodes simultaneously leave the network

Ces travaux de recherche ont été réalisés dans le cadre du projet régional Com-SLoT (Communauté de Services Logistiques sur l'Internet des Objets) qui s'inscrit dans l'axe des "outils numériques pour la performance industrielle" (2013-2016). Com-SLoT vise à mettre en place une communauté de services pour la gestion des objets logistiques. Il s'agit précisément de récolter et de partager toutes les informations nécessaires à la planification, l'exécution et la coordination des flux. Le problème qui est posé dans cette thèse est la "Modélisation des flux logistiques : vers une plate-forme d'interopérabilité des objets logistiques". Le modèle de flux de marchandises que nous cherchons à modéliser a donc pour objectif et défi principal de faciliter le développement et la mise en place des systèmes de gestion collaboratives de flux de marchandises basés sur l'Internet des objets et les plateformes cloud Computing. Ce défi scientifique et technologique peut se décliner en sous objectifs comme suit : (1) Proposer un modèle générique de flux logistique centré sur l'entité logistique en tant qu'entité autonome et communicante. (2) Passer de l’échange au partage : Collecter les données sur l'entité et le flux logistique, stocker et partager ces données à l'ensemble des acteurs de la supply chain. (3) Gérer l'hétérogénéité des données et les droits d'accès pour l'interopérabilité des flux. (4) Intégrer le flux de marchandises avec les technologies de l'internet des objets et des plateformes Cloud. (5) Réaliser une vrai plateforme collaborative en mode SaaS : dans ce cadre, il est plus question d'architecture et d'intégration / This research project was carried out within the framework of the regional project COM-SLoT (Community of Logistics Services on the Internet of Things). This project is in the field of "Digital tools for industrial performance". COM-SLoT aims to set up a community of services for the management of logistics workflows and related business entities. It is a matter of collecting and sharing all information necessary for the planning, the execution and the coordination of workflows. The problem to solve in this thesis is the "Modeling of logistic flows : towards a platform for business entities interoperability". The workflow model we are going to seek therefore has as main goal and challenges to facilitate the design of collaborative management of workflows, based on Internet of Things and Cloud Computing technologies. This challenge can be broken down into sub-goals as follows : (1) Propose a generic workflow model focused on the logistics entity as an autonomous and communicating entity. (2) Switching from peer to peer (PoP) data exchange to information sharing : collecting data on entities and workflows, storing and sharing to supply chain stakeholders. (3) Manage data heterogeneity and access rights to enable workflow interoperability. (4) Integrate Internet of Things technologies in the business entities. (5) Design a SaaS based collaborative platform to overcome existing architectural failures

Comme les syst`emes mat´eriels et logiciels grandissent de fa¸con continue en ´echelle et fonctionnalit´es, la probabilit´e d’erreurs subtiles de- vient toujours plus grande. Les techniques d’abstraction, souvent bas´ees sur l’interpr´etation abstraite de Cousot, fournissent une m´ethode pour ex´ecuter symboliquement les syst`emes en utilisant le domaine abstrait `a la place du domaine concret. Dans cette th`ese, on introduit des techniques d’abstraction pour les logiques sous des interpr´etations multi-valu´ees. Beaucoup d’applications des logiques multi-valu´ees ont ´et´e trouv´ees dans la v´erification du mat´eriel et du logiciel. Pour la v´erification du mat´eriel, des outils de simulation et des r´ealisations des circuits multi-valu´es v´eritables ont ´et´e propos´es, les risques dynamiques ont ´et´e model´es en introduisant des ´etats faux pour trouver des r´egions chevauchantes des signaux en concurrence, etc. Pour la v´erification du logiciel on a besoin d’incertitude parce qu’on ne peut savoir si certains comportements devraient ˆetre possibles et on a besoin du d´esaccord parce que l’on peut avoir des acteurs diff´erents qui sont en d´esaccord pour la mani`ere dont les syst`emes devraient se comporter. Les abstractions sont obtenues en appliquant des relations d’´equivalence et apr`es, les symboles pr´edicatifs de la logique sont red´efinis `a s’appliquer cor- rectement aux classes d’´equivalence `a l’aide des politiques d’interpr´etation. On fournit des r´esultats de pr´eservation pour la logique de premier ordre, pour la logique temporelle et pour la logique temporelle de la connaissance. Avant de discuter les abstractions multi-valu´ees pour la logique temporelle, nous pr´esentons une ´etude de cas pour utiliser l’abstraction dans le contexte des mod`eles du contrˆole d’acc`es. Nous fournirons aussi une technique d’abstraction pour les types de do- nn´ees. Cette technique d’abstraction peut ˆetre ´elargie pour les types abstraits de donn´ees. Ici, les abstractions sont appliqu´ees aux sp´ecifications initiales au moyen des ´equations et ils sont appel´es des abstractions ´equationnelles. De plus, la technique d’abstraction pr´esent´ee g´en´eralise et clarifie la nature de beaucoup de techniques d’abstraction trouv´ees dans la litt´erature, telles: la technique de dupliquer les symboles pr´edicatifs, shape analysis, l’abstraction par pr´edicats, l’approche de McMillan, etc. Pour raisonner au sujet des syst`emes dynamiques, on introduit les types de donn´ees dynamiques et on ´etend la m´ethode d’abstraction ant´erieure `a ce cas. Le probl`eme principal qui survient quand on utilise les abstractions est de trouver l’abstraction convenable ou de raffiner une abstraction d´ej`a existante pour en obtenir une meilleure. On prouve que les techniques d’abstraction que nous avons introduites pour les types de donn´ees sous l’interpr´etation 3- valu´ee Kleene, peuvent ˆetre utilis´ees dans une proc´edure de raffinement. De plus, on montre que la proc´edure de raffinement guid´e par contre-exemple est plus efficace quand on l’utilise sous les abstractions ´equationnelles / As the hardware and software systems are growing continuously in scale and functionality, the likelihood of subtle errors becomes greater. Abstraction techniques, often based on abstract interpretation, provide a method for symbolically executing systems using the abstract instead of the concrete domain. In this thesis, we are concerned with abstractions for logics under multi-valued interpretations. Many applications of multi-valued logics have been found in hardware and software verification. For hardware verification, simulation tools and imple- mentations of genuinely multi-valued circuits have been proposed, dynamic hazards have been modeled by introducing pseudo states to find overlapping regions of competing signals, implementation of gates have been verified on the basis of switch level models, etc. For software verification, we need uncer- tainty because we may not know whether some behaviors should be possible, we need disagreement because we may have different stakeholders that dis- agree about how the systems should behave and we need to represent relative importance because some behaviors are essential and others may or may not be implemented. The abstractions are obtained by applying equivalence relations and then, the predicate symbols of the logic are re-defined to work properly on equiva- lence classes by using interpretation policies. We provide preservation results for first-order logic, temporal logic, and temporal logic of knowledge. As a case study, we show how abstraction can be used to solve the safety problem for protection systems which model access control policies. The use of abstraction in the context of data types, is also investigated. This technique scales well from data types to abstract data types. Here, abstractions are applied to initial specifications by means of equations and they are called equationally specified abstractions. Moreover, the abstraction technique we propose generalizes and clarifies the nature of many abstraction techniques found in the literature, such as the technique of duplicating pred- icate symbols, shape analysis, predicate abstraction, McMillan’s approach, etc. To reason about dynamic systems, we introduce dynamic data types and extend the previous abstraction technique to this case. The main problem that arises when using abstraction techniques is to find the suitable abstraction or to refine an already existing abstraction in order to obtain a better one. In this thesis, we prove that the abstraction techniques for data types, under Kleene’s three-valued interpretation, can be used in a refinement procedure. Moreover, we show that the counterexample guided abstraction refinement procedure (CEGAR) works better when used with equationally specified abstractions

Dans cette thèse, nous nous intéressons au calcul d'ordonnanceurs pour les systèmes hybrides. En fait, nous considérons deux sous-classes des systèmes hybrides, les systèmes temps-réels où des tâches doivent se partager l'accès à une ressource commune, et les systèmes à commutations où un choix doit être fait sur les dynamiques à choisir en fonction d'objectifs à atteindre. Dans la première partie de cette thèse, nous nous intéressons aux problèmes d'ordonnancement et prenons comme étude de cas l'ordonnancement de tâches périodiques sur des architectures multiprocesseurs. Nous nous intéressons plus particulièrement à déterminer si l'on peut modifier certaines valeur des paramètres du système tout en respectant les contraintes temporelles sans changer d'ordonnanceur. La méthode inverse permet de prouver de manière formelle la robustesse des systèmes temporisés paramétriques. Nous introduisons une méthode de réduction du nombre d'états nécessaire à la vérification. Cette réduction nous permet de traîter des études de cas intéressantes telle que celle proposée par Astrium EADS pour le lanceur Ariane 6. Nous montrons également comment la Cartographie Comportementale, une extension de la méthode inverse, permet de trouver la zone de l'espace des paramètres où l'on a l'existence d'un ordonnancement satisfaisant les contraintes temporelles. Nous comparons cette approche avec une méthode analytique pour montrer l'intérêt de notre approche. Dans la seconde partie de cette thèse, nous nous intéressons au contrôle de systèmes affines à commutation. Ces systèmes sont gouvernés par une famille d'équations différentielles linéaires et le contrôleur peut choisir laquelle va gouverner le système pendant le prochain pas de temps. Dans ce cadre, le contrôle peut être vu comme l'ordonnancement des dynamiques que le système va prendre. Le choix de la dynamique peut se faire pour des objectifs de stabilité ou d'accessibilité. Nous proposons une nouvelle méthode qui calcule un contrôleur dont la stratégie est la même pour des ensembles denses de points. Notre méthode utilise le calcul en avant, souvent préférable au calcul à rebours pour les systèmes contractants. Nous montrons que, sous certaines conditions, le système contrôlé évolue vers un comportement limite. Nous appliquons notre méthode sur plusieurs études de cas issues de la littérature ainsi qu'un exemple réel, un prototype de convertisseur de tension multiniveaux. Enfin, nous montrons que notre méthode s'étend aux systèmes comportant des perturbations ainsi qu'aux systèmes non linéaires. / In this thesis, we are interested in designing schedulers for hybrid systems. We consider two specific subclasses of hybrid systems, real-time systems where tasks are competing for the access to common resources, and sampled switched systems where a choice has to be made on dynamics of the system to reach goals. Scheduling consists in defining the order in which the tasks will be run on the processors in order to complete all the tasks before a given deadline. In the first part of this thesis, we are interested in the scheduling of periodic tasks on multiprocessor architectures. We are especially interested in the robustness of schedulers, i.e., to prove that some values of the system parameters can be modified, and until what value they can be extended while preserving the scheduling order and meeting the deadlines. The Inverse Method can be used to prove the robustness of parametric timed systems. In this thesis, we introduce a state space reduction technique which allows us to treat challenging case studies such as one provided by Astrium EADS for the launcher Ariane 6. We also present how an extension of the Inverse Method, the Behavioral Cartography, can solve the problem of schedulability, i.e., finding the area in the parametric space in which there exists a scheduler that satisfies all the deadlines. We compare this approach to an analytic method to illustrate the interest of our approach In the second part of this thesis, we are interested in the control of affine switched systems. These systems are governed by a finite family of affine differential equations. At each time step, a controller can choose which dynamics will govern the system for the next time step. Controlling in this sense can be seen as a scheduling on the order of dynamics the system will have to use. The objective for the controller can be to make the system stay in a given area of the state space (stability) or to reach a given region of the state space (reachability). In this thesis, we propose a novel approach that computes a scheduler where the strategy is uniform for dense subsets of the state space. Moreover, our approach only uses forward computation, which is better suited than backward computation for contractive systems. We show that our designed controllers, systems evolve to a limit cyclic behavior. We apply our method to several case studies from the literature and on a real-life prototype of a multilevel voltage converter. Moreover, we show that our approach can be extended to systems with perturbations and non-linear dynamics.

L'analyse des systèmes communiquant par file a fait l'objet d'études scientifiques nombreuses mais qui n'ont pu offrir des solutions totalement satisfaisantes. Nous proposons d'aborder ce problème dans le cadre de l'interprétation abstraite, en définissant des treillis abstraits adaptés à ce type de systèmes. Nous considérons d'abord le cas où les messages échangés sont assimilables à un alphabet fini, puis nous nous attaquons au cas, plus difficile, des messages portant des valeurs entières ou réelles. Ce problème nous amène à définir et à étudier un nouveau type d'automate, les automates de treillis. Ces automates de treillis peuvent également être utilisés pour l'analyses des programmes utilisant une pile d'appels.

Ce travail de thèse présente une méthode originale pour la simulation symbolique des circuits décrits au niveau algorithmique. Tout d'abord, la description VHDL du circuit est modélisée sous le forme d'un ensemble d'équations récurrentes (SER) qui décrivent l'état du système à un instant donné en fonction des états précédents. Après une extraction automatique du SER du circuit, l'algorithme de simulation VHDL est exécuté pendant un nombre fixe de cycles déterminé par le concepteur. Pendant la simulation, un scénario de test et une simplification par règles de substitution sont appliqués pour obtenir les expressions symboliques ou numériques de chaque objet du circuit (registre, signal ou port de sortie). Trois modes de test (raisonnement, exécution et mixte) sont définis et expliqués en se basant sur la distinction entre la partie opérative et la partie contrôle de circuit. Le simulateur symbolique et le compilateur sont implémentés avec l'aide du système Mathematica. <br />Une méthodologie de vérification autour de la simulation symbolique avec SER est proposée. Plusieurs paradigmes de vérification (la correspondance de forme, la démonstration de théorèmes et SAT) sont employés sur les résultats de la simulation symbolique pour valider ou prouver les propriétés du circuit. La méthodologie est montrée sur deux circuits de taille réelle (un filtre numérique et une mémoire) et sur de nombreux cas académiques.

La technologie facilite l'intégration de nombreux composants sur une puce pour atteindre les performances et les besoins exigés par les applications. La tendance est à l'augmentation de la complexité de tels systèmes, appelés systèmes monopuces. <br />Les systèmes monopuces sont sur un marché très concurrentiel, et l'arrivée rapide du produit sur le marché est très importante. De plus, le coût lié à la conception des parties matérielles et logicielles est très élevé. Détecter une erreur après fabrication entraîne un surcoût financier et de temps non acceptable. Ceci nous entraîne vers les deux problèmes traités dans ce travail de thèse : s'assurer que la système est correct avant sa fabrication et accélérer le processus de conception.<br />Après avoir évalué plusieurs techniques de vérification, nous pensons que le prototypage sur plateforme reconfigurable est une solution adaptée pour les problèmes mentionnés. Ce prototypage permet de vérifier rigoureusement les systèmes grâce à une vitesse élevée, et de tester le système dans son environnement d'utilisation. Il accélère aussi la conception en permettent le développement de certaines couches logicielles avant que le système soit fini.<br />Pour obtenir rapidement un prototype à partir d'une description RTL d'une application, nous proposons un flot de prototypage basé sur une plateforme reconfigurable. Ce flot est composé de quatre étapes : allocation, configuration de la plateforme, adaptation de l'application, et génération du code.<br />Dans l'allocation, les concepteurs associent chaque partie de l'architecture à un nœud de prototypage de la plateforme. Ces associations indiquent sur quelles parties de la plateforme reconfigurable sont réalisées les parties de l'architecture de l'application. La configuration est la réorganisation de la plateforme reconfigurable. L'adaptation consiste à modifier l'application pour satisfaire aux caractéristiques de la plateforme reconfigurable. Cette étape est effectuée si la plateforme ne peut pas être configurée pour s'adapter aux besoins de l'application. Enfin, la génération du code est un processus standard tel que la compilation et l'édition de lien des logiciels, la synthèse logique, le placement sur FPGA, et le routage.<br />Ce flot a été validé en réalisant le prototypage des applications VDSL et DivX. La plateforme utilisée est une plateforme ARM Integrator avec une carte mère, quatre modules processeurs ARM, et d'un module FPGA communiquant à travers un bus AMBA AHB. Une expérience de co-émulation a également été réalisée pour explorer les difficultés et les avantages de cette technique. L'avantage principal est qu'on peut profiter de l'observabilité de la simulation et de la vitesse de l'émulation. <br />Ce travail de thèse montre que l'on peut obtenir rapidement un prototype en utilisant le flot propose sur une plateforme reconfigurable et aussi faciliter le développement des parties logicielles pour accélérer la conception. La configurabilité de plateforme de prototypage et l'intégration du flot de prototypage sur un flot de conception des systèmes restent des problématiques à approfondir.

Cette thèse présente un modèle formel représentant toute architecture de communication sur la puce. Ce modèle est mathématiquement décrit par une fonction nommée GeNoC. La correction de GeNoC est exprimée par un théorème montrant que tout message émis atteint sa destination sans modification de l'information qu'il transporte. Le modèle identifie les composantes communes à toute architecture et leurs propriétés essentielles, à partir desquelles est déduite la preuve du théorème sur GeNoC. Chaque composante est représentée par une fonction sans définition explicite, mais contrainte de satisfaire ses propriétés essentielles. Ainsi, la validation de toute architecture particulière consiste en la preuve que les définitions concrètes de ses composantes satisfont les propriétés essentielles. En pratique, ce formalisme a été réalisé dans la logique du démonstrateur de théorèmes ACL2. Une méthodologie associée au modèle fournit un support systématique pour la spécification et la validation des architectures de communication sur la puce à un haut niveau d'abstraction. Pour valider notre approche, nous avons exhibé différentes architectures constituant autant de concrétisations du modèle générique GeNoC. Ces concrétisations comprennent<br />notamment des systèmes industriels, comme le bus AMBA AHB ou le réseau Octagon de ST Microelectronics.

L'utilisation d'un framework pose des problèmes liés au respect de la structure et du comportement de celui-ci. Ces problèmes sont la conséquence de la perte des informations de conception lors de l'implémentation, ce qui se traduit par l'absence d'une documentation pertinente lors de l'utilisation. Ainsi le but de cette thèse est de fournir un modèle d'expression des dépendances structurelles et comportementales. Ces modèles sont intégrés au cycle de vie du framework, de la spécification jusqu'à la finalisation. Le modèle de dépendances structurelles propose une expression explicite des dépendances grâce à une réification partielle du framework. Ce modèle, indépendant de tout langage permet au développeur du framework aussi bien qu'à un utilisateur, de consulter les dépendances entre les éléments du framework, et de bénéficier d'une aide dynamique ainsi que d'un système de vérification. Le modèle de dépendances comportementales étend l'interface statique des classespar une spécification dynamique (protocole) de celles-ci. Cette spécification définit les séquences valides d'enchaînement de messages entrant et sortant de la classe. Cette spécification, basée sur le modèle formel d'Esterel, permet des vérifications statiques et dynamiques.

La présente étude vise à mieux comprendre quelle dynamique corrélationnelle s’inscrit entre le concept de soi d’un individu et son capital social. La théorie de la vérification de soi (Swann, 1987) sous-tend que les individus ont tendance à s’entourer de gens qui confirment leur vision d’eux même, dans le but de pouvoir prédire et contrôler leur environnement. On peut alors se demander si la personne dont le soi est tapissé de représentations négatives a précisément la capacité de se construire un réseau social qui constituera véritablement un « capital » relationnel pour elle. Un design méthodologique corrélationnel a été utilisé afin d’évaluer les liens de concomitance entre les indicateurs des construits « concept de soi » et « capital social. » Les résultats d’analyses statistiques corrélationnelles entre les indicateurs confirment, en grande partie, l’hypothèse de départ, à savoir que plus une personne nourrit un concept de soi sain, plus elle génère un capital social riche. Les implications pratiques et théoriques sont discutées.