冲突型缓存侧信道攻击的构建驱逐集研究综述

李真真，宋 威

(1.中国科学院信息工程研究所，北京 100085；2.中国科学院大学 网络空间安全学院，北京 100049)

0 引言

CPU漏洞为硬件安全的研究重点，特别是利用CPU微架构的漏洞，具有攻击方式多样、隐蔽性强、难以防御等特点，威胁用户信息和设备的安全[1]。传统的信息安全主要通过加密来保护隐私数据或密钥。从微观角度来看，计算机系统处理数据的信道，又可细分为2段：加密算法执行前的信道和加密算法运行后的信道。各种网络攻击技术，即使获得加密算法运行后的信道中的数据，依然需要通过密码破解来获得有用信息。软硬件的隔离机制和安全机制等，通常位于缓存层级之上。而缓存侧信道技术，针对加密算法执行前的信道部分，通过在计算机底层硬件系统的缓存存储器中获取有效信息，绕过了大部分依赖密码学的防御手段和系统的隔离和安全机制。此外，对于加解密的信道，如果能够从侧面获取一些信息，也能用于密码特征的推测，从而为密码破解提供一些帮助。

基于计算机系统微架构的侧信道攻击，只需要攻击者和受害者共享部分硬件资源就可以攻击。不同进程间共享缓存，为缓存侧信道攻击提供了条件。攻击者可以利用缓存侧信道攻击突破浏览器的沙盒保护，破解内核态的地址随机化，破解英特尔处理器的末级缓存分片算法，从而跨进程、跨处理器核、跨虚拟机，甚至跨SGX飞地发起缓存侧信道攻击[2]。随着缓存侧信道技术的不断发展，侧信道泄漏信息的带宽也越来越大。部分更复杂的微架构攻击中，缓存侧信道攻击是常见的关键子步骤。例如，广泛存在于高性能处理器中的幽灵攻击(Spectre)[3]和熔断攻击(Meltdown)[4]等。

本文重点介绍冲突型缓存侧信道攻击的共性且关键的子步骤：驱逐集构建，综述了缓存侧信道攻击中驱逐集构建方法的发展，梳理总结了驱逐集的三类实现技术，并对影响攻击性能的主要因素进行了分析。

1 驱逐集构建方法的发展

缓存侧信道攻击是攻击者通过检测特定数据在目标缓存的访问延迟的差异，来推测被攻击程序的行为。冲突型缓存侧信道攻击，是指使用一组特殊选取的地址(即驱逐集)诱发并利用目标缓存的冲突，从而推断出关键信息[5]。驱逐集由一组地址集合组成，这组地址集合拥有足够多个和目标地址缓存块映射到相同缓存组的地址(即冲突地址)，它能够利用替换策略将目标地址从缓存中驱逐。构建驱逐集的过程为学习虚拟地址到缓存组的映射。在冲突型缓存侧信道攻击中，攻击者先使用驱逐集把目标地址清除出缓存，或者读入受控的驱逐集地址，控制目标缓存组的状态。接着收集攻击目标运行时的缓存状态变化，再结合先验知识还原出密钥、用户行为信息、系统运行状态、内核空间的数据等。构建驱逐集是冲突型缓存侧信道攻击的首要步骤和关键步骤。

冲突型缓存侧信道攻击中，任何两个同时使用缓存的进程皆可成为攻守双方。不需要共享内存和特殊计算机指令等限制，而只需要在共享缓存上成功构建驱逐集。构建驱逐集不但影响攻击的可行性，同时影响攻击效果。因为缓存被多进程并发使用，所以容易受噪声干扰。为了减少噪声干扰，攻击者通过对内存使用情况进行缓存组级别的细粒度监控。Rowhammer攻击中，需要对某缓存块的驱逐频率足够高，从而提高位翻转的成功率。实际攻击中，对攻击目标的操作是受限的。减少无关数据的读入，从而减少对攻击目标的操作。驱逐集中包含的无关地址，会引起噪声，影响攻击速度和准确度。而减少目标地址的操作，能减少攻击受限和被检测的可能。

驱逐集构建方法的发展与冲突型缓存侧信道攻击的发展紧密相关。图1显示驱逐集的构建方法研究的发展时间线。早期的冲突型缓存侧信道攻击针对L1/L2缓存。因为L1/L2缓存的组数较小，且采用直接位映射方式，构建驱逐集的方法为直接计算出驱逐集。比如候选地址与目标地址以页面大小相同或数倍的偏移量进行对齐。直接计算驱逐集的构建方法可以追溯到Osvik等[6]在2006年实现的针对L1缓存冲突型缓存侧信道攻击。由于攻击者与受害者同驻一个内核比较困难，一定限度限制攻击的使用效果。对于多核处理器，共享末级缓存更容易。2015年成功实施了末级缓存(Last Level Cache，LLC)上的跨核攻击，攻击效果开始显现[7]。但是在末级缓存上直接计算出驱逐集困难。即使攻击者已知微架构的物理地址与切片索引的映射，开启大页，但是在真正的攻击中，物理地址的受控信息仍是不够的，驱逐集中仍包含大量非冲突地址。为解决末级缓存上构建驱逐集问题，第一个构建驱逐集算法(基础裁减法)被提出。2018年，Qureshi[5]首先提出动态随机化缓存CEASER，通过挫败基础裁减法来防御冲突型缓存侧信道攻击。2019年，比基础裁减法更快的分组裁减法[8]被提出。同年，Qureshi[9]发现更快的分组裁减法能突破动态随机化缓存的限制，并提出动态随机化的分组式(Skewed)缓存CEASER-S。随后基础冲突测试法[9]、PPP法[10]和W+W[11]等构造驱逐集算法不断被提出，突破动态随机化的分组式缓存的限制，仍能实施冲突型缓存侧信道攻击。2022年，Purnal等[12]在异构处理器上首次实施冲突型缓存侧信道攻击，并提出针对异构处理器的联合冲突测试法。2023年，Katzman[13]成功利用低精度时钟实施攻击，并同时证明使用低精度时钟，仍能创建构建驱逐集。

图1 构建驱逐集研究的发展时间线

2 构建驱逐集算法的分类

现有构建驱逐集算法主要有三大类：裁减类算法、冲突测试类算法和探测(Probe)类算法。构建驱逐集算法的分类见表1。从该表看出不同类型算法在准备候选地址(集合)、冲突前需缓存命中的地址类型和识别冲突方式三个过程中存在区别。下面对三类算法的基本原理、发展和代表性算法进行详细分析。

表1 构建驱逐集算法的分类

2.1 裁减类算法

2015年，Liu等[14]提出减少驱逐集中的非冲突地址从而减少噪声的方法，即第一个构建驱逐集算法：基础裁减法(Single-Holdout Method，SHM)。2019年，Vila等[8]对裁减法的理论和实现进行研究，并最早提出了初始的分组裁减法(Group Elimination Method，GEM)。2019年，Song等[15]分析了基础裁减法和初始的分组裁减法的时间复杂度上限、实现问题等，并提出了随机分组裁减法。

裁减类算法中，候选集合是目标地址的驱逐集的检测条件为：读取候选集合后，成功驱逐目标地址。访问足够大的虚拟地址集就足以驱逐出缓存中任何内容，这意味着只要虚拟地址集合足够大，该虚拟地址集合一定是目标缓存组的驱逐集。裁减类算法的基本原理如下：先选择一个足够大的候选集合，然后不断裁减候选地址集合，再次检测裁减后的候选集合是否仍是驱逐集，从而快速提升冲突地址在驱逐集中的占比。

裁减算法一般由两个步骤组成：(1)构建出一个大的驱逐集，作为候选集合，(2)将这个集合减少到它的最小驱逐集。即一组随机地址集合撞击目标地址，然后裁减随机地址集合。先读入攻击目标地址，然后读入攻击者控制的一组较大的候选地址集合，再观测攻击目标是否被挤出；如果被挤出，说明候选地址集合是驱逐集。

2.2 冲突测试类算法

冲突测试类算法先把目标地址读入缓存，然后读取一个候选地址，接着观测是否驱逐目标地址。若该候选地址的读入引起目标的挤出，则该候选地址与目标地址冲突。冲突测试类算法的基本流程如图2所示。假设攻击者可以获取无限多的随机地址，该攻击者可通过逐个测试每个地址是否与目标地址冲突来收集一个驱逐集。首先选择一个随机地址，检测该随机地址是否与目标地址冲突。如果随机地址与目标地址冲突，则把目标地址的冲突地址加入目标集合。如果该地址不是目标地址的冲突地址，或者已经找到的冲突地址不足以构成驱逐集，则再次随机选择一个地址，并检测该地址，直到已经找到足够多的冲突地址。

图2 冲突测试类算法的基本流程图

冲突测试类算法的识别冲突方式呈现多样化。基础冲突测试法(Conflict Testing，CT)，通过测试目标地址的延时是否超过末级缓存未命中的阈值，来观测攻击目标是否被挤出末级缓存；W+W法(Write+Write)的冲突检测方式是观察写效应；联合冲突测试法的识别冲突的方式为观测数据直接交换(Data-Direct IO，DDIO)域的挤出。

2019年，基础冲突测试法由Qureshi等提出，并用在末级缓存采用随机替换算法的分组式缓存上[9]。2021年，Song等[16]提出基础冲突测试法也对末级缓存采用LRU和RRIP替换算法的随机化的分组式缓存也有效。Purnal等[17]在英特尔i7处理器上实现了基础冲突测试法。2022年，Thoma等[11]发现了英特尔处理器的写效应，并把写效应作为冲突测试的方式，从而提出了基础冲突测试法的变体W+W法。2022年，Purnal等[12]使用异构处理器的硬件结构特点对冲突测试类算法进行性能优化，并首次发现了非随机化缓存情况下，最小驱逐集的冲突地址数比缓存路数小的场景。

2.3 探测类算法

探测类算法的基本原理为先选取候选集合的子集，然后把该子集的地址全部读入缓存，使多个缓存组受控。越多缓存组受控时，攻击越容易受噪声干扰。驱逐集的实际使用中，驱逐集需要减少到只含有目标缓存组的驱逐集。探测步骤解决了该问题。在探测步骤中，攻击者读入目标地址后，被挤出的地址为与目标地址冲突的候选地址。

探测类算法的代表性算法有PPP法。PPP法(Prime，Prune and Probe，PPP)[10，18]采用目标地址撞击随机地址的方式。PPP算法的流程图如图3所示。每轮PPP过程包含Prime、Prune和Probe三个步骤。

图3 PPP算法的流程图

在Prime步骤，攻击者读入初始候选集合的地址。因为初始候选集合的地址会相互挤出，所以需要裁减出部分地址。在Prune步骤，所有被挤出地址都被裁减掉。裁减过程结束，所有攻击者控制的候选地址全部安装入缓存。最后的Probe步骤中，攻击者或受害者读入攻击目标的地址，然后观测攻击者控制的地址是否有挤出。被挤出的地址是目标地址的缓存冲突地址。执行一轮PPP过程或者反复执行PPP过程。收集足够多的缓存冲突地址，得到驱逐集。

PPP法采用了一种自底向上的方法：攻击者从一个空集开始，增量地增加与目标地址存在缓存冲突的地址。当攻击者无法访问攻击目标时，唯一可用的过程是准备缓存状态，等待受害者执行，并观察缓存状态的变化。

2019年，Werner等[19]提出了动态随机化的分组式缓存结构ScatterCache，从而增加使用裁减类算法寻找驱逐集的难度。2019年，Purnal等[10]提出了PPP法，并在ScatterCache上成功创建驱逐集。实验证明PPP法显著减少所需的受害者访问次数。2021年，Purnal等[18]对动态随机化的分组式缓存进行系统评估，并提出了针对动态随机化的分组式缓存的三种PPP优化算法。

通过对不同构建驱逐集算法的关键特性，结合实际攻击场景、攻击目标，选择出合适的算法，能提高攻击效果。表2对这些算法的关键特性进行对比。其中末级缓存的路数为W，缓存组数为S，切片数为C。初始候选集的大小为n。D为DDIO的路数。对于具体的计算机体系结构，W、S、C、D均为常数。

表2 构建驱逐集算法的关键特性对比

3 影响算法性能的因素分析

在构建驱逐集研究中，需要发现并解决构建驱逐集中的不利因素。这些不利因素是真实处理器上构建驱逐集的成功率下降的关键。现代处理器为了提升性能，采用多级缓存、TLB、硬件预取、分支预测等架构设计。现代操作系统的多任务并发等设计，也同时给算法程序带来背景噪声。本节总结了缓存、TLB、操作系统和时钟等因素对构建驱逐集算法性能的影响。

3.1 缓存结构的影响

缓存替换算法决定缓存块的挤出顺序，故缓存替换算法是构建驱逐集算法的重要因素。以裁减类算法为例。Vila等[8]发现采用LRU替换算法的缓存组比采用其他替换算法的缓存组上，构建驱逐集的成功率更高。Song等[15]对驱逐集地址访问模式进行优化，从而提高驱逐的成功率。英特尔的服务器级处理器从Skylake-SP开始采用非包含型末级缓存，即私有缓存中的地址不一定存在于末级缓存。两种提高驱逐成功率的优化方法，使裁减类算法突破了非包含型末级缓存的限制：2019年，Yan等[20]对裁减法的检测方法进行优化：先构建一个与候选集合映射到相同L2缓存组的L2驱逐集。在目标地址和候选集合的地址读入缓存后，读入L2驱逐集，把候选集合中的地址从L2缓存挤到末级缓存。另外，2019年Song等[15]发现英特尔Xeon 4110上使用单线程访问方法不能构建驱逐集。但是采用多线程多核并行访问驱逐集的方式访问驱逐集时，能驱逐成功目标地址。因为采用多线程多处理器核并行访问一个地址时，同一个地址被同时读入多个私有处理器核，迫使该地址存在于末级缓存。

3.2 TLB的影响

为了加速虚拟地址到物理地址的转换，TLB存放部分虚拟地址到物理地址的转换关系。虚拟地址和物理地址转换中，先查询TLB，TLB未命中，再进行缓慢的查询多级页表模式。访问虚拟地址，涉及虚拟地址转换物理地址，会进行非常频繁的TLB访问。虚拟地址翻译数量增加，TLB的容量有限，故TLB的未命中率同步增加，并最终会导致触发大量的页表访问。页表的访问需要读取缓存获得数据，这导致了缓存状态的改变，干扰构建驱逐集过程。为保证检测缓存延时的正确性，需要防止访问某地址的延时包含TLB未命中的时间。一种减少TLB影响的方式为开启大页，页面大小从4 KB变成2 MB，访问候选集合需要访问的页面数量减少，从而减少TLB未命中的概率[21，14]。另外一种方式为TLB preload[22]。攻击者可以在测量地址的读取时间前，先访问同页面的不同地址，确保检测延时的时候，对应的页面不会缺页从而访问TLB。

3.3 操作系统的影响

现代操作系统是多任务运行的，任务共享软硬件资源。任务切换、上下文切换、中断等带来抖动，从而带来噪声和干扰。构建驱逐集算法的程序不是唯一正在运行的进程，可能同时存在较高CPU负载的其他程序。操作系统的线程调度算法会定期中断代码并执行上下文切换，甚至还会涉及切换虚拟机等更多的上下文切换。采用多次测量或验证方式，能减少噪声的影响。常见的方法有：重复多次测量，直到收集到一致的结果[17]；对多次测量的延时结果求平均值[8，11，15]。

3.4 时钟

确定某个地址是否在某级缓存命中，通常需要使用适当的高精度时钟来测试某个地址的访问时间。部分高精度时钟不可用时，仍能找到可替代的高精度的时钟源[23]。2023年，Katzman等[13]提出了低精度时钟能测量纳秒级别的延时差异。Katzman等[13]只使用一个分辨率为0.1 ms的定时器时，把信号放大了6个数量级，使读入地址是否在缓存两种情况下的时间差超过100 ms，并且平均15 s创建一个驱逐集。这表明降低时钟分辨率并不能阻止驱逐集的建立。

4 结论

虽然计算机的算力在飞速发展，但是依然难以在合理的时间内破解加密算法。计算机系统的隔离和安全机制随着技术和威胁的不断发展而演进。缓存侧信道攻击作为推断密钥和绕过系统的隔离和安全的方案，让信息安全防不胜防。

然而，缓存侧信道攻击还存在一些待解决待优化的问题。比如，存储器目标地址的访问受限、缓存侧信道数据噪声大、缓存结构随着硬件设计在发展变化等。因此，缓存侧信道攻击技术中驱逐集的构建，需要考虑目标地址的访问次数。需要根据具体型号的计算机体系结构中的缓存结构、TLB机制等硬件设计进行算法的选择和优化。还需要研究不同操作系统和程序软件下的驱逐集的自适应构建算法。随着计算机时钟精度的提高和时钟测量技术的进步，结合缓存结构逆向技术和网络通信技术，未来构建驱逐集算法的攻击应用会更多，缓存侧信道攻击的影响将会更广泛。