Publié le

Sihem Amer-Yahia : quand l’informatique devient sociale

Sihem Amer-Yahia, site du Laboratoire d’Informatique de Grenoble

Sihem Amer-Yahia est directrice de recherche CNRS, responsable d’une équipe du Laboratoire d’Informatique de Grenoble à la frontière entre la fouille de données, la recherche d’informations, et l’informatique sociale (social computing).

Après un diplôme d’ingénieur à l’ESI d’Alger, en 1994, elle passe sa thèse en 1999 chez Inria, sous la direction de Sophie Cluet, sur le chargement massif de données dans les bases de données orientées objet. Sihem se lance ensuite dans un grand voyage académique et industriel : un post-doctorat à AT&T Labs, puis des postes à Yahoo! Labs toujours aux États-Unis, Yahoo! Barcelone, le Computing Research Institute au Qatar, avant de rejoindre Grenoble et le CNRS en 2012.

Entre temps, la doctorante est devenue une chercheuse de renommée internationale avec des contributions majeures notamment sur le stockage et l’interrogation des données XML et les systèmes de recommandation.

Sihem a vite compris l’importance du caractère social des données produites par des humains. Elle a été convaincue que pour des logiciels faisant interagir des humains, comme les réseaux sociaux, le crowd sourcing, les systèmes de recommandation, les logiciels de ressources humaines, il fallait tenir compte des comportements sociaux, des facteurs humains.

Image par Gerd Altmann de Pixabay

Donc parlons d’informatique sociale, la passion de Sihem. Le traitement massif de données produites par des humains pose à l’informatique des défis passionnants. Prenons les systèmes de recommandations qui nous aident à choisir des produits ou des services. Pour saisir la richesse des recommandations, il faut maîtriser la langue, et tenir compte du comportement humain : Qu’est-ce qui conduit quelqu’un à s’« engager » en donnant une opinion ? Quels sont les souhaits de chacun ? Quels pourraient être les biais ?… Les données humaines s’introduisent partout, par exemple : dans la justice (comment évaluer les risques de récidive), dans la politique (comment analyser les données du Grand Débat, ou les réactions sur les élections sur Twitter), dans la médecine (le dialogue avec le patient dans le cadre du diagnostic automatique), dans la sociologie (comment détecter automatiquement des messages de haine), dans l’Éducation nationale (comment se comportent les élèves devant Parcoursup)… Cela nous conduit aux frontières de l’informatique, et les informaticiens y côtoient des linguistes, des juristes, des spécialistes de sciences politiques, des sociologues, des médecins, des psychologues… Toute la richesse des sciences humaines et sociales, et au-delà.

Sihem est aujourd’hui internationalement reconnue par ses pair·e·s. Ses travaux sont énormément cités, et ont trouvé des applications directes au sein des entreprises qui l’ont employée.

Sihem aime faire partager sa passion pour l’informatique et la recherche. On pourra lire ou relire ses articles récents [1] dans binaire sur les algorithmes de RH. Elle milite pour plus de place pour les femmes dans les sciences ; elle est source d’inspiration pour les jeunes chercheuses en informatique (un domaine très déséquilibré en genre).

La prestigieuse médaille d’argent du CNRS, qui distingue chaque année un·e scientifique d’un laboratoire CNRS dans chaque discipline, lui a été attribuée en 2020.

Serge Abiteboul, Arcep & Inria ; Pierre Senellart, ENS, Université PSL

[1] Le testing algorithmique de la discrimination à l’embauche (1) et (2), Sihem Amer-Yahia et Philippe Mulhem (CNRS, Univ. Grenoble Alpes), 2010. www.lemonde.fr/blog/binaire/

Publié le

Comment s’assurer qu’un protocole cryptographique n’a pas de faille ? Une histoire de logique !

Grâce aux auteurs du Livre blanc sur la cybersécurité  qu’Inria a publié en 2019, nous vous proposons une série d’articles sur cette question majeure (cf 1er billet). Stéphanie Delaune et Steve Kremer nous expliquent l’importance des protocoles cryptographiques en partant d’une histoire vraie qu’ils nous content.  binaire

C’est la nouvelle année et comme à son habitude votre grand-mère ne vous a pas oublié. Elle souhaite vous faire parvenir une enveloppe contenant, en plus d’un petit message exprimant son affection pour vous, un billet. Mais voilà, elle ne peut pas faire le voyage jusqu’à chez vous et doit donc utiliser un service
de livraison. Malheureusement,  le seul qui soit accessible pour elle, emploie des livreurs curieux, malins mais surtout malhonnêtes.

Vous comprendrez alors aisément qu’envoyer le billet dans une simple enveloppe n’est pas suffisant. D’ailleurs, l’année dernière, Nicolas ne l’a jamais reçu. Cette année, c’est décidé, Mémé le placera dans un coffre et y apposera un cadenas dont elle seule détient la clef avant de confier le colis au service de livraison. C’est bien joli tout ça, mais comment Nicolas va-t-il s’y prendre pour récupérer l’argent ?

Ils décident donc de se mettre d’accord (au téléphone) sur la marche à suivre. À la réception du coffre, Nicolas sécurisera ce dernier en y apposant son propre cadenas avant de le renvoyer à sa grand-mère (via le même service de livreurs malhonnêtes).

Mémé pourra alors retirer son cadenas et laisser le coffre voyager pour la troisième fois, toujours via le même service. Le coffre étant bien fermé avec le cadenas de Nicolas, les livreurs malhonnêtes ne pourront pas récupérer l’argent, et il pourra, à la réception de celui-ci, récupérer enfin l’argent donné par sa grand-mère.

Cette histoire, à première vue rocambolesque, est en fait très proche de la réalité du monde numérique dans lequel nous vivons. Lorsque vous effectuez un achat en ligne, votre numéro de carte bancaire circule sur Internet, et en l’absence d’une protection adaptée, vous pouvez assimiler cette démarche à l’envoi d’une donnée, parfois personnelle et précieuse, sur une simple carte postale. Les livreurs malhonnêtes représentent des agents malveillants qui sont alors susceptibles d’intercepter les messages échangés sur le réseau Internet pour les lire ou même les modifier. C’est ainsi que pour nous prémunir de ces agents malveillants, la plupart des opérations que nous effectuons sur Internet sont sécurisées par ce que l’on appelle des protocoles cryptographiques, c’est à dire la marche à suivre sur laquelle Nicolas et sa grand-mère se sont mis d’accord au préalable. Les messages échangés utilisent l’analogue des cadenas du monde physique : c’est ce que l’on appelle des algorithmes de chiffrement. Ces protocoles sont utilisés lorsque l’on se connecte à un service de banque en ligne, pour effectuer un achat sur Internet, ou tout simplement pour payer chez un commerçant à l’aide de sa carte bancaire (qu’elle soit avec ou sans contact). Le protocole décrit ci-dessus est d’ailleurs l’analogue physique d’un protocole connu sous le nom de protocole de Shamir à trois passes (1).

Mais voilà, comment garantir à Mémé que le protocole qu’elle a décidé d’utiliser est sûr et que le billet arrivera cette année dans les mains du petit Nicolas , Plus généralement, comment s’assurer que les protocoles que nous utilisons dans notre vie quotidienne pour effectuer des achats en ligne ou parfois même pour voter ne comportent pas de faille ? L’existence d’une telle faille de sécurité, si petite soit-elle, permettrait à un agent malveillant de l’exploiter à grande échelle. L’objectif est donc de s’assurer que chaque protocole que nous utilisons ne comporte pas la moindre faille.

Bien entendu, dans un premier temps, on va pouvoir tester le protocole et regarder si celui-ci se comporte bien ; des experts en sécurité vont alors  examiner le protocole pour s’assurer que ce dernier résiste aux différents types d’attaques connues. Cette étape sera d’ailleurs sans doute suffisante pour que l’expert recale le protocole que Mémé prévoyait d’utiliser. En effet, un livreur malhonnête peut tout simplement intercepter le message lors de sa première traversée, y apposer son propre cadenas, et le retourner à Mémé. Celle-ci, à la vue d’un nouveau cadenas apposé sur le coffre, retirera le sien, et le livreur malhonnête n’aura plus qu’à ouvrir le coffre (puisqu’il possède la clef du cadenas restant). En termes plus techniques, cette faille est due à une absence d’authentification : Mémé ne peut pas reconnaître l’origine du cadenas. Il faut également noter, que cette faille n’est pas due à une faiblesse du chiffrement, mais à une erreur de conception dans le protocole lui-même.

Vous en conviendrez, il n’est donc pas si facile de concevoir un protocole qui résiste à ce service de livreurs malhonnêtes, et il serait bon que l’expert puisse se reposer sur des techniques solides et rigoureuses.

Les experts en sécurité ont recours à des preuves mathématiques, et notamment à la logique. L’idée est d’exprimer le protocole, la propriété de sécurité ainsi que les comportements possibles de l’attaquant à l’aide de formules logiques. Ensuite, des algorithmes sont développés pour garantir que les formules représentant les propriétés de sécurité sont satisfaites pour tous les comportements possibles du protocole et de l’attaquant. Malheureusement, ce problème, que nous aimerions résoudre est connu pour être indécidable. Cela signifie qu’il a été montré qu’un tel algorithme, cette machine automatique qui permettrait de trouver toutes les failles, n’existe pas. Que faire ? Sommes-nous contraint à utiliser des protocoles pour lesquels la sécurité n’a pas été prouvée ?

Même si le problème global est indécidable, on peut trouver des solutions approchées répondant partiellement aux besoins exprimés. Des outils de vérification sont alors développés et permettent de garantir la sécurité dans un cadre restreint, comme par exemple en ne considérant qu’un nombre fixé d’exécutions du protocole. Ces algorithmes, pourtant très puissants, peuvent aussi simplement essayer de résoudre le problème général sans avoir la garantie de réussir à conclure dans tous les cas. Le but est de développer des techniques qui fonctionnent sur les protocoles que nous utilisons en pratique. Une autre approche possible consiste à ne pas essayer de développer un outil entièrement automatique mais un outil de vérification interactif. L’outil est donc là pour assister l’expert et l’aider à mener sa preuve jusqu’au bout sans oublier de cas. L’outil peut également faire lui-même les cas les plus faciles, et l’expert ne sera là que pour finaliser le raisonnement dans les cas les plus difficiles.

Les protocoles que nous utilisons à l’heure actuelle n’ont pas tous fait l’objet d’une vérification formelle poussée mais la tendance est à l’amélioration. Par exemple, une étude approfondie des protocoles de téléphonie mobile 5G a été réalisée avec l’outil de vérification Tamarin (2) et des améliorations ont ainsi
été proposées. Le protocole TLS 1.3 (le protocole qui se cache derrière le cadenas figurant au niveau de l’URL quand vous accédez à une page web sécurisée dont l’adresse indique le protocole https) a également été développé avec ce souci de rigueur et l’utilisation d’outils de vérification. Cela reste un travail colossal réalisé par des équipes de recherche et on est encore loin d’un monde où 100% des protocoles ont été prouvés. De plus, il faut bien être conscient que la preuve, si rigoureuse soit-elle, est réalisée dans un modèle, qui n’est qu’une représentation mathématique des programmes exécutés : on peut donc garantir l’absence d’un certain type de failles dans ce contexte, mais cette approche ne permet pas de découvrir les failles au-delà du modèle considéré. Imaginez par exemple, qu’il soit possible de retrouver la clef de chiffrement utilisée lors d’un paiement en mesurant finement le temps mis par la carte pour répondre à une requête. Une telle attaque, appelée attaque par canaux cachés, ne sera a priori pas prise en compte, car sortant des hypothèses du modèle de départ.

Les recherches dans le domaine de la vérification formelle de protocoles s’orientent à l’heure actuelle vers plus d’automatisation et visent à faciliter l’utilisation de ces outils. L’idée est de permettre aux concepteurs de protocoles de les vérifier avant leur déploiement. Compte tenu de la vitesse à laquelle les protocoles sont créés et déployés, il est important que cette phase de vérification puisse se faire plus rapidement et ne repose pas uniquement sur le travail d’un petit nombre d’experts. Enfin, les outils de vérification à l’heure actuelle se concentrent sur les propriétés de sécurité les plus classiques que sont la confidentialité d’une donnée ou l’authentification d’un participant. Le chemin est encore long pour s’assurer que des propriétés comme l’anonymat ou la proximité physique entre une carte et un terminal
de paiement soient satisfaites.

Mémé avait prévu de passer au paiement sans contact pour l’année 2020 . . . il faudra donc repasser !

Stéphanie Delaune (CNRS) & Steve Kremer (Inria)

(1) Ce protocole nécessite un chiffrement un peu particulier, permettant de déchirer plusieurs chiffrement imbriqués “dans le désordre”. Une description plus détaillée de ce protocole est disponible sur sa page wikipedia.

(2) Tamarin est un outil permettant d’analyser automatiquement la sécurité de protocoles cryptographiques. L’outil est développé conjointement à l’ETH Zürich (Suisse), au CISPA (Allemagne) et dans l’équipe PESTO de l’Inria Nancy et du LORIA.

Publié le

Les biais biométriques et ethniques des logiciels de reconnaissance faciale

Développée depuis longtemps, la reconnaissance faciale est aujourd’hui au centre de nombreux débats questionnant la mise en œuvre de cette technologie, notamment sur un plan éthique. Avec des décisions parfois hésitantes comme celles de la Commission européenne qui, après avoir annoncé un moratoire sur l’utilisation de cette technologie, est revenue en arrière quelques jours après. Afin de pouvoir comprendre les enjeux, il est important de bien connaître ces algorithmes et leurs biais. C’est pour contribuer à cette maîtrise que Charles Cuvelliez et Jean-Jacques Quisquater nous présentent une étude récente analysant des produits commercialisés. Pascal Guitton

De quoi parle-t-on ?

On a tendance à confondre – à tort – reconnaissance faciale et analyse faciale. Avec l’analyse faciale, c’est une ou plusieurs propriétés continues liées au visage (âge, fatigue, stress…) qui sont analysées.  Elle a pour but de déterminer une quantité qui permet de verser une personne dans une catégorie (son sexe, son état émotionnel…). Les algorithmes utilisés sont construits avec une connaissance présupposée des catégories en question.

La reconnaissance faciale et les algorithmes qui la sous-tendent calculent, sur la base du visage à reconnaître, un ensemble de valeurs qui caractérisent l’identité de la personne.  Ils comparent ces valeurs soit avec celles d’une base de données lorsqu’il s‘agit d’identifier une personne (identification), soit avec une image du visage prise antérieurement (authentification), par exemple pour déverrouiller un smartphone ou une application bancaire. Un score de similitude est calculé, puis comparé à un seuil fixé par le développeur de l’algorithme. Ce seuil, atteint ou non, décide si le visage est reconnu.

Cette photo montre un passage devant une borne à l'aéroport. On y voit son visage reflété sur l'écran
Borne de la compagnie Delta Air Lines pour les passagers à l’aéroport d’Atlanta – Photo  Chris Rank, Rank Studios 2018) – DeltaNewsHub on Visualhunt / CC BY

Il y a deux types d’erreur : les faux négatifs et les faux positifs. Un faux négatif correspond à une reconnaissance faciale ayant échoué, c’est-à-dire n’ayant pas reconnu un visage pourtant préalablement enregistré. La victime ne peut déverrouiller son téléphone ou passer des portiques de sécurité. C’est souvent gênant, rarement dangereux. Un faux positif est plus problématique. Une reconnaissance est établie alors qu’elle n’aurait pas dû avoir lieu, ce qui se ramène à une usurpation d’identité : une personne obtient des accès auquel elle n’a pas droit ou bien peut être accusée à tort d’un délit.

Selon l’application, l’impact des faux positifs et faux négatifs n’est pas le même : s’il s’agit d’écarter les hooligans d’un stade, un taux élevé de faux négatifs est moins problématique puisque la probabilité d’avoir un hooligan, déjà interdit de stade, est peu élevée.

De gros progrès

Le NIST (National Institute of Standards & Technology), agence du département du commerce des États-Unis, a entamé une étude comparative des solutions commerciales de reconnaissance faciale depuis plusieurs années. Leurs progrès ont été spectaculaires : les taux d’erreur sont  bien inférieurs à ceux de 2010 grâce notamment à l’utilisation des réseaux de neurones profonds (appelés Deep Convolutional Neural Networks en anglais).

La reconnaissance faciale est un problème pratiquement résolu d’un point de vue théorique mais il subsiste encore beaucoup d’algorithmes qui n’atteignent pas la perfection des meilleurs et qui restent cependant intégrés dans des solutions commercialisées. En fait, seuls quelques algorithmes excellent vraiment, notamment pour des images de basse qualité ou pour une reconnaissance faciale qui doit rester efficace sur plusieurs années (c’est-à-dire pour gérer le vieillissement, qui s’il n’est pas bien pris en compte, nécessite par exemple de refaire son passeport). Ne pas choisir un « bon » algorithme, entraîne donc une prise de risques.

Cette photo montre le visage d'un homme sur lequel sont superposées des mesures de hauteur et de largeur (yeux, bouche, nez...).
Photo credit: IBM Research on Visual hunt / CC BY-ND

S’il paraît évident que la qualité des photos utilisées influe directement sur les résultats, il était difficile d’imaginer l’importance de la présence d’un opérateur qui vous guide au moment de la saisie initiale (orientation de la tête ou expressivité du visage [1]) écrit le NIST.  Idéalement, même, il faudrait disposer de plusieurs images d’une même personne dans la base de données de comparaison. L’étude souligne que certains algorithmes ne sont pas stables avec la taille de la base de données : leur taux de faux positifs et de faux négatifs augmente en fonction de cette dernière, ce qui ne permet pas de les utiliser à grande échelle.

Le NIST rappelle que ces algorithmes ne sont pas devenus monnaie courante ; il subsiste des différences de performances importantes qui justifient le maintien d’un test continu d’évaluation.

Cet organisme recommande de ne pas se contenter des simples critères comme le coût ou la facilité d’intégration de l’algorithme dans le système visé. Il faut aussi tenir compte de ses performances, de la possibilité d’un contrôle humain en cas de doute, de la maintenance du code, etc.

Des biais démographiques qui posent question

Le NIST s’est également intéressé aux biais démographiques. Ces faux positifs et/ou ces faux positifs sont-ils plus fréquents pour les femmes, les jeunes, les personnes âgées, sont-ils sensibles à l’origine ethnique ? L’étude a considéré les quatre grands ensembles de photos en usage aux États-Unis : les photos judiciaires et de signalement, les photos des candidats à l’immigration, les photos des candidats à l’obtention d’un visa et les photos aux frontières. Il s’agit en tout de 18.27 millions de photos de 8.49 millions de personnes sur lesquels 189 algorithmes commerciaux de 99 développeurs ont été testés. C’est le taux de faux positifs qui est le plus sensible aux variations démographiques, quel que soit l’algorithme : on observe une variation de ce taux évoluant entre 10 et 100. Les faux négatifs sont plus dépendants de l’algorithme avec une variation du taux en-dessous de 3.

Pour les faux négatifs, le NIST observe un taux d’erreur  entre 0.5 % et 10 % selon l’algorithme. Pour les photos d’identité judiciaire, c’est chez les personnes de couleur noire que le taux d’erreur est le moindre. Leur visage vieillit moins vite, pense, pour l’expliquer, le NIST qui ne veut pas relier cette observation à une proportion plus grande de personnes de couleur noire dans  l’identité judiciaire.

Avec des photos de haute qualité prises dans le cadre d’une demande d’immigration, le taux de faux négatifs est beaucoup plus bas, et ne recèle, semble-t-il, aucune sensibilité aux différences démographiques. Quant aux images prises dans des conditions plus précaires au passage des frontières, les faux négatifs sont plus élevés pour les personnes originaires d’Afrique, des Caraïbes et pour les individus plus âgés.

Les faux positifs

L’étude a aussi révélé que le taux de faux positifs, plus dangereux donc, était de 2 à 5 fois plus élevé chez les femmes, selon  l’algorithme, le pays d’origine ou l’âge. Quant à l’origine ethnique, le taux de faux positifs est le plus élevé pour les Africains de l’est et de l’ouest du continent. Il reste élevé pour les gens d’Amérique centrale. Le taux d’erreur est le moins élevé pour les Européens de l’Est.

Les algorithmes développés par les entreprises chinoises sont les meilleurs, écrit le NIST : non seulement, ils ont des bas taux de faux positifs tant pour les Asiatiques (pour lesquels les autres algorithmes fonctionnent mal) que pour les Caucasiens. L’environnement géographique et culturel du développement de l’algorithme a une importance, ne fut-ce que par le choix des données d’entraînement.

Peut-on limiter ces erreurs ? Oui, lorsqu’il s’agit d’une reconnaissance d’identité, il suffit de passer la  base de données en revue plusieurs fois avec plusieurs algorithmes ou d’appliquer des techniques d’évitement (comme présenter à un évaluateur humain tous les faux positifs). Avec un algorithme d’authentification (par exemple déverrouiller un appareil), c’est plus difficile puisqu’on a une décision tout ou rien, sans retour possible. Quelques algorithmes comme Idemia ou NEC3 ne présentent pas de biais démographique et seront d’ailleurs utilisés pour identifier les athlètes aux jeux olympiques de Tokyo, qui brasseront toutes les origines ethniques.  De façon plus globale, il faut plutôt privilégier les algorithmes qui produisent des taux de faux positifs ou faux négatifs indépendants de la taille de la base de données de comparaison (Aware, Tevian et Real Networks), ils permettent de faire  de la reconnaissance de masse (pour le meilleur ou pour le pire).

Quelles sont les causes des faux positifs et faux négatifs dus aux biais démographiques ? Le NIST ne s’avance pas mais mentionne quelques pistes d’explication, comme les effets de la caméra, notamment l’interaction caméra-individu ou comme on s’en doute la qualité de l’image. Certains algorithmes mesurent la qualité de l’image et refusent carrément une reconnaissance si elle n’est pas suffisante, pour éviter un  faux négatif.

Comme le montrent les algorithmes développés en Chine qui présentent moins de biais démographiques, parce que disposant de données d’entraînement plus larges et plus multi-ethniques, étendre les données d’entraînement est un premier remède. Exploiter la finesse de la texture de la peau ou la forme du visage sont d’autres moyens d’améliorer la reconnaissance : il existe un algorithme  breveté en 2004 qui a réussi, sur cette base, à distinguer des vrais jumeaux !  La reconnaissance de l’iris n’est pas, non plus, prise en compte dans les algorithmes de reconnaissance faciale. Mais ce n’est pas facile : la précision actuelle des capteurs nécessite d’être positionné très (trop) près de la caméra pour que l’iris soit correctement détecté. Enfin, dernière piste, on peut fixer des seuils différents en fonction du groupe visé, âgé, jeune, d’une certaine origine ethnique, à partir duquel on déclare avoir un faux positif ou un faux négatif variable. C’est assumer les biais démographiques.

Quelle régulation ?

L’Europe hésite : en quelques jours, elle a d’abord annoncé vouloir mettre un moratoire visant à interdire pendant 5 ans la reconnaissance faciale dans les lieux publics, puis elle a fait marche arrière en évoquant la mise en place d’exigences spécifiques pour encadrer cette technologie. Entre le déverrouillage de son mobile et la surveillance continue des citoyens dans la rue, la reconnaissance faciale couvre un très large spectre d’applications. Prenons le temps d’une vraie réflexion éclairée par une bonne connaissance des solutions et des enjeux avant de décider une quelconque utilisation.

Charles Cuvelliez (Ecole Polytechnique de Bruxelles, Université de Bruxelles) & Jean-Jacques Quisquater (Ecole Polytechnique de Louvain, Université de Louvain et MIT)

[1] les réseaux de neurones profonds sont robustes à ces critères

Pour en savoir plus :

NISTIR 8271, Face Recognition Vendor Test (FRVT) Part 2: Identification Patrick Grother & alii, Information Access Division, Information Technology Laboratory, https://doi.org/10.6028/NIST.IR.8271

NISTIR 8280, Face Recognition Vendor Test (FRVT), Part 3: Demographic Effects, Patrick Grother & alii, Information Access Division, Information Technology Laboratory https://doi.org/10.6028/NIST.IR.8280

Publié le

Tout est question de point de vue

Sidonie Christophe est chercheuse au sein du Laboratoire en sciences et technologies de l’information géographique (LaSTIG). Dans ce troisième et dernier billet de la série, elle nous explique les enjeux autour de la superposition de cartes, de l’utilisation de la transparence ou d’autres dispositifs numériques permettant d’y voir plus clair dans la visualisation de données complexes.
Antoine Rousseau

Ce texte fait suite aux billets « La géovisualisation, kézako ? » et « Les cartes, c’est trop stylé ! »

Naviguer dans les données, explorer les données, cela sous-entend que l’utilisateur va vouloir passer d’une donnée spatiale à une autre, d’un ensemble de données à un autre, d’une représentation graphique à une autre, d’une dimension à une autre, sans perdre ses repères visuels. La complexité des données et des phénomènes spatio-temporels demande de proposer des outils de géovisualisation permettant à l’utilisateur de changer de point de vue, « pour y voir plus clair » !

Il y a le point de vue d’où on observe l’espace représenté, notre position géographique réelle et celle de notre point de vue dans la représentation, à travers un dispositif numérique (écran, appareil-photo, caméra 3D, lunettes de réalité augmentée, etc.) ou non… et les nombreux angles sous lesquels on peut observer cette représentation (vue du dessus, vue oblique, en immersion, à hauteur de piéton, des toits, etc.) et chercher à voir, ce qui peut être invisible, caché, ou trop compliqué à distinguer. Il est aussi possible de naviguer plus ou moins haut en altitude, plus ou moins en profondeur dans une scène, plus ou moins loin dans le passé, ou dans le futur…

Au-delà de la transparence…

L’empilement de données, comme on le fait dans les systèmes d’information géographique (SIG), permet grâce au jeu de couleurs et de transparences de co-visualiser des données. Néanmoins, la transparence seule a des limites et elle peut aussi rendre tout illisible. Pour améliorer cela, il a fallu concevoir un outil pour mixer progressivement les couleurs et les textures de la carte et de l’image satellite, à l’aide d’un curseur qui permet d’introduire plus ou moins de photo-réalisme dans la carte, ou plus ou moins d’abstraction dans l’image, et choisir soi-même le « bon mélange des couleurs et des textures ». Cela permet par exemple de créer des continuums entre IGN Top25 classique, carte Pop Art et image satellite (1), ou un continuum IGN & OpenStreetMap, ou tout type de continuum.

Continuum de styles topographiques (Hoarau & Christophe 2017)(1)

Le projet MapMuxing avec Inria/ILDA, UMR GRED a permis d’expérimenter des outils de multiplexing cartographique, comme ceux utilisés sur Remonter le Temps (2), pour améliorer la navigation multi-échelle, la co-visualisation de données thématiques, dans l’espace et dans le temps.

Multiplexer des données (Remonter le Temps) (2)

Basculer de la 2D en 3D, en nD…

Selon le contexte d’usage final, l’utilisateur doit pouvoir bénéficier de ces changements de points de vue et explorer ses données, selon des styles différents, ou en 2D ou en 3D. Par exemple, la question de la gestion des inondations et des submersions marines peut se visualiser pour différents types d’usages : animer dans le temps une marée montante (3-1 : marée basse, 3-2 : marée haute), la visualiser en 2D ou en 3D, visualiser des impacts d’une montée des eaux sur des bâtiments (4).

 

Différents points de vue d’une montée des eaux, selon les usages (iTownsResearch) (3).

La géovisualisation doit permettre d’aller plus loin dans l’aide à l’analyse visuelle de données scientifiques, en particulier environnementales, issues de simulations d’aléas hydrauliques (avec l’IFSTTAR), ou de données climatiques urbaines (avec des instituts météorologiques européens et Météo France) : nous cherchons à aider à identifier des artefacts et des changements à travers les échelles spatiales et temporelles, à aider à l’interprétabilité des données, à comparer des sorties de modèles (4-1), en facilitant les premières étapes du raisonnement visuel… jusqu’à la (fameuse) prise de décision.

 

Comparaison de scénarios de montée des eaux à l’horizon 2100 iTownsResearch (4-1) ; Identification d’artefacts dans les écoulements dans les données de simulation d’aléas hydrauliques (Octave Perrin, QGIS) (4-2).

Ces questions de recherche restent ouvertes au LaSTIG, comme celles concernant la visualisation sur le temps long, pour aider à la compréhension des dynamiques d’évolution historique des villes, en particulier dans le projet européen Time Machine, ou l’exploitation et la navigation immersive dans des fonds iconographiques massifs ou l’aide au design urbain, à partir de la réalité augmentée.

Au-delà de la vision, et plus précisément quand la vision est déficiente, le « donner à percevoir et à comprendre » reste un enjeu pour nous, géo-« visualisateurs »… pour aider à la mobilité en ville, à partir d’une perception tactile voire haptique à l’aide d’interfaces spécifiques et de cartes 3D (avec le LIMOS et l’IRIT). On dépasse la perception visuelle, pour aller plus loin et explorer toutes les perceptions possibles pour une meilleure compréhension de l’espace géographique.

Sidonie Christophe (Laboratoire en sciences et technologies de l’information géographique)

En savoir plus

Brasebin M., Christophe S., Jacquinod F., Vinesse A., Mahon H. 3D Geovisualization & stylization to manage comprehensive and participative local urban plans , ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci., IV-2-W1, 83-91, 2016.

Christophe S., Brédif M. (2019). Rendu et représentation graphiques d’informations spatio-temporelles. JF.IG.RV.2019 : Journées Françaises de l’Informatique Graphique et de la Réalité Virtuelle , 12-15 Nov. 2019, Marseille.

Christophe S., Duménieu B., Turbet J., Hoarau C., Mellado N., Ory J., Loi H., Masse A., Arbelot B., Vergne R., Brédif M., Hurtut T., Thollot J., Vanderhaeghe D. (2016) Map Style Formalization: Rendering Techniques Extension for Cartography. Pierre Bénard; Holger Winnemöller. Expressive 2016 The Joint Symposium on Computational Aesthetics and Sketch-Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering, May 2016, Lisbonne, Portugal. The Eurographics Association.

ChristopheS., Perret J., Hoarau C. (2013). Extraction de palettes de couleurs pour l’aide à la conception cartographique. Revue des Sciences et Technologies de l’Information (RSTI) série Technique et science informatiques (TSI), Art et Informatique, volume 32 n° 3-4, pp401-430, 2013.

Devaux A., Hoarau C., Brédif M., Christophe S. (2018). 3D urban geovisualization: in situ augmented and mixed reality experiments, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences.

Hoarau C., ChristopheS. (2017). Cartographic continuum rendering based on color and texture interpolation to enhance photo-realism perception ISPRS Journal of Photogrammetry and Remote Sensing, vol. 127, May 2017, pp. 27-38.

Touya, G., ChristopheS., Ben Rhaiem A., Favreau J.-M. (2018). Automatic Derivation of On Demand Tactile Maps for Visually Impaired People: First Experiments and Research Agenda. International Journal of Cartography (TICA).

Publié le

Le divulgâcheur du bureau des légendes

Pour ce premier article de la série Le divulgâcheur, Ludovic Mé, chercheur en sécurité informatique, décrypte pour nous une scène du « Bureau des Légendes ». Il analyse pour binaire les sept minutes de cette scène d’attaque informatique (qui n’en est d’ailleurs pas vraiment une, mais ne déflorons pas le sujet) qui ouvre l’épisode 5 de la saison 4. Il décrit les actions menées par les experts de la DGSE et celles menées par les pirates, et discute du réalisme et de la cohérence de ces actions. Dans toute la suite, la description de ce qui se passe dans l’épisode est en caractère romain, tandis que les commentaires de l’auteur sont en italique. Nous avons le plaisir de co-publier ce texte avec nos ami.e.s d’Interstices dans le cadre de leur série intitulée « L’informatique – ou presque – dans les films« . Pascal Guitton

Attention !

cet article spoile l’épisode 5, saison 4 du Bureau des Légendes.

Les experts informaticiens de la direction technique de la DGSE sont à pied d’œuvre. Ils attaquent un site, sans doute localisé en Russie, mais ils n’en sont pas totalement sûrs. Et c’est pour la bonne cause, bien entendu : y récupérer un code malveillant, afin de l’analyser et d’en tirer toutes les informations possibles.

Tout d’abord, comment les experts ont-ils appris l’existence de ce code et la manière de le récupérer ? Quelque temps auparavant, Rocambole, une agente de la DGSE infiltrée dans un institut de recherche russe, a vu son téléphone et tous ses appareils connectés victimes d’un groupe de pirates. Un programme malveillant (un virus, ou un programme chargé sur un appstore et contenant une fonction cachée) y a été installé.

Attaquer le téléphone de Rocambole était une bonne idée. Souvent mal protégés (même si cela semble étonnant pour un agent infiltré), les téléphones sont fragiles. Ils sont en outre des cibles intéressantes car ils contiennent énormément d’informations, tant professionnelles que personnelles, qui peuvent intéresser les pirates. Bien que cela ne soit pas précisé dans l’épisode, le virus a vraisemblablement été installé en incitant Rocambole à visiter un site web frauduleux. Notons que la DGSE qualifie les pirates de hackers. Dans le jargon informaticien, ce terme désigne plus globalement toute personne qui cherche à comprendre le fonctionnement de tel ou tel dispositif, pour le réparer, le modifier, ou simplement le maîtriser. Utiliser ce terme à la place du mot pirate est un abus de langage, malheureusement devenu courant.

Les pirates ne soupçonnent en fait pas le double jeu de Rocambole ; ils cherchent juste un moyen de pénétrer dans le réseau de l’institut en ciblant une de ses employés.

Il existe aujourd’hui deux grands types d’attaque virale. Les premières cherchent à atteindre le maximum de monde, pour maximiser le gain attendu, par exemple le vol d’identifiants de connexion. Les secondes ciblent au contraire précisément une personne, dont la position ou les responsabilités font espérer des gains précis. C’est une attaque de ce type qu’a vraisemblablement subie Rocambole.

Heureusement, la tentative de pénétration rendue possible par le virus a été repérée par les mécanismes de sécurité de l’institut, révélant ainsi la présence du virus.

On ne sait rien ici de ce que fait le virus pour faciliter la tentative de pénétration. On n’en sait pas plus sur ce qui aura été tenté durant cette pénétration. Cependant, on peut noter que l’institut de recherche a bien fait de ne pas se contenter de mécanismes de sécurité préventifs. Les attaquants sont malins et ils parviennent parfois à contourner les protections. En complément des mécanismes préventifs, des mécanismes de surveillance ont donc été déployés sur les réseaux et systèmes de l’institut, permettant de détecter certaines attaques a posteriori. Cette deuxième ligne de défense, la supervision de sécurité, est systématique ou presque aujourd’hui, du moins dans les grands organismes.

Le virus a donc été supprimé de tous les appareils de Rocambole. Tous ? Non, malheureusement personne n’a pensé aux bêtes écouteurs Bluetooth qui trainaient au fond de la poche de son manteau.

Le virus s’est propagé à tous les objets qui se sont connectés au téléphone, dont ses écouteurs. Un tel comportement est aujourd’hui assez rare, mais on peut craindre qu’à l’avenir il ne se généralise. Cette propagation est possible car beaucoup d’objets du quotidien intègrent du logiciel qui peut éventuellement contenir des failles exploitables par un virus pour se répandre. L’avenir ultra-connecté, qui nous est promis avec l’internet des objets, pose donc question : la sécurité de ces objets est-elle bien prise en compte ? On sait malheureusement que non dans de très nombreux cas (cf article). Pour autant, installer un virus de manière pérenne sur des écouteurs n’est pas toujours possible. Si on veut que le virus se relance suite à l’arrêt et au redémarrage des écouteurs, celui-ci doit être rendu persistant, c’est-à-dire présent dans la mémoire à long terme du dispositif attaqué, et pas seulement dans sa mémoire d’exécution. C’est possible, mais il faut alors que le dispositif contienne une fonction de mise à jour, que le virus aura pris le soin d’enclencher lors de son installation, pour s’enregistrer en mémoire à long terme. Cela suppose en outre que cette fonction de mise à jour ne soit pas elle-même sécurisée.

Les écouteurs de Rocambole ont fini dans les mains des experts de la DGSE, qui ont donc pu analyser le virus qui s’y trouvait.

L’analyse du code des logiciels malveillants (dont les virus) est une activité menée couramment dans des entreprises de sécurité ou des laboratoires de recherche. L’épisode ne donne aucun éclairage sur cette analyse. On peut cependant noter ici que ce travail n’est généralement pas simple. En effet, tout code malveillant sérieux est obscurci (l’anglicisme « obfusqué » est utilisé), c’est-à-dire que ses auteurs font tout pour le rendre incompréhensible. De nombreuses techniques existent pour cela, mais, en particulier, il arrive souvent qu’une partie du code soit chiffrée, ce qui le rend complètement inexploitable, à moins de retrouver la clé de chiffrement qui est cachée dans ce code et d’exécuter la routine de déchiffrement qui s’y trouve aussi. Visiblement, les experts de la DGSE sont très forts ! Ils ont contourné toutes les difficultés et sont venus à bout de l’analyse.

L’analyse du virus a permis aux experts de découvrir que celui-ci pouvait télécharger un autre code malveillant, potentiellement beaucoup plus dangereux encore.

Le téléchargement d’une charge plus dangereuse est en effet une fonction classique que l’on retrouve dans de nombreux logiciels malveillants.

Pour obtenir ce nouveau code puis l’analyser, une seule solution : activer son téléchargement ! C’est donc ce que font les experts.

On voit ici que les experts ne sont pas réellement en train d’attaquer le site russe, comme nous le disions un peu trop rapidement en début d’article. Ils ne font que déclencher la fonction de téléchargement qu’offre ce site.

Parce qu’ils ne veulent prendre aucun risque, les pirates cherchent à établir la légitimité du téléchargement. En effet, si la demande ne provenait pas d’un site infecté, c’est potentiellement qu’on chercherait à les tromper.

Ce passage est peu cohérent. Nous l’avons vu, Rocambole a vraisemblablement subi une attaque ciblée. Les pirates s’attendent donc à ce que le programme dangereux qu’ils ont rendu accessible sur leur site soit téléchargé par le virus. Ils devraient selon toute vraisemblance avoir mis en place un mécanisme (dit d’authentification) pour s’assurer que la demande de téléchargement provient bien de ce virus et de personne d’autre. Ne pas le faire et mettre leur programme dangereux (et sûrement très précieux !) en téléchargement libre relèverait de l’amateurisme. Ils sont pourtant présentés comme très forts …

Les experts de la DGSE (très forts, eux aussi, rappelons-le) soupçonnent les précautions prises par les pirates. Or, il ne faut pas que la DGSE soit identifiée comme source du téléchargement, sans quoi les pirates, en plus de se savoir repérés, comprendraient que Rocambole est une agente infiltrée. Il faut donc rendre la plus difficile possible l’identification de la source de la demande de téléchargement. À cette fin, les experts s’arrangent pour que cette demande transite par neuf serveurs intermédiaires, relais répartis sur la surface du globe, avant d’atteindre le serveur pirate. Ils brouillent les pistes et compliquent ainsi le travail d’identification des pirates. De plus, au fur et à mesure de la progression de la requête de serveur en serveur, ils prennent soin de supprimer de ces relais les traces de leur passage.

Notons que la demande de téléchargement aurait pu être réalisée depuis le téléphone de Rocambole, puisque la DGSE pourrait en disposer, le réinfecter, et déclencher ainsi le téléchargement par le virus depuis le sol russe. Cela aurait évité tout risque de localisation. Ce n’est, bizarrement,  pas la solution qui a été choisie. Ceci étant dit, la demande de téléchargement étant déclenchée depuis les locaux de la DGSE, l’utilisation de rebonds au travers de plusieurs relais est vraisemblable. Il s’agit en effet d’une technique de camouflage courante. On peut d’ailleurs noter que cette technique peut aussi être utilisée pour protéger la vie privée des utilisateurs : c’est ce que fait le réseau Tor, par exemple. On ne sait cependant pas comment les neuf relais sont choisis. Sans doute pas au hasard, car alors il n’y aurait pas de raison qu’ils relayent la demande de téléchargement, puisqu’ils n’auraient pas été programmés pour cela. Il faut donc imaginer que ces relais sont sous le contrôle de la DGSE, d’une manière ou d’une autre. On peut imaginer que ce sont des machines louées chez différents fournisseurs et sous différentes couvertures. On peut aussi imaginer, même si cela semble improbable car pas éthique, que la DGSE utilise des machines de particuliers ou d’entreprises mal protégées, dont ils ont pris le contrôle et qu’ils pilotent à distance (formant ainsi ce qu’on appelle un botnet). Il y a cependant une nouvelle incohérence : dans ces deux cas, la DGSE aurait pu installer sur ces machines des logiciels pour, d’une part assurer les rebonds, d’autre part effacer toute trace de ces rebonds. Or, plus loin dans l’épisode, on les voit effacer leurs traces à la main.

Les pirates, de leur côté, détectent que la demande de téléchargement est illégitime.

En l’absence d’authentification, cela ne peut se faire qu’en constatant que cette demande provient d’une localisation étrange de leur point de vue, qui n’a a priori pas été infectée.

Ils mettent alors fin au téléchargement et tentent de localiser ceux qui essaient de les berner. Cela va les conduire à passer de relai en relai, en sens inverse des experts de la DGSE.

Comme ils ne disposent a priori d’aucun accès légitime aux relais, les pirates devront attaquer le dernier de la chaîne (le plus proche d’eux), s’y introduire, y trouver de l’information sur l’identité de l’avant-dernier relai, attaquer cet avant-dernier relai, et ainsi de suite. Cette succession d’attaques est possible,mais la vitesse à laquelle elle se produira dans la suite de l’épisode est peu réaliste (nous y reviendrons).

Pour ne pas être détectés, les experts de la DGSE doivent de leur côté effacer leurs traces sur les neuf relais avec plus de rapidité que les pirates ne mettent à les découvrir. Une course de vitesse est donc engagée. Les experts en sortent vainqueurs : aucun relai n’est repéré.

Comme nous l’avons mentionné ci-dessus, on a du mal à comprendre pourquoi l’effacement des traces doit se faire à la main, en tapant des commandes sur un clavier. L’automatisation de l’effacement permettrait d’être infiniment plus rapide. La DGSE dispose certainement du contrôle des relais et aurait pu, dès lors, soit désactiver le système de journalisation des traces, soit installer un logiciel spécifique pour effacer leurs traces. On notera aussi une imprécision de langage : les experts annoncent qu’ils vont « recoder » pour effacer leurs traces. Il s’agit plutôt en fait d’effacer un fichier, comme on le ferait sur un ordinateur personnel. Ce fichier contient de l’information sur toutes les opérations qui sont effectuées sur les serveurs. Le travail de suppression est fait en « ligne de commande » et non dans une fenêtre graphique. À supposer qu’on ait à supprimer des traces à la main, le faire ainsi en ligne de commande est réaliste. Même les commandes passées, qu’on aperçoit sur les écrans des experts, sont correctes. En revanche, la vitesse de frappe des experts n’est pas du tout crédible !

Pour visualiser la progression des pirates, un grand écran des locaux de la DGSE affiche une carte du monde localisant les relais ; ceux-ci passent en rouge si les pirates ont été plus rapides.

Si la présence de cette visualisation est utile pour la compréhension des téléspectateurs, cette représentation graphique de l’avancement des pirates est peu réaliste. En outre, elle suppose que la DGSE surveille chacun des relais de la chaîne et observe les actions des pirates sur ces relais, pour se rendre compte qu’ils ont eu accès aux informations de connexion. Ce n’est pas impossible mais à nouveau c’est peu vraisemblable, supposant que la DGSE ait installé sur ces relais un mécanisme d’observation dédié, alors qu’elle n’a pas pris la peine d’installer un mécanisme d’effacement des traces.

Le premier téléchargement ayant été interrompu par les pirates, les experts en lancent un deuxième, passant par neuf nouveaux relais. Etant donnée la vitesse de réaction des pirates, qui ont coupé la première connexion alors que le quart du code malveillant seulement avait été chargé, les experts en déduisent (habilement !) qu’ils leur faudra environ quatre essais.

Choisir un autre chemin passant par de nouveaux relais est prudent, même si aucun relai du premier chemin n’a été découvert par les pirates. Il est possible de reprendre un téléchargement à l’endroit où il avait été interrompu précédemment, mais cela suppose que le serveur accepte cette fonction de reprise. Nous les avons déjà traités d’amateurs ; nous nous contenterons donc ici de trouver nos pirates plutôt sympathiques : leur serveur autorise la reprise de téléchargement !

Comme lors du premier téléchargement, les pirates détectent que la deuxième demande est illégitime et ils y mettent fin. Mais les experts disposent à présent de la moitié du code malveillant qu’ils convoitent. Et à nouveau, ils gagnent la course de vitesse : seuls deux relais sont localisés. La situation est donc moins favorable que lors de l’essai initial, mais leur protocole d’attaque les autorise à poursuivre l’opération en lançant un troisième téléchargement, car moins de cinq relais ont été découverts. Cependant, lors de ce troisième téléchargement, les choses ne se passent pas aussi bien. Quasi-instantanément, six relais sont localisés par les pirates. Puis un septième. Plus que deux et les pirates sauront que la source est la DGSE. L’heure est grave. Le plus expérimenté des experts prend alors lui-même les choses en main. Ses doigts volent sur le clavier. Un huitième relai est découvert. Plus qu’un seul relai en rempart ! Les commandes s’enchaînent à la vitesse de l’éclair. L’anxiété est à son comble dans la salle d’opération. Chacun redoute de voir le dernier maillon de la chaîne des relais, celui qui précède le site de la DGSE, s’afficher en rouge. Mais non. Ouf. Le plus fort des experts a été plus rapide que les pirates. La progression du rouge s’arrête.

Ne revenons pas sur la vitesse de frappe … Ce qui est le plus difficilement explicable dans cette séquence, c’est la détection quasi-instantanée par les pirates de six relais de la chaîne. Rappelons que les pirates ne disposent a priori d’aucun accès légitime aux relais ; ils doivent les attaquer un à un, s’y introduire et y trouver l’identité du relai précédent. Ce travail est automatisable en partie, certes. Mais la vitesse de localisation atteinte reste très surprenante.

L’opération doit être maintenant stoppée puisque plus de cinq relais ont été localisés. Les experts disposent cependant de 800 kilo-octets de code. L’analyse peut commencer ! Les experts trouvent essentiellement du code compilé, qu’ils estiment inexploitable.

Alors que le code source d’un programme est écrit par son programmeur en utilisant un langage humainement compréhensible (C, java, python, C++ sont des exemples de tels langages), le code compilé est la traduction de ce code source en une suite de valeurs binaires pouvant être comprises par la machine, mais très difficile à interpréter pour des humains. Pour comprendre ce que fait le code malveillant, les experts pourraient tenter de décompiler le code binaire pour revenir au code source, ce qui est parfois possible. D’autres solutions sont aussi envisageables. Pourtant, bien que la compréhension du code téléchargé soit leur objectif initial, les experts laissent de coté le code compilé qu’ils ont récupéré. Nouvelle incohérence, donc

Outre du code compilé, ce qui a été téléchargé contient aussi des passages humainement lisibles, comme un fichier de configuration en langage XML. Les experts se concentrent sur cette partie de code. Et là, bingo, parmi les information de configuration, ils découvrent une information intéressante : une adresse IP.

La vitesse à laquelle cette adresse aura été découverte, dans environ 800 kilo-octets de code, est peu réaliste. En quelques secondes, après un simple survol, les yeux de lynx de l’expert en chef vont repérer dans ce code l’information qui peut être utile. Dans la réalité, vous vous en doutez peut-être, les choses ne seraient pas aussi simples. Tout d’abord, le code serait très vraisemblablement obfusqué, comme déjà expliqué. À supposer qu’il ne le soit pas (ou qu’une « déobfusquation » soit couronnée de succès), resterait à analyser une masse de données importante, qui là encore prendrait du temps. Mais admettons. Il est en revanche possible que des bouts de XML, lisibles, soient inclus dans ce qui a été téléchargé. Et il est en effet possible que ce XML contienne les informations de configuration du code malveillant, ce qui évite à la personne qui lance ce code de taper au clavier ces informations. On dit qu’elles sont « en dur » dans le code. Pour autant, à nouveau, nos pirates font preuve du plus grand amateurisme : laisser dans leur code une adresse IP est inconscient ! Une adresse IP est une suite de nombres correspondant à l’adresse d’une machine sur internet. Lors des courses de vitesse que nous avons décrites précédemment, ce sont les adresses IP des relais que les pirates devaient découvrir. On le voit, ce sont des informations sensibles. Il est hautement improbable que les pirates aient laissé cette information, même si l’expert prétend que tous les programmeurs l’ont un jour fait, sachant que c’est le meilleur moyen de se faire localiser.

Une recherche rapide indique que l’adresse IP découverte (203.0.113.186) appartient à un centre de recherche russe en intelligence artificielle (IA). Une fois le nom de ce centre découvert, il est facile de le localiser sur une carte.

Pour déterminer à qui appartient l’IP découverte, les experts utilisent le service « whois », qui permet l’interrogation de bases de données qui stockent les références des propriétaires d’une adresse donnée. L’accès à ce service est public. Il permet de connaitre l’organisme à laquelle cette adresse IP a été affectée, l’adresse physique de cet organisme, ainsi que d’autres informations. Les auteurs de la série sont prudents : l’adresse 203.0.113.186 ne correspond à aucun organisme réel ; elle fait en effet partie d’un ensemble d’adresses réservées car destinées à servir d’exemple dans les documentations de l’internet. L’affichage sur une carte de la localisation du centre est facile à réaliser puisque le service whois révèle l’adresse physique de l’organisme auquel l’adresse IP a été affectée. Cet affichage est peu utile et ne serait sans doute pas réalisé dans la réalité. Il permet cependant de bien montrer au téléspectateur que le centre est en Russie, tout proche de Moscou.

Les experts établissent ainsi un lien entre le groupe de pirates et un centre de recherche en IA. Ils en concluent que ce centre a lancé un programme d’expérimentation de l’usage de l’intelligence artificielle pour réaliser des attaques informatiques.

Voilà la découverte extrêmement importante qui fera avancer l’intrigue de la série. Cette in- formation est réaliste. Etant donnés les succès qu’elle a connus dans d’autres domaines, comme l’analyse d’image, l’intelligence artificielle est aujourd’hui regardée avec la plus grande attention dans le but d’améliorer la défense des systèmes d’information (on peut par exemple imaginer une analyse « intelligente » des traces laissées par un attaquant). De nouveaux résultats de recherche et de nouveaux outils apparaissent régulièrement. Il faut cependant noter qu’aucun d’entre eux n’a encore établi clairement que l’IA pourrait avoir un apport aussi important en sécurité défensive que celui qu’elle a eu dans d’autres domaines. L’IA pourrait aussi, comme suggéré dans l’épisode, être utilisée de manière offensive, par exemple pour découvrir voire exploiter des failles dans les systèmes adverses. Nous ne disposons pas d’information publique sur le sujet, mais il nous semble fort probable que tous les grands pays s’intéressent au sujet. Là encore, mais cette fois sans doute fort heureusement, rien ne dit que la démarche sera couronnée de succès.

Alors, au final, cette scène, est-elle réaliste et cohérente ? Globalement, plutôt, oui. Pour autant, dans le détail, pas mal de choses clochent, comme nous l’avons vu. Le plus invraisemblable reste l’amateurisme des pirates, comme nous l’avons souligné à plusieurs reprises. Vient ensuite l’absence d’automatisation de la plupart des actions, spécifiquement coté experts. En revanche, une chose est malheureusement réaliste dans cette séquence : pas de femme parmi les experts, même si on en aperçoit une ou deux à l’arrière-plan ! Et les préjugés ont la vie dure : le personnage, certes supérieur hiérarchique, auquel il faut tout expliquer, et avec les mots les plus simples possible, est … une femme !

Ludovic Mé (INRIA)

Vous souhaitez nous proposer une scène à divulgâcher par un.e spécialiste ? N’hésitez pas ! Il suffit de nous en donner la référence en commentaire à cet article.

Publié le

Rencontre à la frontière entre l’informatique et la biologie

Dans la rubrique « Il était une fois… ma thèse », binaire accueille aujourd’hui Camille Marchet, qui a obtenu un accessit du prix de thèse Gilles Kahn en 2019. Camille nous parle du contenu de sa thèse, préparée à l’IRISA, à Rennes, au cours de laquelle elle s’est intéressée à la conception d’algorithmes manipulant des séquences d’ARNs, pour le plus grand bonheur des biologistes ! Camille a aujourd’hui rejoint l’équipe Bonsai au sein du laboratoire CRIStAL, à Lille. Eric Sopena

Vous avez entendu parler de l’ADN, mais connaissez-vous l’ARN ? Pour les amateurs d’informatique, je pourrais le décrire comme la mémoire tampon dans la cellule. L’ADN stocke comme un disque dur le code source des protéines, qui sont les effecteurs. Cependant il contient un volume immense d’information, dont la totalité n’est pas nécessaire pour produire les protéines. La cellule le garde donc au chaud et copie les portions nécessaires à sa production de protéines dans les ARNs (plus précisément, dans les ARNs messagers, car il existe de nombreux autres ARNs).

Quel rapport avec l’informatique ? On sait séquencer l’ARN en grandes quantités, c’est-à-dire lire ces molécules et en obtenir une version numérique. Cela permet de les traiter comme des chaînes de caractères, très étudiées dans certains pans de l’informatique théorique. Ici on se concentre sur des séquences écrites dans un alphabet bien spécifique (pour simplifier, le même que pour l’ADN : les bases A, C, G, T). Les bioinformaticiens comme moi fournissent des algorithmes et des logiciels permettant de travailler avec ces séquences biologiques. Une fois en leur possession, les biologistes peuvent étudier de nombreuses questions. Un exemple touché par mon travail est l’observation des ARNs présents dans une symbiose de planctons. Elle a permis de mieux comprendre les échanges qui régissent la mise en place et le maintien de cette symbiose.

J’ai eu la chance de démarrer ma thèse pendant une révolution du séquençage. On peut à présent accéder à des molécules entières d’ARN au format numérique. Auparavant, on devait reconstituer les molécules à la manière d’un puzzle, à partir de tout petits fragments. Les nouvelles techniques permettent actuellement de séquencer environ un million de milliards de bases par jour ! Les ARNs chez l’humain mesurent typiquement quelques milliers de bases, et des dizaines de milliers d’ARNs au moins peuvent être trouvés dans une expérience. C’est donc un moment excitant, avec beaucoup de nouvelles données, où beaucoup reste à faire.

En particulier, ces nouvelles données contiennent des erreurs d’une nature et d’une quantité inédites. Nous avons donc besoin d’algorithmes capables de passer outre ce bruit pour comparer les séquences, ou les grouper quand elles sont similaires.

Cela est l’une des contributions de ma thèse. Nous avons conçu une méthode de clustering permettant de diviser les séquences en groupes cohérents correspondants à des gènes, sans utiliser d’autre information que celle contenue dans les bases.

Une molécule d’ARN et ses quatre bases en couleur (A, C, G, U, mais le U est remplacé par un T par souci d’unification avec les séquences d’ADN), et un exemple de séquence issue de la dernière technologie de séquençage sur laquelle nous avons travaillé pour la méthode de clustering (adapté de Wikimedia Commons, séquence issue de NCBI SRA).

Un second point est la possibilité de travailler avec d’énormes volumes de données. Certains champs de la biologie moderne produisent des milliards de séquences en quelques heures pour décrire des environnements complexes, comme les écosystèmes marins. Dans le cadre de ma thèse, nous avons conçu une structure permettant de comparer des jeux de données à très large échelle. Elle peut enregistrer des séquences et leur associer de l’information avec une très faible empreinte mémoire grâce à une technique de hachage. Par exemple, pour le plancton, nous avons enregistré des ARNs connus d’espèces que nous pensions être présentes dans notre expérience. Puis, grâce à la structure, nous les avons comparés aux séquences obtenues lors du séquençage de la symbiose. Ainsi nous avons pu assigner certaines séquences à une espèce identifiée, et ce pour plus de cinq milliards de séquences.

La symbiose planctonique sur laquelle nous avons travaillé. Les organismes impliqués sont unicellulaires. La plus grosse cellule qui prend la majorité de la photo est l’hôte, un collodaire. Les symbiotes (plus petits points jaune pâle) sont de la catégorie des dinoflagellés. La photo a été prise dans le cadre de la mission Tara Oceans en 2011 (crédits : Johan Decelle).

Plus généralement, un problème actuel est de pouvoir stocker, comparer, et rechercher intelligemment dans ces jeux de données massifs. C’est un défi auquel j’ai apporté ma contribution, mais qui va encore nous occuper quelques années !

Camille Marchet
@CamilleMrcht

 

 

 

Publié le

D’où vient le risque ? Des données et des algorithmes

La rencontre de chercheurs juristes et informaticiens dans le cadre du lancement du Centre Internet et Société  et du montage du GdR Internet et Société, a été l’occasion de réflexions croisées et de soulever nombre de questions et premières pistes de recherche à explorer ensemble. Cet article résume le résultat d’une table ronde. Serge Abiteboul, Thierry Viéville
Photo by Fernando Arcos from Pexels
  • Les plateformes numériques et leur rôle dans la société occupent les médias et les instances gouvernantes. Nous, juristes et informaticien·e·s, les percevons comme des nouveaux marchés de la donnée. Plusieurs acteurs humains, artistes, auteurs, créateurs de contenu, développeurs de langages, développeurs de plateformes, développeurs d’applications, internautes consommateurs,  acteurs publics et privés, gravitent autour de ces plateformes et sont exposés à deux types de risque :
    – Le risque-données se réfère à la protection des données sur ces plateformes.
    – Le risque-algorithmes se réfère aux dérives de discrimination algorithmique.

Ce document apporte une première réflexion sur comment appréhender les plateformes numériques et les risque-données et risque-algorithmes. Ces questions peuvent être abordées de deux points de vue complémentaires : le point de vue juridique dont le souci principal est de déterminer les cadres qui permettent d’identifier et de réguler ces risques, et le point de vue informatique dont le but est de développer les outils nécessaires pour quantifier et résoudre ces risques.

Les trois facettes du risque algorithmique.

Le risque-algorithmes peut être caractérisé de 3 façons.

  • Il s’agit d’abord de l’enfermement algorithmique qui peut aussi bien porter sur les opinions, la connaissance culturelle, ou encore les pratiques commerciales. En effet, les algorithmes confrontent l’internaute aux mêmes contenus, selon son profil et les paramètres intégrés, en dépit du respect du principe de la loyauté. C’est le cas sur les sites de recommandation de news comme Facebook ou les sites de recommandation de produits comme Amazon.
  • La deuxième facette du risque-algorithmique est liée à la maîtrise de tous les aspects de la vie d’un individu, de la régulation de l’information à destination des investisseurs jusqu’à ses habitudes alimentaires, ses hobbies, ou encore son état de santé. Ce traçage de l’individu laisse présager l’emprise d’une forme de surveillance qui contrevient à l’essence même de la liberté de l’individu.
  • La troisième est liée à la potentielle violation des droits fondamentaux. En particulier, à la discrimination algorithmique définie comme le traitement défavorable ou inégal, en comparaison à d’autres personnes ou d’autres situations égales ou similaires, fondé sur un motif expressément prohibé par la loi. Ceci englobe l’étude de l’équité (fairness) des algorithmes de classement (tri de personnes cherchant un travail en ligne), de recommandation, et d’apprentissage en vue de prédiction. Le problème des biais discriminatoires induits par des algorithmes concerne plusieurs domaines comme l’embauche en ligne sur MisterTemp’, Qapa et TaskRabbit, les décisions de justice, les décisions de patrouilles de police, ou encore les admissions scolaires.

Nous reprenons une classification des biais proposée par des collègues de Télécom ParisTech et discutée dans un rapport de l’Institut Montaigne à Paris. Nous adaptons cette classification aux risque-données et risque-algorithmes en mettant l’accent sur les biais.

Les données proviennent de sources différents et ont des formats multiples. Elles véhiculent différents types de biais.

Des risques aux biais sur les données et dans les algorithmes.

Le biais-données est principalement statistique

Le biais des données est typiquement présent dans les valeurs des données. Par exemple, c’est le cas pour un algorithme de recrutement entraîné sur une base de données dans laquelle les hommes sont sur-représentés exclura les femmes.   

Le biais de stéréotype est une tendance qui consiste à agir en référence au groupe social auquel nous appartenons. Par exemple, une étude montre qu’une femme a tendance à cliquer sur des offres d’emplois qu’elle pense plus facile à obtenir en tant que femme.

Le biais de variable omise (de modélisation ou d’encodage) est un biais dû à la difficulté de représenter ou d’encoder un facteur dans les données. Par exemple, comme il est difficile de trouver des critères factuels pour mesurer l’intelligence émotionnelle, cette dimension est absente des algorithmes de recrutement.

Le biais de sélection est lui dû aux caractéristiques de l’échantillon sélectionné pour tirer des conclusions. Par exemple, une banque utilisera des données internes pour déterminer un score de crédit, en se focalisant sur les personnes ayant obtenu ou pas un prêt, mais ignorant celles qui n’ont jamais eu besoin d’emprunter, etc.

Le biais algorithmique tient principalement du raisonnement.

Un biais économique est introduit dans les algorithmes, volontairement ou involontairement, parce qu’il va être efficace économiquement. Par exemple, un algorithme de publicité oriente les annonces vers des profils particuliers pour lesquels les chances de succès sont plus importantes ; des rasoirs vont être plus présentés à des hommes, des fastfood à des populations socialement défavorisées, etc.

Il convient également de citer toute une palette de biais cognitifs

  • Les biais de conformité, dits du « mouton de Panurge », correspondent à  notre tendance à reproduire les croyances de notre communauté. C’est le cas, par exemple, quand nous soutenons un candidat lors d’une élection parce que sa famille et ses amis le soutiennent.       
  • Le biais de confirmation est une tendance à privilégier les informations qui renforcent notre point de vue. Par exemple, après qu’une personne de confiance nous a affirmé qu’untel est autoritaire, remarquer uniquement les exemples qui le démontrent.            
  • Le biais de corrélation illusoire est une tendance à vouloir associer des phénomènes qui ne sont pas nécessairement liés. Par exemple, penser qu’il y a une relation entre soi-même et un événement extérieur comme le retard d’un train ou une tempête.
  • Le biais d’endogénéité est lié à une relative incapacité à anticiper le futur. Par exemple, dans le cas du credit scoring, il se peut qu’un prospect avec un mauvais historique de remboursement d’emprunt puisse changer de style de vie lorsqu’il décide de fonder une famille.

    Les algorithmes sont une série d’instructions qui manipulent des données en entrée et retournent des données en sortie. Ces données en entrée véhiculent parfois des biais. Les biais peuvent aussi se trouver dans une ou plusieurs instructions des algorithmes.

Doit-on aborder les risque-données et risque-algorithmes sur les plateformes numériques ensemble ou séparément ?

Considérons deux exemples, le contexte de la technologie blockchain, et celui des systèmes d’Intelligence Artificielle.

Sur la blockchain, l’on retrouve tout d’abord les données, les risques et leur biais. Prenons l’exemple des données et des risques associés. La blockchain fonctionne par un chiffrement à double clés cryptographiques : des clés privées et des clés publiques. Beaucoup d’internautes confient aux plateformes leurs clés privées, leur délégant ainsi la gestion de leur adresse et les mouvements de fonds. Ces clés privées sont stockées soit dans un fichier accessible sur Internet (hot storage), soit sur un périphérique isolé (cold storage). Le premier est évidemment très vulnérable au piratage, tandis que 92 % des plateformes d’échange déclarent utiliser un système de cold storage. Depuis 2011, 19 incidents graves ont été recensés pour un montant estimé des pertes s’élevant à 1,2 milliards de dollars. Les causes de ces incidents sont multiples. La plus courante vient de la falsification des clés privées, suivie par l’introduction de logiciels malveillants. Le hack de la plateforme Coincheck au Japon, en janvier 2018, illustre la faiblesse de la protection du système de hot storage.

Autre exemple sur les algorithmes et les risques associés, l’échange de cryptomonnaies sur des plateformes voit se développer et se diversifier les infrastructures de marché. L’ambition est « de permettre la mise en place d’un environnement favorisant l’intégrité, la transparence et la sécurité des services concernés pour les investisseurs en actifs numériques, tout en assurant un cadre réglementaire sécurisant pour le développement d’un écosystème français robuste » . La France s’est dotée récemment d’un cadre juridique permettant de réguler ces activités de manière souple. Pour autant, au niveau mondial, les risques attachés à des cotations non transparentes ou à des transactions  suspectes s’apparentant à des manipulations directes de cours ou de pratiques d’investisseurs informés, de type frontrunning. Le frontrunning est une technique boursière permettant à un courtier d’utiliser un ordre transmis par ses clients afin de s’enrichir. La technique consiste à profiter des décalages de cours engendrés par les ordres importants passés par les clients du courtier.

Venons en à la question « doit-on aborder les risque-données et risque-algorithmes sur les plateformes numériques ensemble ou séparément ? » Concernant la blockchain, la réponse du droit est séparée, car les risques saisis sont différents. D’un côté, certaines dispositions du droit pénal, de la responsabilité civile ou de la protection des données à caractère personnel seront mobilisées. Alors que de l’autre côté, en France, le récent cadre juridique visant à saisir les activités des prestataires de services sur actif numérique et à éviter le risque algorithmique est principalement régulatoire.

Sur les systèmes d’IA, nous prendrons pour répondre à notre question le prisme de la responsabilité (liability) et de la responsabilisation (accountability).

Cette question est diabolique car elle impose au juriste de faire une plongée dans le monde informatique pour comprendre ce en quoi consiste l’intelligence artificielle, ce mot-valise qui recouvre, en réalité, de nombreuses sciences et techniques informatiques. Et faut-il seulement utiliser ce terme, alors que le créateur du très usité assistant vocal Siri vient d’écrire un ouvrage dont le titre, un tantinet provocateur, énonce que l’intelligence artificielle n’existe pas… (Luc Julia, L’intelligence artificielle n’existe pas, First editions, 2019).

Un distinguo entre les systèmes d’IA est néanmoins souvent opéré : seuls certains systèmes sont véritablement « embarqués » dans un corps afin de lui offrir ses comportements algorithmiques : robot, véhicule « autonome »… Les autres systèmes d’IA prennent des décisions ou des recommandations algorithmiques qui peuvent avoir un effet immédiat sur le monde réel et l’esprit humain, sans avoir besoin de s’incarner dans un corps : recommandations commerciales à destination du consommateur, fil d’actualité des réseaux sociaux, justice prédictive et sont souvent considérés comme « dématérialisés ». Cependant, tous les systèmes d’IA finissent par être  incorporés dans une machine : robot, véhicule, ordinateur, téléphone… et tous les systèmes d’IA peuvent potentiellement avoir un impact sur l’esprit ou le corps humains, voire sur les droits de la personnalité (M. Baccache, Intelligence artificielle et droits de la responsabilité, in Droit de l’intelligence artificielle, A. Bensamoun, G. Loiseau, (dir.), L.G.D.J., Les intégrales 2019, p. 71 s.), tant et si bien que nous choisirons ici de saisir la question de la responsabilité lors du recours aux systèmes d’IA d’une manière transversale.

La question transversale que précisément nous poserons consistera à nous demander si la spécificité des systèmes d’IA, tant au regard de leur nature évolutive et de leur gouvernance complexe, qu’au regard des risques découlant de leur mise en œuvre pour l’humain et la société n’appelle pas à préférer à la responsabilité, entendue comme la seule sanction a posteriori de la réalisation d’un risque, une complémentarité entre responsabilisation de la gouvernance de chaque système d’IA tout au long de son cycle de vie et responsabilité a posteriori. Si la responsabilisation est reconnue comme étape préalable à la responsabilité, elle impliquera d’envisager les risques-données et les risques-algorithmiques, de manière conjointe, préservant ainsi la spécificité de chacun de ces risques, mais en les reliant, parce c’est par la conjonction de ces deux types de risques, que des conséquences préjudiciables pour l’humain ou la société peuvent se réaliser.

En effet, dans ses « lignes directrices en matière d’éthique pour une IA digne de confiance » datant d’avril 2019, le Groupe d’experts de haut niveau sur l’intelligence artificielle, mandaté par la Commission européenne, rappelle dans l’une de ses propositions un point fondamental, à savoir les nécessaires reconnaissance et prise de conscience que « certaines applications d’IA sont certes susceptibles d’apporter des avantages considérables aux individus et à la société, mais qu’elles peuvent également avoir des incidences négatives, y compris des incidences pouvant s’avérer difficiles à anticiper, reconnaître ou mesurer (par exemple, en matière de démocratie, d’état de droit et de justice distributive, ou sur l’esprit humain lui-même) » (Groupe d’experts indépendants de haut niveau sur l’intelligence artificielle, Lignes directrices en matière d’éthique pour une IA digne de confiance, avril 2019, constitué par la Commission européenne en juin 2018,).

Ce faisant, le groupe d’experts de haut niveau en appelle à « adopter des mesures appropriées pour atténuer ces risques le cas échéant, de manière proportionnée à l’ampleur du risque » et, en se fondant sur les articles de la Charte des droits fondamentaux de l’Union européenne,  à « accorder une attention particulière aux situations concernant des groupes plus vulnérables tels que les enfants, les personnes handicapées et d’autres groupes historiquement défavorisés, exposés au risque d’exclusion, et/ou aux situations caractérisées par des asymétries de pouvoir ou d’information, par exemple entre les employeurs et les travailleurs, ou entre les entreprises et les consommateurs ».

Alors même que certains risques et la protection de certains groupes vulnérables l’imposent, prendre les mesures appropriées n’est cependant pas aisé, et ce au-delà même de la tension récurrente entre principe d’innovation et principe de précaution. La raison en est que tant les briques techniques utilisées, que les personnes impliquées dans le fonctionnement d’un système d’IA sont nombreuses, variées et en interactions complexes, entraînant de nombreuses interactions qui ne sont pas aisées à maîtriser. Il convient de constater que le groupe d’experts de haut niveau formule un ensemble de propositions, à visées d’éthique et de robustesse technique des systèmes d’IA, qui véhiculent l’idée selon laquelle la confiance en un système d’IA, au regard des risques actuels du déploiement de ceux-ci, se doit de reposer sur une responsabilisation a priori de la gouvernance de celui-ci tout au long de son cycle de vie, qui passe, entre autres choses, par un objectif d’explicabilité de ces actions.

La notion d’accountability est à cet égard une notion centrale pour comprendre la complémentarité et le long continuum existant entre responsabilisation et responsabilité. Plus que par le terme de responsabilité, cette notion d’accountability peut justement être traduite par les notions de reddition de compte et/ou de responsabilisation. Cette responsabilisation permet d’envisager les risques-données et les risques-algorithmiques, de manière conjointe, préservant ainsi la spécificité de chacun de ces risques, mais en les reliant, parce c’est par la conjonction de ces deux types de risques, que des conséquences préjudiciables pour l’humain ou la société peuvent se réaliser.

En résumé. Le point de vue juridique différera selon les enjeux et les concepts applicables. Dans le cas de la blockchain, il est important de séparer le risque-données du risque-algorithmes puisqu’ils traitent de problématiques différentes et nécessitent des cadres de loi différents. Le premier traite de la question de la divulgation de l’identité des parties qui relève de la sécurité des données alors que le second traite de la question des actifs numériques frauduleux. Dans le cas des systèmes d’intelligence artificielle, tout déprendra du point de savoir s’il convient de prévenir le dommage ou de le sanctionner une fois qu’il s’est réalisé. Dans le cas d’une recherche de responsabilisation, il convient d’envisager les risques-données et les risques-algorithmes de manière conjointe.

Si la question est celle de la responsabilité (liability) et la responsabilisation (accountability), i.e., celle d’imputer la faute à une personne physique, il sera important de séparer les deux risques. Cette séparation est aussi celle qui est préconisée en informatique pour permettre d’identifier les “coupables”: données ou algorithmes. Les techniques de provenance des données et de trace algorithmique permettront d’isoler les raisons pour lesquelles il y a faute. Il s’agira d’abord d’identifier si la faute est due à un risque-données du type divulgation de la vie privée ou à un biais statistique dans les données, ou à un risque-algorithmes du type économique ou cognitif, ou si la faute est due aux deux. On ne pourra donc imputer la faute et déterminer les cadres de loi applicables que s’il y a séparation. De même si l’objectif est de “réparer” les données ou l’algorithme, l’étude des deux types de risque doit s’effectuer séparément. C’est ce qu’on appelle l’orthogonalité en informatique. Selon le dictionnaire, le jeu d’instructions d’un ordinateur est dit orthogonal lorsque (presque) toutes les instructions peuvent s’appliquer à tous les types de données. Un jeu d’instruction orthogonal simplifie la tâche du compilateur puisqu’il y a moins de cas particuliers à traiter : les opérations peuvent être appliquées telles quelles à n’importe quel type de donnée. Dans notre contexte, cela se traduirait par avoir un jeu de données parfait et voir comment l’algorithme se comporte pour déterminer s’il y a un risque-algorithmes et avoir un algorithme parfait et examiner les résultats appliqués à un jeu de données pour déterminer le risque-données. Ces stratégies ont de beaux jours devant elles.

Sihem Amer-Yahia (DR CNRS INS2I, Univ. Grenoble-Alpes)
Amélie Favreau (MdC Droit Privé, Univ. Grenoble-Alpes)
Juliette Sénéchal (MdC Droit Privé, Univ. de Lille)

Publié le

Le divulgâcheur : une nouvelle rubrique dont vous pouvez être le héros !

L’informatique est rentrée dans toutes les facettes de nos vies, y compris les toiles sur lesquelles nous regardons films et séries. Parfois même, nous y voyons des scènes où l’utilisation des outils informatiques nous questionne, parce que non conventionnelle à l’écran. Aussi nous vous proposons une nouvelle rubrique, dans laquelle nous inviterons des experts, pour décoder certaines scènes où le numérique joue un rôle important, en nous expliquant ce qui se passe, ce qui est crédible, ce qui l’est moins. Il ne s’agit en aucun cas de singer un rôle de critique sur la qualité de la scène mais bien d’utiliser cet angle pour parler – encore et toujours – du numérique. Et vous pouvez nous aider ! Charlotte Truchet et Pascal Guitton.

Binairiens, binairiennes !

En ce début d’année, nous avons une nouvelle à partager avec vous. L’équipe éditoriale s’étant creusé la tête pour trouver des façons toujours plus vivantes de vous faire découvrir le monde merveilleux de la science informatique, ce blog va bientôt inaugurer une toute nouvelle rubrique, pour laquelle nous allons avoir besoin de vous, lectrices et lecteurs !

Nous avons intitulé cette série : le divulgâcheur.

Traduit en anglais, ce joli mot devient « spoiler ». « Et c’est quoi le rapport avec l’informatique ? », direz-vous, car vous êtes des lecteurs et lectrices pointilleux. Et bien, pendant des années, des décennies même, l’informatique montrée à l’écran était souvent ridiculement caricaturale. On avait souvent affaire à un gamin en hoodie tapant frénétiquement du code HTML écrit en vert sur fond noir dans un sous-sol cradingue, ou alors à un policier interrogeant des bases de données omniscientes sur un terminal à petit écran (voir par exemple ici une drôle de liste de références !). Mais à Binaire, nous avons ressenti que plusieurs séries récentes, par exemple Black Mirror, The Good Wife, ou Le Bureau des Légendes, traitaient de vraies questions informatiques, de façon assez travaillée, voire réaliste.

Réaliste, certes, mais à quel point ? C’est ce que le Divulgâcheur va vous révéler. Dans chaque épisode de notre rubrique, nous inviterons un.e chercheur.euse en informatique à décoder pour nous une scène de série montrant un usage informatique non conventionnel, et à nous en livrer les clefs.

« Mais vous allez nous spoiler, alors ?!!! » direz-vous car vous êtes des lectrices et lecteurs exigeants. Hé oui, d’où le titre de la rubrique. Si vous souhaitez garder le plaisir de la découverte de vos séries favorites, il sera prudent de regarder les épisodes avant de nous lire. Le numéro de l’épisode concerné sera toujours indiqué clairement, c’est promis.

« Mais si je n’aime pas le Bureau des Légendes ? », demanderez-vous, car tout pointilleux et exigeants que vous êtes, vous avez aussi le droit d’avoir mauvais goût 😉 . C’est justement le but de ce petit texte : nous comptons sur vous pour nous proposer des épisodes à traiter ! Plus précisément, voilà ce que nous cherchons :

=> Une scène d’une série, ou d’un film, qui soit basée sur un usage non conventionnel du numérique : pour que l’exercice soit intéressant, il faut que l’informatique soit partie intégrante du scenario et pas juste un élément de décor,

=> idéalement, plutôt de séries ou de films récents,

=> non, pas que Black Mirror ; nous avons déjà un épisode dans les tuyaux et on ne fera pas que des épisodes de Black Mirror !

Laissez-nous en commentaire le nom de la série, le numéro exact de l’épisode (ou le titre du film), et une courte description de la scène considérée. Nous nous engageons alors à essayer de trouver un.e expert.e pour décrypter la scène. Nous n’y arriverons peut-être pas toujours, mais nous essaierons !

Alors, à vous !

L’équipe Binaire

Publié le

Raconte-moi un algorithme : ça va être long ?

En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau

Février : Ça va être long ?

 

Si vous installez parfois des logiciels, vous avez forcément remarqué que la petite barre qui vous indique le temps restant est franchement mensongère. Elle semble avancer à sa guise, sans aucun rapport avec le temps écoulé, ou restant à écouler… Connaître le temps qu’un programme met à s’exécuter, ce n’est pourtant pas beaucoup demander ! En fait, si. Et en gros, à la louche, à peu près, en moyenne ? Même. Et même en faisant abstraction des performances des matériels utilisés, connaître le temps d’exécution d’un algorithme est un problème difficile – souvent insoluble en l’état actuel des connaissances. Bien souvent, on donne la complexité dans le pire des cas d’un algorithme, c’est-à-dire le temps de calcul théorique d’un algorithme sur la pire entrée possible, celle qui lui prendra le plus de temps à s’exécuter. On s’intéresse aussi beaucoup au temps de calcul en moyenne sur toutes les entrées possibles, qui est encore plus difficile à calculer. Et puis, pour résoudre un problème, il existe typiquement plusieurs algorithmes. Alors, savoir combien il faudrait de temps pour résoudre un problème particulier, c’est encore plus compliqué.

Parmi les algorithmes les plus étudiés, on trouve les algorithmes de tri, qui partent d’une suite d’objets non triés et s’occupent de la ranger dans un ordre bien défini. Il en existe de nombreux, aux noms poétiques : tri à bulles, tri par insertion, tri rapide… C’est une des rares familles d’algorithmes dont on connaît bien le temps théorique d’exécution, que ce soit dans le pire des cas ou en moyenne. Le tri par sélection, par exemple, fonctionne de manière très simple : on cherche la plus petite valeur à trier et on la met devant. Puis on cherche la deuxième plus petite dans ce qui reste, et on la met en deuxième, etc. Simple, mais pas terrible en complexité ! Pour n valeurs à trier, il faut lire une fois toutes les données pour trouver la plus petite valeur, ce qui coûte n opérations, pour la seconde, n-1, etc. Au total, on a de l’ordre de n2 opérations à faire dans le pire des cas comme en moyenne.

Le tri rapide, ou quicksort, est plus compliqué à comprendre mais plus efficace : on choisit arbitrairement une valeur dans les données à trier, et on met d’un côté toutes les valeurs plus petites, de l’autre toutes les plus grandes. Ça semble farfelu, c’est pourtant très astucieux : on se retrouve avec deux suites de données beaucoup plus petites à trier! Et on reprend sur ces deux suites. La complexité passe à n*log(n), ce qui représente un gain significatif en temps de calcul.

En général, on connaît la complexité dans le pire des cas de beaucoup d’algorithmes courants, beaucoup plus rarement la complexité en moyenne. Il reste beaucoup à apprendre.

Serge Abiteboul et Charlotte Truchet