Approximate Graph Matching for Software Engineering

La représentation en graphes est l'une des plus communément utilisées pour la modélisation de toutes sortes d'objets ou problèmes. Un graphe peut être brièvement présenté comme un ensemble de nœuds reliés entre eux par des relations appelées arêtes ou arcs. La comparaison d'objets, représentés sous forme de graphes, est un problème important dans de nombreuses applications et une manière de traiter cette question consiste à recourir à l'appariement de graphes. Le travail présenté dans cette thèse s'intéresse aux techniques d'appariement approché de graphes et à leur application dans des activités de génie logiciel, notamment celles ayant trait à l'évolution d'un logiciel. Le travail de recherche effectué comporte trois principaux aspects distincts mais liés. Premièrement, nous avons considéré les problèmes d'appariement de graphes sous la formulation ETGM (Error-Tolerant Graph Matching : Appariement de Graphes avec Tolérance d'Erreurs) et proposé un algorithme performant pour leur résolution. En second, nous avons traité l'appariement d'artefacts logiciels, tels que les diagrammes de classe, en les formulant en tant que problèmes d'appariement de graphes. Enfin, grâce aux solutions obtenues sur les diagrammes de classes, nous avons proposé des mesures d'évolution et évalué leur utilité pour la prédiction de défauts. Les paragraphes suivants détaillent chacun des trois aspects ci-dessus mentionnés. Appariement approché de graphes Plusieurs problèmes pratiques peuvent être formulés en tant que problèmes d'Appariement Approché de Graphes (AAG) dans lesquels le but est de trouver un bon appariement entre deux graphes. Malheureusement, la littérature existante ne propose pas de techniques génériques et efficaces prêtes à être utilisées dans les domaines de recherche autres que le traitement d'images ou la biochimie. Pour tenter de remédier à cette situation, nous avons abordé les problèmes AAG de manière générique. Nous avons ainsi d'abord sélectionné une formulation capable de modéliser la plupart des différents problèmes AAG (la formulation ETGM). Les problèmes AAG sont des problèmes d'optimisation combinatoire reconnus comme étant (NP-)difficiles et pour lesquels la garantie de solutions optimales requiert des temps prohibitifs. Les méta-heuristiques sont un recours fréquent pour ce genre de problèmes car elles permettent souvent d'obtenir d'excellentes solutions en des temps raisonnables. Nous avons sélectionné la recherche taboue qui est une technique avancée de recherche locale permettant de construire et modifier graduellement et efficacement une solution à un problème donné. Nos expériences préliminaires nous ont révélé qu'il était suffisant d'initialiser une recherche locale avec un sous-ensemble très réduit (2 à 5%) d'une solution (quasi-)optimale pour se garantir d'excellents résultats. Étant donné que dans la plupart des cas, cette information n'est pas disponible, nous avons recouru à l'investigation de mesures de similarités pouvant nous permettre de prédire quels sont les appariements de nœuds les plus prometteurs. Notre approche a consisté à analyser les voisinages des nœuds de chaque graphe pour associer à chaque possible appariement de nœud une valeur de similarité indiquant les chances de retrouver la paire de nœuds en question dans une solution optimale. Nous avons ainsi exploré plusieurs possibilités et découvert que celle qui fonctionnait le mieux utilisait l'estimation la plus conservatrice, celle où la notion de voisinage similaire est la plus « restrictive ». De plus, pour attacher un niveau de confiance à cette mesure de similarité, nous avons appliqué un facteur correcteur tenant compte notamment des alternatives possibles pour chaque paire de nœuds. La mesure de similarité ainsi obtenue est alors utilisée pour imposer une direction en début de recherche locale. L'algorithme qui en résulte, SIM-T a été comparé à différents algorithmes récents (et représentant l'état de l'art) et les résultats obtenus démontrent qu'il est plus efficace et beaucoup plus rapide pour l'appariement de graphes qui partagent une majorité d'éléments identiques. Appariement approché de diagrammes en génie logiciel. Compte tenu de la taille et de la complexité des systèmes orientés-objet, retrouver et comprendre l'évolution de leur conception architecturale est une tache difficile qui requiert des techniques appropriées. Diverses approches ont été proposées mais elles se concentrent généralement sur un problème particulier et ne sont en général pas adaptées à d'autres problèmes, pourtant conceptuellement proches. Sur la base du travail réalisé pour les graphes, nous avons proposé MADMatch, un algorithme (plusieurs-à-plusieurs) d'appariement approché de diagrammes. Dans notre approche, les diagrammes architecturaux ou comportementaux qu'on peut retrouver en génie logiciel sont représentés sous forme de graphes orientés dont les nœuds (appelées entités) et arcs possèdent des attributs. Dans notre formulation ETGM, les différences entre deux diagrammes sont comprises comme étant le résultat d'opérations d'édition (telles que la modification, le renommage ou la fusion d'entités) auxquelles sont assignées des coûts. L'une des principales différences des diagrammes traités, par rapport aux graphes de la première partie, réside dans la présence d'une riche information textuelle. MADMatch se distingue par son intégration de cette information et propose plusieurs concepts qui en tirent parti. En particulier, le découpage en mots et la combinaison des termes obtenus avec la topologie des diagrammes permettent de définir des contextes lexicaux pour chaque entité. Les contextes ainsi obtenus sont ultérieurement utilisés pour filtrer les appariements improbables et permettre ainsi des réductions importantes de l'espace de recherche. A travers plusieurs cas d'étude impliquant différents types de diagrammes (tels que les diagrammes de classe, de séquence ou les systèmes à transition) et plusieurs techniques concurrentes, nous avons démontré que notre algorithme peut s'adapter à plusieurs problèmes d'appariement et fait mieux que les précédentes techniques, quant à la précision et le passage à l'échelle. Des métriques d'évolution pour la prédiction de défauts. Les tests logiciels constituent la pratique la plus répandue pour garantir un niveau raisonnable de qualité des logiciels. Cependant, cette activité est souvent un compromis entre les ressources disponibles et la qualité logicielle recherchée. En développement Orienté-Objet (OO), l'effort de tests devrait se concentrer sur les classes susceptibles de contenir des défauts. Cependant, l'identification de ces classes est une tâche ardue pour laquelle ont été utilisées différentes métriques, techniques et modèles avec un succès mitigé. Grâce aux informations d'évolution obtenues par l'application de notre technique d'appariement de diagrammes, nous avons défini des mesures élémentaires d'évolution relatives aux classes d'un système OO. Nos mesures de changement sont définies au niveau des diagrammes de classes et incluent notamment les nombres d'attributs, de méthodes ou de relations ajoutés, supprimés ou modifiés de version en version. Elles ont été utilisées en tant que variables indépendantes dans des modèles de prédiction de défauts visant à recommander les classes les plus susceptibles de contenir des défauts. Les métriques proposées ont été évaluées selon trois critères (variables dépendantes des différents modèles) : la simple présence (oui/non) de défauts, le nombre de défauts et la densité de défauts (relativement au nombre de Lignes de Code). La principale conclusion de nos expériences est que nos mesures d'évolution prédisent mieux, et de façon significative, la densité de défauts que des métriques connues (notamment de complexité). Ceci indique qu'elles pourraient aider à réduire l'effort de tests en concentrant les activités e tests sur des volumes plus réduits de code.