Group of Software Security In Progress

PhantomCache Obfuscating Cache Conflicts With Localized Randomization

作者:Qinhan Tan1, Zhihua Zeng1, Kai Bu1, Kui Ren1

单位:1Zhejiang University

会议:NDSS 2021

论文链接:PhantomCache: Obfuscating Cache Conflicts with Localized Randomization

Abstract

许多cache timing攻击方法步骤需要攻击者明确memory block与cache set之间映射关系,例如Prime+Probe方法中的最小驱逐集(Minimal Eviction Set)计算过程等。

本文提出了一种相对应的保护方案——PhantomCache。该方案通过局部随机化技术(localized randomization technique),破坏memory block到cache set之间的固定映射关系。具体而言,PhantomCache将每个memory block映射到有限数量的若干cache set中的一个;在检索该memory block对应的cache set时,仅在该若干个cache set的范围内进行检索。

1. PROBLEM

1.1 Conflict-based Cache Timing Attack

Prime+Probe 攻击的基本流程:

image-20210411143242805

1.2 Minimal Eviction Set

虚拟地址、物理地址与cache set编号的关系:

image-20210411143658549

从虚拟地址到物理地址:Frame Number变化,Page Offset不变

image-20210411143720121

计算最小驱逐集的一种常见算法:

image-20210411143831797

算法复杂度:$\mathcal{O}( E )$

$E$:E个物理地址中一定可以提取出一个最小驱逐集

1.3 (Inefficient) Randomized Mapping for LLC

全局随机映射方案NewCache[25]:访问数据时需要搜索所有cache line,其在L1上的overhead可以接收,但在LLC上很难应用。

2. OVERVIEW

这一部分中,作者介绍了PhantomCache的设计原理。

2.1 Motivation

cache关联度为m的情况下,

n个物理地址,每个物理地址可能被映射到r个cache set,

且这n个物理地址对应的cache set中有一个公共cache set(称这里的每个物理地址为一个relevant address),

则,访问这n个relevant address之后,能对公共cache set实现prime的概率为:

image-20210411150235057

$P r{\text {prime }}(n)=\sum{i=m}^{n} C_{n}^{i} \times\left(\frac{1}{r}\right)^{i} \times\left(\frac{r-1}{r}\right)^{n-i}$

其中:

  • $\left(\frac{1}{r}\right)^{i} \times\left(\frac{r-1}{r}\right)^{n-i}$含义:n个relevant address中,有i个映射到了公共cache set,有n-i个未映射到公共cache set
  • $C_{n}^{i}$含义:从n个relevant address中选出i个,共有这么多种选法
  • $\sum_{i=m}^{n}$含义:i一定大于等于m,否则不足以成为Eviction Set

在这种情况下,如果cache关联度为m,攻击者即使访问了m个relevant address,也不一定会prime目标cache set。 攻击者平均需要访问整个m

个地址组成的集合$r^m$次

2.2 Methodology

PhantomCache的设计思路:两个阶段的随机映射。

(1)每次开机后,为每个物理地址,随机选取r个 cache set

(2)需要将某个物理地址的数据放入LLC时,从r个cache set中随机选取一个

(3)需要检索某个物理地址的数据是否在LLC时,并行检索r个cache set

image-20210411145934418

2.2.1 Placement policy(将memory block放入cache的方法)

image-20210411150152577

  • r:每个物理地址对应r个cache set
  • F函数:从物理地址到cache set编号的映射函数
  • $salt_i$:每次开机时,使用片上伪随机数生成on-chip pseudo-random number generation(PRNG)初始化的随机盐值,整个处理器中一共有r个

image-20210411150858453

  • PRNG(r):生成一个0到r-1之间的随机数

2.2.2 Search policy(从cache中检索某个物理地址memory block的方法)

首先计算出该物理地址的所有r个候选cache set的cache set编号,

然后将该物理地址的tag bits和所有r个候选cache set的所有cache line的tag bits进行比较(并行比较)。

2.2.3 Replacement policy(cache line替换方法)

不做改变。

3. DESIGN

3.1 Architecture: Localized Randomization

image-20210411152044421

3.1.1 读数据:

借助memory-to-cache mapping $\rightarrow$ 确定r个index $\rightarrow$ 查找r个cache set的所有cache line $\rightarrow$ 命中或缺失:

  • 命中 $\rightarrow$ 获取数据块
  • 缺失:
    • $\rightarrow$ 随机index选择(选出一个介于0到r-1之间的index值) $\rightarrow$ 借助memory-to-cache mapping(利用之前已有的计算结果)$\rightarrow$ 借助memory-to-cache mapping 确定一个index
    • $\rightarrow$ 根据物理地址读主存 $\rightarrow$ 获得数据块放入cache(同时,如果被替换出去的cache块是脏数据块,则需要写回到主存,需通过address restoration计算出cache数据块对应的物理地址)

3.1.2 写数据:

借助memory-to-cache mapping $\rightarrow$ 确定r个index $\rightarrow$ 查找r个cache set的所有cache line $\rightarrow$ 命中或缺失:

  • 命中 $\rightarrow$ 修改cache中数据(不更新主存,只有当前块将被替换出cache之前,才写回主存 ,即write back机制)
  • 缺失 $\rightarrow$ 随机index选择(选出一个介于0到r-1之间的index值) $\rightarrow$ 借助memory-to-cache mapping (利用之前已有的计算结果) $\rightarrow$ 确定一个index $\rightarrow$ 写入数据到cache(同时,如果被替换出去的cache块是脏数据块,需要写回到主存,需要通过address restoration计算出cache数据块对应的物理地址)

3.2 Memory-to-Cache Mapping

通过物理地址的tag位、index位和随机盐值salt(共有r个)计算出cache set编号(cache index)(共有r个)的过程:

image-20210411153307269

我的理解:

拆分物理地址tag和index的意义:

使得 可以通过tag、salt、cache index来恢复出 index bits

(方法是:先计算saltleft和tag的哈希结果,然后通过哈希XOR saltright XOR cache index,就能得到index bits),这样就可以不用存储index bits了

因为是随机映射,正常来讲是需要在cache line中额外存储index bits(,才能保证从cache 写回主存时,能知道cache line中数据对应的主存地址;作者的设计,让index bits不需要被存储在cache line中。

拆分salt的意义:

保证映射对攻击者不可见(保证安全性)

3.3 Single–Clock-Cycle Hash

tag bits与$salt_left$的哈希结果的计算过程

基于LFSR的Toeplitz哈希算法:

image-20210411153652332

​ 如果消息位为1,则每次迭代将result与当前state进行XOR;

​ 如果消息位为0,则result不变;

​ 然后将state更新为新的state

image-20210411153807515

m与tag字段一样长,应该短于最多64位的主存地址。

  • 绿色的:XOR门,每条路径最多6个
  • 蓝色的:AND门,每条路径最多1个

通常,现代处理器可以在一个时钟周期内处理15到20个门操作[34];

某些时钟频率极高的处理器,单个时钟周期内只能进行4 到5个门操作,在这种情况下,我们的哈希函数可能会带来两个时钟周期的延迟

哈希函数的安全性:

PhantomCache的应用场景不同于典型的加密场景。假定攻击者仅知道受害者的物理地址,并且只能观察cache冲突。由于采用了随机盐值,攻击者无法控制哈希函数的输入,也无法知道哈希函数的输出。这增加了故意创建哈希冲突的难度。

3.4 Cache Access

image-20210411154308887

3.5 Address Restoration

从cache中清除脏数据块时,将发生address restoration

image-20210411154345361

4. IMPLEMENTATION

作者使用ChampSim [1](一种trace-based的微体系结构模拟器)实现了PhantomCache。

5. EVALUATION

5.1 Workloads

  • workloads:使用了SPECspeed 2017 Integer和SPECspeed 2017 Floating Point suites中的所有20个benchmark
    • single workloadn核CPU上,每个物理核都在运行相同的benchmark
    • mixed workloadn核CPU上,每个物理核都在运行不同的benchmark,这n个benchmark是从20个benchmark中随机选出来的
  • 每个workload至少运行20亿条指令。

5.2 Metrics

衡量指标:

  • instructions per cycle (IPC)
    • 每时钟周期执行的指令数
    • 越高,性能越好
  • misses per 1,000 instructions(MPKI)
    • 每执行1000条指令过程中LLC上发生的cache缺失数
    • 越低,性能越好
  • miss rate of LLC
    • LLC上的未命中率
    • 越低,性能越好

baseline:未经任何修改的cache

5.3 Results

cache:16MB 16路组相联 LLC

在所有20个SPEC CPU 2017 benchmarks上,相比于baseline,PhantomCache使性能平均降低了1.20%。

ScatterCache **[45](另一种基于映射关系的cache保护方案)相比,在两者公共的17个benchmark上,PhantomCache的效率是ScatterCache的2倍以上**。(PhantomCache仅带来了0.5%的性能下降)。

image-20210411180916018

针对混合工作负载,PhantomCache带来的平均性能降低仅为0.50%,如下图右侧图表所示。

image-20210411181524114