Il convient de contacter rapidement les encadrants du sujet choisi, en leur indiquant le nom des étudiants concernés, typiquement celui des deux étudiants d'un binôme. Un mail ne mentionnant qu'un seul nom ne sera pas pris en compte.
Il peut y avoir un dialogue entre les encadrants d'un projet et plusieurs binômes qui souhaitent traiter ce sujet. Le binôme retenu n'est pas nécessairement le premier qui a pris contact avec les encadrants.
Les encadrants font connaître leur réponse quelques jours plus tard, par un mail destiné aux binômes et à moi. L'attribution est définitive à la réception de la confirmation du binôme par mail aux encadrants et à moi en indiquant clairement le sujet concerné.
Il est souhaitable que le travail commence dès la fin des examens répartis et de tirer au mieux parti des deux semaines d'inter-semestres pour prendre connaissance du sujet et des documents éventuels que les encadrants vous demanderont de lire.
Les soutenances auront lieu fin mai, après les examens répartis de S2. Les dates seront précisées davantage ultiérieurement. Il est conseillé de préparer sa soutenance suffisamment à l'avance et avec ses encadrants.
| Numéro | Titre | Encadrants | Étudiants | Description | Affecté à |
|---|---|---|---|---|---|
| 1 | Validation numérique parallèle | Pacôme Eberhardt, Pierre Fortin, & Fabienne Jézéquel | 2 | ci-dessous | |
| 2 | Interpolation polynomiale multi-précision avec contrôle d'erreur | Christoph Lauter | 2 | ci-dessous | |
| 3 | Binding templaté C++ d'une bibliothèque de précision agrandie | Christoph Lauter | 2 | ci-dessous | |
| 4 | Algorithme de Berlekamp et Massey pour les codes correcteurs | Jérémy Berthomieu | 2 | sujet PDF | Nguyen/Berrezoug |
| 5 | Algorithmique pour les entiers p-adiques | Jérémy Berthomieu | 2 | sujet PDF | |
| 6 | Décomposition en somme de carrés de polynômes | Mohab Safey El Din | 2 | ci-dessous | |
| 7 | Résolution haute-performance de systèmes polynomiaux bi-variés | Mohab Safey El Din | 2 | ci-dessous | |
| 8 | Lest We Remember: Cold-boot Attacks on Encryption-Keys | Bruno Escoffier, Jean-Charles Faugère & Ludovic Perret | 2 ou 3 | sujet PDF | |
| 9 | Réalisation d'une plateforme de tests SSL/TLS | Contact préalable Guenaël Renault | 2 ou 3 | archive tar compressée du sujet | Benoît/Bourdrez/Coll/Diab |
| 10 | Évaluation à grande précision de Γ(p/q) | Marc Mezzarobba | 2 | sujet PDF | |
| 11 | Manipulation de suites P-récursives avec SageMath | Marc Mezzarobba | 2 | sujet PDF | |
| 12 | Application d’arithmétique d’intervalles pour un calcul de norme l2 | Anastasia Volkova-Lozanova & Christoph Lauter | 2 | ci-dessous | |
| 13 | Cassage de Codes avec des Polynômes | Jean-Charles Faugère et Ludovic Perret | 2 ou 3 | ci-dessous | Brit/Merah |
| 14 | Description à venir | Guenaël Renault | 2 | ci-dessous | Beauvais/Lo |
Du fait de leur précision finie, l'utilisation de nombres à virgule flottante pour représenter les nombres réels introduit des erreurs d'arrondi dans les calculs numériques. La propagation de ces erreurs peut alors dégrader très significativement la qualité numérique des résultats. Le logiciel CADNA permet de valider numériquement des codes scientifiques en estimant le nombre de chiffres significatifs exacts des résultats.
Avec le développement actuel du calcul haute performance, cette validation numérique devient cruciale pour de nombreux codes dans les centres de calcul académiques et industriels. Mais les architectures de calcul basées sur les CPU actuels présentent plusieurs niveaux de parallélisme (multi-noeud, multi-coeur, SIMD) qui rendent difficile l'intégration de CADNA dans ces codes.
Travail à effectuer :Nous avons déjà développé des versions de CADNA adaptées aux processeurs multi-coeur (via OpenMP) et aux unités SIMD (SSE, AVX). Le premier but de ce projet serait donc d'implémenter une version de CADNA pour le parallélisme multi-noeud à l'aide du standard MPI.
Ensuite nous aimerions tester l'impact de CADNA sur une application de référence parallélisée entre plusieurs noeuds, puis en associant progressivement les deux autres niveaux de parallélisme. On pourra pour cela s'appuyer sur un serveur de calcul disposant de plus d'une centaine de noeuds et sur un processeur Intel Xeon Phi à 60 coeurs (240 threads matériels).
Référence: logiciel CadnaLes nombres réels sont modelisés sur ordinateur par l'ensemble discret des nombres flottants. Chaque opération d'arithmétique flottante rend un résultat entâché d'erreur. Pour obtenir le résultat du calcul avec une erreur inférieure à une borne fixée à l'avance (erreur cible), il peut être nécessaire de faire ce calcul en arithmétique multi-précision.
Pour approcher la fonction f sur un intervalle I on peut utiliser l'interpolation[1]. Le théorème de Weierstrass montre qu'une fonction continue sur un intervalle I peut être approchée par un polynôme p avec une erreur que l'on peut faire tendre vers zéro[2].
Pour ce projet il faut établir les relations entre les paramètres d'interpolation (degré, précision, etc.) et l'erreur cible de l'interpolation. Il s'agit de concevoir un algorithme d'interpolation polynomiale avec contrôle d'erreur. Il faut calculer l'interpolation avec une erreur inférieure à l'erreur cible.
Pour le calcul de flottants multi-précision on utilisera la bibliothèque MPFR[3] et pour le calcul sur les intervalles flottants on utilisera MPFI[4]. Il n'y a aucun pré-requis d'utilisation de ces bibliothèques, il suffit de lire la documentation pendant ce projet pour pouvoir les utiliser. Les bibliothèques mentionnées sont installées dans les salles de la PPTI.
Références:La norme internationale IEEE754 définit principalement deux formats
(précisions) en virgule flottante: binary32 (single
precision) et binary64 (double precision). Ces deux
formats, ainsi que les opérations flottantes de base sur ces formats
(comme l'addition, la soustraction, la multiplication, la division et
la racine carrée) sont implantés en matériel et couramment
utilisés. Pour la plupart des applications de calcul scientifique, ces
formats sont suffisamment précis.
Certaines applications, en revanche, nécessitent des précisions plus grandes, sans pour autant avoir besoin d'un support pour plusieurs milliers de bits. Justement, à partir de quelques milliers de bits, des bibliothèques de calcul en multiprécision arbitraire, comme MPFR, deviennent efficaces.
Pour le domaine entre 53 bits de précision et quelques centaines de
bits (512 bits), des bibliothèques de calcul en grande précision
spécialisées existent, comme par
exemple, libwidefloat. L'efficacité de cette bibliothèque
vient surtout du fait qu'elle évite toute allocation dynamique de
mémoire.
Cette dernière bibliothèque est encore relativement jeune mais couvre déjà toutes les opérations de base ainsi que les comparaisons, des conversions et d'autres opérations auxiliaires. Elle fournit en tout 16 types pour des formats en virgule flottante allant de 32 à 512 bits. Pour des raisons d'efficacité, elle est écrite en C relativement bas niveau.
Ce caractère proche du matériel dessert en revanche la bibliothèque
quand il s'agit de l'intégrer à un code C ou C++ existant, écrit pour
la plupart des cas pour le format binary64 (double
precision). La bibliothèque ne fournit ses opérations que sous la
forme de fonctions alors que le code existant utilise des opérations
infixes.
Le but de ce projet est de fournir un wrapper efficace en C++ pour
la bibliothèque libwidefloat, couvrant toutes les
opérations de base (+, -, *, /, sqrt, <, <=, etc.) ainsi
que les opérations de conversion depuis et vers les entiers et les
formats IEEE754. Le wrapper devra être templaté afin de permettre
d'utiliser tous les 16 formats qu'offre la
bibliothèque libwidefloat
dans un même code et de façon mélangée.
Le code C++ demandé devra être très bien structuré et bien conçu afin
d'éviter, de la même façon que le fait déjà le code de la bibliothèque
libwidefloat, toute allocation de mémoire indue, ainsi
que toute copie de donnée superflue.
Le code final devra être analysé en termes de performances. Il devra être accompagné de tests pertinents pour sa fonctionalité et la manipulation de mémoire (fuite de mémoire, etc.)
Références:Le problème de déterminer quand un polynôme est positif sur les réels trouve de nombreuses applications dans les sciences de l'ingénieur et en informatique, notamment en arithmétique des ordinateurs. Dans ce contexte, le calcul d'un certificat prouvant la positivité du polynôme considéré est particulièrement important.
Pour prouver qu'un polynôme est positif sur les nombres réels, il suffit de pouvoir l'écrire comme une somme de carrés. Ce projet consiste à étudier les algorithmes existants et à les implanter. Ces algorithmes s'appuient sur une analyse de la localisation des racines du polynôme considéré et des algorithmes de calcul de pgcd. Les implantations seront écrites en C et C++ et utiliseront diverses bibliothèques de calcul formel ecrites en C ou C++.
Les systèmes polynomiaux apparaissent dans de nombreuses applications. Le cas de deux variables est important car il constitue un cas de base permettant d'appréhender de nombreuses applications notamment en robotique pour la planification de trajectoires.
Dans le cadre de ce projet, on étudiera des algorithmes pour la résolution de systèmes polynomiaux en deux variables. Il s'agira d'obtenir des implantations haute-performance d'algorithmes de complexité quasi-optimale vis-a-vis de la taille de la sortie. Ces implantations s'appuieront sur la bibliotheque NTL ecrite en C++.
TLS est aujourd'hui une brique logicielle essentielle de la sécurité sur Internet, largement utilisée et exploitée pour sécuriser les communications d'éléments sensibles : transactions bancaires via Internet, accès à des services web sécurisées, partage d'information sur les architectures orientées services, etc.
Ce protocole manque d'une solution logicielle permettant de tester ses implémentations au regard de leur sécurité : entre les nombreuses implémentations et variantes existantes (dont certaines accusent leur âge), et les vulnérabilités de ces dernières années (dont certaines ont eu un echo significatif dans la presse généraliste), cette clé de voûte de l'Internet doit pouvoir être testée méthodiquement pour en assurer sa robustesse et sa qualité raisonnable.
Le projet a pour objectif de réaliser un prototype de plateforme de tests TLS capable d'interroger de façon autonome un serveur ou un équipement quelconque en vue de tester les fonctionnalités ou vulnérabilités exposées. Du point de vue ingénierie logicielle, cette plateforme devra être conçue de façon modulaire ; les tests ainsi joués doivent pouvoir être extensibles (test en profondeur du protocole) et facilement modifiables. En effet, les protocoles cryptographiques font intervenir des briques de code complexes, nécessitant de nombreuses interactions entre le client et son serveur. Une fois ces tests joués, la plateforme doit pouvoir présenter une vue synthétique des résultats (par exemple au travers d'une interface web).
Il n'est pas attendue d'analyse du protocole TLS, ni de réalisation d'attaques particulières sur le protocole. La recette de ce projet se fera essentiellement sur la capacité à intégrer des éléments de tests disparates déjà existant, de les uniformiser, et d'intégrer cet ensemble dans une plateforme de tests autonome susceptible de générer un rapport. Elle s'inscrit donc dans une logique d'intégration continue, la différence notable avec les systèmes traditionnels étant que ces tests sont réalisés en mode boîte noire, éventuellement boîte grise (possibilité d'accéder au code afin de générer les tests dans un premier temps, puis de les soumettre au serveur dans un second temps).
Un exemple concret est le produit ssltest de Qualys/SSL Labs, mais cet outil présente l'inconvénient majeur de ne pas être autonome : nécessité d'exposer le serveur au système Qualys, ce qui n'est pas souhaitable pour des projets dont les systèmes ne sont pas accessibles depuis Internet. De plus, pour des besoins propres, les tests choisis ne sont pas forcément ceux qui nous intéressent, d'où un besoin d'extensivité (ce que ne permet pas leur suite de tests).
La plateforme livrée devra pouvoir donner certains renseignements bruts sur la pile TLS testée :
Pour aller plus loin, les sujets suivants pourront être creusés
La plateforme devra pouvoir produire des rapports agrégeant les résultats obtenus lors d'une exécution. Ce rapport pourra se faire sous la forme d'une page web ou d'un document PDF.
La norme l2 est une mesure importante dans le domaine des Filtres Digitaux. Appliquée à un filtre, elle est généralement calculée comme une somme infinie de produits de matrices. Cette somme ne peut pas être calculée exactement en précision finie. L'article [1] propose un algorithme pour calculer cette norme en précision arbitraire. L’erreur dans le calcul de la somme infinie a été décomposée en erreur de méthode et un erreur de calcul. Une analyse détaillée de l’erreur commise lors des calculs est fournie.
Cependant, les entrées de l’algorithme étaient considérées exactes. Or pour utiliser cet algorithme dans un générateur de filtres automatisé nous devons considérer que les entrées ne sont pas des nombres exacts mais plutôt de petits intervalles.
Ce projet a pour but de comprendre l’algorithme existant et d’implanter sa version en arithmétique d’intervalles. Cela peut être fait en utilisant une bibliothèque d’arithmétique d’intervalles multi-précision Arb [2] ou MPFI [3]. Il n'y a aucun pré-requis d'utilisation de ces bibliothèques, il suffit de lire la documentation pour pouvoir les utiliser. Certaines étapes de l’algorithme requerront quelques ajustements et par consequent des connaissances en calcul scientifique.
Références:
L’un des problèmes fondamentaux de la cryptographie est d’évaluer la sécurité des systèmes cryptographiques avec les techniques les plus puissantes. L’objectif du projet est de se familiariser avec une autre méthode générale : la cryptanalyse algébrique. L’idée directrice est de modéliser un algorithme cryptographique sous la forme d’un système d’équations non-linéaires. Le système est construit de manière à établir une correspondance entre les solutions de ce système et une information secrète du cryptosystème en question (par exemple, la clef privée d’un chiffrement). La sécurité du cryptosystème repose alors sur la difficulté, de trouver les zéros d'un système d'équations non-linéaires. On propose ici de mettre en œuvre une telle cryptanalyse sur un schéma de type post-quantique : soit un cryptosystème dont la clef-publique est un code correcteur d'erreurs, soit un cryptosystème multivarié. L'objectif est ici de mettre en œuvre une cryptanalyse algébrique avec un logiciel de calcul scientifique type Magma et de réaliser des expérimentations sur la phase de résolution.