{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T02:06:10Z","timestamp":1776305170213,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T00:00:00Z","timestamp":1546387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["PEP: Precise and Efficient Prediction of Good Worst-case Performance for Contemporary and Future Architectures"],"award-info":[{"award-number":["PEP: Precise and Efficient Prediction of Good Worst-case Performance for Contemporary and Future Architectures"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["306595"],"award-info":[{"award-number":["306595"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,1,2]]},"abstract":"<jats:p>For applications in worst-case execution time analysis and in security, it is desirable to statically classify memory accesses into those that result in cache hits, and those that result in cache misses. Among cache replacement policies, the least recently used (LRU) policy has been studied the most and is considered to be the most predictable.<\/jats:p>\n          <jats:p>The state-of-the-art in LRU cache analysis presents a tradeoff between precision and analysis efficiency: The classical approach to analyzing programs running on LRU caches, an abstract interpretation based on a range abstraction, is very fast but can be imprecise. An exact analysis was recently presented, but, as a last resort, it calls a model checker, which is expensive.<\/jats:p>\n          <jats:p>In this paper, we develop an analysis based on abstract interpretation that comes close to the efficiency of the classical approach, while achieving exact classification of all memory accesses as the model-checking approach. Compared with the model-checking approach we observe speedups of several orders of magnitude. As a secondary contribution we show that LRU cache analysis problems are in general NP-complete.<\/jats:p>","DOI":"10.1145\/3290367","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T13:33:51Z","timestamp":1546608831000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Fast and exact analysis for LRU caches"],"prefix":"10.1145","volume":"3","author":[{"given":"Valentin","family":"Touzeau","sequence":"first","affiliation":[{"name":"Grenoble Alps University, France"}]},{"given":"Claire","family":"Ma\u00efza","sequence":"additional","affiliation":[{"name":"Grenoble INP, France"}]},{"given":"David","family":"Monniaux","sequence":"additional","affiliation":[{"name":"CNRS, France"}]},{"given":"Jan","family":"Reineke","sequence":"additional","affiliation":[{"name":"Saarland University, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,1,2]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"00","article-title":"Software Optimization Guide for AMD Family 17h Processors. Advanced Micro Devices. https:\/\/developer.amd.com\/wordpress\/media\/2013\/12\/55723_3_00.ZIP Publication No. 55723","volume":"3","author":"Devices Advanced Micro","year":"2017","unstructured":"Advanced Micro Devices 2017 . Software Optimization Guide for AMD Family 17h Processors. Advanced Micro Devices. https:\/\/developer.amd.com\/wordpress\/media\/2013\/12\/55723_3_00.ZIP Publication No. 55723 , Revision 3 . 00 . Advanced Micro Devices 2017. Software Optimization Guide for AMD Family 17h Processors. Advanced Micro Devices. https:\/\/developer.amd.com\/wordpress\/media\/2013\/12\/55723_3_00.ZIP Publication No. 55723, Revision 3.00.","journal-title":"Revision"},{"key":"e_1_2_2_2_1","volume-title":"SEUS 2010, Waidhofen\/Ybbs, Austria, October 13-15, 2010. Proceedings (Lecture Notes in Computer Science), Sang Lyul Min, Robert G. Pettit IV, Peter P. Puschner, and Theo Ungerer (Eds.)","volume":"6399","author":"Ballabriga Cl\u00e9ment","year":"2010","unstructured":"Cl\u00e9ment Ballabriga , Hugues Cass\u00e9 , Christine Rochange , and Pascal Sainrat . 2010 . OTAWA: An Open Toolbox for Adaptive WCET Analysis. In Software Technologies for Embedded and Ubiquitous Systems - 8th IFIP WG 10.2 International Workshop , SEUS 2010, Waidhofen\/Ybbs, Austria, October 13-15, 2010. Proceedings (Lecture Notes in Computer Science), Sang Lyul Min, Robert G. Pettit IV, Peter P. Puschner, and Theo Ungerer (Eds.) , Vol. 6399 . Springer, 35\u201346. Cl\u00e9ment Ballabriga, Hugues Cass\u00e9, Christine Rochange, and Pascal Sainrat. 2010. OTAWA: An Open Toolbox for Adaptive WCET Analysis. In Software Technologies for Embedded and Ubiquitous Systems - 8th IFIP WG 10.2 International Workshop, SEUS 2010, Waidhofen\/Ybbs, Austria, October 13-15, 2010. Proceedings (Lecture Notes in Computer Science), Sang Lyul Min, Robert G. Pettit IV, Peter P. Puschner, and Theo Ungerer (Eds.), Vol. 6399. Springer, 35\u201346."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158120"},{"key":"e_1_2_2_4_1","unstructured":"Daniel J. Bernstein. 2005. Cache-timing attacks on AES. (2005). https:\/\/cr.yp.to\/antiforgery\/cachetiming- 20050414.pdf  Daniel J. Bernstein. 2005. Cache-timing attacks on AES. (2005). https:\/\/cr.yp.to\/antiforgery\/cachetiming- 20050414.pdf"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2004.09.004"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/782814.782836"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378859"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-013-9178-0"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2016.7461358"},{"key":"e_1_2_2_10_1","unstructured":"Patrick Cousot. 1978. M\u00e9thodes it\u00e9ratives de construction et d\u2019approximation de points fixes d\u2019op\u00e9rateurs monotones sur un treillis analyse s\u00e9mantique de programmes. Th\u00e8se d\u2019\u00e9tat \u00e8s sciences math\u00e9matiques. Universit\u00e9 scientifique et m\u00e9dicale de Grenoble Grenoble France. https:\/\/tel.archives- ouvertes.fr\/tel- 00288657\/en\/  Patrick Cousot. 1978. M\u00e9thodes it\u00e9ratives de construction et d\u2019approximation de points fixes d\u2019op\u00e9rateurs monotones sur un treillis analyse s\u00e9mantique de programmes. Th\u00e8se d\u2019\u00e9tat \u00e8s sciences math\u00e9matiques. Universit\u00e9 scientifique et m\u00e9dicale de Grenoble Grenoble France. https:\/\/tel.archives- ouvertes.fr\/tel- 00288657\/en\/"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062388"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2756550"},{"key":"e_1_2_2_13_1","volume-title":"16th International Workshop on Worst-Case Execution Time Analysis, WCET 2016","author":"Falk Heiko","year":"2016","unstructured":"Heiko Falk , Sebastian Altmeyer , Peter Hellinckx , Bj\u00f6rn Lisper , Wolfgang Puffitsch , Christine Rochange , Martin Schoeberl , Rasmus Bo Sorensen , Peter W\u00e4gemann , and Simon Wegener . 2016 . TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research . In 16th International Workshop on Worst-Case Execution Time Analysis, WCET 2016 , July 5, 2016, Toulouse, France. 2:1\u20132:10. Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Bj\u00f6rn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sorensen, Peter W\u00e4gemann, and Simon Wegener. 2016. TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research. In 16th International Workshop on Worst-Case Execution Time Analysis, WCET 2016, July 5, 2016, Toulouse, France. 2:1\u20132:10."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008186323068"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325479"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03237-0_10"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2010.8"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis, Bj\u00f6rn Lisper (Ed.). Austrian Computer Society, 28\u201339","author":"Grund Daniel","year":"2010","unstructured":"Daniel Grund and Jan Reineke . 2010 b. Toward Precise PLRU Cache Analyis . In Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis, Bj\u00f6rn Lisper (Ed.). Austrian Computer Society, 28\u201339 . http:\/\/rw4.cs. uni- saarland.de\/~grund\/papers\/wcet10- plru.pdf Daniel Grund and Jan Reineke. 2010b. Toward Precise PLRU Cache Analyis. In Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis, Bj\u00f6rn Lisper (Ed.). Austrian Computer Society, 28\u201339. http:\/\/rw4.cs. uni- saarland.de\/~grund\/papers\/wcet10- plru.pdf"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2584655"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2485288.2485362"},{"key":"e_1_2_2_22_1","volume-title":"Worst-Case Execution Time Prediction by Static Program Analysis. The whitepaper of aiT","author":"Heckmann Reinhold","year":"2014","unstructured":"Reinhold Heckmann and Christian Ferdinand . 2014. Worst-Case Execution Time Prediction by Static Program Analysis. The whitepaper of aiT ( 2014 ). http:\/\/www.absint.com\/aiT_{W}{C}{E}{T}.pdf Reinhold Heckmann and Christian Ferdinand. 2014. Worst-Case Execution Time Prediction by Static Program Analysis. The whitepaper of aiT (2014). http:\/\/www.absint.com\/aiT_{W}{C}{E}{T}.pdf"},{"key":"e_1_2_2_23_1","volume-title":"Intel 64 and IA-32 Architectures Optimization Reference Manual","author":"Intel Corporation 2016.","unstructured":"Intel Corporation 2016. Intel 64 and IA-32 Architectures Optimization Reference Manual . Intel Corporation . https:\/\/www. intel.com\/content\/dam\/www\/public\/us\/en\/documents\/manuals\/64- ia- 32- architectures- optimization- manual.pdf Order Number: 248966-033. Intel Corporation 2016. Intel 64 and IA-32 Architectures Optimization Reference Manual. Intel Corporation. https:\/\/www. intel.com\/content\/dam\/www\/public\/us\/en\/documents\/manuals\/64- ia- 32- architectures- optimization- manual.pdf Order Number: 248966-033."},{"key":"e_1_2_2_24_1","unstructured":"Donald E. Knuth. 2011. The Art of Computer Programming: Combinatorial Algorithms part 1. Vol. 4A. Pearson.   Donald E. Knuth. 2011. The Art of Computer Programming: Combinatorial Algorithms part 1. Vol. 4A. Pearson."},{"key":"e_1_2_2_25_1","volume-title":"Spectre Attacks: Exploiting Speculative Execution. CoRR abs\/1801.01203","author":"Kocher Paul","year":"2018","unstructured":"Paul Kocher , Daniel Genkin , Daniel Gruss , Werner Haas , Mike Hamburg , Moritz Lipp , Stefan Mangard , Thomas Prescher , Michael Schwarz , and Yuval Yarom . 2018 . Spectre Attacks: Exploiting Speculative Execution. CoRR abs\/1801.01203 (2018). arXiv: 1801.01203 http:\/\/arxiv.org\/abs\/1801.01203 Paul Kocher, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, Michael Schwarz, and Yuval Yarom. 2018. Spectre Attacks: Exploiting Speculative Execution. CoRR abs\/1801.01203 (2018). arXiv: 1801.01203 http:\/\/arxiv.org\/abs\/1801.01203"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263719"},{"key":"e_1_2_2_27_1","volume-title":"27th USENIX Security Symposium (USENIX Security 18)","author":"Lipp Moritz","year":"2018","unstructured":"Moritz Lipp , Michael Schwarz , Daniel Gruss , Thomas Prescher , Werner Haas , Anders Fogh , Jann Horn , Stefan Mangard , Paul Kocher , Daniel Genkin , Yuval Yarom , and Mike Hamburg . 2018 . Meltdown: Reading Kernel Memory from User Space . In 27th USENIX Security Symposium (USENIX Security 18) . USENIX Association, Baltimore, MD. https:\/\/www. usenix.org\/conference\/usenixsecurity18\/presentation\/lipp Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Anders Fogh, Jann Horn, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. 2018. Meltdown: Reading Kernel Memory from User Space. In 27th USENIX Security Symposium (USENIX Security 18). USENIX Association, Baltimore, MD. https:\/\/www. usenix.org\/conference\/usenixsecurity18\/presentation\/lipp"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.43"},{"key":"e_1_2_2_29_1","volume-title":"Timing Anomalies in Dynamically Scheduled Microprocessors. In 20th IEEE Real-Time Systems Symposium (RTSS).","author":"Lundqvist Thomas","year":"1999","unstructured":"Thomas Lundqvist and Per Stenstr\u00f6m . 1999 . Timing Anomalies in Dynamically Scheduled Microprocessors. In 20th IEEE Real-Time Systems Symposium (RTSS). Thomas Lundqvist and Per Stenstr\u00f6m. 1999. Timing Anomalies in Dynamically Scheduled Microprocessors. In 20th IEEE Real-Time Systems Symposium (RTSS)."},{"key":"e_1_2_2_30_1","first-page":"05","article-title":"A Survey on Static Cache Analysis for Real-Time Systems","volume":"3","author":"Lv Mingsong","year":"2016","unstructured":"Mingsong Lv , Nan Guan , Jan Reineke , Reinhard Wilhelm , and Wang Yi . 2016 . A Survey on Static Cache Analysis for Real-Time Systems . Leibniz Transactions on Embedded Systems 3 , 1 (2016), 05 \u2013 01 \u201305:48. Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi. 2016. A Survey on Static Cache Analysis for Real-Time Systems. Leibniz Transactions on Embedded Systems 3, 1 (2016), 05\u20131\u201305:48.","journal-title":"Leibniz Transactions on Embedded Systems"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100090100038"},{"key":"e_1_2_2_32_1","volume-title":"Applications of Zero-Suppressed Decision Diagrams, Tsutomu Sasao and Jon T","author":"Mishchenko Alan","year":"2001","unstructured":"Alan Mishchenko . 2014. An introduction to zero-suppressed binary decision diagrams . In Applications of Zero-Suppressed Decision Diagrams, Tsutomu Sasao and Jon T . Butler (Eds.). Morgan Claypool . https:\/\/people.eecs.berkeley.edu\/~alanmi\/ publications\/ 2001 \/tech01_zdd_.pdf Alan Mishchenko. 2014. An introduction to zero-suppressed binary decision diagrams. In Applications of Zero-Suppressed Decision Diagrams, Tsutomu Sasao and Jon T. Butler (Eds.). Morgan Claypool. https:\/\/people.eecs.berkeley.edu\/~alanmi\/ publications\/2001\/tech01_zdd_.pdf"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2381913.2381917"},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the 28th Annual Simulation Symposium. 105\u2013114","author":"Mueller Frank","unstructured":"Frank Mueller and David B. Whalley . 1995. Fast Instruction Cache Analysis via Static Cache Simulation . In Proceedings of the 28th Annual Simulation Symposium. 105\u2013114 . Frank Mueller and David B. Whalley. 1995. Fast Instruction Cache Analysis via Static Cache Simulation. In Proceedings of the 28th Annual Simulation Symposium. 105\u2013114."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-007-9032-3"},{"key":"e_1_2_2_36_1","volume-title":"6th International Workshop on Worst-Case Execution Time Analysis (WCET).","author":"Reineke Jan","year":"2006","unstructured":"Jan Reineke , Bj\u00f6rn Wachter , Stephan Thesing , Reinhard Wilhelm , Ilia Polian , Jochen Eisinger , and Bernd Becker . 2006 . A Definition and Classification of Timing Anomalies . In 6th International Workshop on Worst-Case Execution Time Analysis (WCET). Jan Reineke, Bj\u00f6rn Wachter, Stephan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. 2006. A Definition and Classification of Timing Anomalies. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100090100042"},{"key":"e_1_2_2_38_1","volume-title":"Computer-aided verification (CAV) (Lecture Notes in Computer Science)","author":"Touzeau Valentin","unstructured":"Valentin Touzeau , Claire Ma\u00efza , David Monniaux , and Jan Reineke . 2017. Ascertaining Uncertainty for Efficient Exact Cache Analysis . In Computer-aided verification (CAV) (Lecture Notes in Computer Science) , Rupak Majumdar and Viktor Kuncak (Eds.), Vol. 10427 . Springer , 22\u201340. Valentin Touzeau, Claire Ma\u00efza, David Monniaux, and Jan Reineke. 2017. Ascertaining Uncertainty for Efficient Exact Cache Analysis. In Computer-aided verification (CAV) (Lecture Notes in Computer Science), Rupak Majumdar and Viktor Kuncak (Eds.), Vol. 10427. Springer, 22\u201340."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11817963_5"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88387-6_21"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-017-0152-y"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290367","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3290367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:58:04Z","timestamp":1750208284000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,2]]},"references-count":42,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2019,1,2]]}},"alternative-id":["10.1145\/3290367"],"URL":"https:\/\/doi.org\/10.1145\/3290367","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,2]]},"assertion":[{"value":"2019-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}