Le sujet central de cette thèse est le développement d'une méthode dédiée à la preuve de structures de données sans verrou. La motivation première vient du constat que les programmes concurrents sont devenu monnaie courante. Ceci a été possible par l'apparition de nouvelles primitives de synchronisation dans les nouvelles architectures matérielles. La seconde motivation est la quête de logiciel prouvé et donc correct. La sûreté des logiciels est en effet devenue primordiale de par la diffusion des systèmes embarqués et enfouis. La méthode proposée est basée sur le raffinement et dédiée à la conception et la vérification d'algorithme non-bloquant, en particulier ceux sans verrou. La méthode a été formalisée et sa correction prouvée en Isabelle/HOL. Un outil a par ailleurs été développé afin de générer des obligations de preuves à destination des solveurs SMT et des prouveurs de théorèmes du premier ordre. Nous l'avons utilisé afin de vérifier certains de ces algorithmes. / The central topic of this thesis is the proof-based development of lock-free data-structure algorithms. First motivation comes from new computer architectures that come with new synchronisation features. Those features enable concurrent algorithms that do not use locks and are thus more efficient. The second motivation is the search for proved correct program. Nowadays embedded software are used everywhere included in systems where safety is central. We propose a refinement-based method for designing and verifying non-blocking, and in particular lock-free, implementations of data structures. The entire method has been formalised in Isabelle/HOL. An associated prototype tool generates verification conditions that can be solved by SMT solvers or automatic theorem provers for first-order logic, and we have used this approach to verify a number of such algorithms.

La spécification de systèmes complexes est une tâche difficile qui ne peut être accomplie en une seule étape. Dans les méthodes formelles, le concept de raffinement a donné lieu à de nombreux travaux dans lesquels la preuve de la correction entre les différents états de spécifications joue un rôle important. L'activité de refactoring consiste à restructurer un modèle en vue d'améliorer certains facteurs de qualité, tout en préservant la cohérence de ce modèle. Cette thèse préconise l'utilisation de deux techniques de raffinement et de refactoring afin d'établir des modèles UML de qualité c'est-à-dire corrects par construction, extensibles, réutilisables et efficaces. En outre, elle plaide en faveur de l'utilisation conjointe UML (semi-formel) et B, Event-B et CSP (formels). Les principales contributions de cette thèse sont : proposition des patterns de raffinement de diagrammes de classes UML/OCL afin de guider le concepteur lors de la modélisation statique de son application et proposition des schémas de refactoring des modèles UML décrits par des diagrammes de classes, des contraintes OCL et des diagrammes d'états-transitions afin d'aider le concepteur lors de la restructuration des modèles UML.

Cette thèse a eu pour but l'étude et la mise en oeuvre des méthodes de vérification par abstraction pour les modèles AltaRica. A cette effet, une méthode d'abstraction permettant l'utilisation d'une sous approximation de l'espace des états d'un système dans un algorithme CEGAR est présentée. Son utilisation permet d'accélérer l'algorithme CEGAR, ainsi que de réduire les ressources nécessaires lors de la vérification d'un modèle. Nous nous intéressons à une modélisation d'un sous ensemble du langage AltaRica , pour lequel une méthode d'abstraction hiérarchique est décrite, ainsi qu'un algorithme efficace permettant la vérification de contre-exemples issus de cette abstraction. La méthode proposée permet d'abstraire chaque composant de la hiérarchie indépendamment malgré la présence de priorités dans le modèle. Finalement l'implémentation de l'algorithme PCegar dans le model checker Mec 5 est présentée ainsi qu'une analyse de benchmarks sur des modèles académiques et un modèle industriel. / This thesis presents an abstraction verification method for AltaRica models. To this end a CEGAR algorithm that prunes away abstract states and therefore uses an underapproximation of the system state space is proposed. The use of an underapproximation of the abstract state space allow to accelerate the algorithm, and reduce the computational resources required by the algorithm. A CEGAR algorithm for a subset of the AltaRica language is also presented. A hierarchical abstractionscheme and an efficient counter-example analysis method are proposed. The abstraction scheme proposed allow to abstract each component independently despite the presence of priorities in the model. Finally, the implementation of our CEGAR with pruning method is present together with benchmarks on academic and industrial models.

Dans les domaines critiques d'application de l'informatique, il peut être vital de disposer d'un génie logiciel qui soit capable de garantir le bon fonctionnement des systèmes produits. Dans ce contexte, la méthode B évènementielle promeut le développement de modèles abstraits du système à concevoir et l'utilisation de démonstrations formelles ainsi que de la relation de raffinement entre les modèles. Notre but est de pouvoir travailler sur des systèmes ayant des aspects temporels quantitatifs (propriétés et contraintes de temps) en restant au sein du cadre défini par la méthode B qui a déjà montré son efficacité par ailleurs, mais qui ne dispose pas de concepts spécifiques pour le temps. C'est ainsi que nous proposons l'introduction des contraintes de temps par le raffinement, ceci permet de respecter la philosophie de la méthode B et de systématiser cette approche par la formalisation de patrons de raffinement. Nos différentes modélisations du temps sont proposées sous la forme de patron à réappliquer sur le système à étudier. Nous pouvons donc étudier progressivement le système à partir d'une abstraction non-temporelle afin de le valider progressivement et de distribuer la difficulté de la preuve en plusieurs étapes. L'introduction des aspects temporels ne se fait que lorsque cela est nécessaire lors du processus de développement prouvé. Nous avons validé cette approche sur des études de cas réalistes en utilisant les outils logiciels de démonstration formelle de la méthode B. / Critical application domains of computer science require the use of software engineering methods that ensure that the resulting systems behave according to their intended functionality. In this context, the Event-B method uses an approach based on stepwise refinement, starting with abstract, high-level models of the system under development. The system models corresponding to different levels of abstraction are related by precise and formally proved refinement relations. Our goal is to extend this approach to systems whose requirements include quantitative real-time aspects (properties and temporal constraints). In this way, we benefit from the established qualities of the B method, while extending its scope to real-time aspects that it does not yet cover. More specifically, we propose to introduce time constraints by refinement, respecting the overall approach of the B method, and to systematize our approach by the use of refinement patterns. Different time models are represented by generic patterns that can be reused for the development of concrete systems. In this way we can gradually develop the system from a non-temporal abstraction and progressively validate its correctness, distributing the burden of proof is over several refinement steps. Temporal aspects are introduced step by step and only when necessary. We validated this approach using several real-world case studies, using the software tools for formal proof developed for the Event-B method.

Safety-critical systems depend on the fact that their software components provide services that behave correctly (i.e. satisfy their requirements). Additionally, in many cases, these systems have to be adapted or reconfigured in case of failures or when changes in requirements or in quality of service occur. When these changes appear at the software level, they can be handled by the notion of substitution. Indeed, the software component of the source system can be substituted by another software component to build a new target system. In the case of safety-critical systems, it is mandatory that this operation enforces that the new target system behaves correctly by preserving the safety properties of the source system during and after the substitution operation. In this thesis, the studied systems are modeled as state-transition systems. In order to model system substitution, the Event-B method has been selected as it is well suited to model such state-transition systems and it provides the benefits of refinement, proof and the availability of a strong tooling with the Rodin Platform. This thesis provides a generic model for system substitution that entails different situations like cold start and warm start as well as the possibility of system degradation, upgrade or equivalence substitutions. This proposal is first used to formalize substitution in the case of discrete systems applied to web services compensation and allowed modeling correct compensation. Then, it is also used for systems characterized by continuous behaviors like hybrid systems. To model continuous behaviors with Event-B, the Theory plug-in for Rodin is investigated and proved successful for modeling hybrid systems. Afterwards, a correct substitution mechanism for systems with continuous behaviors is proposed. A safety envelope for the output of the system is taken as the safety requirement. Finally, the proposed approach is generalized, enabling the derivation of the previously defined models for web services compensation through refinement, and the reuse of proofs across system models.

Les interfaces homme-machine (IHM) multimodales offrent à l’utilisateur la possibilité de combiner les modalités d’interaction afin d’augmenter la robustesse et l’utilisabilité de l’interface utilisateur d’un système. Plus particulièrement, en sortie, les IHM multimodales permettent au système de restituer à l’utilisateur, l’information produite par le noyau fonctionnel en combinant sémantiquement plusieurs modalités. Dans l’optique de concevoir de telles interfaces pour des systèmes critiques, nous avons proposé un modèle formel de conception des interfaces multimodales en sortie. Le modèle proposé se décompose en deux modèles : le modèle de fission sémantique qui décrit la décomposition de l’information à restituer en informations élémentaires, et le modèle d’allocation qui spécifie l’allocation des modalités et médias aux informations élémentaires. Nous avons également développé une formalisation B Événementiel détaillée des deux modèles : fission sémantique et allocation. Cette formalisation a été instanciée sur des études de cas puis généralisée dans un processus de développement B Événementiel cadre dans lequel s’inscrivent les modèles de fission sémantique et d’allocation. Cette formalisation a permis de procéder à la vérification de propriétés de sûreté, de vivacité et d’utilisabilité. / Multimodal Human-Computer Interfaces (HCI) offer to users the possibility to combine interaction modalities in order to increase user interface robustness and usability. Specifically, output multimodal HCI allow system to return to the user, the information generated by the functional core by combining semantically different modalities. In order to design such interfaces for critical systems, we proposed a formal model for the design of output multimodal interfaces. The proposed model consists of two models: the semantic fission model describes the decomposition of the information to return into elementary information and the allocation model specifies the allocation of the elementary information with modalities and media. We have also developed a detailed Event B formalization for the two models: semantic fission and allocation. This formalization has been instantiated on case studies and generalized in an Event B development process framework including semantic fission and allocation models. This formalization allows to carry out safety, liveness and usability properties verification.

Afin d'anticiper les effets du vieillissement des enceintes de confinement des centrales électronucléaires, l'IRSN effectue des recherches avancées sur le vieillissement du béton. Les problématiques de fissuration liées au vieillissement sont abordées à l'aide d'une méthode micromécanique basée sur des Modèles de Zones Cohésives Frottantes et à l'aide de la méthode d'<<Eigen-Erosion >> basée sur des considérations énergétiques. L'objectif de la thèse est de réduire les temps de calcul liés à ces deux approches, tout en conservant une bonne précision dans les zones d'intérêt, en adaptant la discrétisation en espace à l'aide de techniques de raffinement local adaptatif. La méthode de raffinement retenue est la méthode CHARMS (Conforming Hierarchical Adaptive Refinement Methods). Cette méthode, basée sur le raffinement des fonctions de base, permet un raffinement sans dégradation de la qualité des mailles initiales. En particulier, les non conformités géométriques sont naturellement prises en compte. Initialement appliquée à la Mécanique des Fluides, cette méthode est d'abord étendue à la Mécanique des Milieux Dé-formables en proposant un critère de raffinement général, puis elle est appliquée à la méthode d'<< Eigen-Erosion >> et aux Modèles de Zones Cohésives. Enfin, l'influence de la morphologie des inclusions d'un Volume Elémentaire Représentatif de béton numérique sur le comportement apparent et sur la fissuration est étudiée. / In order to anticipate effects of ageing in confinement structures of nuclear power plant, the IRSN develops research programs to study the ageing of concrete. A micromechanical approach, based on Cohesive Zone Models, and the "Eigen-Erosion" method, based on energetics consideration, are used. The aim of this study is to reduce the computational cost while keeping simulations with good accuracy in the areas of interest. The strategy is to adapt the spatialdiscretization in the areas of interest using local adaptive refinement technics. The selected refinement method is called CHARMS (Conforming Hierarchical Adaptive Refinement Methods). CHARMS is based on the refinement of basis functions and enables refinement without any loss of the inital mesh quality. The geometrical non conformities are implicitly handled. Initialyapplied to Fluid Mechanics, the method is first extended to Solid Mechanics with a specific refinement criterion. It is then applied to "Eigen-Erosion" and to Cohesive Zone Models. The inclusion's shape of a Representative Elementary Volume of numerical concrete is studied in order to determine the influence over the apparent behaviour and the crack propagation.

Le marché des accumulateurs lithium-ion est en expansion. Cette croissance repose partiellement sur la multiplication des niches d’utilisation et l’amélioration constante de leurs performances. En raison de leur durabilité exceptionnelle, de leur faible coût, de leur haute densité de puissance et de leur fiabilité, les anodes basées sur les titanates de lithium, et plus particulièrement le spinelle Li4Ti5O12, présentent une alternative d’intérêt aux matériaux classiques d’anodes en carbone pour de multiples applications. Leur utilisation sous forme de nanomatériaux permet d’augmenter significativement la puissance disponible par unité de poids. Ces nanomatériaux ne sont typiquement pas contraints dans une direction particulière (nanofils, nanoplaquettes), car ces formes impliquent une tension de surface plus importante et requièrent donc généralement un mécanisme de synthèse dédié. Or, ces nanostructures permettent des réductions supplémentaires dans les dimensions caractéristiques de diffusion et de conduction, maximisant ainsi la puissance disponible, tout en affectant les propriétés habituellement intrinsèques des matériaux. Par ailleurs, les réacteurs continus reposant sur la technologie du plasma thermique inductif constituent une voie de synthèse démontrée afin de générer des volumes importants de matériaux nanostructurés. Il s’avère donc pertinent d’évaluer leur potentiel dans la production de titanates de lithium nanostructurés. La pureté des titanates de lithium est difficile à jauger. Les techniques de quantification habituelles reposent sur la fluorescence ou la diffraction en rayons X, auxquelles le lithium élémentaire se prête peu ou pas. Afin de quantifier les nombreuses phases (Li4Ti5O12, Li2Ti3O7, Li2TiO3, TiO2, Li2CO3) identifiées dans les échantillons produits par plasma, un raffinement de Rietveld fut développé et validé. La présence de γ-Li2TiO3 fut identifiée, et la calorimétrie en balayage différentiel fut explorée comme outil permettant d’identifier et de quantifier la présence de β-Li2TiO3. Différentes proportions entre les phases produites et différents types de morphologies furent observés en fonction des conditions d’opération du plasma. Ainsi, des conditions de trempe réductrice et d’ensemencement en Li4Ti5O12 nanométrique semblent favoriser l’émergence de nanomorphologies en nanofils (associés à Li4Ti5O12) et en nanoplaquette (associées à Li2TiO3). De plus, l’ensemencement et les recuits augmentèrent significativement le rendement en la phase spinelle Li4Ti5O12 recherchée. Les recuits sur les poudres synthétisées par plasma indiquèrent que la décomposition du Li2Ti3O7 produit du Li4Ti5O12, du Li2TiO3 et du TiO2 (rutile). Afin d’approfondir l’investigation de ces réactions de décomposition, les paramètres cristallins du Li2Ti3O7 et du γ-Li2TiO3 furent définis à haute température. Des mesures continues en diffraction en rayon X à haute température furent réalisées lors de recuits de poudres synthétisées par plasma, ainsi que sur des mélanges de TiO2 anatase et de Li2CO3. Celles-ci indiquent la production d’un intermédiaire Li2Ti3O7 à partir de l’anatase et du carbonate, sa décomposition en Li4Ti5O12 et TiO2 (rutile) sur toute la plage de température étudiée, et en Li2TiO3 et TiO2 (rutile) à des températures inférieures à 700°C.

<P align="justify">Model-checking is an automated technique which aims at verifying properties of computer systems. A model-checker is fed with a model of the system (which capture all its possible behaviors) and a property to verify on this model. Both are given by a convenient mathematical formalism like, for instance, a transition system for the model and a temporal logic formula for the property.</P> <P align="justify">For several reasons (the model-checking is undecidable for this class of model or the model-checking needs too much resources for this model) model-checking may not be applicable. For safety properties (which basically says "nothing bad happen"), a solution to this problem uses a simpler model for which model-checkers might terminate without too much resources. This simpler model, called the abstract model, over-approximates the behaviors of the concrete model. However the abstract model might be too imprecise. In fact, if the property is true on the abstract model, the same holds on the concrete. On the contrary, when the abstract model violates the property, either the violation is reproducible on the concrete model and so we found an error; or it is not reproducible and so the model-checker is said to be inconclusive. Inconclusiveness stems from the over-approximation of the concrete model by the abstract model. So a precise model yields the model-checker to conclude, but precision comes generally with an increased computational cost.</P> <P align="justify">Recently, a lot of work has been done to define abstraction refinement algorithms. Those algorithms compute automatically abstract models which are refined as long as the model-checker is inconclusive. In the thesis, we give a new abstraction refinement algorithm which applies for safety properties. We compare our algorithm with previous attempts to build abstract models automatically and show, using formal proofs that our approach has several advantages. We also give several extensions of our algorithm which allow to integrate existing techniques used in model-checking such as acceleration techniques.</P> <P align="justify">Following a rigorous methodology we then instantiate our algorithm for a variety of models ranging from finite state transition systems to infinite state transition systems. For each of those models we prove the instantiated algorithm terminates and provide encouraging preliminary experimental results.</P> <br> <br> <P align="justify">Le model-checking est une technique automatisée qui vise à vérifier des propriétés sur des systèmes informatiques. Les données passées au model-checker sont le modèle du système (qui en capture tous les comportements possibles) et la propriété à vérifier. Les deux sont donnés dans un formalisme mathématique adéquat tel qu'un système de transition pour le modèle et une formule de logique temporelle pour la propriété.</P> <P align="justify">Pour diverses raisons (le model-checking est indécidable pour cette classe de modèle ou le model-checking nécessite trop de ressources pour ce modèle) le model-checking peut être inapplicable. Pour des propriétés de sûreté (qui disent dans l'ensemble "il ne se produit rien d'incorrect"), une solution à ce problème recourt à un modèle simplifié pour lequel le model-checker peut terminer sans trop de ressources. Ce modèle simplifié, appelé modèle abstrait, surapproxime les comportements du modèle concret. Le modèle abstrait peut cependant être trop imprécis. En effet, si la propriété est vraie sur le modèle abstrait alors elle l'est aussi sur le modèle concret. En revanche, lorsque le modèle abstrait enfreint la propriété : soit l'infraction peut être reproduite sur le modèle concret et alors nous avons trouvé une erreur ; soit l'infraction ne peut être reproduite et dans ce cas le model-checker est dit non conclusif. Ceci provient de la surapproximation du modèle concret faite par le modèle abstrait. Un modèle précis aboutit donc à un model-checking conclusif mais son coût augmente avec sa précision.</P> <P align="justify">Récemment, différents algorithmes d'abstraction raffinement ont été proposés. Ces algorithmes calculent automatiquement des modèles abstraits qui sont progressivement raffinés jusqu'à ce que leur model-checking soit conclusif. Dans la thèse, nous définissons un nouvel algorithme d'abstraction raffinement pour les propriétés de sûreté. Nous comparons notre algorithme avec les algorithmes d'abstraction raffinement antérieurs. A l'aide de preuves formelles, nous montrons les avantages de notre approche. Par ailleurs, nous définissons des extensions de l'algorithme qui intègrent d'autres techniques utilisées en model-checking comme les techniques d'accélérations.</P> <P align="justify">Suivant une méthodologie rigoureuse, nous instancions ensuite notre algorithme pour une variété de modèles allant des systèmes de transitions finis aux systèmes de transitions infinis. Pour chacun des modèles nous établissons la terminaison de l'algorithme instancié et donnons des résultats expérimentaux préliminaires encourageants.</P>

Les travaux développés dans ce mémoire concernent la formalisation d'un processus sûr d'automatisation en vue de maîtriser la complexité induite par l'intégration de plus en plus importante de technologies de l'information et de la communication au cœur même des processus de production et des produits. Plus précisément, notre travail porte sur l'intégration d'approches méthodologiques, issues du Génie Automatique, et de modèles formels, issus du Génie Informatique et de l'Automatique des Systèmes à Evénements Discrets afin de garantir, a priori, le respect des exigences formulées par les utilisateurs. Notre contribution porte sur deux axes. Le premier concerne l'intégration de techniques de synthèse de la commande dans un processus d'automatisation, incluant les phases de modélisation et de génération d'un code implantable, et leur application à la reconfiguration de systèmes manufacturiers contrôlés par le produit. Le second est basé sur le raffinement formel ou semi-formel de modèles pour identifier et structurer les exigences exprimées à un niveau " système " puis les allouer et les projeter sur une architecture de fonctions, de composants ou d'équipements. Ces travaux ont été initiés dans le cadre de notre thèse en réponse aux besoins de R&D industriels de la Direction des Etudes & Recherche d'EDF, puis ont été poursuivis avec une cible relative aux systèmes manufacturiers et validés dans le cadre de collaborations industrielles variées.