La vie est mal configurée

Aller au contenu | Aller au menu | Aller à la recherche

vendredi, novembre 2 2018

Injonctions contradictoires : moins de maths mais plus d'IA

L’enseignement supérieur français est constamment soumis à des injonctions contradictoires — faire de l’excellent sans moyens, etc. Voici une contradiction amusante — ou navrante — sur l’enseignement de l’informatique.

On fait trop de maths

Encore récemment, les commentateurs et certains responsables politiques n’en avaient que pour les écoles alternatives, notamment la fameuse 42. L’enseignement universitaire, nous disait-on, était trop théorique, supposait trop de prérequis, notamment mathématiques, d’utilité douteuse ; tout ceci était dépassé et il fallait un enseignement basé sur la pratique, sur le « codage », tourné vers les technologies du moment. On a même entendu des gens prétendre qu’il n’y avait pas de formation au développement informatique dans les universités !

(Bien entendu ces discours profitent à des écoles privées, qui proposent à des parents et des jeunes inquiets des formations certes coûteuses mais censées leur assurer une insertion immédiate dans le marché du travail, ce fameux marché du travail où l’on demande des gens ayant 10 ans d’expérience dans des technologies vieilles de 5. Qui plus est, ils considèrent que l’université se limite aux licences généralistes, qui effectivement ne visent pas à enseigner telle ou telle technologie du moment, et omettent les Instituts universitaires de technologie, dont l’objet est justement de fournir une formation technologique.)

Il faut faire de l’apprentissage automatique

Tout ce discours, portant principalement sur les applications Web et mobiles, est déjà un peu dépassé : la mode est maintenant à l’intelligence artificielle (IA) ! Du plus haut niveau de l’État on nous dit que c’est LA chose importante à enseigner.

Ouvrons un manuel d’intelligence artificielle tourné pratique (du style Machine learning en Python), écrit par un ingénieur et pas par un de ces universitaires déconnectés de la réalité du vrai monde dont on nous parle dans les médias. On y trouve beaucoup de formules mathématiques. Certes, on n’y fait pas de démonstrations longues, on explique les choses par l’intuition (par exemple, on ne va pas démontrer la vitesse de convergence d’un algorithme de descente de gradient suivant des bornes sur les dérivées secondes, on va dessiner une cuvette et ce qui arrive lorsque l’on descend), mais il y a tout de même quelques petits raisonnements. Pareil ouvrage est inutilisable pour ces gens absolument rétifs aux mathématiques que des écoles comme 42 sont censées pouvoir aider.

Est-ce évitable ? Les systèmes basés sur l’apprentissage automatique (je simplifie grossièrement) prennent en entrée des tableaux de nombres et produisent des nombres en sortie. Ils sont paramétrés par de grands tableaux de nombres, par des « hyper-paramètres » (des nombres aussi) et par des fonctions mathématiques. L’analyse de leurs résultats suppose une certaine compréhension des statistiques, des probabilités. Aussi, Yann Le Cun, patron de l’IA à Facebook et titulaire d’une chaire annuelle au Collège de France, conseille de « miser sur les maths et la physique ».

Bien entendu, on peut apprendre à utiliser des technologies basées sur l’IA sans comprendre finement son fonctionnement. Le problème est que cette IA a de nombreux « boutons de réglage ». Je doute fortement que l’on puisse s’en servir valablement en tournant ces boutons au petit bonheur et en récupérant des résultats dont on n’a pas les moyens intellectuels de savoir s’ils sont significatifs ou non.

Il est vrai que, comme m’a fait remarquer un collègue qui applique l’apprentissage automatique chez un industriel, l’IA jouit actuellement du privilège qu’il n’y a souvent pas d’éléments de comparaison. Une entreprise acquiert des volumes de données, elle ne sait pas les analyser : ce que l’IA produira, de quelque qualité qu’il soit, sera perçu comme une amélioration par rapport au néant. Cette situation est transitoire et, s’il s’agit de préparer l’avenir et la compétitivité à long terme du pays, comme on nous le dit, c’est faire un mauvais pari que de viser aussi bas.

Caveat

Je ne dis évidemment pas qu’à l’université on n’apprend jamais des « technologies dépassées », qu’il n’y a jamais d’enseignements théoriques superflus par rapport aux objectifs des formations, ou que l’enseignement des mathématiques y est toujours adapté au public visé.

jeudi, novembre 1 2018

Sur le plagiat scientifique

Dans mon billet précédent j’ai évoqué le plagiat de généralités introductives, qui présentent un domaine, une technologie, une application, mais je n’ai pas évoqué le plagiat du contenu scientifique proprement dit.

Les articles sur le plagiat, notamment en lettres, sciences humaines et sociales, évoquent le « copier-coller » : des mémoires, des thèses, des articles, des livres, qui reprennent verbatim du texte publié ailleurs, sans qu’il ne s’agisse de citations dûment attribuées aux auteurs du texte original. Cela m’étonnait, car le copier-coller est facilement détectable par de simples recherches informatiques, il existe même des logiciels spéciaux pour cela (tels que Compilatio).

Toutefois, ces logiciels, en général, ne détectent que les plagiats de documents disponibles en ligne (ou fournis dans une base de documents privée, par exemple les mémoires publiés les années précédentes dans la même université) ; ils ne détectent pas les plagiats de documents publiés uniquement sous forme papier, ou uniquement disponible derrière des paywalls. Par ailleurs, même si ces logiciels existent, encore faut-il qu’ils soient utilisés. Si leur usage est maintenant obligatoire à la soumission d’une thèse dans certaines universités (dont la COMUE Université Grenoble Alpes), ce n’est pas le cas partout… et par ailleurs je ne les ai jamais utilisés lorsque j’évaluais des articles pour des revues ou des conférences, peut-être à tort.

Le copier-coller, facilement détectable par des moyens automatisés, est risqué. Aussi le plagiaire un peu moins naïf prendra soin de paraphraser le texte avec plus ou moins de servilité. J’ignore d’ailleurs à quel point d’éloignement du texte d’origine on ne peut plus parler de plagiat au sens usuel du terme, et où la justice jugerait qu’il ne s’agit plus d’une contrefaçon.

Dans le cas des publications scientifiques, il y a une autre forme de plagiat : le plagiat d’idées. Il s’agit de reprendre sciemment des idées d’autres personnes et de les faire passer pour siennes, sans pour autant reprendre des textes. Il ne s’agit alors plus d’une contrefaçon au sens du droit d’auteur, puisque les idées sont de libre parcours.

Relevons tout d’abord qu’il arrive souvent que les mêmes idées soient publiées par des auteurs différents en toute bonne foi. Le volume des publications scientifiques est considérable, on ne peut pas avoir tout lu sur un sujet. De plus la communauté scientifique est morcelée en disciplines, sous-disciplines et thématiques, de sorte que ce qui porte un nom et est expliqué dans un certain formalisme dans une thématique de recherche peut porter un autre nom et être expliqué autrement dans une autre thématique. J’ai assisté à des colloques dont le but était justement d’obtenir que des chercheurs de deux thématiques puissent se parler et se comprendre, et parfois on découvrait qu’un procédé utilisé dans un domaine était au fond le même que celui décrit sous un autre nom dans un autre domaine !

À d’autres époques, les barrières de langues ont également joué : un chercheur soviétique publiant en russe n’était pas forcément au courant de ce que des Canadiens publiaient en anglais, et vice-versa. (Il y avait d’ailleurs quand j’étais étudiant des rumeurs selon lesquelles des chercheurs occidentaux comprenant le Russe faisaient carrière en republiant des idées théoriques trouvées dans des comptes-rendus de l’époque soviétique ; je n’ai aucune idée de si cela est arrivé.)

Dans ces conditions, il est très possible pour des auteurs peu scrupuleux de prendre des idées déjà publiées et de les reprendre sous un autre nom et dans un autre formalisme. Pour prendre un exemple concret, un de mes travaux récents peut aussi bien être expliqué dans un formalisme de transformation de formules logiques que dans un formalisme d’interprétation abstraite, qui au fond veulent dire la même chose mais qui seront superficiellement différents ; à mon avis, deux auteurs différents auraient pu publier cette même idée sous ces deux formes et on ne s’en serait pas rendu compte, ou du moins seulement après réflexion. Qui plus est, il est toujours possible de plaider l’ignorance des travaux précédents, surtout avec les différences de vocabulaire et de formalisme !

La pire forme de plagiat d’idées dont j’ai eu vent m’a été rapporté par un chercheur, qui avait assisté à la scène suivante chez un « ponte » du domaine. Le mandarin, dans un comité éditorial, donnait à évaluer un article à un de ses doctorants en lui donnant comme consigne de le rejeter, mais de reprendre les idées pour les implanter et les publier. Des collègues, dans d’autres disciplines, ont évoqué le cas d’idées dans des demandes de financements, dont l’évaluation est en théorie confidentielle : les demandes ont été rejetées, mais les idées exploitées par d’autres.

Il est d’ailleurs parfois bon d’être prudent quand on discute d’idées non publiées avec des collègues. J’ai tendance à être plutôt ouvert et à dire sur quoi je travaille, mais cela n’est pas forcément une bonne idée. Des collègues qui avaient un peu trop bavardé en conférence ont eu la surprise de voir leurs idées publiées par leur interlocuteur ! Mon avis serait de se méfier de collègues qui posent beaucoup de questions sur les travaux en cours, mais sont évasifs concernant ce qu’ils font à ce sujet.

De la malhonnêteté scientifique en informatique

On a beaucoup parlé ces derniers temps de fraude scientifique. Toutes les « affaires » concernaient, me semble-t-il, la biologie ; j’aimerais ici esquisser ce qui pourrait relever de la fraude dans ma discipline, l’informatique, et des disciplines connexes.

En premier lieu, un avertissement. Lorsque l’on parle d’erreurs dans des publications scientifiques, on glisse parfois un peu rapidement de l’idée d’erreur à l’idée de fraude. Or, il est tout à fait possible de commettre des erreurs en toute bonne foi. L’idée d’erreur elle-même mérite d’être nuancée : l’erreur scientifique, du moins dans mon domaine, consiste souvent non pas en quelque chose de vraiment faux, mais plutôt en quelque chose qui n’a pas la portée que la publication laisse supposer ; je vais expliciter cela.

Mon sentiment général est d’ailleurs qu’il existe toute une gradation entre la publication la plus honnête et rigoureuse et la publication franchement frauduleuse, passant par diverses négligences, choix avantageux de cas d’études, exagérations, désir de ne pas trop explorer ce qui pourrait conduire à d’autres résultats… Tout ceci est d’ailleurs encouragé par le système de publication scientifique, de recrutement, de promotion et de financement des chercheurs ! Si j’écris un article où j’explique que ma méthode n’est qu’une amélioration de travaux précédents, produisant un gain modeste de performances et que je le soumets à une revue ou conférence de premier plan, il sera probablement rejeté ; si au contraire je présente mon approche comme très novatrice avec un gain important de performances, il sera accepté ; or de l’un à l’autre il n’y a qu’une question de présentation et de choix d’exemples... L’accumulation de publications « cotées » me permettra d’avoir un bon dossier pour demander une promotion, un financement, etc. (même si d’autres facteurs sont considérés).

Revenons à la question des publications en informatique. Il est périlleux de parler en généralités sur une discipline qui recouvre en réalité des sous-disciplines si diverses ; toutefois je ne pense pas me tromper en disant qu’un article ou une thèse d’informatique comprend en général :

  1. Une introduction (longue dans le cas d’une thèse, parfois très brève dans un article) présentant le domaine, les questions que l’on entend soulever ou résoudre, l’intérêt technologique, social ou économique de ces questions et des solutions apportées, les travaux scientifiques connexes, et un résumé des principales contributions.

  2. Des contributions théoriques : descriptions d’algorithmes, preuves de correction ou de complexité de ces algorithmes, définitions mathématiques, théorèmes mathématiques et preuves de ces théorèmes, etc.

  3. Une évaluation pratique, typiquement des chronométrages de temps de calcul sur une batterie d’exemples.

Voyons ce qu’il en serait des fraudes pour chacun de ces aspects.

Introductions d’articles

Dans les présentations de domaines scientifiques dans les rapports et thèses on trouve parfois des plagiats. En effet, ces présentations portent sur des généralités et non sur les travaux spécifiques de l’auteur, et il est tentant de reprendre des textes, schémas etc. trouvés dans d’autres documents. Il est toutefois périlleux de copier-coller depuis des documents trouvés sur le Web, car il est alors facile de retrouver les passages qui semblent « rapportés » ; cette recherche est d’ailleurs automatisée par des logiciels tels que Compilatio, installés dans les universités. Il est bien entendu plus délicat de retrouver la paraphrase ou l’inspiration non créditée. Il ne faut également pas crier au plagiat ou à l’« auto-plagiat » (reprise par un même auteur de textes identiques dans plusieurs publications, afin de multiplier celles-ci sans apport scientifique) si les textes similaires ne concernent que des définitions standard… il n’y a pas trente-six façons de dire, par exemple, qu’un treillis est un ensemble ordonné dont toute paire d’éléments admet une borne supérieure et une borne inférieure !

La présentation des questions résolues est parfois trompeuse (sciemment ou non). En effet, on peut très facilement faire apparaître un résultat comme ayant une portée plus importante qu’il n’en a réellement, par exemple en ne précisant pas certaines restrictions ou définitions ; par exemple, on peut dire que le résultat obtenu est « optimal », mais en ne précisant pas la notion d’optimalité ou complétude utilisée ou les hypothèses sous-jacentes, qui seront plus loin dans l’article. Le lecteur qui se limiterait à l’introduction pourrait en concevoir une idée plus haute des résultats que la réalité.

Les possibles applications technologiques, notamment dans les thèmes à la mode du moment, sont parfois exagérées. J’ai une fois été dans un comité de programme d’une conférence où nous avons accepté un article par ailleurs scientifiquement solide, mais à condition que les auteurs ôtent de leur introduction des perspectives d’applications trop distantes et incertaines.

L’exposé des travaux voisins est un art difficile. Si l’on oublie un travail pertinent, on risque de se faire des ennemis des auteurs vexés et de leurs amis ; cela peut être rédhibitoire. Toutefois, si l’on mentionne des travaux équivalents, la contribution pourra être considérée comme trop mineure. Il s’agira donc de rendre hommage à des travaux tout en expliquant que ce que l’on fait est mieux ou différent, mais si l’on dit trop que c’est mieux on risque de vexer, donc le mieux est d’expliquer que c’est différent. Tout ceci peut être un peu trompeur.

Résultats théoriques

Il paraît a priori difficile de tricher dans des preuves mathématiques : ce n’est pas comme une expérience que l’on peut inventer. Toutefois, il est possible de se tromper...

Un raisonnement mathématique est très rarement parfaitement rigoureux au sens que l’on expliciterait chaque recours à une définition ou à une règle de déduction. En effet, des preuves mathématiques rédigées à ce niveau de détail seraient interminables et incompréhensibles pour un lecteur humain (c’est d’ailleurs pourquoi, si on veut en arriver là, on a recours à un « assistant de preuve », un outil informatique qui vérifie la preuve à son plus haut niveau de détail). Une preuve mathématique usuelle passera au contraire rapidement sur des étapes de raisonnement que tout lecteur du domaine pourrait reconstituer et détailler si besoin.

Parfois, cela se voit à certaines tournures : quand l’on fait une hypothèse « sans perte de généralité », on veut que ramener le cas général au cas particulier étudié se fait par une transformation et une justification suffisamment simples pour que le lecteur ne voie pas de problème à ce qu’on les omette. Dans certains cas, on dira qu’une preuve est la même qu’une autre mutatis mutandis, c’est-à-dire « en changeant ce qui doit être changé »…

Parfois, malheureusement, on commet une erreur. On pense qu’une étape est évidente alors qu’il y a un problème, on prend des quantifications logiques dans le mauvais sens, on se mélange dans les indices, on applique un théorème en oubliant une de ses hypothèses… Georges Gonthier cite même le cas d’un théorème dont la preuve est fausse car s’appuyant sur une erreur d’imprimerie !

Si l’on peut se tromper ainsi de toute bonne foi, on peut certainement le faire volontairement. Il doit également exister des cas intermédiaires, du style « ce résultat semble se déduire de tel résultat dans tel article, et nous n’allons pas chercher la petite bête en vérifiant toutes les conditions au risque de tomber sur un os technique qui prendra du temps à résoudre » — autrement dit on ne commet pas sciemment une erreur, mais on est sciemment négligent au risque d’une erreur.

Pour prendre un exemple concret, il m’est arrivé d’évaluer un article où, dans une démonstration, les auteurs invoquaient un théorème « trop beau pour être vrai ». Je suis allé voir en bibliothèque le livre d’où ils tiraient ce résultat, j’ai vu qu’ils avaient omis en le citant une hypothèse, non vérifiée dans leur cas. Erreur volontaire ou involontaire ?

Par ailleurs, même si un résultat théorique est prouvé rigoureusement, il reste la question de son interprétation informelle, qu’il est possible d’exagérer ! En effet, un résultat théorique porte sur un modèle d’une partie de la réalité, modèle qui peut être imprécis voire passer à côté de l’essentiel, partie de la réalité qui peut être trop restreinte…

Résultats pratiques

Il s’agit ici en général de programmer les algorithmes proposés, puis de les essayer sur des jeux d’exemples afin d’évaluer leur efficacité et leur précision en pratique.

On peut être surpris du recours à une évaluation pratique dans le cas de l’algorithmique, puisque l’on fournit déjà des preuves mathématiques. Il y a plusieurs raisons pour ceci. Tout d’abord, deux algorithmes apparemment équivalents du point de vue de certaines analyses de complexité peuvent avoir des coûts très différents en pratique. Par ailleurs, dans certains domaines on sait que la complexité pire cas de tous les algorithmes est prohibitive, voire qu’il n’existe pas de procédé algorithmique qui fonctionne dans tous les cas : aussi on voudra distinguer différentes propositions suivant ce qui se passe sur des cas réalistes, quelle proportion de cas seront résolus en combien de temps.

Une première difficulté est donc de choisir des cas d’essais réalistes, au sens de représentatifs de ce que les utilisateurs du procédé algorithmique proposé voudraient pouvoir résoudre. Parfois on prend des exemples « synthétiques » plus ou moins aléatoires, mais rien ne dit que ceux-ci soient représentatifs des situations réelles ! Il est tentant de proposer comme exemples « représentatifs » ceux sur lequel l’algorithme proposé dans l’article est particulièrement efficace…

La constitution de bibliothèques d’exemples (SPECint, SMT-LIB etc.) pallie en partie ce problème mais en crée d’autres. En effet, les chercheurs visent alors à résoudre les exemples dans la bibliothèque et non ceux des situations réelles… On a même vu des concepteurs tenter de détecter certains des exemples standard et dans ce cas appliquer des procédures spéciales, un peu comme les véhicules Volkswagen qui détectaient qu’ils étaient sur le banc d’essai antipollution et appliquaient un programme spécial de carburation.

Se pose ensuite le problème de la comparaison aux autres méthodes. Ceci suppose soit de se procurer d’autres outils implantant les méthodes auxquelles on se compare (outils souvent indisponibles, non maintenus, sans documentation…), ou d’implanter soi-même les méthodes en question. Il est alors possible d’implanter ces méthodes de façon stupide, inefficace, tandis que la nouvelle à laquelle on les compare sera implantée intelligemment…

Ainsi, même en rapportant sincèrement des résultats d’expériences réellement conduites, il est possible d’induire le lecteur en erreur, du fait de la non représentativité de ces expériences. Il y a, à mon avis, toute une continuité entre les petites omissions et le choix d’exemples plutôt favorables à la nouvelle méthode et l’invention complète de résultats, comme on peut malheureusement le soupçonner dans le cas de certains articles.

De nos jours, certaines conférences d’informatique suggèrent fortement, voire dans certains cas imposent, la soumission d’artefacts, c’est-à-dire d’un composant logiciel intégrant les outils et les exemples permettant à une équipe d’évaluateurs de reproduire les résultats de l’article, voire d’essayer la méthode sur d’autres exemples. Bien entendu, ce n’est pas une solution totale, mais cela met un peu de rigueur dans le processus.

En conclusion

Il y a toute une gradation entre l’honnêteté complète et les résultats fabriqués. Certaines décisions sont parfaitement humaines et explicables : par exemple, si une méthode a une faiblesse, on va éviter de trop la souligner afin de ne pas donner des verges pour se faire battre… D’une façon générale, cela fait partie de l’exercice que de manifester un certain enthousiasme pour le nouvel algorithme proposé. De là l’on glisse à ne plus mentionner les faiblesses, à exagérer les points positifs, à sélectionner les exemples, à omettre de préciser certaines conditions de mesure… La pente est facile !

dimanche, octobre 7 2018

Sokal squared : une totale confusion

Les réseaux sociaux scientifiques bruissent d’un scandale : des chercheurs ont intentionnellement écrit des articles scientifiques ridicules, et qui auraient dû être rejetés par un comité éditorial un tant soit peu scrupuleux, et ont pu les faire publier dans des revues traitant notamment de questions de genre. Leur but était de démontrer que les revues de ces domaines scientifiques publient n’importe quoi à condition que ce n’importe quoi s’inscrive dans les bonnes thématiques, utilise le bon vocabulaire, les bonnes citations, et produise des conclusions conformes aux préjugés idéologiques du champ considéré, reprenant ici les objectifs et la méthode du fameux canular de Sokal.

Les réactions à cette annonce ont été sans surprise. Ceux qui estimaient que certains champs universitaires relèvent de l’opinion et non de la science, et masquent leur manque de justification scientifique sous un vocabulaire pompeux, ont été confortés dans leur opinion : voilà la preuve que leurs intuitions étaient bonnes ! D’autres, dans les champs de recherche visés ou dans des champs voisins, ont dénoncé une manœuvre politique de droite menée par des chercheurs eux-mêmes médiocres, ne démontrant rien, les revues visées n’étant pas centrales dans le champ du savoir visé. On retrouve là encore largement la polémique suivant le canular de Sokal.

Je ne désire pas ajouter du bruit à cette polémique, donc ne pas parler de ce cas d’espèce, mais seulement éclairer la question des publications de mauvaise qualité voire totalement bidon, et leurs conséquences sur le champ scientifique.

J’ai déjà évoqué ici le cas des revues et conférences totalement bidon. Celles-ci ne sélectionnent pas du tout les articles qu’elles acceptent — on a vu des articles générés aléatoirement être acceptés — et visent un but lucratif (frais d’inscription, frais de publication). Elles ne posent finalement guère de problèmes : certes, des fonds ont été dépensés pour aller en conférence à Orlando ou Las Vegas, mais cela ne représente pas une part importante des budgets de recherche ; par ailleurs, la mention de telles publications, dans un dossier de demande de financement ou de promotion ou dans un bilan de laboratoire, vaudra en général des conséquences négatives. Il y a donc des incitations fortes à ne pas publier dans de tels lieux, du moins dans les institutions de recherche dotées de procédures d’évaluation un tant soit peu sérieuses.

Toutefois, dans le cas de l’affaire Sokal ou de la récente affaire sur les études de genre, il ne s’agissait apparemment pas de ces revues totalement bidon et à but lucratif, que personne ne prend au sérieux, mais de revues scientifiques reconnues comme telles, dont certaines étaient éditées par des universités prestigieuses ou recevaient des articles de chercheurs de ces universités. Il me semble qu’il ne s’agit pas de la même question. Voyons donc les problèmes qui se posent si des revues considérées comme sérieuses, même si « peu centrales », publient des articles qui n’auraient pas dû être publiées.

Le premier problème, à mon avis le plus important, serait que des gens se basent sur des conclusions insuffisamment étayées pour guider des activités dont le dysfonctionnement aurait des conséquences sensibles : par exemple, une étude médicale ou pharmaceutique erronées pour prescrire un traitement, un algorithme incorrect utilisé dans un produit ou service, ou encore promouvoir une réforme économique ou sociale… Normalement, on ne base pas un projet avec des conséquences humaines ou financières importantes sur un article scientifique sans l’étudier en profondeur (examiner chaque justification et non seulement les conclusions) et/ou valider soi-même l’utilisation envisagée ; plus généralement on s’en remet plutôt à des articles de revue, résumant les travaux de plusieurs chercheurs, ou des monographies résumant l’état de l’art.

A priori, l’impact d’un article erroné isolé est donc très limité. Toutefois, il arrive parfois que des conclusions erronées soient reprises dans d’autres articles, et finissent, à force d’être reprises partout, par être considérées comme fiables, alors que tout remonte en fait à une unique source originale incorrecte. Richard Feynman cite ainsi (The Seven Percent Solution, dans Surely you’re joking Mr Feynman) le cas d’une extrapolation erronée dans une étude expérimentale sur la désintégration β, reprise par toute une communauté scientifique qui se demandait comment faire coïncider des modèles et des résultats expérimentaux qui différaient… jusqu’à ce que Feynman eût des doutes, reprît les citations et les calculs depuis l’origine et s’aperçût de l’erreur. Il n’est donc pas à exclure que des idées erronées, reprises par une communauté qui se cite elle-même, aient été mises en place dans des politiques publiques ou dans des protocoles médicaux.

Outre ce problème pour la société en général, il y a un second problème, interne au monde scientifique. Les postes de chercheurs et les financements sont en quantité limitée, de sorte que ceux qui sont attribués à un sujet ne le sont pas à un autre. Un domaine de recherche médiocre et qui s’auto-entretient par des citations, invitations d’articles, et renvois d’ascenseurs divers peut nuire à la science en général de part les ressources qu’il accapare. Ces inconvénients internes au monde scientifique peuvent d’ailleurs produire des effets qui lui sont extérieurs : obligation pour des étudiants de suivre des cours sur la théorie évoquée, voire d’être notés en fonction de leur adhésion à celle-ci ; mise en place de politiques publiques ou de procédures médicales suivant les prescriptions du champ (le Lyssenkysme est un cas exacerbé de ce phénomène, étant soutenu par un pouvoir totalitaire). Tout ceci relève donc de problèmes systémiques, mettant en jeu un champ scientifique et non telle ou telle revue dysfonctionnelle.

Il me semble que certaines analyses qui ont été faites suite à des publications scandaleuses mélangent des phénomènes sans grand rapport les uns avec les autres. Par exemple, si l’accusation est l’existence d’un système de promotion de recherches sans valeur scientifique à l’intérieur de certaines disciplines dans le monde universitaire occidental, il n’est pas pertinent de pointer la publication d’articles générés aléatoirement dans des revues totalement bidon et reconnues comme telles d’un champ de « sciences exactes ».

mercredi, août 15 2018

Absence de hiérarchisation

Je lis souvent que ParcourSup ne demanderait pas de « hiérarchisation des vœux » aux candidats, et que cela expliquerait certaines décisions surprenantes de ce processus (e.g. mettre en géographie un candidat qui voudrait faire des mathématiques). Le sous-entendu est qu’en l’absence de hiérarchisation, le processus affecte les candidats sans tenir compte de leurs préférences.

Or, ParcourSup, même si cela est moins évident que pour APB, suppose une certaine hiérarchisation des vœux par le candidat ! En effet, à chaque étape de ParcourSup où il se voit proposer des offres fermes, le candidat doit désigner parmi ces offres fermes celle qu’il préfère, et démissionner des autres.

La différence avec APB est qu’avec APB on demandait au candidat de classer au préalable tous ses vœux par préférences décroissantes, alors qu’avec ParcourSup on ne l’interroge que sur certaines comparaisons de préférences, celles effectivement nécessaires au fonctionnement du processus. Par comparaison, APB exigeait des informations dont il n’aurait pas besoin (si on est classé trop loin par une formation pour y avoir une place, les comparaisons de préférence entre cette formation et les autres n’ont aucune importance et ne sont pas consultées par l’algorithme).

J’ai de grandes réserves quant à un processus qui exige de multiples étapes de consultation où les candidats doivent impérativement avoir une connexion Internet fiables, et ne donne que tardivement des affectations définitives tant aux formations qu’aux candidats, d’où des difficultés à s’organiser. Il ne faut cependant pas confondre la lenteur de convergence d’un processus avec le calcul d’un résultat arbitraire.

mercredi, juillet 25 2018

L'incroyable étant réel, où finit le plausible ?

J’ai expliqué être opposé aux machines de vote électronique car j’estime qu’en cas de contestation, il serait impossible à l’expertise technique de convaincre les électeurs de l’absence de tricherie. On m’a demandé s’il ne s’agissait par là d’une forme de renoncement.

Le scientifique doit-il renoncer à son expertise au motif que des complotistes pourraient l’accuser de malhonnêteté ? La raison doit-elle s’incliner devant la croyance et la partialité politique ? Sans doute non. Toutefois, rejeter toute méfiance comme relevant du complotisme irrationnel, et donc à ignorer, est à mon avis une mauvaise analyse.

Si l’on m’avait dit, il y a quelques mois qu’un proche du Président de la République se faisait passer pour un policier pour pouvoir rouer de coups des manifestants, peut-être par sadisme, j’aurais dit qu’il s’agissait d’un excellent scénario pour un film censé se passer dans une dictature sud-américaine des années 1970, mais que c’était « trop gros » pour se passer en France. Et pourtant, des choses « trop grosses » se sont passées, avec des complicités multiples.

L’incroyable d’hier est devenu le réel d’aujourd’hui. Si pareilles choses sont possibles, il est rationnel de penser que d’autres, moins visibles, le sont, et il est donc rationnel d’être méfiant !

mardi, juillet 24 2018

Intelligence artificielle et calculabilité

À une récente demi-journée d’études sur intelligence artificielle et sciences humaines et sociales, deux intervenants ont soulevé la question de la calculabilité et de l’indécidabilité. Un échange de courriels s’est ensuivi, notamment avec mon collègue Denis Trystram. Je vais résumé ici ma position, qui me semble la même que celle de Denis.

La théorie de la calculabilité établit des bornes à ce qui est calculable par un algorithme, par une version idéalisée d’un ordinateur. Comme résultats notables on a :

  1. Quelle que soit la propriété que l’on veut vérifier sur un programme, plus précisément sur la relation entre les données fournies en entrée et le résultat du calcul, il n’existe aucun algorithme qui permette de décider à coup sûr si un logiciel la vérifie. Autrement dit, il n’existe aucun algorithme capable de décider si un logiciel est correct au vu du code du logiciel. (Théorème de Rice, extension du théorème de l’arrêt de Turing.)

  2. Il n’existe aucune procédure qui dise si un énoncé mathématique est vrai ou faux. (Je simplifie beaucoup, pour plus de précision voir les énoncés des théorèmes d’indécidabilité de Gödel, et aussi le théorème d’indéfinissabilité de Tarski.)

Cette théorie est complétée par celle, un peu plus récente, de la complexité, qui établit notamment qu’il y a des problèmes pour lesquels il existe certes des algorithmes, mais forcément de coût prohibitif.

On a parfois prétendu que ces théorèmes établissent la supériorité de l’esprit humain sur la machine et, comme dans ce colloque, on s’est interrogé sur le lien avec l’intelligence artificielle.

Si, par le passé, on a rangé dans l’intelligence artificielle la réponse à des problèmes dont la définition était très strictement posée en termes mathématiques (démontrer des théorèmes, gagner aux échecs…), l’attention actuelle porte sur des problèmes qui, justement, ne sont pas définis mathématiquement et où l’enjeu consiste en fait à extraire une forme de définition d’une accumulation d’exemples (par exemple, on va apprendre à la machine à reconnaître un mouton en lui montrant une grande quantité de photographies et en lui disant lesquelles contiennent des moutons). Il s’agit par ailleurs souvent de problèmes flous, où il y a des cas tranchés et d’autres où plusieurs réponses seraient admissibles.

Les théorèmes de calculabilité et de complexité ne s’appliquent qu’à des propriétés bien définies mathématiquement. Par exemple, le fait qu’un problème soit de complexité élevée exclut qu’il existe un algorithme efficace dans tous les cas, mais n’exclut pas qu’il existe un algorithme efficace en pratique sur les cas industriellement utiles, car le concept de « cas industriellement utile » est mal défini.

Le rapport entre les questions d’intelligence artificielle proprement dites étudiées actuellement et les résultats classiques de calculabilité ne me semble donc pas évident.

dimanche, juillet 22 2018

La grande incertitude de la recherche mathématique

Quelle différence y a-t-il entre l’enseignement et la recherche en mathématiques ? Bien évidemment, il y a une différence de degré d’abstraction et de technicité entre l’enseignement, a fortiori secondaire, et la recherche. Je pense toutefois que la différence la plus importante est que lorsque l’on est élève, on sait ce que l’on doit faire, alors qu’en recherche, non.

Lorsqu’un·e enseignant·e pose un problème de mathématiques, il ou elle a en tête une façon de le résoudre en n’utilisant que les connaissances que l’étudiant·e est censé·e avoir à ce moment, et la décompose en étapes telles que chacune soit faisable sans trop de questionnements. C’est ce qui permet de poser en travaux dirigés, voire en examen, ce qui a jadis été une question de recherche. Par exemple, j’ai une feuille de travaux dirigés presque faisable en deux heures pour de bons étudiants où l’on démontre le théorème de complétude de la logique du premier ordre, lequel constituait pourtant la thèse de doctorat du célébrissime logicien Kurt Gödel.

À l’opposé, en recherche (à tout niveau), on ne sait en général pas si le résultat que l’on compte prouver est vrai, puisque c’est la démonstration que l’on cherche qui établirait cette vérité (il arrive toutefois que l’on cherche à redémontrer un théorème par une autre méthode, ce qui peut être instructif). Bien entendu, on ne va pas à l’aveuglette, on est guidé par des indices : par exemple, si des calculs numériques (approximés) semblent indiquer qu’une quantité est nulle, il est raisonnable d’essayer de le démontrer. Il est cependant périlleux de conclure que parce qu’une chose semble vraie elle l’est forcément, et plusieurs conjectures qui semblaient raisonnables ont été par la suite démontrées fausses.

Plus profondément, le mathématicien en recherche non seulement ne sait pas si le résultat qu’il cherche à démontrer est vrai ou faux, mais doit en premier lieu poser les bonnes questions, les bonnes définitions. Il ne s’agit donc pas simplement de réaliser un « tour de force » en démontrant un résultat, mais surtout de construire un édifice conceptuel (que l’on nomme souvent théorie : théorie des distributions de Laurent Schwartz, théorie de Ramsey, etc.). Pour ma part, je n’en suis pas là : je démontre modestement des petits résultats.

Quelques exemples de ce phénomène en action. Il y a quelques années, je m’étais demandé si la raison pour laquelle on avait proposé tant de méthodes partielles pour inférer ce que l’on appelle des invariants inductifs polyédraux n’était pas qu’il ne peut exister de méthode algorithmique totale. Ce problème traînait dans mon esprit. J’ai démontré un résultat plus faible que celui que j’aurais voulu ; mais peut-être est-ce que parce que le résultat plus fort serait faux ? Je n’en sais rien ! J’ai interrogé des collègues (Olivier m’a dit de demander à Joël, Joël m’a dit de demander à Olivier, etc.) ; personne ne savait comment prendre la question. De guerre lasse, plusieurs années plus tard, j’ai fini par publier mon résultat trop faible à mon goût.

Actuellement, Valentin Touzeau, doctorant, et moi-même tentons de démontrer des résultats sur la complexité de certains problèmes, c’est-à-dire leur degré de difficulté lorsqu’il s’agit de les résoudre par un algorithme (je simplifie). Avant de nous lancer là-dedans, nous ne savions pas quels résultats nous pourrions prouver (si ce n’est quelques bornes larges et évidentes pour qui connaît ce genre de questions). J’ai pu prouver qu’un des problèmes en question est NP-complet (c’est une des classes de complexité), et Valentin me dit qu’il a une idée pour montrer qu’un autre de ces problèmes est PSPACE-complet (c’est une autre classe). Je suis très excité par cette perspective, mais je reste prudent : nous ne devons pas crier victoire tant que nous n’avons pas une preuve rédigée au propre !

Si je suis excité, c’est parce que le résultat ainsi démontré correspondrait à une intuition souvent citée par les gens qui proposent des algorithmes pour résoudre partiellement les problèmes en question pour expliquer pourquoi le second est plus difficile que le premier. Mais je n'en sais toujours rien.

samedi, juillet 21 2018

Politiques publiques et Internet : 2006-2018, rien ne change

Le Parlement européen n’a pas adopté un projet de directive sur le copyright. Les réactions, suite à cette décision, m’ont rappelé celles au moment du projet de loi DADVSI en 2006, puis du projet de loi HADOPI, ou encore celles autour de Wikipédia. On peut même dire qu’elles étaient très prévisibles ! Je les analyse au prisme du rapport légitime au pouvoir que certains groupes exercent, et leur disqualification des autres points de vue.

Lors de l’examen des projets de loi DADVSI et HADOPI, certains avaient dénoncé les campagnes de courriers et messages hostiles au projet de loi, les décrivant comme des « pressions » intolérables envers les élus. S’agit-il de dire que de simples citoyens, certes nombreux, n’ont pas à se mêler du processus législatif ? Pourtant la Déclaration de 1789 dit « La Société a le droit de demander compte à tout Agent public de son administration. »…

Dans le même temps, les industriels du secteur, les sociétés professionnelles, les intermédiaires (notamment les sociétés de perception et répartition des droits, les SPRD) ne se privent pas d’interventions auprès des élus. Ainsi, un assistant parlementaire m’avait expliqué, à l’époque, que la sénatrice qui l’employait avait construit sa carrière sur sa proximité avec ce milieu et qu’en conséquence il ne fallait pas s’attendre à ce que, quels que soient les arguments entendus, elle n’en adopte pas les propositions. On se rappellera également d’amendements présentés simultanément et séparément par des parlementaires de plusieurs groupes, dont on peut donc raisonnablement penser qu’ils étaient suggérés, argumentaires compris, par des groupes défendant des intérêts privés — on attribuait certains amendements au groupe Vivendi Universal, j’ignore ce qu’il en était. On se rappellera également qu’Alain Suguenot, député-maire de Beaune, avait fait état de pressions contre lui (menaces de retrait des professionnels d’un festival à organiser dans sa ville).

Comment analyser cette disparité de traitement ? Il y a d’un côté des messages légitimes, émis par des groupes qui estiment normal d’avoir accès aux élus pour faire valoir leurs intérêts, et de l’autre des messages illégitimes. Lorsque ces derniers sont entendus, ceux qui s’estiment les seuls à avoir droit au chapitre expriment publiquement leur indignation.

Selon un argumentaire bien rôdé, les groupes s’opposant à certains projets ou soutenant certaines mesures qui n’agréent pas aux industries culturelles seraient forcément financés par les « GAFA » (Google, Amazon, Facebook, Apple, et plus généralement les grandes entreprises de l’Internet, souvent américaines). Là encore, l’accusation n’est pas neuve : on se rappellera que certains accusaient Wikipédia d’être financée par Google !

S’il est légitime de s’interroger sur les financements de certaines associations intervenant dans le débat politique, pourquoi serait-il illégitime de s’interroger, par exemple, sur les éventuelles activités libérales de certains universitaires (économistes, juristes) intervenant dans ce débat, susceptibles de donner lieu à conflit d’intérêts ? Pourtant, on n’entend jamais ces questions dans les médias. Là encore, il paraît légitime de suspecter certains (même si l’on n’a pas le moindre début de preuve), et illégitime de s’interroger sur d’autres tant est grande leur respectabilité.

Un autre argument classique est que les nouveaux circuits du divertissement permettent à certains intermédiaires (Google, etc.) de s’enrichir indûment. Il est très possible que cela soit le cas ; ce n’est pas mon propos d’en disputer ici. En revanche, il est très intéressant de constater que ceux qui se plaignent de ces nouveaux circuits et s’interrogent sur la destination des profits ainsi réalisés refusent tout débat sur la destination des profits réalisés par les circuits plus classiques. Il me semble d’ailleurs (mais je peux être mal informé) qu’il règne une grande opacité sur la répartition des profits entre les artistes et les industries et intermédiaires. Cela est d’autant plus regrettable que dans les débats, on n’a à la bouche que la préservation des artistes et de leurs revenus, et qu’on ne manque pas de témoignages d’artistes, au fil des décennies, se plaignant d’avoir été exploités par leur maison de disques, leur producteur, etc. Un débat éclairé ne peut se contenter d’arguments dénonçant une évolution récente sans pour autant analyser la situation antérieure. Là encore, la situation antérieure est présumée légitime, l’évolution illégitime.

Enfin, revient l’accusation que les groupes opposés à certaines réglementations concernant Internet seraient des « anarchistes ». Accusation commode, l’anarchie étant censée être une option politique extrême et irréaliste — la ficelle est ancienne ! Là encore, l’idée sous-jacente semble être que les seuls points de vue politiques légitimes sont ceux consistant à ajuster les paramètres du jeu social en faveur des grands intérêts préexistants.

Ainsi, les débats politiques autour d’Internet sont globalement prévisibles : les positions, les postures, des uns et des autres sont connues. Le cadre dirigeant de SPRD parle au nom des artistes avec l’aplomb de celui qui estime qu’on doit l’écouter et accéder à ses demandes. Les activistes d’Internet, les « gusses dans un garage » selon une expression d’une ministre de la culture, crient à la censure. Les premiers accusent les seconds de faire le jeu des GAFA. Rien ne change !

Ce qui devait arriver est arrivé

Mes lecteurs savent qu’une des principales raisons pour lesquelles je suis opposé au vote électronique pour les élections à grands enjeux, c’est que s’il devait y avoir une contestation (allégations de « piratage » ou de malversations), les experts scientifiques et techniques seraient placés dans une situation impossible : leurs propos seraient incompréhensibles pour le grand public, des gens relèveraient comme scandaleuses de simples remarques techniques, et on attribuerait le jugement des experts à leurs préférences politiques.

La polémique autour du système « ParcourSup » d’attribution des places dans l’enseignement supérieur illustre bien mes craintes : il s’est passé ce que je craignais comme ci-dessus. Des gens se répandent sur les réseaux sociaux en expliquant que très certainement mes collègues Claire Mathieu et Hugo Gimbert, concepteurs (à un degré que j’ignore) de ce système, sont « macronistes ».

Je ne suis aucunement surpris. À une autre époque, des gens avaient émis l’hypothèse que j’étais des amis d’Alain Finkielkraut car j’avais enlevé de sa biographie Wikipédia l’affirmation qu’il était un journaliste d’extrême-droite (je n’ai vu Alain Finkielkraut en chair et en os qu’une fois dans ma vie et n’ai jamais parlé avec lui), ou encore que j’avais corrigé la biographie de Monique Canto-Sperber au motif que je lui étais redevable au motif que je lui aurais dû ma place au LIENS (quiconque sait comment fonctionne le CNRS sait que cela est une idée délirante). Plus récemment, j’ai vu des tracts expliquant (je résume rapidement) que mon laboratoire fait des recherches militaires utilisables par Frontex (là encore, quiconque sait ce que nous faisons rira jaune).

Devant l’impossibilité d’un débat serein, devant l’omniprésence des attaques ad hominem, le plus simple me paraît être d’éviter le recours à des dispositifs d’intérêt douteux et qui susciteront le doute quant au processus démocratique, doute qui ne sera pas levé par les explications des spécialistes.

samedi, juin 2 2018

Algorithme vs logiciel

Lors des débats actuels sur ParcourSup, ou à des discussions antérieures au sujet d’« algorithmes » utilisés à différentes fins en rapport avec la société, j’ai vu des questions sur la différence entre « algorithme » et « logiciel ». Je vais ici tenter d’expliquer les différences et similarités entre ses deux concepts.

Prenons un exemple simple : nous avons un tableau de nombres (par exemple 16, 3, 45, 2, 7, 32, 42, 51) et nous voulons les classer par ordre croissant. Ceci est la spécification de notre algorithme : nous spécifions ce que nous désirons obtenir.

Un algorithme possible pour cette tâche de tri est le suivant : on recherche dans le tableau le plus petit nombre, on l’intervertit avec le nombre en première position, puis on recommence pareil sur le reste du tableau privé du premier élément, puis sur le reste du tableau privé du deuxième élément, et ainsi de suite jusqu’à la fin du tableau. (On le connaît dans les cours d’algorithmique sous le nom de tri par sélection.)

Voyons maintenant pourquoi cet algorithme est correct, c’est-à-dire qu’il fait bien ce que nous voulons. Tout d’abord, la sortie est triée : on a bien le plus petit nombre en premier, puis le plus petit parmi les nombres restants, etc. Par ailleurs, cette sortie a bien le même contenu que l’entrée, ce sont bien les mêmes données dans un autre ordre, puisqu’on ne procède que par permutations.

Remarquons que la description de cet algorithme est incomplète : je n’ai pas dit comment je recherche le plus petit nombre dans le tableau. C’est parce que la méthode précise par laquelle je recherche ce plus petit nombre importe peu pour garantir le bon fonctionnement de mon algorithme de tri : ce qui importe c’est qu’on me donne ce nombre, ou plus précisément sa position dans le tableau. J’écris pour que des humains me lisent, je ne vais pas les surcharger de détails !

En revanche, si je programme un logiciel qui procède à un tri, je suis bien obligé de régler tous les détails : comment le tableau est stocké dans l’ordinateur, quelle procédure de recherche du plus petit élément j’utilise. La langue naturelle est imprécise et par ailleurs difficile à faire comprendre par un ordinateur, aussi je décris mon logiciel dans un langage de programmation qui me permet de décrire précisément les étapes de calcul que je désire faire effectuer par l’ordinateur.

Notons qu’un logiciel complet ne se limiterait pas à un unique algorithme : il faut une interface utilisateur (dont l’affichage nécessiterait d’autres algorithmes), des traitements de situations d’erreurs, etc. Tout ceci peut paraître facile et de peu d’intérêt, mais il me semble que, dans la grande majorité des logiciels, la plus grande partie du code du logiciel concerne ces aspects et non des algorithmes délicats.

Revenons à notre algorithme de tri. Étant donné un tableau de nombres passé en entrée, il n’existe qu’une seule sortie permise par la spécification : un tableau avec le même contenu mais trié dans l’ordre. Peu importe la façon dont on a procédé ! Imaginons maintenant qu’il s’agisse d’un tableau de noms d’élèves avec leurs notes, que l’on va trier par notes croissantes. Nous n’avons pas dit comment départager les ex-æquo, aussi, suivant l’algorithme de tri utilisé, nous pourrions avoir plusieurs sorties possibles dans ce cas. Notre spécification est alors incomplète.

Lorsque la spécification est complète (on a complètement défini d’avance le résultat attendu), ni le choix de l’algorithme ni les détails de fonctionnement du logiciel ne nous importent, puisque, quelle que soit la façon dont on s’y prend, il y aura toujours le même résultat au bout. Il nous faut toutefois nuancer cette affirmation.

Le choix de l’algorithme et les détails de fonctionnement du logiciel ont leur importance en ce qui concerne le temps de calcul. Par exemple, l’algorithme de tri que j’ai décrit ci-dessus est très mauvais sous cet aspect : le nombre d’opérations qu’il nécessite croît avec la taille du tableau d’entrée beaucoup plus vite que le nombre d’opérations utilisées par d’autres algorithmes, de sorte que son coût serait prohibitif sur une grosse base de données (et donc une personne compétente ne l’emploiera jamais que sur de petits tableaux).

Par ailleurs, nous pouvons aussi soupçonner qu’il y a des écarts entre l’algorithme « idéal » décrit sur le papier, et ce qui a été effectivement mis en œuvre dans le logiciel, qu’il s’agisse de « bugs » involontaires ou d’altérations censées répondre à certaines contraintes mais pas forcément bien maîtrisées. Il ne suffit donc pas d’avoir la spécification ou l’algorithme idéal pour vérifier qu’un logiciel répond à la demande.

PS On me souffle des analogies : l'algorithme c'est le plan, la théorie; le logiciel, la réalisation, la pratique. La mienne : l'algorithme c'est un thème musical, le logiciel c'est l'interprétation complète d'un morceau comportant plusieurs thèmes orchestrés.

mercredi, mai 30 2018

APB, ParcourSup et les méchants algorithmes

Voici ce que je comprends d'APB et ParcourSup, expliqué en termes compréhensibles du grand public. Merci de me corriger en cas d'erreur.

« Dans le temps », quand on passait les concours de certaines grandes écoles, celles-ci établissaient une « liste principale » d'admis et une « liste complémentaire ». Les admis sur la liste principale étaient appelés, et s'ils démissionnaient (habituellement, parce qu'ils étaient admis dans une autre école qu'ils préféraient), on appelait des candidats sur la liste complémentaire, qui eux-mêmes pouvaient démissionner. Bref, si l'on était sur la liste principale on savait que l'on était admis, mais on en était aussi quasi sûr si on n'était pas trop loin sur la liste complémentaire, au vu de ce qui s'était passé les années précédentes.

Le procédé était toutefois laborieux : tout n'était pas centralisé (il me semble qu'il y avait un service Minitel, mais pour certains concours seulement) et il y avait, au moins pour certaines écoles, des courriers papier qui s'échangeaient (on recevait une convocation pour admission et il fallait répondre par courrier pour démissionner). Tout ceci faisait que certains candidats étaient finalement admis en septembre, à quelques jours de la rentrée, en général dans un établissement éloigné du logement parental. Heureusement que ces établissements sont dotés de résidences !

Une première amélioration consiste à tout centraliser sur un unique service télématique, au lieu d'utiliser des courriers et des services séparés. Par ailleurs, pour assurer une réponse raisonnablement rapide, il faut empêcher qu'un étudiant hésitant puisse bloquer les autres, donc on va exiger qu'entre plusieurs offres fermes d'admission il ne puisse en choisir qu'une (sa préférée parmi celles proposées), et ainsi libère les autres. C'est le fonctionnement de ParcourSup.

Notons qu'avec ce système, il n'y a pas obligation de se désister de formations sur lesquels on est encore en attente, même si l'on sait que l'on est admis sur une formation qu'on leur préfère ; on me dit que certains lycéens tergiversent ainsi, ce qui prolonge les incertitudes des autres.

On peut alors se demander pourquoi demander au candidat à chaque fois de choisir sa préférée parmi les offres fermes déjà proposées, alors qu'il suffirait de lui demander une fois pour toutes son ordre de préférence : le programme peut alors répondre de lui-même à la question de l'offre préférée parmi celles présentées, et on peut affecter rapidement les étudiants dans les formations sans avoir à leur poser des questions à plusieurs reprises. C'est le fonctionnement de l'algorithme à la base d'APB (algorithme de Gale & Shapley version « optimale pour les universités »).

Si tout est si simple et compréhensible, pourquoi toutes ces controverses sur l'opacité des algorithmes, les tirages au sort etc. ? Tout d'abord, sur APB.

APB concernait des formations sélectives et non sélectives. Les formations sélectives classent leurs candidats et peuvent en refuser certains, les formations non sélectives (la plus grande partie des licences universitaires) ne le peuvent pas, et doivent donc a priori accepter tout candidat avec le baccalauréat — quel que soit la série de celui-ci et l'adéquation avec les études envisagées. Cependant, une formation non sélective peut avoir une limite de capacité, ne serait-ce qu'en raison de contraintes de locaux, d'équipements et de personnels enseignants. Dans ce cas, APB départageait les candidats par tirage au sort.

Il n'y a évidemment aucune fatalité à devoir utiliser un tirage au sort si l'on utilise un algorithme d'affectation. En revanche, si, suite à des décisions politiques (refus d'accorder plus de moyens, refus de classer ou sélectionner les candidats) on se retrouve avec plus de candidats que de places, il faut bien un moyen pour les départager, qu'on utilise un procédé automatisé ou non.

On dit que l'algorithme d'APB donnait un bonus au premier choix des candidats. On dit également qu'au moins certaines années, les formations étaient informées du classement que le candidat leur attribuait. Ceci fausse les bonnes propriétés de l'algorithme de Gale & Shapley. On peut éviter tout doute à ce sujet en demandant aux candidats leurs préférences quant aux formations sur lesquelles ils candidatent après que celles-ci aient rendu leurs classements.

Par ailleurs, ni APB et ParcourSup ne sont strictement basés sur un classement (fût-il obtenu par tirage au sort). Ils prennent en compte des critères de résidence, de taux de boursiers, et de places en internat. Tout ceci complexifie considérablement le problème à résoudre et éloigne le fonctionnement de l'algorithme des principes simples évoqués plus haut.

Enfin, dans le cas de ParcourSup, ainsi que dans le cas des formations sélectives pour APB, il y a la question du classement des candidats par les formations. Dans les concours classiques des grandes écoles, ce classement est obtenu par des écrits anonymisés et des oraux menés par un jury restreint, avec des harmonisations et des coefficients connus et publiés d'avance. Dans le cas de ParcourSup, on se base sur des notes de lycée non harmonisées, des appréciations d'enseignants, des lettres de motivation, selon des processus tenus secrets que l'on a parfois qualifiés d'« algorithmes locaux » — c'est un bien grand mot pour désigner ce qui, dans certains cas en tout cas, est un classement selon la moyenne avec coefficients de certaines notes de lycée.

samedi, mai 26 2018

Un humain tellement inhumain

La ministre de l’enseignement supérieur et de la recherche, Mme Frédérique Vidal, a expliqué qu’un des buts de ParcourSup par rapport à APB est de « remettre de l’humain » ; à l’opposé certains jugent « inhumain » le nouveau processus. Humain, inhumain, voilà qui mérite une petite analyse de vocabulaire.

Clairement, Mme Vidal considère qu’un processus plus humain est intrinsèquement meilleur, comme, dans d’autres contextes (alimentation, pharmacie), on considère souvent de nos jours que ce qui est « naturel » est intrinsèquement meilleur. L’« humain », le « naturel », sont considérés comme bons, par opposition à l’automatique, à l’artificiel, considérés comme mauvais.

Pourtant, quoi de plus humain, pour un·e enseignant·e, que de « saquer » une élève jugée « trop sûre d’elle pour son propre bien » car elle a d’excellentes notes dans d’autres disciplines, ou encore un étudiant dont les options politiques ou syndicales déplaisent ? Quoi de plus humain que de noter favorablement, même inconsciemment, un élève que l’on juge agréable ? Quoi de plus humain, pour des étudiants s’estimant mal notés, que de soupçonner l’existence de favoritisme ou de discrimination ?

Pour toutes ces raisons, on a très largement adopté dans l’enseignement supérieur, les examens et les concours, la correction sur copies anonymes. Pourtant, n’est-il pas déshumanisant de remplacer le nom de l’étudiant par un numéro d’ordre ?

Ainsi, ce qui est plus humain, au sens d’une plus grande intervention des sentiments et jugements humains, n’est pas forcément plus juste ou meilleur… ni même d’ailleurs plus humain au sens de respectueux de la dignité humaine.

Quant à ParcourSup, on soutient parfois qu’il s’agit d’un processus plus humain que l’algorithme APB parce qu’il pose des questions successives aux candidats au lieu de les affecter à la suite d’un calcul à partir de l’ordre de leurs préférences. Là encore, on semble considérer qu’il est meilleur d’impliquer l’humain à chaque étape plutôt que de lui demander de se fier au résultat ultime d’un calcul qu’il n’effectue pas lui-même. Attitude curieuse ! Comme si une moyenne de notes calculée à la main était plus humaine qu’une moyenne calculée à l’aide d’un tableur. De fait, l’allongement de la durée du processus due à l’attente des réponses des candidats, bref de leur facteur humain, conduit à une attente et une angoisse que certains jugent inhumaine.

Ainsi, cet argument de l’humanité du nouveau processus confond plusieurs sens de « humain » : « Qui appartient à l'homme, qui lui est propre » (on demande une intervention du candidat à chaque étape », « Qui épouse pleinement la nature humaine dans ses qualités et ses défauts » (y compris la subjectivité de son jugement), et « Qui est sensible à la pitié, qui fait preuve d'indulgence, de compréhension envers les autres hommes ». C’est ainsi qu’avec un processus humain selon les deux premiers sens celui-ci peut s’avérer inhumain au sens du troisième.

samedi, mars 17 2018

Ma gestion des conflits d'intérêts

Dans la recherche scientifique, nous avons souvent à nous préoccuper de conflits d’intérêts. On pense évidemment à ceux des chercheurs qui travaillent sur un sujet tel que les produits pharmaceutiques, les pesticides, etc., où il y aurait intérêt à biaiser les résultats des études en faveur de tel ou tel industriel qui financerait les recherches, ou emploierait par ailleurs le chercheur comme consultant (on en trouve facilement des exemples dans l’actualité). Dans mon domaine de recherche, ces problèmes ne se posent guère. En revanche, se pose souvent le problème des conflits d’intérêts lorsqu’il s’agit d’évaluer leurs collègues ou leurs travaux.

Les travaux scientifiques sont évalués avant leur publication en revues, comptes-rendus de conférence, ou ouvrages, du moins chez les éditeurs scientifiques sérieux : le travail répond-il aux standards de qualité de sa discipline ? Quant aux scientifiques (au sens large, j’inclus les universitaires de toute discipline), ils sont évalués, à divers points de leur carrière. Les évaluateurs sont, habituellement, des scientifiques plus ou moins du même domaine (pour évaluer une publication très technique, on prendra des spécialistes, alors que pour évaluer une carrière on pourra prendre des évaluateurs plus loin thématiquement). Fatalement, ces évaluateurs connaissent parfois les auteurs des articles, les candidats aux promotions. Certains critiquent d’ailleurs un fonctionnement « par cooptation » ; mais il est difficile de faire autrement : pour évaluer quelqu’un pour un poste en France, avec un dossier en français et dans le contexte particulier de l’enseignement supérieur et la recherche français, en général il faut un français du même domaine, qui n’est pas si vaste.

Il se pose donc des conflits d’intérêts. Voici donc comment je gère ceux-ci quand c’est moi l’évaluateur.

Le malaise

Il m’est arrivé que l’on me demande de rédiger un rapport sur le dossier d’une personne que j’apprécie beaucoup. Je ne rentrais dans aucune des conditions que l’organisme commanditaire de l’évaluation considérait comme constituant un conflit d’intérêts, et pourtant je me sentais mal à l’aise. Je fis ce travail mais in fine j’aurais préféré que cela fût quelqu’un d’autre.

Premier critère pour moi : je peux refuser une évaluation, même si je ne rentre dans aucun cas officiel de conflit d’intérêts, si celle-ci me met mal à l’aise d’une façon ou d’une autre.

(Par ailleurs, je me suis retrouvé à devoir donner mon avis sur la candidature de quelqu’un dont j’appréciais humainement la compagnie, mais dont la compétence ne me paraissait pas suffisante pour le poste. Cette personne, l’ayant appris, m’en a par la suite durablement voulu. Ce genre de problèmes est également à prendre en compte.)

L’apparence du favoritisme

Imaginons que j’évalue un dossier sans éprouver d’inconfort en le faisant, que je ne rentre dans aucun des cas de conflit d’intérêts identifiés par le commanditaire de l’évaluation. Je risque cependant, dans certains cas, que certains se fassent la réflexion que j’aurais agi par favoritisme ou, au contraire, inimité, s’il y avait entre moi et la personne à évaluer des liens, réels ou supposés, positifs ou négatifs, remettant en cause mon objectivité.

Second critère : éviter ce qui pourrait donner lieu à mauvaise interprétation.

Les critères du commanditaire

Certains commanditaires d’évaluation ont une liste officielle de critères signalant un conflit d’intérêt (par exemple, avoir été directeur de thèse du candidat, avoir co-signé une publication avec lui pendant les 3 dernières années...) ; d’autres non. Dans tous les cas, si j’estime avoir un conflit d’intérêts (réel ou potentiel), j’explique les faits au commanditaire et je le laisse estimer si ceux-ci constituent ou non un conflit d’intérêts en son sens. En effet, je n’ai pas à me substituer à lui en ce qui concerne la politique de son organisme, de son éditeur, de sa revue…

Ainsi, dans ce domaine comme dans d’autres, je sépare bien ce qui relève d’une éthique personnelle (qui, en l’espèce, relève plus du désir d’éviter des situations inconfortables que d’un questionnement purement moral) de ce qui relève d’une question de politique des organismes ou des publications, où je laisse la décision à ceux qui en ont la responsabilité.

samedi, janvier 20 2018

Sur la portée des attaques SPECTRE et MELTDOWN

Les attaques Meltdown et Spectre ont beaucoup inquiété. Devant certaines questions, il me semble pertinent de préciser certains points.

Ces attaques visent à faire fuir des informations depuis un logiciel attaqué vers un logiciel attaquant, ce dernier devant réaliser un certain nombre d’actions très spécifiques pour obtenir, indirectement, des informations censément secrètes. Elles s’appuient sur des chronométrages fins de certaines opérations très particulières, le temps nécessaire à les réaliser variant suivant la valeur des données secrètes. Elles contournent ainsi les mécanismes de protection qui permettent à une même machine de faire fonctionner séparément les programmes de plusieurs utilisateurs.

Ces attaques sont donc importantes pour les prestataires de services d’hébergement cloud, qui louent à des utilisateurs la possibilité de lancer des logiciels sur des machines (dites « serveurs ») puissantes et situées dans des locaux adaptés (data centers), avec des connexions Internet à haut débit et faible latence et des assurances de fonctionnement en continu (personnel de permanence, onduleurs en cas de coupure de courant). Elles sont également importantes pour les entreprises et organismes qui ont des serveurs où un grand nombre d’utilisateurs peuvent lancer des logiciels de leur choix ; par exemple, pour les universités, certains étudiants ayant à cœur de vouloir contourner les mécanismes de sécurité.

Qu’en est-il des utilisateurs individuels ? Une personne qui utilise seule sa propre machine ne va évidemment pas essayer de se pirater elle-même. On pourrait éventuellement envisager une attaque en escalade : tout d’abord, les intrus se rendraient maîtres d’un logiciel peu privilégié (n’ayant pas accès aux donnés de l’utilisateur humain de la machine) mais communiquant en réseau, puis à partir de là essaieraient d’obtenir les données de l’utilisateur ; mais cela semble assez difficile (il y a probablement d’autres failles plus faciles à exploiter).

Le cas qui me paraît le plus réaliste est celui des navigateurs Web, qui font fonctionner des logiciels venant de l’extérieur (principalement écrits en langage Javascript). Pour être exécuté efficacement, le Javascript est traduit (on dit « compilé ») en instructions directement exécutables par l’ordinateur. Il semble possible d’écrire du Javascript tel qu’avec certains navigateurs le produit de cette traduction puisse être utilisé pour réaliser les chronométrages permettant l’attaque. Parmi les contre-mesures discutées, il y a la détection, lors des processus de compilation, de configurations vulnérables à l’attaque Spectre (ou de configurations attaquantes) et l’ajout d’instructions empêchant la fuite d’informations.

On m’a évoqué le cas des processeurs ARM ou STMicro. Ceux-ci ne sont pas utilisés dans des ordinateurs personnels ou dans des serveurs classiques, mais plutôt dans des objets connectés ou non ou des terminaux mobiles (téléphones, tablettes…). C’est un univers vaste et il faut distinguer plusieurs cas.

Les attaques Spectre et Meltdown visent à contourner des mécanismes de protection et d’isolation de processus les uns et des autres. Elles n’ont donc aucun intérêt sur des processeurs simples n’ayant pas de tels mécanismes de protection, où chaque logiciel a accès à la mémoire de tous les autres (ce qui a d’ailleurs été longtemps le cas sur les ordinateurs personnels).

Ces attaques s’appuient sur des mécanismes (mémoires caches, exécution spéculative…) qui n’existent que dans les processeurs à hautes performances, notamment ceux que l’on met dans les ordinateurs personnels et les serveurs. Les processeurs plus simples n’utilisant pas de tels mécanismes ne sont pas vulnérables.

Ces attaques supposent que l’on puisse charger un logiciel intrus, donc qu’il soit possible de charger des logiciels nouveau sans que ceux-ci n’aient à être authentifiés par le fabricant de l’objet. Les objets n’ayant pas la possibilité de charger des nouveaux logiciels, ou qui restreignent ce chargement à des logiciels produits par le fabricant de l’objet ou du moins validés par lui, avec au moment du chargement vérification de ce fait (signature électronique), ne sont donc pas concernés.

mardi, janvier 9 2018

Retour sur quelques questions sur MELTDOWN et SPECTRE

Suite à la publication de mes billets précédents sur les failles MELTDOWN et SPECTRE, j’ai répondu à diverses questions, et je pense que certaines méritent une réponse publique.

Les attaques par canaux cachés n’ont rien de nouveau

Un de mes interlocuteurs pensait que ces failles étaient les premières failles de sécurité basées sur un problème dans le matériel. Ce n’est pas le cas — peut-être serait-il en revanche exact que ce sont les premières failles de sécurité basées sur un problème dans le matériel qui soient venues à l’attention des journalistes.

Les failles MELTDOWN et SPECTRE s’appuient sur l’exploitation de « canaux cachés » permettant de transmettre de façon indirecte des informations d’un logiciel privilégié (au sens qu’il a accès à des informations sensibles) vers un logiciel intrus, ces canaux de communication découlant de certaines fonctionnalités du matériel (mémoires caches, notamment). Les attaques par canaux cachés n’ont rien de nouveau.

Une attaque par canal caché tend à recouvrer des informations secrètes en exploitant des effets indirects de l’exécution du programme manipulant ces données. Par exemple, dans le cas de cartes à puce contenant des clefs cryptographiques secrètes et qui doivent le rester, on a appliqué des attaques consistant à mesurer finement la consommation électrique instantanée de la carte à puce ou son rayonnement électromagnétique. Dans le cas de logiciels sensibles s’exécutant sur la même machine que des logiciels malveillants (cas réaliste par exemple dans le cas de cloud computing, où des applications de plusieurs clients fonctionnent sur le même serveur), le logiciel malveillant peut notamment observer de petites fluctuations de son temps d’exécution dues à l’activité du logiciel sensible. Je n’ai pas le temps ce soir de rechercher les premières propositions de ce type d’attaques, mais je relève notamment l’attaque de Daniel J. Bernstein en 2005 contre des logiciels implantant le standard de chiffrement AES.

Ce type d’attaques est maintenant tellement représenté dans la littérature scientifique et technique que certains logiciels sont « durcis » pour éviter de laisser prise à ces observations exploitant l’isolation imparfaite fournie par les processeurs. Par exemple, pour éviter que des mesures fines du temps qu’un logiciel met à chiffrer des données ne soient exploitées pour retirer des informations sur les clefs cryptographiques, on mettra en œuvre du chiffrement en temps constant. Pour éviter que des informations ne fuient par les caches (je ne vais pas expliquer en quoi cela consiste, c’est assez technique), on va programmer les logiciels d’une façon à ne pas avoir d’action sur le cache qui permette de dériver des informations sur les données secrètes. D’ailleurs, un des buts d’une thèse que je dirige, celle de Valentin Touzeau, est d’analyser les logiciels pour détecter de telles vulnérabilités.

Il y a déjà eu des trous de sécurité importants dans le matériel, y compris d’Intel

Certains matériels Intel contiennent, en sus du processeur principal, un processeur auxiliaire nommé « moteur de gestion », caché du système d’exploitation installé sur le processeur principal et comportant son propre système d’exploitation et logiciels. En 2017 il a été révélé que ce moteur de gestion était vulnérable à des attaques.

Ce n’est pas la première fois qu’il y a des trous de sécurité importants nécessitant des mises à jour massives chez les prestataires d’hébergement

Je ne vais pas refaire l’historique de tous les trous de sécurité trouvés dans les logiciels utilisés chez les hébergeurs et me contenterai de mentionner le fait suivant. En 2008, donc à une époque où les services en ligne étaient déjà bien développés, avec beaucoup d’informations personnelles stockées chez des prestataires, on s’est aperçu que le générateur de clefs cryptographiques SSH et SSL livré notamment dans les distributions Linux Debian et Ubuntu avait été modifié, apparemment par erreur naïve et non par malice, de sorte que toutes les clefs générées étaient vulnérables. Cela voulait dire que des gens malveillants pouvaient se faire passer auprès de divers systèmes pour des utilisateurs ou administrateurs légitimes, ou encore intercepter des communications Web réputées sécurisées (le fameux logo cadenas) en se faisant passer pour un site légitime et récupérer toutes les informations secrètes transmises (mots de passe, y compris bancaires, etc.).

Malgré l’importance et la stupidité de ce bug, qui a nécessité une mise à jour d’urgence dans un très grand nombre de systèmes (y compris des systèmes non basés sur Debian ou Ubuntu, puisque ce qui compte c’est la machine qui avait généré les clefs), la presse grand-public n’en a pas parlé.

Il existe de la recherche universitaire en sécurité informatique

Il existe dans les universités, ou des organismes tels que le CNRS ou l’INRIA, de la recherche en sécurité informatique. Celle-ci n’est l’apanage ni des entreprises privées telles que Google, ni des organismes très orientés applications industrielles tels que le CEA, ni des services gouvernementaux spécialisés comme l’ANSSI ou la DGA-MI. D’ailleurs, les vulnérabilités MELTDOWN et SPECTRE ont été découvertes conjointement par des chercheurs de l’université technique de Graz, en Autriche, et une jeune chercheuse de cette équipe a rejoint le CNRS l’an dernier.

Ce qui est en revanche exact, c’est que les entreprises comme Google, Amazon, Facebook ou Microsoft ont des moyens sans commune mesure avec les laboratoires universitaires. Ainsi, il y a quelques années, j’ai vu un collègue recruter pour une des équipes de sécurité chez Google ; il « faisait son marché », envisageait de débaucher des universitaires (dont moi), etc., avec un budget pour 20 personnes. Par comparaison, le CNRS, tous laboratoires confondus, recrute cette année, est c’est exceptionnellement généreux, 2 jeunes chercheurs en sécurité informatique.

Où est la nouveauté ?

La nouveauté consiste en l’utilisation active de l’exécution spéculative des processeurs à hautes performances, conjointement aux canaux cachés.

Quel impact ?

À lire certains, la vulnérabilité MELTDOWN aurait permis de lire à volonté n’importe quelle portion de la mémoire de la machine attaquée. Or, après lecture plus approfondie des documents publiés par Intel et Google, on s’aperçoit que les données attaquables sont celles résidant en mémoire cache de niveau 1 au moment de l’attaque, ce qui est une infime portion de la mémoire de la machine. Un des codes de démonstration de la faille qui circule publiquement fait juste avant l’attaque un appel au système qui a pour effet secondaire de charger dans le cache de niveau 1 des informations qu’il va ensuite lire via MELTDOWN ; ce code de démonstration se contente cependant de provoquer le chargement de données absolument pas sensibles. Il n’est pas évident pour moi qu’il soit possible de forcer le système d’exploitation à manipuler des données sensibles de façon à ce qu’elles soient disponibles en cache de niveau 1 au moment de l’attaque (il est cependant possible qu’il y ait un autre volet de l’attaque qui n’ait pas encore été rendu public au 8 janvier et que la présence dans le cache L1 ne soit pas nécessaire).

En l’état de mes informations, je ne comprends donc pas trop l’urgence qu’il y a à mettre en œuvre des contre-mesures, éventuellement mal maîtrisées ou occasionnant des pertes notables de performance, contre l’attaque MELTDOWN.

J’insiste cependant que je ne suis pas un expert en sécurité informatique de bas niveau, et que je n’ai accès à aucune information secrète.

En revanche, les attaques MELTDOWN et SPECTRE m’inquiètent en ce qu’elles démontrent que les processeurs actuels, avec leurs nombreux dispositifs destinés à augmenter les performances, notamment les mémoires cache et l’exécution spéculative, sont devenus d’une telle complexité qu’il existe des interactions insoupçonnées des créateurs de ces systèmes. La compartimentation proposée par ces processeurs est très imparfaite et il est difficile de penser à tous les biais possibles d’attaque. On peut également se poser des questions sur le modèle de sécurité basé sur la séparation mémoire matérielle entre processus, et des processus entre utilisateurs : est-il adapté à une époque où le navigateur Web exécute des logiciels de toute provenance à l’aide de mécanismes complexes et donc potentiellement vulnérables ? Je n’ai évidemment pas de réponse à ces questions.

PS: L'hyperthreading peut sans doute aussi aboutir à ce que certaines données sensibles soient chargées en cache...

lundi, janvier 8 2018

MELTDOWN wonderment

It seems that the Meltdown leak only happens if (kernel) data is in the L1 cache.

This seems like an onerous restriction on applicability of the attack : it is like one would have to make a system call to the kernel which would read the secret data just prior to the attack.

This is a far cry from the first comments on the issue, which implied that any memory accessible by the kernel (thus, in Linux and MacOS X at least, all of physical RAM) was readable.

Or is there something not yet public ?

samedi, janvier 6 2018

MELTDOWN implemented

I now have a working implementation of the MELTDOWN attack, which I developed in about one day after reading the Lipp et al. paper. It is not pretty; the one from Pavel Boldin is much more complete.

I got stuck for hours, not understanding why I could not transfer information depending on secret data through the side channel, until I read Pavel Boldin’s implementation and realized that just before conducting the attack, he made a system call that made the kernel read the secret data under attack (as an example, he read from /proc/version, which makes the kernel read from a format string known as linux_proc_banner, and then checked that he could that format string from the supposedly protected kernel memory).

I suppose that the reason is that this loads the string into some of the CPU caches, which would imply that the MELTDOWN attack only works for data that is already in some of these caches. I suppose that if a cache reload of the secret data is needed, then the protection check will be performed before the speculative loads are performed.

I am unsure whether there is a method to force the cache loading of arbitrary protected memory locations.

I also have a working implementation for breaking kernel address space layout randomization (KASLR). I simply implemented the ideas from Jang et al., Breaking Kernel Address Space Layout Randomization with Intel TSX: namely, it takes fewer CPU cycles to generate a protection fault against a mapped, but protected, page, than for unmapped space; in both cases this generates a segmentation violation, but no trap is generated if the illegal accessed is wrapped in a transaction (Restricted Transactional Memory). It is sufficient to measure the time taken to complete the transaction, on my machine it is about 186 cycles when mapped versus 200+ cycles when unmapped.

PS: My idea about the data needing to be inside a close cache is confirmed by Intel's analysis:

For instance, on some implementations such a speculative operation will only pass data on to subsequent operations if the data is resident in the lowest level data cache (L1). This can allow the data in question to be queried by the application, leading to a side channel that reveals supervisor data.


vendredi, janvier 5 2018

Pourquoi l'informatique devient incompréhensible, et l'impact sur la sécurité

Les failles de sécurité SPECTRE et MELTDOWN sont, comme je l’ai expliqué dans des billets précédents, des attaques par canaux cachés. Il me semble pertinent de prendre ici un peu de recul sur ces questions ; je n’aurai pas la prétention de dire qu’il s’agit de philosopher, mais c’est un peu l’idée.

Grosso modo, quand on programme, on décrit une suite d’opérations à exécuter par la machine pour obtenir le résultat désiré. Le sens, on dit aussi la sémantique, de ces opérations est documenté, que l’on programme dans un langage de programmation de haut niveau (Python, C++, Prolog…) ou en langage machine (Intel x86…). Plus précisément, ce qui est documenté c’est la sémantique fonctionnelle, c’est-à-dire le résultat des opérations (par exemple, l’opération d’addition réalise une addition, sous réserve que le résultat ne dépasse pas un certain nombre de chiffres, etc.). Il existe en revanche diverses propriétés non fonctionnelles peu documentées et souvent difficilement prévisibles : le temps de calcul, la consommation électrique, etc. Naturellement, il est bien plus facile de raisonner sur les propriétés fonctionnelles que sur les propriétés non fonctionnelles.

Les mécanismes de sécurité incorporés aux langages, processeurs et systèmes d’exploitation modernes visent les propriétés fonctionnelles : notamment lorsqu’un programme tente d’accéder à des données auxquelles il n’a pas accès, cet accès est refusé. On peut ainsi isoler les uns des autres différents programmes, différents utilisateurs.

Il est toutefois bien plus difficile d’isoler les aspects non fonctionnels. Par exemple, si je lance un logiciel sur une machine, même si je n’ai pas officiellement le droit de lire la table des logiciels lancés par d’autres utilisateurs, je peux savoir qu’un autre logiciel est lancé si le mien est ralenti. Par des mesures plus fines, je peux même éventuellement me douter de ce qu’il fait : par exemple, s’il est dans une phase de calcul intensif sans grands accès à la mémoire principale, mes accès à la mémoire principale ne seront guère ralentis, tandis que s’il fait beaucoup d’accès, il ralentira les miens. D’une façon générale, plus il y a de ressources partagées (temps de calcul, mémoire, etc.) entre plusieurs utilisations, plus il y a la possibilité de passer des informations via des propriétés non fonctionnelles entre des domaines qui, a priori, sont fonctionnellement isolés. On appelle cela des canaux cachés.

Il y a maintes façons d’utiliser les canaux cachés. Par exemple, si on a la possibilité de faire fonctionner, sur la même machine, un logiciel qui a accès à une base de données sensibles mais n’a pas accès aux communications réseau et un logiciel qui n’a pas accès à la base de données et a accès aux communications réseau, séparés fonctionnellement (pas de canal de communication officiel entre les deux), on pourra transmettre des informations de l’un à l’autre par un canal caché (par exemple, mais il existe bien évidemment des méthodes plus efficaces, en alternant des périodes d’accès mémoire intensifs et faibles en une sorte de code Morse). La nouveauté des attaques MELTDOWN et SPECTRE est qu’il est possible de faire exécuter à un logiciel disposant d’accès privilégié aux données des instructions qu’il ne devrait pas vraiment exécuter, et qui n’ont d’ailleurs pas d’effet fonctionnel, mais conservent leurs effets non fonctionnels. Ce qui permet à ces attaques de fonctionner, c’est que diverses ressources matérielles (et notamment des mémoires cache) sont partagées entre des logiciels privilégiés (noyau du système d’exploitation, navigateur Web…) et non privilégiés (simple application, code Javascript d’une page Web…).

La complexité des machines actuelles, due à la recherche de hautes performance, avec la présence de nombreuses ressources partagées, est telle qu’il est difficile d’éviter les canaux cachés. Elle rend également difficile de démontrer quoi que ce soit de précis sur les propriétés non fonctionnelles, notamment le temps d’exécution. C’est un problème qui concerne notamment ceux qui veulent produire des dispositifs matériels répondant sous un certain délai garanti, par exemple des systèmes qui contrôlent des avions : comment, dans un système mettant en jeu plusieurs cœurs de processeur partageant de la mémoire, chacun avec des mémoires cache compliquées, garantir que l’exécution d’un programme prendra moins d’un centième de seconde dans tous les cas ? Nous sommes loin de ces processeurs des années 1980 dont la documentation donnait le temps d’exécution de chaque instruction...

Si l’on peut résumer une bonne partie de l’informatique depuis 70 ans, tant côté logiciel que matériel, on a progressivement éloigné le programmeur de l’exécution physique sur la machine, en rajoutant de plus en plus de couches de traduction, d’émulation, de virtualisation… Il y a d’excellentes raisons à cela : il est bon que le programmeur n’ait pas à se préoccuper des détails matériels de chaque machine, au risque que son programme ne fonctionne plus sur le modèle sorti un an après ; on peut mutualiser des ressources (dans un avion ou une voiture, mettre plusieurs tâches sur le même calculateur au lieu de mettre plusieurs calculateurs ; dans le cloud, mettre plusieurs utilisateurs indépendants sur le même serveur…). Cet éloignement nous empêche toutefois de bien appréhender les canaux cachés et propriétés non fonctionnelles.

Plus généralement, on a assisté à une bureaucratisation de la programmation. Sur un ordinateur personnel des années 1980, si l’on voulait dessiner une forme dans l’écran, il suffisait, au pire, d’aller écrire les valeurs des couleurs désirées dans la mémoire destinée à l’affichage vidéo : on voulait du bleu, on écrivait un code dans une case mémoire et on avait du bleu. Maintenant, il faut en quelque sorte remplir une série de formulaires administratifs pour avoir le droit de demander à un autre logiciel d’allumer le point. C’est la différence entre faire des travaux soi-même chez soi et demander au service de l’entretien d’envoyer un ouvrier les faire… Dans le premier cas, on maîtrise évidemment mieux ce qui est effectivement fait.

L'attaque MELTDOWN

Les réseaux sociaux et les blogs spécialisés en sécurité bruissaient de rumeurs depuis une semaine (pourquoi des modifications si urgentes dans le système de gestion de mémoire du noyau Linux, alors que d’habitude il faut des mois et des mois pour que le moindre changement soit accepté ?). Comme d’habitude lorsque des trous de sécurité majeurs sont découverts, ceux-ci n’étaient documentés que sous embargo, c’est-à-dire qu’on a d’abord informé les industriels ou groupes de développeurs susceptibles de fournir des correctifs, en leur laissant un délai suffisant, avant de publier les articles décrivant les problèmes.

Il y a en fait deux catégories d’attaques publiées ce jour : MELTDOWN et SPECTRE, qui partagent certaines caractéristiques. J’ai publié un autre billet sur SPECTRE, dont je vais reprendre ici quelques éléments explicatifs. Je vais discuter ici de MELTDOWN, en me basant sur la lecture de l’article décrivant les attaques (Lipp et al., Meltdown). Les attaques MELTDOWN sont celles contre lesquelles Microsoft, Apple et les développeurs de Linux ont intégré des contre-mesures. Je vais tenter de les expliquer à un niveau ne nécessitant pas de connaissances particulières en informatique.

Lire la suite...

- page 1 de 95