Test Data Generation for Exposing Interference Bugs in Multi-Threaded Systems

Tester les systèmes multi-thread est difficile en raison du comportement non-déterministe de l'environnement (ordonnanceurs, cache, interruptions) dans lequel ils s'exécutent. Comme ils ne peuvent contrôler l'environnement, les testeurs doivent recourir à des moyens indirects pour augmenter le nombre d'ordonnancements testés. Une autre source de non-déterminisme pour les systèmes multi-thread est l'accès à la mémoire partagée. Lors de leur exécution, les systèmes multi-thread peuvent générer des conditions de courses aux données ou d'interférence dues aux données partagées. La génération de jeux de test en utilisant des techniques basées sur les recherches locales a déjà fourni des solutions aux problèmes des tests de systèmes mono et multi-thread. Mais il n'y a pas encore eu de travaux abordant la question des bugs d'interférence dans les systèmes multi-thread en utilisant les recherches locales. Dans cette thèse, nous étudions la possibilité d'utiliser ces approches afin de maximiser la possibilité d'exposer des bugs d'interférence dans les systèmes multi-thread. Nous formulons notre hypothèse de recherche comme suit : les techniques basées sur les recherches locales peuvent être utilisées efficacement pour générer des jeux de test pour maximiser les conditions d'obtention de bugs d'interférence dans les systèmes multi-thread. Après étude de la littérature, nous avons découvert trois défis majeurs concernant l'utilisation des approches basées sur les recherches locales : C1 : Formuler le problème initial comme un problème de recherche locale, C2 : Développer une fonction de coût adaptée, et C3 : Trouver la meilleure recherche locale (la plus adaptée). Nous procédons d'abord à une étude préliminaire sur la façon dont ces défis peuvent être relevés dans les systèmes mono-thread. Nous pensons que nos résultats pourraient être ensuite applicables aux systèmes multi-thread. Pour notre première étude, nous abordons le problème de la génération des jeux de test pour lever des exceptions de type division par zéro dans un système mono-thread en utilisant des approches basées sur les recherches locales, tout en tenant compte de C1, C2 et C3. Nous constatons que les trois défis sont importants et peuvent être traitées, et que les approches basées sur les recherches locales sont nettement plus efficaces qu'une approche aléatoire lorsque le nombre de paramètres d'entrées croît. Nous traitons ensuite notre principal problème de génération de jeux de test afin de révéler des bugs d'interférence dans les systèmes multi-thread en utilisant des approches basées sur les recherches locales, tout en répondant aux trois mêmes défis. Nous avons constaté que même dans les systèmes multi-thread, il est important de traiter les trois défis et que les approches basées sur les recherches locales surpassent une approche aléatoire lorsque le nombre de paramètres d'entrée devient grand. Nous validons ainsi notre thèse. Cependant, d'autres études sont nécessaires afin de généraliser nos résultats.

Abstract

Testing multi-threaded systems is difficult due to the non-deterministic behaviour of the environment (schedulers, cache, interrupts) in which the multi-threaded system runs. As one cannot control the environment, testers must resort to indirect means to increase the number of schedules tested. Another source of non-determinism in multi-threaded systems is the shared memory access. When executed, multi-threaded systems can experience one of many possible interleavings of memory accesses to shared data, resulting in data race or interference conditions being raised. Test data generation using search-based techniques has provided solutions to the problem of testing single and multi-threaded systems over the years. But to the best of our knowledge, there has been no work addressing the issue of interference bugs in multi-threaded systems using search-based approaches. In this thesis, we perform a feasibility study of using search-based approaches to maximize the possibility of exposing interference bug pattern in multi-threaded systems. We frame our thesis hypothesis as: Search-based techniques can be used effectively to generate test data to expose interference condition in multi-threaded systems. From the related work we found out three major challenges of using search-based approaches: C1: Formulating the original problem as a search problem, C2: Developing the right fitness function for the problem formulation, and C3: Finding the right (scalable) search-based approach using scalability analysis. Before studying multi-threaded systems, we perform a preliminary study on how these challenges can be addressed in single-threaded systems, as we feel that our findings might be applicable to the more complex multi-threaded systems. In our first study, we address the problem of generating test data for raising divide-by-zero exception in single-threaded systems using search-based approaches, while addressing C1, C2, and C3. We find that the three challenges are important and can be addressed. Further, we found that search-based approaches scale significantly better than random when the input search space grows from very small to huge. Based on the knowledge obtained from the study, we address our main problem of generating test data to expose interference bugs in multi-threaded systems using search-based approaches, while addressing the same challenges C1, C2, and C3. We found that even in multi-threaded systems, it is important to address the three challenges and that search-based approaches outperforms random when the input search-space becomes large. Thus we confirm our thesis. However, further studies are necessary to generalize.