Cette thèse propose une approche d'aide à la conception et au développement de modèles formels B. Cette approche se base sur la construction d'un système de transitions symboliques décrivant les comportements du modèle. Cette seconde vue est complémentaire avec la description orientée données du modèle B et peut être utilisée pour le décrire, le documenter ou le valider. Le système de transitions est élaboré à partir d'un espace d'états fourni par l'utilisateur et les transitions sont construites par résolution d'obligations de preuve. Nous proposons également de prendre en compte le processus de raffinement B en introduisant la notion de hiérarchie dans les systèmes de transitions. Cette représentation permet de mettre en évidence le lien entre les données des différents niveaux de raffinement. De plus, la méthode que nous proposons se base sur la décomposition des états d'une représentation du modèle abstrait, permettant ainsi de conserver la structure générale du système. Enfin, nous terminons ce manuscrit en décrivant l'outil GénéSyst qui implante cette méthode, ainsi que son utilisation dans le cadre du projet GECCOO, pour la vérification de propriétés de sécurité.

Dans cette thèse nous nous intéressons à une technique de vérification basée sur les approximations par réécriture dans le but de l'automatiser et d'étendre son domaine d'application. L'utilisation de cette technique permet la vérification de propriétés pour des systèmes informatique. Une sur-approximation des termes atteignables par réécriture est calculée et nous pouvons déterminer si des termes indésirables (représentant la propriété) appartiennent à la sur-approximation. Si ils n'appartiennent pas à la sur-approximation alors on est sûr que les termes indésirables ne sont pas atteignables par le système et la propriété est vérifiée, sinon nous ne pouvons pas conclure à cause de la sur-approximation. C'est dans ce cadre que se placent les contributions de cette thèse. Tout d'abord nous présentons une méthode de raffinement d'approximation, s'inspirant du paradigme CEGAR (Counterexample-Guided Abstraction Refinement), déterminant comment construire automatiquement une approximation qui ne contient pas de terme indésirable. Si cette construction échoue alors des termes indésirables sont atteignables et on peut conclure que le système analysé ne vérifie pas la propriété. De plus, à partir d'un graphe des réécritures, nous présentons comment vérifier trois modèles de propriétés LTL exprimant des conditions sur l'ordre d'application des règles de réécriture. D'autre part, nous présentons dans cette thèse deux nouvelles applications de cette technique : la vérification de spécifications écrites avec l'algèbre de processus CCS (sans renommage) et l'analyse d'atteignabilité par approximation de deux problèmes indécidables pour les machines de Turing.

Malgré les progrès importants effectués en matière de conception de logiciels et l'existence de méthodes de développement éprouvées, il faut reconnaître que les défaillances de systèmes causées par des logiciels restent fréquentes. Il arrive même que ces défaillances concernent des logiciels critiques et provoquent des dommages significatifs. Considérant l'importance des intérêts en jeu, et le fait que la garantie de logiciel "zéro défaut" est hors d'atteinte, il est donc important de pouvoir déterminer en cas de dommages causés par des logiciels les responsabilités des différentes parties. Pour établir ces responsabilités, un certain nombre de conditions doivent être réunies: (i) on doit pouvoir disposer d'éléments de preuve fiables, (ii) les comportements attendus des composants doivent avoir été définis préalablement et (iii) les parties doivent avoir précisé leurs intentions en matière de répartition des responsabilités. Dans cette thèse, nous apportons des éléments de réponse à ces questions en proposant un cadre formel pour spécifier et établir les responsabilités en cas de dysfonctionnement d'un logiciel. Ce cadre formel peut être utilisé par les parties dans la phase de rédaction du contrat et pour concevoir l'architecture de logs du système. Notre première contribution est une méthode permettant d'intégrer les définitions formelles de responsabilité et d'éléments de preuves dans le contrat juridique. Les éléments de preuves sont fournis par une architecture de logs dite "acceptable" qui dépend des types de griefs considérés par les parties. La seconde contribution importante est la définition d'une procédure incrémentale, qui est mise en ?uvre dans l'outil LAPRO, pour l'analyse incrémentale de logs distribués.

Grâce aux progrès récents en photogrammétrie, il est désormais possible de reconstruire automatiquement un modèle d'une scène 3D à partir de photographies ou d'une vidéo. La reconstruction est réalisée en plusieurs étapes. Tout d'abord, on détecte des traits saillants (features) dans chaque image, souvent des points mais plus généralement des régions. Puis on cherche à les mettre en correspondance entre images. On utilise ensuite les traits communs à deux images pour déterminer la pose (positions et orientations) relative des images. Puis les poses sont mises dans un même repère global et la position des traits saillants dans l'espace est reconstruite (structure from motion). Enfin, un modèle 3D dense de la scène peut être estimé. La détection de traits saillants, leur appariement, ainsi que l'estimation de la position des caméras, jouent des rôles primordiaux dans la chaîne de reconstruction 3D. Des imprécisions ou des erreurs dans ces étapes ont un impact majeur sur la précision et la robustesse de la reconstruction de la scène entière. Dans cette thèse, nous nous intéressons à l'amélioration des méthodes pour établir la correspondance entre régions caractéristiques et pour les sélectionner lors de l'estimation des poses de caméras, afin de rendre les résultats de reconstruction plus robustes et plus précis. Nous introduisons tout d'abord une contrainte photométrique pour une paire de correspondances (VLD) au sein d'une même image, qui est plus fiable que les contraintes purement géométriques. Puis, nous proposons une méthode semi-locale (K-VLD) pour la mise en correspondance, basée sur cette contrainte photométrique. Nous démontrons que notre méthode est très robuste pour des scènes rigides, mais aussi non-rigides ou répétitives, et qu'elle permet d'améliorer la robustesse et la précision de méthodes d'estimation de poses, notamment basées sur RANSAC. Puis, pour améliorer l'estimation de la position des caméras, nous analysons la précision des reconstructions et des estimations de pose en fonction du nombre et de la qualité des correspondances. Nous en dérivons une formule expérimentale caractérisant la relation ``qualité contre quantité''. Sur cette base, nous proposons une méthode pour sélectionner un sous-ensemble des correspondances de meilleure qualité de façon à obtenir une très haute précision en estimation de poses. Nous cherchons aussi raffiner la précision de localisation des points en correspondance. Pour cela, nous développons une extension de la méthode de mise en correspondance aux moindres carrés (LSM) en introduisant un échantillonnage irrégulier et une exploration des échelles d'images. Nous montrons que le raffinement et la sélection de correspondances agissent indépendamment pour améliorer la reconstruction. Combinées, les deux méthodes produisent des résultats encore meilleurs / With the recent progress in photogrammetry, it is now possible to automatically reconstruct a model of a 3D scene from pictures or videos. The model is reconstructed in several stages. First, salient features (often points, but more generally regions) are detected in each image. Second, features that are common in images pairs are matched. Third, matched features are used to estimate the relative pose (position and orientation) of images. The global poses are then computed as well as the 3D location of these features (structure from motion). Finally, a dense 3D model can be estimated. The detection of salient features, their matching, as well as the estimation of camera poses play a crucial role in the reconstruction process. Inaccuracies or errors in these stages have a major impact on the accuracy and robustness of reconstruction for the entire scene. In this thesis, we propose better methods for feature matching and feature selection, which improve the robustness and accuracy of existing methods for camera position estimation. We first introduce a photometric pairwise constraint for feature matches (VLD), which is more reliable than geometric constraints. Then we propose a semi-local matching approach (K-VLD) using this photometric match constraint. We show that our method is very robust, not only for rigid scenes but also for non-rigid and repetitive scenes, which can improve the robustness and accuracy of pose estimation methods, such as based on RANSAC. To improve the accuracy in camera position estimation, we study the accuracy of reconstruction and pose estimation in function of the number and quality of matches. We experimentally derive a “quantity vs. quality” relation. Using this relation, we propose a method to select a subset of good matches to produce highly accurate pose estimations. We also aim at refining match position. For this, we propose an improvement of least square matching (LSM) using an irregular sampling grid and image scale exploration. We show that match refinement and match selection independently improve the reconstruction results, and when combined together, the results are further improved

Cette thèse se situe dans le contexte de la vérification fonctionnelle des circuits intégrés complexes. L’objectif de ce travail est de créer un flot de vérification conjoint au flot de conception basé sur une technique appelée "vérification basée sur les assertions(ABV)". Le concept de base du flot est le raffinement automatique des spécifications formelles données sous la forme d’assertions PSL du niveau TLM au niveau RTL. La principale difficulté est la disparité des deux domaines : au niveau TLM, les communications sont modélisées par des appels de fonctions atomiques. Au niveau RTL, les échanges sont assurés par des signaux binaires évoluant selon un protocole de communication précis. Sur la base d’un ensemble de règles de transformation temporelles formelles, nous avons réalisé un outil permettant d’automatiser le raffinement de ces spécifications. Comme le raffinement des modèles, le raffinement des assertions n’est pas entièrement automatisable : des informations temporelles et structurelles doivent être fournies par l’utilisateur. L’outil réalise la saisie de ces informations de façon ergonomique, puis procède automatiquement à la transformation temporelle et structurelle de l’assertion. Il permet la génération d’assertions RTL mais aussi hybrides. Les travaux antérieurs dans ce domaine sont peu nombreux et les solutions proposées imposent de fortes restrictions sur les assertions considérées. À notre connaissance, le prototype que nous avons mis en oeuvre est le premier outil qui réalise un raffinement temporel fondé sur la sémantique formelle d’un langage de spécification standard (PSL). / The context of this thesis is the functional verification of complex integrated circuits.The objective of our work is to create a seamless verification flow joint to the design flowand based on a proved technique called Assertions-Based Verification (ABV). The mainchallenge of TLM to RTL refinement is the disparity of these two domains : at TLM,communications are modeled as atomic function calls handling all the exchanged data.At RTL, communications are performed by signals according to a specific communicationprotocol. The proposed temporal transformation process is based on a set of formaltransformation rules. We have developed a tool performing the automatic refinement ofPSL specifications. As for design refinement assertion refinement is not fully automated.Temporal and structural information must be provided by the user, using an ergonomicinterface. The tool allows the generation of assertions in RTL but also hybrid assertions.Little work has been done before in this area, and the proposed solutions suffer from severerestrictions. To our knowledge, our prototype is the first tool that performs a temporaltransformation of assertions based on the formal semantics of a standard specificationlanguage (PSL).

Ces travaux concernent la modélisation formelle d’exigences et les interactions entre agents. Nous y avons développé un langage de modélisation pour les exigences d’un système à élaborer, KHI. En s’inspirant notamment des méthodes KAOS et TROPOS-i*, KHI synthétise les concepts essentiels relatifs aux buts et aux agents. Il permet en particulier d’exprimer la question de la capacité effective des agents à assurer la satisfaction des spécifications qui leurs sont assignées. Nous appelons cette question le problème de l’assignation. Dans KHI, nous exprimons ce problème comme la question de la satisfaction d’un certain nombre de critères de correction par un modèle. Pour donner un formalisme aux concepts de KHI et un moyen de résolution du problème de l’assignation, nous introduisons également une logique temporelle multi-agents, USL. Elle s’inspire des travaux dans le domaine, en particulier ATL*sc et SL. Comme ces derniers formalismes, elle utilise des contextes de stratégies pour exprimer des capacités d’agents à assurer la satisfaction de propriétés temporelles. Elle se distingue des autres formalismes existants principalement par deux aspects : d’abord elle utilise des stratégies non-déterministes. Nous les appelons des multi-stratégies. Nous pouvons ainsi exprimer des propriétés de raffinement entre les multi-stratégies. Par ailleurs, nous utilisons pour USL des exécutions du système qui ne sont pas nécessairement infinies. Nous pouvons alors formaliser les notions d’engagement contradictoire pour un agent et de capacités d’actions conflictuelles pour un ensemble d’agents. Nous réduisons ensuite la satisfaction des critères de correction qui expriment le problème de l’assignation dans KHI à des instances du problème de model-checking pour une version adéquate de USL, USLKHI . Nous donnons un algorithme de résolution pour ce problème, il tourne en espace polynomial. L’ensemble des concepts et des outils présentés est par ailleurs illustré par un cas d’étude décrivant des missions d’observation spatiale. / These studies relate to modeling languages for requirements engineering. The aim is to provide tools for the evaluation of agents' capacity to ensure the satisfaction of their assigned specifications (we talk of "the assignment problem"). To do so, we first develop a modeling language (Khi). Then we give a set of assignment correctness criteria for systems that are modelled as instances of Khi. We also develop a formal tool, USLKhi, for wich we solve the model checking problem. We reduce the different correctness criteria for Khi instances to instances of the model checking problem for USLKhi. Thus as a whole, our proposition enables to express, formalise and solve the assignment problem. We also illustrate the set of concepts and tools that are presented with a case study featuring spatial observation missions.

Malgré les progrès importants effectués en matière de conception de logiciels et l'existence de méthodes de développement éprouvées, il faut reconnaître que les défaillances de systèmes causées par des logiciels restent fréquentes. Il arrive même que ces défaillances concernent des logiciels critiques et provoquent des dommages significatifs. Considérant l'importance des intérêts en jeu, et le fait que la garantie de logiciel "zéro défaut" est hors d'atteinte, il est donc important de pouvoir déterminer en cas de dommages causés par des logiciels les responsabilités des différentes parties. Pour établir ces responsabilités, un certain nombre de conditions doivent être réunies: (i) on doit pouvoir disposer d'éléments de preuve fiables, (ii) les comportements attendus des composants doivent avoir été définis préalablement et (iii) les parties doivent avoir précisé leurs intentions en matière de répartition des responsabilités. Dans cette thèse, nous apportons des éléments de réponse à ces questions en proposant un cadre formel pour spécifier et établir les responsabilités en cas de dysfonctionnement d'un logiciel. Ce cadre formel peut être utilisé par les parties dans la phase de rédaction du contrat et pour concevoir l'architecture de logs du système. Notre première contribution est une méthode permettant d'intégrer les définitions formelles de responsabilité et d'éléments de preuves dans le contrat juridique. Les éléments de preuves sont fournis par une architecture de logs dite "acceptable" qui dépend des types de griefs considérés par les parties. La seconde contribution importante est la définition d'une procédure incrémentale, qui est mise en ?uvre dans l'outil LAPRO, pour l'analyse incrémentale de logs distribués. / Despite the effort made to define methods for the design of high quality software, experience shows that failures of IT systems due to software errors remain very common and one must admit that even critical systems are not immune from that type of errors. One of the reasons for this situation is that software requirements are generally hard to elicit precisely and it is often impossible to predict all the contexts in which software products will actually be used. Considering the interests at stake, it is therefore of prime importance to be able to establish liabilities when damages are caused by software errors. Essential requirements to define these liabilities are (1) the availability of reliable evidence, (2) a clear definition of the expected behaviors of the components of the system and (3) the agreement between the parties with respect to liabilities. In this thesis, we address these problems and propose a formal framework to precisely specify and establish liabilities in a software contract. This framework can be used to assist the parties both in the drafting phase of the contract and in the definition of the architecture to collect evidence. Our first contribution is a method for the integration of a formal definition of digital evidence and liabilities in a legal contract. Digital evidence is based on distributed execution logs produced by "acceptable log architectures". The notion of acceptability relies on a formal threat model based on the set of potential claims. Another main contribution is the definition of an incremental procedure, which is implemented in the LAPRO tool, for the analysis of distributed logs.

Cette thèse, intitulée NSIBM : un solveur parallèle de Navier-Stokes avec raffinement automatique basé sur la méthode des frontières immergées, a été effectuée au sein du laboratoire iCube, département de mécanique, à Strasbourg, dans le quartier de l'Orangerie, sous la direction du professeur Yannick Hoarau. L'essentiel du travail effectué consiste en le développement d'un programme capable de résoudre numériquement l'équation de Navier-Stokes qui régit des fluides en mouvement. Une attention particulière a été portée à la production de maillages conformes aux géométries proposées et à leur génération. Les moyens mis en œuvre ici pour gérer l'éternel problème de la finesse du maillage opposée au trop grand nombre de cellules sont multiples : le raffinement, la parallélisation et les frontières immergées. Dans un premier temps, j'ai conçu un générateur de maillage en deux et trois dimensions en y intégrant la possibilité de diviser des cellules, et cela de manière automatique, par des critères géométriques, numériques ou physiques. Il permet également de supprimer des cellules, de manière à ne pas mailler le vide ou les parties solides de la géométrie.Dans un deuxième temps, j'ai rendu ce code parallèle en lui donnant la capacité d'utiliser plusieurs processeurs, afin de calculer plus vite et donc d'utiliser davantage de mailles. Cette étape fait appel à deux technologies : Metis, qui partage équitablement les mailles sur le nombre choisi de processeurs et OpenMPI, qui est l'interface de communication entre ces processeurs. Enfin, la méthode des frontières immergées a été introduite au code pour gérer les bords non verticaux ou horizontaux dans un maillage cartésien, c'est-à-dire formé de rectangles ou de pavés droits. Elle consiste à donner un caractère hybride à une cellule traversée par une frontière par l'introduction d'un terme numérique de forçage simulant la présence de la paroi.Ce travail de développement a ensuite été mis à l'épreuve et validé dans une série de cas tests en deux comme en trois dimensions. Des exemples de maillages complexes générés facilement sont donnés. / This thesis, entitled NSIBM: a parallel Navier-Stokes solver with automatic mesh refinement based on immersed boundary method, has been conducted within the iCube laboratory dedicated to mechanics and located in Strasbourg. It has been supervised by Professor Yannick Hoarau. This work mainly deals with coding a program able to solve the Navier-Stokes equations that governs moving fluids, in a numerical way. Particular attention was paid to the production of meshes that suit given geometries and their generation.The means used here to handle the eternal problem of the fineness of the mesh opposed to too many cells are several~:refinement, parallelization and the immersed boundary method.Initially, I designed a two and three-dimensional mesh generator that includes the possibility of dividing cells,in an automatic way, by geometrical, numerical or physical criteria. It also allows to remove cells, where there is no point keeping it. Secondly, I parallelized the program by giving him the ability to use multiple processors to calculate faster and therefore use bigger meshes.This step uses two available libraries~: \textit{Metis}, which gives a optimal mesh partition, and \textit{openMPI}, which deals with communication between nodes. Finally, the immersed boundary method has been implemented to handle non-vertical or non-horizontal edges in a cartesian grid. Its principle is to confer a hybrid status to a cell which is crossed by an edge by adding a numerical force term simulating the presence of the boundary. This development work was then tested and validated in a serie of test cases in two and three dimensions. Examples of complex meshes easily generated are given.

Dans le contexte des sciences archéologiques, des images tridimensionnelles issues de scanners tomodensitométriques sont segmentées en régions d’intérêt afin d’en faire une analyse. Ces objets virtuels sont souvent utilisés dans le but d’effectuer des mesures précises. Une partie de ces analyses nécessite d’extraire la surface des régions d’intérêt. Cette thèse se place dans ce cadre et vise à améliorer la précision de l’extraction de surface. Nous présentons dans ce document nos contributions : tout d’abord, l’algorithme du HMH pondéré dont l’objectif est de positionner précisément un point à l’interface entre deux matériaux. Appliquée à une extraction de surface, cette méthode pose des problèmes de topologie sur la surface résultante. Nous avons donc proposé deux autres méthodes : la méthode du HMH discret qui permet de raffiner la segmentation d’objet 3D, et la méthode du HMH surfacique qui permet une extraction de surface contrainte garantissant l’obtention d’une surface topologiquement correcte. Il est possible d’enchainer ces deux méthodes sur une image 3D pré-segmentée afin d’obtenir une extraction de surface précise des objets d’intérêt. Ces méthodes ont été évaluées sur des acquisitions simulées d’objets synthétiques et des acquisitions réelles d’artéfacts archéologiques. / In the context of archaeological sciences, 3D images produced by Computer Tomography scanners are segmented into regions of interest corresponding to virtual objects in order to make some scientific analysis. These virtual objects are often used for the purpose of performing accurate measurements. Some of these analysis require extracting the surface of the regions of interest. This PhD falls within this framework and aims to improve the accuracy of surface extraction. We present in this document our contributions : first of all, the weighted HMH algorithm whose objective is to position precisely a point at the interface between two materials. But, applied to surface extraction, this method often leads to topology problems on the resulting surface. So we proposed two other methods : The discrete HMH method which allows to refine the 3D object segmentation, and the surface HMH method which allows a constrained surface extraction ensuring a topologically correct surface. It is possible to link these two methods on a pre-segmented 3D image in order to obtain a precise surface extraction of the objects of interest These methods were evaluated on simulated CT-scan acquisitions of synthetic objects and real acquisitions of archaeological artefacts.

Grâce aux progrès récents en photogrammétrie, il est désormais possible de reconstruire automatiquement un modèle d'une scène 3D à partir de photographies ou d'une vidéo. La reconstruction est réalisée en plusieurs étapes. Tout d'abord, on détecte des traits saillants (features) dans chaque image, souvent des points mais plus généralement des régions. Puis on cherche à les mettre en correspondance entre images. On utilise ensuite les traits communs à deux images pour déterminer la pose (positions et orientations) relative des images. Puis les poses sont mises dans un même repère global et la position des traits saillants dans l'espace est reconstruite (structure from motion). Enfin, un modèle 3D dense de la scène peut être estimé. La détection de traits saillants, leur appariement, ainsi que l'estimation de la position des caméras, jouent des rôles primordiaux dans la chaîne de reconstruction 3D. Des imprécisions ou des erreurs dans ces étapes ont un impact majeur sur la précision et la robustesse de la reconstruction de la scène entière. Dans cette thèse, nous nous intéressons à l'amélioration des méthodes pour établir la correspondance entre régions caractéristiques et pour les sélectionner lors de l'estimation des poses de caméras, afin de rendre les résultats de reconstruction plus robustes et plus précis. Nous introduisons tout d'abord une contrainte photométrique pour une paire de correspondances (VLD) au sein d'une même image, qui est plus fiable que les contraintes purement géométriques. Puis, nous proposons une méthode semi-locale (K-VLD) pour la mise en correspondance, basée sur cette contrainte photométrique. Nous démontrons que notre méthode est très robuste pour des scènes rigides, mais aussi non-rigides ou répétitives, et qu'elle permet d'améliorer la robustesse et la précision de méthodes d'estimation de poses, notamment basées sur RANSAC. Puis, pour améliorer l'estimation de la position des caméras, nous analysons la précision des reconstructions et des estimations de pose en fonction du nombre et de la qualité des correspondances. Nous en dérivons une formule expérimentale caractérisant la relation ``qualité contre quantité''. Sur cette base, nous proposons une méthode pour sélectionner un sous-ensemble des correspondances de meilleure qualité de façon à obtenir une très haute précision en estimation de poses. Nous cherchons aussi raffiner la précision de localisation des points en correspondance. Pour cela, nous développons une extension de la méthode de mise en correspondance aux moindres carrés (LSM) en introduisant un échantillonnage irrégulier et une exploration des échelles d'images. Nous montrons que le raffinement et la sélection de correspondances agissent indépendamment pour améliorer la reconstruction. Combinées, les deux méthodes produisent des résultats encore meilleurs / With the recent progress in photogrammetry, it is now possible to automatically reconstruct a model of a 3D scene from pictures or videos. The model is reconstructed in several stages. First, salient features (often points, but more generally regions) are detected in each image. Second, features that are common in images pairs are matched. Third, matched features are used to estimate the relative pose (position and orientation) of images. The global poses are then computed as well as the 3D location of these features (structure from motion). Finally, a dense 3D model can be estimated. The detection of salient features, their matching, as well as the estimation of camera poses play a crucial role in the reconstruction process. Inaccuracies or errors in these stages have a major impact on the accuracy and robustness of reconstruction for the entire scene. In this thesis, we propose better methods for feature matching and feature selection, which improve the robustness and accuracy of existing methods for camera position estimation. We first introduce a photometric pairwise constraint for feature matches (VLD), which is more reliable than geometric constraints. Then we propose a semi-local matching approach (K-VLD) using this photometric match constraint. We show that our method is very robust, not only for rigid scenes but also for non-rigid and repetitive scenes, which can improve the robustness and accuracy of pose estimation methods, such as based on RANSAC. To improve the accuracy in camera position estimation, we study the accuracy of reconstruction and pose estimation in function of the number and quality of matches. We experimentally derive a “quantity vs. quality” relation. Using this relation, we propose a method to select a subset of good matches to produce highly accurate pose estimations. We also aim at refining match position. For this, we propose an improvement of least square matching (LSM) using an irregular sampling grid and image scale exploration. We show that match refinement and match selection independently improve the reconstruction results, and when combined together, the results are further improved