<  Back to the Polytechnique Montréal portal

Analyse détaillée de trace en dépit d'événements manquants

Marie Martin

Master's thesis (2018)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (2MB)
Show abstract
Hide abstract

Abstract

With tracing, a lot of information can be gathered from a system or an application. This information needs to be exploited in order to provide a useful insight into the operation of our system. Experts develop complex trace analyses, but it does not take into account the fact that some events may have been lost during the tracing process, due to a much bigger flow of generated events than the capacity of writing into the trace. Therefore, the results may contain some inconsistencies. Our objective is to deal with these lost events at the trace analysis level. Using finite state machines to model the system, we are able to check the certainty of each new state. If no transition can be triggered from the current state, we check if one could be triggered from another state. By doing so, we can find inconsistencies. Then, we can correct these by looking for the sequence of transitions between the last coherent state and the incoherent one. Dijkstra's shortest-path algorithm is applied, with frequencies used as weights for the transitions. Once the transitions have been inferred, we can deduce the related lost events and their content. The proposed solution has been implemented in Trace Compass, a trace visualisation tool. The new information is displayed on the view representing the results of the analysis. It allowed us to apply our method to a few usecases, thus demonstrating its usefulness. The accuracy of the recovery phase is 53%. The overhead of the detection phase is reasonable for small traces, but can increase rapidly for bigger ones. However, the inference phase does not cost too much in any case.

Résumé

Le traçage offre une compréhension détaillée du fonctionnement d'un système ou d'une application, mais la simple étude d'une trace ne permet pas d'exploiter tout le potentiel des informations contenues dans les événements qui la constituent. C'est pour cela que les spécialistes des systèmes distribués et de l'analyse de performance développent des analyses complexes, qui sont ensuite intégrées aux outils de visualisation de traces. Ces outils supposent que le processus de traçage s'est déroulé sans erreurs. Néanmoins, il arrive que des événements soient perdus. Ceci survient lorsque les structures de données (souvent des tampons circulaires) devant stocker les événements avant leur écriture dans la trace sur disque sont pleins, alors que d'autres événements sont générés. Pour éviter de bloquer le système, le traceur doit jeter les événements les plus récents, ou écraser les plus anciens. Il n'existe pas de mécanisme pour gérer ce cas lors de l'analyse de trace, ce qui crée des incohérences dans les résultats sans que l'utilisateur en soit notifié. L'objectif de cette recherche est donc d'étudier le problème des événements perdus dans une trace lors de son analyse, et d'apporter des solutions permettant d'indiquer les incohérences et d'y remédier. Notre hypothèse était que les événements présents dans la trace contiennent suffisament d'information pour pouvoir détecter un changement d'état qui n'aurait pas dû avoir lieu, et pour compléter la chronologie manquante. Pour cela, nous avons utilisé des machines à états finis, puisque ce formalisme de représentation permet de modéliser le système étudié, en définissant la façon dont les événements génèrent des changements d'états. Ces machines à états possèdent des propriétés qui peuvent être exploitées pour retrouver les informations perdues.
Department: Department of Computer Engineering and Software Engineering
Program: Génie informatique
Academic/Research Directors: Michel Dagenais
PolyPublie URL: https://publications.polymtl.ca/3248/
Institution: École Polytechnique de Montréal
Date Deposited: 17 Oct 2018 15:34
Last Modified: 09 Nov 2022 22:41
Cite in APA 7: Martin, M. (2018). Analyse détaillée de trace en dépit d'événements manquants [Master's thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/3248/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item