Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La propension des systèmes informatiques à subir des défaillances matérielles est à l'origine d'une recherche abondante afin de concevoir des systèmes dits tolérants aux pannes. Le procédé couramment retenu consiste à procéder à des réplications, donnant alors naissance à ce que l'on nomme un système distribué. La question se pose alors de savoir si l'on peut garantir que les multiples copies sont cohérentes entre elles. Ainsi, la recherche d'un accord devient-elle un problème à résoudre, à portée paradigmatique : le Consensus. Or, la complexité des algorithmes de Consensus rend la tache ardue : il n'est donc pas rare que l'on commette des erreurs lors de leur conception. De là découle l'idée, développée depuis plus de trente ans, de recourir à des procédés de vérification mécanique des algorithmes et de leurs preuves de correction. Ces procédés prennent place parmi ce que l'on désigne usuellement comme étant des méthodes formelles. C'est à la croisée des recherches en algorithmique distribuée et en méthodes formelles que se situent nos travaux. Plus spécifiquement, il s'agit de faire usage d'un logiciel de certification formelle, Isabelle/HOL, afin de garantir l'exactitude des preuves de correction d'algorithmes de Consensus exprimés dans un cadre formel uniforme du nom de Heard-Of, proposé en 2009 par Charron-Bost et Schiper. Nous montrons que, du fait de leur expression dans un même cadre formel, et du fait de leur proximité, suivant les cas, soit de conception (nombre de rondes, recours à des mécanismes de vote, ...) soit de forme syntaxique, soit d'hypothèses de fonctionnement (synchronisme partiel, ...), ces algorithmes présentent des preuves dont une part conséquente d?arguments sont communs. Cela permet de copier certains d'entre eux d'une preuve à l'autre, afin de réduire l'effort de certification : ces arguments peuvent alors être automatiquement évalués par la machine pour chacun d'entre eux, l'utilisateur n'ayant à intervenir que là où celle-ci est en peine, c'est-à-dire lorsque les différences algorithmiques induisent qu'il faille réviser les détails de l'argumentation. L'exposé que nous faisons de la certification que nous avons effectuée pour six algorithmes distribués dédiés à la résolution du problème du Consensus illustre cette démarche. Par conséquent, nous présentons d'abord les portions communes des démonstrations, puis détaillons ce qui est propre à chacune, l'objectif n'étant pas de permettre une lecture linéaire de chaque démonstration mais de mettre en évidence notre proposition / Computer systems fail. Whatever the reason of these failures, it has been a widespread approach to try and increase the faults-tolerance of a computer system through its replication. The resulting system is said to be a distributed one, in which replicas have to be kept consistent with each others. Hence, reaching agreement, and Consensus in particular, becomes the problem to solve - indeed, the paradigm. Solving Consensus (under various assumptions) is a hard task : algorithms designed on this purpose are subtle and proving their being correct is error-prone - whenever they are, which occasionally appears not to be the case. For more that thirty years, researchers interested in what is called Formal Methods have been working on mechanizing the verification process, in order to increase confidence in the correctness of (distributed) algorithms. The work we present here is at the intersection of distributed algorithms and formal methods. We use the Isabelle/HOL software to certify the correctness proof of various Consensus algorithms expressed in a uniform framework based on the Heard-Of Model, introduced by Charron-Bost and Schiper in 2009. Expressed in a common model, these algorithms, which, depending on the case, share some common mecanisms (number of steps, intermediate votes, ...), some elements of syntax, or types of assumptions (partial synchronism...), can be proved using some common arguments. As a consequence, the certification effort can be reduced by copying some intermediate lemmas from one proof to another and let the computer automatically parse them until some manual adaptation is required. This lead to the idea of certifying the correctness of multiple algorithms all together, instead of proving them one after the other, as one would do on paper in a traditional way. The effort of translation in the formal language of the proof assistant is then possibly reduced. Of course, each proof will also contain specific arguments, which will have to be isolated and translated into the software. Here, we illustrate this proposition through the presentation of formal certificates of correctness for six Consensus algorithms. As a consequence, on should not expect to find here a comprehensive linear presentation of each proof : we first show the arguments shared by multiple proofs, followed by those which are specific to each o them

Les applications complexes comme la téléphonie mobile, la télévision numérique ou la visiophonie exigent une grande puissance de calcul, mais aussi une flexibilité accrue afin de suivre l'évolution des standards. L'intégration de tels systèmes sur une seule puce requiert l'embarcation de processeurs devant respecter des contraintes de performances, de coût en <br />surface et de faible consommation. Leur conception en un temps réduit met en oeuvre des compilateurs rapidement reciblables, ainsi que de nouveaux outils d'aide à la conception. <br />Ceux-­ci sont nécesssaire pour suivre le cycle de vie de tels processeurs, composé d'étapes de réduction de coût et de réutilisation. Cette thèse présente plusieurs techniques visant à réduire le temps de développement du couple logiciel­processeur embarqué, à savoir la <br />validation fonctionnelle à haut­niveau et l'aide au raffinement de l'architecture et du jeu d'instructions. <br />La validation de la description haut­niveau du logiciel embarqué est assurée dans son en­ vironnement matériel réel grâce à la co­simulation C­VHDL, développée durant cette thèse. <br />La mise au point du logiciel est alors facilitée par l'utilisation d'outils de développement standard, et par la faculté à simuler le système complet sur un large intervalle de temps. L'aide au raffinement d'architecture est assurée par la re­configuration automatique d'un <br />compilateur reciblable, afin d'explorer un grand nombre de solutions en un temps réduit. L'analyse de codes applicatifs typiques ainsi compilés permet d'isoler les configurations architecturales performantes. De plus, un outil d'estimation se concentrant sur l'encodage des champs constants dans le le jeu d'instructions est proposé.

La qualité de service temporelle permet à l'utilisateur d'une application à composants d'estimer les propriétés extra-fonctionnelles l'application. Afin d'obtenir une estimation précise de la qualité, les informations de qualité de service temporelle doivent être présentes durant le processus de développement de l'application, de la spécification jusqu'à l'implantation. La contribution de cette thèse est la définition d'un processus de gestion de la qualité de service temporelle pendant le développement d'une application à composants. Nous nous intéressons dans un premier temps à l'introduction des informations temporelles lors de la spécification de l'application. Nous utilisons une approche à base de motifs pour intégrer le temps dans la spécification de l'application. Dans un second temps, nous fournissons un moniteur de qualité de service temporelle à partir de la spécification. Le moniteur s'assure, pendant l'exécution, que l'application respecte la qualité de service temporelle requise par la spécification. Finalement, nous décrivons notre outil /Thot/ implantant le processus de gestion de la qualité de service temporelle et nous l'utilisons sur un cas d'application.

Le présent document présente d'abord un bref historique ainsi que les concepts de base de la génétique de population pour ensuite présenter les concepts utilisés pour développer le module d'assistance au jumelage du programme Analypop, un programme de gestion et d'analyse de registre de population. Par la suite, nous verrons comment la conception choisie permet aux chercheurs d'effectuer la consultation ainsi que d'enregistrer certains changements dans le registre de population. Finalement, nous verrons deux fonctionnalités qui permettent d'exporter les données pour qu'elles puissent être traitées par d'autres programmes. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Logiciel, Démographie, Registre de Population, Analypop.

Les termes client Web riche ou interface riche sont utilisés pour désigner l'interface utilisateur d'une application Web qui comprend des fonctionnalités et des méthodes d'interactions similaires à celles des interfaces utilisateurs conventionnelles. Un client Web riche assure une part du traitement de l'application. Cela peut aller de la validation de saisies jusqu'à la prise en charge complète des interactions avec l'utilisateur. Il doit donc être doté d'une certaine intelligence, c'est-à-dire que du code, décrivant son comportement ainsi qu'une part de la logique d'affaire de l'application, doit pouvoir y être exécuté. L'utilisation de méthodes d'interactions avancées (comme le glisser-déplacer, la saisie semi-automatique ou l'utilisation de contrôles « widgets ») implique aussi des capacités de traitement plus poussées que pour les clients Web standards. Il existe une multitude de technologies pouvant êtres utilisées pour le développement d'un client Web riche. Le principal problème relié à cette situation est que les projets basés sur une technologie de présentation deviennent dépendants de cette dernière. Un changement de technologie implique alors la perte des investissements relatifs au développement de la partie client. Le fait d'avoir à supporter plusieurs plateformes de présentation implique aussi généralement d'avoir à maintenir plusieurs versions distinctes du client de l'application. Ces travaux couvrent les approches existantes et la conceptualisation d'une nouvelle approche permettant de définir, indépendamment d'une technologie de présentation, le volet client d'une application. Celle-ci a été expérimentée à l'intérieur de trois projets concrets présentés sous forme d'étude de cas. Une revue des plateformes d'exécution contemporaines pour les clients Web riches y est effectuée, suivi d'un état de l'art couvrant les méthodes existantes pour la définition d'interfaces utilisateur. Les travaux s'intéressant à la définition d'interfaces utilisateurs à l'aide de dialectes XML sont également couverts, de même que les architectures couramment utilisées pour la définition d'un client Web riche. Les résultats obtenus à l'intérieur des études de cas auront permis de montrer la faisabilité de l'approche ainsi que de mesurer certains avantages de celle-ci selon différents critères de qualité.

Nous pouvons voir le développement d'un logiciel selon deux perspectives. La première concerne le développement, par un programmeur ou une petite équipe de programmeurs, d'un petit logiciel, avec un utilisateur et un seul ordinateur. C'est ce qu'on appelle de la programmation à petite échelle (programming in the small). Ce genre de développement s'enseigne dans les cours de programmation en informatique (computer science). La deuxième perspective consiste à faire de la programmation à grande échelle avec plusieurs équipes de programmeurs, plusieurs fonctionnalités, plusieurs utilisateurs et même, parfois, plusieurs ordinateurs et serveurs. C'est ce qu'on appelle le génie logiciel (software engineering), qui s'enseigne dans des baccalauréats en génie logiciel. Même si beaucoup de progrès a été fait en génie logiciel, il reste qu'il existe encore des lacunes dans l'enseignement de cette discipline. Les difficultés se situent, entre autres, dans les cours d'introduction à la programmation. Il y a plusieurs façons d'enseigner le développement de logiciels. Cependant, peu importe celle qui est employée, la transition entre la programmation à petite échelle et la programmation à grande échelle n'est pas facile. Nous désirons donc créer une méthode qui favorise la résolution de problèmes, tout en facilitant la transition ultérieure vers les grands projets. Nous croyons également que la transition serait plus facile si ladite méthode de développement utilisait des principes de génie logiciel déjà utilisés et reconnus. C'est pourquoi nous avons tenu compte d'un corpus de connaissances en génie logiciel (Abran et aL, 2001) dans la construction de la méthode.

Le débogage tient une place grandissante dans le cycle de développement d'un logiciel. Les recherches dans ce domaine tentent de créer des outils permettant un accès plus rapide aux fautes, quel que soit le langage de programmation utilisé. Étant donné l'indépendance du code Java vis-à-vis de la plateforme sur laquelle il est exécuté, la machine virtuelle Java doit fournir un ensemble de mécanismes permettant aux outils de débogage d'accéder aux informations relatives à l'exécution de l'application déboguée. Bien que la grande majorité des machines virtuelles commerciales soient dotées de mécanismes de support au débogage, aucune libre, en revanche, n'offrait une telle fonctionnalité à l'achèvement de nos travaux. La principale motivation derrière ce mémoire a été la mise en lumière des différentes étapes jalonnant la mise en place d'une architecture de débogage Java totalement libre. Nous décrivons ici le choix de l'architecture et les critères nous ayant conduits à ce choix. Nous détaillons également les entités intervenant dans cette architecture, leur nature et leur rôle. Nous proposons enfin une critique constructive des normes régissant ce domaine, suggérant quelques améliorations possibles. Dans le cadre de nos travaux, nous avons réalisé l'implantation de l'interface de débogage Java (Java Virtual Machine Debug Interface, JVMDI) au sein de SableVM, machine virtuelle Java libre et conforme aux normes. D'autre part, nous avons développé un module indépendant permettant d'établir la connexion entre machine virtuelle Java et débogueur. Ce module gère également les objets manipulés durant une session de débogage, ainsi que les événements générés par la machine virtuelle. Finalement, nous avons connecté les éléments conçus ou modifiés dans le cadre de notre étude à d'autres éléments existants au préalable (Eclipse, un débogueur Java disponible librement). Les résultats obtenus lors des tests nous ont conforté dans les différents choix effectués lors du développement. L'utilisation de débogueurs totalement indépendants de la machine virtuelle utilisée, tel Eclipse, et la bonne tenue des sessions de débogage effectuées ont permis la validation de la conformité de nos travaux aux normes en vigueur. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Machine virtuelle, Java, SableVM, Débogage, Interface de débogage, Architecture de débogage, JDWP, JVMDI, JPDA, JVMTI, JRE.

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.