Nous vivons au temps des algorithmes, ces outils ne décident rien mais fournissent des réponses statistiquement significatives, au point de provoquer un dilemme au moment de prendre une décision, quand notre conviction intime rentre en contradiction avec ce que le résultat de l’algorithme propose. Et un domaine où cela devient critique est celui de la justice. Voyons comment dépasser ce dilemme avec Serge Abiteboul. Thierry Viéville.
Les algorithmes exécutés par des ordinateurs sont entrés dans nos vies : ils nous conseillent des films, nous proposent des chemins pour nous rendre à notre prochain rendez-vous… Bientôt, ils conduiront nos voitures ou nous permettront de rester chez nous dans notre quatrième âge. En prenant autant d’importance, ils soulèvent des questionnements, des inquiétudes. Prenons un exemple frappant dans un domaine régalien, la justice. Aux États-Unis, le logiciel Compas assiste les juges pour décider de libérations conditionnelles, en évaluant le risque de possibles récidives – la décision de remise en liberté est strictement liée à la probabilité de récidive. L’algorithme assiste, mais ne décide pas. Oui, mais un juge aura-t-il le courage, ou la légèreté, de remettre un condamné en liberté contre l’avis du logiciel si l’on peut prouver que l’algorithme fait statistiquement de meilleures prédictions que les juges ?
La questionest philosophique : y a-t-il des tâches de telles natures que les confier à des machines nous ferait perdre une part de notre humanité, des tâches qu’il faut leur interdire même si elles les réalisent mieux que nous ? Nous ne répondrons pas à cette question, mais relativisons son importance aujourd’hui. Si les algorithmes deviennent de plus en plus intelligents, ils sont loin de pouvoir, par exemple, remplacer les juges dans des cas encore plus complexes que celui de la libération conditionnelle aux États-Unis. Quand des algorithmes participent à la vie de la cité se pose également la question de leur responsabilité. Revenons sur le logiciel Compas. Il présente sur un juge l’avantage d’une certaine cohérence. Il a été montré notamment que les décisions des juges sont dépendantes de l’heure ; il vaut mieux passer après le repas qu’avant. Et celles des cours de justice, par exemple aux prud’hommes, varient énormément d’une chambre à une autre. Pas de cela avec les algorithmes ! Ils peuvent garantir une certaine cohérence.
Nous pourrions également espérer qu’ils soient plus « justes », qu’ils ne discriminent pas suivant les origines ethniques, le genre… Pourtant, des journalistes ont évalué les prédictions de Compas et découvert qu’il surestimait largement les risques de récidives des condamnés noirs. Des informaticiens racistes ? Pas vraiment, mais on ne sait pas écrire un algorithme qui prédise les récidives – la question est trop complexe. Alors on utilise un algorithme d’apprentissage automatique. On lui apprend le travail à réaliser en l’entraînant sur un grand volume de données de décisions de juges, à imiter des humains. Ce sont ces décisions, qui présentaient des biais raciaux, que Compas a reproduites. Il faut avoir conscience des problèmes que l’utilisation de programmes informatiques peut soulever, vérifier ces programmes et les données qui sont utilisées pour les « entraîner », surveiller leurs résultats.
Notre exemplenous a permis d’insister sur un aspect essentiel de la responsabilité : l’absence de biais, l’équité. La transparence en est un autre. Nous pouvons, par exemple, nous inquiéter de ce que Facebook fait de nos données personnelles dans une relative opacité. Nous pourrions aussi parler de la loyauté : faut-il accepter un service qui propose des restaurants en disant ne tenir compte que des avis de consommateurs et qui remonte en réalité dans sa liste de résultats les commerçants qui paient pour ça ? La responsabilité sociétale des algorithmes a nombre de facettes.
Les algorithmes peuvent nous permettre d’améliorer nos vies. Il faut corriger leurs défauts, combattre leurs biais inacceptables. Il peut s’avérer difficile de vérifier, d’expliquer leurs choix, s’ils proviennent de statistiques mettant en jeu des milliards d’opérations ou s’ils se basent sur des motifs complexes découverts par des algorithmes d’apprentissage. Pourtant, notre incompétence ne peut pas servir de justification pour autoriser le viol de principes moraux. Quand les effets des décisions sont sérieux, comme garder une personne incarcérée, sans doute vaut-il mieux attendre d’être certain du fonctionnement de l’algorithme, exiger qu’il explique ses choix et, bien sûr, faut-il pouvoir les contester.
En 2013, le blog Intelligence mécanique voyait le jour sous l’impulsion de Thierry Viéville ! Grâce à lui, plusieurs d’entre vous, en savent plus sur le monde de l’informatique.
A l’époque l’objectif de ce blog était le suivant : parler de l’intelligence des machines, celle de l’informatique et surtout co-construire ensemble une culture scientifique liée à la science informatique pour maîtriser ce monde numérique qui nous entoure sans le subir ni se limiter à le consommer.
Ikram Chraibi Kaadoud
Ikram Chraibi Kaadoud a récemment repris le flambeau : même objectif qu’en 2013, avec toutefois une variante, plus de sciences cognitives !
Chaque article débute par une indication pour expliciter le niveau de complexité qui sera abordé dans l’article mais toujours dans un esprit de médiation :
Tout public, lycéen·ne·s : l’article contiendra peu ou pas de référence mathématique au delà du niveau de début de lycée, il servira de ressources aux lycéen·ne·s sur ces sujets
Public familial : l’article aura vocation à expliquer un concept, répondre à une question informatique d’un point de vue sociétal, sans pour autant imposer d’éléments techniques
Public averti : l’article contiendra des références en sciences informatiques et mathématiques et des notions plus techniques pourront être abordées, avec toujours les liens Wikipédia idoines
A l’occasion de la parution d’un livre blanc sur la cybersécurité réalisé au sein d’Inria, nous nous sommes interrogés sur un concept peu connu des non initiés : les réseaux zéro-confiance (zero-trust networks). J.J. Quisquater (Université de Louvain), Ch. Cuvelliez et J.M. Dricot (Université de Bruxelles) nous expliquent de quoi il s’agit et surtout nous aident à prendre conscience des risques induits par d’autres types d’architectures réseau. Pascal Guitton
Avez-vous déjà remarqué combien le scénario d’une attaque informatique est d’une triste monotonie ? Lors de la visite d’un site infecté ou parce qu’il a cliqué sur un lien malveillant, un utilisateur reçoit gracieusement sur son ordinateur un petit bout de logiciel qui va établir un lien avec le monde extérieur, jusqu’au hacker. Le trafic qu’envoie ce logiciel (et celui qu’il reçoit) est chiffré et déguisé en trafic web normal. Et avec l’idée tenace qu’il ne faut se protéger que de l’extérieur, on ne se méfiera pas du trafic qui a l’air légitime et qui part vers Internet. Depuis cet ordinateur infecté qui est devenu le patient zéro, le hacker compte bien sur le fait qu’il peut sûrement parler avec d’autres machines dans le réseau privé virtuel (VPN) [1] au sein duquel il s’est installé. Avec un peu de chance, cette machine a même eu l’autorisation par le passé de communiquer avec des machines dans un autre VPN, plus critique. De proche en proche, le hacker étend son empreinte jusqu’à trouver la machine qui l’intéresse. L’exfiltration de données de cette machine (et donc de l’entreprise à laquelle elles appartiennent), qui fera bientôt la une des journaux, commence.
Businessman with network security technology. Image de Suphakit73 via Shutterstock
Quand on réfléchit aux raisons profondes du succès d’un tel scénario, on arrive toujours à la même explication : les réseaux des entreprises ont beau être segmentés en VPN, au sein d’une même zone et d’un même VPN, les machines se font confiance et ne savent donc pas si l’une d’entre elles est devenue une brebis galeuse. Ce n’est qu’aux frontières des VPN qu’un peu de méfiance s’installe via des pare-feux et encore, uniquement sur base d’un contrôle sommaire de quelle machine (adresse d’origine) envoie du trafic à quelle machine (adresse de destination). C’est oublier que sur son réseau, il y a les utilisateurs, les employés, les systèmes internes (la gestion des salaires, le système d’inventaire), les serveurs web. Vous avez sans doute codifié correctement qui peut accéder à quoi : les employés n’ont besoin d’avoir accès qu’aux systèmes internes, les serveurs web ont besoin d’avoir accès à des bases de données qui contiennent les données à afficher ; tout cela est bien segmenté. Mais il y a les exceptions dans le pare-feu (firewall) qui permettent aux employés d’avoir accès à Internet ou à des serveurs sur un autre site ou, encore, qui permettent à votre web developer d’avoir accès aux serveurs web en production dans la zone démilitarisée… Tout cela se fait en franchissant allègrement les frontières des VPN. Et puis, tous ces employés utilisent peut-être un système de partage de fichiers mais tous n’ont pas mis à jour le logiciel en question. Certains sont vulnérables à une attaque récemment rendue publique. Le hacker en profite et peut progresser ainsi d’une machine à l’autre. Tant que les réseaux fonctionneront ainsi, les attaques classiques auront de beaux jours devant elles.
Internet, le premier réseau zéro-confiance
Il est pourtant un autre réseau avec lequel on interagit tous les jours et où on ne fait confiance à rien, ni à personne : Internet. L’idée des réseaux zéro-confiance est alors simple : appliquons cette méfiance, aussi à l’intérieur de son propre réseau. Un réseau zéro-confiance est considéré comme toujours et tout le temps hostile : il contient en permanence des menaces qui viennent de l’intérieur et de l’extérieur. La méfiance est portée à l’extrême : l’utilisateur, l’appareil qu’il utilise et le trafic réseau qu’il génère doivent toujours être authentifiés. Mieux : les politiques de sécurité doivent être évolutives en fonction du comportement de l’usager selon qu’il travaille d’un web café ou du bureau.
Les réseaux traditionnels sont au contraire partitionnés en zones (VPN) qui contiennent un ou plusieurs pare-feu(x). Ces zones reçoivent un certain degré de confiance qui leur octroie des privilèges et donc, le niveau de ressources auquel on a accès. Dans un réseau zéro-confiance, les machines ne doivent pas seulement être protégées de l’extérieur, elles doivent être protégées l’une de l’autre dans le réseau et prouver en permanence qui elles sont. L’authentification dans les réseaux zéro-défaut est triple : la machine doit être authentifiée, prouver qui elle est, l’utilisateur et l’application (car certaines applications fonctionnent de manière autonome) doivent aussi prouver qui ils sont et le trafic doit être tenu confidentiel, donc chiffré.
Le protocole IEEE 802.1X se rapproche un peu de ce modèle car il authentifie d’abord la machine qui se connecte au réseau avant d’authentifier l’utilisateur qui est dessus. À la place d’une organisation en VPN, la sécurité d’un réseau zéro-confiance obéit à un modèle en deux couches : la couche donnée (data plane) et la couche contrôle (control plane). Le control plane joue le rôle de chef d’orchestre. Un degré de confiance (trust score) est en permanence calculé pour chaque ressource du réseau, une machine, une application, un utilisateur. Ce degré de confiance permet alors au control plane de donner, dynamiquement ou non, accès au réseau aux ressources qui le demandent.
Au final, au sein d’un réseau zéro-confiance, les entités se parlent de manière chiffrée, uniquement compréhensible entre elles, entités qui se sont authentifiées avant de commencer leur discussion. Les flux de trafic sont sûrs, les origines et destination le sont tout autant. Leurs identités sont prouvées cryptographiquement par un système de certificat (web of trust ou CA), exactement comme quand on accède à des sites web https. Tout ceci demande une automatisation poussée pour que ces mécanismes complexes soient transparents pour l’utilisateur final. La promesse des réseaux zéro-confiance, c’est de mettre fin à l’idée que plus de sécurité sur le réseau se fait toujours au détriment de la commodité de l’utilisation. Les réseaux zéro-confiance sont aussi rendus possibles par la capacité de calcul que tous les appareils ont acquise, du plus petit au plus grand. Avec l’avènement des clouds, qui n’est rien d’autre qu’un réseau public, c’est plus que jamais la logique des réseaux zéro-confiance qu’on devrait leur appliquer. Pourtant, aujourd’hui, on essaie de prolonger la logique des VPN et autre types de gestions d’accès de son propre réseau à celle d’un AWS [2] ou d’Azure. L’épisode Snowden nous a montré qu’on ne peut pas faire totalement confiance à une infrastructure dont on ne maîtrise pas l’implantation. D’ailleurs, même au sein de votre propre data center, vous devriez chiffrer le trafic !
Les VPN, une voie de contamination souvent oubliée
Mais d’où viennent les VPN et leur logique qui semble être à l’origine de beaucoup de maux ? Pas d’un modèle de sécurité mûrement réfléchi mais de la manière dont les réseaux d’entreprise se sont petit à petit connectés à Internet. Ce fut d’abord le serveur mail : les mails furent le premier service Internet que voulurent les entreprises pour leurs employés. Ensuite vint le site web (élémentaire) qui assurait une présence de la société sur Internet. On isola bien vite les serveurs web et email entre le réseau interne de l’entreprise et Internet. La zone dite démilitarisée (DMZ) isolée par des pare-feux, pour éviter qu’une intrusion réussie n’aille plus loin, était née. Après, il fut question d’octroyer un accès internet à tous les employés mais sans leur donner pour cela une vraie adresse IP, ce qu’on faisait aux premières heures du Net. Le concept de traduction d’adresse réseau (NAT), et donc de VPN, à l’intérieur même du réseau d’entreprise s’en est suivi, le pare-feu cumulant bien son rôle avec celui de serveur NAT.
Images extraites du site de la société Cisco
La mobilité des employés entre le bureau et la maison fut une autre épine pour la sécurité de l’entreprise : la solution de facilité consistait à connecter le portable ramené chez soi en le rattachant au réseau de l’entreprise. Ainsi, pensait-on, il devenait (virtuellement) un ordinateur du lieu de travail et bénéficiait des mêmes niveaux de sécurité. La connexion internet généralisée est ensuite arrivée. Ce même PC (qui devenait le PC familial) fut donc alors connecté à la fois au réseau d’entreprise et à l’Internet. Il devient donc ainsi une passerelle entre un monde sans sécurité (l’internet) et le cœur même du réseau de l’entreprise, évitant ainsi tous les niveaux de sécurité mis en place à l’entrée de celle-ci.
En guise de conclusion
Les réseaux zéro-confiance, un concept plus qu’une technologie, veulent remettre tout cela à plat. Ils vont plus loin que de réduire des VPN à des réseaux mono-machine.
D’une certaine manière, les réseaux zéro-confiance portent mal leur nom : ils continuent bien à faire confiance à l’utilisateur, plus que jamais même, car une fois la confiance accordée, il l’accompagne pour lui donner accès aux ressources qu’il demande en garantissant sa sécurité sans affecter sa facilité d’usage…
J.J. Quisquater (Université de Louvain), Ch. Cuvelliez et J.M. Dricot (Université de Bruxelles)
[1] Dans le contexte d’une entreprise, on appelle VPN un sous-réseau logique (sans connexions physiques dédiées) dans le réseau global de l’entreprise au sein duquel les machines sont connectées directement les unes aux autres. Ce sous-réseau coïncide souvent avec une équipe, un département, un étage, une fonction, un site même parfois. Ce VPN est isolé, protégé des autres VPN. Au sein d’un VPN, les machines ne sont pas censées ne pas avoir confiance les unes envers les autres. Ensemble, ces VPN forment le réseau de l’organisation. Si les VPN sont limités et confinés à l’intérieur du réseau local (Local Area Network ou LAN) de l’entreprise, on les dénomme VLAN (Virtual LAN). Si le réseau de l’entreprise utilise Internet comme infrastructure pour se construire, le terme VPN est alors utilisé. Un VPN peut interconnecter des VLAN entre sites par exemple. L’accès au réseau de l’entreprise depuis l’extérieur (extranet, accès des employés) est aussi appelé VPN..
[2] AWS : Amazon Web Service, l’offre cloud de Amazon
Olivier Bournez, François Fages, Guillaume Le Guludec et Amaury Pouly ont reçu, pour l’article [1], le Prix La Recherche 2019, option Sciences de l’information. « Les informaticiens ont montré que les réactions chimiques, telles celles qui se produisent dans une cellule, peuvent simuler une machine de Turing. Autrement dit, les réactions chimiques sont des ordinateurs universels. Les informaticiens ont aussi mis au point un compilateur permettant de transformer n’importe quelle fonction mathématique en réactions chimiques élémentaires. » Bravo ! C’est tout sauf simple. Qui mieux qu’Olivier pour expliquer à Binaire qu’il n’est pas nécessaire de calculer en binaire pour réaliser des calculs ? Laure Thiébault, Serge Abiteboul
Les ordinateurs actuels fonctionnent dans une logique binaire, c’est-à-dire basée sur de la logique digitale sur des 0 et des 1, et avec un temps discret : une horloge, dont la fréquence est souvent exprimée en giga hertz. Cette horloge séquence les instructions une à une, et les valeurs 0 et 1 correspondent par exemple à +5 ou -5 volts.
Dans le but de construire des modèles alternatifs aux ordinateurs actuels, il est possible de considérer des modèles qui travaillent dans une logique continue : on utilise par exemple des tensions qui peuvent prendre des valeurs réelles, qui ne sont pas seulement binaires. Les composants électroniques ont par défaut un comportement continu.
Les modèles de l’intelligence artificielle comme ceux de l’apprentissage profond (deep learning) sont de ce type, car ils travaillent sur des quantités continues. Pour réaliser physiquement ces algorithmes, on le fait souvent avec des ordinateurs digitaux, mais on peut aussi le faire avec de l’électronique analogique. Il n’y a a priori pas besoin pour réaliser ces calculs de les rendre discrets alors qu’ils sont intrinsèquement continus.
Mais de tels modèles restent à temps discret, avec une horloge. On peut aussi considérer des modèles analogiques où à la fois la logique et le temps sont continus.
En fait, les tous premiers ordinateurs étaient de ce type. Par exemple les analyseurs différentiels construits dans les années 1930 au MIT étaient des machines purement mécaniques qui codaient les quantités par des angles, et qui réalisaient des opérations sur celles-ci comme des additions, multiplication, intégration à l’aide d’engrenages et de dispositifs mécaniques ingénieux. Claude Shannon, qui a été opérateur sur ces machines pour payer ses études, a proposé dans les années 1940 un modèle mathématique, appelé « General Purpose Analog Computer (GPAC) » de ces machines. Il a montré que ce qui était programmable sur ces machines correspond à ce qui peut s’écrire par un type d’équations (les équations différentielles ordinaires vectorielles dont le membre droit est polynomial).
En 2019, réaliser avec de l’électronique analogique un GPAC est facile, et certaines sociétés comme Analog Paradigm vendent des composants ou des ordinateurs analogiques basés sur le modèle de Shannon. Les amateurs de musique analogique connaissent aussi de nombreux vendeurs de composants qui permettent d’effectuer des traitements sur des signaux qui permettent de construire soi-même une telle machine si on le souhaite.
Jusqu’en 2007, on pensait ces machines moins puissantes que les ordinateurs digitaux actuels. En fait, il n’en est rien : tout ce qui peut se calculer avec une machine de Turing, c’est-à-dire le modèle mathématique actuel de l’informatique digitale moderne, peut se programmer avec une machine analogique à temps continu. On code pour cela le calcul dans des quantités continues et on laisse la machine évoluer pour produire le résultat.
L’ordinateur « Analog Paradigm Model 1 »
Ce qui est encore plus surprenant, c’est que lorsqu’on programme des fonctions sur des machines (comme celle ci-contre), il suffit de tourner certains potentiomètres pour accélérer les calculs : il est en fait possible de calculer les fonctions aussi vite que l’on souhaite, et donc beaucoup plus vite qu’avec les ordinateurs actuels (au moins si l’on reste sur le modèle mathématique réalisé par la machine).
Depuis 2017, on sait expliquer quelle est la puissance de ces machines : il faut en réalité mesurer le temps de calcul par la longueur de la solution des équations différentielles. La question de savoir si l’on peut calculer plus vite revient ainsi à discuter la longueur des solutions d’une équation différentielle. Ce résultat est surprenant et inattendu, car il relie un concept purement mathématique à un concept informatique : le temps de calcul. Il permet par ailleurs de poser des questions philosophiques très profondes sur certaines notions comme le temps, sur ce que l’on peut prouver avec des modèles mathématiques ou de la physique ou sur ce que l’on peut modéliser par des équations différentielles.
Mais est-il vraiment raisonnable et intéressant de revenir à des machines analogiques ? Une des raisons de l’abandon de ces machines a été historiquement le fait qu’il semblait que la logique analogique ne passait pas aussi bien à l’échelle que la logique digitale.
Le prix du magazine « La Recherche » 2019 pour la mention « sciences de l’information » a été attribué à une publication qui démontre que l’on peut réaliser ces machines par des réactions biochimiques : les quantités continues sont codées par des concentrations de protéines, qui interagissent par des réactions biochimiques bien choisies. En faisant ainsi, on peut programmer ces protéines pour effectuer tout calcul faisable par une machine de Turing, c’est-à-dire par un ordinateur digital actuel.
Cela ouvre la voie à la réalisation d’ordinateurs alternatifs, et résoudre ce problème du passage à l’échelle, mais aussi à d’autres questions encore plus fascinantes : la nature a, via l’évolution, conçu certains mécanismes cinétiques pour réaliser (c’est-à-dire calculer) certaines opérations, comme par exemple le maximum de certaines quantités. Pourrait-on les réaliser d’une façon alternative plus efficace ? Les solutions proposées par l’évolution sont-elles les meilleures ? Peut-on concevoir de programmer la biologie d’une façon encore plus efficace ?
Olivier Bournez, Professeur d’Informatique de l’Ecole polytechnique
Peut-être rêvez vous de voyage mais vous ne disposez pas de beaucoup de jours de congés pour faire le tour de l’Europe ? Si vous trouvez une solution optimale pour faire le tour, vous pouvez même payer vos vacances avec le million de dollars de récompense. Dans le cadre de la rubrique « Il était une fois… ma thèse », Binaire a demandé à Fabian Reiter, qui a travaillé au laboratoire IRIF/Université de Paris Diderotoù il a réalisé une thèse intitulée “Distributed Automata and Logic ». Il est lauréat d’un accessit au prix SIF Gilles Kahn pour ses travaux. Tamara Rezk
Nous sommes en avril 1889 à Paris. La Tour Eiffel vient d’être inaugurée, et les derniers préparatifs sont en cours pour l’Exposition universelle qui se tiendra de mai à octobre. Bientôt, le monde entier tournera son regard vers Paris.
Pour Edmond Gaudelin, c’est le moment idéal pour organiser une petite tournée à travers l’Europe. Son objectif est simple : dans chaque capitale, il souhaite vendre en grandes quantités des fausses cartes d’abonnement permettant de visiter l’exposition à volonté. Alors que le prix officiel est fixé à 100 francs par personne, il vendra ses contrefaçons pour 25 francs. Une fois qu’il aura parcouru toutes les autres villes, il compte retourner à Paris pour aussi voler quelques-unes des médailles d’or qui seront décernées lors de l’exposition. Puis, si tout se déroule comme prévu, il s’enfuira au Chili, où il sera accueilli par son ancien compagnon de cellule Faustino Carelosánchez.
Évidemment, Gaudelin veut agir rapidement pour ne pas être identifié par la police avant de se retrouver en relative sécurité au Chili. Penché sur une carte de l’Europe, il se rend compte que son itinéraire doit satisfaire deux critères principaux : d’une part, minimiser la durée totale du voyage, et d’autre part, ne visiter chaque ville qu’une seule fois, afin d’éviter d’être facilement reconnu.
CC-BY-SA-3.0,2.5,2.0,1.0
Une manière de procéder serait de planifier tout le voyage à l’avance sur papier. Mais Gaudelin n’est pas très familier avec le réseau ferroviaire international, et surtout, il n’a pas le temps d’essayer toutes les permutations des villes; pour la vingtaine de capitales européennes qui existent en 1889, il y a plus de deux trillions de possibilités de les ordonner. Au lieu de cela, Gaudelin décide de répartir le problème entre ses complices, qui sont disséminés dans toute l’Europe. Chacun d’entre eux connaît bien une partie du réseau et peut envoyer des télégrammes à ses voisins les plus proches. Ainsi, dans chaque ville, le complice local pourra indiquer à Gaudelin la prochaine ville à visiter. Étant donné que personne n’a une vue d’ensemble, le parcours résultant ne sera pas nécessairement optimal. Néanmoins, le but de Gaudelin est de trouver une méthode qui puisse être assez facilement appliquée par tous ses complices et qui permette d’obtenir une bonne approximation d’un parcours idéal.
De nos jours, le problème de Gaudelin (un personnage purement fictif) est généralement appelé le « problème du voyageur de commerce ». Il s’agit d’un exemple de « problème de graphe », ou autrement dit, d’un objectif que l’on aimerait atteindre par rapport à une structure de réseau donnée. Il n’est pas important que ce soit un réseau ferroviaire, un réseau informatique, ou une structure plus abstraite. Dans le cadre de ma thèse, je me suis intéressé au défi de résoudre ce genre de problèmes de manière distribuée, c’est-à-dire de la même manière que Gaudelin et ses complices. Plus précisément, à partir d’une description formelle d’un problème tel que « passer exactement une fois par chaque capitale en minimisant la durée du voyage », le but ultime de ma recherche est de générer automatiquement un « algorithme distribué » permettant de résoudre le problème. Dans le cas de Gaudelin, l’algorithme distribué ne serait rien d’autre que la méthode suivie par les complices. Dans le cas d’un réseau informatique, cela correspond à un programme exécuté par chaque ordinateur du réseau. De façon plus générale, on peut dire qu’un algorithme distribué détermine le comportement de chaque participant dans un groupe qui doit résoudre un problème commun. Et bien souvent, il est beaucoup plus facile de décrire le problème que d’expliquer à chacun ce qu’il doit faire.
Maintenant, vous vous demandez peut-être si, en 2019, le problème de Gaudelin est résolu. Malheureusement, la réponse est non, ou du moins pas de manière satisfaisante. En effet, il s’agit d’un problème très difficile en informatique théorique. Depuis plus d’un demi-siècle, de nombreux chercheurs ont essayé de démontrer qu’il est même mathématiquement impossible de trouver efficacement une solution optimale, mais jusqu’à présent, personne n’a réussi. (Si vous y parvenez, l’Institut de mathématiques Clay vous offrira un million de dollars.) En plus, quand on s’attaque au problème de manière distribuée, cela introduit encore une source de difficulté supplémentaire. Alors, où en sommes-nous actuellement? Principalement, on se penche sur des questions connexes, mais plus faciles à aborder. Pour ma part, j’ai considéré des algorithmes distribués dans
lesquels chaque participant est représenté par un « automate fini », c’est-à-dire une petite machine qui dispose seulement d’une mémoire bornée et dont les capacités de communication sont très restreintes. J’ai obtenu plusieurs résultats théoriques indiquant que de tels automates peuvent, en principe, être générés automatiquement à partir de « formules logiques » décrivant certains types de problèmes. Bien que les automates obtenus soient beaucoup trop faibles pour résoudre des problèmes aussi difficiles que celui de Gaudelin, j’espère que ce genre de résultats nous aideront à mieux comprendre ce qui est possible dans le calcul distribué, et quels sont les coûts en termes de ressources informatiques.
Il était une fois… la thèse de Pierre Laperdrix, lauréat d’un accessit au prix SIF Gilles Kahn et du prix Cnil/Inria. Pierre a travaillé pendant sa thèse sur la protection de la vie privée au laboratoire IRISA/Inria Rennes Bretagne-Atlantique. Il nous explique que les navigateurs laissent des … empreintes ! Si vous voulez savoir comment cela est lié à votre vie privée, je vous invite à lire. Tamara Rezk
Pierre Laperdrix, Crédit photo Cyril Gabbero
Avez-vous déjà joué à « Qui est-ce ? », ce jeu de société où il faut identifier un personnage mystère en posant toute une série de questions ? « Est-ce que ton personnage a les cheveux bruns ? » « Est-ce que ton personnage porte une moustache ? »
En se basant sur un ensemble d’attributs très précis, le joueur est à même de retrouver le personnage choisi par son adversaire et de gagner la partie. Sur Internet, il existe une technique qui n’est pas sans rappeler le principe de ce jeu : le traçage par empreintes de navigateur. On substitue alors les attributs physiques recherchés par la composition et la configuration d’un appareil connecté sur Internet : « Quel est ton navigateur ? » « Quel est ton système d’exploitation ? » « Quelle est la taille de ton écran ? » « Quelle est la langue de ton navigateur ? »
Ce sont ici quelques exemples d’attributs techniques qui peuvent être récoltés via n’importe quel script sur Internet. En combinant ces informations, on définit ce que l’on appelle une empreinte de navigateur. Cette technique est particulièrement dangereuse, car il existe une telle diversité d’appareils connectés sur le web qu’il est possible d’identifier un utilisateur de façon unique et de repérer les pages qu’il visite.
Diversité de l’Internet moderne (image Pierre Paperdrix)
Pendant ma thèse, mon objectif était de comprendre ce phénomène d’empreintes de navigateurs, ou browser fingerprinting en anglais, et de développer des systèmes de défense appropriés. Que peut-on récolter ? Quels sont les mécanismes qui influencent les valeurs récoltées ? Comment peut-on s’en protéger ? Pour répondre à ces questions, j’ai lancé le site AmIUnique.org (« Suis-je unique » en français).
Vous voulez connaître votre empreinte ? Rendez-vous sur AmIUnique.org !
Plus de 4 ans après son lancement, le site recense plus de mille connexions par jour, et près d’un million d’utilisateurs sont déjà venus consulter leur empreinte de navigateur et vérifier ainsi si elle était unique ou non. Si vous n’avez pas encore fait le test, rendez-vous vite sur le site ! Vous y trouverez des explications ainsi que des liens vers des outils pour vous protéger du traçage sur Internet. Dans le cadre de mes travaux, les données récoltées par ce site ont été une source d’informations essentielles qui m’a permis de comprendre en détail ce qui était possible avec cette technique.
Comment se protéger du traçage par empreintes ?
Aujourd’hui, le browser fingerprinting est toujours au cœur de l’actualité, et des grands noms de l’Internet comme Apple [1], Mozilla [2], Tor ou Brave [3] travaillent activement dans ce domaine pour protéger leurs internautes. Ils développent des patchs pour leur navigateur pour éliminer le plus possible les différences observables entre appareils. Le navigateur Tor, très célèbre pour sa protection forte de l’anonymat sur Internet, va même encore plus loin en exhibant la même empreinte pour chacun de ses utilisateurs [4]. De
mon côté, j’ai exploré dans mes travaux comment tromper les traceurs sur Internet en changeant constamment d’empreintes [5,6]. Au final, la méthode la plus simple pour se prémunir de cette pratique est tout simplement de bloquer les scripts de traçage et de les éviter. L’utilisation d’un bloqueur de publicités comme uBlock Origin ou de moteurs de recherche respectueux de la vie privée comme Qwant [7] ou DuckDuckgo [8] est très fortement conseillée.
Dans le cadre de la rubrique « Il était une fois… ma thèse », Théo Mary, lauréat du prix SIF Gilles Kahn 2018, nous présente sa thèse effectuée à l’IRIT, où il cherche à exploiter pleinement le potentiel des supercalculateurs en employant une nouvelle méthode algorithmique, moins sensible au nombre d’équations potentiellement explosif. Laure Thiébault
Connaissez-vous le point commun entre prédire la météo de demain, concevoir des voitures résistantes aux crash, et sonder les fonds marins à la recherche de gisements de pétrole ? D’abord, ce sont des problèmes trop difficiles ou coûteux pour être résolus de manière directe. Surtout, ce sont des problèmes physiques que l’on peut décrire par un objet fondamental des mathématiques : les équations linéaires. Par conséquent, on peut simuler numériquement la résolution de ces problèmes en résolvant des systèmes d’équations linéaires.
Un système d’équations linéaires (sous forme matricielle)
Vous vous souvenez certainement combien il pouvait être fastidieux, en cours de maths au lycée, de résoudre de tels systèmes, même en présence d’un petit nombre d’équations. Or, en pratique, il est courant d’avoir affaire à des systèmes de plusieurs milliers, voire millions d’équations. Si l’on dispose heureusement d’algorithmes de résolution et d’ordinateurs capables de résoudre ces systèmes à notre place, le coût de calcul peut devenir très élevé pour un nombre d’équations aussi important.
Pour répondre à ce besoin, de grandes quantités de ressources et d’argent sont consacrées à la construction de supercalculateurs disposant d’une gigantesque puissance de calcul, grâce à un grand nombre d’unités de calcul appelées « cœurs ». À titre d’exemple, si votre ordinateur personnel possède probablement au plus une dizaine de cœurs, le supercalculateur à cette date le plus puissant du monde dispose de plusieurs millions de cœurs. Malgré tout, la taille des problèmes à résoudre aujourd’hui est tellement grande que même ces supercalculateurs ne sont pas suffisants.
Pour relever ce défi, j’ai travaillé pendant ma thèse sur de nouveaux algorithmes de résolution dont le coût calculatoire est fortement réduit. Plus précisément, il est crucial que le coût de ces algorithmes, c’est-à-dire leur complexité, ne dépende que faiblement du nombre d’équations. Depuis le début des années 2000, des méthodes dites « hiérarchiques » ont été proposées. Cependant, ces méthodes hiérarchiques, très complexes et sophistiquées, ne sont pas capables d’exploiter efficacement les supercalculateurs : ainsi, leur réduction de la complexité théorique ne se traduit que très modestement en gains réels de temps de calcul.
C’est pourquoi ma thèse s’est concentrée sur une autre méthode (dite « Block Low Rank »), plus adaptée que les méthodes hiérarchiques à être mise en œuvre sur les supercalculateurs. Mon premier résultat fondamental a été de calculer la complexité de cette méthode, qui était inconnue. J’ai prouvé que, même si elle était légèrement plus élevée que celle des méthodes hiérarchiques, elle restait suffisamment faible pour s’attaquer à des systèmes de très grande taille. Dans la seconde partie de ma thèse, j’ai travaillé sur la mise en œuvre efficace de cette méthode sur supercalculateurs, pour convertir cette réduction de complexité théorique en gains de temps réels.
En réduisant fortement le coût de résolution des systèmes d’équations linéaires, ce travail a ainsi permis de résoudre plusieurs problèmes physiques auparavant hors de portée, notamment en géophysique où j’ai pu résoudre en moins d’une heure un système de 130 millions d’équations sur un supercalculateur disposant de 2400 cœurs.
Que peut-il se passer dans la tête d’un chercheur quand il a terminé sa journée et que son esprit vagabonde dans l’imaginaire ? Il partage parfois sa pensée sur l’impact de la science ici des sciences du numérique sur notre société, ou il se met aussi à la fantaisie, comme ici. Moi, j’adore. Alors je partage. Serge lui ne voulait pas trop qu’on utilise ce blog pour faire « sa pub », mais bon on ne va pas se censurer non plus, sous prétexte que http://binaire.blog.lemonde.fr existe grâce à lui. Thierry Viéville.
