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

Se procurer les outils les plus récents et les plus performants liés à la sécurisation de réseaux informatique est loin d'être suffisant pour réduire les risques d'intrusions. En effet, le maillon le plus faible dans la chaîne de la sécurité informatique est souvent l'intervention humaine qui est parfois nécessaire pour installer et configurer ces outils. Limiter cette intervention humaine permettra sans doute de réduire à la fois les risques et les coûts engendrés par la sécurité. Il est important, par exemple, de développer des méthodes sûres permettant de configurer automatiquement un réseau informatique de sorte que son comportement soit conforme à une politique de sécurité donnée. C'est dans cet axe de recherche que se situe ce travail. En effet, nous proposons une méthode formelle permettant de générer à partir d'une politique de sécurité (spécifiée par une formule logique) et d'un réseau informatique (spécifié par un processus) une configuration sécuritaire de ce réseau.

Ce document présente SCOOP, un nouveau cadriciel Python pour la distribution automatique de hiérarchies de tâches dynamiques axé sur la simplicité. Une hiérarchie de tâches réfère à des tâches qui peuvent récursivement générer un nombre arbitraire de sous-tâches. L’infrastructure de calcul sous-jacente consiste en une simple liste de ressources de calcul. Le cas d’utilisation typique est l’exécution d’un programme principal sous la tutelle du module SCOOP, qui devient alors la tâche racine pouvant générer des sous-tâches au travers de l’interface standard des « futures » de Python. Ces sous-tâches peuvent elles-mêmes générer d’autres sous-sous-tâches, etc. La hiérarchie de tâches complète est dynamique dans le sens où elle n’est potentiellement pas entièrement connue jusqu’à la fin de l’exécution de la dernière tâche. SCOOP distribue automatiquement les tâches parmi les ressources de calcul disponibles en utilisant un algorithme de répartition de charge dynamique. Une tâche n’est rien de plus qu’un objet Python pouvant être appelé en conjonction avec ses arguments. L’utilisateur n’a pas à s’inquiéter de l’implantation du passage de message ; toutes les communications sont implicites. / This paper presents SCOOP, a new Python framework for automatically distributing dynamic task hierarchies focused on simplicity. A task hierarchy refers to tasks that can recursively spawn an arbitrary number of subtasks. The underlying computing infrastructure consists of a simple list of resources. The typical use case is to run the user’s main program under the umbrella of the SCOOP module, where it becomes a root task that can spawn any number of subtasks through the standard “futures” API of Python, and where these subtasks may themselves spawn other subsubtasks, etc. The full task hierarchy is dynamic in the sense that it is unknown until the end of the last running task. SCOOP automatically distributes tasks amongst available resources using dynamic load balancing. A task is nothing more than a Python callable object in conjunction with its arguments. The user need not worry about message passing implementation details; all communications are implicit.

Titre de l'écran-titre (visionné le 28 février 2024) / Avec l'avènement de la technologie de la chaîne de blocs, un nouveau type de contrat appelé contrat intelligent a émergé. Les contrats intelligents sont des programmes informatiques permettant de formaliser des accords contractuels complexes tout en assurant automatiquement le respect de ces accords sans l'aide d'intermédiaires de confiance. Aujourd'hui, ils gèrent des millions de dollars en jetons numériques et effectuent des tâches quotidiennes de processus métier. Compte tenu des énormes enjeux financiers, les pirates informatiques sont plus que jamais motivés à exploiter tout bogue dans les contrats intelligents ou l'infrastructure sous-jacente. Une grande prudence est donc requise avant le déploiement des contrats intelligents, d'autant plus qu'ils deviennent immuables (*pas de possibilité de les modifier*) une fois déployés sur la chaîne de blocs. Écrire des contrats intelligents sécurisés et fiables est une tâche ardue et les méthodes existantes de sécurisation des contrats intelligents reposent largement sur l'expérience du programmeur, laissant ainsi place à des erreurs de logique et d'inattention. Dans cette thèse, nous proposons une approche novatrice basée sur la réécriture de programmes pour renforcer la sécurité des contrats intelligents. Plus précisément, étant donné un contrat intelligent *S* et une politique de sécurité *ϕ*, nous dérivons un nouveau contrat intelligent *S'* à partir de *S* et de *ϕ* de telle sorte que *S′* satisfait la politique de sécurité *ϕ* et reste correct par rapport à *S*. Le contrat *S′* (*c'est-à-dire le contrat sécurisé*) est celui qui sera en fin de compte déployé sur la chaîne de blocs. L'approche présentée utilise l'algèbre SBPA$^\textup{*}_\textup{0,1}$ qui est une variante de BPA$^\textup{*}_\textup{0,1}$ (*Basic Process Algebra*) étendue avec des variables, des environnements et des conditions pour formaliser et résoudre le problème. Le problème de trouver la version sécuritaire *S′* à partir de *S* et de *ϕ* se transforme en un problème de résolution d'un système d'équations linéaires pour lequel nous savons déjà comment extraire la solution dans un temps polynomial. Cette recherche contribue à combler le fossé dans la sécurisation des contrats intelligents et ouvre la voie à une adoption plus large de cette technologie révolutionnaire. / With the advent of blockchain technology, a new type of contract called smart contract has emerged. Smart contracts are computer programs to formalize complex contractual agreements while automatically ensuring compliance with these agreements without the help of trusted intermediaries. Today, they manage millions of dollars in digital tokens and perform daily business process tasks. Given the huge financial stakes, hackers are more motivated than ever to exploit any bugs in smart contracts or the underlying infrastructure. Great caution is therefore required before deploying smart contracts, especially since they become immutable (*no possibility to modify them*) once deployed on the blockchain. Writing secure and reliable smart contracts is a daunting task and existing methods of securing smart contracts rely heavily on the experience of the programmer, leaving room for errors of logic and carelessness. In this thesis, we propose an innovative approach based on program rewriting to strengthen the security of smart contracts. Specifically, given a smart contract *S* and a security policy *ϕ*, we derive a new smart contract *S′* from *S* and *ϕ* such that *S′* satisfies the security policy *ϕ* and remains correct with respect to *S*. The *S′* contract (*i.e. the secure contract*) is the one that will ultimately be deployed on the blockchain. The presented approach uses the algebra SBPA$^\textup{*}_\textup{0,1}$ which is a variant of BPA$^\textup{*}_\textup{0,1}$ (*Basic Process Algebra*) extended with variables, environments and conditions to formalize and solve the problem. The problem of finding the secure version *S′* from *S* and *ϕ* turns into a problem of solving a system of linear equations for which we already know how to extract the solution in polynomial time. This research helps bridge the gap in securing smart contracts and paves the way for wider adoption of this game-changing technology.

Dans ce travail, nous définissons une nouvelle algèbre de processus basée sur CCS. Cette algèbre, qui est destinée à la sécurisation formelle de réseaux, est munie d'un opérateur de surveillance qui permet de contrôler les entrées et les sorties d'un processus, ou d'un sous-processus, à l'image d'un pare-feu dans un réseau informatique. L'algèbre permet donc de modéliser des réseaux munis de moniteurs, et également, n'importe quel système communicant devant être contrôlé par des moniteurs. Avant d'entrer dans le vif du sujet, nous débutons par une revue des approches globales en détection d'intrusions, soient l'approche comportementale et l'approche par scénarios. Nous parcourons par la suite différents langages formels destinés à la modélisation de systèmes communicants, en prêtant une attention particulière aux algèbres de processus.

La parallélisation est une solution possible pour améliorer un simulateur séquentiel s'il devient trop lent dû à une surcharge de calculs et qu'on ne désire pas concevoir à neuf un nouveau simulateur parallèle. Ce mémoire présente la conception UML d'une architecture pour un simulateur parallèle flexible et extensible capable de gérer différents environnements de déploiement par une configuration au temps d'exécution. Ce projet a vu le jour dans le but d'améliorer les performances de l'architecture KARMA, une architecture séquentielle pour la simulation d'engagements d'armes, pour réussir à atteindre le temps-réel dans une simulation haute-fidélité avec matériel dans la boucle. L'approche retenue propose une architecture non commerciale et développable à faibles coûts. L'implémentation et les tests préliminaires ont été basés sur un logiciel source libre et portable sur plusieurs plates-formes nommé ACE.

Depuis une dizaine d'année, l'évolution des machines de calcul tend vers des architectures parallèles et hétérogènes. Composées de plusieurs nœuds connectés via un réseau incluant chacun des unités de traitement hétérogènes, ces grilles offrent de grandes performances. Pour programmer ces architectures, l'utilisateur doit s'appuyer sur des modèles de programmation comme MPI, OpenMP, CUDA. Toutefois, il est toujours difficile d'obtenir à la fois une bonne productivité du programmeur, qui passe par une abstraction des spécificités de l'architecture et performances. Dans cette thèse, nous proposons d'exploiter l'idée qu'un modèle de programmation spécifique à un domaine applicatif particulier permet de concilier ces deux objectifs antagonistes. En effet, en caractérisant une famille d'applications, il est possible d'identifier des abstractions de haut niveau permettant de les modéliser. Nous proposons deux modèles spécifiques au traitement du signal et de l'image sur cluster hétérogène. Le premier modèle est statique. Nous lui apportons une fonctionnalité de migration de tâches. Le second est dynamique, basé sur le support exécutif StarPU. Les deux modèles offrent d'une part un haut niveau d'abstraction en modélisant les applications de traitement du signal et de l'image sous forme de graphe de flot de données et d'autre part, ils permettent d'exploiter efficacement les différents niveaux de parallélisme tâche, données, graphe. Ces deux modèles sont validés par plusieurs implémentations et comparaisons incluant deux applications de traitement de l'image du monde réel sur cluster CPU-GPU. / Since a decade, computing systems evolved to parallel and heterogeneous architectures. Composed of several nodes connected via a network and including heterogeneous processing units, clusters achieve high performances. To program these architectures, the user must rely on programming models such as MPI, OpenMP or CUDA. However, it is still difficult to conciliate productivity provided by abstracting the architectural specificities, and performances. In this thesis, we exploit the idea that a programming model specific to a particular domain of application can achieve these antagonist goals. In fact, by characterizing a family of application, it is possible to identify high level abstractions to efficiently model them. We propose two models specific to the implementation of signal and image processing applications on heterogeneous clusters. The first model is static. We enrich it with a task migration feature. The second model is dynamic, based on the StarPU runtime. Both models offer firstly a high level of abstraction by modeling image and signal applications as a data flow graph and secondly they efficiently exploit task, data and graph parallelisms. We validate these models with different implementations and comparisons including two real-world applications of images processing on a CPU-GPU cluster.

Les trois principales ressources du calcul sont le temps, l'espace et l'énergie, les minimiser constitue un des défis les plus importants de la recherche de la performance des processeurs.Dans cette thèse, nous nous intéressons à un quatrième facteur qui est l'information. L'information a un impact direct sur ces trois facteurs, et nous montrons comment elle contribue ainsi à l'optimisation des performances. Landauer a montré que c’est la destruction - logique - d’information qui coûte de l’énergie, ceci est un résultat fondamental de la thermodynamique en physique. Sous cette hypothèse, un calcul ne consommant pas d’énergie est donc un calcul qui ne détruit pas d’information. On peut toujours retrouver les valeurs d’origine et intermédiaires à tout moment du calcul, le calcul est réversible. L'information peut être portée non seulement par une donnée mais aussi par le processus et les données d’entrée qui la génèrent. Quand un calcul est réversible, on peut aussi retrouver une information au moyen de données déjà calculées et du calcul inverse. Donc, le calcul réversible améliore la localité de l'information. La thèse développe ces idées dans deux directions. Dans la première partie, partant d'un calcul, donné sous forme de DAG (graphe dirigé acyclique), nous définissons la notion de « garbage » comme étant la taille mémoire – le nombre de registres - supplémentaire nécessaire pour rendre ce calcul réversible. Nous proposons un allocateur réversible de registres, et nous montrons empiriquement que le garbage est au maximum la moitié du nombre de noeuds du graphe.La deuxième partie consiste à appliquer cette approche au compromis entre le recalcul (direct ou inverse) et le stockage dans le contexte des supercalculateurs que sont les récents coprocesseurs vectoriels et parallèles, cartes graphiques (GPU, Graphics Processing Unit), processeur Cell d’IBM, etc., où le fossé entre temps d’accès à la mémoire et temps de calcul ne fait que s'aggraver. Nous montons comment le recalcul en général, et le recalcul inverse en particulier, permettent de minimiser la demande en registres et par suite la pression sur la mémoire. Cette démarche conduit également à augmenter significativement le parallélisme d’instructions (Cell BE), et le parallélisme de threads sur un multicore avec mémoire et/ou banc de registres partagés (GPU), dans lequel le nombre de threads dépend de manière importante du nombre de registres utilisés par un thread. Ainsi, l’ajout d’instructions du fait du calcul inverse pour la rematérialisation de certaines variables est largement compensé par le gain en parallélisme. Nos expérimentations sur le code de Lattice QCD porté sur un GPU Nvidia montrent un gain de performances atteignant 11%. / The main resources for computation are time, space and energy. Reducing them is the main challenge in the field of processor performance.In this thesis, we are interested in a fourth factor which is information. Information has an important and direct impact on these three resources. We show how it contributes to performance optimization. Landauer has suggested that independently on the hardware where computation is run information erasure generates dissipated energy. This is a fundamental result of thermodynamics in physics. Therefore, under this hypothesis, only reversible computations where no information is ever lost, are likely to be thermodynamically adiabatic and do not dissipate power. Reversibility means that data can always be retrieved from any point of the program. Information may be carried not only by the data but also by the process and input data that generate it. When a computation is reversible, information can also be retrieved from other already computed data and reverse computation. Hence reversible computing improves information locality.This thesis develops these ideas in two directions. In the first part, we address the issue of making a computation DAG (directed acyclic graph) reversible in terms of spatial complexity. We define energetic garbage as the additional number of registers needed for the reversible computation with respect to the original computation. We propose a reversible register allocator and we show empirically that the garbage size is never more than 50% of the DAG size. In the second part, we apply this approach to the trade-off between recomputing (direct or reverse) and storage in the context of supercomputers such as the recent vector and parallel coprocessors, graphical processing units (GPUs), IBM Cell processor, etc., where the gap between processor cycle time and memory access time is increasing. We show that recomputing in general and reverse computing in particular helps reduce register requirements and memory pressure. This approach of reverse rematerialization also contributes to the increase of instruction-level parallelism (Cell) and thread-level parallelism in multicore processors with shared register/memory file (GPU). On the latter architecture, the number of registers required by the kernel limits the number of running threads and affects performance. Reverse rematerialization generates additional instructions but their cost can be hidden by the parallelism gain. Experiments on the highly memory demanding Lattice QCD simulation code on Nvidia GPU show a performance gain up to 11%.

Dans leur présentation traditionnelle, les systèmes à mémoire distribuée virtuellement partagée (MVP, en anglais DSM) permettent à des processus de partager un espace d'adressage commun selon un modèle de cohérence fixé : cohérence séquentielle, à la libération, etc. Les pro- cessus peuvent habituellement être distribués sur des noeuds physiquement distincts et leurs in- teractions par la mémoire commune sont implémentées (de manière transparente) par la MVP, en utilisant une bibliothèque de communication. Dans la plupart de travaux dans ce domaine, il est sous-entendu que la MVP et l'architecture sous-jacente sont données. Le programmeur doit alors adapter son application à ce cadre fixe, afin d'obtenir une exécution efficace. Cette approche impose des limitations statiques et ne permet pas de comparer des approches alternatives. La contribution de cette thèse consiste à proposer une plate-forme générique d'implémentation et d'expérimentation appelée DSM-PM2, qui permet de développer et d'optimiser conjointement les applications distribuées et le(s) protocole(s) de cohérence de la MVP sous-jacente. Cette plate-forme, implémentée entièrement au niveau logiciel, est portable sur plusieurs architectures de grappes hautes performances. Elle fournit les briques de bases nécessaires pour implémenter et évaluer une large classe de protocoles de cohérence multithreads dans un cadre unifié. Trois mo- dèles de cohérence sont actuellement supportés : la cohérence séquentielle, la cohérence à la libéra- tion et la cohérence Java. Plusieurs études de performance ont été effectuées à l'aide d'applications multithreads pour l'ensemble des protocoles proposés, sur différentes plates-formes. DSM-PM a été validé par son utilisation en tant que cible d'un système de compilation Java pour des grappes appelé Hyperion.

Les besoins en puissance de calcul des processeurs sont en constante augmentation en raison de l'importance croissante des applications multimédia dans la vie courante. Ces applications requièrent de nombreux calculs avec des données de faible précision généralement issues des pixels. Le moyen le plus efficace pour exploiter le parallélisme de données de ces applications est le parallélisme dit de sous-mots (SWP pour \textit{subword parallelism}). Les opérations sont effectuées en parallèle sur des données de faible précision regroupées ce qui permet d'utiliser au mieux les ressources disponibles dimensionnées pour traiter des mots. Dans cette thèse, la conception de différents opérateurs SWP pour les applications multimédia est proposée. Une bonne adéquation entre largeur des sous-mots et largeur des données manipulées permet une meilleure utilisation des ressources et conduit ainsi à améliorer l'efficacité de l'exécution de l'application sur le processeur. Les opérateurs arithmétiques de base développés sont ensuite utilisés dans un opérateur SWP reconfigurable. Ce dernier peut être configuré pour effectuer diverses opérations multimédia avec différentes largeurs de données. L'opérateur reconfigurable peut être utilisé comme unité spécialisée ou comme co-processeur dans un processeur multimédia afin d'en améliorer les performances. La vitesse interne des différentes unités de traitement est également améliorée en représentant les nombres en système redondant plutôt qu'en système binaire. Le système redondant permet entre autre d'augmenter la vitesse des opérations arithmétiques en évitant une propagation de retenue couteuse lors d'opérations d'addition. Les résultats obtenus montrent l'intérêt en terme de performances d'utiliser des opérateurs SWP lors de l'exécution d'applications multimédia.