Détection à faible surcoût des conditions de course et des violations de la sûreté de la mémoire de tas

Parmi les outils existants de détection des conditions de course et des violations de la sûreté spatiale et temporelle de la mémoire de tas, les techniques de vérification dynamique se distinguent par leur précision et leur meilleure capacité de passage à l’échelle par rapport aux approches statiques. Toutefois, malgré ces atouts, les outils dynamiques les plus perfectionnés restent difficilement utilisables dans de nombreux contextes de test réels, en raison de leur forte consommation en mémoire et en ressources de calcul. Cette limitation freine leur adoption dans des environnements contraints en ressources, tels que les systèmes embarqués, et complique les tests effectués sous des charges réalistes. En outre, même les détecteurs les plus répandus présentent souvent des lacunes de détection, ce qui met en lumière la nécessité de développer de nouvelles approches capables d’élargir leur couverture sans alourdir le coût en temps d’exécution ou en mémoire. En conséquence, cette thèse poursuit deux objectifs principaux : concevoir de nouveaux détecteurs dynamiques à faible surcoût pour les conditions de course et les violations de la sûreté de la mémoire de tas, et améliorer la couverture d’un détecteur existant sans accroître le surcoût en temps d’exécution ou en mémoire. Ces objectifs visent à surmonter les principales limites des approches actuelles et ont guidé les trois axes de recherche développés au cours de cette thèse. Le premier axe de recherche a examiné dans quelle mesure les avancées matérielles récentes en matière de traçage d’exécution pouvaient être exploitées pour concevoir un détecteur de conditions de course (data races) à faible surcoût, adapté aux environnements à ressources limitées, tels que les systèmes embarqués, tout en conservant les capacités de détection offertes par les outils existants à fort surcoût. Dans cette optique, nous avons conçu et mis en oeuvre ThreadMonitor (TMon), un détecteur post-mortem de conditions de course destiné aux programmes C et C++ multithreadés utilisant la bibliothèque Pthread. TMon a été spécifiquement développé pour offrir une couverture de détection équivalente à celle de ThreadSanitizer (TSan), tout en réduisant considérablement le surcoût d’exécution. Pour cela, TMon repose sur deux phases principales : une phase de traçage légère et une phase d’analyse post-mortem. Durant la phase de traçage, TMon utilise les paquets ptwrite d’Intel, une fonctionnalité de traçage matériel récemment répandue dans Intel Processor Trace (Intel PT), afin de tracer les mêmes événements que ceux suivis par TSan, avec un très faible impact sur les performances. Grâce à ces paquets, TMon enregistre pour chaque événement exactement les mêmes informations d’exécution que celles collectées par TSan à des vi fins d’analyse. Par la suite, l’analyseur post-mortem de TMon reconstruit la séquence des événements à partir des traces afin de déterminer si l’exécution observée présente des conditions de course. TMon n’induit aucun surcoût direct sur la mémoire de données, introduit un surcoût minimal sur la mémoire d’instructions, et engendre un ralentissement très limité. Nos évaluations expérimentales montrent qu’en moyenne, TMon entraîne un surcoût d’exécution 2 à 6 fois inférieur à celui de TSan, y compris en prenant en compte le coût d’écriture des traces sur disque. Le deuxième axe de recherche a visé à évaluer s’il était possible de réaliser une détection exhaustive des violations temporelles et spatiales d’accès à la mémoire de tas dans les programmes C en combinant la propagation dynamique de métadonnées associées aux pointeurs avec une analyse effectuée à la compilation, tout en limitant le surcoût induit. Dans ce cadre, nous avons développé AddressMonitor (AMon), un outil de vérification à l’exécution qui associe le marquage des pointeurs à une analyse statique et à des transformations réalisées lors de la compilation. Plus précisément, AMon permet de détecter les accès hors limites (outof- bound accesses), les utilisations après libération (use-after-frees), les doubles libérations (double-frees) ainsi que les fuites de mémoire (memory leaks). Il identifie également deux pratiques de programmation à risque liées à la gestion mémoire : le passage d’un pointeur non-base aux fonctions standard de réallocation ou de libération, ainsi que les utilisations potentielles après libération survenant à la suite d’une réallocation. À la compilation, AMon identifie les opérandes pointeurs alloués sur le tas, génère des variantes non marquées, et remplace les pointeurs d’origine en conséquence. À l’exécution, il attribue une valeur de marquage unique à chaque objet alloué, insère cette valeur dans le pointeur, et maintient une table des objets permettant de suivre les informations spatiales, temporelles et de débogage pendant toute l’exécution du programme. Nos évaluations expérimentales montrent qu’AMon présente un meilleur compromis entre surcoût en temps d’exécution et surcoût mémoire que les outils de pointe existants. Son efficacité et sa pertinence pratique ont été confirmées par son intégration réussie dans un système informatique embarqué propriétaire déployé par notre partenaire industriel Ericsson. Le troisième axe de recherche a étudié comment les compromis d’implémentation visant à réduire le surcoût dans les détecteurs dynamiques de conditions de course peuvent engendrer des angles morts de détection non documentés, et si de telles limitations peuvent être atténuées sans augmenter le temps d’exécution ni la consommation mémoire. Nous nous sommes penchés sur TSan, un détecteur de conditions de course de pointe intégré aux chaînes de compilation Clang et GCC. Nous avons analysé son sous-système de mémoire d’ombre — responsable de l’enregistrement et de la vérification de l’historique des accès mémoire — et vii mis en évidence deux angles morts jusqu’alors non documentés : le premier dû à l’éviction aléatoire lors du remplacement des entrées en mémoire d’ombre, le second lié au caractère non atomique de la vérification des courses et de la mise à jour des valeurs d’ombre. Nous avons formalisé les conditions dans lesquelles ces angles morts se manifestent, et proposé des stratégies d’atténuation qui permettent d’améliorer la couverture de détection sans modifier le surcoût initial de l’outil.

Abstract

Compared to static approaches, dynamic verification techniques offer superior detection accuracy and scalability for identifying data races and heap-related memory safety violations. However, despite these advantages, state-of-the-art dynamic tools often introduce significant runtime and memory overhead, which limits their practicality in real-world testing scenarios— particularly in resource-constrained environments such as embedded systems, or when evaluating software under realistic workloads. Furthermore, even widely adopted detectors exhibit detection blind spots resulting from implementation-level compromises, highlighting the need for novel mitigation strategies that broaden detection coverage without increasing overhead. This thesis addresses these challenges through two primary objectives: the design of novel lowoverhead dynamic detectors for data races and heap-related memory safety violations, and the enhancement of detection coverage in an existing dynamic tool without introducing additional performance cost. These objectives directly target key limitations in current approaches and form the basis of the three research tracks pursued in this work. The first research track examined whether recent hardware support for execution tracing could be leveraged to design a low-overhead data race detector suitable for resourceconstrained environments, while preserving the detection coverage of existing high-overhead tools. To this end, we developed ThreadMonitor (TMon), a postmortem data race detector for multithreaded C and C++ programs using the Pthread library. TMon is specifically designed to match the detection capabilities of ThreadSanitizer (TSan)—a state-of-the-art race detector integrated into both the Clang and GCC toolchains—while significantly reducing the runtime overhead. It features two main phases: a lightweight tracing phase and a postmortem analysis phase. During tracing, TMon utilizes the low-overhead ptwrite packet, a hardware-assisted tracing feature provided by Intel Processor Trace, to record the same program events monitored by TSan. This mechanism captures, with minimal overhead, the essential runtime information required for race detection. The postmortem analyzer then reconstructs the execution trace to determine whether any data races occurred. TMon incurs no direct data memory overhead, introduces only minimal instruction memory overhead, and causes a negligible performance impact. Experimental results show that TMon imposes 2× to 6× less execution time overhead than TSan, including the cost of trace generation. The second research track investigated whether comprehensive detection of temporal and spatial heap access violations in C programs could be achieved by combining dynamic metaix data propagation with compile-time analysis, without incurring high runtime overhead. To address this, we designed and implemented AddressMonitor (AMon), a runtime verification tool that integrates pointer tainting with compile-time analysis and code transformations. Specifically, AMon detects out-of-bound accesses, use-after-frees, double-frees, and memory leaks. Additionally, it is able to identify two other unsafe programming practices related to heap access: passing a non-base pointer to standard memory reallocation or deallocation functions, and potential use-after-free conditions arising from memory reallocation. At compile-time, AMon identifies heap pointer operands, generates their untainted counterparts, and replaces the original pointers with these variants. At runtime, it assigns a unique taint value to each allocated object, embeds it into the pointer, and maintains an object table to track spatial, temporal, and debugging information throughout execution. Our evaluation studies demonstrate that AMon offers a more favorable trade-off between runtime and memory overhead than existing state-of-the-art tools. The practicality of AMon has been demonstrated through its successful integration into a proprietary embedded computing system deployed by our industry partners at Ericsson. The third research track explored how implementation-level tradeoffs in dynamic data race detectors—introduced to reduce runtime and memory overhead—can lead to undocumented detection blind spots, and whether such limitations can be addressed without compromising performance. Focusing on TSan, we analyzed its shadow memory subsystem responsible for recording and validating memory access histories. We identified two previously undocumented detection blind spots in this tool: one resulting from random eviction in the shadow slot replacement policy, and the other from the non-atomicity of race checking and shadow value updates. We formally characterized the conditions under which these detection blind spots arise and proposed mitigation strategies that improve detection coverage without affecting the initial overhead of the tool. In conclusion, this thesis makes an important contribution in achieving low-overhead, highcoverage dynamic identification of data races and memory safety violations, advancing stateof- the-art tools. The industry adoption of the research outcomes further proves the practical significance of the contributions of this thesis.