Spelling suggestions: "subject:"méthode formelle"" "subject:"méthode formelles""
1 |
Spécification, validation et satisfiabilité [i.e. satisfaisabilité] de contraintes hybrides par réduction à la logique temporelleHallé, Sylvain January 2008 (has links) (PDF)
Depuis quelques années, de nombreux champs de l'informatique ont été transformés par l'introduction d'une nouvelle vision de la conception et de l'utilisation d'un système, appelée approche déclarative. Contrairement à l'approche dite impérative, qui consiste à décrire au moyen d'un langage formelles opérations à effectuer pour obtenir un résultat, l'approche déclarative suggère plutôt de décrire le résultat désiré, sans spécifier comment ce «but» doit être atteint. L'approche déclarative peut être vue comme le prolongement d'une tendance ayant cours depuis les débuts de l'informatique et visant à résoudre des problèmes en manipulant des concepts d'un niveau d'abstraction toujours plus élevé. Le passage à un paradigme déclaratif pose cependant certains problèmes: les outils actuels sont peu appropriés à une utilisation déclarative. On identifie trois questions fondamentales qui doivent être résolues pour souscrire à ce nouveau paradigme: l'expression de contraintes dans un langage formel, la validation de ces contraintes sur une structure, et enfin la construction d'une structure satisfaisant une contrainte donnée. Cette thèse étudie ces trois problèmes selon l'angle de la logique mathématique. On verra qu'en utilisant une logique comme fondement formel d'un langage de « buts », les questions de validation et de construction d'une structure se transposent en deux questions mathématiques, le model checking et la satisfiabilité, qui sont fondamentales et largement étudiées. En utilisant comme motivation deux contextes concrets, la gestion de réseaux et les architectures orientées services, le travail montrera qu'il est possible d'utiliser la logique mathématique pour décrire, vérifier et construire des configurations de réseaux ou des compositions de services web. L'aboutissement de la recherche consiste en le développement de la logique CTLFO+, permettant d'exprimer des contraintes sur les données, sur la séquences des opérations
d'un système, ainsi que des contraintes dites «hybrides». Une réduction de CTL-FO+ à la logique temporelle CTL permet de réutiliser de manière efficace des outils de vérification existants. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Méthodes formelles, Services web, Réseaux.
|
2 |
Contribution à l'intégration de temporalité au formalisme B : Utilisation du calcul des durées en tant que sémantique temporelle pour BColin, Samuel 03 October 2006 (has links) (PDF)
Dans le domaine des systèmes informatisés où la fiabilité est la première priorité, les méthodes formelles ont prouvé leur efficacité pour la conception de logiciels sûrs. La dépendance à de tels systèmes augmente, et les contraintes rencontrées se font plus diverses et précises, en particulier les contraintes temporelles. Certaines méthodes formelles, notamment la méthode B, rendent la conception malaisée sous de telles contraintes, puisqu'elles n'ont pas été prévues pour cela à l'origine.<br /><br />Nous nous proposons donc d'étendre la méthode B pour lui permettre de spécifier et valider des systèmes à contraintes temporelles complexes. Nous utilisons pour ce faire des calculs de durées pour exprimer la sémantique du langage B et en déduire une extension conservative qui permet de l'utiliser à la fois dans son cadre d'origine et dans le cadre de systèmes à contraintes temporelles.<br /><br />Nous nous penchons également sur le problème de l'utilisation d'un outil de preuve générique pour valider des formules de calcul des durées. La généricité de ce type d'outil répond à la multiplication des méthodes formelles, mais pose le problème de l'intégration des fondations mathématiques de ces méthodes à un outil générique. Nous proposons donc d'étudier la mise en oeuvre en plongement léger du calcul des durées dans l'assistant de preuve Coq. Nous en déduisons un retour sur expérience de la définition d'une logique modale particulière dans un outil à vocation générique.
|
3 |
Génération de codes et d'annotations prouvables d'algorithmes de points intérieurs à destination de systèmes embarqués critiques / Generation of codes and provable annotations of interior-point algorithms for critical embedded systemsDavy, Guillaume 06 December 2018 (has links)
Dans l'industrie, l'utilisation de l'optimisation est omniprésente. Elle consiste à calculer la meilleure solution tout en satisfaisant un certain nombre de contraintes. Cependant, ce calcul est complexe, long et pas toujours fiable. C'est pourquoi cette tâche est longtemps restée cantonnée aux étapes de conception, ce qui laissait le temps de faire les calculs puis de vérifier que la solution était correcte et si besoin refaire les calculs. Ces dernières années, grâce à la puissance toujours grandissante des ordinateurs, l'industrie a commencé à intégrer des calculs d'optimisation au cœur des systèmes. C'est-à-dire que des calculs d'optimisation sont effectués en permanence au sein du système, parfois des dizaines de fois par seconde. Par conséquent, il est impossible de s'assurer a posteriori de la correction d'une solution ou de relancer un calcul. C'est pourquoi il est primordial de vérifier que le programme d'optimisation est parfaitement correct et exempt de bogue.L'objectif de cette thèse a été de développer outils et méthodes pour répondre à ce besoin.Pour ce faire, nous avons utilisé la théorie de la preuve formelle qui consiste à considérer un programme comme un objet mathématique. Cet objet prend des informations en entrée et produit un résultat. On peut alors, sous certaines conditions sur les entrées, prouver que le résultat satisfait nos exigences. Notre travail a consisté à choisir un programme d'optimisation puis à prouver formellement que le résultat de ce programme est correct. / In the industry, the use of optimization is ubiquitous. Optimization consists of calculating the best solution subject to a number of constraints. However, this calculation is complex,long and not always reliable. This is why this task has long been confined to the design stages,which allowed time to do the computation and then check that the solution is correct and if necessary redo the computation. In recent years, thanks to the ever-increasing power of computers, the industry has begun to integrate optimization computation at the heart of the systems. That is to say that optimization computation is carried out continuously within the system, sometimes dozens of times per second. Therefore, it is impossible to check a posteriori the solution or restart a calculation. That is why it is important to check that the program optimization is perfectly correct and bug-free. The objective of this thesis was to develop tools and methods to meet this need. To do this we have used the theory of formal proof that is to consider a program as a mathematical object. This object takes input data and produces a result. We can then, under certain conditions on the inputs, prove that the result meets our requirements. Our job was to choose an optimization program and formally prove that the result of this program is correct.
|
4 |
Spécification et vérification formelles des systèmes de composants répartisBarros, Tomás 25 November 2005 (has links) (PDF)
Un composant est une entité autonome qui interagit avec son environnement par des interfaces correctement spécifiées. Fractive est une implantation du modèle de composants Fractal qui propose des primitives de haut niveau et une sémantique pour la programmation à base de composants Java distribués, asynchrones et hiérarchiques. Fractive propose également une séparation entre aspects fonctionnels et non-fonctionnels, ces derniers permettant un contrôle de l´exécution d´un composant et de son évolution dynamique. Dans cette thèse, nous proposons un outillage formel pour la vérification d´applications construites avec Fractive. Cela permet de vérifier que chaque composant remplit correctement le rôle qui lui a été assigné au sein du système, et que la mise à jour ou le remplacement d´un composant n´engendre pas d´interblocage ou de panne du système. Nous avons défini un nouveau format intermédiaire qui étend les réseaux d´automates communicants, en paramétrisant leurs événements de communication et de traitement. Nous avons ensuite utilisé ce format intermédiaire pour définir les spécifications comportementales d´applications Fractive. Nous considérons que les modèles des composants primitifs sont connus (donnés par l´utilisateur ou par analyse statique). En utilisant la description des composants, nous construisons un contrôleur décrivant le comportement non fonctionnel du composant. La sémantique d´un composant est ensuite générée comme le produit de synchronisation des LTSs de ses sous-composants et du contrôleur. Le système résultant peut être vérifié par rapport aux besoins exprimés dans un ensemble de formules de logique temporelle, comme illustré dans le manuscrit.
|
5 |
An Intermediate Model for the Verification of Asynchronous Real-Time Embedded Systems: Definition and Application of the ATLANTIF languageStöcker, Jan 09 December 2009 (has links) (PDF)
La validation des systèmes critiques réalistes nécessite d'être capable de modéliser et de vérifier formellement des données complexes, du parallélisme asynchrone, et du temps-réel simultanément. Des langages de haut-niveau, comme ceux qui héritent des fondations théoriques des algèbres de processus, ont une syntaxe concise et une grande expressivité pour représenter ces aspects. Cependant, ils disposent de peu d'outils logiciels permettant d'appliquer des algorithmes efficaces du model-checking. Néanmoins, de tels outils existent pour des modèles graphiques, de niveau plus bas, tels que les automates temporisés (par exemple Uppaal) et les réseaux de Petri temporisés (par exemple Tina). Les modèles intermédiaires sont un moyen pour combler le fossé qui sépare les langages des modèles graphiques. Par exemple, NTIF (New Technology Intermediate Format) a été proposé pour représenter des processus séquentiels non-temporisés qui manipulent des données complexes. Dans cette thèse, nous proposons un nouveau modèle nommé ATLANTIF, qui enrichit NTIF de constructions temps-réel et de compositions parallèles de processus séquentiels. Leur synchronisation est exprimée d'une manière simple et intuitive par la nouvelle notion de synchroniseur. Nous montrons qu'ATLANTIF est capable d'exprimer les constructions principales des langages de haut niveau. Nous présentons aussi des traducteurs d'ATLANTIF vers des automates temporisés (pour la vérification avec Uppaal) et vers des réseaux de Petri temporisés (pour la vérification avec Tina). Ainsi, ATLANTIF étend la classe des systèmes qui peuvent en pratique être vérifiés formellement, ce que nous illustrons par un exemple.
|
6 |
Etude de l'apport des méthodes formelles déductives pour les développements de sécuritéJaeger, Eric 08 March 2010 (has links) (PDF)
La mise en oeuvre des méthodes formelles déductives lors du développement de systèmes permet d'obtenir des garanties mathématiques quant à leur validité. Pour cette raison, leur utilisation est recommandée ou exigée par certains standards relatifs à la sûreté de fonctionnement ou à la sécurité, tels que l'IEC 61508 ou les Critères Communs. Il reste cependant légitime de s'interroger sur la portée exacte des bénéfices obtenus. Certains aspects d'un système peuvent en effet échapper à la formalisation, et il n'est pas toujours facile d'identifier ces limitations ou leurs conséquences. De même, si la validité d'une preuve vérifiée mécaniquement est difficilement contestable, son utilisation pour justifier d'une confiance réelle dans le système physique n'est pas toujours admise. De telles questions sont particulièrement pertinentes dans le domaine de la sécurité, lorsque les systèmes sont l'objet d'attaques de la part d'agents intelligents ; par rapport à la sûreté il y a un changement radical de point de vue, qui justifie de s'interroger quant à l'application de principes ou de pratiques bien connus. Nous identifions les bénéfice et évaluons la confiance résultant de l'application des méthodes formelles déductives lors de développements de systèmes de sécurité. Cette analyse aborde les éventuelles difficultés, déviations ou problèmes qui peuvent être rencontrés et les illustre par des exemples. Elle comporte également une étude détaillée du concept de raffinement, et présente un plongement profond visant à valider la logique de la méthode B en Coq. Ce plongement conduit par ailleurs à l'étude des représentations à la de Bruijn.
|
7 |
Spécification et analyse formelles des politiques de sécurité dans un processus de courtage de l'informatique en nuage / Formal specification and analysis of security policies in a cloud brokerage processGuesmi, Asma 01 July 2016 (has links)
Les offres de l’informatique en nuage augmentent de plus en plus et les clients ne sont pas capables de lescomparer afin de choisir la plus adaptée à leurs besoins. De plus, les garanties de sécurité proposées parles fournisseurs restent incompréhensibles pour les clients. Cela représente un frein pour l'adoption dessolutions de l’informatique en nuage.Dans cette thèse, nous proposons un mécanisme de courtage des services de l’informatique en nuage quiprend en compte les besoins du client en termes de sécurité.Les besoins exprimés par le client sont de deux natures. Les besoins fonctionnels représentent lesressources et leurs performances. Les besoins non-fonctionnels représentent les propriétés de sécurité etles contraintes de placement des ressources dans le nuage informatique. Nous utilisons le langage Alloypour décrire les offres et les besoins. Nous utilisons l'analyseur Alloy pour l'analyse et la vérification desspécifications du client. Le courtier sélectionne les fournisseurs qui satisfont les besoins fonctionnels et nonfonctionnelsdu client. Il vérifie ensuite, que la configuration du placement des ressources chez lesfournisseurs respecte toutes les propriétés de sécurité exigées par le client.Toutes ces démarches sont effectuées avant le déploiement des ressources dans le nuage informatique.Cela permet de détecter les erreurs et conflits des besoins du client tôt. Ainsi, on réduit les vulnérabilités desressources du client une fois déployées. / The number of cloud offerings increases rapidly. Therefore, it is difficult for clients to select the adequate cloud providers which fit their needs. In this thesis, we introduce a cloud service brokerage mechanism that considers the client security requirements. We consider two types of the client requirements. The amount of resources is represented by the functional requirements. The non-functional requirements consist on security properties and placement constraints. The requirements and the offers are specified using the Alloy language. To eliminate inner conflicts within customers requirements, and to match the cloud providers offers with these customers requirements, we use a formal analysis tool: Alloy. The broker uses a matching algorithm to place the required resources in the adequate cloud providers, in a way that fulfills all customer requirements, including security properties. The broker checks that the placement configuration ensures all the security requirements. All these steps are done before the resources deployment in the cloud computing. This allows to detect the conflicts and errors in the clients requirements, thus resources vulnerabilities can be avoided after the deployment.
|
8 |
Étude des architectures de sécurité de systèmes autonomes : formalisation et évaluation en Event B / Model based safety of FDIR architectures for autonomous systems : formal specification and assessment with Event-BChaudemar, Jean-Charles 27 January 2012 (has links)
La recherche de la sûreté de fonctionnement des systèmes complexes impose une démarche de conception rigoureuse. Les travaux de cette thèse s’inscrivent dans le cadre la modélisation formelle des systèmes de contrôle autonomes tolérants aux fautes. Le premier objectif a été de proposer une formalisation d’une architecture générique en couches fonctionnelles qui couvre toutes les activités essentielles du système de contrôle et qui intègre des mécanismes de sécurité. Le second objectif a été de fournir une méthode et des outils pour évaluer qualitativement les exigences de sécurité. Le cadre formel de modélisation et d’évaluation repose sur le formalisme Event-B. La modélisation Event-B proposée tire son originalité d’une prise en compte par raffinements successifs des échanges et des relations entre les couches de l’architecture étudiée. Par ailleurs, les exigences de sécurité sont spécifiées à l’aide d’invariants et de théorèmes. Le respect de ces exigences dépend de propriétés intrinsèques au système décrites sous forme d’axiomes. Les preuves que le principe d’architecture proposé satisfait bien les exigences de sécurité attendue ont été réalisées avec les outils de preuve de la plateforme Rodin. L’ensemble des propriétés fonctionnelles et des propriétés relatives aux mécanismes de tolérance aux fautes, ainsi modélisées en Event-B, renforce la pertinence de la modélisation adoptée pour une analyse de sécurité. Cette approche est par la suite mise en œuvre sur un cas d’étude d’un drone ONERA. / The study of complex system safety requires a rigorous design process. The context of this work is the formal modeling of fault tolerant autonomous control systems. The first objective has been to provide a formal specification of a generic layered architecture that covers all the main activities of control system and implement safety mechanisms. The second objective has been to provide tools and a method to qualitatively assess safety requirements. The formal framework of modeling and assessment relies on Event-B formalism. The proposed Event-B modeling is original because it takes into account exchanges and relations betweenarchitecture layers by means of refinement. Safety requirements are first specified with invariants and theorems. The meeting of these requirements depends on intrinsic properties described with axioms. The proofs that the concept of the proposed architecture meets the specified safety requirements were discharged with the proof tools of the Rodin platform. All the functional properties and the properties relating to fault tolerant mechanisms improve the relevance of the adopted Event-B modeling for safety analysis. Then, this approach isimplemented on a study case of ONERA UAV.
|
9 |
Coordination and reconfiguration of distributed cloud applications / Coordination et reconfiguration des applications reparties dans le nuageAbid, Rim 16 December 2015 (has links)
Les applications reparties dans le nuage sont constituées d'un ensemble de composants logiciels interconnectés et répartis sur plusieurs machines virtuelles. Cet environnement nécessite des protocoles pour configurer dynamiquement ces applications. Nous présentons dans la première partie de cette thèse un nouveau protocole pour résoudre les dépendances dans ces applications. Ce protocole consiste à (dé) connecter et démarrer/arrêter les composants dans un ordre spécifique. Il supporte les pannes des machines virtuelles et les opérations de reconfiguration se terminent toujours avec succès. Ces machines virtuelles interagissent à travers un «publish-subscribe communication media» et se reconfigurent d'une manière décentralisée. La conception de ces protocoles étant une source d'erreurs, nous avons étudié l'utilisation du langage formelle LNT pour spécifier le protocole et les outils disponibles dans la boîte à outils CADP pour le vérifier. D'autre part, la gestion des applications reparties dans le nuage est une tâche complexe car l'administration manuelle n'est plus réaliste pour ces systèmes. Nous avons proposé d'automatiser certaines fonctions d'administration en utilisant des boucles de contrôle appelées gestionnaires autonomes. Plusieurs gestionnaires peuvent être déployés pour la gestion de la même application. Cependant, leur utilisation sans coordination peut conduire à des incohérences et des situations d'erreur. Dans la deuxième partie de cette thèse, nous avons proposé une nouvelle approche pour coordonner plusieurs gestionnaires autonomes. Cette approche repose sur une langue de coordination simple, de nouvelles techniques asynchrone pour la synthèse de contrôleur et la génération de code Java. Nous avons appliqué notre approche pour coordonner les applications de cloud computing dans le monde réel. / Cloud applications are composed of a set of interconnected software components distributed over several virtual machines. There is a need for protocols that can dynamically reconfigure such distributed applications. We present in the first part of this thesis a novel protocol, which can resolve dependencies in these applications, by (dis)connecting and starting/stopping components in a specific order. The protocol also supports virtual machine failures. The virtual machines interact through a publish-subscribe communication media and reconfigure themselves upon demand in a decentralised fashion. Designing such protocols is an error-prone task. Therefore, we investigated the use the LNT value-passing process algebra to specify the protocol and the model checking tools available in the CADP toolbox to verify it.Managing distributed cloud applications is a challenging problem because manual administration is no longer realistic for these complex distributed systems. Thus, autonomic computing is a promising solution for monitoring and updating these applications automatically. This is achieved through the automation of administration functions and the use of control loops called autonomic managers. Multiple autonomic managers can be deployed in the same system and must make consistent decisions. Using them without coordination may lead to inconsistencies and error-prone situations. In the second part of the thesis, we propose our approach for coordinating stateful autonomic managers, which relies on a simple coordination language, new techniques for asynchronous controller synthesis and Java code generation. We used our approach for coordinating real-world cloud applications.
|
10 |
Model Checking sur Architecture MultiprocesseurT. Saad, Rodrigo 20 November 2011 (has links) (PDF)
Nous proposons de nouveaux algorithmes et de nouvelles structures de données pour la vérifi cation formelle de systèmes réactifs nis sur architectures parallèles. Ces travaux se basent sur les techniques de véri cation par model checking. Notre approche cible des architectures multi-processeurs et multi-coeurs, avec mémoire partagée, qui correspondent aux générations de serveurs les plus performants disponibles actuellement. Dans ce contexte, notre objectif principal est de proposer des approches qui soient à la fois effi caces au niveau des performances, mais aussi compatibles avec les politiques de partage dynamique du travail utilisées par les algorithmes de génération d'espaces d'états en parallèle ; ainsi, nous ne plaçons pas de contraintes sur la manière dont le travail ou les données sont partagés entre les processeurs. Parallèlement à la défi nition de nouveaux algorithmes de model checking pour machines multi-coeurs, nous nous intéressons également aux algorithmes de vérifi cation probabiliste. Par probabiliste, nous entendons des algorithmes de model checking qui ont une forte probabilité de visiter tous les états durant la vérifi cation d'un système. La véri fication probabiliste permet des gains importants au niveau de la mémoire utilisée, en échange d'une faible probabilité de ne pas être exhaustif ; il s'agit donc d'une stratégie permettant de répondre au problème de l'explosion combinatoire.
|
Page generated in 0.4978 seconds