Les équipements intelligents, notamment les smartphones, sont la cible de nombreuses attaques de sécurité. Par ailleurs, la mise en œuvre de mécanismes de protection usuels est souvent inadaptée du fait de leurs ressources fortement contraintes. Dans ce contexte, nous proposons d'utiliser des chaînes de fonctions de sécurité qui sont composées de plusieurs services de sécurité, tels que des pare-feux ou des antivirus, automatiquement configurés et déployés dans le réseau. Cependant, ces chaînes sont connues pour être difficiles à valider. Cette difficulté est causée par la complexité de ces compositions qui impliquent des centaines, voire des milliers de règles de configuration. Dans cette thèse, nous proposons l'architecture d'un orchestrateur exploitant la programmabilité des réseaux pour automatiser la configuration et le déploiement de chaînes de fonctions de sécurité. Il est important que ces chaînes de sécurité soient correctes afin d’éviter l'introduction de failles de sécurité dans le réseau. Aussi, notre orchestrateur repose sur des méthodes automatiques de vérification et de synthèse, encore appelées méthodes formelles, pour assurer la correction des chaînes. Notre travail appréhende également l'optimisation du déploiement des chaînes dans le réseau, afin de préserver ses ressources et sa qualité de service. / Smart environments, in particular smartphones, are the target of multiple security attacks. Moreover, the deployment of traditional security mechanisms is often inadequate due to their highly constrained resources. In that context, we propose to use chains of security functions which are composed of several security services, such as firewalls or antivirus, automatically configured and deployed in the network. Chains of security functions are known as being error prone and hard to validate. This difficulty is caused by the complexity of these constructs that involve hundreds and even thousands of configuration rules. In this PhD thesis, we propose the architecture of an orchestrator, exploiting the programmability brought by software defined networking, for the automated configuration and deployment of chains of security functions. It is important to automatically insure that these security chains are correct, before their deployment in order to avoid the introduction of security breaches in the network. To do so, our orchestrator relies on methods of automated verification and synthesis, also known as formal methods, to ensure the correctness of the chains. Our work also consider the optimization of the deployment of chains of security functions in the network, in order to maintain its resources and quality of service.

La préservation de propriétés établies sur le programme source jusqu'au code exécutable est un point important dans les méthodes formelles. Cette propriété de préservation est établie par la vérification formelle du proccessus de compilation. Un compilateur est formellement vérifié s'il est accompagné d'une preuve de préservation sémantique : "si la compilation réussit, le code compilé se comporte comme le code source le prédit." Le projet CompCert étudie la vérification formelle de compilateurs réalistes utilisable dans l'embarqué-critique. Il s'agit de développer et formellement vérifier de tels compilateur via l'assistant de preuve Coq. Un compilateur pour le langage C vers l'assembleur PowerPC a déjà ainsi été produit. Le code exécutable du compilateur a été obtenu en deux étapes non vérifiés : la génération automatique de code Ocaml par le mécanisme d'extration de Coq et la compilation du de ce code extrait par le système Objective Caml. En fait, cette lacune est commune à tous les développements spécifiés dans l'assistant de preuve Coq et destinés à produire un éxécutable. Cette thèse décrit l'étude, le développement et la vérification formelle, dans l'assistant de preuve Coq, d'un compilateur pour le fragment purement fonctionnel du langage ML : le langage cible du mécanisme d'extraction de Coq. Concrètement, il s'git d'une chaîne de compilation en amont pour mini-ML (lambda calcul, let, letrec et filtrage) vers le premier langage intermédiaire de la chaîne de compilation en aval du compilateur CompCert. Ce langage, Cminor, est un langage de bas niveau à la C. L'expressivité du langage source traité rend ce compilateur réaliste. Il comporte aussi des optimisations classiques propre à la compilation de langages fonctionnels : la décurryfication, comme celle implémentée dans le compilateur OCaml ; la représentation uniforme des données, explicitation des fermetures, numérotation des constructeurs et une mise en style par passage de continuation (CPS) optimisée. Le point fort de ce compilateur et que, comme les compilateurs modernes pour langage de haut niveau, il peut interagir avec un gestionnaire de mémoire automatique. Cette interaction a aussi été formellement vérifiée.

L'utilisation omniprésente des systèmes informatiques impose de s'assurer de leur bon fonctionnement. Dans ce but, les méthodes de vérification formelle permettent de suppléer les simulations qui ne peuvent être complètement exhaustives du fait de la complexité croissante des systèmes. Le model checking fait partie de ces méthodes et présente l'avantage d'être complètement automatisée. Cette méthode consiste à développer des algorithmes pour vérifier qu'une spécification exprimée la plupart du temps sous la forme d'une formule logique est satisfaite par un modèle du système. Les langages historiques de spécification utilisent comme formules atomiques des variables propositionnelles qui permettent d'exprimer principalement des propriétés portant sur les états de contrôle du modèle. Le but de cette thèse est de vérifier des propriétés plus riches portant sur diverses données manipulées par les modèles: des compteurs, des horloges ou des queues. Ces données peuvent prendre une infinité de valeurs et induisent donc des modèles avec un nombre infini d'états. Nous définissons un cadre général pour l'extension des logiques temporelles avec des contraintes permettant de comparer la valeur des variables a différents états de l'exécution. Nous établissons des résultats de décidabilité et complexité pour des problèmes de model checking impliquant diverses instances de ces extensions. Nous privilégions pour cela l'approche à base d'automates en combinant des constructions connues pour les logiques propositionnelles classiques avec des méthodes d'abstraction des modèles dont les variables sont interprétées dans des domaines infinis.

Cette thèse propose une Démarche de Vérification Formelle d'Architectures Logicielles : DVFAL. La démarche DVFAL supporte divers formalismes de description d'architectures logicielles tels que : les ADL (langages de description d'architectures), UML2.0, Symphony et des profils UML2.0 dédiés au domaine des architectures logicielles. La démarche DVFAL préconise l'ADL Wright en tant que langage formel pivot permettant de représenter des architectures logicielles décrites dans les divers formalismes. En outre, elle propose des transformations de modèles sous forme des traducteurs (Wright vers CSP de Hoare et Wright vers Ada) pour bénéficier des outils de vérification des propriétés supportant CSP et Ada tels que FDR et FLAVERS. Enfin, la démarche DVFAL propose un profil UML2.0-Wright jouant le rôle d'un langage intermédiaire entre les formalismes à base d'UML et Wright.

Nos travaux de recherche consistent à apporter des solutions de modélisation conformément à l'approche MDA. Nos recherches consistent à fournir des solutions permettant de guider et d'assister les activités de modélisation des architectures logicielles. Il s'agit principalement de proposer une démarche de conception orientée modèle permettant de décrire l'architecture logicielle en tenant compte de trois aspects : le style architectural, les opérations de reconfiguration et le protocole de reconfiguration.<br />Nous proposons des notations visuelles permettant de décrire de façon compatible avec UML 2.0 l'architecture logicielle. La technique de description que nous adoptons est orientée règles, basée sur les théories de transformation de graphe, permettant, ainsi, de décrire la dynamique structurelle.<br />Nous proposons une extension d'UML 2.0 par un nouveau profil formé de trois méta-modèles. Nous proposons aussi une approche de validation basée sur des règles intra-modèle et des règles inter-modèles. Nous adoptons également une approche de vérification. Cette approche permet, dans une première étape, une transformation automatique du style architectural et de chaque opération de reconfiguration vers le langage Z. Elle permet dans une deuxième étape, de vérifier la consistance du style architectural et la conformité de l'évolution d'une architecture vis-à-vis de son style architectural. Nous utilisons le système de preuve Z/EVES. Finalement, nous proposons une démarche de modélisation des architectures logicielles dynamiques, appelée X, permettant de décrire les différentes étapes pour modéliser l'architecture logicielle. La démarche proposée est inspirée de la méthode MDA et 2TUP.<br />Le profil et la démarche X que nous avons proposés ont fait l'objet d'une implémentation et d'une intégration, sous forme de plug-in java, dans l'atelier d'aide à la conception FUJABA. Le plug-in implémenté est disponible sur l'URL : http://www.laas.fr/~khalil/TOOLS/X.zip.

Lustre est un langage de programmation spécialement conçu pour la réalisation des systèmes réactifs. Le besoin de garantir que ces systèmes ont un comportement conforme a celui attendu nécessite de définir et de mettre en œuvre des méthodes de vérification formelle des programmes lustre, qui sont relatées dans cette thèse. La vérification d'un système consiste a contrôler que tous ses comportements sont corrects vis-a-vis de ses spécifications. Les comportements d'un programme lustre peuvent classiquement être représentés par une machine d'états finis, dont la génération permet de vérifier ses spécifications. La methode standard mettant en œuvre ce principe est limitée par le probleme d'explosion de la machine générée, qui n'est pas minimale. Un nouvel algorithme évitant ce probleme est présenté. Son implémentation nécessite l'emploi d'une technique de représentation et de manipulation symbolique de la machine (bdds), dont le cout d'utilisation est largement abaisse grâce a de nombreuses optimisations. Basées sur cette technique, deux autres implémentations originales de la methode standard et de la nouvelle methode proposée ci-dessus sont décrites. Les aspects de diagnostic correspondant au cas ou les programmes sont incorrects vis-a-vis de leurs spécifications sont aussi abordes

Le couplage des approches orientées objets avec la méthode B est une piste pour l'amélioration de l'activité de spécification et de développement de logiciels. La méthode B fournit des notations et des outils supports puissants permettant de modéliser et de vérifier des modèles. Les approches objets fournissent des mécanismes intéressants pour la structuration et le développement de gros systèmes. L'apport de notre travail de thèse contribue aux activités de couplage entre ces deux formalismes en utilisant le prouveur de B pour valider et vérifier des spécifications UML.<br /><br />En étendant les schémas de dérivation d'UML vers B proposés dans des travaux précédents réalisés dans l'équipe de recherche Dédale, nous proposons une approche de dérivation en B de méta-modèles UML, de diagrammes statiques et de diagrammes dynamiques. L'objectif de cette proposition est de vérifier la sémantique et la cohérence entre différents diagrammes de spécifications UML.<br /><br />Notre thèse apporte aussi une contribution au développement de spécifications objets en utilisant la méthode B. La première proposition concerne la prise en compte de certains types d'associations entre classes lors de la dérivation en B. La deuxième proposition concerne la validation de spécifications orientées objets décrites à l'aide de diagrammes de séquence UML2.0.

Les systèmes d'édition collaborative permettent à plusieurs utilisateurs d'éditer simultanément un document. Aujourd'hui, l'édition collaborative massive est une réalité. Il ne s'agit plus d'éditer à quelques utilisateurs mais à des milliers d'utilisateurs répartis dans le monde. Les éditeurs collaboratifs actuels n'ont pas été conçus pour supporter un nombre si important d'utilisateurs. Les problèmes soulevés ne sont pas d'ordre technologique, ils remettent en cause les fondements algorithmiques des éditeurs. L'objectif de cette thèse est de proposer des algorithmes adaptés à l'édition collaborative massive. Nous montrons qu'un tel algorithme doit assurer trois critères : convergence des données, préservation des intentions et passage à l'échelle. Au regard de l'état de l'art, seul le modèle des transformées opérationnelles (OT) peut concilier ces trois critères.<br />La première contribution de cette thèse montre que l'approche OT conçue pour des éditeurs temps réel peut être utilisée pour réaliser des outils asynchrones. Nous avons réalisé un gestionnaire de configurations dénommé SO6. La seconde contribution est une approche formelle à la conception et à la vérification de fonctions de transformation pour le modèle OT. Cette approche repose sur un démonstrateur automatique de théorème. Avec cette approche, nous montrons que toutes les fonctions de transformation proposées jusqu'ici sont fausses. La troisième et dernière contribution de ce travail est un nouvel algorithme de réplication optimiste (WOOT) adapté à l'édition collaborative massive de structures linéaires. Ce modèle repose sur le calcul monotone d'une extension linéaire des ordres partiels formés par les relations entre les différents éléments de la structure.

La vérification formelle de systèmes concurrents temps réels se heurte au problème de l'explosion du nombre d'états à explorer. Ce problème connu sous le nom ``d'explosion combinatoire'' à plusieurs causes. Cette thèse s'intéresse à deux d'entre-elles. · Pour lutter contre l'explosion due à la représentation du parallélisme par l'entrelacement d'actions, cette thèse propose des techniques basées sur l'approche des ordres-partiels pour construire un graphe réduit. Pour exploiter les ordres-partiels, les techniques proposées utilisent la construction de « pas de transitions » afin de limiter le nombre d'états explorés. Différentes constructions des « pas de transitions » sont proposées en fonction de la classe de propriétés que l'on souhaite préserver (Blocages, Équivalence de traces, LTL). · Pour lutter contre l'explosion due aux contraintes temporelles, cette thèse propose une approche par sur-approximation du comportement. L'objectif est d'avoir un graphe abstrait du comportement de la sur-approximation plus petit que celui du système. Comme classiquement, les techniques d'abstractions permettent d'obtenir une procédure de décision semi-effective. Lorsque l'analyse de la sur-approximation ne permet pas de conclure, la thèse propose une méthode effective permettant de conclure pour les formules de LTL: le système est analysé, guidé par les résultats obtenus sur la sur-approximation. Cette thèse présente les algorithmes de ces différentes techniques de réduction et l'outil tina (http://www.laas.fr/tina) dans lequel ils ont été implémentés.

Nous considérons une sous classe d'automates temporisés probabilistes où les contraintes temporelles au niveau des gardes et des invariants sont exprimées par des paramètres. Cette sous classe est appelée la classe des automates Temporisés Probabilistes Paramétrés Semi Déterminés (ATPP Semi Déterminés). Cette classe d'automates se définit en particulier par l'attribution d'une unique distribution à chaque état et par des gardes de la forme x<=a où a est un paramètre ou un entier naturel. Nous imposons de plus deux propriétés sur ces automates qui sont celles de non blocage et fortement non zenon. Notre travail vise à calculer le temps moyen maximal de convergence vers un état dit absorbant q_end dans ce type d'automates. L'unique méthode traitant déjà ce type de problème fait appel à la discrétisation du temps et à l'application de techniques de programmation linéaire. Elle est cependant exponentielle car elle dépend du nombre d'horloges et de la plus grande constante à laquelle sont comparées les horloges, lors de la discrétisation. Le graphe résultant peut être de taille exponentielle. Pour tout ATPP Semi Déterminé, on définit un automate totalement déterministe, appelé ATPP Déterminé, en remplaçant toute garde de la forme x<=a par une garde de la forme x=a. Le temps d'attente en chaque état est ainsi fixé par la valuation de l'état initial qui remet toutes les horloges à zéro. Nous démontrons que le temps moyen de convergence vers q_end dans l'ATPP Déterminé est égal au temps moyen maximal de convergence dans l'ATPP Semi Déterminé dont il découle. Pour calculer le temps moyen de convergence vers q_end nous construisons à partir de l'ATPP Déterminé un graphe appelé "graphe des macro-steps" qui contient de façon concise l'information nécessaire au calcul du coût moyen de convergence vers q_end. Ce graphe est de taille polynomiale et se construit en temps polynomial. Le calcul du temps moyen de convergence dans le graphe des macro-steps est solution d'un système linéaire, comme dans le cas des chaînes de Markov avec coûts. On résout ce système linéaire en temps polynomial, ce qui permet d'obtenir finalement le temps moyen maximal de convergence vers q_end dans l'ATPP Semi Déterminé. Nous appliquons enfin cette méthode à certains protocoles de communication, notamment BRP (Bounded Retransmission Protocol) et CSMA/CD (Carrier Sense Multiple Access with Collision Detection).