Publié le

Nook, robot de bridge

On sait que les algorithmes permettent de fournir des mécanismes qui gagnent contre les humains aux jeu d’échecs ou à des jeux plus complexes comme le jeu de go … mais qu’en est-il du jeu de bridge ? Ce jeu,  au-delà de la combinatoire, laisse une place importante aux interactions humaines. Le robot de bridge, Nook, développé par NukkAI se positionne au meilleur niveau grâce à la combinaison de l’IA symbolique et de l’IA numérique. Marie-Christine Rousset nous explique comment ça marche, et s’appuie sur cet exemple pour nous permettre de mieux comprendre l’Intelligence Artificielle. Les explications de l’IA sont souvent simplistes. Marie-Christine nous conduit un peu plus loin dans la technique dans des termes que nous pensons compréhensibles pour tous. Serge Abiteboul et Thierry Viéville.

Le bridge est un jeu de cartes dans lequel une équipe de 2 joueurs essaie d’atteindre un objectif commun appelé un « contrat » déterminé au cours de la phase des enchères. Réaliser un contrat consiste à faire au moins un certain nombre de plis face à une équipe adverse qui va collaborer selon des règles codifiées pour essayer de faire chuter le contrat.

Jeu de bridge avec la boîte d’enchères qui montrent les deux facettes de ce jeu. ©Marie-Lan Nguyen wikicommon

 

À la différence des jeux de plateaux comme les échecs ou le go, le bridge est un jeu à information incomplète. Au départ, chaque joueur ne connaît que les 13 cartes qu’il a en main. Au cours de la partie, en raisonnant sur les informations transmises pendant la phase des enchères et sur les cartes jouées à chaque pli, chaque joueur peut restreindre ses hypothèses sur les cartes restant en jeu mais il doit prendre ses décisions (choisir la carte à jouer à chaque pli) sans la connaissance complète des cartes restant en main de son partenaire ou de ses adversaires.

Bien jouer au bridge implique de maîtriser différents types de compétences :

  • Faire des déductions (si tel joueur a joué telle séquence de coups, il a ou n’a pas telle carte) ;
  • Émettre et réviser des hypothèses (tel adversaire a au moins 5 cartes à Pique ou n’a plus de cartes à Cœur) ;
  • Anticiper un certain nombre de coups probables de l’équipe adverse ; et
  • Évaluer les probabilités des différentes mains adverses possibles pour guider la prise de risque et calculer l’espérance de gain des coups à jouer.

L’intelligence artificielle de Nook, en tirant parti de la force combinée d’approches d’IA symbolique et de techniques d’IA numérique, a réussi à surpasser le niveau de 8 champions de bridge de niveau mondial sur plusieurs centaines de parties avec le même contrat à réaliser (3 Sans Atout).  Pour une juste comparaison entre Nook et les joueurs humains, Nook et chaque champion ont joué les mêmes jeux, dans la même position de déclarant, contre deux robots Wbridge5 constituant l’équipe adverse. Wbridge5 (développé par Yves Costel) est multi champion du monde des robots de bridge dans le cadre de compétitions opposant uniquement des robots. Comme le montre la photo suivante, chaque champion humain (tout comme Nook)  joue avec son jeu (caché)  et le jeu de son partenaire (qui fait le “mort”) visible de tous, contre deux adversaires ici simulés par Wbridge5 paramétré en position de défenseur. 

A la différence de jeux à information complète (comme les échecs ou le go), dans un arbre de jeu (voir Encart 1) pour le bridge les coups adverses possibles en riposte au choix d’un coup par le robot (à partir d’un nœud Max de l’arbre de jeu) dépendent des cartes des mains adverse, qui ne sont pas connues par le robot. Pour chaque nœud Min de l’arbre (c’est-à-dire un nœud qui modélise les ripostes des adversaires), Il faut donc générer des mondes possibles (les mains possibles des adversaires), et pour chacun explorer les ripostes les plus probables des adversaires à la carte jouée par le robot.

La force de Nook est d’explorer de façon intelligente un arbre de jeu avec des mondes possibles en s’appuyant sur quatre techniques complémentaires :

  • Raisonnement automatique sur des règles ;
  • Apprentissage automatique à partir d’un échantillon de parties déjà jouées afin d’apprendre la stratégie des adversaires ;
  • Génération aléatoire de mondes possibles de type Monte Carlo (Encart1) contrainte par les règles du domaine et les modèles de l’adversaire ; et
  • Recherche arborescente de type MinMax avec élagage Alpha-Beta (Encart 2)  dans chaque monde possible en exploitant les modèles des différents joueurs.

Plus précisément, l’algorithme d’exploration de l’arbre de jeu des mondes possibles de Nook est une extension de l’algorithme AlphaMu [1] développé par Tristan Cazenave et Véronique Ventos (et optimisé dans [2]). A chaque étape du jeu, l’algorithme génère différents mondes possibles aléatoirement (voir Encart 1) tout en vérifiant leur compatibilité avec les contraintes inférées par règles et par les modèles de l’adversaire observés ou appris. Dans chacun des mondes possibles, les différents coups possibles sont évalués par un algorithme MinMax (voir Encart 2) rendu très sélectif par l’exploitation des modèles de l’adversaire.

Certains modèles de joueurs sont des réseaux de neurones qui ont été entrainés à leur tâche spécifique de façon automatique (Voir Encart 3). Les données d’entraînement sont obtenues à partir de centaines de milliers de parties jouées par WBridge5 contre lui-même. Le réseau de neurones utilisé, de type ResNet, n’est pas très gros, et la taille de l’ensemble des données d’entraînement est raisonnable. De ce fait, l’étape d’entraînement, réalisée sur l’ordinateur Jean Zay du CNRS, a demandé 200.000 fois moins de ressources de calcul que l’entraînement du réseau de neurones utilisé dans AlphaGo de DeepMind, qui a battu le maître de jeu de Go Lee Sedol en 2016.

Le raisonnement automatique sur des règles est la clef pour restreindre la combinatoire et expliquer les décisions. Les règles fournies à Nook modélisent les connaissances d’un joueur de bridge, pour inférer, à partir de la séquence des enchères, des contraintes positives ou négatives sur les mains des différents joueurs. Par exemple, une enchère “2 Sans Atout”du partenaire après une ouverture “1 Sans Atout” suivi de Passe de l’adversaire implique que le partenaire a une distribution régulière ou  moins de 5 cartes à Coeur ou à Pique . D’autres règles décrivent comment l’adversaire choisit la première carte (Module d’entame). 

Ces règles sont interprétables par les humains (car exprimées avec des concepts qui font sens pour des joueurs comme  « distribution régulière ») et exploitables par la machine à qui on a fourni le lien entre ces concepts abstraits et des distributions concrètes de mains. A partir de la connaissance abstraite et inférée qu’une main a une distribution régulière, on peut générer automatiquement toutes les mains concrètes correspondantes (et leurs probabilités) en fonction des cartes que l’on a dans sa propre main et, au fur et à mesure de la partie, des cartes jouées par les différents joueurs.

On comprend donc bien l’intérêt des règles pour restreindre au fil du temps les mondes possibles et ainsi guider la génération aléatoire au cœur de l’exploration arborescente de type Monte Carlo (voir Encart 1).

L’autre intérêt de ces règles est qu’elles peuvent être utilisées pour expliquer, à tout moment de la partie, la vision à haut niveau et probabiliste des mains cachées des adversaires. En effet, au bridge, répondre à des questions du type « pourquoi avoir joué cette carte ? » fait partie des règles de bonne conduite pour vérifier en particulier qu’il n’y a pas de tricherie de la part d’un joueur ou qu’un coup n’est pas juste un coup de chance. Le bridge n’est pas le poker …

Conclusion

Même si Nook ne joue pour l’instant qu’une partie des « contrats » existants au bridge (le « trois sans-atout »), ses concepteurs ont d’ores et déjà prouvé le bénéfice d’une IA « hybride » qui lui donne notamment la possibilité d’expliquer ses choix. Cette nouvelle approche, que NukkAI envisage de déployer dans d’autres domaines comme la cybersécurité, l’éducation ou les transports,  ouvre une voie pour avoir « quelque chose qui ressemble plus à de l’intelligence que ce que l’on a vu ces dernières années »,  souligne Cédric Villani, auteur d’un rapport parlementaire qui en 2018 avait inspiré la stratégie du gouvernement français sur l’intelligence artificielle, venu observer le défi en direct.  « Nous ne visons pas une intelligence artificielle qui remplace l’humain, mais qui collabore et où l’humain garde toujours la maîtrise » revendiquent Jean-Baptiste Fantin et Véronique Ventos, les deux créateurs de NukkAI. 

Marie-Christine Rousset, professeure d’informatique à l’université Grenoble Alpes

Encart 1 : Exploration arborescente Monte Carlo.L’exploration arborescente est à la base de la plupart des algorithmes utilisés pour les programmes de jeux à deux joueurs. Il s’agit de générer récursivement un arbre de jeu qui modélise,  à partir de la situation de jeu initiale, les différents coups possibles et pour chacun d’eux les ripostes possibles, jusqu’à atteindre les fins de partie (qui peuvent être gagnantes ou perdantes). Un chemin dans cet arbre représente une partie complète dont on peut donc savoir si elle est gagnante pour l’un des 2 joueurs (et perdante pour l’autre joueur).  L’arbre de jeu complet est trop gros pour être construit en entier sauf pour des jeux très simples comme le tic tac toe. Une exploration de type Monte Carlo consiste à casser la combinatoire en n’explorant qu’un certain nombre de chemins qui sont construits en générant aléatoirement un nombre restreint de coups possibles à chaque étape de la simulation. 
 Encart 2 : Algorithme MinMax et élagage Alpha-BetaL’algorithme MinMax  prend le point de vue d’un des joueurs qui, dans une situation de jeu donnée, doit choisir le coup qui maximise ses chances de gagner, sans connaître la stratégie de l’adversaire mais en supposant que cet adversaire, quand c’est à son tour de jouer, choisit systématiquement les ripostes qui maximisent ses propres chances et donc minimisent les chances de gagner du premier joueur.  A partir de chaque situation de jeu, l’algorithme développe l’arbre de jeu jusqu’à une certaine profondeur, donnée en paramètre. Pour chaque situation de jeu du niveau le plus profond, à l’aide d’une fonction d’évaluation qui lui est fournie et qui dépend de chaque jeu, il calcule une valeur qui est une estimation des chances de gagner à partir de cette situation. Il calcule ensuite la valeur de la racine de façon récursive en faisant remonter le minimum des valeurs du niveau inférieur pour les nœuds Min où c’est à l’adversaire de jouer, et le maximum des valeurs du niveau inférieur pour les nœuds Max où c’est à l’algorithme de jouer. L’algorithme choisit alors le coup qui maximise la valeur de la racine. Plus la fonction d’évaluation est appliquée loin de la racine, c’est-à-dire plus on anticipe de coups successifs, plus fine est l’estimation du meilleur coup à jouer.

L’algorithme MinMax effectue une exploration complète de l’arbre de recherche jusqu’à un niveau donné. L’élagage Alpha-Beta permet d’optimiser l’algorithme Minmax en ne réalisant qu’une exploration partielle de l’arbre de jeu, tout en obtenant la même valeur comme résultat pour la racine. Au cours de l’exploration, deux types d’élagage peuvent être effectués : des coupes alpha qui évitent d’examiner des sous-arbres d’un nœud Min dont la valeur courante est inférieure à la valeur courante d’un nœud Max au dessus dans l’arbre ; et des coupes beta qui élaguent les sous-arbres d’un nœud Max dont la valeur courante est supérieure à la valeur courante d’un nœud Min au dessus dans l’arbre. On peut montrer que ces contraintes garantissent que les sous-arbres ainsi élagués conduiraient à des configurations dont la valeur ne contribuerait pas au calcul du gain à la racine de l’arbre.
Encart 3 : Apprentissage automatique de réseaux de neurones L’apprentissage profond est un ensemble de techniques d’apprentissage automatique qui s’appuient sur des réseaux de neurones artificiels pour modéliser le calcul d’un résultat en fonction d’une entrée. Un réseau de neurones est une composition de couches composées de neurones formels qui constituent les entités élémentaires de calcul dans ce modèle. Chaque neurone prend en entrée des sorties des neurones des couches précédentes, calcule une somme pondérée (par des poids dits synaptiques) de ses entrées puis passe cette valeur à une fonction d’activation pour produire sa sortie.

 Les différents types de réseaux de neurones varient selon la structure, le nombre de couches et les fonctions d’activation considérées. Les plus étudiés sont les perceptrons multi-couches, les réseaux de neurones convolutifs, et les réseaux résiduels (ResNet). 

Le  point commun de tous les réseaux de neurones artificiels est que les poids synaptiques qui sont déterminants dans le calcul effectué par chaque neurones sont optimisés (on dit souvent qu’ils sont « appris ») à partir d’exemples étiquetés, c’est-à-dire d’entrées pour lesquelles on connaît le résultat. L’apprentissage des meilleurs poids se fait en itérant des étapes de rétropropagation du gradient de l’erreur, qui consiste à corriger les erreurs effectuées à une étape en modifiant les poids synaptiques des neurones en fonction de  leur importance dans la réalisation de l’erreur.

Références et footnote:

(*) NukkAI (https://nukk.ai/) est un laboratoire privé d’Intelligence Artificielle créé par Véronique Ventos, chercheuse en IA, Maitre de Conférences en disponibilité à l’Université Paris-Saclay, et Jean-Baptiste Fantun, ancien élève de l’Ecole Polytechnique, agrégé de Mathématiques et titulaire d’un master en IA.

[1] The AlphaMu Search Algorithm for the Game of Bridge. Tristan Cazenave et Véronique Ventos. in Monte Carlo Search at IJCAI, 2020.

[2] Optimizing AlphaMu. Tristan Cazenave, Swann Legras et Véronique Ventos. in IEEE Conference on Games (CoG), August 17-20, 2021

Pour aller plus loin :
– https://interstices.info/programmation-des-echecs-et-dautres-jeux qui explique comment fonctionne d’autres jeux avec des joueurs algorithmiques
– https://interstices.info/le-jeu-de-go-et-la-revolution-de-monte-carlo qui explique comment la méthode de Monte-Carlo s’applique au jeu de go
– https://interstices.info/lapprentissage-profond-une-idee-a-creuser qui présente le fonctionnement des réseaux de neurones

Publié le

Please, ne traquez pas mon smartphone ?

Voici un article consacré au Prix de thèse Gilles Kahn qui depuis 1998 récompense chaque année une thèse en Informatique. Cette année l’un des accessit revient à Charlie Jacomme pour ses travaux. Charlie nous parle des enjeux de la preuve des propriétés de sécurité et derrière celles-ci de la protection de la vie privée.  Pierre Paradinas.

« Peut-on prouver que personne ne peut me traquer via mon smartphone ? » La réponse est tristement simple. Non, comme le démontrent de nombreux exemples comme le flicage de   Ouïghours via leurs smartphones par les autorités chinoises, ou encore l’exploitation par la police Allemande, sans contrôle judiciaire, des informations de localisations tirées d’une application de traçage de la Covid-19.

Tout n’est pourtant pas perdu, car même s’il existe de nombreuses attaques possibles aujourd’hui, des personnes essayent de les éviter en créant des systèmes sécurisés et respectueux de la vie privée. Cependant, inventer de tels systèmes est difficile et on finit par trouver qu’on a laissé des failles.

Pour rendre plus facile la conception de tels systèmes et obtenir de véritables garanties, le domaine des méthodes formelles en sécurité propose des techniques permettant de prouver la sécurité d’un système. On obtient ainsi une preuve mathématique que le système est sécurisé. Cependant, cette tache est difficile car prouver la sécurité revient à prouver qu’aucune attaque n’est possible : on veut démontrer l’impossible. Et par ailleurs, on souhaite démontrer cela sur des systèmes très complexes et pour des attaquants aussi puissants (mais réalistes) que possible.

Le logo du logiciel Squirel

Le but principal de ma thèse a été de simplifier la tache de réaliser des preuves de sécurités. Pour ce faire, j’ai par exemple développé un programme informatique en accès libre, appelé le Squirrel Prover, qui permet de se faire aider par un ordinateur pour construire des preuves de sécurités. On écrit toujours la preuve soi-même, mais un ordinateur aide,  guide, et au final  confirme que la preuve est correcte. J’ai aussi travaillé sur la modularité des preuves, en développant des résultats qui permette de découper les preuves en morceaux indépendants. Et depuis la fin de ma thèse, j’essaie d’appliquer ces techniques pour vérifier concrètement la sécurité des systèmes que nous utilisons tous les jours.

Malheureusement, et comme je l’ai illustré par des exemples en introduction, la plupart des systèmes que nous utilisons aujourd’hui ne sont pas sécurisés. Ainsi, même si on peut inventer et prouver des systèmes véritablement respectueux de la vie privée, il reste un défi majeur : il faut que ces systèmes soient utilisés et déployés par les gouvernements et les entreprises. Et ça, cela nous fait sortir du monde de la recherche…

Charlie Jacomme, Laboratoire Méthodes Formelles (LMF), actuellement en post-doc au CISPA, à Saarbrucken.

 

Publié le

Corriger les failles informatiques, une impossible exhaustivité à gérer comme un risque !

Dans le domaine de la cybersécurité, il existe de nombreuses phases du développement et du déploiement des systèmes logiciels qui sont sensibles. A l’occasion de la publication d’un rapport du NIST, c’est aux failles logicielles et à leurs correctifs que nous nous intéressons. Trois experts, Charles Cuvelliez, Jean-Jacques Quisquater & Bram Somers nous expliquent les principaux problèmes évoqués dans ce rapport. Pascal Guitton.

Tous les jours, des failles sur les logiciels sont annoncées par leurs éditeurs, dès lors qu’un correctif est disponible. Plus rarement, la faille n’est pas découverte en interne chez l’éditeur ou ni même de façon externe, par un chercheur ; elle l’est alors d’une part par des hackers malveillants qui se gardent bien d’en faire la publicité mais les dégâts causés par leur exploitation la font vite connaître. D’autre part, par les services secrets de certains pays qui les apprécient beaucoup pour réaliser des attaques plus furtives.

Le volume des failles à traiter quotidiennement devient de plus en plus souvent ingérable pour les entreprises. Parfois l’éditeur du logiciel ne supporte même plus la version pour laquelle une vulnérabilité a été découverte : il n’y aura pas de correctif. Appliquer un correctif peut demander du temps, nécessiter la mise à l’arrêt des équipements, leur redémarrage, le temps de l’installer. Cette indisponibilité est parfois incompatible avec l’utilisation d’un logiciel qui doit fonctionner en permanence : un correctif ne s’applique pas n’importe quand. Dans des cas plus rares, le correctif ne peut être appliqué que par le fabricant, pour des raisons de conformité ou de certification.

Le risque zéro n’existe pas pour la sécurité des logiciels, ; dès qu’on installe un logiciel, il y a un risque de faille.  C’est l’approche suivie par le NIST dans son standard (Guide to Enterprise Patch Management Planning : Preventive Maintenance for Technology) qui vient d’être publié il y a peu.

Couverture du rapport du NIST

Si on ne peut ou ne veut pas appliquer de correctif, on peut désactiver le logiciel ou le module dans laquelle la faille a été identifiée. On peut installer une version plus récente du logiciel mais avec un autre risque : que ce dernier fonctionne différemment et perturbe toute la chaîne opérationnelle au sein de laquelle il est un maillon. On peut isoler le logiciel pour qu’aucune personne extérieure ne puisse l’atteindre en vue d’exploiter la faille (en segmentant le réseau et en le plaçant dans un segment sûr). On peut même décider que l’impact – si la faille est exploitée – est minime : on accepte alors le risque (ce n’est tout de même pas conseillé). On peut aussi confier le logiciel à un fournisseur à qui incombera la responsabilité de gérer les correctifs.

Un véritable cycle

Si on décide d’installer le correctif, c’est tout un cycle qui démarre et qui ne se réduit pas à le télécharger et à l’installer d’un clic comme on le pense souvent. Il faut chercher où, dans l’organisation, le logiciel est installé. Cela commence par détenir l’inventaire des logiciels dans son entreprise, qui n’est correct que si on connait parfaitement toutes les machines installées. D’ailleurs ce ne sont pas toujours les logiciels d’une machine qu’on doit mettre à jour, c’est parfois la machine elle-même et son système d’exploitation. Dans le cas de l’Internet des objets, la situation se complique : on peut quasiment toujours mettre à jour le firmware de ces derniers mais la tâche est immense : où sont-ils sur le terrain ? Comment les mettre à jour tous sans en oublier un ? Faut-il envoyer des techniciens sur place ? Combien de temps faudra-t-il pour tous les mettre à jour ?  Il peut même arriver qu’on doive passer à une nouvelle mise à jour alors l’ancienne n’est pas terminée pour tous les objets, au risque donc de désynchronisation de l’ensemble.

Si on a pu installer le correctif, après avoir planifié son déploiement, l’avoir testé pour voir si le programme qu’on utilisait fonctionne toujours correctement comme avant, il faut observer le programme mis à jour : le correctif peut lui-même receler une faille (car il est souvent développé dans l’urgence) ou avoir été compromis par un hacker (ce sont les fameuses attaques dites supply chain). Par erreur, un utilisateur peut désinstaller la mise à jour, réinstaller la version précédente, lors par exemple d’une restauration d’une sauvegarde. Si on a opté pour éteindre la machine ou le logiciel car on ne peut appliquer de correctif, il faut aussi surveiller que personne ne la/le redémarre. Un correctif peut par erreur remettre à zéro la configuration du programme qui l’intègrera, y compris les réglages de sécurité.

Toutes ces opérations ne s’organisent pas à la dernière minute, lorsqu’une faille critique est annoncée.

Sécuriser les environnements

On peut mettre en place un environnement plus sûr de sorte qu’une faille y ait moins d’impact ou n’y trouve pas de terrain favorable. Cela commence par ne mettre à disposition les logiciels qu’aux personnes qui en ont vraiment besoin. De deux logiciels équivalents, on peut privilégier celui qui a un historique plus favorable en nombre (réduit) de failles. On peut vérifier la rigueur du développement, la fréquence des correctifs, leur nombre, les problèmes relayés par les communautés d’utilisateurs à propos des failles. On peut aussi installer ses logiciels dans des environnements plus favorables et plus faciles à l’application de correctifs comme les containers cloud.

Dans son rapport, le NIST distingue quatre réponses aux failles : l’application de correctifs au fil de l’eau, en respectant un planning et des contraintes comme le week-end pour les logiciels dont on ne peut tolérer l’interruption. Il y a les correctifs à appliquer d’urgence. Si un correctif n’existe pas (encore), ce sont des mesures d’atténuation qu’on appliquera en fonction des instructions du fournisseur. Si le fournisseur n’apporte plus de support, il faudra isoler la machine qui héberge le logiciel pour le rendre inatteignable sauf par ses utilisateurs, si on ne peut s’en passer.

Que faire face à cette complexité ? Le NIST propose de classer les actifs informatiques dans des groupes de maintenance. Appliquer un correctif ou gérer une faille, c’est de la maintenance de sécurité. Chaque groupe de maintenance aura sa politique de gestion des failles.

Et de citer comme groupe de maintenance les ordinateurs portables des employés où les failles et les correctifs ont trait au système d’exploitation même de la machine, les firmwares et autres programmes installés. Les portables des utilisateurs ont une plus grande tolérance à une interruption et l’impact est limité si un ordinateur subit une faille puisqu’il y a des logiciels de contrôle et d’alerte à la moindre infection qui tourne sur ces machines puissantes. Ces éléments permettent une politique de mise à jour des failles adaptée.

A l’autre extrême, on trouve le groupe de maintenance « serveur de données (data center) » qui ne peut tolérer quasiment aucune interruption, qui ne peut être mis à l’arrêt qu’à des moments planifiés longuement à l’avance. Les mesures d’atténuation du risque sont tout autre, la défense en profondeur, les protections mises en place dans le réseau, la segmentation.

Autre exemple : le groupe de maintenance liés aux tablettes et autres smartphones utilisés par les employés, avec, aussi, sa tolérance aux interruptions, ses mesures propres de protection… Avoir une politique de mise à jour et de correction des failles par groupe de maintenance évite le goulot d’étranglement de tout vouloir faire en même temps et au final de laisser des failles béantes, peut-être critiques.

Le déploiement des correctifs.

Le NIST propose de déployer le correctif par groupes d’utilisateurs pour voir si tout se déroule correctement, puis de l’étendre graduellement pour limiter l’impact d’un correctif qui ne serait pas au point. Le déploiement progressif peut se faire en fonction de la qualification des utilisateurs, de leur compétence. Même pour les correctifs à appliquer d’urgence, le NIST propose ce déploiement graduel (mais plus rapide, en heures, sinon en minutes plutôt qu’en jours).

S’il n’y pas de correctifs disponibles, on est dans les mesures d’atténuation, comme isoler le logiciel quand on ne peut pas s’en passer, migrer dans un segment la machine qui le contient, adapter les droits d’accès des utilisateurs : on parle de micro-segmentation ou de « software-defined perimeters ». Tout ceci ne se fait pas le jour où l’entreprise fait face pour la première fois à un logiciel qui n’aura (plus) jamais de correctif. Les architectes doivent avoir réfléchi et proposé à l’avance les bonnes politiques et manière de faire. Il faut d’ailleurs les réévaluer en permanence car le réseau évolue : le risque est-il bien limité et le reste-t-il avec cette architecture ?

Oublier qu’il y a là une partie du réseau qui héberge les cas à problèmes serait la pire chose à faire. Il faut aussi interpeller les utilisateurs à intervalles réguliers pour voir s’ils utilisent vraiment ce logiciel vulnérable ? Peut-on se permettre de garder un trou de sécurité ? N’y a-t-il pas une alternative sur le marché ?

Métrique

L’organisation et sa direction doivent pouvoir vérifier que la politique d’application des correctifs est efficace. Mesurer et affirmer que 10 % des machines ou des logiciels n’ont pas pu recevoir des correctifs n’apporte aucune information si ce n’est faire peur car on imagine ces 10 % des machines ouvertes à tout vent.

Le NIST propose de donner trois indicateurs : la proportion de correctifs appliqués à temps par rapport à un objectif fixé, le temps moyen et le temps médian d’application du correctif (qui doivent bien sûr être inférieur à l‘objectif). Cet objectif peut être fixé par groupe de maintenance ou selon la criticité de la vulnérabilité et l’importance du logiciel dans le fonctionnement de l’entreprise.

En fin de compte, le mieux est d’acquérir un logiciel qui connaitra le moins de failles possibles : il faut mener, dit le NIST, une véritable due diligence avec le fournisseur : combien de failles, combien par année ? Combien de temps pour produire un correctif quand une faille est trouvée ? Les correctifs sont-ils groupés ? Publiez-vous les correctifs sur la base de données des vulnérabilités CVE ? Publiez-vous les correctifs ad hoc ou à intervalles réguliers ? Cela vous arrive-t-il de ne pas publier des correctifs mais d’alors proposer des mesures d’évitement ? Vos correctifs ont-ils déjà créé des problèmes ? Testez-vous les correctifs avant de les publier ? Quel est le retour de vos clients ?

Les réponses à ces questions en diront long sur le sérieux du fournisseur.

Charles Cuvelliez (Ecole Polytechnique de Bruxelles, Université de Bruxelles), Jean-Jacques Quisquater (Ecole Polytechnique de Louvain, Université de Louvain) & Bram Somers (Group Chief Technology Officer, Belfius Banque)

Publié le

Générer des modèles 3D à partir d’une photographie : le papier-mâché par ordinateur

Voici un autre article consacré au Prix de thèse Gilles Kahn qui depuis 1998 récompense chaque année une thèse en Informatique. Cette année l’un des accessit revient à Thibault Groueix pour ses travaux qui nous emmènent dans les images 2D/3D et leurs interprétations via de l’IA. Pierre Paradinas.

Les algorithmes de génération ou d’analyse d’image ont connu un boom au cours des dix dernières années – et ils continuent toujours de s’améliorer, sans qu’aucune limite de saturation ne se dessine quant à leurs performances ni leurs champs d’application. Ainsi, un ordinateur peut facilement indiquer si une image contient un chien ou un chat, et identifier les pixels concernés. Plus spectaculairement, en combinaison avec de l’analyse de texte, des approches comme DALL-E 2 permettent aujourd’hui de générer des images à partir de simples phrases.

De tels algorithmes sont basés sur des réseaux de neurones, mais dans quelle mesure ces réseaux « comprennent”-ils vraiment les images? Par exemple, sont-ils capables de saisir la 3D sous-jacente dans une photo 2D “plate”?  C’est sur cette question que portent mes travaux de recherche. Notre cerveau possède intrinsèquement cette incroyable faculté: à partir de projections 2D de rayons lumineux sur la rétine, il peut instantanément reconstruire une représentation mentale 3D du monde et des objets. En analyse d’image par ordinateur, reconstruire la 3D à partir d’une seule image est un Graal. C’est un problème ouvert depuis près de 60 ans.

C’est un problème difficile pour trois raisons. D’une part par manque de base de données d’apprentissage adéquate. D’autre part, les méthodes développées pour générer et analyser des images 2D reposent sur l’ordonnancement et la régularité des grilles de pixels, et ne se transpose pas facilement au domaine de la 3D par le simple ajout d’une dimension car cela est trop coûteux en mémoire. Enfin, parce qu’il n’y a pas de représentation universelle pour les formes 3D.  Le maillage triangulaire est un standard de l’industrie mais c’est une représentation très difficile à prédire pour un réseau de neurones car elle est discrète et combinatoire. En revanche, il est beaucoup plus simple de prédire une déformation d’un maillage préétabli, car c’est c’est un espace continu. J’ai donc proposé avec mes co-auteurs une nouvelle représentation qui réunit deux qualités : d’abord (i) reconstruire des maillages triangulaires de haute-qualité, et (ii) être compatible avec certaines architectures de réseaux de neurones classiques en apprentissage profond. Cette représentation est inspirée de la technique du “papier mâché” : un réseau de neurones apprend à déformer des feuilles planaires et à les placer sur une forme 3D de sorte à ce que l’union de ces feuilles déformées représente fidèlement la forme initiale.

Ayant établi cette représentation, on peut maintenant l’associer aux techniques génériques d’apprentissage profond. Une boîte noire reçoit une image en entrée, prédit la déformation des feuilles et l’on ajuste automatiquement les paramètres de la boîte noire afin que l’objet 3D reconstruit corresponde à la vérité terrain. Une fois terminée cette phase d’entraînement de l’algorithme, on peut reconstruire une forme 3D à partir d’une nouvelle image, y compris les parties de l’objet invisibles dans l’image. Ce travail a  constitué un jalon important dans le domaine de la reconstruction 3D à partir d’une seule image. Pour l’instant, il ne se généralise pas à toutes les catégories d’images principalement par manque de diversité dans les bases de données 3D disponibles. 

À partir d’une seule image, a gauche, notre modèle prédit un maillage triangulaire de l’objet en 3D, en déformant des feuilles, comme dans la technique du papier-mâché.

Une des applications de ces recherches est la création d’objets virtuels. Ils sont présents dans de nombreuses industries comme le cinéma, les jeux vidéos, la simulation physique, l’architecture etc. Pensez par exemple au kart de Mario-Kart, aux minions dans Moi, moche et méchant, aux simulations de l’écoulement de l’air dans les turbines des réacteurs Safran…. Créer un objet 3D est aujourd’hui une tâche très complexe et généralement assez inaccessible. Ces techniques démocratisent l’accès et la manipulation de ce type de données, en inventant des outils simples pour créer, éditer et assembler des modèles 3D.

Thibault Groueix  a passé sa thèse à l’ENPC, et travaille actuellement chez Adobe.

Publié le

En utilisant la clé vous la montrez… trop tard elle est révélée !

Voici le premier des articles consacrés au Prix de thèse Gilles Kahn qui depuis 1998 récompense chaque année une excellente thèse en Informatique. Cette année le premier prix revient à Gabrielle De Micheli pour ses travaux dans le domaine de la cryptographie. En prime, vous pouvez aussi retrouver Gabrielle dans une vidéo de Arte sur la question abordée dans ce billet.  Pierre Paradinas

La cryptographie est une branche de l’informatique qui s’intéresse de manière générale à la protection de données et communications numériques. Elle est primordiale dans notre société où la majeure partie de nos données personnelles sont en effet numériques (par exemple, nos transactions bancaires).

À l’origine de la cryptographie se trouve le problème de l’échange de messages chiffrés, c’est-à-dire de messages inintelligibles, que seul un récepteur légitime peut déchiffrer, donc lire. Afin d’assurer une transmission sécurisée de ces messages, une clé secrète est généralement partagée entre l’expéditeur et le destinataire.

Au début des années 1970, Merkle s’écarte de ce concept de clé partagée et formalise, avec Hellman, la notion de cryptographie à clé publique où deux clés mathématiquement liées sont générées et utilisées : une clé publique et une clé secrète. Un message est ensuite chiffré à l’aide de la clé publique du récepteur. Ce dernier sera alors le seul capable de déchiffrer le message à l’aide de sa clé secrète correspondante.

Les cryptosystèmes à clé publique, également connus sous le nom de protocoles dits asymétriques, sont tous construits à l’aide de problèmes mathématiques particuliers. Ces derniers doivent correspondre à des fonctions qui sont faciles à calculer pour toute entrée donnée mais difficiles à inverser.  Historiquement, deux candidats ont émergé : la multiplication de deux nombres premiers et l’exponentiation modulaire. L’inverse de ces opérations consiste à factoriser un nombre entier et à calculer un logarithme discret et sont considérés comme des problèmes difficiles à résoudre, même avec l’aide d’ordinateurs très puissants. Prenons l’exemple de la factorisation. Si l’on demande à un ordinateur de factoriser l’entier 1081, on obtient facilement 1081 = 23 x 47. Cependant, si on souhaite la factorisation d’un entier beaucoup plus grand, par exemple un entier de plus de 300 caractères, alors la factorisation devient trop compliquée à obtenir en un temps raisonnable.

Ces problèmes répondent bien aux exigences d’un protocole asymétrique. En effet, pour qu’un protocole soit sûr et efficace, le déchiffrement d’un message sans la clé secrète doit être proche de l’impossible, alors que le chiffrement d’un message et le déchiffrement avec la clé secrète doivent être faciles, c’est-à-dire réalisés uniquement avec des opérations simples.

Mes travaux de thèse se sont concentrés sur le second candidat : l’exponentiation modulaire et son opération inverse, le calcul d’un logarithme discret. L’objectif de ma thèse a été de répondre à la question suivante. Comment évaluer la sécurité des protocoles dans lesquels une exponentiation modulaire impliquant un secret est effectuée ?

Cette question peut se répondre de deux façons différentes. D’une part, mes travaux ont étudié la difficulté de résoudre le problème du logarithme discret qui donne un accès direct à l’exposant, donc au secret. D’autre part, j’ai étudié les vulnérabilités d’implémentation, c’est-à-dire des failles qui peuvent se glisser dans le code, pendant l’exponentiation rapide qui peuvent également conduire à l’exposant secret. Il existe en effet des attaques dites par canaux cachés qui vont nous permettre de récupérer de l’information secrète qui nous mènera jusqu’à la clé secrète.
Gabrielle De Micheli, a préparée sa thèse au centre Inria Nancy-Grand Est, actuellement postdoctorante à l’université de californie à San Diego (UCSD).
Pour aller plus loin : un reportage de Arte sur les travaux présenté dans ce billet  https://www.arte.tv/fr/videos/105025-000-A/cybersecurite-la-science-des-codes-secrets/
Publié le

J’ai un problème : je ne sais pas trop ce qu’est l’intelligence artificielle 

Ce texte est paru originellement dans le Hors-Série de Pour la Science n° 115 : « Jusqu’où ira l’intelligence artificielle ? », mai 2022.

Entretien avec Serge Abiteboul, directeur de recherche à Inria et à l’ENS Paris. Propos recueillis par Olivier Voizeux.

Peut-on dire que, plus que le jeu d’échecs, les réseaux de neurones ont dopé la recherche sur l’intelligence artificielle ?

Ce serait un peu du bourrage de crâne. Un système comme Deep Blue, d’IBM, qui a battu le champion du monde d’échecs Gary Gasparov en 1997, embarquait des années de recherches, le plus souvent développées pour autre chose. Toutes les techniques informatiques ont des applications considérables qui sont à l’œuvre tous les jours, qui marchent très bien et ont pour nom « gestion de données », « système d’exploitation », « compilateur », « communication numérique », « interface humain-machine », « calcul parallèle », « raisonnement logique », etc. Ce qu’on observe depuis une dizaine d’années, c’est l’arrivée d’algorithmes d’apprentissage automatique, qui ont obtenu des résultats superbes dans des domaines qui nous bloquaient jusque-là. Mais internet et votre téléphone portable fonctionnent en grande partie sans eux, même si on utilise de plus en plus l’apprentissage automatique, par exemple dans les assistants vocaux.

Pouvez-vous préciser l’apport de l’apprentissage automatique ?

Sur certains problèmes, les approches dites « symboliques », fondées sur le calcul et le raisonnement, ne progressaient presque plus. Je pense notamment à des problèmes tout bêtes comme de distinguer l’image d’un chat de celle d’un chien, ou, plus intéressant, de reconnaître une tumeur cancéreuse. Et, assez soudainement, des techniques connues depuis longtemps et qui avaient souvent des résultats médiocres, les réseaux de neurones, se sont mises à fonctionner. La traduction automatique des langues, par exemple, s’est améliorée considérablement (lire l’entretien avec Thierry Poibeau). Avec l’apprentissage automatique et les méthodes statistiques, ainsi nommées parce qu’elles s’appuient sur de gros volumes d’informations, un logiciel apprend de données fournies par des humains, en observant son environnement, en simulant des situations, etc. Pour faire une analogie, vous pouvez apprendre à jouer au tarot parce que des amis vous en expliquent les règles, mais vous pouvez aussi vous former en regardant des joueurs. Souvent, les deux modes coexistent. On connaissait depuis des années des algorithmes pour faire apprendre aux machines, notamment les réseaux de neurones. Pourquoi tout à coup sont-ils devenus plus performants ?

Il y a eu une sorte de conjonction de planètes avec l’arrivée, presque au même moment, de beaucoup plus de puissance de calcul, de plus en plus de corpus de données pour nourrir l’apprentissage, et du développement de nouveaux algorithmes dits « d’apprentissage profond »

(deep learning, en anglais). D’un coup, des problèmes qui nous résistaient depuis des années se sont mis à tomber. Cela avait un côté génial. Mais, encore une fois, cette approche n’a pas remplacé ce qui existait avant. Même quand AlphaGo, de DeepMind, a battu le joueur de go Lee Sedol, il n’utilisait pas uniquement des algorithmes d’apprentissage profond.

Le revers de ces méthodes n’est-il pas leur opacité ?

En effet, quand on fait tourner un algorithme d’apprentissage profond, on ne sait pas expliquer pourquoi on arrive à un résultat particulier. Les longs calculs réalisés ne font pas à proprement parler un raisonnement, en tout cas un raisonnement qu’un humain serait capable de comprendre. On peut penser que, tant pis, seule l’efficacité prime, mais ce n’est pas si simple. Prenons deux exemples en médecine : un algorithme d’apprentissage qui aide à retrouver des tumeurs cancéreuses (voir La fée IA au chevet des malades, par N. Ayache) examine des milliers d’images annotées par des médecins, et à partir de toute cette connaissance se prononce sur les images qu’on lui soumettra. Impossible pour un humain de se former en étudiant toutes ces images : il y en a trop. Et de toute façon, il y aura un médecin, voire une équipe, pour discuter l’avis de la machine qui sera un avis comme un autre, pris comme tel. En revanche, en matière de diagnostic médical, si vous rentrez dans un programme un grand nombre d’informations sur un patient, et qu’à la fin ce logiciel décide « c’est une hépatite », ça ne peut pas suffire au médecin qui a besoin d’explications. Il ou elle a besoin d’entendre que, en fonction des observations du malade, statistiquement ce peut être telle maladie avec 95 % de chances, mais aussi telle autre avec 5% de chances, et qu’il faudrait poser telle question au malade pour écarter telle possibilité, ou demander tel examen complémentaire, etc. Dans les deux cas, il y a un travail collaboratif entre machine et humains. Dans le premier, nul besoin d’explications (les techniques d’apprentissage automatique un peu brutales sont efficaces). Dans le second, des explications sont indispensables.

Où finit l’informatique « ordinaire », où commence l’intelligence artificielle ?

Cette distinction n’a pas vraiment de sens. On a, à l’intérieur de l’informatique, un vrai continuum.

Quelle est alors votre définition de l’intelligence artificielle ?

Pour Alan Turing, une activité d’une machine sera qualifiée d’« intelligence artificielle » si elle est considérée comme intelligente quand un humain s’y livre. À ses yeux, ce ne peut être qu’une imitation de l’intelligence humaine, une simulation. J’utilise la définition de Turing mais, honnêtement, ça ne me dit pas grand-chose puisque, tout comme lui, je ne sais pas définir l’intelligence humaine. En fait, j’ai un problème : je vous en parle, mais je ne sais pas trop ce qu’est l’intelligence artificielle ! L’expression fait fantasmer. Mais qu’est-ce qu’elle signifie ? Depuis ma thèse, je travaille sur des systèmes de gestion de base de données, qui répondent aux questions des humains. C’est quand même intelligent de répondre à des questions ! J’ai travaillé sur des bases de connaissances qui font de la déduction. Là encore, c’est intelligent de raisonner. Plus récemment, l’apprentissage automatique m’a permis d’introduire de nouvelles fonctionnalités dans des systèmes sur lesquels nous travaillons avec des étudiants. Distinguer ce qui en informatique tient de l’intelligence artificielle ou pas, ça n’aide en rien. Pour moi, c’est avant tout un buzzword, surtout utile pour récupérer des financements ou impressionner des amis. Le truc cool, aujourd’hui, n’est pas l’intelligence artificielle, mais l’apprentissage automatique qui vient compléter d’autres techniques essentielles de l’informatique.

Donc vous ne cherchez jamais à développer des programmes « plus intelligents » ?

Je cherche à faire des programmes qui résolvent des problèmes, qui répondent aux besoins de leurs utilisateurs. Cela dit, je ne connais pas beaucoup d’informaticiens qui essaient d’écrire des programmes idiots… même si on ne sait pas définir l’intelligence.

Quel est l’objectif de la recherche en intelligence artificielle ? Dépasser l’humain ?

Vous l’avez compris, je ne sais pas distinguer recherche en intelligence artificielle et en informatique. Les chercheurs en informatique veulent repousser les limites de la science. Certains se posent des questions théoriques, par exemple sur la calculabilité ou la puissance du raisonnement, presque du ressort des mathématiques pures. À l’autre bout du spectre, d’autres développent des produits informatiques prêts à être utilisés le mois d’après comme les logiciels scikit-learn (une bibliothèque Python pour l’apprentissage automatique) et Caml (un langage de programmation et un environnement populaire). Parfois, une recherche très théorique comme celle des universitaires Ronald Rivest, Adi Shamir et Leonard Adleman débouche sur un algorithme de chiffrement très pratique, le RSA, qui est à la base de tous les échanges chiffrés sur internet. Pour moi, cette diversité est la grande richesse de la recherche dans ma discipline. Les humains sont de magnifiques machines à résoudre des problèmes. Pourquoi ne pas essayer de les imiter avec des ordinateurs ? C’est le genre de défi qui fait avancer les sciences. Quant à les dépasser… pourquoi pas ? À vrai dire, l’informatique accomplit déjà des tas de choses dont nous sommes incapables. Reproduire à la main des calculs que votre smartphone traite à toute vitesse prendrait un temps dingue à des centaines de milliers de personnes qui commettraient des millions d’erreurs. Les ordinateurs calculent bien mieux que nous. Faire mieux que l’humain n’est pas si difficile.

Mais, d’une calculette, on ne dit pas qu’elle est intelligente…

Un des trucs qu’on apprend à l’école primaire, c’est calculer, non ? Moi, je trouve ça intelligent. Le chien du voisin, sait-il calculer ?

Peut-être ce déni s’explique-t-il parce que la calculette est devenue ordinaire ?

En effet, comme c’est un objet de notre quotidien, on lui interdit d’être vraiment intelligent. Peut-être que ce qu’on sait expliquer par une suite d’opérations est dénué de vraie intelligence. La preuve automatique d’un théorème mathématique, on peut la décortiquer pas à pas. Et une machine reproduira « bêtement » le calcul, donc ça ne doit pas être bien sorcier. Mais comme on ne comprend pas comment fonctionne l’apprentissage automatique, alors c’est forcément intelligent.

Est-ce qu’il y a, sur l’intelligence artificielle, une approche particulière à la France ?

Non. La recherche en informatique est devenue extrêmement mondiale, il ne peut pas y avoir d’approche hexagonale. Il y a une grande fluidité entre les pays. J’ai fait ma thèse aux États-Unis comme beaucoup de collègues, on interagit sans cesse avec des collègues américains, européens, africains, asiatiques, nos labos sont peuplés de doctorants, postdoctorants, visiteurs, etc., de multiples nationalités. Si on voulait vraiment chercher une coloration française, ce serait plutôt du côté de la formation scolaire et universitaire. Nos étudiants avaient jusqu’à récemment, en moyenne, une formation plus mathématique que ceux venus d’ailleurs. Cela leur donnait des bases théoriques vraiment solides. J’espère que cela ne va pas changer.

Ils ne sont pas capables de créativité tout court : ni en maths, ni en biologie, ni en littérature. On y travaille, on fait des progrès, mais les poèmes que nos algorithmes créent sont encore médiocres. Ce qu’on sait faire, c’est donner plein d’exemples de beaux tableaux d’un peintre à une machine, et lui demander de produire une œuvre dans le même genre. Elle ne crée pas vraiment, elle singe. D’ailleurs, on retrouve la même difficulté de définition qu’avec l’intelligence, je ne sais pas définir formellement la beauté ou la créativité. À ce sujet, les travaux du jeune chercheur en IA Antoine Cully dans sa thèse m’ont passionné. Il montre, par exemple, comment un robot à six pattes a pu inventer une nouvelle façon de marcher avec une patte abîmée ou manquante. Mais ce robot a-t-il vraiment découvert une nouvelle façon de marcher ? Ou cette nouvelle démarche était-elle plus ou moins déjà inscrite dans tous les calculs qu’on lui avait demandés avant ?

Sauriez-vous développer un algorithme de bêtise artificielle ?

Vous ne trouvez pas qu’il y a assez de bêtise naturelle ?

Imaginez qu’il n’y en ait pas autour de nous et qu’on ait besoin d’une machine bête pour nous divertir.

S’il s’agit de programmer un générateur de formules fausses, je peux facilement le faire. Mais si vous voulez en plus qu’elles soient drôles, c’est de l’humour. Là, c’est encore plus dur que la créativité.

L’intelligence artificielle est sortie des laboratoires, elle est entrée dans la cité, et elle y produit des effets. Lesquels vous paraissent les plus importants ?

Il y a deux questions qui me semblent particulièrement critiques en ce moment, et elles sont liées : c’est la sobriété énergétique et le travail. Selon les sources, le numérique représenterait aujourd’hui de 3 à 4% des émissions de gaz à effet de serre dans le monde, et cela croît. Je ne sais pas chiffrer la proportion de l’intelligence artificielle dedans. Ce n’est pas énorme, mais cela augmente aussi. Pour limiter notre impact sur l’environnement, il va nous falloir changer nos modes de vie par exemple arrêter de changer de téléphone tous les deux ans ou de passer du temps à visionner des films en haute résolution sur un téléphone cellulaire. Il y a beaucoup de gaspillage, comme avec les « chaînes de blocs » (blockchains), ces procédés de stockage sécurisés et décentralisés, qui pourraient fonctionner en consommant plusieurs ordres de grandeur d’énergie en moins pour le même résultat. Dans le numérique comme pour le reste, il va nous falloir apprendre à être frugaux.

Et concernant le monde du travail ?

L’ensemble de la technologie numérique a une incidence sur l’emploi, pas seulement l’intelligence artificielle. Aujourd’hui, on peut faire fonctionner une usine avec très peu d’individus grâce à l’informatique en général. Il est vrai qu’avec l’intelligence artificielle on va aller encore plus loin dans le remplacement de l’humain. Après sa force physique, son travail intellectuel devient de plus en plus remplaçable. Le hiatus est qu’on veut une société plus sobre énergétiquement, qui produise et pollue moins, et qu’on veut aussi moins travailler, donc utiliser plus de machines. Or il faut de l’énergie pour fabriquer les machines et elles ont des rendements souvent moins bons que les nôtres. Pour y arriver, de sérieuses avancées scientifiques et d’importantes mesures d’économie seront nécessaires. Et puis, si les machines remplacent les humains, qui va être rétribué ? Uniquement ceux qui les possèdent ? Dans ce cas, la grande masse de la population sera non seulement privée d’activité, mais aussi de quoi se nourrir. Ce ne sera pas socialement tenable. Dans les vingt à cinquante ans à venir, une transformation complète de la société s’imposera, exigeant que l’économie soit beaucoup plus redistributive. Voilà pour le volet sociétal, qui se double d’un volet humain. Dans notre culture, on nous apprend dès l’enfance que le travail est la grande valeur. Comment fera-t-on dans un monde où une grande partie d’entre nous sera sans emploi, ou avec de l’emploi partiel, ou des travaux associatifs ou d’aide à la personne, non « productifs » dans le sens économique actuel ? Il nous faut inventer une nouvelle philosophie du travail, de son utilité sociale, une nouvelle philosophie des loisirs. Le côté génial, c’est que, si on ne se plante pas écologiquement ou socialement, l’informatique nous permet d’avoir l’ambition la plus dingue, celle d’une société égalitaire où tout le monde vivrait bien, en s’éduquant, avec autant de loisir que souhaité. Ce n’est pas de la science- fiction… Enfin, je l’espère.

https://www.pourlascience.fr/sd/informatique/j-ai-un-probleme-je-ne-sais-pas-trop-ce-qu-est-l-intelligence-artificielle-23682.php

Publié le

Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing

Frédéric Magniez  a tenu la Chaire annuelle Informatique et sciences numériques 2020-2021 du Collège de France. Il n’y avait pas eu à l’époque d’article sur binaire. Voilà qui corrige cette situation peu acceptable.
Frédéric Magniez, mathématicien et informaticien, est directeur de l’Institut de recherche en informatique fondamentale (www.irif.fr) et directeur adjoint de la Fondation des sciences mathématiques de Paris. Ses travaux de recherche portent sur la conception et l’analyse d’algorithmes probabilistes pour le traitement des grandes masses de données, ainsi que sur le développement de l’informatique quantique et plus particulièrement les algorithmes, la cryptographie et ses interactions avec la physique. Serge Abiteboul
Frédéric Magniez, 2020. Crédits : Patrick Imbert, Collège de France

Une prouesse inutile ?

L’année 2021 sera sans aucun doute quantique ! Il y a à peine plus d’un an, Google réalisait un calcul sur un prototype de circuit quantique programmable. D’un point de vue technologique la prouesse était encore inimaginable il y a seulement quelques années. D’un point de vue de la puissance de calcul, la tâche demandée est certes très spécifique, mais nécessiterait plusieurs milliers d’années de calcul sur tout autre machine existante, aussi puissante soit-elle ! Un vrai tournant venait donc d’être engagé. Cette année, un consortium européen va lancer une plateforme de simulation et de programmation quantique rassemblant chercheurs et industriels issus de la physique et de l’informatique. Cette plateforme utilisera une technologie quantique fournie par la start-up française Pasqal. Enfin, l’État va lancer un plan national quantique qui va voir la création de plusieurs centres dédiés à la recherche sur les technologies quantiques, dont l’informatique.

Le calcul effectué par Google fin 2019 revenait à lancer un gigantesque dé truqué ou faussé. Le calcul des probabilités de chaque face du dé est lié au circuit quantique programmé dans la machine de Google. La simulation d’un circuit quantique, même de petite taille (53 bits dans l’expérience de Google), est d’une telle complexité pour nos ordinateurs actuels qu’elle ne peut être réalisée en moins de plusieurs millénaires par ces derniers. En revanche, le lancé de ce dé est quasiment instantané sur le prototype quantique de Google, puisque ce dernier implémente directement ledit circuit quantique, et ce avec une précision satisfaisante, c’est-à-dire pour vérifier que le bon dé avait été lancé. Cette réalisation, même imparfaite, semble pour le moment impossible à réaliser autrement que quantiquement.

Cette prouesse semble loin de toute application pratique. Néanmoins, elle valide un courant de pensée remontant aux années 1980, en particulier aux propos de Feynman, affirmant que notre interprétation et compréhension de ce qui est calculable devait évoluer. Elle remet en cause les fondements du calcul remontant à la thèse de Church-Turing. Cette thèse, qui a évolué au fil des années, tendait à affirmer que tout progrès technologique ne remettrait jamais en cause le modèle mathématique du calcul défini par Church et Turing en 1936. Ce modèle permet de discerner ce qui est calculable par une machine de ce qui ne l’est pas. Quelques décennies après, cette thèse avait été reformulée ainsi : tout modèle de calcul raisonnable peut être simulé efficacement par une machine de Turing probabiliste (i.e. ayant accès à une source d’aléa). La notion de complexité y avait donc été ajoutée, rendant la thèse plus ambitieuse mais aussi plus fragile.

Les fondations – Enigma bis ?

Cette thèse étendue de Church-Turing a donc été remise en question au tout début de l’informatique quantique, lorsque Deutsch définit en 1985 la notion de machine de Turing quantique, avec son lot de premiers algorithmes exponentiellement plus rapides que leurs équivalents déterministes (mais pas encore probabilistes). D’abord perçu comme une curiosité, ce modèle de calcul finit par susciter intérêt et questionnements dans la communauté scientifique. Finalement en 1993, Bernstein et Vazirani construisent mathématiquement une machine universelle quantique efficace, c’est-à-dire le premier
compilateur quantique (l’existence d’une machine programmable) qui valide mathématiquement le modèle de calcul (mais pas sa réalisation physique). En même temps arrive l’évidence qu’un ordinateur quantique peut être exponentiellement plus rapide qu’un ordinateur classique, i.e. qu’une machine de Turing probabiliste. Cependant les problèmes résolus sont tous artificiels et semblent encore bien loin de toute application concrète.

C’est Simon puis Shor qui arrivent avec la première application algorithmique, et pas des moindres, en 1994, soit seulement une année après l’acceptation par la communauté du concept même de calcul quantique. En effet, cette application permettait de déchiffrer la plupart des messages cryptés par les mécanismes dits à clé publique, et de réduire à néant les procédés cryptographiques les utilisant (monnaie électronique, CB, vote électronique, authentification, …). Heureusement, l’ordinateur quantique n’existe pas (encore) ! Pourtant cette découverte n’est pas sans rappeler les découvertes de Turing et la construction de la machine qui a permis de déchiffrer les messages allemands eux-mêmes chiffrés par la machine Enigma durant la deuxième guerre mondiale…

Les algorithmes quantiques – Une nouvelle façon de penser

Néanmoins, deux décennies plus tard, alors que la possibilité d’une construction future d’un ordinateur quantique commençait à être prise au sérieux, une compétition scientifique internationale a été lancée en 2016 afin de définir les nouveaux standards de chiffrement post-quantique, ouvrant la voie à une longue recherche puis standardisation toujours en cours. Une autre alternative repose pourtant dans l’utilisation relativement simple de fibre optique afin de communiquer en encodant l’information directement sur des photons. Il s’agit du protocole quantique d’échange de clé proposé par Bennett et Brassard en 1984, soit 10 années avant la découverte de l’algorithme de Shor. En quelque sorte l’attaque et la parade reposent sur la même technologie, à ceci près que le protocole en question a déjà été construit et testé sur de grandes distances, un satellite dédié à même été envoyé par la Chine en 2016. L’Europe n’est pas en reste avec des projets d’infrastructure de grande envergure dédiés au déploiement de solutions quantiques de chiffrement. Cependant ces solutions quantiques nécessitent des technologies spécifiques, alors que les solutions algorithmiques dites post-quantiques pourraient être déployées sur les structures et ordinateurs actuels.

Depuis 1994, les applications (calcul scientifique, optimisation, recherche opérationnelle, simulation, apprentissage automatique, IA…) foisonnent dans tous les domaines où l’informatique joue un rôle crucial, et pour des tâches où nos ordinateurs actuels ne sont pas assez puissants. Mais surtout les outils développés (transformée de Fourier quantique, estimation de phase, amplification d’amplitude, estimateur quantique, marche quantique, …) progressent continuellement, impactant toutes les thématiques de l’informatique, en en créant de nouvelles (information quantique, complexité hamiltonienne, simulation quantique, …), ou encore en tissant de nouveaux liens de l’informatique vers d’autres disciplines dont la physique, la chimie et les mathématiques.

Mais avant tout l’informatique quantique a introduit une nouvelle façon d’analyser, raisonner et démontrer. Les outils existants précédemment n’étant plus adaptés, il a fallu en créer de nouveaux. Apportant un nouveau regard mathématique à des questions anciennes, ces nouveaux outils ont permis de progresser sur des questions ouvertes depuis de nombreuses années. Cette démarche a été baptisée preuve ou méthode quantique. Une preuve quantique est un peu l’analogue des nombres complexes pour la trigonométrie ou encore l’électricité : un outil très puissant permettant de mener facilement des calculs difficiles, ou encore d’établir des preuves inaccessibles jusque là, y compris dans des domaines pour lesquels ils n’ont pas été construits initialement. La dernière démonstration en date est la réfutation d’une célèbre conjecture en mathématiques (conjecture de Connes) à l’aide d’un résultat en théorie de la complexité quantique.

Vision et formations nécessaires

Une fois tous ces algorithmes quantiques découverts, dont l’utilisation de certains serait à n’en pas douter révolutionnaire, la question de la possibilité de construire un ordinateur les exécutant fut donc de plus en plus pressante. L’importance d’un plan d’envergure a d’abord émané de tous les acteurs concernés, scientifiques comme industriels, avec une feuille de route et des jalons intermédiaires appropriés, puis fut largement soutenue par les politiques. Plusieurs plans ont vu le jour, dont un au niveau européen à travers le Quantum Flagship en 2018, et le Plan Quantique national en 2021. L’avantage industriel que pourrait procurer la construction d’un ordinateur quantique, même imparfait, a créé une frénésie stimulante qui touche tous les secteurs stratégiques (finance, industrie, santé, sécurité…). Les progrès technologiques de grands groupes industriels, tels que Google et IBM par exemple, ont été de véritables locomotives, laissant apparaître rapidement que le plus grand défi serait de trouver une application à ces premiers prototypes, certes révolutionnaires, mais très éloignés des machines nécessaires aux applications précédemment découvertes en algorithmique quantique. En effet, non seulement ces machines sont petites, mais elles ont un taux d’erreur encore trop grand. Pourtant elles sont capables d’effectuer des calculs impossibles à réaliser classiquement, mais des calculs sans impact industriel actuellement.

Un véritable travail de fourmi s’est donc enclenché, mais, pour l’instant, avec une communauté encore trop petite. Les mêmes personnes ont actuellement en charge de comprendre et de maîtriser toutes les facettes du calcul quantique, de la modélisation à la réalisation expérimentale en passant par la solution algorithmique, son analyse, sa programmation et sa vérification, là où la chaine de production constitue habituellement un véritable écosystème de l’informatique. Il nous faut donc nouer de multiples partenariats, construire et enseigner dans de nouvelles formations, afin de saisir cet unique défi que pourrait constituer ce nouveau tournant technologique.

C’est dans ce contexte que le Collège de France m’a donc invité à occuper pour un an sa chaire Informatique et sciences numériques, et à donner dans ce cadre un cours sur les algorithmes quantiques. Ce cours tâchera de répondre à une demande croissante d’information et de formation de nombreux publics. Le public ciblé va des esprits curieux de saisir les possibilités et les limites du calcul quantique, aux acteurs des sciences informatiques au sens large : informaticiens, mathématiciens du numérique et physiciens des technologies quantiques, qu’ils soient étudiants, chercheurs, développeurs, entrepreneurs ou encore futurs utilisateurs des algorithmes quantiques.

En guise de conclusion, il convient de rappeler que c’est en France, en 1980, qu’a débuté la révolution quantique expérimentale lorsque l’expérience du groupe d’Alain Aspect (CNRS) a validé à Orsay les prédictions de la physique quantique, qui ne pouvaient s’expliquer par la physique classique seule. Puis le prix Nobel a été décerné en 2012 à Serge Haroche (Collège de France) pour ses travaux sur la manipulation de systèmes quantiques. Le versant informatique de cette révolution a, lui, débuté en 1994 conjointement aux travaux outre-Atlantique, grâce à la vision de Miklos Santha (CNRS). Alors étudiant de master, j’ai suivi le mouvement de son équipe, qui était basée aussi à Orsay. Rapidement, Miklos a su constituer un groupe qui essaime, fait des émules en France et attire des talents internationaux. A l’époque, le pari pouvait sembler risqué, mais dans les années 2000, les possibilités de recrutement au CNRS et à l’Université sont plus nombreuses, et plusieurs chercheurs sont recrutés afin de mieux comprendre les liens que tisse le traitement de l’information quantique entre informatique, mathématiques et physique.

Frédéric Magniez, Directeur de recherche CNRS,  Directeur de l’IRIF
Pour la leçon inaugurale de la chaire annuelle Informatique et sciences numériques du Collège de France – 1er avril 2021

Pour aller plus loin

  • Pages de Frédéric Magniez sur le site internet du Collège de France :
    https://www.college-de-france.fr/site/frederic-magniez/index.htm
  • Article sur les travaux de Frédéric Magniez dans CNRS le journal
    https://lejournal.cnrs.fr/articles/une-informatique-a-reinventer-pour-le-calcul-quantique
Publié le

Etalab : de l’ouverture des données à leur partage collaboratif

Dans le cadre de la rubrique autour des “communs du numérique”, un entretien avec Laure Lucchesi, directrice d’Etalab au sein de la Direction interministérielle du numérique (DINUM). Après une vingtaine d’années dans le numérique dans les secteurs public et privé dans plusieurs pays, elle devient directrice d’Etalab en 2016. Elle a une longue expérience du logiciel libre et de l’open data. A Etalab, elle encourage le développement des communs numériques.
Laure Lucchesi (Etalab)

Pourriez-vous raconter un peu ce que fait Etalab aux lecteurs de binaire ?

Etalab est un département de la direction interministérielle du numérique (DINUM) sous l’autorité de la ministre de la Transformation et de la Fonction publiques. Notre mission c’est de faire en sorte que l’État et le service public rendu aux usagers s’améliorent en exploitant tout le potentiel des données. L’un des leviers, c’est l’ouverture des données publiques, que l’on appelle parfois « open data », qui consiste à mettre en ligne sur une plateforme, data.gouv.fr, les données produites par les systèmes d’information de l’État et non couvertes par des secrets, afin qu’elles puissent être réutilisées par d’autres. En 2020, la crise sanitaire a par exemple bien mis en évidence l’utilité de la mise à disposition de tous des données publiques, sans lesquelles des services comme covidtracker ou vitemadose n’auraient pas pu exister.

Cette donnée publique, c’est la matière première d’une action publique transparente, véritablement au service de la démocratie. Elle ouvre aussi la voie à davantage de participation des citoyens, à de nouvelles façons de produire et d’améliorer le service public : des services innovants, crées par des tiers à partir des données en open data, viennent ainsi compléter et « augmenter » le service public, en démultiplier la portée en quelque sorte.

Plus largement, notre mission consiste à ouvrir – au sens de rendre accessibles et réutilisables par tous – un maximum de ressources numériques de l’État : les données, mais aussi les APIs (sur api.gouv.fr), les codes sources logiciels (code.gouv.fr), et même les communs numériques que l’administration utilise, produit et/ou auxquels elle contribue (https://communs.numerique.gouv.fr/communs/).

Nous avons d’ailleurs lancé fin 2021 un nouveau programme : l’Accélérateur d’initiatives citoyennes (citoyens.transformation.gouv.fr), pour faciliter la réutilisation de ces ressources numériques et les coopérations entre l’administration et la société civile qui porte des projets d’intérêt général.

Nous avons également mis en place le programme “Entrepreneurs d’intérêt général” qui s’apprête à lancer sa 6e promotion : nous sélectionnons des spécialistes de la technologie, du design et du droit du numérique pour tester et expérimenter de nouveaux possibles avec des agents de l’État. L’idée est de s’attaquer à des défis publics et d’ouvrir l’administration à des talents venus de l’extérieur. On s’appuie sur l’agilité du numérique, sur des modes d’action différents de ceux qui prévalent dans l’administration, pour résoudre des problèmes concrets.

Etalab a démarré il y a un peu plus de dix ans comme un lab innovant, pionnier, faiseur et un peu bidouilleur. L’enjeu est désormais de passer de l’innovation à la transformation, et d‘accompagner toute l’administration dans la « mise à jour » de son logiciel d’action publique ! D’institutionnaliser notre action, sans perdre pour autant nos valeurs d’ouverture et d’innovation radicale.

Le rapport Bothorel[1] et la circulaire du Premier ministre du 27 avril 2021 ont permis de renforcer cette politique et sa gouvernance : On a désormais une véritable politique publique de la donnée, déclinée également dans chaque ministère. Chaque administration doit avoir son administrateur ou administratrice des données, algorithmes et codes sources (l’équivalent d’un « chief data officer ») et définir sa feuille de route en la matière.

https://communs.numerique.gouv.fr/communs/

Y a t-il des freins à ces actions ?

Comme dans tout changement, il y a naturellement des interrogations légitimes, et des résistances dues à une perte de contrôle : mes données ne sont pas assez bonnes ; eur qualité va-t-elle être critiquée ? Quels sont les risques que je prends ? Qu’est-ce qui va etre fait avec mes données ?…

Ensuite, l’ouverture des données exige du temps et des moyens. Il faut bien comprendre que l’ouverture de ses données n’est pas le cœur de la mission d’une administration ; elle doit être accompagnée pour cela et on a peut-être trop longtemps sous-estimé ces besoins.

Enfin, ouvrir la donnée ne suffit pas. Pour que cela soit un succès, il faut aussi stimuler la réutilisation de ces données, faire vivre au quotidien l’engagement d’un écosystème d’innovation.

Le mouvement de l’ouverture des données publiques est-il bien engagé en France ? Dans tous les ministères ?

Oui, tous les ministères, ainsi que bon nombre de leurs établissements sont engagés dans cette ouverture. Les feuilles de route des ministères en témoignent, et la France est pour la première fois cette année au tout premier rang des pays européens en matière d’open data !

La crise sanitaire a permis de démontrer très concrètement, jusqu’au grand public, l’intérêt de l’ouverture des données pour l’information des citoyens. On a vu comment des tierces parties pouvaient s’emparer de ces données pour en proposer des usages, on a bien réalisé comment des données publiques ouvertes pouvaient devenir le socle de services publics ou privés avec de grandes utilités économiques et sociales. Mais il ne s’agit pas seulement d’ouvrir. A partir du moment où ces données sont utilisées, il faut aussi qu’elles restent à jour et de qualité, et il faut garantir leur pérennité.

Nous considérons ainsi certaines donnée –  dites « de référence » parce qu’elles sont centrales et servent à identifier ou nommer des entités, par exemple la base nationale des adresses géolocalisées (BAN) – comme une véritable infrastructure, dans laquelle il faut investir et dont il faut assurer l’entretien collectif. C’est en cela que les mécanismes contributifs et la notion de « communs contributifs », auquel une communauté d’usage participe, prend tout son sens.

Usage et enrichissement de la Base Adresse par les services de secours : Ici le SDIS 64

Est-ce que cela va assez vite ? Partout ?

Cela avance partout, même si pour certains ministères, cela va peut-être moins vite. Cela tient souvent à des niveaux de maturité numérique différents, de culture de la donnée plus ou moins forte. Dans certains domaines, il y a déjà une grande habitude de la donnée métier.

Pour nous, l’objectif est que chacun s’autonomise. Certains services étaient pionniers, certaines collectivités parfois aussi, dès 2009, avant même les services de l’État.

Au fur et à mesure que les administrations gagnent en maturité, notre rôle change, il est moins centralisateur, plus fédérateur : la mise en œuvre s’est naturellement distribuée et nous sommes plus dans l’accompagnement, tout en continuant à fixer le cadre d’action, à donner de grandes orientations, et à faciliter aussi les expérimentations.

Où trouve-t-on les données ouvertes publiques ?

En France, le point d’entrée est data.gouv.fr. Il ne se substitue pas aux différents sites et portails, mais il a vocation à recenser un maximum de données pour fournir un point d’entrée unique.

Qu’est-ce que les communs numériques représentent pour vous ?

L’open data n’est pas toujours le point de départ d’un commun, au sens d’une ressource numérique produite et gérée par une communauté. Dans de nombreux cas, l’administration – qui est la seule productrice – met à disposition des données telles qu’elle les a collectées et créées pour sa mission initiale, avec peu ou pas de « voie de retour » de la part des réutilisateurs.

Par exemple, l’INSEE affecte à chaque entreprise un identifiant unique, le numéro SIREN, et les données des entreprises sont stockées dans une base de 13 millions d’établissements – le fichier Sirène – parmi les plus riches du monde. Ce répertoire est depuis 2017 en open data, mais il n’est pas pour autant un commun, l’INSEE en assure seul la production et la gestion. Cette mise à disposition est déjà très précieuse pour l’économie et la société, mais la notion de commun numérique emporte avec elle la notion de production et d’entretien collectifs.

La base adresse nationale (BAN) commence à s’en rapprocher, avec des contributions des collectivités territoriales, de l’IGN, de la DGFIP, de l’Insee et d’une communauté d’acteurs qu’il faut parvenir à faire collaborer, autour de règles de gestion et d’usage partagées. La Base « Accès Libre », qui collecte et rend disponibles les données d’accessibilité des établissements recevant du public pour les personnes en situation de handicap (https://acceslibre.beta.gouv.fr/) en est un autre exemple.

Les communs sont pleins de promesses et participent à la souveraineté. Mais il y a encore besoin de mieux tester et comprendre comment s’y prendre pour orchestrer au mieux leur fonctionnement quand il implique l’acteur public.

Quelle gouvernance ? Par l’État ? Par qui ?

Que l’État assure seul la gouvernance, ce n’est pas l’objectif. Il faut trouver d’autres formes de gouvernance, plus ouvertes, mêlant acteurs publics et la société civile, pour garantir l’intérêt collectif. Les modalités de ces associations sont encore souvent au stade de l’expérimentation.

Est-ce qu’il y a un risque que le soufflé des communs publics retombe ?

Ouvrir, c’est une première étape qui demande déjà beaucoup de travail. Ensuite pour passer à de l’enrichissement collaboratif et de la validation, c’en est une autre. Pour la première étape, la dynamique est lancée, l’utilité est démontrée. Pour la seconde étape, la complexité organisationnelle est claire. Mais je reste optimiste. C’est le bon moment parce que la question de la souveraineté pousse dans ce sens, et vient redynamiser le mécanisme d’ouverture.

Et parmi les services autour de la donnée, vous considérez aussi des approches à partir de l’IA ?

On aide les administrations à expérimenter dans le cadre de projets autour de l’IA. Cela ouvre le sujet de la transparence des algorithmes publics et de l’explicabilité des résultats. Cela vise à éviter des comportements de type boîte noire.

On travaille aussi à ouvrir des bases de données d’apprentissage annotées, et à les partager avec des acteurs publics et privés, ainsi que des modèles d’apprentissage.

Alors que de plus en plus d’algorithmes sont susceptibles d’être utilisés comme aide à la décision, pour attribuer des aides par exemple ou des places dans l’enseignement supérieur, il y a désormais des obligations légales de savoir expliquer comment ces modèles fonctionnent. Nous travaillons à accompagner les agents publics dans la mise en œuvre de ces obligations, dès la conception des systèmes jusqu’à leur documentation et aux réponses fournies aux usagers qui souhaiteraient comprendre.

Serge Abiteboul, François Bancilhon

[1] Rapport de la Mission Bothorel « Pour une politique publique de la donnée », 2020.

Les communs numériques