Cette thèse étudie l’enforcement de propriétés temporisées à l’exécution en présence d’évènements incontrôlables. Les travaux se placent dans le cadre plus général de la vérification à l’exécution qui vise à surveiller l’exécution d’un système afin de s’assurer qu’elle respecte certaines propriétés. Ces propriétés peuvent être spécifiées à l’aide de formules logiques, ou au moyen d’autres modèles formels, parfois équivalents, comme des automates. Nous nous intéressons à l’enforcement à l’exécution de propriétés spécifiées par des automates temporisés. Tout comme la vérification à l’exécution, l’enforcement à l’exécution surveille l’exécution d’un système, la différence étant qu’un mécanisme d’enforcement réalise certaines modifications sur l’exécution afin de la contraindre à satisfaire la propriété souhaitée. Nous étudions plus particulièrement l’enforcement à l’exécution lorsque certains évènements de l’exécution sont incontrôlables, c’est-à-dire qu’ils ne peuvent pas être modifiés par un mécanisme d’enforcement. Nous définissons des algorithmes de synthèse de mécanismes d’enforcement décrits de manières fonctionnelle puis opérationnelle, à partir de propriétés temporisées régulières (pouvant être représentées par des automates temporisés). Ainsi, deux mécanismes d’enforcement équivalents sont définis, le premier présentant une approche correcte sans considération d’implémentation, alors que le second utilise une approche basée sur la théorie des jeux permettant de précalculer certains comportements, ce qui permet de meilleures performances. Une implémentation utilisant ce précalcul est également présentée et évaluée. Les résultats sont encourageant quant à la faisabilité de l’enforcement à l’exécution en temps réel, avec des temps supplémentaires suffisamment courts sur de petites propriétés pour permettre une utilisation de tels systèmes. / This thesis studies the runtime enforcement of timed properties when some events are uncontrollable. This work falls in the domain of runtime verification, which includes all the techniques and tools based on or related to the monitoring of system executions with respect to requirement properties. These properties can be specified using different models such as logic formulae or automata. We consider timed regular properties, that can be represented by timed automata. As for runtime verification, a runtime enforcement mechanism watches the executions of a system, but instead of just outputting a verdict, it modifies the execution so that it satisfies the property. We are interested in runtime enforcement with uncontrollable events. An uncontrollable event is an event that an enforcement mechanism can not modify. We describe the synthesis of enforcement mechanisms, in both a functional and an operational way, that enforce some desired timed regular property. We define two equivalent enforcement mechanisms, the first one being simple, without considering complexity aspects, whereas the second one has a better time complexity thanks to the use of game theory; the latter being better suited for implementation. We also detail a tool that implements the second enforcement mechanism, as well as some performance considerations. The overhead introduced by the use of our tool seems low enough to be used in some real-time application scenarios.

L’omniprésence des systèmes logiciels et le rôle important qu’ils jouent dans la vie quotidienne rendent les utilisateurs de plus en plus exigeants. Entre autre, ils demandent plus de fiabilité et des systèmes qui peuvent s’adapter à leur contexte d’utilisation. Afin de satisfaire ces demandes, les cadres techniques et les méthodes de conception sous-jacents au développement des systèmes doivent être modulaires, flexibles et consistants. L’architecture orientée service (SOA) est un paradigme qui offre des mécanismes permettant une grande flexibilité des architectures des systèmes logiciels tout en réduisant leurs coûts de développement puisqu’elle se base sur des entités modulaires et réutilisables appelées services. Ces services peuvent être réutilisés dans le cadre d’une composition ou d’une chorégraphie de services pour la construction de nouveaux processus métiers transverses. SOA promet aussi d’augmenter la fiabilité des systèmes au travers de la notion de contrat de services. De son côté, le paradigme de l’Ingénierie des modèles (IDM) offre au travers de ses deux principes fondateurs, l’abstraction et l’automatisation, deux moyens puissants de gestion de la complexité des systèmes. Malgré les progrès des deux paradigmes, IDM et SOA, il y a encore des défis à résoudre. Notamment, on peut citer : (1) La vérification rigoureuse des spécifications des systèmes conformes aux principes de SOA. Ce point constitue un défi car pour modéliser ces systèmes, les concepteurs ont besoin de plus d'un point de vue représentant chacun une préoccupation spécifique du système et bien sûr ces points de vue doivent être sémantiquement cohérents. Ce problème est appelé la vérification de la consistance horizontale, une tâche manuellement difficile qui constitue une étape importante pour réduire les incohérences dans les modèles des applications SOA avant de les transformer en d'autres formes (du code, des cas de tests, etc.). (2) La transformation des spécifications des systèmes en artefacts exécutables. Malgré la maturité de l’architecture SOA, la transformation des spécifications des systèmes SOA en artefacts exécutables s'avère encore une étape fastidieuse et est généralement effectué manuellement. En particulier, la transformation des chorégraphies de services en orchestrations exécutables reste un problème en raison de la nécessité de prendre en compte les aspects complexes des systèmes distribués, tels que l’asynchronisme et la concurrence. (3) La vérification de l’exécution. Au moment de la spécification, des comportements inattendus peuvent encore apparaitre lors de l’exécution. Pour cette raison, il est nécessaire de pouvoir vérifier la conformité de l'exécution d’un système par rapport à sa spécification. Ce problème est appelé la vérification de la consistance verticale. Ce travail de thèse propose ainsi une approche de type SOA dirigée par les modèles résolvant les défis mentionnés précédemment. Cette approche comprend une méthodologie en deux étapes pour la vérification de la consistance horizontale et verticale des systèmes SOA spécifiés en utilisant la norme SoaML de l’OMG. Le problème de vérification de la consistance horizontale est résolu au moyen de l'analyse statique de la spécification des systèmes. Le deuxième défi est résolu en spécifiant les règles de transformation d'un modèle de spécification de chorégraphie de services en une orchestration exécutable qui implémente la logique de la chorégraphie tout en prenant en compte la nature asynchrone des communications entre les services distribués. Le problème de vérification de la consistance verticale est résolu par notre approche par l'analyse hors ligne des traces d’exécution d’un système. L’ensemble de la proposition méthodologique a été implanté sous la forme d’une extension à l’outil de modélisation UML open-source Papyrus. / As software systems are pervasive and play an important role in everyday life, the users are becoming more and more demanding. They mainly require more reliable systems that automatically adapt to different use cases. To satisfy these requirements, technical frameworks and design methods, upon which the systems development is based, must meet specific objectives mainly modularity, flexibility, and consistency. Service-Oriented Architecture (SOA) is a paradigm that offers mechanisms to increase the software flexibility and reduce development costs by enabling service orchestration and choreography. SOA promises also reliability through the use of services contracts as an agreement between the service provider and consumer. Model-driven SOA is a novel and promising approach that strengthens SOA with Model-Driven Engineering (MDE) technics that ease the specification, development, and verification of Service-Oriented Applications by applying abstraction and automation principles. Despite the progress to integrate MDE to SOA, there are still some challenging problems to be solved: (1) Rigorous verification of SOA system specifications. This is a challenging problem because to model SOA systems designers need more than one viewpoint, each of which captures a specific concern of the system. These viewpoints are meant to be semantically consistent with each other. This problem is called horizontal consistency checking and it is an important step to reduce inconsistencies in SOA models before transforming them into other forms (code generation, test cases derivation, etc.). (2) Transformation of systems specifications into executable artifacts. Despite the maturity of SOA, the transformation of system specifications into executable artifacts is usually manual, fastidious and error-prone. The transformation of services choreographies into executable orchestrations particularly remains a problem because of the necessity to take into account critical aspects of distributed systems such as asynchrony and concurrency when executing centralized orchestrations. (3) Runtime verification. Even after verifying Horizontal consistency at design time, there could be unexpected and unspecified data interactions that are unknown during design-time. For this reason, we still need consistency verification at runtime to handle such unforeseen events. This problem is called Vertical consistency checking. This thesis work proposes a Model-driven SOA approach to address the above-mentioned challenges. This approach includes a two-step model-driven methodology to horizontally and vertically verify the consistency of SOA systems specifications described using the SoaML standard from the Object Management Group (OMG). The horizontal consistency checking problem, which is the first challenge, is solved by means of static analysis of the system specification at the design level. The second challenge is solved by specifying the transformation from a choreography specification model to an executable orchestration implementing the choreography logic. Our transformation takes into consideration the asynchronous nature of the communications between distributed services. The vertical consistency checking problem, which is the third challenge, is solved by our approach thanks to offline analysis that allows consistency verification between both design and runtime levels. The entire methodological proposal was implemented as an extension to the open source UML modeling tool Papyrus.

La vérification à l’exécution est une méthode formelle légère qui consiste à vérifier qu’une exécution d’un système est correcte par rapport à une spécification. La spécification exprime de manière rigoureuse le comportement attendu du système, en utilisant généralement des formalismes basés sur la logique ou les machines à états finies. Alors que la verification a l’éxecution traite les systèmes monolithiques de manière exhaustive, plusieurs difficultés se présentent lors de l’application des techniques existantes à des systèmes décentralisés, c-à-d. des systèmes avec plusieurs composants sans point d’observation central. Dans cette thèse, nous nous concentrons particulièrement sur trois problèmes : la gestion de l’information partielle, la séparation du déploiement des moniteurs du processus de vérification lui-même et le raisonnement sur la décentralisation de manière modulaire et hiérarchique. Nous nous concentrons sur la notion de spécification décentralisée dans laquelle plusieurs spécifications sont fournies pour des parties distinctes du système. Utiliser une spécification décentralisée a divers avantages tels que permettre une synthèse de moniteurs à partir des spécifications complexes et la possibilité de modulariser les spécifications. Nous présentons également un algorithme de vérification général pour les spécifications décentralisées et une structure de données pour représenter l’exécution d’un automate avec observations partielles. Nous développons l’outil THEMIS, qui fournit une plateforme pour concevoir des algorithmes de vérification décentralisée, des mesures pour les algorithmes, une simulation et des expérimentations reproductibles pour mieux comprendre les algorithmes.Nous illustrons notre approche avec diverses applications. Premièrement, nous utilisons des spécifications décentralisées pour munir une analyse de pire cas, adapter, comparer et simuler trois algorithmes de vérification décentralisée existants dans deux scénarios: l’interface graphique Chiron, et des traces et spécifications générées aléatoirement. Deuxièmement, nous utilisons des spécifications décentralisées pour vérifier diverses propriétés dans un appartement intelligent: correction du comportement des capteurs de l’appartement, détection d’activité spécifiques de l’utilisateur (Activities of Daily Living, ADL) et composition de spécifications des deux catégories précédentes.En outre, nous élaborons sur l’utilisation de spécifications décentralisées pour la vérification décentralisée pendant l’exécution de programmes parallélisés. Nous commençons par discuter les limitations des approches et des outils existants lorsque les difficultés introduites par le parallélisme sont rencontrées. Nous détaillons la description de zones de parallélisme d’une unique exécution d’un programme et décrivons une approche générale qui permet de réutiliser des techniques de verification à l’éxécution existantes. Dans notre configuration, les moniteurs sont déployés dans des fils d’exécution spécifiques et échangent de l’information uniquement lorsque des points de synchronisation définis par le programme lui-même sont atteints. En utilisant les points de synchronisation existants, notre approche réduit les interférences et surcoûts résultant de la synchronisation, au prix d’un retard pour déterminer le verdict. / Runtime Verification (RV) is a lightweight formal method which consists in verifying that a run of a system is correct with respect to a specification. The specification formalizes the behavior of the system typically using logics or finite-state machines. While RV comprehensively deals with monolithic systems, multiple challenges are presented when scaling existing approaches to decentralized systems, that is, systems with multiple components with no central observation point. We focus particularly on three challenges: managing partial information, separating monitor deployment from the monitoring process itself, and reasoning about decentralization in a modular and hierarchical way. We present the notion of a decentralized specification wherein multiple specifications are provided for separate parts of the system. Decentralized specifications provide various advantages such as modularity, and allowing for realistic monitor synthesis of the specifications. We also present a general monitoring algorithm for decentralized specifications, and a general datastructure to encode automata execution with partial observations. We develop the THEMIS tool, which provides a platform for designing decentralized monitoring algorithms, metrics for algorithms, and simulation to better understand the algorithms, and design reproducible experiments.We illustrate the approach with two applications. First, we use decentralized specifications to perform a worst-case analysis, adapt, compare, and simulate three existing decentralized monitoring algorithms on both a real example of a user interface, and randomly generated traces and specifications. Second, we use decentralized specifications to check various specifications in a smart apartment: behavioral correctness of the apartment sensors, detection of specific user activities (known as activities of daily living), and composition of properties of the previous types.Furthermore, we elaborate on utilizing decentralized specifications for the decentralized online monitoring of multithreadedprograms. We first expand on the limitations of existing tools and approaches when meeting the challenges introduced by concurrency and ensure that concurrency needs to be taken into account by considering partial orders in traces. We detail the description of such concurrency areas in a single program execution, and provide a general approach which allows re-using existing RV techniques. In our setting, monitors are deployed within specific threads, and only exchange information upon reaching synchronization regions defined by the program itself. By using the existing synchronization, we reduce additional overhead and interference to synchronize at the cost of adding a delay to determine the verdict.

La sécurité est une exigence cruciale dans les applications basées sur l'information et la technologie de communication, surtout quand un réseau ouvert tel que l'Internet est utilisé. Pour assurer la sécurité dans ces applications des protocoles cryptographiques ont été développé. Cependant, la conception de protocoles de sécurité est notoirement difficile et source d'erreurs. Plusieurs failles ont été trouvées sur des protocoles qui se sont prétendus sécurisés. Par conséquent, les protocoles cryptographiques doivent être vérifiés avant d'être utilisés. Une approche pour vérifier les protocoles cryptographiques est l'utilisation des méthodes formelles, qui ont obtenu de nombreux résultats au cours des dernières années.Méthodes formelles portent sur l'analyse des spécifications des protocoles modélisées en utilisant, par exemple, les logiques dédiés, ou algèbres de processus. Les méthodes formelles peuvent trouver des failles ou permettent de prouver qu'un protocole est sécurisé sous certaines hypothèses par rapport aux propriétés de sécurité données. Toutefois, elles abstraient des erreurs de mise en ouvre et les attaques side-channel.Afin de détecter ces erreurs et la vérification des attaques d'exécution peut être utilisée pour analyser les systèmes ou protocoles exécutions. En outre, la vérification de l'exécution peut aider dans les cas où les procédures formelles mettent un temps exponentielle ou souffrent de problèmes de terminaison. Dans cette thèse, nous contribuons à la vérification des protocoles cryptographiques avec un accent sur la vérification formelle et l'automatisation. Tout d'abord, nous étudions les protocoles d'examen. Nous proposons des définitions formelles pour plusieurs propriétés d'authentification et de confidentialité dans le Pi-calcul Appliqué.Nous fournissons également une des définitions abstraites de propriétés de vérifiabilité. Nous analysons toutes ces propriétés en utilisant automatiquement ProVerif sur plusieurs études de cas, et avons identifié plusieurs failles. En outre, nous proposons plusieurs moniteurs de vérifier les exigences d'examen à l'exécution. Ces moniteurs sont validés par l'analyse d'un exécutions d'examen réel en utilisant l'outil MARQ Java.Deuxièmement, nous proposons un cadre formel pour vérifier les propriétés de sécurité de protocoles de monnaie électronique non transférable. Nous définissons la notion de vie privée du client et les propriétés de la falsification. Encore une fois, nous illustrons notre modèle en analysant trois études de cas à l'aide ProVerif, et confirmons plusieurs attaques connues.Troisièmement, nous proposons des définitions formelles de l'authentification, la confidentialité et les propriétés de vérifiabilité de protocoles de réputation électroniques. Nous discutons les définitions proposées, avec l'aide de ProVerif, sur un protocole de réputation simple. Enfin, nous obtenons un résultat sur la réduction de la vérification de la validité d'une route dans les protocoles de routage ad-hoc, en présence de plusieurs attaquants indépendants qui ne partagent pas leurs connaissances. / Security is a crucial requirement in the applications based on information and communication technology, especially when an open network such as the Internet is used.To ensure security in such applications cryptographic protocols have been used.However, the design of security protocols is notoriously difficult and error-prone.Several flaws have been found on protocols that are claimed secure.Hence, cryptographic protocols must be verified before they are used.One approach to verify cryptographic protocols is the use of formal methods, which have achieved many results in recent years.Formal methods concern on analysis of protocol specifications modeled using, e.g., dedicated logics, or process algebras.Formal methods can find flaws or prove that a protocol is secure under ``perfect cryptographic assumption" with respect to given security properties. However, they abstract away from implementation errors and side-channel attacks.In order to detect such errors and attacks runtime verification can be used to analyze systems or protocols executions.Moreover, runtime verification can help in the cases where formal procedures have exponential time or suffer from termination problems.In this thesis we contribute to cryptographic protocols verification with an emphasis on formal verification and automation.Firstly, we study exam protocols. We propose formal definitions for several authentication and privacy propertiesin the Applied Pi-Calculus. We also provide an abstract definitions of verifiability properties.We analyze all these properties automatically using ProVerif on multiple case studies, and identify several flaws.Moreover, we propose several monitors to check exam requirements at runtime. These monitors are validated by analyzing a real exam executions using MARQ Java based tool.Secondly, we propose a formal framework to verify the security properties of non-transferable electronic cash protocols.We define client privacy and forgery related properties.Again, we illustrate our model by analyzing three case studies using ProVerif, and confirm several known attacks.Thirdly, we propose formal definitions of authentication, privacy, and verifiability properties of electronic reputation protocols. We discuss the proposed definitions, with the help of ProVerif, on a simple reputation protocol.Finally, we obtain a reduction result to verify route validity of ad-hoc routing protocols in presence of multiple independent attackers that do not share their knowledge.