• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 74
  • 43
  • 8
  • Tagged with
  • 127
  • 127
  • 55
  • 55
  • 52
  • 48
  • 34
  • 31
  • 27
  • 25
  • 21
  • 20
  • 17
  • 16
  • 15
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Une approche rigoureuse pour l’ingénierie de compositions de services Web / A rigourous approach for engineering web services compositions

Rouached, Mohsen 28 April 2008 (has links)
L'évolution de l'Internet comme support de communication entre les applications et les organisations a révolutionné les méthodes de coopération classiques. Les technologies réseaux actuelles, notamment les services Web, permettent le développement de nouveaux paradigmes de coopération. En effet, les entreprises peuvent dans un premier temps externaliser leurs procédés métiers comme des services Web pour former dans un deuxième temps ce qu'on appelle une entreprise virtuelle par compositions de services externalisés. Mais, comme souvent en informatique, ce qui est supposé apporter de la facilité apporte aussi son lot de complexité et de questions. Cela va de la pertinence des langages utilisés pour décrire les compositions de services, leur formalisation, leur vérification formelle avant et après l'exécution, au problème de maintenir une qualité de services constante. L'objectif de cette thèse est de proposer une approche rigoureuse pour la spécification, la modélisation, la vérification et la validation des compositions de services Web. Le travail effectué a permis la mise en place de techniques de preuves pour les services Web pour répondre à de nouveaux challenges liés essentiellement à la composition et la vérification. L'approche développée consiste en : (i)la définition d'un langage de spécification de la composition pour assurer sa vérification formelle, (ii) l'extension du langage de composition transformé pour prendre en compte les aspects de communication entre des compositions différentes, (iii) l'extraction et la spécification des propriétés à vérifier avant et après l'exécution de la composition, (iv) la vérification de la composition (vérification a priori et vérification a posteriori), et (v) l'utilisation des spécifications des déviations détectées pour découvrir des services qui peuvent tomber en panne ou devenir indisponibles en cours d'exécution. / The proliferation of the Internet as a communication medium between applications and organizations has revolutionized the classic methods of cooperation. The current network technologies, including Web services, allow the development of new paradigms of cooperation. Indeed, enterprises can outsource their business processes as Web services to form what is called a virtual enterprise by compositions of outsourced services. However, as so often in computer science applications, which is supposed to bring the facility provides also its set of complexity and questions. This covers the relevance of the language used to describe the compositions of services, their formalizations, their formal verification before and after running the composition process, and the need of maintaining a constant quality of services. The aim of this dissertation is to develop a rigorous approach to specifying, modelling, verifying and validating the behaviour of Web service compositions with the goal of simplifying the task of designing coordinated distributed services and their interaction requirements. More precisely, we have proposed a semantic framework that provides a foundation for addressing the existing limitations in the context of Web services compositions by supporting the following functionalities: (i) to formally specify requirements for BPEL processes. The requirements specify behavioural properties of the composition process, or assumptions about the behaviour of the composition as a whole and its constituent services, (ii) to extend the approach to include models of service choreography with multiple interacting Web services compositions, from the perspective of a collaborative distributed composition development environment, (iii) to verify these requirements against process executions. The requirements verification can be done either a-priori, i.e., at design time, or a-posteriori, i.e., after runtime, (iv) to use the specifications of the violated requirements to generate queries for discovering services that could substitute for malfunctioning services or services that may become unavailable or fail to meet certain requirements.
2

Propriétés de jeux multi-agents / Multi-agent games properties

Lopes, Arnaud Da Costa 20 September 2011 (has links)
Nous etendons les logiques temporelles du temps alternant ATL et ATL* au moyen de contextes strategiques et de contraintes sur la memoire : la premiere extension permet aux agents de s'en tenir a leurs strategies lors de l'evaluation des formules, contrairement a ATL ou chaque quantificateur de strategies ecrase les strategies anterieurement selectionnees. La seconde extension permet aux quantificateurs de strategies de se restreindre aux strategies sans memoire ou avec memoire bornee. Nous avons l'etudie l'expressivite de nos logiques. Nous montrons qu'elles expriment des proprietes importantes comme l'exstence d'equilibres, et nous les comparons formellement a d'autres formalismes proches (ATL, ATL*, Game Logic, Strategy Logic, ...). Nous avons aborde les problemes de model-checking. Nous donnons un algorithme PSPACE pour la logique n'impliquant que des strategies sans memoire, et un algorithme EXPSPACE pour le cas des strategies a memoire bornee. Dans le cas general, malgre leur forte expresssivite, nous prouvons que leur model-checking reste decidable par un algorithme a base d'automates d'arbres alternants qui permet d'evaluer une formule sur la classe complete des CGS avec n joueurs. / We extend the alternating-time temporal logics ATL and ATL* with strategy contexts and memory constraints: the first extension make agents commit to their strategies during the evaluation of formulas, contrary to plain ATL where strategy quantifiers reset previously selected strategies. The second extension allows strategy quantifiers to restrict to memoryless or bounded-memory strategies. We consider expressiveness issues. We show that our logics can express important properties such as equilibria, and we formally compare them with other similar formalisms (ATL, ATL*, Game Logic, Strategy Logic, ...). We address the problem of model-checking for our logics, especially we provide a PSPACE algorithm for the sublogics involving only memoryless strategies and an EXPSPACE algorithm for the bounded-memory case. In the general case, despite the high expressiveness of these logics, we prove that their model-checking problems remain decidable by designing a tree-automata-based algorithm for model-checking ATLsc on the full class of n-player concurrent game structures.
3

Vérification formelle des systèmes numériques par démonstration de théorèmes: application aux composants cryptographiques

Toma, D. 18 July 2006 (has links) (PDF)
A cause de la complexité croissante des systèmes sur puce (SoC), la vérification devient un aspect très important : 70 - 80% du coût de conception est alloué à cette tâche. Plus de 60% des projets de développement d'ASIC doivent être repris à cause des erreurs fonctionnelles, environ 50% des erreurs de conception étant situées au niveau du module. Dans le monde industriel, la vérification est souvent synonyme de simulation - une méthode de vérification naturelle pour les concepteurs, mais qui ne garantit pas l'absence d'erreurs. Une alternative est fournie par la vérification formelle qui prouve mathématiquement qu'un circuit satisfait une spécification. Dans cette thèse, on s'intéresse aux méthodes déductives basées sur la démonstration de théorèmes. La démonstration de théorèmes permet de vérifier formellement des descriptions matérielles de haut niveau et des systèmes réguliers ou très complexes, car la taille de données n'a plus d'importance. Par contre la modélisation de la description matérielle se fait directement en logique, ce qui rend l'accès difficile pour les concepteurs. Notre travail a pour but de faciliter l'introduction des outils de démonstration de théorèmes dans le flot de conception. Nous proposons une méthode automatique de traduction d'un circuit VHDL vers un modèle sémantique basé sur des équations récurrentes par rapport au temps qui peut être l'entrée de tout outil de démonstration de théorèmes et nous définissons une approche de vérification adaptée au modèle. Afin de valider notre proposition, nous avons choisi le démonstrateur ACL2 pour vérifier une bibliothèque de circuits de cryptographie.
4

Vérification formelle des résultats de la synthèse de haut niveau

Dushina, J. 10 October 1999 (has links) (PDF)
Pour satisfaire la demande du marché actuel, plusieurs outils commerciaux de vérification formelle sont apparus ces dernières années. Le niveau le plus abstrait de description accepté dans la plupart de ces outils est le niveau appelé transfert de registres, c'est-à-dire une description avec des cycles d'horloge explicitement définis. Pour rester compétitifs, néanmoins, les concepteurs sont obligés d'élever le niveau d'abstraction et commencent à utiliser des outils de synthèse de haut niveau. Cette thèse a pour objet la vérification formelle des résultats de synthèse de haut niveau par rapport à la spécification initiale décrite en VHDL. Nous proposons une méthodologie de vérification qui épouse le flot de conception et consiste en la vérification de deux étapes principales:<br />l'ordonnancement et l'allocation. La vérification de chaque étape est fondée sur un modèle de machine abstraite que nous avons défini: contrairement au modèle de machine d'états finis classique, il réduit<br />considérablement l'espace d'états d'où les registres de la partie opérative sont exclus. En outre, la machine abstraite est similaire aux descriptions VHDL utilisées lors de la synthèse et offre, par conséquent, un niveau d'abstraction plus élevé de représentation des<br />circuits. La preuve d'équivalence entre la machine abstraite et la machine d'états finis classique justifie la première et constitue une des contributions théoriques de la thèse. Un prototype d'outil basé sur la simulation symbolique a été développé et exécuté sur des benchmarks de la synthèse comportementale. La thèse<br />s'achève sur les problèmes ouverts et les axes de recherche à explorer.
5

Verification formelle et optimisation de l'allocation de registres

Robillard, Benoit, Bruno 30 November 2010 (has links) (PDF)
La prise de conscience générale de l'importance de vérifier plus scrupuleusement les programmes a engendré une croissance considérable des efforts de vérification formelle de programme durant cette dernière décennie. Néanmoins, le code qu'exécute l'ordinateur, ou code exécutable, n'est pas le code écrit par le développeur, ou code source. La vérification formelle de compilateurs est donc un complément indispensable à la vérification de code source.L'une des tâches les plus complexes de compilation est l'allocation de registres. C'est lors de celle-ci que le compilateur décide de la façon dont les variables du programme sont stockées en mémoire durant son exécution. La mémoire comporte deux types de conteneurs : les registres, zones d'accès rapide, présents en nombre limité, et la pile, de capacité supposée suffisamment importante pour héberger toutes les variables d'un programme, mais à laquelle l'accès est bien plus lent. Le but de l'allocation de registres est de tirer au mieux parti de la rapidité des registres, car une allocation de registres de bonne qualité peut conduire à une amélioration significative du temps d'exécution du programme.Le modèle le plus connu de l'allocation de registres repose sur la coloration de graphe d'interférence-affinité. Dans cette thèse, l'objectif est double : d'une part vérifier formellement des algorithmes connus d'allocation de registres par coloration de graphe, et d'autre part définir de nouveaux algorithmes optimisants pour cette étape de compilation. Nous montrons tout d'abord que l'assistant à la preuve Coq est adéquat à la formalisation d'algorithmes d'allocation de registres par coloration de graphes. Nous procédons ainsi à la vérification formelle en Coq d'un des algorithmes les plus classiques d'allocation de registres par coloration de graphes, l'Iterated Register Coalescing (IRC), et d'une généralisation de celui-ci permettant à un utilisateur peu familier du système Coq d'implanter facilement sa propre variante de cet algorithme au seul prix d'une éventuelle perte d'efficacité algorithmique. Ces formalisations nécessitent des réflexions autour de la formalisation des graphes d'interférence-affinité, de la traduction sous forme purement fonctionnelle d'algorithmes impératifs et de l'efficacité algorithmique, la terminaison et la correction de cette version fonctionnelle. Notre implantation formellement vérifiée de l'IRC a été intégrée à un prototype du compilateur CompCert.Nous avons ensuite étudié deux représentations intermédiaires de programmes, dont la forme SSA, et exploité leurs propriétés pour proposer de nouvelles approches de résolution optimale de la fusion, l'une des optimisations opéréeslors de l'allocation de registres dont l'impact est le plus fort sur la qualité du code compilé. Ces approches montrent que des critères de fusion tenant compte de paramètres globaux du graphe d'interférence-affinité, tels que sa largeur d'arbre, ouvrent la voie vers de nouvelles méthodes de résolution potentiellement plus performantes.
6

Preuve de validité du vérificateur de code octet Java

Lazaar, Jamal January 2008 (has links) (PDF)
L'utilisation du langage Java dans plusieurs environnements (web, systèmes embarqués, systèmes mobiles, etc.) a élevé considérablement le niveau d'exigence envers ce langage, ce qui a amené les chercheurs et les développeurs à s'intéresser au système de sécurité de la Machine Virtuelle Java (MVJ) qui repose principalement sur le vérificateur du code octet. Dans ce mémoire, nous expliquons le fonctionnement du vérificateur Java, son rôle, les différentes techniques proposées pour son implémentation et un algorithme que nous proposons comme alternative sérieuse aux autres vérificateurs qui existent déjà. Nous nous intéresserons plus particulièrement à l'effet des sous-routines sur le bon typage des instructions. Nous présentons aussi une nouvelle approche de vérification de la synchronisation en nous basant sur l'analyse de flot de données et en identifiant les références qui pointent vers le même objet. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Machine Virtuelle Java, Code octet, Vérificateur, Synchronisation, Java, ClassLoader, Instructions, Treillis, Analyse de flot de données, Fonctions de transfert, Point fixe.
7

Vérification des politiques XACML avec le langage Event-B

Errachid, Mohammed 03 1900 (has links) (PDF)
Les politiques permettent de définir les règles de la sécurité et de la gestion des différents composants du système. Cela implique l'emploi d'un langage pour exprimer les règles d'affaires et les règles non fonctionnelles, et de donner aux utilisateurs la possibilité de tester et de corriger les politiques. Plusieurs langages tels que XACML, Rei ou PONDER, sont utilisés pour exprimer les politiques par rapport aux objectifs du système d'information. Ces langages peuvent définir plusieurs règles et politiques, mais la plupart de ces langages ne donnent pas de mécanisme pour tester et vérifier la présence des conflits et de l'incohérence entre les politiques du système. Ce mémoire vise la vérification des politiques de contrôle d'accès. Notre approche consiste à traduire les politiques XACML sous forme d'un ensemble de machines abstraites de la méthode B. Nous exprimons aussi les propriétés à vérifier par des formules logiques. L'approche offre aux utilisateurs des moyens pour vérifier les politiques afin de s'assurer que les règles expriment bien les objectifs régissant le comportement et les interactions des systèmes gérés. Dans la première phase, les composantes des politiques XACML ont été exprimées avec des expressions formelles basées sur la logique du premier ordre. Par la suite, les outils développés pour la méthode B, comme le langage Event-B sous la plate forme Rodin, ont été utilisés pour vérifier les règles des politiques par rapport à un ensemble de propriétés que nous avons définies. Notre approche est plus flexible et permet aux utilisateurs de tester et de vérifier les règles avant l'implémentation de ces politiques. Une telle vérification est fondée sur les preuves avec logique du premier ordre, où des propriétés importantes de la politique peuvent être énoncées et prouvées. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Politique, XACML, Méthode formelle, Event-B, Vérification.
8

Analyse des traces d'exécution pour la vérification des protocoles d'interaction dans les systèmes multiagents

Ben Ayed, Nourchène January 2003 (has links)
Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.
9

Verification and composition of security protocols with applications to electronic voting / Vérification et composition des protocoles de securité avec des applications aux protocoles de vote electronique

Ciobâcǎ, Ştefan 09 December 2011 (has links)
Cette these concerne la verification formelle et la composition de protocoles de securite, motivees en particulier par l'analyse des protocoles de vote electronique. Les chapitres 3 a 5 ont comme sujet la verification de protocoles de securite et le Chapitre 6 vise la composition.Nous montrons dans le Chapitre 3 comment reduire certains problemes d'une algebre quotient des termes a l'algebre libre des termes en utilisant des ensembles fortement complets de variants. Nous montrons que, si l'algebre quotient est donnee par un systeme de reecriture de termes convergent et optimalement reducteur (optimally reducing), alors des ensembles fortement complets de variants existent et sont finis et calculables.Dans le Chapitre 4, nous montrons que l'equivalence statique pour (des classes) de theories equationnelles, dont les theories sous-terme convergentes, la theorie de l'engagement a trappe (trapdoor commitment) et la theorie de signature en aveugle (blind signatures), est decidable en temps polynomial. Nous avons implemente de maniere efficace cette procedure.Dans le Chapitre 5, nous etendons la procedure de decision precedente a l'equivalence de traces. Nous utilisons des ensembles fortement complets de variants du Chapitre 3 pour reduire le probleme a l'algebre libre. Nous modelisons chaque trace du protocole comme une theorie de Horn et nous utilisons un raffinement de la resolution pour resoudre cette theorie. Meme si nous n'avons pas reussi a prouver que la procedure de resolution termine toujours, nous l'avons implementee et utilisee pour donner la premiere preuve automatique de l'anonymat dans le protocole de vote electronique FOO.Dans le Chapitre 6, nous etudions la composition de protocoles. Nous montrons que la composition de deux protocoles qui utilisent des primitives cryptographiques disjointes est sure s'ils ne revelent et ne reutilisent pas les secrets partages. Nous montrons qu'une forme d'etiquettage de protocoles est suffisante pour assurer la disjonction pour un ensemble fixe de primitives cryptographiques. / This thesis is about the formal verification and composition of security protocols, motivated by applications to electronic voting protocols. Chapters 3 to 5 concern the verification of security protocols while Chapter 6 concerns composition.We show in Chapter 3 how to reduce certain problems from a quotient term algebra to the free term algebra via the use of strongly complete sets of variants. We show that, when the quotient algebra is given by a convergent optimally reducing rewrite system, finite strongly complete sets of variants exist and are effectively computable.In Chapter 4, we show that static equivalence for (classes of) equational theories including subterm convergent equational theories, trapdoor commitment and blind signatures is decidable in polynomial time. We also provide an efficient implementation.In Chapter 5 we extend the previous decision procedure to handle trace equivalence. We use finite strongly complete sets of variants introduced in Chapter 3 to get rid of the equational theory and we model each protocol trace as a Horn theory which we solve using a refinement of resolution. Although we have not been able to prove that this procedure always terminates, we have implemented it and used it to provide the first automated proof of vote privacy of the FOO electronic voting protocol.In Chapter 6, we study composition of protocols. We show that two protocols that use arbitrary disjoint cryptographic primitives compose securely if they do not reveal or reuse any shared secret. We also show that a form of tagging is sufficient to provide disjointness in the case of a fixed set of cryptographic primitives.
10

Subwords : automata, embedding problems, and verification / Sous-mots : automates, problèmes de plongement, et vérification

Karandikar, Prateek 12 February 2015 (has links)
Garantir le fonctionnement correct des systèmes informatisés est un enjeu chaque jour plus important. La vérification formelle est un ensemble de techniquespermettant d’établir la correction d’un modèle mathématique du système par rapport à des propriétés exprimées dans un langage formel.Le "Regular model checking" est une technique bien connuede vérification de systèmes infinis. Elle manipule des ensembles infinis de configurations représentés de façon symbolique. Le "Regular model checking" de systèmes à canaux non fiables (LCS) soulève des questions fondamentales de décision et de complexité concernant l’ordre sous-mot qui modélise la perte de messages. Nous abordons ces questions et résolvons un problème ouvert sur l’index de la congruence de Simon pour les langages testables par morceaux.L’accessibilité pour les LCS est décidable mais de complexité F_{omega^omega} très élevée, bien au delà des complexités primitives récursives. Plusieurs problèmes de complexité équivalente ont été découverts récemment, par exemple dans la vérification de mémoire faibles ou de logique temporelle métrique. Le problème de plongement de Post (PEP) est une abstraction de l’accessibilité des LCS, lui aussi de complexité F_{omega^omega}, et qui nous sert de base dans la définition d’une classe de complexité correspondante. Nous proposons une généralisation commune aux deux variantes existantes de PEP et donnons une preuve de décidabilité simplifiée. Ceci permet d’étendre le modèle des systèmes à canaux unidirectionnels (UCS) par des tests simples tout en préservant la décidabilité de l’accessibilité. / The increasing use of software and automated systems has made it important to ensure their correct behaviour. Formal verification is the technique that establishes correctness of a system or a mathematical model of the system with respect to properties expressed in a formal language.Regular model checking is a common technique for verification of infinite-state systems - it represents infinite sets of configurations symbolically in a finite manner and manipulates them using these representations. Regular model checking for lossy channel systems brings up basic automata-theoretic questions concerning the subword relation on words which models the lossiness of the channels. We address these state complexity and decision problems, and also solve a long-standing problem involving the index of the Simon's piecewise-testability congruence.The reachability problem for lossy channel systems (LCS), though decidable, has very high F_{omega^omega} complexity, well beyond primitive-recursive. In recent times several problems with this complexity have been discovered, for example in the fields of verification of weak memory models and metric temporal logic. The Post Embedding Problem (PEP) is an algebraic abstraction of the reachability problem on LCS, with the same complexity, and is our champion for a "master" problem for the class F_{omega^omega}. We provide a common generalization of two known variants of PEP and give a simpler proof of decidability. This allows us to extend the unidirectional channel system (UCS) model with simple channel tests while having decidable reachability.

Page generated in 0.1451 seconds