Javaへの変換による 安全なC言語の実装

Presentation on theme: "Javaへの変換による 安全なC言語の実装"— Presentation transcript:

1 Javaへの変換による 安全なC言語の実装
上嶋 祐紀　　住井 英二郎 （東北大学 大学院 情報科学研究科）

2 C言語ではメモリ安全性が保証されていない
背景 C言語ではメモリ安全性が保証されていない 予期せぬ動作やセキュリティーホールの原因 Java言語はメモリ安全とされている

3 （Java処理系のメモリ安全性を仮定すれば）
目的 C言語のプログラムをJava言語のプログラムに変換 （そのためのトランスレータを実装） Cプログラムのメモリ安全性を保証 （Java処理系のメモリ安全性を仮定すれば） ＋ CプログラムをJavaバイトコードで配布したり、 　ブラウザ上でアプレットとして動かすことも可能に メモリ安全な言語への変換 仮にトランスレータにバグがあっても、 実行系が保証する安全性を確保できる

4 方針 C言語の仕様で定義されている動作： Javaプログラムにおいて安全に模倣 C言語の仕様で「未定義」とされている動作： 実行時検査により確実にエラーとする あるいは 安全な（未定義でない）動作で置き換える

5 型の異なるポインタ間のキャストもサポート
実現方法 Cのメモリモデルとポインタ演算をJavaで模倣 メモリブロック（連続したメモリ領域） Javaの配列により模倣 「どのように読み書きするべきか」を表す アクセスメソッド[大岩 04] を持たせる Blockクラスとして実装 ポインタ 「ベース」と「オフセット」の２ワードで表現 (Fat Pointer [Austin 他 94] [大岩 他 01] ) FatPtrクラスとして実装 型の異なるポインタ間のキャストもサポート

6 Outline 変換の例 変換に利用するJavaクラスの詳細 最適化 実験結果と考察 関連研究 結論と今後の課題 配列の宣言 アドレス演算
ポインタと整数の加算 キャスト 変換に利用するJavaクラスの詳細 最適化 実験結果と考察 関連研究 結論と今後の課題

7 変換に利用するJavaのクラス （詳細は後述）
１ワードメモリブロック : FatBlockクラス フィールド : contents メソッド : アクセスメソッド readFat : １ワード読み出し writeFat : １ワード書き込み readByte : １バイト読み出し … ポインタ : FatPtrクラス フィールド base : FatBlockオブジェクトへの参照 offset : 現在指しているメモリが 　　　　　baseから何バイト離れているかを表す整数 readFat … contents base offset

8 変換の例 ： 配列の宣言 int i; int *p; 配列以外の変数は、 int a[3]; １要素の配列とみなす
変換の例　：　配列の宣言 int i;　int *p; int a[3]; 配列以外の変数は、 １要素の配列とみなす FatBlock i = new FatBlock(1);　FatBlock p = new FatBlock(1); FatBlock a = new FatBlock(3); writeFat … readFat … p i offset 0 offset 0 readFat … a

9 変換の例 ： アドレス演算 p = &a[1]; p.writeFat(0 * 4, new FatPtr(a, 1 * 4));
変換の例　：　アドレス演算 p = &a[1]; p.writeFat(0 * 4, new FatPtr(a, 1 * 4)); writeFat … base offset 4 p offset 0 readFat … a

10 変換の例 ： ポインタと整数の加算 p + 1 FatPtr temp = p.readFat(0 * 4);
変換の例　：　ポインタと整数の加算 p + 1 FatPtr temp = p.readFat(0 * 4); new FatPtr(temp.base,　temp.offset + 1 * 4) temp readFat … 4 4 p offset 0 readFat … a

11 変換の例 ： ポインタと整数の加算 p + 1 FatPtr temp = p.readFat(0 * 4);
変換の例　：　ポインタと整数の加算 p + 1 FatPtr temp = p.readFat(0 * 4); new FatPtr(temp.base,　temp.offset + 1 * 4) temp readFat … 4 8 p offset 0 readFat … a

12 intを模倣するJavaオブジェクト（後述）
変換の例　：　キャスト *(char *)p　// ただし、a[1]にはintが格納されているものとする FatPtr temp = p.readFat(0 * 4); temp.base.readByte(temp.offset) intを模倣するJavaオブジェクト（後述） temp readFat … 4 4 p offset 0 readByte … a 0x

13 Javaオブジェクト（Byteオブジェクト）
変換の例　：　キャスト *(char *)p 実行時に何もしない （ポインタの中身は変わらない） FatPtr temp = p.readFat(0 * 4); temp.base.readByte(temp.offset) １バイトの整数を模倣する Javaオブジェクト（Byteオブジェクト） temp readFat … 4 4 0x12 p offset 4 offset 0 readByte … a 0x

14 Outline 変換の例 変換に利用するJavaクラスの詳細 最適化 実験結果と考察 関連研究 結論と今後の課題 Block抽象クラス
FatBlockクラス FatPtrクラス FatIntクラス Fat抽象クラス 最適化 実験結果と考察 関連研究 結論と今後の課題

15 格納される要素の型に応じた子クラスを持つ
Block抽象クラス メモリブロックをJavaで実装 格納される要素の型に応じた子クラスを持つ FatBlock, ByteBlock, … Block抽象クラス FatBlockクラス ByteBlockクラス ・・・

16 Block抽象クラス abstract class Block { int objsize; // 格納されている要素の（Cにおける）サイズ
int size; // メモリブロックのサイズ int addr; // メモリブロックの先頭アドレス Object[] contents; // 連続したメモリ領域を表現 abstract Fat readFat(int vo); 　　　// １ワード読み出し abstract void writeFat(int vo, Fat f); // １ワード書き込み … // 各型の値を読み書きするためのアクセスメソッド }

17 FatBlockクラス class FatBlock extends Block { Fat[] contents; // Fatは後述
FatBlock(int n) { objsize = 4; size = 4 * n; contents = new Fat[n]; addr = AddrCounter.getAddr(); AddrCounter.incrAddr(size); }　　// AddrCounterは、「現在のヒープポインタ」を模倣 Fat readFat(int vo) {//１ワード読み出し用アクセスメソッド if(vo % 4 == 0) return this.contents[vo / 4]; else // 例外を発生 } … // 各型の値を読み書きするためのアクセスメソッド

18 Fat Pointer [Austin 他 94] [大岩 他 01] をJavaで実装 FatIntクラス:
FatPtrクラス FatIntクラス FatPtrクラス: Fat Pointer [Austin 他 94] [大岩 他 01] をJavaで実装 FatIntクラス: Fat Integer [大岩 他 01] をJavaで実装 Fat抽象クラス: FatPtrとFatIntに共通する親クラス

19 FatPtrクラス class FatPtr extends Fat { /* Block base; int offset; */
FatPtr(Block b, int n) { base = b; offset = n; } int asInt() { // ポインタを整数として表示したときの値を返す if(this.base == null) return this.offset; else return this.base.addr + this.offset; }

20 Cでは整数とポインタを相互にキャストすることが可能： 整数もポインタと同様に表現しなければならない
FatIntクラス Cでは整数とポインタを相互にキャストすることが可能： 整数もポインタと同様に表現しなければならない Fat Integer [大岩 他 01] をJavaで実装 C言語の整数も２ワードで表現する FatPtrと同じフィールド、メソッドを持つ baseは常にnull

21 FatPtrとFatIntに共通する親クラス
整数とポインタ間のキャストは何もしなくてよい abstract class Fat { Block base; int offset; abstract int asInt(); }

22 Outline 変換の例 変換に利用するJavaクラスの詳細 最適化 実験結果と考察 関連研究 結論と今後の課題 最適化以前
データフロー解析による最適化 実験結果と考察 関連研究 結論と今後の課題

23 オブジェクト生成やメソッド呼び出しが大量に起こる
最適化以前 Cの基本型の変数 全てJavaのBlockクラスの（サブクラスの）オブジェクトに変換、 読み書きのたびにアクセスメソッドを使用 Cの基本型の値 全てJavaのオブジェクトに変換 （Cの通常の整数は、ポインタとまったく関係のないものも 　全てFatIntオブジェクトに変換） オブジェクト生成やメソッド呼び出しが大量に起こる 通常のCプログラムの実行と比べ、大きなオーバーヘッド

24 （BlockやFatではなく）Javaの通常の基本型変数に変換
データフロー解析による最適化 以下の条件を全て満たすCの変数を、 （BlockやFatではなく）Javaの通常の基本型変数に変換 int, long, doubleといった、Cの基本型を持つ ポインタを代入されることがない アドレス演算子（＆）によりアドレスを取られることがない 関数の仮引数ではない

25 これらの最適化により、プログラム実行時間の
更なる最適化 Cの基本型の値はJavaの（オブジェクトではなく） 基本型の値に変換、 「必要になる」までオブジェクトを生成しない 「必要になる」とは 配列、構造体、ないしBlockオブジェクトに変換された 変数に代入される 関数の実引数または返り値になる これらの最適化により、プログラム実行時間の ある程度の削減に成功

26 Outline 変換の例 変換に利用するJavaクラスの詳細 最適化 実験結果と考察 関連研究 結論と今後の課題 トランスレータ 実験結果

27 トランスレータ Cプログラムを入力として、Javaプログラムを出力 Objective Camlで実装 Cプログラムの字句・構文解析には CILライブラリ [Necula 他 02] を利用 Javaプログラムのpretty printerには Joustライブラリ [Cooper] を利用

28 The Computer Language Shootout Benchmarksの ９個のCプログラムを用いた 実験環境
CPU : Pentium GHz メインメモリ : 2 GB OS : Linux 2.6 GCC ： –O3 オプション JavaコンパイラおよびJava仮想マシン ： JDK 1.5.0

29 実験結果 nsieve ループ内で配列を用いて整数演算を行う spectral-norm 浮動小数の配列で表された行列・ベクトルの演算を行う
mandelbrot ループ内で浮動小数演算を行う recursive 再帰関数内で整数演算あるいは浮動小数演算を行う partial-sums

30 実験結果 nsieve-bits ループ内で配列を用いてビット演算を行う fannkuch ループ内で配列を用いて整数演算を行う
binary-trees ループ内で構造体の確保、読み書き、解放を行う n-body ループ内で構造体の配列を用いて浮動小数演算を行う

31 mandelbrot, partial-sums
考察 mandelbrot, partial-sums 最適化により、手書きの場合とほぼ同じ Javaプログラムをトランスレータが生成

32 考察 binary-trees, n-body 全プログラムにわたって構造体を用いている
構造体のメンバが全てBlockクラスのオブジェクトと なることによるオーバーヘッドが大きい 構造体のメンバをBlockとしない実装に変更 ループや再帰関数の中でポインタを用いている FatPtrクラスのオーバーヘッドがある 更なる解析・最適化が必要 オフセットが常に０であるようなポインタを検出し、 通常のJavaの参照に変換？

33 nsieve, spectral-norm, recursive, nsieve-bits,
考察 nsieve, spectral-norm, recursive, nsieve-bits, fannkuch, binary-trees, n-body 関数の引数がBlockクラスのオブジェクトとなる ループや再帰関数の中でアクセスされることによる オーバーヘッドが大きい 関数定義 f(t x) {…} を f(t x’) { t x = x’; …} と書き換える x’は（決してアドレスを取られないので） Blockとする必要がない xを最適化することも可能（最適化の条件を満たせば）

34 nsieve, spectral-norm, nsieve-bits, fannkuch, n-body
考察 nsieve, spectral-norm, nsieve-bits, fannkuch, n-body 配列がBlockオブジェクトとなることによる オーバーヘッドがある 更なる解析・最適化が必要 アクセスメソッドを必要としない配列を検出し、 通常のJavaの配列に変換？

35 Outline 変換の例 変換に利用するJavaクラスの詳細 最適化 実験結果と考察 関連研究 結論と今後の課題
CからJavaへのトランスレータ 安全なCの処理系に関する研究 結論と今後の課題

36 関連研究 ： CからJavaへのトランスレータ
Jazillian [Jazillian, Inc.] Ephedra [Martin 他 01] 共に、CプログラムをJava言語に移植するための 支援ツール ポインタのキャストなど、Java言語に存在しない機能は あまりサポートしていない 我々のトランスレータ CプログラムをJava環境で安全に実行することが目的 アクセスメソッドを使用することにより、 キャストされたポインタによるメモリアクセスにも対応

37 関連研究 ： 安全なCの処理系に関する研究 CCured [Necula 他 02] Fail-Safe C [Oiwa 他 01]
出力されるコードの安全性は、 トランスレータの正当性によってのみ保証 ポインタやキャストの実現が十分ではなく、 ポインタと整数のキャストに一部対応していない Fail-Safe C [Oiwa 他 01] Cプログラムを安全に実行するための、CからCへのトランスレータ 我々のトランスレータ 出力を高水準で安全なJavaプログラムとした Javaの安全性やクラス機構を利用して、 Fail-Safe Cの概念をより明確かつ単純に実現した

38 Outline 変換の例 変換に利用するJavaクラスの詳細 最適化 実験結果と考察 関連研究 結論と今後の課題

39 結論 メモリ安全な言語（Java）への変換により、 Cプログラムのメモリ安全性を確保する手法を提案

40 当座の目標 ： SPEC CPU ベンチマーク（の大半）の動作
今後の課題 ANSI C フルセットのサポート 符号なし整数、共用体、関数ポインタ、多次元配列、goto文 標準ないし既存のCライブラリへの対応 Cプログラム（を変換したJavaプログラム）から Javaのライブラリを利用する方法についても検討 （考察で述べた）最適化 JITコンパイラがどのような最適化をどこまで自動的に行うか（あるいは行わないか）できるだけ具体的に調べる 他の安全な言語（C#やMLなど）への変換 変換されたプログラムの性能 C言語の仕様をどこまでサポートできるか 当座の目標 ： SPEC CPU ベンチマーク（の大半）の動作