Comments
Description
Transcript
プログラムの振る舞い秘匿のための 動的アドレス変換
卒業論文
プログラムの振る舞い秘匿のための
動的アドレス変換
平成 17 年 2 月 9 日提出
指導教員 坂井修一 教授
電子情報工学科
30382 清水 一人
概要
近年、コンピュータが用いられる場面は急激に増えており、それとともにセキュリティに対する意
識が高まっている。
悪意のある攻撃者の侵入を防いだり、他人に知られたくない情報を盗み見られてしまうのを防い
だり、といった管理者にとって外部の人間からの攻撃に対するものだけではなく、管理者自身や内
部のユーザが悪意を持っている場合、あるいは任意の人間が直接ハードウェアに手を加えることの
できる場合にも安全にプログラムが実行され、かつプログラムの内容が秘匿できることが求められ
ている。
そこで注目されているのがセキュアプロセッサである。これはプロセッサ以外のハードウェア
や Operating System(OS) が信頼できない状態であってもプログラムがプロセッサを認証し、また、
データを暗号化することによって安全に、秘匿した状態でプログラムを実行することができるとい
うものである。
セキュアプロセッサを用いることでプロセッサ・メモリ間のデータバスは暗号化されて通信が行
われるが、一方でアドレスバスは秘匿されていない。アドレスバスを監視することでプログラムの
挙動を把握できてしまうという危険性が残されている。
そこで本研究では、プロセッサからメモリにデータを書き出すときに読み込み元のアドレスでは
なく、リクエストごとに異なる場所に書き込み、その対応をプロセッサが管理するという手法を提
案し、メモリアクセスの局所性をとらえることが困難になることを示した。
また、アドレスの対応を階層化して管理し、一部をプロセッサ内部にキャッシュとして持つこと
でプロセッサによる管理を現実的なものとし、この手法による速度低下やメモリ使用量の増加が平
均で数%程度に抑えられることを示した。
i
目次
第 1 章 はじめに
1.1
1.2
1.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
研究の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
研究の背景
第 2 章 関連研究
2.1
2.2
ソフトウェアによるプログラム保護 . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1
2.2.2
2.2.3
2.3
. .
XOM . . . . . . .
L-MSP . . . . . .
AEGIS . . . . . .
セキュアプロセッサ
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
アドレスバスの情報秘匿 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1
2.3.2
Oblivious RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HIDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 3 章 通常のプロセッサにおけるプログラムの動作
3.1
3.2
3.3
動作の概要と弱点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
弱点への対策 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
プログラムのアドレスバスにおける特徴 . . . . . . . . . . . . . . . . . . . . . . .
第 4 章 プログラム挙動の秘匿手法
4.1
4.2
4.3
. . . . .
提案手法概要 . . . . . . . . .
構造詳細 . . . . . . . . . . . .
4.3.1 アドレス変換テーブル
3
3
3
4
4
5
5
5
5
6
6
6
7
10
.
.
.
.
10
10
10
10
アドレス変換ツリー . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
12
12
アドレスの動的変換
4.3.2
4.3.3
4.3.4
1
1
1
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
アドレス変換キャッシュ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
空き領域アドレス . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4
動作詳細 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5
4.4.1 メモリからキャッシュへの読み込み . . . . . . .
4.4.2 L2 キャッシュからメモリへの書き込み . . . . .
4.4.3 アドレス変換キャッシュからメモリへの書き込み
マルチタスク環境における外部構成 . . . . . . . . . . .
.
.
.
.
13
13
14
15
15
4.6
提案手法のまとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
ii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
第 5 章 評価
5.1
5.2
メモリアクセスの局所性 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
19
19
19
20
5.2.3 速度低下 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.4 メモリ使用量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
評価のまとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
21
21
評価環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1
5.2.2
5.3
メモリアクセス回数の分散 . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 6 章 おわりに
6.1
6.2
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
今後の課題
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
23
23
23
第 1 章 はじめに
1.1
研究の背景
今日の情報化社会においてプログラムはあらゆる場面で用いられるようになり、そこでは様々な
データを扱っている。その中には他者に知られたくないものも存在し、必要に応じたセキュリティ
が求められている。一方でプログラムの実行環境は多岐にわたり、信頼できる環境下で実行される
ということが保証できない状態にある。
悪意を持ったユーザがプログラムから情報を盗もうとした場合、2 種類の攻撃方法が考えられる。
まず 1 つめは、OS を改変することによって通常ではユーザが取得しえない情報を得る、という方
法である。これは Linux などでのオープンソースな OS では特に容易であり、改変によって OS は
信頼できるものではなくなる。2 つめは、ハードウェアに直接手を加えるという方法である。ハー
ドウェアに手を加えることでソフトウェア的な方法では取得できない情報までもが取得可能にな
り、メモリなど、プロセッサ以外のハードウェアは信頼できるものではなくなってしまう。
このような OS やハードウェアが信頼できない状況下ではプログラムは解析されやすく、たとえ
ば著作権保護の機能を持ったプログラムやグリッドコンピューティングなどのプログラムを実行す
る環境を持つ人間にデータやそのプログラムの挙動を知られたくない場合には、ハードウェアレベ
ルでの対策が必要であると考えられる。
この対策として、セキュアプロセッサというものが研究されている。まず、プロセッサの外側で
扱うデータには暗号化を施し、内側はアクセス保護をすることで直接データを読み取ることを不可
能にする。さらに、非対称鍵暗号を用いてプロセッサの認証を行うことで実行環境を暗号機能のつ
いた特定のチップに限ることができ、これらを用いて、内容を知られたくないプログラムを暗号化
した状態で配布することを可能にする。
1.2
研究の目的
上記の技術を用いることで、データの暗号化は確かに可能となる。しかし、データが暗号化され
ていてもアドレスバスは通常のアクセスと同じように扱われているため、これらの従来手法だけで
はアドレスバスをハードウェア的に監視することによってメモリ領域のアクセス頻度などからプロ
グラムの挙動を推測、解析されてしまうという危険性が残されている。
本研究は、この危険性を解消するためにプロセッサの内部でプログラムの使用するメモリアドレ
スを管理し、メモリへの書き込みリクエストのたびに異なる場所へ書き込みを行うことでプログラ
ムの振る舞いが解析されるのを防ぐことを目的とする。
1
1.3
本論文の構成
第 2 章で現在までに行われているプログラム解析に対する関連研究の概要を述べ、それらの手法
の長所と短所について考察する。第 3 章では通常のプロセッサを用いてプログラムを動作させた場
合にアドレスバスを監視して得られる情報とその特徴を述べ、第 4 章でこれを無効にするための本
研究での手法を提案する。第 5 章でシミュレータによる提案手法の評価を行い、そして最後に第 6
章でまとめと今後の課題について述べる。
2
第 2 章 関連研究
2.1
ソフトウェアによるプログラム保護
ハードウェアに手を加えずにデータを保護する方法としてソフトウェアでの実装によるメモリ保
護があげられる。稲村らは、OS のカーネルに手を加えることによりメモリ領域を保護する方法と
して暗号化メモリシステムを提案している [1]。この方式は、プロセスが切り替わるコンテキスト
スイッチが発生するときに保護が必要な領域のみをカーネル領域に保護された暗号鍵で暗号化、復
号化をするというものである。
この場合、OS のセキュリティホールなどをついて外部の攻撃者が侵入し、他のプロセスのメモ
リ領域を盗み見た場合でも重要な部分は暗号化されていることになる。管理者権限まで乗っ取った
としても、カーネル領域を見ることはできないために暗号鍵を取得することはできず、暗号化され
たメモリ領域を復号化することはできない。よって外部からの侵入を許しても、保護が必要とされ
たデータは盗み見られない。
この手法はハードウェアの改造を必要としないために現在普及している通常のプロセッサでも適
用可能であるという利点があるが、OS を信頼しているものとするため、攻撃者が内部にいる場合、
とりわけ OS を改造できる権限を持った攻撃者がいる場合には、その攻撃に対して無力である。
2.2
セキュアプロセッサ
ハードウェアによる単純なプログラム保護の対策として、暗号鍵をプロセッサ内部に埋め込む方
式が挙げられる。これは、暗号化した状態のプログラムを配布し、プロセッサ内部に埋め込まれた
暗号鍵でプログラムを復号化して実行する方式であるが、暗号鍵が埋め込まれていることから不特
定のプログラム提供者が存在するマルチベンダ環境ではプログラム保護対策として利用することは
難しい。そこで、使用する暗号鍵を対称鍵と非対称鍵の組み合わせにすることによってマルチベン
ダ環境でも利用可能なプログラム保護機能を持ったプロセッサが提案されている。
動作の様子を図 2.1 に示す。灰色の部分および黒い太矢印が暗号化されたデータ、通信路である。
この方式では、プログラム提供者は共通鍵暗号方式でプログラムを暗号化する。プロセッサは非対
称暗号方式を使用しており、内部に秘密鍵を持ち、公開鍵はプログラム提供者たちに公開されてい
る。この公開鍵を用いてプログラムの暗号化時に用いた共通暗号鍵を暗号化し、プログラムととも
に配布する。これがプロセッサに渡されると暗号化された共通暗号鍵はプロセッサ内部の秘密鍵
によって復号化され、その鍵でさらにプログラムを復号化する。このようにして OS やプロセッサ
以外のハードウェアには平文のプログラムを知られることなくプログラムの暗号化配布が可能と
なる。
3
6798;:=<?>A@9BDC
EF
+-,HGJI/K
&('*)
+-,/.1032
45 )
PQ )
L M F
+-,HGNIOK
! "$#%
EF
+-,HGNIOK
PQ )
[
\
LRM F
PQ )
]
^
WYX/Z
LM F
PQ )
LM F
+-,HGJI/K
STUV
_
a
`
b
g
c
f
d
e
h
図 2.1: セキュアプロセッサの動作
2.2.1
XOM
David Lie らは、セキュアプロセッサの一種として XOM(eXecute-Only Memory) アーキテクチャ
を提案している [2, 3, 4]。前述の方法を用いることによってプロセッサとメモリ間に平文でデータ
やプログラムが流れるのを防ぐことはできるが、実行モードが特権モードの場合ではレジスタや
キャッシュの内容が読み出せてしまうため、悪意を持って改造された OS では前述の対称鍵と非対
称鍵を組み合わせた暗号方式だけでは対応しきれないという問題がある。
この問題に対して XOM は、プロセッサ内部のレジスタやキャッシュに専用のタグを追加し、こ
れが一致しないプロセスからの読み込みはできないようにしており、これで特権モードからのレジ
スタやキャッシュの読み込みも防ぐことが可能となっている。一方で、メモリアドレスのアクセス
パターンによるプログラム挙動の解析への危惧は指摘されているものの、対策については言及され
ていない。
2.2.2
L-MSP
L-MSP は橋本、春木らが提案、実装したアーキテクチャで、プロセス管理の機能もプロセッサ
内部に持たせたものである [5, 6]。前述の XOM ではレジスタにプロセスごとのタグをつけること
で改造された OS からの情報取得を防いでいたが、L-MSP ではハードウェアコンテキストスイッチ
機能を備え、割り込みが発生するとコンテキストをまとめて暗号化してキャッシュを通してメモリ
に待避し、実行が再開されるときにはメモリから暗号化されているコンテキスト情報を読み込んで
プロセッサ内部で復号化する。このようにすることで XOM よりも遅延を緩和することを意図して
いる。
4
2.2.3
AEGIS
AEGIS は Edward Suh らの提案するアーキテクチャで、情報の秘匿に加えて改竄の検出も行うも
のである [7, 8]。データ改竄を検出するために、データを一定サイズに区切ってそれぞれのハッシュ
値を計算し、データにアクセスする際にはそのハッシュ値との比較を行う。さらにこのハッシュ値
をいくつかまとめたもののハッシュを計算し、さらにそれを繰り返すことでハッシュ値の階層構造
(ハッシュツリー) を作成する。このハッシュツリーを用いることで効率的にデータの改竄を防いで
いる。
2.3
アドレスバスの情報秘匿
前述のセキュアプロセッサでは、いずれもデータバスは暗号化されているものの、アドレスバス
は通常のプロセッサと同様であり、アドレスバスを監視することでプログラムに関する何らかの情
報が得られてしまう。
2.3.1
Oblivious RAM
Goldreich らは、メモリとプロセッサの間のやり取りから読み取ることのできるメモリアドレス
の参照局所性を厳密に秘匿する手法を Oblivious RAM として提案している。
文献 [9] ではメモリとプロセッサをそれぞれチューリングマシンとしてモデル化して、一定期間
中に必ず全メモリが一度だけアクセスされることを保証している。この保証により、一定期間毎に
アドレスの対応付けを変えることが行えればメモリの参照局所性は隠蔽される。また、その場合の
性能のオーバヘッドを計算量として見積もっている。
この手法の問題点はモデルと実際のコンピュータに違いがあること、また、実際のソフトウェア
を動作させた場合の性能評価が行われていないこと、そして、プロセッサ内の記憶領域などが一部
理想化されていることである。
2.3.2
HIDE
Xiaotong Zhuang らは、アドレスバスによって得られる情報からプログラムのアルゴリズムを解
析できることを示し、暗号鍵生成のプログラムのアドレスバスを監視することで暗号鍵を得ること
ができるとしている。そしてこの問題への対策として HIDE アーキテクチャを提案している [10]。
HIDE では、メモリ空間を一定のサイズごとに区切り、その領域の中ではそれぞれのラインに一
度ずつのアクセスしか許可しない。領域内の全てのラインに対してアクセスがあったか、あるいは
一定時間がたった時にその領域内のデータをランダムに入れ替え、入れ替えた先のアドレスはプロ
セッサが管理する。そして再度全ラインに対してのアクセスを許可する。これを繰り返すことでメ
モリアクセスの局所性を秘匿することができ、プログラムの挙動解析を防ぐことができる。
しかし、一定時間ごとのメモリアドレスのランダム入れ替えによる速度低下や、プロセッサによ
るアドレス管理に用いられるメモリサイズは無視できるものではなく、さらに専用命令の追加も必
要であり、専用コンパイラ、専用バイナリが必要となる問題点もある。
特にアドレス管理に用いるメモリについては、全体がプロセッサ内に配置されていると仮定され
ており、プロセッサ内に膨大な記憶領域が必要となってしまう。
5
第 3 章 通常のプロセッサにおけるプログラム
の動作
3.1
動作の概要と弱点
暗号化などの機能を備えていない従来のプロセッサでの一般的なプログラムの実行の様子を図 3.1
に示す。
まず、プログラムは二次記憶に保存される。ここでは、その保存されたプログラムを直接見るこ
とが可能であり、逆アセンブルなどによって解析することができる。
OS によってプログラムが開始されると二次記憶にあるプログラムはメモリに読み込まれる。ま
た、プログラムだけでなく必要なデータも二次記憶からメモリ上に、あるいはプロセッサで計算さ
れた計算結果もプロセッサからメモリ上にコピーされる。このメモリは他のプロセスから見ること
ができてしまう。さらにこれらメモリに配置されたデータは OS によって二次記憶のスワップファ
イルに書き出されることもあり、スワップファイルを読むことでメモリを読むのと同じ意味を得ら
れる。
マルチタスク環境では OS がプロセスごとにプログラムやデータ、コンテキスト情報をメモリ上
で管理しており、プロセスを切り替えるときには OS が割込命令を出してプログラムを停止させ、
これらの情報を切り替える。ここではデータやコンテキストを OS が管理しているため、OS を改
造することでこれらを読み取ることが可能となる。
プログラムが実行されている間はプログラムをキャッシュに読み込み、必要なデータにアクセス
して動作するのはプロセッサが行うことでこれには OS は関係しない。しかし、特権モードで動作
するプログラムの場合にはキャッシュやレジスタの内容を直接読み込むことが可能で、他のプロセ
スのデータであっても見ることが可能である。
さらに、メモリとの間のデータバスにハードウェアを追加するなどの方法でハードウェア的に監
視されていると、メモリからキャッシュにデータを読み込むとき、あるいはキャッシュからメモリ
にデータを書き込むときにそれらのデータの内容が漏れてしまう。
3.2
弱点への対策
3.1 をまとめると、通常のプロセッサにおけるプログラムの動作には
1. 二次記憶上のプログラムの解析
2. メモリやスワップファイルの読み取り
3. OS 改変によるプロセス情報の読み取り
4. OS 改変によるキャッシュ、レジスタの読み取り
5. ハードウェア監視によるメモリデータの読み取り
6
F NO
5PE
)*
+-,/.10-2(314
IJ LKM
!
5
B !
C6DE
F HG I 5 65 798;:=<
!>?=@
56A
B !
56A
RQTSU
"$#&%('
図 3.1: 通常のプログラム動作
のような弱点が存在する。
1 や 2 や 5 はプログラムやデータ自体を暗号化することによって防ぐことが可能で、対称鍵と非
対称鍵暗号を併用したセキュアプロセッサであれば対応可能である。また、4 はプロセッサ内部で
プロセスの識別を行う XOM や L-MSP のような手法によって防げる。3 はプロセッサにコンテキ
ストスイッチ機能を持たせた L-MSP で防ぐことができる。
3.3
プログラムのアドレスバスにおける特徴
ここまでで述べた弱点やそれに対する手法は OS やハードウェアを信頼せずにメモリのデータバ
スを暗号化するという方式であったが、アドレスバスは通常のままである。このアドレスバスを
監視することにより、プログラムの特徴を推測できてしまうおそれがあるが、XOM[2, 3, 4] などで
は対策がなされていない。この特徴を見出すために、Out-of-Order 実行を行うスーパースカラプロ
セッサのシミュレータである SimpleScalar[11] を用いてメモリアクセスの特徴を計測した。評価パ
ラメータを表 3.1 に示す。
図 3.2 は、上記のシミュレータにおいて SPEC2000int の 11 種類のベンチマーク ( bzip2, crafty,
gap, gcc, gzip, mcf, parser, twolf, vortex, vpr-place, vpr-route ) をベンチマーク終了まで全命令実行し
たときの、同じメモリアドレスに対するアクセス頻度を表すグラフである。横軸は同じメモリアド
レスに対する L2 Fill Request があった回数を全命令実行にかかったサイクル数を用いて正規化した
値、縦軸はアクセスがあった全ラインに対する百分率の累積を表す。つまり、グラフで真横に線が
描かれる部分は、該当する回数のアクセスがあったラインが存在しない部分、縦に線が描かれる部
分はその回数のアクセスがあったラインが多い部分、といえる。また、100%に達するのが遅いも
7
表 3.1: 評価パラメータ
Simulator
SimpleScalar(sim-outorder)
L1 ICache
16KB, LRU, 1way, 32 Bytes line
1cycle access latency
L1 DCache
16KB, LRU, 4way, 32 Bytes line
1cycle access latency
L2 Cache
256KB, LRU, 4way, 128 Bytes line
6cycles access latency
Memory
48cycles access latency
命令セット
ベンチマーク
実行命令数
Alpha 21264 ISA
SPEC2000int (入力セット:test)
全命令
のは集中的にアクセスされるラインが多いものとなる。
このグラフを見ると、
• mcf のようにほとんどのラインに対して少ない回数のアクセスしかしないもの
• gzip のようにある回数のアクセスをするラインが大多数を占めるもの
• vpr-route のようになかなか 100%に達しない、つまり多くのラインに対して集中的なアクセ
スがあるもの
のように大きな特徴が現れていることがわかり、このアクセス頻度の割合からプログラムの特徴が
推測できる可能性があることがわかる。特に、グラフが 100%近くで右に伸びていればいるほど、
少ない範囲に対して非常に偏ってアクセスしていることがわかる。これは、どのデータがよく読ま
れているかを知るために有効な情報となる。
一方で、データがプロセッサ内部のキャッシュから外部のメモリに書き出されてから再び同じデー
タがキャッシュに戻されるまでのサイクル数のグラフを図 3.3 に示す。横軸はメモリに書き出され
てからキャッシュに戻されるまでのサイクル数を正規化した値、縦軸は書き出されたものがキャッ
シュに戻された回数全体に対する百分率の累積を表す。
こちらのグラフでは twolf や vpr-place がやや特徴を持っているものの、それ以外はどれも似た
曲線を描いており、大きな特徴を持っているとは言い難い。
また、頻繁にアクセスがあるラインが判明すると、どこの領域が解析するにあたって重要なの
か、ということはわかるが、アクセスされない領域がわかっても重要な情報は得られにくい。
以上より、単にアクセス頻度に意味があるのではなく、アクセスされない領域が判明することに
は問題がないが、以前にアクセスした領域に再びアクセスしている、つまりメモリアクセスの空間
的局所性が見えてしまうことに解析する上での意味があることがわかる。
8
100
bzip2
crafty
gap
gcc
gzip
mcf
parser
twolf
vortex
vpr-route
vpr-place
80
Percentage
60
40
20
0
1
10
Normalized Access Frequency
100
図 3.2: 同一アドレスに対するアクセス頻度
!
"$#&% ' #()!*
' ,+ % !
' ,+,#&-)!
図 3.3: 同一アドレスへの書き込みから読み込みまでの間隔
9
第 4 章 プログラム挙動の秘匿手法
4.1
アドレスの動的変換
3.3 より、キャッシュからメモリに書き込まれるタイミングはそのままでも、書き込むアドレス
が秘匿されれば特徴をつかみ取られづらくできると考える。
そこで、本研究ではプロセッサ内部にアドレス管理機能を持ち、キャッシュからデータがメモリ
に書き込まれる時に動的にアドレスを変換させて読み込まれた場所とは別の場所へ書き込み、同一
アドレスへの局所的アクセスを隠蔽することで空間的局所性を秘匿するという方法を提案する。こ
の手法では、データがキャッシュからメモリに追い出されてから再び読み込まれてキャッシュに戻
されるまでのサイクル数は測定可能であるが、同じアドレスに書き込まれていても同じデータでは
ないため、アクセス頻度からのプログラムの挙動解析は不可能となる。
4.2
提案手法概要
まず、提案手法の動作の概要を図 4.1 に示す。通常のプロセッサとの違いは、アドレス変換テー
ブル、空き領域アドレス群、の 2 つを持つ点である。
キャッシュミスが発生してメモリからキャッシュへの読み込みが発生した場合にはアドレス変換
テーブルにしたがって論理アドレスを実際のアドレスに変換し、対象のメモリアドレスにアクセス
する。
逆にキャッシュからデータが追い出されメモリに書き込まれるときには、今回アクセスする論理
アドレスに対応する実際のアドレスをアドレス変換テーブルより参照するが、このアドレスには
書き込まず、プロセッサが管理している空き領域アドレス群に書き込む。これによりアドレス変換
テーブルで参照した実際の対応アドレスは使われなくなるのでこのアドレスを空き領域アドレス群
に入れる。
このような方法をとることで、メモリアクセスの空間的局所性を秘匿することができる。
4.3
構造詳細
次に、各部分についての詳細について述べる。
4.3.1
アドレス変換テーブル
アドレス変換テーブルは、プログラムからみた通常の論理アドレスと、プロセッサが管理する実
際のアドレスの対応テーブルである。
それぞれのラインに対して変換前アドレスと変換後アドレスの 2 つのアドレスが必要であり、実
装する対象のプロセッサが 64bit プロセッサである場合には 1 ラインに対して最大で 128bit のデー
10
23)( 5(,6*7'987, 5:;0*<
!*+,-.=(
)
!#*+,-./(01
23)(
4
!#"$
%&'( !"
図 4.1: 提案手法概要
タサイズが必要となる。仮に L2 キャッシュのラインサイズを 128Bytes とすると、128Bytes に対し
1
て 128bit のデータを持つために、プログラムが使用するメモリサイズのおおよそ のメモリが必
8
要である。これはプロセッサ内部に配置するにはあまりにも大きいものである。
そこで、このアドレス変換テーブルを階層化したアドレス変換ツリーと、その一部だけをプロ
セッサ内部に保持するためのアドレス変換キャッシュの 2 つを用いる。
4.3.2
アドレス変換ツリー
アドレス変換ツリーは、アドレス変換テーブルを階層化したもので、図 4.2 に示される構造を
とる。
アドレス変換テーブルを単純にメモリ上に配置し、その中の一部分だけをプロセッサ内に読み込
むという方法も考えられるが、これではアドレス変換テーブルへのメモリアクセスの局所性が見え
てしまい、結果的に本来のメモリアクセスの局所性も見えることになる。これを回避するために階
層構造をとり、書き込みの度に格納先を変化させることで局所性を秘匿する。
ツリーの葉ノードはアドレス変換テーブルの一部に対応し、変換後のアドレスを持つ。ツリーの
葉ノードを除くすべてのノードは、それぞれ子ノードへのポインタを持つ。これらはまずメモリ上
に配置され、必要に応じてアドレス変換キャッシュに読み込んで使用する。
ラインサイズを 128Bytes とすると、アドレス変換テーブルの時と同様に考えて、ツリーの葉ノー
1
ドにはプログラムが確保したメモリ領域の のデータサイズが必要である。葉ノード以外のノー
8
1
1
1
ドは 16 の子ノードへの 64bit のポインタを持つため、その上の階層では の
である
が必
8
16
128
1
2
要となり、さらにひとつ上の階層では
、と続く。アドレス変換ツリー全体では
、つまり
2048
15
13%のデータサイズを使用する。ただし、これはプログラムがページ単位で確保したメモリ領域全
体を使用する場合である。使われていない部分の変換テーブルは作成しないため、実際のメモリ使
用量はこれよりも少なくて済む。
11
$! ! "$#%
図 4.2: アドレス変換ツリー
4.3.3
アドレス変換キャッシュ
アドレス変換キャッシュは、アドレス変換ツリーのアクセス遅延を軽減するために用いるもので、
図 4.3 に示されるように階層ごとに分割されている。図の左側はツリーをイメージしたもの、右側
が実際のキャッシュの構造である。それぞれの階層ではエントリ数が異なり、階層の上位に近いほ
どエントリ数は少なく、下位の方がエントリ数は大きくなる。
各ノードはメモリ上に配置されたアドレス変換ツリーから読み込まれるが、このときのメモリア
クセスは L2 キャッシュミスによるメモリアクセスと共通のバスを用いて行う。これは、アドレス
変換ツリーのアクセス頻度などから情報が漏れるのを防ぐために、通常のアクセスに紛れ込ませる
ためである。よってアドレス変換キャッシュのラインサイズを L2 キャッシュのラインサイズにあ
わせる必要がある。
L2 キャッシュのラインサイズを 128Bytes とした場合、アドレス変換ツリーの各ノードも 128Bytes
になり、ツリーの葉ノードは 16 個の変換後 64bit アドレス、それ以外のノードは 16 個の子ノード
への 64bit のポインタを持つこととなる。各ノードが 16 エントリであることからツリーの各階層は
4bit ずつとなり、64bit アドレス空間全体を管理するときには、L2 のラインサイズである 128Bytes
を格納するために必要な 7bit を 64bit から差し引いた 57 を 4bit で分割した 15 階層の構造となる
(図 4.4)。
また、キャッシュの各ラインはそれぞれ対応する変換前アドレスタグを持つ。このタグは階層に
よって有効ビット数が異なり、階層が上位に近づくにしたがって下位のビットは無効となる。キャッ
シュ検索を行うときには、全階層に対して同時に変換前アドレスタグとの比較を行い、ヒットした
ものの中で最も有効ビット数が大きいもの、つまり階層が一番低いものを有効なヒットとする。
4.3.4
空き領域アドレス
プログラムが用いるデータならびにアドレス変換キャッシュをプロセッサからメモリに書き出す
際に、元とは異なる位置に書き込むが、その書き込み先として空き領域を確保している必要があ
る。そのため、この空き領域のアドレスをまとめて空き領域アドレス群としてプロセッサ内に保持
する。図 4.5 のように、読み込みの際にはアドレス変換キャッシュから得られたアドレスに直接ア
12
!" ! #
#$"
./ 0
#% & # #
' ! !
) *$+-,
(!"
#
!
!
(!"!
(!"
) +-,
!"# $%
!"
&"#
*./
'
(*)%
&
+,-. ()
図 4.3: アドレス変換キャッシュ
クセスを行うが、書き込みの時にはアドレス変換キャッシュから得られたアドレスは空き領域アド
レス群に格納し、代わりに空き領域アドレス群から一つアドレスを取り出し、このアドレスをデー
タ書き込み先として用いる。
4.4
動作詳細
提案手法の動作詳細について述べる。
4.4.1
メモリからキャッシュへの読み込み
L2 キャッシュにおいてキャッシュミスが発生してメモリから L2 キャッシュへのデータ読み込み
が発生した場合、読み込む変換前アドレスがアドレス変換部に渡される。すると、まずプロセッサ
内部に配置されたアドレス変換キャッシュの下位の階層から順に上位に向かって変換前アドレスタ
13
%$ ! #
& (
' )& * +,$.- /0$1325467#
! "#
<= 9: ; />%&"+7?2
8 8 "0 9: ;
+@$.-467# A"&B"* +7 /0$CD2EFG
<= 9: ; />%&"+JE2
-K
=H 95I;
8 L
L
<= 9: ; />%&"M$N2
+%
<= 9: ; />%&"+H2
? "
8 ? 8 8 図 4.4: 階層とアドレスの対応
グを検索する。最下層にてキャッシュヒットした時は、該当テーブル内に書かれた変換後アドレス
を返し、このアドレスに対してメモリアクセスを行う (図 4.6)。
それ以外の階層でキャッシュヒットした場合には、そのテーブル内に書かれた子ノードへのポイ
ンタを参照して子ノードをアドレス変換キャッシュに読み込み、最下層のノードが得られるまでこ
れを繰り返す (図 4.7)。
最下層がキャッシュに入った後は上記と同様にそのテーブル内の変換後アドレスにメモリアクセ
スを行う。最下層に達する途中で子ノードへのポインタがまだ有効でなかった場合、新たに子ノー
ド用のメモリ領域を確保してポインタを指定する。
また、子ノードをキャッシュインしようとしたが該当階層のキャッシュに空きがなかった場合、
アドレス変換キャッシュからひとつノードを追い出さなければならない。この追い出しについては
4.4.3 で述べる。
全階層を検索してもキャッシュヒットしない場合、これはプログラムの起動直後のみであるが、
まずアドレス変換ツリーの root ノード用のメモリ領域を確保し、次にこれをアドレス変換キャッ
シュに入れる。この後は途中階層でキャッシュヒットした場合と同様に子ノードをキャッシュに入
れることを繰り返して該当アドレスにメモリアクセスを行う。
4.4.2
L2 キャッシュからメモリへの書き込み
L2 キャッシュからデータが追い出されてメモリにデータを書き込むときも読み込みの時と同様に
まず変換前アドレスをアドレス変換部に渡し、変換前アドレスタグから検索を行う。全階層キャッ
シュミスする場合や途中階層でキャッシュヒットした場合などに最下層までをキャッシュに入れる
手順は読み込みの場合と同様であるが、最下層の必要なノードがキャッシュにある状態からあとの
動作は異なる。該当するキャッシュから変換後アドレスを読み込むが、これをそのまま使わずに空
き領域アドレス群に入れる。その代わりに空き領域アドレス群からひとつアドレスを取り出し、こ
れを書き込み先アドレスとする (図 4.8)。
14
7
45 26!31
./0%1 2(!3"
#$&%'()*+
,
&-
! "
8 :9;<
45 26!31
./0%1 2(!3"
#$&%'()*+
,
&-
#=%'()*>
! "
#=%'()*>
図 4.5: 空き領域アドレス
4.4.3
アドレス変換キャッシュからメモリへの書き込み
アドレス変換キャッシュからノードが追い出されるとき、ここでもアドレス変換を行う。4.3.3 で
述べたとおり、アドレス変換ツリーの 1 つのノードは L2 キャッシュのラインサイズと同じサイズ
になっており、アドレス変換で用いる空き領域とも同サイズになっている。そこでノード追い出
しの際に 4.4.2 と同様に空き領域アドレス群の中からアドレスをひとつ取り出してそのアドレスに
ノードを書き出し、元のアドレスは空き領域アドレス群の中に登録する (図 4.9)。
ここでノードの格納場所が変わったため、追い出されたノードの親ノードが保持しているポイン
タを書き換える必要がある。親ノードがキャッシュ内に存在している場合はそのまま親ノードの書
き換えを行うが、見つからない場合は親ノードをキャッシュに入れなければならない。親ノードと
同階層に空きがない場合、再びキャッシュからの追い出しが発生し、上の階層に向かって繰り返さ
れる。
4.5
マルチタスク環境における外部構成
マルチタスク環境では OS がメモリ領域の管理を行い、プロセスごとに論理アドレスと物理アド
レスの対応が異なる。そのため、シングルタスクの場合とは異なり、プロセッサとメモリの間に
Translation Lookaside Buffer(TLB) や OS のページングが入ることになる。ここにさらにアドレス秘
匿のためのアドレス変換テーブルが入り二回のアドレス変換が行われることになるが、このテーブ
ルを用いた変換は、TLB や OS を通した後に行う場合 (図 4.10) と通す前に行う場合 (図 4.11) の二
通りが考えられる。しかし、TLB や OS を通した後にアドレス秘匿のための変換を行う場合におい
ては通常の論理アドレスが OS に渡されてしまうため、OS が改変されていて論理アドレスが読み
取られてしまう危険性が存在する。これではアドレスを変換する意味がなくなり本末転倒である。
よって論理アドレスをアドレス変換テーブルによって別のアドレスに変換してから TLB や OS に
渡すものとする。この変換後のアドレスが改変された OS によって読み取られた場合でも、すでに
データとの対応がとれなくなっているため、局所性は読み取れない。
15
!"
%'& (
!$
"
#
$
)
* +,.-
図 4.6: メモリから L2 キャッシュへの読み込み
!
!
" #$
%'& (
DEEFGH"H N#O$P
DEEFGH"HGH
) 8* 8* 9+ :, ;
- ;- <. =/ >0
7
?31 @2 @2 A4 B5 C
6 C6 B5 C6
DEEFGH"H
I GJ KFML
図 4.7: メモリからアドレス変換キャッシュへの読み込み
また、アドレス変換テーブルはプロセスによって異なるため、プロセス切り替え時にプログラム
が使用するデータとともに切り替えが行われる。
4.6
提案手法のまとめ
このようにしてメモリから読み出されるときとメモリに書き込まれるときのアドレスを異なるも
のにし、同一アドレスへの局所的アクセスを隠蔽する。
この手法はキャッシュ、メモリ間でメモリアドレスを管理するのみであり、プロセッサ内のコア
部分やキャッシュ、あるいはメモリや OS からは透過的に利用される。よって第 2 章で紹介した手
法と併用することが可能であり、プログラムやデータ自身、またアドレス変換テーブルの暗号化に
はそれらを用いればよい。
16
!"
%'& (
#
$
!$
"
1 0243
)
*+,-./0"
図 4.8: L2 キャッシュからメモリへの書き込み
!
!
" #$
%'& (
" #$
"
)
"
*+,-./0$
1 2 43
図 4.9: アドレス変換キャッシュからメモリへの書き込み
17
%& '(*)+
!"$#
.%/
, 図 4.10: 変換前の論理アドレスを TLB や OS に渡す場合
!"$#
%& '(*)+
.%/
, 図 4.11: 変換後アドレスを TLB や OS に渡す場合
056, .$
)56,
5#(3
!*+,-.7(
)
!#*+,-./(01
23)(
4
!#"$
%&'( !"
図 4.12: 提案手法全体の詳細
18
第 5 章 評価
5.1
評価環境
本研究では、以上の提案手法を CPU シミュレータ (SimpleScalar) に組み込んで評価を行った。評
価時の基本的なパラメータを表 5.1 に示す。アドレス変換キャッシュは、L2 キャッシュと同じ速度
で動作すると仮定し、テーブルを 1 回参照するのに 6cycles を要するものとした。
表 5.1: 評価基本パラメータ
Simulator
SimpleScalar(sim-outorder) ベース
L1 ICache
16KB, LRU, 1way, 32 Bytes line
1cycle access latency
L1 DCache
L2 Cache
256KB, LRU, 4way, 128 Bytes line
6cycles access latency
Memory
48cycles access latency
Address
Translation
Cache
256KB, LRU, 128 Bytes line, 15 階層
6cycles access latency
各階層の entry 数 最下層から順に 1968,64,4,1,1,1,1,1,1,1,1,1,1,1,1
各階層の way 数
最下層から順に 16, 4,4,1,1,1,1,1,1,1,1,1,1,1,1
命令セット
Alpha 21264 ISA
ベンチマーク
実行命令数
5.2
5.2.1
16KB, LRU, 4way, 32 Bytes line
1cycle access latency
SPEC2000int (入力セット:test)
全命令
結果
メモリアクセス回数の分散
まず、3.3 で述べたメモリアクセスの局所性の秘匿について示す。
アドレスごとのアクセス回数の分散値を計算したのが図 5.1 である。これは提案手法適用前の分
散値を 1.0 としたときの相対値を表し、空き領域アドレスのエントリ数を 32K から 512K まで変化
させてグラフ化している。どれも相対的にかなり小さな値となり、十分な効果が得られた。
19
!$" +
!" !"*)
!"('
!" ,
'C&$
'C
!%" &
!%" !$" !"#
!
.0/ 1$2 436587 1
3:995;7< <
=>2@? 5BA 7<
図 5.1: 分散の相対値比較
5.2.2
メモリアクセスの局所性
図 5.2 は提案手法を組み込んだプロセッサにおけるメモリアクセスの局所性を表すグラフであ
る。これは第 3 章で示したプログラムごとの同一アドレスに対するアクセス頻度 (図 3.2) と同じも
のをアドレス変換を行った場合で作成したものである。ここからは、5.2.1 の結果より、空き領域
アドレスを 256K エントリ (2MB) としてシミュレーションを行った。アドレス変換を行った結果、
同じアドレスに集中してアクセスすることはなくなり、アクセスの空間的局所性は大きく隠蔽され
たことがわかる。さらに、mcf を除いてはプログラムごとの特徴も薄れ、メモリアクセスからのプ
ログラムの挙動推測は難しくなったと言える。
5.2.3
速度低下
次に、提案手法による速度低下について示す。この提案手法では、L2 キャッシュミスが発生した
ときにアドレス変換キャッシュへのアクセスが起こり、さらにアドレス変換キャッシュミスが発生
した場合やアドレス変換キャッシュからのノードの追い出しが発生した場合には、メモリアクセス
も増えることになるために速度が低下する。
図 5.3 が提案手法適用前と適用後の Instructions Per Cycle(IPC) の比較のグラフである。大きな速
度低下は見られず、最小で 0.01%から最大で 9.58%、平均で 3.6%の低下となっている。
20
100
bzip2
crafty
gap
gcc
gzip
mcf
parser
twolf
vortex
vpr-route
vpr-place
80
Percentage
60
40
20
0
1
10
Normalized Access Frequency
100
図 5.2: 提案手法を用いた場合の同一アドレスに対するアクセス頻度
5.2.4
メモリ使用量
最後に、アドレス変換ツリーに用いたメモリサイズについて示す。図 5.4 は、プログラム自身が
用いたメモリサイズに対するアドレス変換ツリーが用いたメモリサイズの割合を表したグラフであ
る。第 4 章において 13%の領域が必要だと述べたが、確保した領域に対する実際のメモリ使用率が
小さく、アドレス変換ツリーが用いたメモリサイズは最小で 5.2%から最大で 6.6%、平均で 6.3%と
なった。
5.3
評価のまとめ
本章では、まず、アドレス変換を行った時のプログラムのメモリアクセスの空間的局所性を調べ
た。このとき、メモリアクセスの分散は十分に小さくなることを確認した。さらに、プロセッサ内
部に空き領域アドレスを 256k エントリ程度用意すれば、適用前ではあらわれていた空間的局所性
は多くの場合で秘匿できることがわかった。
このときの提案手法による速度低下は平均で 4%程度にとどまり、メモリ使用量の増加は 6%程
度であるという結論が得られた。
21
+-,.0/213
465758.:9;.:1<>=@?AB3 3C4D=E=E,BFG 1IHEG JK
465758.:9;.:1<>= MLCN 1POQ7R N 1>O
*
()
! #"
! % $ ! $
& # ' !
図 5.3: 提案手法を用いる前後の IPC 比較
!
"
# 図 5.4: メモリ使用量の割合
22
$
# & % "
# ' %
(
*
) #
第 6 章 おわりに
6.1
まとめ
本研究では、プロセッサ以外のハードウェアや OS が信頼できない環境においてプログラムや
データを暗号化しても、メモリアクセスの局所性からプログラムの挙動が解析される可能性がある
ことを指摘した。
そして、それを防ぐためには同一アドレスへの局所的アクセスを隠蔽することが必要であり、メ
モリから読み込んだデータを異なる領域に書き戻し、そのアドレス変換テーブルを外部から読み取
ることのできないプロセッサ内部で管理する手法を提案した。
アドレス変換テーブルを現実的に管理するために、テーブル全体をメモリ上に配置し、必要な部
分のみをキャッシュとしてプロセッサ内部に持たせた。これらの読み書きを通常のデータの読み書
きと同様にして行うことでメモリアクセスの特徴を見えにくくし、プログラムの挙動が解析される
ことを防いだ。
また、この手法を用いることで起こる実行速度の低下は数%にとどまること、プロセッサ内部に
必要な記憶領域は大きくても数 MB であること、外部メモリに必要な領域はプログラムが使用す
る領域の数%∼13%程度であることから、この手法が現実的であることを示した。
6.2
今後の課題
挙動秘匿の度合いには、資源量や遅延とのトレードオフが存在する。このトレードオフを考慮し
た最適なパラメータを求めるためには、メモリアクセス局所性を利用した解析方法のモデル化を行
う必要がある。これは他の研究でも課題となっており、解析方法のモデル化が本研究の有効性をよ
り正確に示すことにつながると考えられる。
23
参考文献
[1] 稲村雄, 本郷節之. 暗号技術によるメモリデータ保護方式の提案. 情報処理学会論文誌, Vol. 45,
No. 8, 2004.
[2] Dan Boneh, David Lie, Pat Lincoln, Lohn Mitchell, and Mark Mitchell. Hardware support for
tamper-resistatnt and copy-resistant software. Technical report, Stanford University Computer Science, 1999.
[3] David Lie, Chandramohan A. Thekkath, Mark Mitchell, Patrick Lincoln, Dan Boneh, John C.
Mitchell, and Mark Horowitz. Architectural support for copy and tamper resistant software. In
Architectural Support for Programming Languages and Operating Systems, pp. 168–177, 2000.
[4] David Lie, Chandramohan A. Thekkath, and Mark Horowitz. Implementing an untrusted operating
system on trusted hardware. In Proceedings of ACM Symposium on Operating Systems Principles,
2003.
[5] 春木洋美, 橋本幹生, 川端健. 耐タンパプロセッサ (L-MSP) システムの実装とプロセス管理. 暗
号と情報セキュリティシンポジウム, 2004.
[6] 橋本幹生, 春木洋美. 敵対的な OS からソフトウェアを保護するプロセッサアーキテクチャ. 情
報処理学会論文誌 コンピューティングシステム, Vol. 45, No. 3, March 2004.
[7] G. Edward Suh, Dwaine Clarke, Blaise Gassend, Marten van Dijk, and Srinivas Devadas. AEGIS:
Architecture for tamper-evident and tamper-resistant processing. In International Conference on
Supercomputing, 2003.
[8] Blaise Gassend, G. Edward Suh, Dwaine Clarke, Marten van Dijk, and Srinivas Devadas. Caches
and hash trees for efficient memory integrity verification. In Proceedings of International Symposium on High-Performance Computer Architecture, 2003.
[9] Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs.
Journal of the ACM, Vol. 43, No. 3, pp. 431–473, 1996.
[10] Xiaotong Zhuang, Tao Zhang, and Santosh Pande. HIDE: An infrastructure for efficiently protecting information leakage on the address bus. In Proceedings of the International Conference on
Architectural Support for Programming Languages and Operating Systems, 2004.
[11] Simplescalar. http://www.simplescalar.com/.
24
謝辞
本研究を進めるにあたり、多くの方々にお世話になりました。
指導教員である坂井修一教授には研究テーマやその内容についてのアドバイスをいただき、大変
助かりました。非常に感謝しております。
清水修助手、事務補佐員の八木原晴水さん、志田明子さんには研究を行う上での事務などでお世
話になりました。ありがとうございます。
入江英嗣氏には研究内容や論文の添削などで指導していただきました。
高田正法氏には研究テーマの決定をはじめ、プログラミング、計算機の扱い方など、あらゆる面
で助言や指導などをしていただき、常に助けていただきました。
田代大輔氏、Luong Dinh Hung 氏にはシミュレータのプログラムについて様々な助言をいただき
ました。
その他にも、坂井研究室の皆様には研究や論文執筆、研究室での生活のサポートなど様々な面で
ご協力いただき、大変お世話になりました。本当にありがとうございました。 本論文の研究は、一部、JST CREST ディペンダブル情報処理基盤、21 世紀 COE 情報技術戦略
コアの研究によります。
25