RELOAD+REFRESH: Abusing Cache Replacement Policies to Perform Stealthy Cache Attacks
背景知识
1、缓存架构
•现代处理器普遍采用多级层次化高速缓存架构，一般包含三级。
•低级缓存（L1, L2）为各核心独享，容量更小，离处理器更近；
•最后一级缓存（称为LLC或L3）为核心共享，容量更大。它被划分为多个区块，分别对应一个CPU核心，通过环形总线互连实现共享。每个元素的物理地址通过复杂寻址功能确定其到区块的映射。
•Intel处理器中通常具有包容式L3缓存：私有低级缓存中存在的所有数据都将位于共享的L3缓存中。这种方法使缓存一致性更容易实现。但是，大概是由于缓存攻击，最新的Intel Skylake Server微体系结构使用了非包容性的L3缓存。
2、缓存替换策略
•当处理器请求数据时，首先从缓存中取数据（由低级到最后一级）。
•缓存命中：从缓存中加载数据。
•缓存未命中：从主存中取数据，并将其放入缓存，假定其在不久的将来会被再次使用。若缓存组中没有空闲行，则内存控制器必须决定将缓存中的哪个元素逐出。由于每当有一个缓存未命中时，处理器可能会停顿几个周期，因此决定逐出哪个数据和保留哪个数据对于性能至关重要。
•有很多可用的替换策略，包括FIFO（先进先出），LRU（最近最少使用）或其近似策略，例如NRU （最近未使用），LFU（最近最少使用），CLOCK （保留元素的循环列表）甚至伪随机替换策略。由于真正的LRU策略需要复杂的硬件来跟踪每次访问，难以实施，因此现代高性能处理器应用LRU的近似策略。
3、缓存攻击
•缓存攻击监视缓存的使用（缓存命中和未命中的序列）以取回有关共驻主存的受害进程的信息。只要安全性至关重要的软件的内存访问模式取决于诸如密钥之类的敏感数据的实际值，攻击者就可以推断出这些敏感数据。
•通常分为三类：FLUSH+RELOAD, PRIME+PROBE, EVICT+TIME。
•其中FLUSH+RELOAD和PRIME+PROBE及其变体具有更优的性能。
•两种攻击均以LLC为目标，选择受害者进程预期将访问的一个内存位置。它们包括三个阶段：初始化（攻击者以某种方式准备缓存），等待（攻击者在受害进程执行时等待）和恢复（攻击者检查缓存的状态以获取有关受害进程信息）。
4、应对措施
•限制对可利用于获取受害者信息的共享硬件资源的访问；
•系统级软件方法：修改当前的云基础架构或Linux内核；
•针对敏感应用程序进行专门设计，以防止出现侧信道（不依赖敏感信息进行内存访问）；
•有效防御攻击的唯一对策可能是在用户级别实施的基于检测的对策。缓存攻击利用在某些硬件中运行程序的影响获取信息。类似地，这些对策采用监视机制来观察这些影响。检测系统可以使用时间测量，硬件性能计数器或将数据放置在Intel TSX指令定义的事务区域中等方式测量受害者或受害者和攻击者的LLC缓存未命中受到的影响。然而，这些系统将无法检测到不会在受害方产生缓存未命中的攻击。
本文贡献
•提出了一种检测现代缓存中采用的替换策略的方法；
•揭示了第四代到第八代现代英特尔酷睿处理器中实施的替换策略；
•扩展了对现代缓存的理解，并为改进传统缓存攻击奠定了基础；
•提出了一种新的缓存攻击RELOAD + REFRESH，可以利用Intel缓存替换策略来提取有关受害者内存访问的信息。
•实验证明所提出的攻击对受害者造成的缓存未命中可忽略不计，使现有的检测方法失效。
Retrieval of Intel cache eviction policies
•本文主要关注LLC，原因是：以LLC为目标的攻击不需要攻击者和受害者运行在同一核心这一前提；从LLC中能够提取细粒度的信息，是很多研究工作关注的重点。确定缓存采用的驱逐策略有利于攻击者更加隐蔽有效地完成攻击。
•为了研究驱逐策略，本文使用软件方法模拟硬件。使用自己的数据填充一组缓存，在需要时访问该数据并强制发生一次未命中，观察组中的哪个元素被逐出。
•对于所有实验，我们都启用了系统的hugepages功能。
•访问的顺序对于推断驱逐策略很重要。我们使用指令lfence来强制按序执行，确保所有lfence前的加载和存储指令在其后的加载或存储指令之前完成。
•本文提出的检测缓存驱逐策略的思路就是将每个集合中数据的实际演变与运行期间驱逐策略定义的理论演变进行比较。
•经过多次实验，我们得出的结论是，在处理器上实施的策略与最符合实验观察结果的策略相对应。
检测算法：
•本文要揭示的是LLC采用的缓存策略（L1采用的策略不同，L2相同）。在所有情况下都正确预测了超过97％的策略，且错误很可能是由噪声引起的。
RELOAD + REFRESH
•我们对实验中揭示的在英特尔处理器中实施的策略进行描述。假设该策略名为Quad-Age LRU。下图表示了在处理器请求时检索一条数据所遵循的过程。
•我们实验中用到的处理器仅在插入年龄Insertion Age上存在差异，即载入缓存时缓存行的初始化年龄。
•采用set dueling的第四代、第五代处理器包括插入年龄为2或3两种模式，称为mode 1，mode 2；
•其余的处理器（6th，7th，8th）插入年龄为2，即与mode 1相同。
主要思想：
如果实现了任何类型的共享机制，则知道驱逐策略的攻击者可以将受害者可能会使用的一些数据放置在缓存集中的所需位置。由于块的位置及其年龄确定了确切的驱逐候选对象，因此攻击者可以将目标数据强制为驱逐候选对象。如果受害者使用该目标，则其不再是驱逐候选对象，因为其年龄值随着访问减小。攻击者可以强制发生一次未命中，然后检查目标是否仍在高速缓存中。如果是，则受害者使用了该数据。而且在这个过程中受害者从缓存中加载了数据，而没有遭受任何缓存未命中（没有攻击踪迹）。
攻击步骤：
Mode 2情况下，step 1-5与mode 1相同。但step 6取决于受害者和攻击者是否在同一内核中。
•当不在同一核内时，step 5已经还原到了初始状态，不再需要step 6；
•在同一核内时，仍然需要step 6访问逐出集中的其余数据，使低级别缓存中的目标数据被逐出。
利用Mode 2策略还可以实现一种无需共享内存的可检测的快速跨核缓存攻击：
•攻击者首先用自己的数据填充缓存集；等待受害者执行；重载第一个数据，若重载时间较短，则受害者未访问目标数据，否则访问了目标数据。
•若受害者访问了目标数据，那么在第三步的重载后，缓存状态已回到了初始状态，等同于REFRESH操作。
•若受害者未访问目标数据，那么攻击者还需要清除并重载自己的数据以初始化其年龄。
算法2,3总结了插入年龄为2时RELOAD+REFRESH的步骤：
•为了避免乱序执行，确保以固定顺序载入，确保元素的年龄值都被更新，使用链表形式访问eviction_set（每个元素存放下一个内存行地址）。
Noise tolerace
•对于本文提出的攻击，载入缓存的顺序非常重要。如果其他进程同时执行并使用映射到同一缓存块的数据，引入噪声，攻击的有效性就会受到影响并可能触发一些检测机制。
•假设生成噪声的进程仅使用了一个地址，则攻击者可以轻松处理噪声，避免检测且仍能获得有关受害者的信息。
•处理噪声的技巧是将目标数据放置在缓存集中的另一个位置（以第二个位置为例）。如果有任何数据映射到该缓存集，则攻击者的数据被替换，特别是放置在缓存集第一位的数据。当攻击者强制发生未命中时，驱逐候选将是目标地址（如果受害者未使用目标数据）或插入在第三位的元素（受害者使用了目标数据）。攻击者通过重新加载目标数据来获取有关受害者的信息，并且他必须从第三个位置开始REFRESH，并以第一个元素作为结束，从缓存中逐出“噪声”，将所有块的年龄重新初始化为2。
Comparison with previous approaches
与FLUSH+RELOAD，PRIME+PROBE攻击进行比较。
1、隐蔽通道
•表中列出了每个固定时间窗口的F-Score实验结果。
•这些实验是在i5-7600K机器中进行的。当样本之间的等待时间很短时，PRIME + PROBE和RELOAD + REFRESH都无法区分1和0，PRIME+ PROBE在测试中体现了更好的分辨率。
•尽管R+R的分辨率低于其他的攻击，它仍可用于获取加密实现的密钥。我们将重现两个已发布的攻击来展示这一事实。
2、AES T-table攻击
（1）重复进行实验直至恢复密钥1000次所需的平均样本数量及F-score
（2）LLC未命中次数的测量
•获取AES密钥的RELOAD+REFRESH攻击对受害者进程影响很小。
•我们使用PAPI软件接口读取受害者进程相关的计数器，比较正常执行和受到攻击时受害者进程每次加密发生的LLC未命中次数。
（3）测量每次加密耗费的时间（rdtsc）
•与其他攻击相比，R+R攻击与正常执行的加密时间差异较小，无攻击的平均加密时间为595个周期，R+R攻击为623个周期。
•存在差异的原因是进行R+R攻击时，受害者如果要使用目标数据则需要从LLC中而不是L1，L2中加载。
3、RSA 平方乘算法攻击
•我们仅监视“乘”操作，使用监视事件间的时间差来获取密钥。
•差异存在原因：时间戳收集时间不同。正常执行时收集于每个指数位处理完成后，攻击时收集于reload操作完成后。
（1）针对RSA的不同攻击的准确率及F-score如下表。
（2）LLC未命中次数的测量
•我们观察到未命中次数的分布不仅与攻击相关，还依赖于密钥。因此，每次加密发生的未命中次数不能用于检测正在执行的攻击，需要在解密执行的同时测量未命中次数。
•我们依然定时监视受害者LLC未命中次数，以100μs为采样间隔在每种情况下收集1000个完整RSA解密的样本。
•结果表明在初始化步骤中未命中的数目有所变化。在此初始化过程中，仅考虑在不同情况下导致的未命中数是不可能区分攻击和正常操作的。之后，在正常操作期间，未命中的数量变得稳定并且趋于零。同样，可以在RELOAD + REFRESH攻击期间观察到这种趋势。相反，FLUSH + RELOAD和PRIME + PROBE都会引起大量的未命中。
•RELOAD + REFRESH方法（以及其他攻击）与解密操作不同步，因此，在某些情况下，受害者和攻击者都可能尝试同时访问目标数据。如果受害者执行乘法运算时，攻击者刷新并重新加载提及的缓存行，那么受害者可能会发生一次未命中。
Detection evaluation
•RELOAD + REFRESH在受害进程上引起的LLC未命中次数可忽略不计。因此，除非进行调整，否则现有的检测技术将无法检测到该攻击。
•本文强调了一个在基于性能计数器的检测系统中尚未考虑的问题：将来的攻击是否会类似地基于此类系统计数器的选择进行绕过，性能计数器的选择是个难题。此外，每个平台中可以并行读取的可用计数器的数量受到限制。因此，检测系统无法随意扩展以应对未来的攻击。
•为了量化我们的建议对受害者的影响，并且为了提供一些关于检测系统应考虑使用哪些计数器来处理RELOAD + REFRESH的见解，我们在执行对AES和RSA的攻击时定期监视不同计数器并分析结果。本文使用PAPI收集此类信息，采样率设置为100μs。鉴于并非所有计数器都可以并行读取，因此我们重复了多次实验。当采样间隔在预期值±此采样值的10％的范围内时，我们将结果合并。在RSA的特定情况下，删除了涉及执行开始的样本（我们将重点放在稳定部分）。最后，我们对每个算法随机选择了10000个样本并进行攻击并分析。
•从表5可以看出，L3丢失或访问的单个计数器不能用于区分攻击和两种目标算法的正常操作；L3访问计数能够用于RSA攻击检测，但不能用于AES。L2指令未命中计数器，对两种算法均可以区分攻击和非攻击。
•我们可以得出结论，RELOAD + REFRESH仅在低级缓存中以可观察的方式改变了系统的性能。因此，引用LLC的计数器不足以检测RELOAD + REFRESH。
•因此，如果现有的检测系统希望能够检测到低级缓存事件，则需要对其进行调整或重新训练，使其包含有关低级缓存事件的其他信息。但是，依靠低级缓存事件来检测攻击可能比较困难，因为尚不清楚与受害者共享计算机的良性应用程序会如何影响它。因此，必须进行进一步分析以建立可靠的检测系统。
Discussion of the results
•替换算法中没有随机性使得可以准确确定在发生冲突的情况下将移除位于缓存集中的哪些元素。同样，英特尔处理器中包含的准确计时器以及cflush指令，可以跟踪对不同缓存的访问，并强制缓存行具有所需的年龄。我们利用这些事实来运行RELOAD + REFRESH。反过来，RELOAD + REFRESH会按预期工作，这一事实证实了我们有关替换策略的一些分析结果。
•RELOAD + REFRESH只是在启用了某种内存共享机制的前提下的一种利用驱逐策略的方法。如果受害者和攻击者不共享内存，则可以阻止这一攻击。也可以通过一些其他针对缓存攻击的常规对策来限制资源共享，从而防止这种情况的发生。但是，如第4节所述，可以使RELOAD + REFRESH在没有共享内存的情况下工作。我们没有进一步探讨这种攻击变体，因为它需要将替换策略保持在模式2中，而最新的Intel处理器也无法使用这种替换策略。
讨论：
1、侧信道攻击能否用于获取特征信息以实现程序调用库的特征识别？
目前已有工作提出利用侧信道攻击通过获取页面访问信息识别SGX程序的访问库类型及编译选项信息。对于一般程序，从理论上是可以实现的，需要进一步的研究。
2、侧信道攻击多以AES、RSA等算法为目标，很少见到对于椭圆曲线加密算法、国密算法等实现的攻击，这些算法是否对侧信道攻击具有天然的抵抗？
3、侧信道攻击能否在黑盒下执行？
侧信道攻击在黑盒下完成几乎是不可能的，需要攻击者对目标程序有非常深入的了解，提前对其进行分析，且具有一定的访问权限，能够获知受害进程执行时预期使用的缓存集、访问的地址等信息。
4、RELOAD+REFRESH攻击能否在AMD处理器上实现？
该文中提到的该攻击的执行前提仅包括存在内存共享机制，理论上能够在AMD处理器上执行，实际情况需要在AMD上进行具体实验。
5、比起其他攻击，RELOAD+REFRESH攻击能否带来更好的攻击效果，应用于原本攻击无法实现的场景？作者为什么会提出这样一种攻击？
从攻击有效性来看，该攻击应该是低于FLUSH+RELOAD攻击的，其攻击性能和范围并没有提升。它的重点是其在面对基于性能计数器的检测时的隐蔽性。提出的思路就是当前基于性能计数器的检测系统很多都是根据缓存攻击发生时会导致受害进程LLC未命中次数增加这一假设实现的，那么作者就提出一种不会对LLC未命中产生影响的攻击，受害者要访问的目标数据始终存放在缓存中而不被攻击者驱逐，也就绕过了这种检测。
6、该攻击在受到噪声干扰后可能会导致攻击失效或被检测，虽然文中提出了对单个噪声的处理措施，但在实际执行时噪声难以预测的情况下该措施有效性大大降低，因此可以通过在程序编译过程中加入噪声等方式缓解此攻击带来的影响。
7、该攻击能否用于Intel处理器的crosstalk漏洞？
