vendredi, février 24, 2012

La Tragédie des facteurs communs


X.509 (#) est un standard de l'ITU Telecommunication Standardization Sector pour les infrastructures à clés publiques. (Il est également parfois employé dans les infrastructure de gestion de privilèges pour le traitement des autorisations.) Dans cette norme, un certificat garantit l'association d'une clé publique à une entité nommée et identifiée. Les certificats sont délivrés par des autorités de certification qui peuvent dépendre les unes des autres dans une forme hiérarchique. Les navigateurs du marché sont livrés, par exemple, avec un certain nombre de certificats des autorités « racines » pré-installés de façon à ce que les certificats SSL des éditeurs et des fournisseurs de services soient immédiatement reconnus.

 



OpenPGP(#) est un autre dispositif populaire sur Internet pour chiffrer les échanges et authentifier les messages. Il fonctionne sans hiérarchie d'autorités de certifications, comme celles du standard X.509, et met également en oeuvre un chiffrement symétrique à clés publiques.

 



Les clés publiques sont donc devenues avec la généralisation des infrastructures de sécurité — que l'on pense aux protocoles SSL/TLS (#) et HTTPS (#), par exemple — l'épine dorsale du e-commerce, du paiement des transactions en ligne, de l'authentification des utilisateurs de services Web mais également de toutes les télécommunications, via leur rôle dans les routeurs, les équipements de télécommunications, les cartes à puces et les lecteurs, et dans la prolifération envahissante des devices connectés qui nous submerge.

 



Une cladistique des clés publiques. À première vue, ces clés publiques sont d'apparence bien modeste au regard de l'importance qu'elles ont prise aujourd'hui dans tous les secteurs de l'économie numérique : ce ne sont, après tout, que des nombres entiers, si connus et ressasses qu'on les dit « naturels ». Mais, pas de méprise ! Ces entiers ne sont point les chétives créatures qu'ils paraissent à l'oeil non averti...

 



Le naturaliste arithméticien porté sur la cryptographie distingue ainsi dans la zoologie des clés publiques quelques clades particulièrement intéressants. Les modules RSA, peut-être les plus populaires et les plus connus — nommés d'après Ron Rivest, Adi Shamir et Leonard Adleman en 1978 (#) — sont des nombres entiers qui sont le produit de deux très grands nombres premiers : n = pq, où p et q représentent ces très grands nombres premiers. La robustesse de RSA repose sur la difficulté que représente la factorisation de n : c'est-à-dire l'effort de calcul nécessaire pour déterminer p et q connaissant n. C'est un problème pour lequel on ne connaît pas à ce jour d'algorithme en temps polynomial. Dans l'infrastructure à clés publiques RSA, le message M est chiffré en calculant Me [n], M porté à la puissance e, modulo n, la clé publique du destinataire. (On suppose que tous les messages sont au final codés comme des entiers, ou des blocs d'entiers.) Le destinataire, seul à connaître les fameux très grands nombres premiers p et q du module RSA, est donc seul à posséder la clé privée d qui lui permet de déchiffrer le message crypté Me. En effet, connaissant p et q, d et e ont été choisis tels que ed - 1 soit divisible par (p - 1)(q - 1) ; du coup, pour déchiffrer on élève à nouveau le message crypté à la puissance d modulo n et l'on obtient Med qui n'est autre que M lui-même modulo n. (Cette dernière identification miraculeuse est due au Petit théorème de Fermat (#), l'autre gus de Montauban, notre arithméticien national plus fameux par son grand théorème, dit aussi le dernier, démontré il y a quelques années (#) par Andrew Wiles.)

 



Dans cette cladistique des clés publiques on trouve également les clés El Gamal (#) qui en appellent à l'imposante théorie algébrique des nombres. Cette fois la clé est constituée de trois entiers : p un nombre premier, g un générateur du groupe des entiers modulo p, et y un entier (public) tel que y = gxx, un entier strictement inférieur à p - 1, est la clé privée.

 



D'autres clés publiques sont utilisées pour la signature numérique ou DSA (Digital Signature Algorithm) défini dans les standards du FIPS (FIPS 186-3) promulgués par le gouvernement américain. La clé publique DSA est un quadruplet (p, q, g, y) dans lequel p et q sont des nombres premiers tels que q divise p - 1, g est un générateur d'un sous-groupe d'ordre q du groupe des entiers positifs modulo p et, comme dans le El Gamal, y = gxx, un entier strictement inférieur à q, est la clé privée.

 



Enfin on trouve également les clé publiques basées sur les courbes elliptiques (#) depuis les premiers travaux de Miller en 1985, dont je vous ferai grâce des détails puisque, vaillant lecteur, vous êtes malgré tout parvenu jusqu'ici !

 



De la poliorcétique des clés publiques. Inutile de dire que ces clés publiques ont été, depuis la publication des premiers algorithmes de chiffrement, l'objet d'attaques innombrables et furieuses tant des mathématiciens intéressés à la démonstration de leur robustesse que des hackers sublimés par l'exploit et la gloire du cassage des infrastructures de sécurité. Dans l'ensemble, cependant, le secret RSA — pour prendre le plus répandu — est plutôt bien gardé (#) et les ingénieux algorithmes de décomposition en facteurs premiers lancés à son assaut n'ont pas encore fait tomber la forteresse.

 



Il est difficile de résister ici à la tentation de mentionner quelques uns de ces algorithmes qui sont de véritables petits bijoux calculatoires (#). Par exemple, le crible algébrique (GNFS General Number Field Sieve) est un algorithme, fondé sur l'arithmétique modulaire particulièrement efficace pour la décomposition en facteurs premiers. L'algorithme de décomposition par fractions continues (#) plus ancien est toujours efficace, mais on lui préfère le crible quadratique de Pomerance (#) qui en 1990 établit un record en décomposant un nombre de 116 chiffres — en 1994, il décomposait un module RSA de 129 chiffres, premier d'une longue série de réussites des hussards de l'agèbre modulaire à l'assaut de la forteresse RSA : le dernier en date, en 2009, étant la décomposition d'un module RSA long de 768 bits (#) rendant aujourd'hui préférable le choix de clé de 1 024, voire 2 048 bits, dans les infrastructures PKI. Les algorithmes de Pollard (#) et de Williams, dont dérive le GNFS, établirent les records ultérieurs et furent employés dans les premières recherches de facteurs premiers réparties sur un très grand nombre de machines — technique de parallélisation maintenant très souvent employée pour l'analyse de très grands volumes de données en météorologie, en génétique, en astronomie, souvent via de simples économiseurs d'écrans proposés en libre chargement. Son titre de gloire fut la factorisation en 1993 (#) du neuvième nombre de Fermat — encore lui ! —
2512 + 1. Citons encore l'imprononçable SQUFOF (Square Form Factorization) de Daniel Shanks (#), et la factorisation par utilisation de courbes elliptiques (#) de Lenstra dans cette revue superficielle de l'attirail guerrier du cryptographe.

 



Si les modules RSA résistent encore c'est que sous leur frêle constitution de simple produit d'entiers, leur robustesse réside dans un choix des facteurs premiers p et q bien loin d'être innocent. La génération des clés pour les algorithmes comme RSA et ceux mentionnés précédemment est méticuleusement spécifiée dans plusieurs standards comme PKCS, IEEE 1363-2000, FIPS 186-3, ANSI X9.44 et ISO/IEC 18033-2, pour précisément résister aux attaques connues et anticipées. Cependant, première ombre au tableau réel qui s'annonce moins idyllique que le satisfecit irénique qui, semble-t-il, prévaut aujourd'hui, à l'examen approfondi (#) ces standards bien intentionnés diffèrent substantiellement les uns des autres. Cette diversité semblerait indiquer qu'il existe un consensus autour de l'idée que la robustesse d'un module RSA ne dépendrait pas nécessairement de l'exactitude de l'algorithme de génération. Et, de fait, on peut imaginer plusieurs processus de construction des modules RSA : construction théorique (#) — où p < q < rp pour r > 1 — ; construction simple décrite dans les standards et dans certaines implémentations comme OpenSSL, GnuPG et la librairie crypto de GNU, dans laquelle p et q sont choisis dans des intervalles donnés ; construction algorithmique dans laquelle, une fois choisi p, un calcul détermine q, pour que le produit tombe dans un intervalle choisi à l'avance. L'analyse de ces constructions démontre en effet que si la factorisation est dure (en temps non polynomial) celle des modules RSA uniformément construits par ces processus l'est également, ce qui serait donc plutôt positif. L'analyse des implémentations existantes, en revanche, montre qu'aucune d'entre elles (GNU crypto, GnuPG, OpenSSL, Openswan) ne suit exactement les standards en question (PKCS, IEEE 1363-2000, FIPS 186-3, RSA-OAEP, IEEE 1363-2000, NESSIE), avec pour résultat net que certaines implémentations et certains standards engendrent ces modules RSA de façon non uniforme. La non-uniformité, rappelons-le, ne met pas a priori en danger la sécurité des modules RSA, i.e la difficulté de leur factorisation qui est leur utime rempart, mais peut avoir un impact plus subtil qui vient d'être brutalement démontré par deux études de la population des clés publiques in vivo.

 



L'ethnologie des clés publiques. Sur ces considérations, somme toute relativement rassurantes, deux papiers récemment publiés — l'un à la conférence IMC 2011 (#), en novembre dernier à Berlin, par une équipe de TU München (#) ; l'autre dans l'ePrint Archive, mi-février 2012, par une équipe de l'EPFL (#) — distillent un troublant sentiment de panique. Ces ethnologues numériques ramènent des nouvelles bien inquiétantes de leurs études in vivo des clés publiques et des certificats X.509 tels qu'ils sont aujourd'hui utilisés dans leur habitat naturel Internet.

 



Tels des Dian Fossey de l'arithmétique, l'équipe de la TU München a vécu plus de 18 mois en compagnie de certificats X.509 sauvages, dans leur milieu Internet naturel, collectant des données depuis le premier million de sites Web les plus populaires dans le classement d'Alexa (#) et écoutant plus de 250 millions de sessions SSL/TLS sur le réseau universitaire allemand servant 120.000 personnes. Les résultats sont édifiants : l'infrastructure de certification X.509 actuellement en ligne se trouve dans un état avancé de détérioration.

 



Le pourcentage de certificats qui ne déclencheraient pas d'avertissement à l'utilisateur chez un client utilisant le référentiel racine de Mozilla (#) — qui a pourtant du pas mal grossir ces dernières années — ne dépasse par un très faible niveau de 18 %. Ce faible niveau de conformité s'explique par le très grand nombre de chaînes de validation incorrectes (40 % de tous les certificats vus !) et l'encore plus grand nombre de noms d'hôte incorrects ou manquants dans le certificat — ce qui contredit l'utilité et l'existence même d'un certificat en premier lieu ! Autres problèmes récurrents, les dates de validité des certificats depuis longtemps expirées, les certificats « escrocs » sans autorité racine, et le très grand nombre de certificats partagés par des entités sans relation entre elles (menant au problème d'usurpation d'identité, par exemple). Bref, un constat de déliquescence bien loin de la netteté chirurgicale du dispositif in vitro des spécifications des organismes de standardisation.

 



Mais ce n'est pas tout ! La seconde étude ethnologique de l'EPFL qui, quant à elle, a collecté plus de 11 millions de clés publiques par des scans d'un grand nombre d'hôtes Internet et en analysant le nouvel Observatoire du SSL (#) récemment mis en ligne par l'Electronic Frontier Foundation bat en brèche la belle assurance des arithméticiens modulaires.

 



Les 11,7 millions de clés publiques vues contiennent 6,4 millions de modules RSA distincts ; le reste est réparti entre clés El Gamal et clés DSA — une seule clé ECDSA repérée, un hapax. On y lit encore les scories de la dévastation due à la vulnérabilité de l'OpenSSL Debian de 2009 (#). Notée en mai 2008, une erreur de jugement avait conduit à retirer une seule ligne de code du générateur de nombre pseudo-aléatoire du paquetage OpenSSL dans la distribution Debian. Cette suppression entraînait une insuffisance d'entropie dans l'initialisation du générateur — à chaque usage — dont les nombres aléatoires ne devenaient plus aussi imprévisibles que théoriquement prévu, et qui, en conséquence, compromettait toutes les clés publiques engendrées sur les distributions dérivées de Debian, entre septembre 2006 et mai 2008. Par ricochet tous les systèmes, même non Debian, qui auraient utilisés des clés engendrées par l'OpenSSL Debian courraient de ce fait le risque d'être infectés et d'avoir été compromis. Épidémie majeure de compromission potentielle des transmissions et des échanges d'autant plus dangereuse qu'elle est largement sourde et invisible du grand public ! Ces clés furent blacklistées (#) et ces listes diffusées dans toutes les installations avec les mises à jour. Mais ces clés faibles circulent toujours aujourd'hui, leur proportion (0,3 %) est en baisse depuis 2009.

 



Ces modules RSA uniques, une fois collectés, ont été soumis à des analyses de factorisation, superficielles au vu de leur nombre, mais significatives quant aux conséquences réelles de leur usage sur le Net. Elles visent, notamment à vérifier l'hypothèse sous-jacente à la sécurité des architectures PKI qui est que dans la génération de clés publiques les choix antérieurs de nombres premiers ne sont jamais répétés. Et là, patatras ! Tout le bel édifice s'écroule devant les faits : sur 6,6 millions de certificats X.509 et clés PGP contenant des modules RSA, 270.000, soit 4 % partagent le même module RSA bien que n'impliquant des entités totalement étrangères. La duplication des clés est parfois la règle plutôt que l'exception...

 



Par ailleurs, l'étude a trouvé 12.934 modules RSA, soit 2 pour 1000, n'offrant aucune sécurité. Même en se restreignant aux modules RSA de taille 1.024 bits, les modules RSA en liberté aujourd'hui n'assurent au mieux qu'un niveau de sécurité de 99,8 %. (Une illustration saisissante : 98,49 % des certificats X.509 utilisent le même exposant RSA, 65.537, le lointain second à 0,76 % étant 17.) Lorsqu'on regroupe les 6.185.228 certificats X.509 lorsqu'ils partagent le même module RSA — les groupes qui ne contiennent qu'un seul module sont les « bons », leur sécurité est garantie par la solidité théorique de RSA — on trouve avec désespoir plus de 14 groupes de plus de 1.000 certificats ayant des modules RSA communs. Au total, l'étude ne dégage que 5.989.523 modules RSA distincts qui, de surcroît, malgré les factorisations des modules de 512 bits en 2006 et de 768 bits en 2009, ont à 2,4 % des tailles encore inférieures à 768 bits. Aujourd'hui 73,9 % sont des modules RSA de 1.024 bits, 21,7 % de 2.048 bits et le reste est constitué d'entiers de tailles supérieures, jusqu'à 16.384 bits (pour 181 d'entre eux). Mais plus grave encore, une grande proportion des ces modules RSA ont en commun l'un de leurs deux nombres premiers (les p et q mentionnés plus haut) ce qui entraîne la perte totale de sécurité parce que leur décomposition commune est simplifiée par des algorithmes ad hoc (#).

 



L'aléatoire est au coeur des systèmes de chiffrement et faute de les tester correctement et de savoir tester correctement les générateurs de nombres aléatoires, on se rassurera à trop bon compte de leur fiabilité et de leur sécurité. Le ton alarmiste de certains commentaires publiés (#) sur cette étude est bien de mise : elle tire la sonnette d'alarme sur un problème profond et difficilement indétectable des architectures de sécurité. Quelques équipes innovantes travaillent aujourd'hui sur des nouvelles pistes pour y remédier. La jeune pousse MassiveRand — dont cet auteur est un très modeste actionnaire minoritaire — (#) par exemple, propose un TRNG True Random Number Generator, générateur de nombres aléatoires non déterministe) à très haut débit, pour les applications dans lesquelles la qualité des nombres aléatoires est cruciale.

 



Comme le répète inlassablement Bruce Schneier (#) les mauvais générateurs de nombres aléatoires nuisent gravement à la sécurité, quelque soit l'ingéniosité du dispositif mis en oeuvre.

 



samedi, février 04, 2012

In (Big) Datis Veritas

La Pénurie de données à l'âge classique. L'expérience était naguère encore chiche. L'efficacité d'une expérience scientifique classique reposait tout autant sur l'importance de l'hypothèse théorique dans laquelle elle s'inscrivait que sur l'ingéniosité de l'expérimentateur à la concevoir et en collecter les résultats tant était élevé le coût de la réalisation et de la production de données à partir de son observation. L'expérience de Michelson et Morley en 1887, par exemple, est généralement considérée comme la première d'une série successivement plus complexe d'évaluations de la Théorie spéciale de la relativité. Elle mit en oeuvre des miroirs parfaitement polis, des verres parfaitement transparents, rivés sur un lourd bâti en pierre flottant dans un bain de mercure, entièrement couverts pour pallier les variations infimes de tempértaure ; ces tonnes de matériel furent, de surcroît, amenées et construites à grands frais au sous-sol de la résidence universitaire de ce qui est devenu la Case Western University pour éviter vibrations et autres effets indésirables (#). Les quelques 238 données produites par quatre jours d'expérimentation occuperaient aujourd'hui difficilement le premier quadrant d'une simple feuille de tableur ! Mais le talent des expérimentateurs et le génie des théoriciens compensaient alors amplement l'avarice de l'expérimentation. Des maigres ruisselets de données qui sourdaient ainsi laborieusement d'expériences rares et coûteuses, une analyse en profondeur reconnaissait alors des faits c'est-à-dire, dans la perspective fondamentaliste prévalente, du réel et de la connaissance consistant ici en la croyance dans les faits.

 



L'observateur, théoricen, expérimentateur ou partie prenante, énonce donc que l'expérience de Michelson-Morley démontre que la vitesse de la lumière est constante. Mais l'expérience, dans les données qu'elle produit, énonce-t-elle une vérité ? En fait, elle n'a aucun besoin de le faire puisqu'elle remplit efficacement sa tâche sans dire un mot.

 



L'expérience produit des cas, des jeux de données (datasets) dit-on maintenant, où la vitesse de la lumière est invariable. Il n'y a là rien de remarquable : n'importe quel rayon lumineux en fait autant. Mais l'art de l'expérimentateur et le soubassement théorique aboutissent ici à une mesure du temps que la lumière met à parcourir des distances égales dans des directions différentes qui souligne l'invariabilité de la vitesse de la lumière. Ainsi pour reprendre Norwood Hansen (#) : «  facts are small theories and true theories are big facts  » (les faits sont eux-mêmes de petites théories et les vraies théories ne sont que des faits grandioses).

 



Cet équilibre économique précaire entre disette de données et profondeur de leur analyse conduit à des schémas d'interprétation particuliers devenus standards. Les données sont probantes si elles soulignent, elles exhibent, elles mettent en valeur ou elles transmettent sans faire de commentaire, ce qui en pratique comporte à la fois une référence et une instanciation. Des données qui font référence à un trait et l'instancient exemplifient ce trait, pour reprendre le vocabulaire de Nelson Goodman ; le jeu de données devient alors exemplaire du trait auquel il fait référence (#). Puisque l'exemplification est donc un mode de référence, tout ce qui exemplifie est un symbole. Des échantillons, des exemples au sens ordinaire, des données exemplifient les traits qu'ils exhibent et servent donc tous de symboles. Et puisque l'exemplification requiert l'instanciation, un jeu de données, comme symbole, ne peut exemplifier que des traits qu'il instancie : un échantillon significatif est nécessairement sélectif dans ce qu'il représente. Ainsi le jeu de données comme symbole appelle une interprétation : le comprendre nécessite de savoir lesquels parmis ses aspects exemplifient et à quels traits ils réfèrent.

 



Les traits qu'un jeu de données exemplifie dépendent de sa fonction. Parfois il arrive qu'un jeu de données, comme symbole, accomplisse toute une variété de fonctions. L'art de l'expériementateur et l'intention de celui qui produit le jeu de données peuvent contribuer à restreindre cette variété mais ne suffisent pas à déterminer le trait exemplifié tout simplement parce qu'ils peuvent se tromper. Ainsi Michelson et Morley se proposaient par leur expérience d'exemplifier la présence et la grandeur du vent d'éther. Or l'expérience à non seulement prouvé l'inexistence de l'éther luminifère mais également l'incapacité des catégories classiques à rendre compte des phénomènes électromagnétiques, point que Michelson et Morley trouvaient eux-mêmes inconcevable ! Les exemplaires opèrent par rapport à une constellation d'hypothèses ; quand on change ces hypothèses d'arrière-plan un jeu de données peut se mettre à exemplifier de nouveaux traits. Le jeu de données exemplaire contribue à construire la réalité en « matérialisant » et en organisant la constellation d'hypothèses sous-jacente.

 



Alea Big Data Est. L'intérêt actuel croissant pour le Big Data (#) et la perpective scientifique dans laquelle il peut s'inscrire accentue notablement l'importance de ces considérations sur représentation et la construction de la réalité.

 



Le premier constat est évidemment celui du bouleversement de l'équation économique de la production de données à des fins d'expériementation par et pour le Web. Les datacenters pharaoniques des titans du Web comme Google, Facebook, Twitter, Microsoft, etc. collectent des masses littéralement inimaginables de données. D'après IDC (#), le volume de données numériques créées et copiées sur le Web en 2011 a atteint 1,8 zettaoctets — et les métaphores incommensurables qui illustrent ces chiffres nous sont devenues familières.

 



Du coup la multiplicité des fonctions accomplies par un jeu de données, dans notre analyse précédente, explose mécaniquement avec le nombre mais également avec la croissance polynomiale des mises en relation possibles avec d'autres jeux de données tout aussi innombrables. À un coût rendu marginalement nul, la supernova des Big Data illumine les sciences sociales, économiques et comportementales (cognitives) avec un impact prospectif majeur sur la finance, la communication et l'information, et, au final comme l'explore habilement Nicholas Carr (#) sur notre esprit et notre cerveau.

 



Le second constat est, qu'en contrepoint, la déflagration des capacités de production, de stockage et de calcul des données a entraîné et accompagné des progrès mathématiques théoriques majeurs signalant l'irruption massive de l'aléa dans les avancées récentes de la combinatoire et de l'algorithmique. Les statistiques et leurs disciplines souvent mal aimées, parfois reléguées à des fonctionnaires crayeux au teint couleur muraille oeuvrant mystérieusement dans les poussiéreux corridors de bunkers staliniens surplombant des périphériques encombrés, acquièrent soudain un lustre nouveau en changeant de statut. Elles sont en train de devenir des datistiques pourrait-on dire, tant elles saluent le retour à la scène de l'Aléa.

 



L'utilisation de la simulation pour les calculs réputés intraitables en très haute dimension, par exemple, révolutionne les mathématiques appliquées (#). En effet, à quoi sert donc de produire plus de données ? Traditionnellement à réduire les marges d'incertitude dans les calculs. Mais si l'on produit vraiment massivement plus de données, on peut envisager d'accélerer subtantiellement les temps d'exécution de simulations numériques dans les tests et le calibrage des modèles statistiques ainsi que les temps d'exécution de ces modèles à des fins prédictives. On peut aussi compenser naturellement le manque d'information par des données produites très rapidement et en quantité, c'est-à-dire par des échantillons probants au sens précédent (#).

 



Les progrès de la formalisation mathématique de la méthode de Monte Carlo et, en particulier, de la nature de l'échantillonage de données permettant de substituer à une information manquante un jeu de données approprié pour le calcul d'estimations numériques de distributions de probabibilité (#) permet de généraliser l'usage d'algorithmes probabilistes à toute une classe de problèmes considérés comme hors de portée des algorithmes déterministes classiques. Ce qu'on appelle Markov Chain Monte Carlo, un ensemble de techniques mis au point récemment et qui touche à la représentation des groupes (#), à la géométrie algébrique (#), et au renouveau de la théorie des équations différentielles (#) notamment pour l'analyse du temps de convergence des processus markoviens (#), permet d'attaquer des problèmes combinatoires complexes, en haute dimension, récurrents dans les moteurs de recherche, le data mining, l'apprentissage automatique, l'indexation des contenus, la classification des documents, la détection de patterns, la gestion de flux de données en temps réel, etc.

 



Un exemple concret est constitué par le développement des bases de données dites de Monte Carlo (Monte Carlo Databases), spécialisées dans la gestion de données incertaines. Ici, au lieu de représenter l'incertitude par des probabilités numériques individuelles associées à chaque rangée d'une table relationnelle, le SGBD Monte Carlo (#) produit à la volée lors de l'exécution d'une requête SQL un jeu de valeurs pour les données incertaines suivant la distribution de probabilité souhaitée : un échantillon probant à la demande.

 



Le succès des algorithmes probabilistes dans la résolution de problèmes combinatoires ou calculatoires bouleverse l'analyse de la complexité algorithmique. Ces nouvelles méthodes laissent à penser que la barrière entre problèmes P et NP — solubles en temps polynomial ou non — n'est pas aussi imperméable et franche qu'on l'imagine. ( P = NP est encore un des grands problèmes mathématiques ouverts, non résolu #.) Les datisticiens théoriques savent désormais que s'il faut un temps exponentiellement long pour trouver une solution exacte aux calculs sur les Big Data, ils arrivent à des approximations probantes en temps polynomial pourvu qu'ils disposent du levier d'une chaîne de Markov, à convergence rapide, pour produire à la demande des instances aléatoires du problème.

 



Vérité et données. Pour l'exprimer de façon radicale, ces nouveaux moyens adaptés aux Big Data pourraient remettre en cause certains fondements de notre compréhension de la réalité. Au risque d'errer du côté du constructiviste radical (#) d'Ernst von Glasersfeld — disparu il y a un peu plus d'un an — ou de trahir un léger accent Orwellien, il faut reconnaître avec Goodman « qu'avoir à usiner les instruments spécifiques de production des faits rend sans objet toute vélléité d'identification du physique au réel et du perçu à la simple apparence ». La réalité issue du traitement par les moyens mathématiques modernes des Big Data est-elle vraie ?

 



Lorsque Google restitue une image de la propagation de la grippe dans le monde entier (#) à partir des requêtes des internautes, qu'elle collecte et qu'elle analyse en linguiste, le taux d'incidence calculé est il le vrai taux d'incidence de la grippe dans le monde ? Le statisticien réservé note tout au plus une corrélation entre l'indicateur de Google et le taux d'incidence mesuré auprès des médecins par le Center for Disease Control and Prevention, et oppose que rien n'assure que l'outil soit capable de fournir des tendances aussi pertinentes à l'avenir. (Les résultats ne reposent-ils pas essentiellement sur l'habitude largement répandue des internautes de se servir de Google horresco referens pour leurs recherches ?) Le datisticien goguenard lui demandera alors en retour combien de données il doit rajouter pour que le taux d'incidence devienne le taux réel pour tout usage pratique (politiques de vaccinations préventives, élaboration de stratégies de santé publique, information et sensibilisation des individus...) ?

 



C'est la confrontation assurée des deux cultures de la modélisation statistique telle que la commentait Leo Breiman dans un papier célèbre (#). Imaginons les données produites par une boîte noire : à l'entrée des variables indépendantes, à la sortie des résultats que l'on souhaite élever au rang de faits à des fins de prédiction — prédire quels seront les résultats produits pour des variables à venir — et à des fins d'information — comprendre comment les résultats sont associés naturellement aux variables d'entrée. Dans l'approche de la modélisation, typique d'après Breiman de « 98 % » des statisticiens, on postule qu'un processus stochastique est à l'oeuvre dans la boîte noire, les résultats étant issus de tirages aléatoires indépendants d'après un modèle commun de données. Il s'agit alors d'estimer les paramètres du modèle sur la base des observations réalisées puis d'utiliser ce modèle calibré à des fins de prédiction. Dans l'approche algorithmique plane l'ombre portée du Test de Turing : l'intérieur de la boîte noire est considéré comme inconnu et inscrutable, voire même comme sans pertinence aucune, et il s'agit plutôt de trouver un algorithme, une fonction des variables, qui produit les résultats ou une approximation des résultats. Dans la première approche la validation du modèle est une affaire manichéenne, positivement ou négativement tranchée par les tests classiques de goodness-of-fit comme le Chi-2. Dans la seconde, la validation est matière à riposte graduée, fondée sur la précision relative de l'approximation.

 



L'avalanche des Big Data et le déploiement massif des moyens de calcul associés donne une toute autre force à la validation dans l'approche algorithmique. Comme on l'a vu, non seulement le nombre massif et ses nouveaux instruments mathématiques conduisent la précision des approximation à des degrés jamais atteints — et, défend le pragmatique, bien plus que suffisants pour toute connaissance ou action pratique sur laquelle la conforter — mais circonviennent des problèmes que l'approche de modélisation avait renoncé même à attaquer. De plus les avancées théoriques des années 1980 et 1990, calcul sur les réseaux Bayesiens (#), simulation Monte Carlo des chaînes de Markov et Logique de Markov (#), théorie de Vapnik-Chervonenkis et les support vector machines (#), les outils « ensemblistes » pour l'apprentissage automatique (#) — boosting, bagging, random forests, etc. — acquièrent une plus vive acuité encore avec l'accès à bas coût aux plateformes de calcul du cloud computing, comme MapReduce, Hadoop, Dryad, Pregel, GoldenOrb et bien d'autres.

 



Dans le sillage du déferlement des Big Data la vérité pourrait alors se trouver redéfinie par le poids croissant de l'approche algorithmique (#). (Que l'on songe à Twitter Trends, par exemple.) Il n'est pas question ici du problème philosophique de la vérité qui tourne autour de la réconciliation de versions alternatives et concurrentes des faits par l'attribution de leur variété à des désaccords sur les conventions d'interprétation de ces mêmes faits. Il est plutôt question de la dérive graduelle de la définition opérationnelle de la vérité qui nous contentait jusqu'alors.

 



La vérité est ici et maintenant dans le test — une fois abandonnée la grande ambition du programme de Hilbert de fonder la vérité sur la cohérence du système mathématique issu du formalisme logique à laquelle, nonobstant les Bourbachistes (#), Gödel a imposé une bifurcation majeure. La vérité (métaphoriquement) dite par les données devient avec les Big Data affaire de crédibilité (probabilistes) et d'utilité (pragmatiques) — Huxley et Orwell.

 



Ce faisant, les Big Data promeuvent une réalité qui a de moins en moins à voir avec une croyance vraie justifiée. D'abord la justification au sens d'un argument qui part de prémisses vraies n'est plus de mise. Ce n'est pas ce qui soutient le jeu de (Big) données mais ce qu'il met en avant qui plaide pour un exemplaire. La vérité n'est pas non plus cruciale. Les expériences, les jeux de données, les échantillons informent au moyen de l'exemplification. Les données, symboles non verbaux, ne sont ni vraies ni fausses : le succès — opérationnel — qu'elles rencontrent ne repose donc pas sur la vérité. Leur contribution cognitive peut simplement consister à augmenter le répertoire conceptuel dont on dispose, à affiner son pouvoir de discriminer, à aiguiser sa capacité à reconnaître, synthétiser, organiser, etc.

 



Ainsi les Big Data très loin d'être épistémiquement inertes sont, au contraire, hautement fissiles et il est loisible de s'inquiéter de leur niveau actuel au regard de la masse critique.

 



ShareThis