Static analysis of least recently used caches : complexity, optimal analysis, and applications to worst-case execution time and security

Analyse statique de caches LRU : complexité, analyse optimale, et applications au calcul de pire temps d'exécution et à la sécurité Dans le cadre des systèmes critiques, la certification de programmes temps-réel nécessite de borner leur temps d'exécution.Les mémoires caches impactant fortement la latence des accès mémoires, les outils de calcul de pire temps d'exécution incluent des analyses de cache.Ces analyses visent à prédire statiquement si ces accès aboutissent à des cache-hits ou des cache-miss.Ce problème étant indécidable en général, les analyses de caches emploient des abstractions pouvant mener à des pertes de précision.Une hypothèse habituelle pour rendre le problème décidable consiste à supposer que toutes les exécutions du programme sont réalisables.Cette hypothèse est raisonnable car elle ne met pas en cause la validité de l'analyse: tous les véritables chemins d'exécutions du programme sont couverts par l'analyse.Néanmoins, la classification des accès mémoires reste difficile en pratique malgré cette hypothèse, et les analyses de cache efficaces utilisent des approximations supplémentaires.Cette thèse s'intéresse à la possibilité de réaliser des analyses de cache de précision optimale sous l'hypothèse que tous les chemins sont faisables.Les problèmes de classification d'accès mémoires en hits et miss y sont définis formellement et nous prouvons qu'ils sont NP-difficiles, voire PSPACE-difficiles, pour les politiques de remplacement usuelles (LRU, FIFO, NMRU et PLRU).Toutefois, si ces résultats théoriques justifient l'utilisation d'abstractions supplémentaires, ils n'excluent pas l'existence d'un algorithme efficace en pratique pour des instances courantes dans l'industrie.Les abstractions usuelles ne permettent pas, en général, de classifier tous les accès mémoires en Always-Hit et Always-Miss.Certains sont alors classifiés Unknown par l'analyse de cache, et peuvent aboutir à des cache-hits comme à des cache-miss selon le chemin d'exécution emprunté.Cependant, il est aussi possible qu'un accès soit classifié comme Unknown alors qu'il mène toujours à un hit (ou un miss), à cause d'une approximation trop grossière.Nous proposons donc une nouvelle analyse de cache d'instructions LRU, capable de classifier certains accès comme Definitely Unknown, une nouvelle catégorie représentant les accès pouvant mener à un hit ou à un miss.On est alors certain que la classification de ces accès est due au programme et à la configuration du cache, et pas à une approximation peu précise.Par ailleurs, cette analyse réduit le nombre d'accès candidats à une reclassification par des analyses plus précises mais plus coûteuses.Notre principale contribution est une analyse capable de produire une classification de précision optimale.Celle-ci repose sur une méthode appelée block focusing qui permet le passage à l'échelle en analysant les blocs de cache un par un.Nous profitons ainsi de l'analyse de l'analyse Definitely Unknown, qui réduit le nombre de candidats à une classification plus précise.Cette analyse précise produit alors une classification optimale pour un coût raisonnable (proche du coût des analyses usuelles May et Must).Nous étudions également l'impact de notre analyse exacte sur l'analyse de pipeline.En effet, lorsqu'une analyse de cache ne parvient pas à classifier un accès comme Always-Hit ou Always-Miss, les deux cas (hit et miss) sont envisagés par l'analyse de pipeline.En fournissant une classification plus précise des accès mémoires, nous réduisons donc la taille de l'espace d'états de pipeline exploré, et donc le temps de l'analyse.Par ailleurs, cette thèse étudie la possibilité d'utiliser l'analyse Definitely Unknown dans le domaine de la sécurité.Les mémoires caches peuvent être utilisées comme canaux cachés pour extraire des informations de l'exécution d'un programme.Nous proposons une variante de l'analyse Definitely Unknown visant à localiser la source de certaines fuites d'information.