lien externe

Jules Desharnais

Envoyez-nous un courriel

Les mathématiques au service des TI

 
Rencontrer le chercheur Jules Desharnais c'est plonger profondément dans le domaine des mathématiques, plus précisément dans celui des mathématiques de la construction de programmes. On est évidemment ici dans le domaine de la recherche fondamentale et des fondements théoriques de la science informatique. Pas beaucoup d'éprouvettes, de produits chimiques ou autres matériaux à manipuler.
 
Ce professeur titulaire au Département d'informatique et génie logiciel de la Faculté des sciences et génie travaille surtout avec sa tête, un crayon et... du papier ! Si l’ordinateur et l’Internet lui sont essentiels pour la rédaction des publications, la communication avec ses collègues chercheurs et le suivi des recherches dans son domaine, il ne cache pas qu’il aimerait s’affranchir de la ''tyrannie de l’écran''. À plusieurs égards, il souhaite que la technologie continue d’évoluer pour rendre son travail de plus en plus agréable et facile, particulièrement pour les écrans d’ordinateur, qu’il trouve en effet trop petits pour bien visualiser les preuves, les graphes et autres représentations abstraites des programmes.
 
Il était d'ailleurs de la vingtaine de chercheurs de l'Université Laval que l'Institut Technologies de l'information et Sociétés (ITIS) a amené au tout nouveau Laboratoire d'immersion virtuelle (LIV) du centre de recherche pour la défense de Valcartier (RDDC), début mars, pour voir de plus près le potentiel de cette technologie. Jules Desharnais pense que l’imagerie virtuelle pourrait être une alternative intéressante à l'espace limité que représentent autant son tableau de classe devant ses étudiants, que son écran d'ordinateur devant sa tête de chercheur.
 
« J'aimerais avoir de meilleurs outils informatiques pour m'aider. À faire des preuves sur papier, c'est pas toujours facile d’effectuer des modifications, de déplacer une formule d’algèbre par exemple », expose-t-il. On imagine bien qu’en recherche, il décline des pages et des pages et des pages et des pages d'algèbre, avec des symboles pas toujours évidents à manipuler, autant sur ses feuilles de papier qu’à l’écran d’un ordinateur. Il dit connaître l’existence d’un logiciel de reconnaissance de l’écriture qui génère du code LateX.
 
Mais pour l'instant, il préfère continuer à noircir du papier. Un papier, d’ailleurs, auquel il ne manque peut être qu’un ''e'' pour répondre à son souhait ! Avec ce que la révolution du e-paper/papier électronique nous réserve (voir notre Dossier e-paper), c’est fort possiblement de ce côté-là aussi que Jules Desharnais verra apparaître de nouveaux outils stupéfiants. Et dans pas si longtemps ! Le e-paper est vraiment à nos portes. Souhaitons-le lui. 


Développement des théories mathématiques et de leur application à la construction de programmes informatiques


La recherche fondamentale qu'il mène vise d'une part le développement de théories mathématiques utiles et d’autre part les applications à la construction de programmes informatiques. Le professeur Desharnais résume ainsi ses sujets de recherche:
  • le développement de l'algèbre de Kleene;
  • des applications à la théorie du contrôle des systèmes à événements discrets;
  • des applications à la sécurité des programmes.
« L’algèbre de Kleene est essentiellement l’algèbre des langages réguliers et des automates finis, deux concepts étudiés en deuxième année du baccalauréat en informatique. Une particularité importante de cette algèbre, c’est qu’il est possible de déterminer automatiquement - c’est-à-dire au moyen d’un programme - si une équation de l’algèbre est vraie ou pas. Mais l’algèbre de Kleene n’est pas très expressive. Or, on aimerait utiliser cette algèbre pour modéliser les programmes informatiques pour ensuite déduire automatiquement leurs propriétés à partir du modèle. Mais le manque d’expressivité de l’algèbre de Kleene a pour effet d’empêcher une modélisation fine des programmes informatiques. Le but de la recherche sur l’algèbre de Kleene est de l’étendre avec de nouveaux opérateurs afin d’augmenter son expressivité, tout en n’exagérant pas, afin de préserver la propriété de vérification automatique des équations; dans le cas contraire, l’égalité est dite indécidable », explique-t-il en précisant bien le sens à donner à ce dernier concept, sur lequel nous reviendrons plus bas.
 
Jules Desharnais étudie actuellement une extension de l’algèbre de Kleene avec un opérateur appelé opérateur de domaine. Il étudie aussi des variantes de l’algèbre de Kleene appelées algèbres de raffinement. Ces algèbres permettent de spécifier le comportement des programmes par des expressions mathématiques appelées spécifications. Ces spécifications sont ensuite transformées - on dit qu’elles sont raffinées - pour produire d’autres expressions à partir desquelles on peut extraire des programmes, d’où le terme construction de programmes.
 
Et qui a dit que les mathématiques n’avaient pas un vocabulaire excitant ? Précisons que le chercheur Desharnais et l’un de ses étudiants au doctorat, Jean-Lou De Carufel, étudient particulièrement une algèbre appelée algèbre démoniaque qui sert de structure de base à plusieurs algèbres de raffinement. Mais attention les amis, qu’on ne s’imagine surtout pas ici que les programmes sont guidés par des entités surnaturelles et malveillantes ! « Le terme démoniaque reflète simplement le fait qu’il faut prévoir les pires comportements des programmes, comportements dits démoniaques dans la littérature sur la construction et la vérification des programmes », nous rassure l’expert en la matière.
 
Devenu spécialiste de l’algèbre de Kleene, comme nous venons de le voir concernant son premier objet de recherche, Jules Desharnais veut, dans un deuxième temps, reformuler la théorie du contrôle des systèmes à événements discrets en utilisant celle des algèbres de Kleene.
 
Évidemment, nous préférions lui demander de nous expliquer ça davantage à partir d'un exemple concret. Agréable surprise, la réponse du professeur nous montre finalement que son application est très universelle: « Cette théorie s'applique par exemple dans le domaine du contrôle des chaînes de montage », dit-il. Mais il utilisera un exemple encore plus général pour nous la faire comprendre:
 
« Prenez un labyrinthe dans lequel se trouvent un chat et une souris. Supposez qu’il y a dans le labyrinthe des portes contrôlables pour empêcher le chat ou la souris de passer de certaines sections à des sections adjacentes. Supposez aussi qu’il y a des capteurs dans certaines sections permettant de déterminer si le chat ou la souris est dans ces sections. L’objectif est de calculer (construire) un programme contrôleur qui permet une liberté maximale au chat et à la souris tout en fermant les portes appropriées pour les empêcher de se retrouver dans la même section du labyrinthe. La théorie du contrôle permet de calculer un tel contrôleur. Ce qui complique le calcul, c’est le fait qu’il n’y a pas de portes et de capteurs pour chaque section. »
 
Faut-il mettre ou ne pas mettre de la crème dans le biscuit au moment X ou au moment Y dans une chaîne de montage? C'est un peu le même défi !
 
Après cette brillante vulgarisation, il nous explique qu’ici son premier objectif est de reformuler la théorie du contrôle de manière plus élégante et plus facilement vérifiable, ce que devrait permettre l’algèbre de Kleene. Il a d’ailleurs réussi à faire une synthèse de quelques articles portant sur des concepts de contrôlabilité différents. « Déjà, cette synthèse est compacte et permet de mieux comprendre les liens entre ces concepts, grâce à une formule dont la démonstration est facilement vérifiable, ce qui est un atout important pour la communication des résultats », témoigne l’auteur des travaux toujours en cours.
 
Parlons maintenant de son troisième objet de recherche, celui qui s'attaque au problème de la sécurité des programmes.
 

La notion de sécurité à 100% d'un logiciel n'est pas une évidence


Un logiciel, ce n'est pas du matériel. Le matériel s’use et brise, ce qui implique cependant de pouvoir travailler avec des probabilités d'usure. Un logiciel, lui, ne s’use pas. « Il s'applique toujours - à la perfection même - s'il est dans les mêmes conditions », dénote bien le chercheur. À la perfection ! Cela ne veut malheureusement pas dire que la notion de sécurité à 100% est une évidence. Encore cette fameuse notion d’indécidabilité...
 
La notion d’indécidabilité a été évoquée plus haut au sujet des équations de l’algèbre de Kleene. L’un des grands drames de l’informatique, c’est l’existence des problèmes indécidables, c’est-à-dire des problèmes qu’aucun algorithme (méthode systématique et programmable) ne peut résoudre. Le plus connu de ces problèmes est le problème de l’arrêt. Il serait très utile en pratique d’avoir un programme P qui pourrait analyser un programme P’ quelconque et nous dire si oui ou non ce programme P’ termine toujours (tout programmeur a un jour écrit un programme qui tombe dans une boucle infinie non prévue). Mais on démontre facilement qu’un tel programme P n’existe pas.
 
« Le but de ma recherche en sécurité, c’est de développer une méthode d’analyse des programmes afin de déterminer s’ils satisfont certaines politiques de sécurité, pour ensuite modifier ces programmes afin de les rendre sécuritaires. Il s’avère que beaucoup de propriétés liées à la sécurité des programmes sont indécidables. C’est le cas par exemple d’une politique aussi simple que la suivante: un programme donné ne doit pas lire un fichier confidentiel pour ensuite le transmettre sur Internet. Ceci ne veut pas dire qu’il faille abandonner la recherche. Même si l’indécidabilité empêche de vérifier automatiquement à tout coup si un programme satisfait une politique de sécurité, il n’en reste pas moins que de nombreuses failles peuvent être découvertes de manière automatique dans beaucoup de programmes utilisés en pratique », assure Jules Desharnais.
 
Un autre de ses étudiants au doctorat, Frédéric Painchaud, en est d’ailleurs à programmer un analyseur de programmes Java afin d’extraire de ces programmes l’information adéquate (ni trop abstraite, ni trop détaillée) pour pouvoir ensuite déterminer si ces programmes satisfont certains types de politique de sécurité. Si le programme analyseur peut déterminer qu’un programme Java ne satisfait pas une politique donnée ou à tout le moins indiquer des parties de code à risque, alors la théorie du contrôle pourra être utilisée pour modifier le programme afin de le rendre sécuritaire, quitte à devoir se passer de certaines fonctionnalités du programme. L’environnement d’exécution des programmes Java permet déjà de vérifier des permissions d’accès simples. La recherche vise à permettre la mise en oeuvre de politiques de sécurité plus complexes et adaptées à chaque utilisateur.
 
Toute cette recherche sur la sécurité des programmes s’appuie d’ailleurs déjà sur une décennie d’efforts, partagés même avec des partenaires autres qu’universitaires: « Nous avons débuté en 1997 grâce à des contrats du CRDV (aujourd’hui RDDC-Valcartier) qui ont été accordés au groupe de recherche LSFM », confirme celui qui fait partie de ce groupe (langages, sémantique et méthodes formelles) du Département d'informatique et génie logiciel, qui compte actuellement huit membres chercheurs, dont plusieurs font de la recherche sur la sécurité. « Le groupe était à l’époque dirigé par Mourad Debbabi, aujourd’hui professeur à l’Université Concordia », tient-il à préciser.
 
Outre Jules Desharnais, entre 1997 et 2001, sous les thèmes de la « Détection de code malicieux » et de la « Détection de code malicieux dans les logiciels commerciaux », ces travaux impliquèrent également les chercheurs Jean Bergeron et Nadia Tawbi. Les contrats du CRDV ont mené à la programmation de prototypes qui ont permis de valider certaines approches. Ils ont aussi permis à LSFM, au CRDV et à des étudiants de gagner des prix fort intéressants:
  • la médaille d’or TechnoFed’2000, dans la catégorie Partenariat;
  • l’OCTAS de la Relève universitaire décerné par la Fédération de l’informatique du Québec (en 2001);
  • un prix d'excellence, dans la catégorie Institutions, au Concours canadien de l'informatique et de la productivité pour l'avenir (CIPA 2001), la plus prestigieuse compétition dans le domaine des technologies de l'information au Canada.

Bien branché à l’IFIP


Algèbre démoniaque, théorie du contrôle des systèmes à événements discrets, notion d’indécidabilité, tout ça souvent déclinés à la sauce des algèbres de Kleene... Finalement,  nous nous en sommes bien sortis dans notre voyage au monde de la recherche version Jules Desharnais !
 
Au fait, sont-ils nombreux de par le vaste monde à s'intéresser aux algèbres de Kleene ? Lui n'est déjà pas solitaire, car il collabore étroitement sur le sujet avec un chercheur universitaire allemand, Bernhard Möller, et un autre du Royaume-Uni, Georg Struth. Il collabore également avec Richard St-Denis et Marc Frappier, de l’Université de Sherbrooke, avec lesquels il a fait une demande de subvention d’équipe au FQRNT l’automne passé, sur le thème de la synthèse de contrôleurs de programmes pour la mise en œuvre de politiques de sécurité (et il y a une composante sur l’algèbre de Kleene dans cette recherche). Pour la période 2003-2007, une subvention CRSNG de 28 000 $/an lui avait déjà permis de concrétiser son projet de recherche intitulé: « Les mathématiques de l'analyse et de la construction de programmes, avec la sécurité comme application principale. »
 
Précisons ici que les chercheurs du domaine se rencontrent régulièrement dans le cadre d’une conférence qui se tient tous les 18 mois. La dernière à avoir eu lieu est The 9th International Conference on Relational Methods in Computer Science and the 4th International Workshop on Applications of Kleene Algebra (RelMiCS 9/AKA 4), à Manchester, au Royaume-Uni, entre le 29 août et le 2 septembre 2006.
 
Parlant de la collaboration internationale, depuis 1995, il a accepté l'invitation à devenir membre permanent du groupe de travail Algorithmic Languages and Calculi de l’International Federation for Informatic Processing  (IFIP). Un Working Group d'environ 30 chercheurs de haut niveau - dont cinq Canadiens - qui s'intéresse beaucoup à l'élégance des preuves (but de ce comité: To explore and evaluate new ideas in the field of programming, possibly leading to the design of new languages).
 
Avec tout ça, comme il a actuellement cinq étudiants au doctorat sous sa supervision - dont quatre sont finissants, alors qu’une étudiante commence - il est passablement occupé en recherche. Mais souhaitons que Jules Desharnais ne perde aussi jamais sa passion d’enseigner tant il est frappant de voir son visage qui s'illumine totalement lorsqu'il se lève au tableau. Ce qui doit faire la grande joie de ses étudiants. Oui, il a d'ailleurs un petit tableau de classe, avec le crayon feutre et tout, dans son propre bureau de professeur, malgré l'étroitesse du lieu. Et c’est parce qu’il s’y est levé à plusieurs reprises pour nous expliquer ses travaux, lors de l’heure qu’il nous a consacrée, que nous avons nous aussi été témoins de ce regard si allumé.