ISCA 2021の"Zero Inclusion Victim: Isolating Core Caches from Inclusive Last-level Cache Evictions"を読む

何となくマイクロアーキテクチャの論文を読みたくなったのでISCAの論文から選んで読んでみている。メモがてらブログにサマライズを書いていく。 2回目。もう少し提案手法を読み解いていく。

ieeexplore.ieee.org

図2はInclusive Victimsの数を正規化したものを示す。I-LRUの256kB L2キャッシュのものをベースに正規化している。

IMINポリシーは、L1キャッシュへの将来のグローバルアクセスストリームに関して予測を行ってリプレースを行っている。将来最も遠く再利用されるブロックをリプレースしている。

キャッシュのサイズが同一であれば、I-LRUに対してHawkeyeとMINはより多くのInclusive Victimsが発生していることが分かる。マットも最近アクセスされたブロックは、プライベートキャッシュに常駐している可能性が高く、Inclusive Victimsの発生につながる可能性がある。

Hawkeyeにおいても、MINと同様の挙動が見られ、最適な動作に近づこうとするLLCの置換ポリシ―によって、大量のInclusive Victimsが発生することにつながる。また、L2キャッシュの容量が大きくなると、Inclusive Victimsの数が大きくなっていることが分かる。

f:id:msyksphinz:20220405000346p:plain — 図は本論文より引用

また、性能の問題とは別に、Inclusive Victimsは、LLCの掃き出しに基づくクロスコアタイミングサイドチャネル攻撃の成功確率を高めるために使用することができるという研究成果がある。

[10]: D. Gruss, et al. Cache Template Attacks: Automating Attacks on Inclusive Last-level Caches. In USENIX Security, 2015.
[11]: D. Gullasch, at al. Cache Games — Bringing Access-based Cache Attacks on AES to Practice. In Security & Privacy, 2011.
[16]: G. Irazoqui, T. Eisenbarth, and B. Sunar. S$A: A Shared Cache Attack that Works Across Cores and Deﬁes VM Sandboxing — and its Application to AES. In Security & Privacy, 2015.
[23]: M. Kayaalp, et al. A High-resolution Side-channel Attack on Last-level Cache. In DAC, 2016.
[29]: M. Lipp, et al. ARMageddon: Last-level Cache Attacks on Mobile Devices. In USENIX Security, 2016.
[30] F. Liu, et al. Last-level Cache Side-Channel Attacks are Practical. In Security & Privacy, 2015.
[38] Y. Oren, et al. The Spy in the Sandbox: Practical Cache Attacks in JavaScript and their Implications. In CCS, 2015.
[39] D. A. Osvik, A. Shamir, and E. Tromer. Cache Attacks and Countermeasures: The Case of AES. In Proceedings of the Cryptographers’ Track at the RSA Conference on Topics in Cryptology, 2006.
[44] T. Ristenpart, et al. Hey, You, Get Off of My Cloud: Exploring Information Leakage in Third-party Compute Clouds. In CCS, 2009.
[51] W. Song and P. Liu. Dynamically Finding Minimal Eviction Sets Can Be Quicker Than You Think for Side-Channel Attacks against the LLC. In USENIX RAID, 2019.
[54] P. Vila, B. Kopf, and J. F. Morales. Theory and Practice of Finding Eviction Sets. In Security & Privacy, 2019.
[62] Y. Yarom and K. Falkner. FLUSH+RELOAD: A High Resolution, Low Noise, L3 Cache Side-channel Attack. In USENIX Security, 2014.
[65] Y. Zhang, et al. Cross-tenant Side-channel Attacks in PaaS Clouds. In CCS, 2014.

B. 本研究の貢献とスケッチ

本論文では、Inclusive Victimsの存在しないInclusiveキャッシュ階層の設計である。Inclusive Victimsを一切生成しないInclusive LLC(Zero Inclusion Victims(VIV) LLC)を設計する。

この問題の本質は、Inclusive Victimsを選択するセットIndex関数を使ってLLC Victimsを見つける必要があるということである。ZIV LLCはInclusive Victimsが発生しないように、必要な時だけグローバルなLLC交換ポリシーを効率的かつ最小にすることである。

3. ZIV LLCの設計

本節では、ZIV LLCの詳細設計を紹介する。

ベースラインキャッシュ階層について述べる
設計提案のハイレベルな説明を行う
ZIV LLC の 3 つの主要な構成要素について詳細に説明する．

A. ベースライン CMP キャッシュ階層

評価対象となるキャッシュ階層では、共有のInclusiveなLLCとコア毎のプライベートキャッシュを持っているものとする。LLCはバンク化されており、プライベートキャッシュはMESIコヒーレンスプロトコルを用いている。面積効率のため、コヒーレンスディレクトリ構造はスパースディレクトリとしてLLCから切り離されている。スパースディレクトリの各エントリは、全コアのプライベートキャッシュの最終レベルのタグ数の2倍の大きさになっている。プライベートキャッシュのデータEvictionは、常にホームのスパースディレクトリに通知される。ブロックがDirtyでありライトバックを生成する場合を除き、Evictionはデータなしのメッセージである。

B. ZIV LLCの設計概要

セットアソシアティブキャッシュの設計方法により、LLC実装時にInclusive Victimsが発生する。LLCのブロックBを埋めるとき、BがマップするLLCセットから置き換えの候補を選ぶ必要がある。ZIV LLCでは、LLC内のブロックにおいてプライベートキャッシュに存在しないブロックが少なくとも一つ存在するというものを利用している。そして、この仮定では、Inclusiveキャッシュの上位階層であるプライベートキャッシュの容量がLLCよりも小さくなければならないということに基づいている。

そして、プライベートキャッシュに存在しないLLCブロックを置換することが可能であれば、キャッシュ化し王ではInclusive Victimsから解放されることができる。

図5は、ZIV LLCの機能階層の示したものである。