Les systèmes embarqués sont de plus en plus présents dans notre quotidien, à l’instar des téléphones ou des équipements des voitures modernes. Les systèmes embarqués modernes utilisent des plates-formes de plus en plus complexes. Après avoir longtemps utilisé un seul processeur, les plates-formes modernes peuvent désormais contenir plusieurs processeurs. Depuis quelques années, afin de continuer à améliorer la performance de ces systèmes à moindre coût, certaines de ces plates-formes embarquent désormais plusieurs processeurs différents, parfois même capables de modifier rapidement leurs caractéristiques pendant l’exécution du système. C’est ce qu’on appelle des plates-formes hétérogènes.Cette thèse traite de l’ordonnancement d’applications temps réel strict pour des plates-formes hétérogènes reconfigurables. Établir une polituqe d’ordonnancement consiste à garantir l’exécution d’ensembles de tâches récurrentes, avec le respect des contraintes temporelles de chaque tâche. Dans un contexte de temps réel strict, une tâche doit nécessairement être pleinement exécutée avant son échéance. Tout retard pourrait compromettre la sécurité du système ou des utilisateurs.Produire un ordonnancement temps réel strict efficace pour de telles plates-formes hétérogènes est particulièrement difficile. En effet, la vitesse d’exécution d’un processeur d’une telle plates-forme dépend à la fois du type du processeur et de la tâche exécutée. Cela rend les tâches difficilement interchangeables et augmente ainsi considérablement la complexité des polituqes d’ordonnancement. De plus, le coût d’une migration – le déplacement d’une tâche en cours d’exécution – d’un processeur à un autre est élevé, ce qui peut rendre les polituqes d’ordonnancement peu efficaces en pratique.Dans cette thèse, deux voies sont explorées pour tirer parti des possibilités offertes par ces plates-formes hétérogènes. Tout d’abord, en proposant un ordonnanceur dit global, qui permet une utilisation théorique de l’entièreté de la plates-forme. Pour atteindre cet objectif, nous isolons différents sous-problèmes, en suivant un schéma établi par la littérature existante. Pour chaque sous-problème, nous proposons une amélioration significative par rapport à l’état de l’art. L’ensemble constitue un nouvel ordonnanceur. Une évaluation empirique montre que ses performances sont bien supérieures à celles des ordonnanceurs existants. De plus, la polituqe d’ordonnancement proposée a une meilleure applicabilité, car elle réduit le nombre de migrations d’un processeur à un autre.Une deuxième voie explorée est le paradigme d’application dite multimode. Nous proposons ici le premier modèle où le matériel comme le logiciel peuvent être modifiés pendant l’exécution de l’application, afin de s’adapter au contexte dans lequel elle se trouve. Enfin, deux nouveaux protocoles utilisant ce modèle sont proposés et évalués. Il est montré théoriquement et empiriquement que ces protocoles présentent une faible complexité et de bonnes performances, et correspondent donc au besoin d’applications réelles. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Transport and trade of gas are decoupled after the liberalization of the European gas markets, which are now organized as so-called entry-exit systems. At the core of this market system are bookings and nominations, two special capacity-right contracts that grant traders access to the gas network. The latter is operated by a separate entity, known as the transmission system operator (TSO), who is in charge of the transport of gas from entry to exit nodes. In the mid to long term, traders sign a booking contract with the TSO to obtain injection and withdrawal capacities at entry and exit nodes, respectively. On a day-ahead basis, they then nominate within these booked capacities a balanced load flow of the planned amounts of gas to be injected into and withdrawn from the network the next day. The key property is that by signing a booking contract, the TSO is obliged to guarantee transportability for all balanced load flows in compliance with the booked capacities. To assess the feasibility of a booking, it is therefore necessary to check the feasibility of infinitely many nominations. As a result, deciding if a booking is feasible is a challenging mathematical problem, which we investigate in this dissertation.Our results range from passive networks, consisting of pipes only, to active networks, containing controllable elements to influence gas flows. Since the study of the latter naturally leads to a bilevel framework, we first consider some more general properties of bilevel optimization. For the case of linear bilevel optimization, we consider the hardness of validating the correctness of big-Ms often used in solving these problems via a single-level reformulation. We also derive a family of valid inequalities to be used in a bilevel-tailored branch-and-cut algorithm as a big-M-free alternative.We then turn to the study of feasible bookings. First, we present our results on passive networks, for which bilevel approaches are not required. A characterization of feasible bookings on passive networks is derived in terms of a finite set of nominations. While computing these nominations is a difficult task in general, we present polynomial complexity results for the special cases of tree-shaped or single-cycle passive networks. Finally, we consider networks with linearly modeled active elements. After obtaining a bilevel optimization model that allows us to determine the feasibility of a booking in this case, we derive various single-level reformulations to solve the problem. In addition, we obtain novel characterizations of feasible bookings on active networks, which generalize our characterization in the passive case. The performance of these various approaches is compared in a case study on two networks from the literature, one of which is a simplified version of the Greek gas network. / Transport et commerce de gaz sont découplés depuis la libéralisation des marchés européens du gaz, qui sont désormais organisés en systèmes dit d'entrée-sortie. Au cœur de ce système de marché se trouvent les réservations et les nominations, deux contrats spéciaux de droit à la capacité qui permettent aux négociants d'accéder au réseau de gaz. Ce dernier est exploité par une entité distincte, appelée gestionnaire de réseau de transport~(GRT), qui est chargée du transport du gaz entre les nœuds d'entrée et de sortie. À moyen et long terme, les négociants signent un contrat de réservation avec le GRT pour obtenir des capacités d'injection et d'extraction aux nœuds d'entrée et de sortie, respectivement. Au jour le jour, ils désignent ensuite, dans les limites des capacités réservées, un flux de charge équilibrée des quantités de gaz prévues à injecter et à extraire le lendemain. La propriété essentielle est qu'en signant un contrat de réservation, le GRT est obligé de garantir la transportabilité de tous les flux de charge équilibrée respectant les capacités réservées. Pour évaluer la faisabilité d'une réservation, il est donc nécessaire de vérifier la faisabilité d'une infinité de nominations. Par conséquent, décider si une réservation est réalisable est un problème mathématique difficile, que nous étudions dans cette thèse.Nos résultats vont des réseaux passifs, constitués uniquement de pipelines, aux réseaux actifs, contenant des éléments contrôlables pour influencer les flux de gaz. Comme l'étude de ces derniers conduit naturellement à un cadre biniveau, nous considérons d'abord certaines propriétés plus générales de l'optimisation biniveau. Pour le cas de l'optimisation biniveau linéaire, nous étudions la difficulté de valider l'exactitude des constantes de type big-M souvent utilisées dans la résolution de ces problèmes via une reformulation à un seul niveau. Nous déduisons également une famille d'inégalités valides à utiliser dans un algorithme de branch-and-cut adapté au biniveau comme alternative à l'approche utilisant des big-Ms.Nous nous tournons ensuite vers l'étude des réservations réalisables. D'abord, nous présentons nos résultats sur les réseaux passifs, pour lesquels les approches biniveaux ne sont pas nécessaires. Une caractérisation des réservations réalisables sur les réseaux passifs est déduite en termes d'un ensemble fini de nominations. Bien que le calcul de ces nominations soit une tâche difficile en général, nous présentons des algorithmes polynomiaux pour les cas particuliers des réseaux passifs en forme d'arbre ou contenant un cycle unique. Enfin, nous considérons les réseaux avec des éléments actifs modélisés à l'aide de contraintes linéaires. Après avoir obtenu un modèle biniveau, permettant de déterminer la faisabilité d'une réservation dans ce cas, nous dérivons diverses reformulations à un seul niveau pour résoudre le problème. En outre, nous obtenons de nouvelles caractérisations des réservations réalisables sur les réseaux actifs, qui généralisent notre caractérisation dans le cas passif. La performance de ces différentes approches est comparée dans une étude de cas réalisée sur deux réseaux de la littérature, dont l'un est une version simplifiée du réseau de gaz grec. / Nach der Liberalisierung der europäischen Gasmärkte, welche nun als sogenannte Entry-Exit Systeme organisiert sind, sind Transport und Handel von Gas entkoppelt. Im Zentrum dieses neuen Marktsystems sind Buchungen und Nominierungen, zwei spezielle Kapazitätrechtsverträge, die Händlern Zugang zum Gasnetz gewähren. Letzteres wird von einem separaten Akteur betrieben, dem sogenannten Fernleitungsnetzbetreiber (FNB), der für den Transport des Gases von den Einspeise- zu den Ausspeiseknoten verantwortlich ist. Händler schließen mittel- bis langfristig einen Buchungsvertrag mit dem FNB ab, um Ein- und Ausspeisekapazitäten zu erhalten. Täglich nominieren sie dann innerhalb der gebuchten Kapazitäten einen bilanzierten Lastfluss der geplanten Gasmengen, die am nächsten Tag eingespeist und entnommen werden sollen. Die Haupteigenschaft ist, dass der FNB sich durch Unterzeichnung eines Buchungsvertrages für die Transportierbarkeit aller bilanzierten Lastflüsse innerhalb der gebuchten Kapazitäten verpflichtet. Um die Zulässigkeit einer Buchung zu bestimmen ist es daher notwendig, die Zulässigkeit von unendlich vielen Nominierungen zu prüfen. Die Entscheidung, ob eine Buchung zulässig ist, ist daher ein anspruchsvolles mathematisches Problem, das wir in dieser Dissertation untersuchen.Unsere Ergebnisse reichen von passiven Netzen, die nur aus Rohren bestehen, bis hin zu aktiven Netzen, die steuerbare Elemente zur Beeinflussung der Gasflüsse enthalten. Da die Untersuchung aktiver Netze uns auf natürlichem Wege zu Bilevel-Problemen führt, betrachten wir zunächst einige allgemeinere Eigenschaften der Bilevel-Optimierung. Für den Fall der linearen Bilevel-Optimierung betrachten wir die Schwierigkeit, Big-Ms zu validieren, die oft bei der Lösung dieser Probleme mittels einer einstufigen Reformulierung verwendet werden. Wir leiten außerdem eine Familie gültiger Ungleichungen ab, die in einem Bilevel-spezifischen Branch-and-Cut Algorithmus als big-M-freie Alternative verwendet werden können.Wir wenden uns dann der Untersuchung von zulässigen Buchungen zu. Zunächst stellen wir unsere Ergebnisse zu passiven Netzwerken vor, für die Bilevel-Ansätze nicht erforderlich sind. Eine Charakterisierung zulässiger Buchungen in passiven Netzwerken wird in Bezug auf eine endliche Menge an Nominierungen hergeleitet. Während die Berechnung dieser Nominierungen im Allgemeinen eine schwierige Aufgabe ist, präsentieren wir polynomielle Komplexitätsergebnisse für die Spezialfälle baumförmiger oder einzyklischer passiver Netze. Schließlich betrachten wir Netze mit linear modellierten aktiven Elementen. Nachdem wir ein Bilevel-Modell hergeleitet haben, mit dem wir die Zulässigkeit einer Buchung in diesem Fall bestimmen können, leiten wir verschiedene einstufige Reformulierungen zur Lösung des Problems ab. Darüber hinaus erhalten wir neuartige Charakterisierungen zulässiger Buchungen auf aktiven Netzen, die unsere Charakterisierung im passiven Fall verallgemeinern. Die Anwendbarkeit dieser verschiedenen Ansätze wird in einer Fallstudie an zwei Netzen aus der Literatur verglichen, wovon eines eine vereinfachte Version des griechischen Gasnetzes ist. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir de bonnes performances. Il est alors intéressant de chercher à rendre plus évident, voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques, basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des recherches locales, efficaces. La neutralité est, en particulier, une caractéristique structurelle importante des paysages. De tels paysages présentent de nombreux plateaux bloquant la progression d'une recherche locale. Après une analyse fine des plateaux, nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à produire une amélioration. Une stratégie de guidage vers cette solution est alors proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques, et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes efficaces.

Dans la première partie de la thèse, nous présentons un nouveau système permettant de produire des mouvements de caméra réalistes pour l'animation stopmotion. Le système permettra d'enrichir les logiciels d'animation 3D classiques (comme par exemple Maya et 3D Studio Max) afin de leur faire contrôler des mouvements de caméra pour la stop motion, grâce à l'utilisation d'une interface haptique. Nous décrivons le fonctionnement global du système. La première étapeconsiste à récupérer et enregistrer les données envoyées par le périphérique haptique de motion capture. Dans la seconde étape, nous réélaborons ces données par un procédé mathématique, puis les exportons vers un logiciel de 3D pour prévisualiser les mouvements de la caméra. Finalement la séquence est exécutée avec un robot de contrôle de mouvement et un appareil photo. Le système est évalué par un groupe d'étudiants du Master "Art plastiques et Création numérique" de l'Université de Valenciennes. Dans la deuxième partie, nous définissons une nouvelle classe de courbes à partir des courbes polynomiales paramétriques à hodographe pythagorien (PH) construite sur un espace algébrique-trigonométrique. Nous montrons leurs propriétés fondamentaleset leurs avantages importants par rapport à leur équivalent polynomial, grâce à l'utilisation d'un paramètre de forme. Nous introduisons une formulation complexe et nous résolvons le problème d'interpolation de Hermite.

Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.

De nombreux domaines applicatifs utilisent des techniques de traitement d'images basées sur l'analyse de la topologie des images discrètes, en particulier pour des opérations devant préserver cette topologie. Si beaucoup de travaux théoriques et méthodologiques ont été menés dans le cadre des images binaires, les questions relatives à la modélisation et à la gestion simultanées des propriétés topologiques de plusieurs éléments sémantiques dans une même image discrète reste à l'heure actuelle un problème peu exploré. Dans cette thèse, nous avons porté notre attention sur la définition de déformations homotopiques compatibles avec la présence de plusieurs éléments non hiérarchisés dont les relations spatiales peuvent être significatives. Après avoir décrit le cadre théorique retenu pour les images binaires, et après avoir montré sa compatibilité avec les approches les plus fréquentes en imagerie, nous proposons des modélisations des images n-aires appuyées sur ce cadre théorique et dont les objets d'intérêts forment un sous-treillis de l'ensemble des parties de la partition initiale en régions de sémantiques distinctes. Ainsi, nous sommes en mesure de décrire quelques transformations élémentaires des images n-aires respectueuses non seulement des topologies individuelles des différents objets mais aussi des topologies "collectives" qui traduisent les inter-relations des objets.

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.

Optimisation of Performance Metrics of Embedded Hard Real-Time Systems using Software/Hardware Parallelism. Nowadays, embedded systems are part of our daily lives.Some of these systems are called safetycritical and have strong requirements in terms of safety and reliability.Additionally, these systems must have a long autonomy, good performance and minimal costs.Finally, these systems must exhibit predictable behaviour and provide their results within firm deadlines.When these different constraints are combined in the requirement specifications of a modern product, classic design techniques making use of single core platforms are not sufficient.Academic research in the field of real-time embedded systems has produced numerous techniques to exploit the capabilities of modern hardware platforms.These techniques are often based on using parallelism inherently present in modern hardware to improve the system performance while reducing the platform power dissipation.However, very few systems existing on the market are using these state-of-the-art techniques.Moreover, few of these techniques have been validated in the context of practical experiments.In this thesis, we realise the study of operating system level techniques allowing to exploit hardware parallelism through the implementation of parallel software in order to boost the performance of target applications and to reduce the overall system energy consumption while satisfying strict application timing requirements.We detail the theoretical foundations of the ideas applied in the dissertation and validate these ideas through experimental work.To this aim, we use a new Real-Time Operating System kernel written in the context of the creation of a spin-off of the Université libre de Bruxelles.Our experiments are based on the execution of applications on the operating system which run on a real-world platform for embedded systems.Our results show that, compared to traditional design techniques, using parallel and power-aware scheduling techniques in order to exploit hardware and software parallelism allows to execute embedded applications with substantial savings in terms of energy consumption.We present future and ongoing research work that exploit the capabilities of recent embedded platforms.These platforms combine multi-core processors and reconfigurable hardware logic, allowing further improvements in performance and energy consumption. / Optimisation de Métriques de Performances de Systèmes Embarqués Temps Réel Durs par utilisation du Parallélisme Logiciel et Matériel. De nos jours, les systèmes embarqués font partie intégrante de notre quotidien.Certains de ces systèmes, appelés systèmes critiques, sont soumis à de fortes contraintes de fiabilité et de robustesse.De plus, des contraintes de coûts, d’autonomie et de performances s’additionnent à la fiabilité.Enfin, ces systèmes doivent très souvent respecter des délais très stricts de façon prédictible.Lorsque ces différentes contraintes sont combinées dans le cahier de charge d’un produit, les techniques classiques de conception consistant à utiliser un seul cœur d’un processeur ne suffisent plus.La recherche académique dans le domaine des systèmes embarqués temps réel a produit de nombreuses techniques pour exploiter les plate-formes modernes.Ces techniques sont souvent basées sur l’exploitation du parallélisme inhérent au matériel pour améliorer les performances du système et la puissance dissipée par la plate-forme.Cependant, peu de systèmes existant sur le marché exploitent ces techniques de la littérature et peu de ces techniques ont été validées dans le cadre d’expériences pratiques.Dans cette thèse, nous réalisons l’étude des techniques, au niveau du système d’exploitation, permettant l’exploitation du parallélisme matériel par l’implémentation de logiciels parallèles afin de maximiser les performances et réduire l’impact sur l’énergie consommée tout en satisfaisant les contraintes temporelles strictes du cahier de charge applicatif. Nous détaillons les fondements théoriques des idées qui sont appliquées dans la dissertation et nous les validons par des travaux expérimentaux.A ces fins, nous utilisons le nouveau noyau d’un système d’exploitation écrit dans le cadre de la création d’une spin-off de l’Université libre de Bruxelles.Nos expériences, basées sur l’exécution d’applications sur le système d’exploitation qui s’exécute lui-même sur une plate-forme embarquée réelle, montre que l’utilisation de techniques d’ordonnancement exploitant le parallélisme matériel et logiciel permet de larges économies d’énergie consommée lors de l’exécution d’applications embarquées.De futurs travaux en cours de réalisation sont présentés.Ceux-ci exploitent des plate-formes innovantes qui combinent processeurs multi-cœurs et matériel reconfigurable, permettant d’aller encore plus loin dans l’amélioration des performances et les gains énergétiques. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cryptography is the foundation of modern IT security,it provides algorithms and protocols that can be usedfor secure communications. Cryptographic algorithmsensure properties such as confidentiality and data integrity.Confidentiality can be ensured using encryption algorithms.Encryption algorithms require a secret information called a key.These algorithms are implemented in cryptographic devices.There exist many types of attacks against such cryptosystems,the main goal of these attacks is the extraction of the secret key.Side-channel attacks are among the strongest types of attacksagainst cryptosystems. Side-channel attacks focus on the attacked device, they measure its physicalproperties in order to extract the secret key. Thus, these attacks targetweaknesses in an implementation of an algorithm rather than the abstract algorithm itself.Power analysis is a type of side-channel attacks that can be used to extract a secretkey from a cryptosystem through the analysis of its power consumption whilethe target device executes an encryption algorithm. We can say that the secret information is leaking from the device through itspower consumption. One of the biggest challenges in the domain of side-channel analysisis the evaluation of a device from the perspective of side-channel attacksor in other words the detection of information leakage.A device can be subject to several sources of information leakageand it is actually relatively easy to find just one side-channel attack that works(by exploiting just one source of leakage),however it is very difficult to find all sources of information leakage or to show that there is no information leakage in the givenimplementation of an encryption algorithm. Evaluators use various statistical tests during the analysis of a cryptographic device to checkthat it does not leak the secret key. However, in order to performsuch tests the evaluation lab needs the device to acquire the measurementsand analyse them. Unfortunately, the development process of cryptographicsystems is rather long and has to go through several stages. Thus, an information leakagethat can lead to a side-channel attackcan be discovered by an evaluation lab at the very last stage using the finalproduct. In such case, the whole process has to be restarted in order to fix the issue,this can lead to significant time and budget overheads. The rationale is that developers of cryptographic systems would like to be able to detect issues related to side-channel analysis during the development of the system,preferably on the early stages of its development. However, it is far from beinga trivial task because the end product is not yet available andthe nature of side-channel attacks is such that it exploits the properties ofthe final version of the cryptographic device that is actually available to the end user. The goal of this work is to show how simulators can be used for the detection of issues related to side-channel analysis during the development of cryptosystems.This work lists the advantages of simulators compared to physical experimentsand suggests a classification of simulators for side-channel analysis.This work presents existing simulators that were created for side-channel analysis,more specifically we show that there is a lack of available simulation toolsand that therefore simulators are rarely used in the domain. We present threenew open-source simulators called Silk, Ascold and Savrasca.These simulators are working at different levels of abstraction,they can be used by developers to perform side-channel analysisof the device during different stages of development of a cryptosystem.We show how Silk can be used during the preliminary analysisand development of cryptographic algorithms using simulations based on high level of abstraction source code. We used it to compare S-boxesas well as to compare shuffling countermeasures against side-channel analysis.Then, we present the tool called Ascold that can be used to find side-channel leakagein implementations with masking countermeasure using the analysis of assembly code of the encryption.Finally, we demonstrate how our simulator called Savrasca can be used to find side-channelleakage using simulations based on compiled executable binaries. We use Savrascato analyse masked implementation of a well-known contest on side-channel analysis (the 4th edition of DPA Contest),as a result we demonstrate that the analysed implementation contains a previouslyundiscovered information leakage. Through this work we alsocompared results of our simulated experiments with real experiments comingfrom implementations on microcontrollers and showed that issues found using our simulatorsare also present in the final product. Overall, this work emphasises that simulatorsare very useful for the detection of side-channel leakages in early stages of developmentof cryptographic systems. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse porte principalement sur l'équilibrage de charge dans de grands graphes aléatoires. En informatique, un problème d'équilibrage de charge survient lorsque différentes tâches ont besoin d'accéder à un même ensemble de points de ressources. Il faut alors décider quelles ressources spécifiques seront allouées à quelles tâches. Suivant le contexte, les notions de "tâche" et de "ressource" peuvent avoir différentes interprétations. Afin de prendre des exemples concrets, on se concentrera sur deux applications en particulier: - un système de hachage à choix multiples (plus précisément, le "cuckoo hashing"). L'objectif est ici d'allouer des cellules d'un tableau à des objets, afin de pouvoir ensuite vérifier facilement la présence d'un objet et récupérer les données associées. Les tâches sont liées aux objets à stocker, et les ressources sont les cellules du tableau. - un réseau de distribution de contenu distribué, au sens où les contenus peuvent être stockés sur une multitude de petits serveurs aux capacités individuelles très limitées. Ici, les tâches sont des demandes de téléchargement (ou requêtes) pour un contenu et les ressources sont liées aux serveurs et à la façon dont leurs espaces de stockage sont utilisés. Le problème d'équilibrage de charge consiste à décider quel serveur va servir quelle requête. Les contraintes locales portant sur chaque ressource (en quelle quantité est-elle disponible et pour quelles tâches est-elle convenable?) ainsi que la charge de travail associée avec chaque tâche peuvent être représentées efficacement sur un graphe biparti, avec des contraintes de capacité sur ses sommets et ses arêtes. De plus, en pratique, les systèmes considérés sont souvent de très grande taille (avec parfois des milliers de tâches et de points de ressources différents) et relativement aléatoires (que ce soit par choix ou une conséquence de leur grande taille). Une modélisation à l'aide de grands graphes aléatoires est donc souvent pertinente. L'ensemble des solutions envisageables pour un problème d'équilibrage de charge donné étant vaste, il est primordial de commencer par déterminer des bornes sur les performances que l'on peut espérer. Ainsi, on considérera dans un premier temps une solution optimale du problème (même si elle ne serait pas réalisable avec des contraintes pratiques). Les performances d'une telle solution peuvent être obtenues en étudiant les appariements de taille maximum dans un grand graphe aléatoire, ce que l'on réalisera à l'aide de la méthode de la cavité. Cette méthode vient de l'étude des systèmes désordonnés en physique statistique, et on s'attachera ici à l'appliquer de manière rigoureuse dans le cadre que l'on considère. Dans le contexte du cuckoo hashing, les résultats obtenus permettent de calculer le seuil sur la charge du système (le nombre d'objets à insérer par rapport à la taille du tableau) en-dessous duquel on peut construire une table de hachage correcte avec grande probabilité dans un grand système, et également de traiter de manière similaire de variantes de la méthode de hachage basique qui tentent de diminuer la quantité d'aléa nécessaire au système. Au-delà du problème d'équilibrage de charge, dans le cadre des réseaux de distributions de contenu distribués, un second problème se pose: comment décider quel contenu stocker et en quelle quantité, autrement dit comment répliquer les contenus? On appelle ce second problème un problème d'allocation de ressources. A nouveau, l'étude déjà réalisée permet de quantifier l'efficacité d'une politique de réplication fixée en supposant que la politique d'équilibrage de charge fonctionne de manière optimale. Il reste cependant à optimiser la politique de réplication de contenus utilisée, ce que l'on effectue dans un régime où l'espace de stockage disponible au niveau de chaque serveur est important par rapport à la taille d'un contenu. Finalement, afin de quantifier maintenant les performances minimales atteignables en pratique, on s'intéressera aux mêmes questions lorsque la politique d'équilibrage de charge utilisée est un simple algorithme glouton. Cette étude est réalisée à l'aide d'approximations de champs moyen. On utilisera également les résultats obtenus afin de concevoir des politiques de réplication de contenus adaptatives.