Tag: cache

Home » Posts tagged "cache"
Computer, Murmuring, Network, Security, Service, SoftwareNo Comment Cassandra, Computer, Database, Movie, Murmuring, Network, Programming, Recreation, Service, Software, TelevisionNo Comment

Working Set Size (WSS) 的想法

Netflix 的 Brendan Gregg (他比較知名的發明是 Flame Graph) 寫了一篇「How To Measure the Working Set Size on Linux」，他想要量測單位時間內會用到的記憶體區塊大小：

The Working Set Size (WSS) is how much memory an application needs to keep working. Your app may have populated 100 Gbytes of main memory, but only uses 50 Mbytes each second to do its job. That's the working set size. It is used for capacity planning and scalability analysis.

這可以拿來分析這些應用程式是否能夠利用 L1/L2/L3 cache 大幅增加執行速度，於是就可以做成圖，像是這樣：

在 Netflix 這樣人數的公司，需要設計一些有用的指標，另外發展出對應的工具，讓其他人更容易迅速掌握狀況，畢竟不是每個人都有上天下海的能力，遇到狀況可以馬上有頭緒進行 trouble shooting...

Computer, Linux, Murmuring, OS, SoftwareNo Comment

讀書時間：Spectre 的攻擊方式

上次寫了 Meltdown 攻擊的讀書心得 (參考「讀書時間：Meltdown 的攻擊方式」)，結果後來中獎狂流鼻水，加上 Spectre 用的手法就更複雜，慢慢看的情況就拖到最近才看完... 這邊就以讀者看過 Meltdown 那篇心得的前提來描述 Spectre。

Spectre 的精華在於 CPU 支援 branch prediction 與 out-of-order execution，也就是 CPU 遇到 branch 時會學習怎麼跑，這個資訊提供給 out-of-order execution 就可以大幅提昇執行速度。可以參考以前在「CPU Branch Prediction 的成本...」提到的效率問題。

原理的部份可以看這段程式碼：

這類型程式碼常常出現在現代程式的各種安全檢查上：確認 x 沒問題後再實際將資料拉出來處理。而我們可以透過不斷的丟 x 值進去，讓 CPU 學到以為都是 TRUE，而在 CPU 學壞之後，突然丟進超出範圍的 x，產生 branch misprediction，但卻已經因為 out-of-order execution 而讓 CPU 執行過 y = ... 這段指令，進而導致 cache 的內容改變。

然後其中讓人最驚豔的攻擊，就是論文示範了透過瀏覽器的 JavaScript 就能打的讓人不要不要的...

圖片裡，上面這段是 JavaScript 程式碼，下面則是 Chrome V8 在 JIT 後轉成的 assembly (這是 AT&T style)：

可以從這段程式碼看到，他想要透過這段 JavaScript 取出本來無法存取到的祕密值 index，然後透過 probeTable 得知 cache 的變化。

在這樣的攻擊下，你就可以取得這個 process 裡可以看到的空間，甚至極端的 case 下有可能是 kernel space (配合 Meltdown 的條件)。

不過如果你不能跑 JavaScript 也沒關係，Spectre 的論文裡也提供各種變形方式提供攻擊。像是這樣的程式碼也可以被拿來攻擊：

if (false but mispredicts as true)
    read array1[R1]
read [R2]

其中 R1 是有帶有祕密值的 register，當 array[R1] 有 cache 時，讀 [R2] 就有機會比較快，而沒有 cache 時就會比較慢 (這是因為 memory bus 被佔用的關係)，在這個情境下就能夠產生 timing attack：

Suppose register R1 contains a secret value. If the speculatively executed memory read of array1[R1] is a cache hit, then nothing will go on the memory bus and the read from [R2] will initiate quickly. If the read of array1[R1] is a cache miss, then the second read may take longer, resulting in different timing for the victim thread.

所以相同道理，利用乘法器被佔用的 timing attack 也可以產生攻擊：

if (false but mispredicts as true)
    multiply R1, R2
multiply R3, R4

在論文裡面提到相當多的方法 (甚至連 branch target buffers (BTB) 都可以拿來用)，就麻煩去論文裡看了。現在用 cache 算是很有效的方式，所以攻擊手法主要都是透過 cache 在取得資訊。

Spectre 論文提到的 mitigation (workaround) 是透過 mfence 與 lfence 強制程式碼的順序，但這表示 compiler 要針對所有的 branch 加上這段，對效能影響應該蠻明顯的：

In addition, of the three user-mode serializing instructions listed by Intel, only cpuid can be used in normal code, and it destroys many registers. The mfence and lfence (but not sfence) instructions also appear to work, with the added benefit that they do not destroy register contents. Their behavior with respect to speculative execution is not defined, however, so they may not work in all CPUs or system configurations.

Google 推出的 Retpoline 則是想要避免這個問題。Google 在「Retpoline: a software construct for preventing branch-target-injection」這邊詳細說明了 Retpoline 的原理與方法，採取的方向是控制 speculative execution：

However, we may manipulate its generation to control speculative execution while modifying the visible, on-stack value to direct how the branch is actually retired.

這個方式是抽換掉 jmp 與 call 兩個指令，以 *%r11 為例，他將 jmp *%r11 與 call *%r11 改成 jmp retpoline_r11_trampoline 與 call retpoline_r11_trampoline (這邊的 jmp 指的是所有 jump 系列的指令，像是 jz 之類的)：

retpoline_r11_trampoline:
  call set_up_target;
capture_spec:        
  pause;
  jmp capture_spec;
set_up_target:
  mov %r11, (%rsp); 
  ret;

藉由抽換 %rsp 內容跳回正確位置，然後也利用這樣的程式結構控制 CPU 的 speculative execution。

而在效能損失上，已經有測試報告出來了。其實並沒有像 Google 說的那麼無痛，還是會因為應用差異而有不同等級的效能損失... 可以看到有些應用其實還是很痛：「Benchmarking Linux With The Retpoline Patches For Spectre」。

下半年新出的 CPU 應該會考慮這些問題了吧，不過不知道怎麼提供解法 @_@

Computer, Hardware, Murmuring, Programming, Security, SoftwareNo Comment

讀書時間：Meltdown 的攻擊方式

Meltdown 的論文可以在「Meltdown (PDF)」這邊看到。這個漏洞在 Intel 的 CPU 上影響最大，而在 AMD 是不受影響的。其他平台有零星的消息，不過不像 Intel 是這十五年來所有的 CPU 都中獎... (從 Pentium 4 以及之後的所有 CPU)

Meltdown 是基於這些前提，而達到記憶體任意位置的 memory dump：

  • 支援 µOP 方式的 out-of-order execution 以及當失敗時的 rollback 機制。
  • 因為 cache 機制造成的 side channel information leak。
  • 在 out-of-order execution 時對記憶體存取的 permission check 失效。

out-of-order execution 在大學時的計算機組織應該都會提到，不過我印象中當時只講「在確認不相干的指令才會有 out-of-order」。而現代 CPU 做的更深入，包括了兩個部份：

  • 第一個是 µOP 方式，將每個 assembly 拆成更細的 micro-operation，後面的 out-of-order execution 是對 µOP 做。
  • 第二個是可以先執行下去，如果發現搞錯了再 rollback。

像是下面的 access() 理論上不應該被執行到，但現代的 out-of-order execution 會讓 CPU 有機會先跑後面的指令，最後發現不該被執行到後，再將 register 與 memory 的資料 rollback 回來：

而 Meltdown 把後面不應該執行到 code 放上這段程式碼 (這是 Intel syntax assembly)：

其中 mov al, byte [rcx] 應該要做記憶體檢查，確認使用者是否有權限存取那個位置。但這邊因為連記憶體檢查也拆成 µOP 平行跑，而產生 race condition：

Meltdown is some form of race condition between the fetch of a memory address and the corresponding permission check for this address.

而這導致後面這段不該被執行到的程式碼會先讀到資料放進 al register 裡。然後再去存取某個記憶體位置造成某塊記憶體位置被讀到 cache 裡。

造成 cache 內的資料改變後，就可以透過 FLUSH+RELOAD 技巧 (side channel) 而得知這段程式碼讀了哪一塊資料 (參考之前寫的「Meltdown 與 Spectre 都有用到的 FLUSH+RELOAD」)，於是就能夠推出 al 的值...

而 Meltdown 在 mov al, byte [rcx] 這邊之所以可以成立，另外一個需要突破的地方是 [rcx]。這邊 [rcx] 存取時就算沒有權限檢查，在 virtual address 轉成 physical address 時應該會遇到問題？

原因是 Linux 與 OS X 上有 direct-physical map 的機制，會把整塊 physical memory 對應到 virtual memory 的固定位置上，這些位置不會再發給 user space 使用，所以是通的：

On Linux and OS X, this is done via a direct-physical map, i.e., the entire physical memory is directly mapped to a pre-defined virtual address (cf. Figure 2).

而在 Windows 上則是比較複雜，但大部分的 physical memory 都有對應到 kernel address space，而每個 process 裡面也都還是有完整的 kernel address space (只是受到權限控制)，所以 Meltdown 的攻擊仍然有效：

Instead of a direct-physical map, Windows maintains a multiple so-called paged pools, non-paged pools, and the system cache. These pools are virtual memory regions in the kernel address space mapping physical pages to virtual addresses which are either required to remain in the memory (non-paged pool) or can be removed from the memory because a copy is already stored on the disk (paged pool). The system cache further contains mappings of all file-backed pages. Combined, these memory pools will typically map a large fraction of the physical memory into the kernel address space of every process.

這也是 workaround patch「Kernel page-table isolation」的原理 (看名字大概就知道方向了)，藉由將 kernel 與 user 的區塊拆開來打掉 Meltdown 的攻擊途徑。

而 AMD 的硬體則是因為 mov al, byte [rcx] 這邊權限的檢查並沒有放進 out-of-order execution，所以就避開了 Meltdown 攻擊中很重要的一環。

Computer, Hardware, Murmuring, Security, Software1 Comment

Meltdown 與 Spectre 都有用到的 FLUSH+RELOAD

Meltdown 與 Spectre 攻擊裡都有用到的 FLUSH+RELOAD 技巧。這個技巧是出自於 2013 年的「Flush+Reload: a High Resolution, Low Noise, L3 Cache Side-Channel Attack」。當時還因此對 GnuPG 發了一個 CVE-2013-4242。

FLUSH+RELOAD 是希望透過 shared memory & cache 得到 side channel information，藉此突破安全機制。

論文裡面提到兩個攻擊模式，一種是在同一個 OS 裡面 (same-OS)，另外一種是在同一台機器，但是是兩個不同的 VM (cross-VM)。攻擊的前提是要拿到與 GnuPG process 相同的 shared memory。兩個環境的作法都是透過 mmap() GnuPG 的執行檔以取得 shared memory。

在 same-OS 的情況下會使用同一個 process：

To achieve sharing, the spy mmaps the victim’s executable file into the spy’s virtual address space. As the Linux loader maps executable files into the process when executing them, the spy and the victim share the memory image of the mapped file.

在 cross-VM 的情況下會因為 hypervisor 會 dedup 而產生 shared memory：

For the cross-VM scenario we used two different hypervisors: VMware ESXi 5.1 on the HP machine and Centos 6.5 with KVM on the Dell machine. In each hypervisor we created two virtual machines, one for the victim and the other for the spy. The virtual machines run CentOS 6.5 Linux. In this scenario, the spy mmaps a copy of the victim’s executable file. Sharing is achieved through the page de-duplication mechanisms of the hypervisors.

接下來就能夠利用 cache 表演了。基本原理是「存取某一塊記憶體內容，然後計算花了多久取得，就能知道這次存取是從 L1、L2、L3 還是記憶體取得」。所以 FLUSH+RELOAD 就設計了三個步驟：

  • During the first phase, the monitored memory line is flushed from the cache hierarchy.
  • The spy, then, waits to allow the victim time to access the memory line before the third phase.
  • In the third phase, the spy reloads the memory line, measuring the time to load it.

先 flush 掉要觀察的記憶體位置 (用 clflush)，然後等待一小段時間，接著掃記憶體區塊，透過時間得知有哪些被存取過 (就會比較快)。這邊跟 cache 架構有關，你不能想要偷看超過 cache 大小的量 (這樣會被 purge 出去)，所以通常是盯著關鍵的部份就好。

接著是要搞 GnuPG，先看他在使用 RSA private key 計算的程式碼：

而依照這段程式碼挑好位置觀察後，就開始攻擊收資訊。隨著時間變化就可以看到這樣的資訊：

然後可以觀察出執行的順序：

於是就能夠依照執行順序推敲出 RSA key 了，而實際測試的成果是這樣，在一次的 decrypt 或是 sign 就把 RSA key 還原的差不多了 (96.7%)：

We demonstrate the efficacy of the FLUSH+RELOAD attack by using it to extract the private encryption keys from a victim program running GnuPG 1.4.13. We tested the attack both between two unrelated processes in a single operating system and between processes running in separate virtual machines. On average, the attack is able to recover 96.7% of the bits of the secret key by observing a single signature or decryption round.

知道了這個方法後，看 Meltdown 或是 Spectre 才會知道他們用 FLUSH+RELOAD 的原因... (因為在 Meltdown 與 Spectre 裡面就只有帶過去)

Computer, Hardware, Murmuring, Security, Software1 Comment

Etsy 介紹的 Cache Smearing

在 Etsy 的 engineering blog 上提到了他們怎麼設計 cache 機制：「How Etsy caches: hashing, Ketama, and cache smearing」。

使用 consistent hash 已經是基本款了，文章裡花了一些篇幅介紹為什麼要用 consistent hash。

後半段則是有了 consistent hash 後會遇到的問題，也就是講 hot key 怎麼處理：有些資料非常熱 (常常被存取)，就算用 consistent hash 也還是有可能搞爆單一機器。

他們做了幾件事情，第一件事情是設計 cache smearing 機制，把單一資料加上 random key，使得不同的 key 會打散到不同的機器上：

Let’s take an example of a hot key popular_user_data. This key is read often (since the user is popular) and is hashed to pool member 3. Cache smearing appends a random number in a small range (say, [0, 8)) to the key before each read or write. For instance, successive reads might look up popular_user_data3, popular_user_data1, and popular_user_data6. Because the keys are different, they will be hashed to different hosts. One or more may still be on pool member 3, but not all of them will be, sharing the load among the pool.

第二件事情則是監控哪些 key 比較熱門：

We’ve seen this problem many times over the years, using mctop, memkeys, and our distributed tracing tools to track down hot keys.

第三件事情是維護 hot key 的清單 (不是每個 key 都會上 cache smearing)：

We manually add cache smearing to only our hottest keys, leaving keys that are less read-heavy efficiently stored on a single host.

是個當規模大到單一 hot key 會讓單台伺服器撐不住時的 workaround...

Computer, Murmuring, Network, Programming, Service, SoftwareNo Comment

Microsoft 與 GitHub 合作，將會把 GVFS 移植到 Linux 與 Mac 上

Microsoft 與 GitHub 合作將本來只有在 Windows 上可以用的 GVFS 移植到 Linux 與 Mac 上：「Microsoft and GitHub team up to take Git virtual file system to macOS, Linux」。

GVFS 是解決微軟內部自己在用 Git 的痛處，因為微軟的 repository 都... 有... 點... 肥... (畢竟有不少產品發展了很久)。

目前 Git 的操作是卡在 I/O 與 memory cache 的限制上：

Also, Git wasn't designed for a codebase that was so large, either in terms of the number of files and version history for each file, or in terms of sheer size, coming in at more than 300GB. When using standard Git, working with the source repository was unacceptably slow. Common operations (such as checking which files have been modified) would take multiple minutes.

GVFS 的想法是有用到的部份再真的去拉，藉此大幅減少 I/O 需求...

Computer, Murmuring, Network, Programming, Service, SoftwareNo Comment AWS, Cloud, Computer, Database, Murmuring, Network, Service, SoftwareNo Comment AWS, Blog, CDN, Cloud, Computer, Murmuring, Network, Security, Service, WWWNo Comment

Recent Comments

Archives

Blogroll