cacheの基礎と攻撃、randomized cache architecture

TL;DR

IEEE S&P 2021に採択されたランダム化を利用してサイドチャネル攻撃に対抗するcacheアーキテクチャに関する分析論文

cacheの基礎およびcacheに対するサイドチャネル攻撃を整理

本論文では攻撃をより効率的に行うPRIME + PRUNE + PROBE攻撃も提案されている

はじめに

体系的な分析を行っているため定式的な議論が主だった本論であるが、ここではその前提となるcacheの基礎や攻撃手法の分類を整理したい。

cacheの基礎

階層化されたメモリアーキテクチャには容量と速度のトレードオフが存在し、cacheはメモリアクセスの空間・時間局所性を利用してレイテンシ削減を実現する。cache上のアドレスへアクセスするためには、当該アドレスがcacheのどこに存在するのかを知る必要がある。この探索のため、アドレスと格納位置がマッピングされており、以下3つの方式が存在する。

directly mapped cache

各メモリアドレスはcache lineを1つだけ保持する

Fig. 2のようにアドレスにはindexとtagがあり、indexによってcache上の位置が決定される

tagはcacheにあるアドレスが当該アドレスかどうか区別するために使用する

fully-associative

メモリアドレスを任意のcache lineに保持可能

set-associative

メモリアドレスをcache lineの固定されたサブセットに保持する

1つのサブセットには複数のcache-lineが保持できる

このサブセットをwayと呼び、4つのcache-lineを保持できるものを4-way set associativeと言う

4-wayの場合、tagは4つとも探索する必要がある

https://gyazo.com/1df7a0732d3dd306fdd002c4824cb517

（論文中より引用）

現実のcacheのサイズは限られているため、あるアドレスが同じcache setに割り当てられるcache contentionが発生する。

cacheへの攻撃

前述の通り、cacheは時間・空間局所性によりメモリアクセスの遅延を削減するが、実行時間測定によるサイドチャネル攻撃が存在している。

FLUSH + RELOAD

アドレスをcacheからflushしてから待機する

一定時間後、reloadすることでそのアドレスに被害者がアクセスしたか判断

攻撃者と被害者でメモリが共有されている必要がある

PRIME + PROBE

全cacheからcache lineをflushする

メモリアクセスの待ち時間ではなくcache contentionを測定

cache setを埋め（PRIME）、その所要時間を測定（PROBE）

そのcache setに被害者がアクセスしている場合、PRIMEに要する時間が長くなる

攻撃にはアドレスのcache lineへのマッピングを知っている必要がある

攻撃者と被害者でメモリが共有されている必要はない

最近の研究ではLLCも対象

EVICT + RELOAD

cache contentionを利用

攻撃者と被害者でメモリが共有されている必要がある

なお本論文ではPRIME + PRUNE + PROBE攻撃を提案しており、攻撃に必要なeviction setの効率的な構築方法や最適化手法を提案し、10^30以上必要だったアクセス数を10^7にできるとしている。

randomized cache architectureによる対策

アドレスからindexへのマッピングを、決定的ではあるがランダムに見えるように置き換えることで攻撃を緩和する。元々はlookup tableを想定されていたたが、最近ではハードウェア上でマッピングをランダム化するため、妥当なオーバヘッドでevictionベースのcache攻撃を阻止できる。

https://gyazo.com/814c35fe38cbffbf9ca29894dde6a213

なおeviction set構築アルゴリズムが発展し、メモリアドレスをランダム化するだけでは保護が難しくなってきている。

最後に

References

コンピュータの構成と設計 第5版 下, デイビッド・A・パターソン,ジョン・Ｌ・ヘネシー(著）,成田 光彰　訳, 日経BP, 2014.