Contexte de la collaboration

Cette proposition se place dans le cadre d’une collaboration entre la société CAST (Paris) et le laboratoire LIRIS (Université Lyon 1). La collaboration s’inscrit dans les domaines des Graphes et Big Data.

Contexte scientifique

Les graphes des applications sont des structures de données extraites automatiquement à partir de l’analyse du code, des fichiers projets (comme les pom.xml dans le monde Java), et des structures de données (relationnelles, hiérarchiques ou simples fichiers). CAST Imaging dispose d’une grande base de connaissance de ces graphes qui couvre aujourd’hui plus de 50 langages et technologies concernant des applications à la fois modernes exploitant les dernières nouveautés des Cloud providers comme AWS ou Azure, mais aussi des plus classiques faites autour de JEE, .NET, C, les bases de données relationnelles, etc. Ces applications sont représentées via une interface graphique dédiée par des graphes où les éléments du code (fonction, classes, procédure, tables, fichiers de données, etc) sont représentés par des nœuds, et les dépendances (appel, héritage, composition, …) entre ces éléments sont représentées par des arêtes/arcs. Par conséquent, l’analyse et la compréhension de ces applications passent naturellement par l’analyse et la compréhension de leurs graphes respectifs.

Objectifs de la thèse

Les graphes des applications peuvent comporter plusieurs millions de nœuds et d’arêtes/arcs. Ils peuvent avoir des représentations lourdes notamment quand nous souhaitons prendre en compte un maximum d’informations sur les applications. Ils deviennent des multigraphes hétérogènes où les nœuds ne sont pas tous de même nature, les arêtes peuvent décrire plusieurs relations entre une même paire de nœuds, avec des ensembles d’attributs et de poids à la fois sur les nœuds et sur les arêtes. Ces graphes sont riches en informations, mais leurs analyse et visualisation dans leurs structures réelles deviennent difficiles. Notre objectif dans cette thèse est donc de s’appuyer sur des modélisations avancées et des algorithmes de graphes poussés pour analyser les graphes d’applications et proposer des représentations simples de ces graphes facilement explorables d’un point de vue algorithmique et compréhensibles d’un point de vue visuel.

Dans un premier temps, nous nous focaliserons sur l’enrichissement des graphes d’applications actuels aux niveaux structurel et sémantique :

D’un point de vue structurel, nous identifierons clairement les classes de nœuds (hétérogénéité) et les relations structurelles intra-classe et inter-classes (héritage, inclusion, appels de fonctions, etc).
D’un point de vue sémantique, nous capturerons un maximum d’informations sémantiques sous forme d’attributs, de poids ou de relations entre objets.
Nous développerons par la suite des techniques de stockage et d’indexation de ces graphes adaptées au passage à l’échelle.

Dans un deuxième temps, nous mènerons une analyse algorithmique des graphes d’applications. Les structures macroscopiques des graphes d’applications sont quelconques, mais l’analyse de leurs sous-graphes, la recherche et la découverte de patterns et des propriétés structurelles permettent une meilleure compréhension du graphe. L’analyse des graphes d’applications pourra s’appuyer à la fois sur des algorithmiques d’exploration de graphes et sur des algorithmes de machine learning (clustering, graph embedding, etc). Cette analyse algorithmique des graphes d’applications servira d’une part à mieux comprendre les ces graphes et d’autre part à concevoir des représentations simples de ces graphes qui faciliteront leur visualisation. Ces représentations seront des structures résumant le graphe d’application sous forme de structures hiérarchiques multi-niveaux, avec des regroupements et compressions de nœuds/sous-graphes, arêtes, etc. Pour ce faire, nous serons amenés à explorer la littérature des graphes liées aux techniques de décomposition, d’agrégation et de compression de graphes, pour proposer de telles représentations et de les adapter pour qu’elles prennent en compte les contraintes réelles des graphes d’applications (hétérogénéité des nœuds et arêtes, attributs, poids, etc) et qui préservent au mieux les propriétés structurelles des graphes d’applications.

La visualisation des graphes d’applications est une partie centrale de la thèse. L’objectif est de proposer des méthodes de navigation dans le graphe d’application qui permettent de guider/orienter l’utilisateur dans la découverte et la compréhension du graphe sans le submerger immédiatement avec tout le détail que nous disposons. D’où l’intérêt des représentations des graphes d’applications décrites dans le paragraphe précédent. Ces représentations simples et simplifiées donneront une visualisation claire qui permettra à l’utilisateur de faire une meilleure analyse visuelle du graphe. Notre objectif dans cette partie de visualisation est de développer des algorithmes qui donneront une meilleure performance en temps d’analyse (affichage, exploration etc), et une visualisation compréhensible (représentations réduites et simplifiées). Pour ce faire, nous explorons des techniques de visualisation progressive de sorte que l’utilisateur puisse découvrir à la demande (d’une façon interactive) ou automatiquement un graphe d’application et ses représentations pas-à-pas, et de plus, d’afficher ces parties du graphe de différents angles avec différentes informations en utilisant par exemple des vues 3D des représentations des graphes d’applications.

Finalement, il est à noter que ces graphes d’applications sont dynamiques car les applications sont mises à jour régulièrement. Nous serons amenés à automatiser les mises à jour sur les graphes d’applications.

Les candidats ayant obtenu un M2 recherche/ingénieur en informatique, intéressés, disposant de connaissances approfondies en théorie et algorithmique des graphes, en programmation et des notions en big data et machine learning sont priés d’envoyer leur CV détaillé, une lettre de motivation pour le sujet et des relevés de notes (avec le classement si possible) aux emails suivants :

Hamamache Kheddouci : hamamache.kheddouci@liris.cnrs.fr,
Salma Nagbi : s.nagbi@castsoftware.com

Une lettre de recommandation d’une personne qui vous a encadré par le passé (avec ses informations de contact) serait un plus !

Le processus de recrutement se déroulera en plusieurs étapes :

• Entretien avec le responsable scientifique au LIRIS
• Entretien avec l’un de nos chefs d’équipe et/ou notre directeur R&D
• Un échange final pour informer sur la décision finale