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é

Open Access

Abstract

The certification of real-time safety critical programs requires bounding their execution time. Due to the high impact of cache memories on memory access latency, modern Worst-Case Execution Time estimation tools include a cache analysis. The aim of this analysis is to statically predict if memory accesses result in a cache hit or a cache miss. This problem is undecidable in general, thus usual cache analyses perform some abstractions that lead to precision loss. One common assumption made to remove the source of undecidability is that all execution paths in the program are feasible. Making this hypothesis is reasonable because the safety of the analysis is preserved when adding spurious paths to the program model. However, classifying memory accesses as cache hits or misses is still hard in practice under this assumption, and efficient cache analysis usually involve additional approximations, again leading to precision loss. This thesis investigates the possibility of performing an optimally precise cache analysis under the common assumption that all execution paths in the program are feasible.We formally define the problems of classifying accesses as hits and misses, and prove that they are NP-hard or PSPACE-hard for common replacement policies (LRU, FIFO, NMRU and PLRU). However, if these theoretical complexity results legitimate the use of additional abstraction, they do not preclude the existence of algorithms efficient in practice on industrial workloads.Because of the abstractions performed for efficiency reasons, cache analyses can usually classify accesses as Unknown in addition to Always-Hit (Must analysis) or Always-Miss (May analysis). Accesses classified as Unknown can lead to both a hit or a miss, depending on the program execution path followed. However, it can also be that they belong to one of the Always-Hit or Always-Miss category and that the cache analysis failed to classify them correctly because of a coarse approximation. We thus designed a new analysis for LRU instruction that is able to soundly classify some accesses into a new category, called Definitely Unknown, that represents accesses that can lead to both a hit or a miss. For those accesses, one knows for sure that their classification does not result from a coarse approximation but is a consequence of the program structure and cache configuration. By doing so, we also reduce the set of accesses that are candidate for a refined classification using more powerful and more costly analyses.Our main contribution is an analysis that can perform an optimally precise analysis of LRU instruction caches. We use a method called block focusing that allows an analysis to scale by only analyzing one cache block at a time. We thus take advantage of the low number of candidates for refinement left by our Definitely Unknown analysis. This analysis produces an optimal classification of memory accesses at a reasonable cost (a few times the cost of the usual May and Must analyses).We evaluate the impact of our precise cache analysis on the pipeline analysis. Indeed, when the cache analysis is not able to classify an access as Always-Hit or Always-Miss, the pipeline analysis must consider both cases. By providing a more precise memory access classification, we thus prune the state space explored by the pipeline analysis and hence the WCET analysis time.Aside from this application of precise cache analysis to WCET estimation, we investigate the possibility of using the Definitely Unknown analysis in the domain of security. Indeed, caches can be used as side-channel to extract some sensitive data from a program execution, and we propose a variation of our Definitely Unknown analysis to help a developer finding the source of some information leakage. ; 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 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.