Detecting Problematic Execution Patterns Through Automatic Kernel Trace Analysis

Les processeurs multicoeurs, les systèmes distribués et la virtualisation deviennent de plus en plus répandus, rendant ainsi le débogage des systèmes en production plus difficile, surtout quand les problèmes rencontrés ne sont pas facilement reproductibles. Cette complexité architecturale a introduit une nouvelle gamme de problèmes potentiels qu'on devrait pouvoir détecter à l'aide de nouvelles méthodologies efficaces et extensibles. En effet, en traçant le noyau d'un système d'exploitation, on est capable d'identifier les goulots d'étranglement, les failles de sécurité, les bogues de programmation ainsi que d'autres genres de comportements indésirables. Le traçage consiste à collecter les événements pertinents se produisant sur un système en production, tout en ayant un impact minimal sur la performance ainsi que sur le flot normal d'exécution. La trace générée est typiquement inspectée en différé, n'introduisant aucun impact sur le système tracé. Ce travail présente une nouvelle approche basée sur les automates pour la modélisation de patrons de comportements problématiques sous forme d'une ou plusieurs machines à états finis exécutables. Ces patrons sont ensuite introduits dans un analyseur qui vérifie leur existence simultanément et efficacement dans des traces de plusieurs giga-octets. L'analyseur fournit une interface de programmation offrant des services essentiels aux automates. Les patrons implémentés touchent à différents domaines incluant la sécurité, le test de logiciels et l'analyse de performance. Les résultats de l'analyse fournissent suffisamment d'information pour identifier précisément la source du problème ce qui nous a permis d'identifier une séquence de code dans le noyau Linux pouvant générer un inter-blocage. La performance de l'analyseur est linéaire par rapport à la taille de la trace. Les autres facteurs affectant sa performance sont discutés. En outre, la comparaison entre la performance de l'analyseur par rapport à celle d'une approche dédiée, suggère que le surcoût de l'utilisation des machines à états pour l'exécution et non seulement pour la modélisavi tion, est acceptable surtout lors d'une analyse différée. La solution implémentée est facilement parallélisable et pourrait bien s'appliquer à des analyses en-ligne. Le mémoire se conclut par une liste de suggestions d'optimisations possibles pouvant encore améliorer la performance de l'analyseur.

Abstract

As multi-core processors, distributed systems and virtualization are gaining a larger share in the market, debugging production systems has become a more challenging task, especially when the occurring problems are not easily reproducible. The new architectural complexity introduced a large number of potential problems that need to be detected on live systems with adequate, efficient and scalable methodologies. By tracing the kernel of an operating system, performance bottlnecks, malicious activities, programming bugs and other kinds of problematic behavior could be accurately detected. Tracing consists in monitoring and logging relevant events occurring on live systems with a minimal performance impact and interference with the flow of execution. The generated trace is typically inspected remotely with no overhead on the system whatsoever. This work presents an automata-based approach for modeling patterns of undesired behavior using executable Finite State Machines. They are fed into an offline analyzer which efficiently and simultaneously checks for their occurrences even in traces of several gigabytes. The analyzer provides an Application Programming Interface offering essential services to the Finite State Machines. To our knowledge, this is the first attempt that relies on describing problematic patterns for kernel trace analysis. The implemented patterns touch on several fields including security, software testing and performance debugging. The analysis results provide enough information to precisely identify the source of the problem. This was helpful to identify a suspicious code sequence in the Linux kernel that could generate a deadlock. The analyzer achieves a linear performance with respect to the trace size. The remaining factors impacting its performance are also discussed. The performance of the automatabased approach is compared with that of a dedicated implementation suggesting that the overhead of using Finite State Machines for execution and not just for modeling is acceptable especially in post-mortem analysis. The implemented solution is highly parallelizable and may be ported for online pattern viii matching. The thesis concludes by suggesting a list of possible optimizations that would further improve the analyzer's performance.