Verification by abstract interpretation under weakly consistent memory

Vérification par interprétation abstraite en mémoire faiblement cohérente

Thibault Suzanne (1, 2)

1 DI-ENS - Département d'informatique - ENS Paris
2 ANTIQUE - Analyse Statique par Interprétation Abstraite

Static analysis aims to certify critical software by establishing the absence of errors amongst every possible execution of a given program. Abstract interpretation provides a general theoretical framework to build such analysis that are soundby- design : they take every possible behaviour of the target into account. In this thesis, we address the verification of concurrent programs that run in weakly consistent memory models. In addition to sequentially consistent executions that match the interleavings of the threads, these models allow counter-intuitive behaviours that further complicate human reasoning. We propose dedicated abstract domains to analyse the programs that run under such models. Supported by experimental results, we show how these domains, by means of adapted iteration methods, allow precisely verifying the correction of typical concurrent programming algorithms. To improve the scaling, we extend this work to the design of a thread-modular analysis. We show by experimentations how, by leveraging specific abstractions and an optimised iteration strategy, this method allows efficiently analysing programs that involve a greater number of threads. We eventually define abstract domains allowing to precisely infer relations that are specific to the memory model, in order to certify programs entailing complex invariants.

Parmi les méthodes de certification de logiciels critiques, l'analyse statique vise à établir l'absence d'erreurs dans toutes les exécutions possibles d'un programme donné. L'interprétation abstraite fournit un cadre théorique général permettant de concevoir de telles analyses sûres par construction : elles n'oublient aucun comportement de la cible. Nous nous intéressons dans cette thèse à la vérification de programmes concurrents s'exécutant dans des modèles mémoire dits faiblement cohérents. En plus des exécutions séquentiellement cohérentes générées par les entrelacements des processus, ces modèles autorisent des comportements contre-intuitifs rendant le raisonnement d'autant plus difficile. Nous proposons des domaines abstraits dédiés pour analyser les programmes s'exécutant dans de tels domaines. Résultats expérimentaux à l'appui, nous montrons comment ces domaines permettent, à l'aide de méthodes de calcul adaptées, de vérifier avec précision la correction d'algorithmes classiques de programmation concurrente. Pour permettre un meilleur passage à l'échelle, nous étendons ces travaux à la conception d'une analyse modulaire. Nous montrons par l'expérience comment, en tirant profit d'abstractions spécifiques et d'une stratégie d'itération optimisée, cette méthode permet d'analyser efficacement des programmes comportant un plus grand nombre de processus. Nous définissons finalement des domaines permettant d'inférer avec précision des relations spécifiques au modèle mémoire afin de pouvoir certifier des programmes aux invariants complexes.

Mots clés: Abstract interpretation; Thread-modular static analysis; Weakly consistent memory; Concurrent program

Mots clés: Interprétation abstraite; Analyse statique modulaire; Mémoire faiblement cohérente; Programmes concurrents

Domaines: Cryptographie et sécurité [cs.CR]

Thibault Suzanne. Vérification par interprétation abstraite en mémoire faiblement cohérente. Cryptographie et sécurité [cs.CR]. Université Paris sciences et lettres, 2019. Français. ⟨NNT : 2019PSLEE013⟩. ⟨tel-02503839⟩