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.

Abstract

Graph representations are among the most common and effective ways to model all kinds of natural or human-made objects. Once two objects or problems have been represented as graphs (i.e. as collections of objects possibly connected by pairwise relations), their comparison is a fundamental question in many different applications and is referred to as graph matching. The work presented in this document investigates approximate graph matching techniques and their application in software engineering as efficient ways to retrieve the evolution through time of software artifacts. The research work we carried involves three distinct but related aspects. First, we consider approximate graph matching problems within the Error-Tolerant Graph Matching framework, and propose a tabu search technique initialised with local structural similarity measures. Second, we address the matching of software artifacts, such as class diagrams, and propose new concepts able to integrate efficiently the rich lexical information to our tabu search. Third, based on matchings obtained from the application of our approach to subsequent class diagrams, we proposed new design evolution metrics and assessed their usefulness in defect prediction models. The following paragraphs detail each of those three aspects. Approximate Graph Matching Many practical problems can be modeled as approximate graph matching (AGM) problems in which the goal is to find a ”good” matching between two objects represented as graphs. Unfortunately, existing literature on AGM do not propose generic techniques readily usable in research areas other than image processing and biochemistry. To address this situation, we tackled in a generic way, the AGM problems. For this purpose, we first select, out of the possible formulations, the Error Tolerant Graph Matching (ETGM) framework that is able to model most AGM formulations. Given that AGM problems are generally NP-hard, we based our resolution approach on meta-heuristics, given the demonstrated efficiency of this family of techniques on (NP-)hard problems. Our approach avoids as much as possible assumptions about graphs to be matched and tries to make the best out of basic graph features such as node connectivity and edge types. Consequently, the proposal is a local search technique using new node similarity measures derived from simple structural information. The proposed technique was devised as follows. First, we observed and empirically validated that initializing a local search with a very small subset of ”correct” node matches is enough to get excellent results. Instead of directly trying to correctly match all nodes and edges of a given graph to the nodes and edges of another graph, one could focus on correctly matching a reduced subset of nodes. Second, in order to retrieve such subsets, we resorted to the concept of local node similarity. Our approach consists in assessing, by analyzing their neighborhoods, how likely it is to have a pair of nodes included in a good matching. We investigated many ways of computing similarity values between pairs of nodes and proposed additional techniques to attach a level of confidence to computed similarity value. Our work results in a similarity enhanced tabu algorithm (Sim-T) which is demonstrated to be more accurate and efficient than known state-of-the-art algorithms. Approximate Diagram Matching in software engineering Given the size and complexity of OO systems, retrieving and understanding the history of the design evolution is a difficult task which requires appropriate techniques. Building on the work done for generic AGM problems, we propose MADMatch, a Many-to-many Approximate Diagram Matching algorithm based on an ETGM formulation. In our approach, design representations are modeled as attributed directed multi-graphs. Transformations such as modifying, renaming, or merging entities in a software diagram are explicitly taken into account through edit operations to which specific costs can be assigned. MADMatch fully integrates the textual information available on diagrams and proposes several concepts enabling accurate and fast computation of matchings. We notably integrate to our proposal the use of “termal footprints” which capture the lexical context of any given entity and are exploited in order to reduce the search space of our tabu search. Through several case studies involving different types of diagrams (such as class diagrams, sequence diagrams and labeled transition systems), we show that our algorithm is generic and advances the state of art with respect to scalability and accuracy. Design Evolution Metrics for Defect Prediction Testing is the most widely adopted practice to ensure software quality. However, this activity is often a compromise between the available resources and sought software quality. In object-oriented development, testing effort should be focused on defect-prone classes or alternatively on classes deemed critical based on criteria such as their connectivity or evolution profile. Unfortunately, the identification of defect-prone classes is a challenging and difficult activity on which many metrics, techniques, and models have been tried with mixed success. Following the retrieval of class diagrams' evolution by our graph matching approach, we proposed and investigated the usefulness of elementary design evolution metrics in the identification of defective classes. The metrics include the numbers of added, deleted, and modified attributes, methods, and relations. They are used to recommend a ranked list of classes likely to contain defects for a system. We evaluated the efficiency of our approach according to three criteria: presence of defects, number of defects, and defect density in the top-ranked classes. We conducted experiments with small to large systems and made comparisons against well known complexity and OO metrics. Results show that the design evolution metrics, when used in conjunction with known metrics, improve the identification of defective classes. In addition, they provide evidence that design evolution metrics make significantly better predictions of defect density than other metrics and, thus, can help in reducing the testing effort by focusing test activity on a reduced volume of code.