Review of conflict-based cache side-channel attacks and eviction sets

doi:10.11772/j.issn.1001-9081.2024070933

Journal of Computer Applications ›› 2025, Vol. 45 ›› Issue (7): 2070-2078.DOI: 10.11772/j.issn.1001-9081.2024070933

• The 39th CCF National Conference of Computer Applications (CCF NCCA 2024) • Previous Articles Next Articles

Review of conflict-based cache side-channel attacks and eviction sets

Zihao YAO¹^,², Ziqiang MA¹^,²^,³(), Yang LI¹^,², Lianggen WEI¹^,²

^1.School of Information Engineering，Ningxia University，Yinchuan Ningxia 750021，China
^2.Collaborative Innovation Center for Ningxia Big Data and Artificial Intelligence Co-founded by Ningxia Municipality and Ministry of Education （Ningxia University），Yinchuan Ningxia 750021，China
^3.Ningxia Key Laboratory of Artificial Intelligence and Information Security for Channeling Computing Resources from the East to the West （Ningxia University），Yinchuan Ningxia 750021，China

Received:2024-07-05 Revised:2024-09-05 Accepted:2024-09-25 Online:2025-07-10 Published:2025-07-10
Contact: Ziqiang MA
About author:YAO Zihao， born in 1999， M. S. candidate. His research interests include computer system security， cache side-channel attack， eviction set construction algorithm.
LI Yang， born in 1999， M. S. candidate. His research interests include computer system security， cache side-channel attack and defense， transient attack.
WEI Lianggen， born in 1997， M. S. candidate. His research interests include computer system security， lattice attack， lattice cryptography.
Supported by:
Talent Introduction Project of Ningxia Hui Autonomous Region Key Research and Development Program(2021BEB04047)

基于冲突的缓存侧信道攻击与驱逐集综述

姚梓豪¹^,², 马自强¹^,²^,³(), 李扬¹^,², 魏良根¹^,²

^1.宁夏大学信息工程学院，银川 750021
^2.宁夏大数据与人工智能省部共建协同创新中心（宁夏大学），银川 750021
^3.宁夏“东数西算”人工智能与信息安全重点实验室（宁夏大学），银川 750021

通讯作者: 马自强
作者简介:姚梓豪（1999—），男，安徽阜阳人，硕士研究生，主要研究方向：计算机系统安全、缓存侧信道攻击、驱逐集构造算法
李扬（1999—），男，江西上饶人，硕士研究生，主要研究方向：计算机系统安全、缓存侧信道攻击与防御、瞬态攻击
魏良根（1997—），男，四川成都人，硕士研究生，主要研究方向：计算机系统安全、格攻击、格密码。
基金资助:
宁夏回族自治区重点研发计划引才专项(2021BEB04047)

Abstract

Abstract:

Cache side-channel attacks exploit the shared characteristics of computer caches， and pose serious threats to target cryptographic systems across processors and virtual machines. Among them， conflict-based cache side-channel attacks overcome the limitations imposed of privileged instructions， and can construct a set of virtual addresses that map to the same cache set as the target address， that is the eviction set， so as to cause cache conflicts and ultimately obtain the target’s sensitive data. Constructing eviction set has become a key technique in conflict-based cache side-channel attacks and speculative execution attacks. Therefore， a review of researches on conflict-based cache side-channel attacks and eviction sets was conducted. First， the fundamental principles of conflict-based cache side-channel attacks were discussed. Subsequently，the core mechanisms and evolution of eviction set construction algorithms were discussed. These algorithms were systematically categorized into conflict elimination methods and conflict progressive methods， distinguished by their strategies for candidate address manipulation and eviction set construction. Furthermore， key factors influencing eviction set construction algorithms were summarized. Finally，current challenges and future research directions for conflict-based cache side-channel attacks were discussed.

Key words: system security, cache side-channel attack, eviction set, virtual address, cache replacement policy

摘要：

缓存侧信道攻击是一种利用计算机缓存共享特性的侧信道攻击手段，对跨处理器、跨虚拟机的目标密码系统构成严重威胁。其中基于冲突的缓存侧信道攻击突破了使用特权指令的限制，能构造一组与目标地址映射到同一缓存集的虚拟地址，即驱逐集，从而造成缓存冲突，进而最终获取目标的隐私数据。构造驱逐集已成为基于冲突的缓存侧信道攻击和推测执行攻击的关键技术之一。因此，对基于冲突的缓存侧信道攻击与驱逐集的研究进行综述。首先，剖析了基于冲突的缓存侧信道攻击的基本原理；其次，分析了驱逐集构造算法的基本原理、发展现状，根据候选地址的操作策略和驱逐集的构造策略不同，将算法分为冲突移除法和冲突渐增法两类；再次，对驱逐集构造算法的影响因素进行了归纳；最后，讨论了基于冲突的缓存侧信道攻击的现状及未来的研究方向。

关键词: 系统安全, 缓存侧信道攻击, 驱逐集, 虚拟地址, 缓存替换策略

CLC Number:

TP309.01

Zihao YAO, Ziqiang MA, Yang LI, Lianggen WEI. Review of conflict-based cache side-channel attacks and eviction sets[J]. Journal of Computer Applications, 2025, 45(7): 2070-2078.

姚梓豪, 马自强, 李扬, 魏良根. 基于冲突的缓存侧信道攻击与驱逐集综述[J]. 《计算机应用》唯一官方网站, 2025, 45(7): 2070-2078.

Figures/Tables 10

Fig. 1 Eviction set mapping to target cache set

Fig. 2 Flow of probing timing class attack

Fig. 3 Attack flow targeting directories

Fig. 4 Prime+Retouch attack using Tree-PLRU

Fig. 5 Flow of Prime+Abort attack

Fig. 6 Comparison of various attack operations

Fig. 7 Flow of conflict removal algorithm

Fig. 8 Flow of conflict-based incremental algorithm

Fig. 9 Flow of pruning-based incremental algorithm

Tab. 1 Comparison of various eviction set construction algorithms

类别		算法	平均情况下每轮候选地址集的操作	$k$ 轮后候选地址数	冲突判定方式	驱逐集构造方式	时间复杂度	缓存访问次数
冲突移除法		SHA	移除一条地址	$N - k$	目标地址从LLC逐出	自顶向下	$O (k 2)$	$N 2$
		GEA	移除 $N W + 1$ 条地址	$N - k N W + 1$	目标地址从LLC逐出	自顶向下	$O (k)$	$(W 2 + W) N$
		PlumTree算法	移除候选集中一半地址	$N - ∑ i = 0 k N 2 i$	候选地址从LLC逐出	自顶向下	$O (S W l o g S)$	$(S W l o g S)$ / $(S W 2 l o g S)$
冲突渐增法	修剪渐增法	PPP算法	修剪 $r i$ 条地址	$N - ∑ i = 0 k (r i)$	候选地址从LLC逐出	自底向上	$O (1)$	$(S W)$ / $(S W 2)$
	修剪渐增法	折半搜索算法	修剪 $N 2 i$ 条地址	$N - ∑ i = 0 k N 2 i$	目标地址从LLC逐出	自底向上	$O (W l o g N)$	$W N l o g N$
	顺序渐增法	联合冲突算法	增选一条候选地址	$k$	目标地址从LLC逐出	自底向上	$O (1)$	$(D - 1) D C + (W - D + 1) C$
		写冲突算法	增选一条候选地址	$k$	两次写操作间的时间较长	自底向上	$O (1)$	$S W$
		CTPP	增选一条候选地址	$k$	目标地址从LLC逐出	自底向上	$O (1)$	$S W 2$

Tab. 1 Comparison of various eviction set construction algorithms

类别		算法	平均情况下每轮候选地址集的操作	$k$ 轮后候选地址数	冲突判定方式	驱逐集构造方式	时间复杂度	缓存访问次数
冲突移除法		SHA	移除一条地址	$N - k$	目标地址从LLC逐出	自顶向下	$O (k 2)$	$N 2$
		GEA	移除 $N W + 1$ 条地址	$N - k N W + 1$	目标地址从LLC逐出	自顶向下	$O (k)$	$(W 2 + W) N$
		PlumTree算法	移除候选集中一半地址	$N - ∑ i = 0 k N 2 i$	候选地址从LLC逐出	自顶向下	$O (S W l o g S)$	$(S W l o g S)$ / $(S W 2 l o g S)$
冲突渐增法	修剪渐增法	PPP算法	修剪 $r i$ 条地址	$N - ∑ i = 0 k (r i)$	候选地址从LLC逐出	自底向上	$O (1)$	$(S W)$ / $(S W 2)$
	修剪渐增法	折半搜索算法	修剪 $N 2 i$ 条地址	$N - ∑ i = 0 k N 2 i$	目标地址从LLC逐出	自底向上	$O (W l o g N)$	$W N l o g N$
	顺序渐增法	联合冲突算法	增选一条候选地址	$k$	目标地址从LLC逐出	自底向上	$O (1)$	$(D - 1) D C + (W - D + 1) C$
		写冲突算法	增选一条候选地址	$k$	两次写操作间的时间较长	自底向上	$O (1)$	$S W$
		CTPP	增选一条候选地址	$k$	目标地址从LLC逐出	自底向上	$O (1)$	$S W 2$

References 47

[1]	葛景全，屠晨阳，高能.侧信道分析技术概览与实例［J］.信息安全研究，2019， 5（1）： 75-87.
	GE J Q， TU C Y， GAO N. Technology overview of side channel analysis ［J］. Journal of Information Security Research， 2019， 5（1）： 75-87.
[2]	KOCHER P， HORN J， FOGH A， et al. Spectre attacks： exploiting speculative execution ［J］. Communications of the ACM， 2020， 63（7）： 93-101.
[3]	LIPP M， SCHWARZ M， GRUSS D， et al. Meltdown： reading kernel memory from user space ［C］// Proceedings of the 27th USENIX Security Symposium. Berkeley： USENIX Association， 2018： 973-990.
[4]	SCHWARZ M， LIPP M， MOGHIMI D， et al. ZombieLoad： cross-privilege-boundary data sampling ［C］// Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2019： 753-768.
[5]	LOU X， ZHANG T， JIANG J， et al. A survey of microarchitectural side-channel vulnerabilities， attacks， and defenses in cryptography ［J］. ACM Computing Surveys， 2022， 54（6）： No.122.
[6]	王永娟，樊昊鹏，代政一，等.侧信道攻击与防御技术研究进展［J］.计算机学报，2023， 46（1）： 202-228.
	WANG Y J， FAN H P， DAI Z Y， et al. Advances in side channel attacks and countermeasures ［J］. Chinese Journal of Computers， 2023， 46（1）： 202-228.
[7]	KIM S， HAN M， BAEK W. DPrime+DAbort： a high-precision and timer-free directory-based side-channel attack in non-inclusive cache hierarchies using Intel TSX ［C］// Proceedings of the 2022 IEEE International Symposium on High-Performance Computer Architecture. Piscataway： IEEE， 2022： 67-81.
[8]	Corporation Intel. Intel Transactional Synchronization Extensions （Intel TSX） asynchronous abort ［EB/OL］. ［2024-04-10］. .
[9]	SCHWARZ M， WEISER S， GRUSS D， et al. Malware guard extension： using SGX to conceal cache attacks ［C］// Proceedings of the 2017 International Conference on Detection of Intrusions and Malware， and Vulnerability Assessment， LNCS 10327. Cham： Springer， 2017： 3-24.
[10]	LIPP M， GRUSS D， SPREITZER R， et al. ARMageddon： cache attacks on mobile devices ［C］// Proceedings of the 25th USENIX Security Symposium. Berkeley： USENIX Association， 2016： 549-564.
[11]	GE Q， YAROM Y， COCK D， et al. A survey of microarchitectural timing attacks and countermeasures on contemporary hardware ［J］. Journal of Cryptographic Engineering， 2018， 8： 1-27.
[12]	李真真，宋威.冲突型缓存侧信道攻击的构建驱逐集研究综述［J］.网络安全与数据治理，2024， 43（1）： 3-9.
	LI Z Z， SONG W. Survey on constructing eviction sets for conflict-type cache side channel attacks ［J］. Cyber Security and Data Governance， 2024， 43（1）： 3-9.
[13]	OSVIK D A， SHAMIR A， TROMER E. Cache attacks and countermeasures： the case of AES ［C］// Proceedings of the 2005 Cryptographers’ Track at the RSAC Conference， LNCS 3860. Berlin： Springer， 2006： 1-20.
[14]	LIU F， YAROM Y， GE Q， et al. Last-level cache side-channel attacks are practical ［C］// Proceedings of the 2015 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2015： 605-622.
[15]	KAYAALP M， ABU-GHAZALEH N， PONOMAREV D， et al. A high-resolution side-channel attack on last-level cache ［C］// Proceedings of the 53rd ACM/EDAC/IEEE Design Automation Conference. New York： ACM， 2016： 1-6.
[16]	YAN M， SPRABERY R， GOPIREDDY B， et al. Attack directories， not caches： side channel attacks in a non-inclusive world ［C］// Proceedings of the 2019 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2019： 888-904.
[17]	PURNAL A， TURAN F， VERBAUWHEDE I. Prime+Scope： overcoming the observer effect for high-precision cache contention attacks ［C］// Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2021： 2906-2920.
[18]	KATZMAN D， KOSASIH W， CHUENGSATIANSUP C， et al. The gates of time： improving cache attacks with transient execution ［C］// Proceedings of the 32nd USENIX Security Symposium. Berkeley： USENIX Association， 2023： 1955-1972.
[19]	LEE J， SANG F， KIM T. Prime+Retouch： when cache is locked and leaked ［EB/OL］. ［2024-04-12］. .
[20]	DISSELKOEN C， KOHLBRENNER D， PORTER L， et al. Prime+ abort： a timer-free high-precision L3 cache attack using Intel TSX ［C］// Proceedings of the 26th USENIX Security Symposium. Berkeley： USENIX Association， 2017： 51-67.
[21]	KOHLBRENNER D， SHACHAM H. Trusted browsers for uncertain times ［C］// Proceedings of the 25th USENIX Security Symposium. Berkeley： USENIX Association， 2016： 463-480.
[22]	MARTIN R， DEMME J， SETHUMADHAVAN S. TimeWarp： rethinking timekeeping and performance monitoring mechanisms to mitigate side-channel attacks ［C］// Proceedings of the 39th Annual International Symposium on Computer Architecture. Piscataway： IEEE， 2012： 118-129.
[23]	VATTIKONDA B C， DAS S， SHACHAM H. Eliminating fine grained timers in Xen ［C］// Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop. New York： ACM， 2011： 41-46.
[24]	HU W M. Reducing timing channels with fuzzy time ［J］. Journal of Computer Security， 1992， 1（3/4）： 233-254.
[25]	CHEN B， WANG Y， SHOME P， et al. GoFetch： breaking constant-time cryptographic implementations using data memory-dependent prefetchers ［C］// Proceedings of the 33rd USENIX Security Symposium. Berkeley： USENIX Association， 2024： 1117-1134.
[26]	QURESHI M K. New attacks and defense for encrypted-address cache ［C］// Proceedings of the ACM/IEEE 46th International Symposium on Computer Architecture. New York： ACM， 2019： 360-371.
[27]	VILA P， KÖPF B， MORALES J F. Theory and practice of finding eviction sets ［C］// Proceedings of the 2019 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2019： 39-54.
[28]	SONG W， LIU P. Dynamically finding minimal eviction sets can be quicker than you think for side-channel attacks against the LLC ［C］// Proceedings of the 22nd International Symposium on Research in Attacks， Intrusions and Defenses. Berkeley： USENIX Association， 2019： 427-442.
[29]	KESSOUS T， GILBOA N. Prune+PlumTree — finding eviction sets at scale ［C］// Proceedings of the 2024 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2024： 3754-3772.
[30]	PURNAL A， VERBAUWHEDE I. Advanced profiling for probabilistic Prime+Probe attacks and covert channels in ScatterCache ［EB/OL］. ［2024-04-12］. .
[31]	PURNAL A， GINER L， GRUSS D， et al. Systematic analysis of randomization-based protected cache architectures ［C］// Proceedings of the 2021 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2021： 987-1002.
[32]	ZHAO Z N， MORRISON A， FLETCHER C W， et al. Last-level cache side-channel attacks are feasible in the modern public cloud ［C］// Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems， Volume 2. New York： ACM， 2024： 582-600.
[33]	PRUNAL A， TURAN F， VERBAUWHEDE I. Double trouble： combined heterogeneous attacks on non-inclusive cache hierarchies ［C］// Proceedings of the 31st USENIX Security Symposium. Berkeley： USENIX Association， 2022： 3647-3664.
[34]	THOMA J P， GÜNEYSU T. Write me and I’ll tell you secrets — write-after-write effects on Intel CPUs ［C］// Proceedings of the 25th International Symposium on Research in Attacks， Intrusions and Defenses. New York： ACM， 2022： 72-85.
[35]	XUE Z， HAN J， SONG W. CTPP： a fast and stealth algorithm for searching eviction sets on Intel processors ［C］// Proceedings of the 26th International Symposium on Research in Attacks， Intrusions and Defenses. New York： ACM， 2023： 151-163.
[36]	LI Z， XUE Z， SONG W. Feasibility analysis and performance optimization of the conflict test algorithms for searching eviction sets ［C］// Proceedings of the 2023 International Conference on Information Security and Cryptology， LNCS 14562. Singapore： Springer， 2023： 214-232.
[37]	JALEEL A， THEOBALD K B， STEELY S C Jr，， et al. High-performance cache replacement using Re-Reference Interval Prediction （RRIP）［C］// Proceedings of the 37th Annual International Symposium on Computer Architecture. New York： ACM， 2010： 60-71.
[38]	WONG H. Intel Ivy Bridge cache replacement policy ［EB/OL］. ［2024-04-12］. .
[39]	GENKIN D， PACHMANOV L， TROMER E， et al. Drive-by key-extraction cache attacks from portable code ［C］// Proceedings of the 2018 International Conference on Applied Cryptography and Network Security， LNCS 10892. Cham： Springer， 2018： 83-102.
[40]	WERNER M， UNTERLUGGAUER T， GINER L， et al. ScatterCache： thwarting cache attacks via cache set randomization ［C］// Proceedings of the 28th USENIX Security Symposium. Berkeley： USENIX Association， 2019： 675-692.
[41]	GRUSS D， LETTNER J， SCHUSTER F， et al. Strong and efficient cache side-channel protection using hardware transactional memory ［C］// Proceedings of the 26th USENIX Security Symposium. Berkeley： USENIX Association， 2017： 217-233.
[42]	ZHANG R， BOND M D， ZHANG Y. Cape： compiler-aided program transformation for HTM-based cache side-channel defense ［C］// Proceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction. New York： ACM， 2022： 181-193.
[43]	JIANG F， TONG F， WANG H， et al. PCG： mitigating conflict-based cache side-channel attacks with prefetching ［EB/OL］. ［2024-06-12］. .
[44]	QURESHI M K. CEASER： mitigating conflict-based cache attacks via encrypted-address and remapping ［C］// Proceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway： IEEE， 2018： 775-787.
[45]	DOMNITSER L， JALEEL A， LOEW J， et al. Non-monopolizable caches ［J］. ACM Transactions on Architecture and Code Optimization， 2011， 8（4）： No.35.
[46]	KIM T， PEINADO M， MAINAR-RUIZ G. STEALTHMEM： system-level protection against cache-based side channel attacks in the cloud ［C］// Proceedings of the 21st USENIX Security Symposium. Berkeley： USENIX Association， 2012： 1-16.
[47]	LIU F， GE Q， YAROM Y， et al. CATalyst： defeating last-level cache side channel attacks in cloud computing ［C］// Proceedings of the 2016 IEEE International Symposium on High Performance Computer Architecture. Piscataway： IEEE， 2016： 406-418.

Review of conflict-based cache side-channel attacks and eviction sets

基于冲突的缓存侧信道攻击与驱逐集综述

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 47

Related Articles 6

Recommended Articles

Metrics

[1]	Zihao YAO, Yuanming LI, Ziqiang MA, Yang LI, Lianggen WEI. Multi-object cache side-channel attack detection model based on machine learning [J]. Journal of Computer Applications, 2024, 44(6): 1862-1871.
[2]	CHANG Tianyou, WEI Qiang, GENG Yangyang. Constructing method of PLC program model based on state transition [J]. Journal of Computer Applications, 2017, 37(12): 3574-3580.
[3]	CHEN Jian, SHEN Xiaojun, YAO Yiyang, XING Yafei, JU Xiaoming. Cache replacement strategy based on access mechanism of ciphertext policy attribute based encryption [J]. Journal of Computer Applications, 2017, 37(10): 2964-2967.
[4]	SU Yong-xin DUAN Bin. Unexpected behaviors detection in embedded system based on instruction stream [J]. Journal of Computer Applications, 2011, 31(06): 1483-1486.
[5]	XIE Jun, ZHANG Tao, ZHANG Shi-geng, HUANG Hao. Layered and separated operating system kernel [J]. Journal of Computer Applications, 2005, 25(06): 1286-1289.
[6]	ZHOU Jian-bo, DONG Hong-bin, LIANG Yi-wen. File system security model based on lineage mechanism [J]. Journal of Computer Applications, 2005, 25(05): 1160-1162.