<  Retour au portail Polytechnique Montréal

Langage dédié et analyse automatisée pour la détection de patrons au sein de traces d'exécution

Kadjo Gwandy Kouamé

Mémoire de maîtrise (2015)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (2MB)
Afficher le résumé
Cacher le résumé

Résumé

La complexité des systèmes informatiques distribués et à plusieurs unités de calcul a introduit de nouvelles classes de problèmes. Ces problèmes sont difficiles à reproduire et leur complexité accrue a suggéré l'introduction de nouvelles méthodes de compréhension des systèmes. L'analyse dynamique, à l'aide de traces d'exécution, permet de comprendre les systèmes à partir de leurs données d'exécution. Les traces d'exécution enregistrent, sous forme d'événements, les informations précises et détaillées de l'exécution du système instrumenté. Pour des systèmes comme le noyau d'exploitation de Linux, le traçage fournit des événements de bas niveau (appels systèmes, fautes de pages). De plus, en quelques secondes, le fichier de trace peut enregistrer des millions d'événements. Des visionneuses de trace, telle que Trace Compass, ont été développées dans le but de fournir des analyses de la trace sous différents angles de vue tels que l'allocation des ressources ou l'usage des unités de calcul, et à un haut niveau d'abstraction. Cependant, au-delà des analyses déjà fournies par les visionneuses, les utilisateurs souhaiteraient pouvoir créer des analyses personnalisées qui représenteraient mieux leurs besoins. Par exemple, un utilisateur pourrait tenter de vérifier si le système a subi une attaque particulière. Il faudrait dans ce cas précis pouvoir appliquer à la trace une analyse spécialisée qui permettrait de vérifier la présence d'une séquence d'événements ou d'informations qui décrit l'attaque recherchée. Il existe donc un besoin quant à la nécessité d'identifier des formes particulières ou de retrouver des séquences d'intérêts au sein de la trace. Ce travail propose l'introduction d'un langage déclaratif utilisant les automates finis pour la description de patrons d'intérêts. Les patrons décrits sont ensuite passés à un analyseur élaboré afin de vérifier et repérer leurs présences au sein de traces d'exécution. L'utilisation de machines à états pour la description des patrons permet de décrire des patrons complexes. Ainsi, la mise en place d'un mécanisme de suivi de l'exécution des patrons a été réalisée. Le langage déclaratif proposé est conçu de façon déclarative en XML. Il permet de représenter avec succès tous les types de patrons rencontrés dans la littérature (patrons de détection d'attaques, patrons de test de programmes, patrons d'évaluation de performance, patrons d'agrégations des événements...). La spécification du langage proposé permet de créer des événements synthétiques qui peuvent être traités par l'analyseur au fur et à mesure qu'ils sont créés. La solution proposée dans ce mémoire devrait être capable de traiter les traces de grandes tailles (500MB et plus); la performance en terme de temps d'extraction des données est donc importante. Nous nous assurons qu'elle est au moins aussi bonne que celle des travaux antérieurs du même genre et que la déviation par rapport à la méthode d'extraction standard de Trace Compass reste acceptable. La solution proposée écrit directement les données sur le disque. Elle n'accumule donc pas d'informations en mémoire. L'analyse en terme d'espace en mémoire est donc négligeable. De plus, nous démontrons l'utilité de l'approche proposée à l'aide d'exemples concrets de cas d'utilisation. Une tentative de découverte de la source d'un défaut de requête Web est présentée ainsi qu'un exemple de détection d'attaque dans le système. Enfin, nous proposons à la fin de notre étude une liste de suggestions pour des améliorations possibles à la solution en termes de description des patrons et de réduction du temps de l'analyse.

Abstract

The complexity of distributed and multi-core systems introduced new classes of problems. These problems could be difficult to reproduce and their increasing complexity has suggested the introduction of new methods of systems comprehension. Dynamic analysis, through execution traces, allows to understand the system behavior from its execution data. The execution traces record, in the form of events, accurate and detailed information about the execution of an instrumented system. For systems like the Linux kernel, tracing provides low level events such as system calls and page faults. Moreover, in a few seconds, the trace file can record millions of events. Visualizers, like Trace Compass, were developed to provide analysis of the trace from different points of view such as ressources allocation and CPU usage, and with a high-level of abstraction. However, beyond the analyses that have been already provided by the visualizers, users would like to be able to create custom analyses that better represent their needs. For example, a user could attempt to verify if the system is under a particular attack. It should then be possible to apply to the trace a specialized analysis that would verify the presence of a sequence of events or information that describes the intended attack. Thus, there is a need to be able to identify patterns or to find predefined sequences of events within the trace. This work proposes the introduction of a declarative automata-based pattern description language. The described patterns are then passed to an analyzer designed to efficiently verify and detect their presence within the execution trace. The use of state machines allows to describe complex patterns. Thus, a mechanism to follow the execution of the patterns has been implemented. The proposed language is designed declaratively in XML. It has successfully represented all the types of pattern found in the literature (security attack patterns, testing patterns, system performance patterns, events aggregation patterns, ...). The language specification allows to create synthetic events that can be processed by the analyzer as they are created. This proposal should be able to process large trace files (1GB or more). Thus, performance in terms of time of data extraction is important. We ensure that this solution is at least as good as previous ones of the same kind and that the deviation from the standard extraction method of Trace Compass remains acceptable. The proposed solution writes the data directly to disk. It therefore does not accumulate information in memory. The analysis in terms of memory space is negligible. In addition, we try to demonstrate the usefulness of our approach with some application test cases. An example of an attempt to find the root cause of a web request defect and an example of attack detection in a system are presented. Finally, we propose at the end of this study a list of suggestions for possible improvements of the solution in terms of the description of patterns and reduction of the time of the analysis.

Département: Département de génie informatique et génie logiciel
Programme: Génie informatique
Directeurs ou directrices: Michel Dagenais
URL de PolyPublie: https://publications.polymtl.ca/1900/
Université/École: École Polytechnique de Montréal
Date du dépôt: 16 déc. 2015 09:53
Dernière modification: 03 mai 2023 14:10
Citer en APA 7: Kouamé, K. G. (2015). Langage dédié et analyse automatisée pour la détection de patrons au sein de traces d'exécution [Mémoire de maîtrise, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/1900/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel

Afficher document Afficher document