# 論文紹介 Cache Audit 前半
CacheAudit[TISSEC'15]
## 1.概要
キャッシュサイドチャネルによりLeakし得る情報量に対し、信頼できる上限を与える自動的な静的解析
~~**Cache** + **Au**tomatic + Cre**dit** ?~~
Audit=監査という単語があったらしい
### 対象
実行可能形式(x86バイナリ)
ただし、Indirect Jumpをもつようなバイナリは対象外
### 目標
キャッシュサイドチャネルによってLeakし得る情報量の上限を与える
- Ex. 256bit鍵の暗号化アルゴリズムに対し、キャッシュサイドチャネルの適用を考える
- 6bit以下のLeak → (確率的に)破られる心配はない
- 250bit以上の強度は保証される
- 128bit以下のLeak → 暗号の強度は低い「かも」
- 実際にLeakする量を与えるわけでない
- 128bit以上という程度でしか強度を保証できない
### 手法
- 抽象解釈
- Cacheの動作を考慮したSemanticsを定義
- 攻撃者から観測可能な結果の組み合わせ数の上界を求める
## 2.Background
### Cache
CPUとメインメモリとの間のレイテンシを埋めるためのアーキテクチャ([SP'19](https://ieeexplore.ieee.org/document/8835261))
メインメモリのアクセスは数千サイクルほど消費するのでできるだけ避けたい
#### Memory Hierarchy
- 最近のキャッシュは多段構造をもつ
- L1/L2は各コアに搭載され、L3は全てのコアで共有される
- マルチコアではCache Coherencyの問題もある([IBM](https://www.ibm.com/docs/en/aix/7.2?topic=architecture-cache-coherency))
- False Sharingによる性能低下
- 一般に階層間には包含関係がある
- (L1の内容)$\subset$(L2の内容)$\subset$(L3の内容)
- Size(m1mac)
- LineSize 128B
- Performance Core [(Level0)](https://developer.apple.com/documentation/kernel/1387446-sysctlbyname/determining_system_capabilities)
- L1 ICache: 192KB
- L1 DCache: 128KB
- L2 Cache : 12MB
- Efficient Core (level1)
- L1 ICache: 128KB
- L1 DCache: 64KB
- L2 Cache: 4MB
- No L3 Cache
- Main Memory: 16GB
- Storage: 1TB SSD
<img src=https://i.imgur.com/9c51yd4.png width=400mm>
キャッシュ・メモリ周りのアーキテクチャ模式図
#### Cache Structure
キャッシュを効率よく管理するための仕組み
32bitアドレス空間におけるキャッシュモデル
以下は$n$ビットアドレス空間での一般化
- メモリは$2^l$バイトごとに区切られ、この単位を「Block」と呼ぶ
- CacheにはBlockごとに格納され、この単位を「Line」と呼ぶ
- アドレスの最下位$l$ビットがBlock内でのOffsetに相当する
- 下位$c+l$ビットから$l+1$ビットがCache Setを特定するindexビットとなる
- すなわち、Cache Setの個数は$2^c$個である
- 1つのCache Setあたりのライン数$k$をAssociativityと呼ぶ
- 残りの上位$n-c-l$ビットがTagとなり、Cache Set内での検索に使われる
:::info
$k=1$のときダイレクトマップ方式
$c=0$のときフルアソシアティブ方式
それ以外をセットアソシアティブ方式と呼ぶ
:::
<img src=https://i.imgur.com/xZbgnbp.png width=200mm>
- 上のモデルで0xdeadbeb1を検索
1. index 0x<span style='color:blue'>eb</span> Cache Setを特定
2. Tag 0x<span style='color:red'>deadb</span>をもつラインがあるか、Set内を全探索
- あればHit、なければMiss
3. Line内のOffset 0x<span style='color:green'>1</span> 番目のバイトが目的のValueである
##### Cache Sizeはいくらになるか？
(Cache Setの個数) $\times$ (Associativity)$\times$(1ライン当たりのByte)
$2^{l+c} \times k$
#### Replacement Policy
Cache Missを起こしたときにどのラインを入れ替えるか
近い将来最も使いそうにないブロックを上書きするのが最良である([SIGRARCH'10](https://people.csail.mit.edu/emer/papers/2010.06.isca.rrip.pdf))
代表的なアルゴリズム
- LRU (Least Recently Used)
- 最近一番使われてないやつを抜く
- モデルとしては単純だが、実装コストがAssociativityに応じて高くなる
- FIFO (First In First Out)
- 最も古くからいるものを抜く
- 実装コストは低い
- PLRU（Pseudo LRU）
- 各ラインにフラグビットを用意
- 直感的には0がRecently Used・1がNot Recently Usedを表す
- Miss発生時のアルゴリズム
1. フラグが1のラインがなければ、全てのラインのフラグを1にする
2. フラグが1のラインから1つ選んでEvictする（どれでもいい）
3. 新しいラインのフラグは0にする
- Hitしたらそのラインのフラグは0にする
- これを$m$ビットに拡張したものがSRRIP([SIGRARCH'10](https://people.csail.mit.edu/emer/papers/2010.06.isca.rrip.pdf))
##### PLRUアルゴリズム
### Cache Side Channel Attack
大きく3つの手法に分類できる
1. Time-based
攻撃対象の全体の実行時間を観測
実行時間はメモリアクセスの回数に大きく依存するという観察から
2. Access-based
攻撃対象のキャッシュの状態を観測
- どのキャッシュラインを使ったか、を見れる
攻撃者と対象が同じハードウェアを共有する状況で発生
3. Trace-based
攻撃対象のキャッシュのhit/missの動きを観測
消費電力などから観測でき、組み込みシステムに関連
## Leakage Example
### Bubble Sort
```clike=
void BubbleSort(int a[], int n) {
int i,j,tmp;
for(i=0;i<n-1;i++){
for(j=0;j<n-1;j++){
if(a[j] > a[j+1]){
tmp = a[j+1];
a[j+1] = a[j];
a[j] = tmp;
}
}
}
}
```
- 配列aの中身（の順番）をSecretとする
- 攻撃者は、元の配列の順序を推定するのが目標
- 実行Pathが特定できると、元の順序が復元可能
- if文の評価は必ず$\frac{n(n-1)}{2}$回実行される
### 攻撃者が観測可能な情報
投機実行とかスーパースカラとかModernCPUの機能の話は一旦忘れる
1. Time-based
何回if文の中身が実行されたのか推定できる
- $\frac{n(n-1)}{2}+1$通りのPathを区別できる
2. Access-based
ソート実行後のキャッシュの状態を推定できる
- Data Cacheは一意
3. Trace-based
hit/missの列から、どこでif文の中身が実行されたのか推定できる
- 列の長さからif文の実行回数が分かる
- 同じ長さの列でも、hit/missの位置でPathを識別できる
- $2^{\frac{n(n-1)}{2}}$通りのPathを識別可能（実際には高々$n!$通りしかない）
### 確率的な推定
$n=32$のとき、元配列の順序は$32!$通り考えられる
→当てずっぽうだと、$\frac{1}{32!}$の確率で当たる
- time baesd → 確率$(\frac{32\cdot 31}{2} +1 )\div 32! = \frac{497}{32!}$で当てられる
- (論文だと$\frac{993}{32!}$になってるけどミス？)
- access based → 当てずっぽうと同じ
- trace based → 確率1で当てられる
攻撃者から観測可能な状態が多い
＝実際に観測された状態から情報を引き出せる確率が上がる
## 3.Formalize(Concrete Semantics)
### Cache
メモリブロックの集合を$\mathcal{B}$とする
キャッシュセットの集合を $\mathcal{S}$とする
それぞれのブロックは以下の関数$set$を用いて特定のブロックにマッピングされる
$$
set:\mathcal{B}\rightarrow\mathcal{S}
$$
### Programs and Computation
プログラム$P$は、以下の5つの要素の組$(\Sigma,I,F,\mathcal{E},\mathcal{T})$から成るグラフ
（有限オートマトン$<\mathcal{E},\Sigma,I,\mathcal{T},F>$？）
- $\Sigma$: 有限の状態集合
- $I\subset\Sigma$：初期状態集合
- $F\subset\Sigma$：受理状態集合
- $\mathcal{E}$ : event集合
- $\mathcal{T}\subseteq\Sigma\times\mathcal{E}\times\Sigma$: 遷移関係
#### Computation
初期状態$\sigma_0\in I$から始まる$P$上のWalkのこと
具体的には、状態とeventの列
$\sigma_0 e_0 \sigma_1 e_1...\sigma_n(\sigma_0\in I\land(\sigma_k,e_k,\sigma_{k+1})\in \mathcal{T})$
#### Traces
状態とeventの列の集合全体
$$
Traces:\Sigma \times (\Sigma\times\mathcal{E})^*\\
Traces=\{\sigma_0e_0\sigma_1...\sigma_n\ |\ n < \infty\ \land\ (\sigma_k,e_k,\sigma_{k+1})\in \mathcal{T})\}
$$
#### Collecting Semantics
Pが起こし得るComputationの集合
$Col(P)\subseteq Traces$で表す
$$
Col(P) = I \cup next(I)\cup next^2(I)...
$$
:::success
すなわち、$Col(P)$は次の関数$F$の最小不動点
$$
F(X) = I \cup next(X)
$$
:::
ただし、$next:Traces\rightarrow Traces$は1-Computation Stepで、
$$
next(S) = \{t.\sigma_n e_n \sigma_{n+1}|t.\sigma_n \in S \land (\sigma_n e_n \sigma_{n+1})\in \mathcal{T}\}
$$
### Cache Update and Effect
Cache awareなSemanticsが欲しい
Program Stateはメモリ状態とキャッシュ状態からなる
$$
\Sigma = \mathcal{M}\times\mathcal{C}\\
m \in \mathcal{M} : \mathcal{A} \rightarrow V\\
c \in \mathcal{C} : \mathcal{B} \rightarrow A
$$
- メモリはアドレス・レジスタから値への写像
- これはコード領域・プログラムカウンタも含む
- キャッシュはブロックからAgeへの写像
#### メモリ状態の遷移
直感的にはstep実行と同義
$upd_\mathcal{M}:\mathcal{M}\rightarrow\mathcal{M}$
#### メモリEffect
アクセスされるメモリブロックを返す関数
$eff_\mathcal{M}:\mathcal{M}\rightarrow \mathcal{E}_\mathcal{M}$
- ただし$\mathcal{E}_\mathcal{M}=\mathcal{B} \cup \{\perp\}$
#### キャッシュ状態
各メモリブロック$\mathcal{B}$に$age \in
A= \{0,1,...,k-1,k\}$を割り当てるmappingの集合
$$
\mathcal{C}=\{c\in\mathcal{B}\rightarrow A \\
|\forall a,b\in \mathcal{B}\text{ s.t. } a \neq b,\\
set(a)=set(b) \implies (c(a)\neq c(b) \lor c(a)=c(b)=k)
\\\}
$$
:::info
定義の条件部分の直感的理解
$s\in\mathcal{S}$に対し、$\{c(b)\ |\ b\in\mathcal{B} \land set(b) =s\}$は$s$に割り当てられるブロックの集合の年ageの多重集合(重複を許可)
この集合内に$0,...,k-1$は高々1つしかない
:::
$c\in\mathcal{C},b\in\mathcal{B}$に対して、
- $c(b) < k$：ブロック$b$はキャッシュに存在
- $c(b) = k$：ブロック$b$はキャッシュにない(Evicted)
#### キャッシュ状態の遷移
キャッシュ状態はメモリEffectによって新たなキャッシュ状態に変わる
$upd_\mathcal{C}:\mathcal{C}\times\mathcal{E}_\mathcal{M} \rightarrow \mathcal{C}$
<details><summary>形式的定義</summary>
$$
upd_\mathcal{C}(c,b) :=\lambda b'\in \mathcal{B}.\left\{
\begin{array}{cll}
\\c(b') & set(b') \neq set(b)
\\c(b') & set(b') = set(b) \land b' \neq b \land c(b') = k
\\0 & set(b') = set(b) \land b' = b \land c(b') = k
\\c(b') + 1 & set(b') = set(b) \land b' \neq b \land c(b') <k \land c(b) = k
\\ \Pi_{c(b)} c(b') & set(b') = set(b) \land c(b') < k \land c(b) < k
\end{array}
\right.
$$
</details>
:::info
2つのブロック間の関係に以下の略記を使う
- ds = Different Set
- ss = Same Set
- db = Different Block
- sb = Same Block
:::
$$
upd_\mathcal{C}(c,b) :=\lambda b'\in \mathcal{B}.\left\{
\begin{array}{cll}
& \text{relation} & b' \text{ state} & b\text{ state}
\\c(b') & \text{ds}
\\c(b') & \text{ss,db} & \text{evicted}
\\0 &\text{sb}
\\c(b') + 1 & \text{ss,db} & \text{cached} & \text{evicted}
\\\Pi_{c(b)} c(b') & \text{ss} & \text{cached} & \text{cached}
\end{array}
\right.
$$
1. 違うSetなのでageは変わらない
2. 同じSetだが既にEvictされているので変わらない
3. 今まさにアクセスされたブロックなのでageが0になる
4. 同じSetで既にキャッシュ内、入れ替えが起こったのでズレる
5. 同じSetでアクセスされたブロックもキャッシュ内にあるので、Replacement Policyに従って並べ替え
:::info
要するに$b'$を変数とする関数を返す($\mathcal{C}$がMappingの集合であることに注意)
:::
#### キャッシュEffect
キャッシュhit/missを定式化
$$
eff_\mathcal{C}(c,b) = \left\{\array{\perp& b=\perp\\hit&c(b)<k\\miss & otherwise}\right.
$$
#### 遷移関係
$\mathcal{E}=\{hit,miss,\perp\}$とすると、
$\mathcal{T}\subset(\mathcal{M\times\mathcal{C}})\times \mathcal{E} \times (\mathcal{M\times\mathcal{C}})$は次のように定義できる
$$
\mathcal{T} = \{((m_1,c_1),e,(m_2,c_2))
\\| m_2=upd_\mathcal{M}(m_1)
\\\land c_2=upd_\mathcal{C}(c_1,eff_\mathcal{M}(m_1))
\\\land e=eff_\mathcal{C}(c_1,eff_\mathcal{M}(m_1))
\\
\}
$$
要するに、状態遷移のEdgeに対してキャッシュhit/miss(or None)を表す記号を加える
### SideChannel
プログラム$P$の初期状態$I$を入力の集合として捉える
- 各$i\in I$に対して、Computeを行うと、実行$\sigma_0e_0...\sigma_n$が**決定的に**得られる
$P:I\rightarrow Col$というmappingと解釈できる
- 攻撃者は$trace \in Col$から特定の情報を観測できる
- これを$view:Col\rightarrow O$で表す
- これらの合成$C=(view\circ P):I\rightarrow O$は、初期状態からPのExecutionによって攻撃者が観測する情報を表す
- $|range(C)|$は、観測できる結果の大きさである
- これが大きいと、攻撃者はより高い精度で元の入力を絞れる
#### Access-based
$$
view^{acc}=(m_0,c_0)e_0(m_1,c_1)...(m_n,c_n)\mapsto c_n
$$
最終的なキャッシュ状態を観測できる
#### Trace-based
$$
view^{tr}=\sigma_0 e_0 \sigma_1 e_1...\sigma_n \mapsto e_0 e_1...e_{n-1}
$$
hit/missのトレースを観測できる
#### Time-based
$$
view^{time}=\sigma_0 e_0 \sigma_1 e_1...\sigma_n \mapsto t_{hit}|\{i|e_i=hit\}| + t_{miss}|\{i|e_i=miss\}| + t_\perp|\{i|e_i=\perp\}|
$$
全体の実行時間を観測できる
### Quantify SideChannel
Secret Inputを確率変数$X\in I$とする
攻撃者はこの$X$を高い確率で推定することが目標
#### 定式化
- 攻撃者のもつ確率変数$\hat{X}$に対し$P(\hat{X}=X)$を最大化する
#### 攻撃者が何の情報ももたないとき
$$
P(\hat{X}=X) \leq \mathrm{max}_{\sigma \in I} P(X=\sigma)
$$
最も出やすい値が事前にわかっているならば、その値を答えるのが一番
#### 攻撃者が$C(X)$を観測したとき
$$
P(\hat{X}=X) \leq \mathrm{max}_{\sigma \in I} P(X=\sigma) \cdot |range(C)|
$$
- 大雑把に言うと、$I$を$|range(C)|$種類に識別できるから
#### 問題
60面サイコロを振ったとき出た値を表す確率変数を$X$とする。
以下の条件のとき、$X$を当てられる確率を答えてください。
##### (1) 何も情報がない
<details><summary>答え</summary>
- 値：$\frac{1}{60}$
- 理由：$1,...,60$のいずれも等確率であり得るから。
</details>
##### (2) 和が10で割り切れると教えられた
<details><summary>答え</summary>
- 値：$\frac{1}{6}$
- 理由：候補が$10,20,30,40,50,60$のいずれかになるから。
</details>
##### 結論
10で割ったあまりを観測できると、解候補を10組に分割できるので、当てられる確率が10倍になる。
これは一様分布での話だが、一様でなくても確率を上から抑えることは可能
### Extend to Leakage Bits
超ざっくり言うと$\log_2 |range(C)|$がLeaked Bit
- $|range(C)|=8$のとき、3bit分の情報量が落ちる
- 具体的に3bitが判明する、という意味ではない
形式的には、エントロピーの考え方を用いる
（かなり理解あやふやですが・・・）
##### 情報エントロピー
事象$A$が起こる確率が$P(A)$のとき、$E$が起こったときに得られる自己エントロピー$H(E)$は以下で表される。
$$
H(A) = -\log_2 P(A)
$$
低確率の事象の方が起こった時の情報エントロピーが大きい。
確率変数$X$が確率分布$P$に従うとき、$H(X=x)$の期待値をエントロピーと呼び、$H(X)$と表す。
$$
H(X) = \sum_{x\in X} P(X=x)H(X=x)
$$
#### 例
16bit鍵を表す確率変数$X$のエントロピーを考える。
##### 観測がないとき
攻撃者から見て、鍵$x$が出る確率は$P(X=x) = \frac{1}{2^{16}}$
「鍵$x$が出る」のエントロピーは
$$
-\log_2 P(X=x) = 16 \text{ bit}
$$
鍵$X$の平均エントロピーは、
$$
\sum_{x \in dom(X)} P(X=x) \times (- \log_2 P(X=x)) = 16 \text{ bit}
$$
##### 観測があるとき
攻撃者が$C(X)=c$を観測できるとする。
ただし、$C$は何らかのハッシュ関数で、$X$を均等に8等分して値$c_0,...,c_7$のいずれかを返す。
すると、鍵$x$が出る条件付き確率は
$$
P(X=x|C(X)=c) = \left\{
\begin{array}{ll}
\frac{8}{2^{16}} & \text{if } C(x) = c\\
0 & \text{otherwise}
\end{array}\right.
$$
になる。
また、「鍵$x$が出る」のエントロピーは
$$
-\log_2 P(X=x|C(X)=c) = \left\{
\begin{array}{ll}
13 \text{ bit} & \text{if } C(x) = c\\
\infty & \text{otherwise}
\end{array}\right.
$$
よって、$C(X)=c$が観測されるときの鍵$X$のエントロピーは、
$$
\begin{align}
\sum_{x \in dom(X)} P(X=x|C(X)=c) \times (- \log_2 P(X=x|C(X)=c) &= \frac{2^{16}}{8} \times \frac{8}{2^{16}}\times 13 + (2^{16} \times \frac{7}{8}) \times 0 \times \infty
\\&= 13 \text{ bit}\end{align}
$$
すなわち、攻撃者が$C(X)$を観測できることによって、鍵のエントロピー（＝強度）が低下する。
このエントロピー低下の差分が「Leaked Bit」と呼ばれる。
## Concrete Semanticsのまとめ
- プログラム$P$とは、次で定義されるオートマトンである
- $P=<\mathcal{E},\Sigma,I,F,\mathcal{T}>$
- $\Sigma = \mathcal{M}\times\mathcal{C}$
- $\mathcal{E}=\{hit,miss,\perp\}$
- オートマトン上のPathをComputationと呼ぶ
- Computation全体は$Traces \subseteq \Sigma\times(\mathcal{E} \times \Sigma)^*$
- collection Semantics $Col(P)$は初期状態からのComputationの集合
- 初期状態からあり得る全ての実行パスを網羅
- 次の関数$F$の最小不動点である
- $F(X) = I\ \cup \ next(X)$
- ただし、$next:Traces\ \rightarrow Traces$はone-computation step
- 遷移関係$\mathcal{T}$は$upd_{\mathcal{M}},eff_{\mathcal{M}},upd_{\mathcal{C}},eff_{\mathcal{C}}$から定義される
- 攻撃者は$C=(view\circ P):I\rightarrow O$という写像で情報を観測できると捉えられる
- $|range(C)|$とは攻撃者が観測できるパターン数である
- $\log_2|range(C)|$がLeaked bitである
- $|range(C)|$を上から抑えられれば、Leaked bitの上界が得られる
Sign in with Wallet
Connect another wallet