Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現

Presentation on theme: "Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現"— Presentation transcript:

1 Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
大阪大学　大学院情報科学研究科 梅森 文彰　誉田 謙二　横森 励士　井上 克郎

2 研究の背景 ソフトウェアの大規模化・複雑化によって テスト工程のコストが増大 フォールト位置の特定を効率よく行う手法 プログラムスライス
フォールトの検出やフォールト位置の特定・修正（デバッグ）に時間がかかるようになった フォールト位置の特定を効率よく行う手法 プログラムスライス

3 Javaを対象とするスライシングシステムの構築
研究の目的 近年のソフトウェア開発環境では　オブジェクト指向言語 Javaが多く利用されている 実利用を考慮したスライシングシステムはあまり実現されていない Javaを対象とするスライシングシステムの構築 研究の目的 オブジェクト指向言語Javaは近年のソフトウェア開発環境で多く利用されていますが、Javaには多くの実行時決定要素が存在します。 そのため、静的スライスでは十分な解析制度が得られず、動的スライスでは解析コストが膨大な量になってしまいます。 そこで、Javaを対象とするスライスシステムの構築としてDCスライスを適用し、またバイトコードを解析単位とすることで、 細粒度のスライスを計算し、その結果をソースコードに反映させます。

4 Javaを対象とするスライシングシステムの構築
多くの実行時決定要素の存在 配列の添字、オブジェクトへの参照、動的束縛 例外処理、並列処理 静的な解析のみでは十分な解析精度が得られない 動的な解析のみでは多大な解析コストがかかる 　　　　　　静的な解析と動的な解析を組み合わせた 　　　　　　DC（Dependence Cache）スライスをJavaに適用 研究の目的 オブジェクト指向言語Javaは近年のソフトウェア開発環境で多く利用されていますが、Javaには多くの実行時決定要素が存在します。 そのため、静的スライスでは十分な解析制度が得られず、動的スライスでは解析コストが膨大な量になってしまいます。 そこで、Javaを対象とするスライスシステムの構築としてDCスライスを適用し、またバイトコードを解析単位とすることで、 細粒度のスライスを計算し、その結果をソースコードに反映させます。

5 プログラムスライス ある文のある変数(スライス基準)の値に 影響を与えうる文の集合 maxの値が誤っている maxをスライス基準に指定
1: scanf("%d", &a); 2: scanf("%d", &b); 3: max = a; 4: min = b; 5: if ( a > b) { 6: max = b; 7: min = a; } 8: printf("%d", max); maxの値が誤っている maxをスライス基準に指定 maxに関係ある部分を抽出 関連のあるプログラム文のみを抽出することで、デバッグ対象を限定することができ、フォールト位置特定を効率よく行うことができる

6 スライス - 計算手順 - 1. 依存関係解析 2. プログラム依存グラフ(PDG)構築 3. スライス計算 制御依存関係(CD)解析
DD 1. 依存関係解析 制御依存関係(CD)解析 データ依存関係(DD)解析 2. プログラム依存グラフ(PDG)構築 節点: プログラム文やバイトコード命令 辺: 節点間の依存関係 3. スライス計算 スライス基準に対応するPDG節点から有向辺を逆向きにたどる 到達可能な節点集合に対応する文が求めるスライス 1: scanf(“%d”,&i); 2: if (i < 5) { 3: a = 1; 4: b = 0; 5: i = i + 1; 6: } 7: printf(“%d”,i); プログラム依存グラフ 1 2 3 4 5 7 スライス計算手順 1．依存関係解析 依存関係解析には、制御依存関係解析とデータ依存関係解析があり、 制御依存関係とは、 ある条件文とその条件文によって実行されるかどうかが決定する文との関係のことです。 例えば、i<5という条件文によりi++という文が実行されるかどうか決定するのでここに制御依存関係が存在します。 データ依存関係とは、 ある変数を定義する文と参照する文の関係のことです。 例えば、変数aについて、a=1で定義され、b=aで参照されているのでここにデータ依存関係が存在します。 ２．プログラム依存グラフ(PDG)構築 プログラム依存グラフとは各プログラム文を節点で表し、文間の依存関係を有向辺で表したグラフです。 ３． スライス計算 まず、スライス基準に対応するPDGの節点を設定します。 そして、ここから有向辺を逆方向にたどることで到達可能な節点の集合を求めます。

7 DCスライス 制御依存関係解析：静的 データ依存関係解析：動的 PDG節点：ソースプログラムの各文やバイトコードの 各命令
実行時のコスト削減 データ依存関係解析：動的 配列やポインタ，構造体の詳しい解析 PDG節点：ソースプログラムの各文やバイトコードの　　　 　　　　　　　　各命令 メモリ使用量の抑制 動的スライスより低コストで、静的スライスより高精度なスライス計算が可能

8 DCスライスにおける動的データ依存関係解析
一時記憶：キャッシュ 各データと1対1対応するように用意する 各データを最後に定義した命令を保持する アルゴリズム データが定義されたとき 定義した文をキャッシュに保存 データが参照されたとき 最後に定義した文をキャッシュから取得 取得した文と実行中の文との間に 発生するデータ依存関係を抽出 10: a = 1; 11: c = 4; 12: b = a; a キャッシュ a b c 10 - 11 （文12実行時）

9 既存のDCスライス実現手法とその問題点 ソースコード埋め込みによるDCスライス計算† 問題点 ソースコードに解析命令を付加し、
コンパイル・実行することにより 動的情報を持つPDGを構築 問題点 構文制約によりソースコードの埋め込み 位置が制限される クラスファイルしか存在しないクラスを 介した依存関係解析の実現が困難 　　　　　解析精度の低下 1 : a = 10; 2 : b = a + 1; 1’: def(a, 1); 1 : a = 10; 2’: ref(a, 2); 2’: def(b, 2); 2 : b = a + 1; † F.Ohata, K.Hirose, M.Fujii and K.Inoue:“A Slicing Method for Object-Oriented Programs Using Lightweight Dynamic Information”, Proceedings of 8th Asia Pacific Software Engineering Conference , pp , Macau, China, December (2001).

10 提案する実現手法 「Javaバーチャルマシン（JVM）に基づく動的データ依存関係解析」
バイトコード上での制御依存関係も定義し，静的に解析する 利点 解析精度の向上 コードの埋め込みを行わないため、構文制約の影響を受けず、解析精度の低下を防止 クラスファイルしか存在しないクラスを介した依存関係の抽出も可能 細粒度の解析の実現 バイトコードの各命令をPDG節点とすることで、ソースコードの各文を節点とした場合と比べ細粒度の解析が可能 ユーザへの負担の軽減 通常の実行を行うだけでDCスライス計算に必要な情報を取得することができる

11 Javaスライシングシステムの構成 スライサ CD DD iconst_0 istore_1 iconst_5 iload_1
int i = 0; if (i < 5) { i++; } ソースコード スライサ CD DD スライス基準 iconst_0 Javaコンパイラ istore_1 1: iconst_0 2: isotre_1 3: iconst_5 4: iload_1 5: if_cmpge L8 6: iinc 1 1 7: L8: nop 8: return 1: 2: i = 3: 5 4: i 5: < 6: i++ 7: 8: main iconst_5 iload_1 if_cmpge L8 iinc 1 1 Javaスライスシステムの適用例 まずソースコードをJavaコンパイラに通すと、バイトコードと対応関係が得られます。 次にバイトコードをバイトコードダンプツールに通し、静的制御依存関係を求めます。 またバイトコードをJavaバーチャルマシン上で実行することで、通常の実行結果と動的データ依存関係が得られます。 そしてこれらの依存関係と先程の対応表、スライス基準を基にスライサによってPDGを構築し、スライス基準に対応する節点から スライスを求めます。 そしてその結果をソースコードに反映させます。 L8: nop 制御依存関係 解析ツール int i = 0; if (i < 5) { i++; } スライス結果 return Java バーチャルマシン 静的制御依存関係 通常の実行結果 動的データ依存関係

12 Javaスライシングシステム – 計算手順 -
Phase 1: ソースコード・バイトコード対応表の出力 Phase 2: バイトコードに対する依存関係解析 (a)： 静的制御依存関係解析 (b)： 動的データ依存関係解析 Phase 3: PDGによるスライス計算 Javaスライスシステムの解析手順 Phase 1: ソースコード・バイトコード対応表の出力 Phase 2: バイトコードに対する依存関係解析 (a)： 静的制御依存関係解析 (b)： 動的データ依存関係解析† Phase 3: PDGによるスライス計算 今回私が研究したのはPhase1、Phase2の(a)、Phase3で、以降この３つについて説明します。 以降、スライス、スライス基準、PDGに対し、バイトコード、ソースコードそれぞれに関するものを、(S)、(B)を用いて表します。 例えば、ソースコード上のスライス基準はスライス基準(S) 、バイトコード単位のスライスはスライス(B) と表されます。

13 Phase1:ソースコード・バイトコード対応表の出力
コンパイル時に、ソースコードのトークン列とバイトコードとの対応を抽出 iconst_0 istore_1 i = iconst_5 5 iload_1 i if_cmpge L8 < iinc 1 1 i++ L8: nop return main int i = 0; if (i < 5) { i++; } Phase 1: ソースコード・バイトコード対応表の出力 ここでは、ソースコードのトークン列とバイトコードとの対応を抽出します。 手順、まずトークン列と構文木要素との対応を抽出します。 次に構文木要素とバイトコードとの対応を抽出します。 対応表の例として、図のようなソースコードに対して次のようなバイトコードと対応関係が得られます。 例えば、1行目のiconst_０はソースコードのこの０に対応するのでこちらで０が出力されています。 以下同様になっています。

14 Phase 2(a): 静的制御依存関係解析†
バイトコード間の制御依存関係を静的に解析 手順 基本ブロックの分割 制御フローグラフの構築 制御依存関係の抽出 iconst_0 istore_1 iconst_5 iload_1 if_cmpge L8 iinc 1 1 L8: nop return iconst_0 istore_1 iconst_5 iload_1 if_cmpge L8 iconst_0 istore_1 iconst_5 iload_1 L8: nop return Phase 2(a): 静的制御依存関係解析 ここではバイトコード間の制御依存関係を静的に解析します。 手順、まずバイトコードを分岐も合流もない基本ブロックに分割します。 次にプログラムの流れを有向辺で表し、制御フローグラフを構築します。 そして、それから制御依存関係を抽出します。 例えば、図のようなバイトコードをまず基本ブロックに分け、制御フローグラフを構築します。 これにより、この図の赤字のような制御依存関係が得られます。 if_cmpge L8 iinc 1 1 iinc 1 1 L8:nop return †Andrew.W: Modern Compiler Implementation in C, 1998

15 Phase 2(b): 動的データ依存関係解析
Java バーチャルマシン s1: iconst_0 s2: iconst_5 s3: iadd s4: istore_0 s1: iconst_0 ローカル変数 スタック s2: iconst_5 5 s3: iadd 5 5 s4: istore_0 データ依存関係 対応するキャッシュ s2 s4 s3 s1

16 Phase 3: PDGによるスライス計算 スライス基準に対応するPDG節点から有向辺を逆向きにたどることで、スライスを抽出 手順
対応表による、スライス基準(S)からスライス基準(B)への変換 PDG(B)の構築およびその探索 対応表による、スライス(B)からスライス(S)への変換 Phase 3: PDGによるスライス計算 ここでは、スライス基準に対応するPDG節点から有向辺を逆向きにたどります。 手順として、 まずソースコード上のスライス基準から、バイトコード上のスライス基準に変換します。 次にバイトコードのPDGを構築し、探索を行いスライスを得ます。 最後にバイトコード単位のスライスから、ソースコード単位のスライスに変換します。 スライス、スライス基準、PDGに対し、バイトコード、ソースコードそれぞれに関するものを、(S)、(B)を用いて表す。

17 Javaスライシングシステム - 実装 - Javaコンパイラの機能拡張 言語:Java、行数:約3,000行(約42,000行)
Phase 1: ソースコード・バイトコード対応表の出力 Javaコンパイラの機能拡張 言語:Java、行数:約3,000行(約42,000行) Phase 2 　(a): バイトコードに対する静的制御依存関係解析 バイトコードダンプツールの機能拡張 言語:C、行数:約1,600行(約4,000行) 　(b):　バイトコードに対する動的データ依存関係解析 Java バーチャルマシンの機能拡張 言語:C、行数:約1,100行(約520,000行) Phase 3: PDGによるスライス計算 スライサの作成 言語:C、行数:約1,200行 Javaスライスシステムの実装 Phase1ではJavaコンパイラの機能拡張を行いました。 Phase2の(a)ではバイトコードダンプツールの機能拡張を行いました。 Phase3では約1200行のプログラムを作成しました。 ()内は機能拡張後のツールにおけるコード総行数を表す

18 （Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2）
評価（1/2） ソートプログラム（5クラス・231行） 多くのコストがかかるものの、現実的な数値 バイトコードを単位とする細粒度の解析 JDKライブラリに対するデータ依存関係解析 ソースコード・バイトコードの対応関係を簡単化するため、 　 バイトコードの最適化を行っていない （Pentium4 1.5GHz, 512MB, FreeBSD 5.0-CURRENT, JDK1.2.2） JVM実行時間 [ms] JVM消費メモリ [Kbytes] 通常実行 解析付実行 341 3,089 通常実行 解析付実行 4,178 26,091

19 スライスサイズ [行（全体に対する割合）]
評価（2/2） 動的スライスとの比較 構築されるPDGの節点数 提案手法 動的スライス 34,956 1,808,051 スライスサイズ [行（全体に対する割合）] 静的スライス 提案手法 動的スライス スライス基準1 79（34.2%） 51（22.1%） スライス基準2 27（11.7%） 25（10.8%） 23（10.0%） 動的スライスに比べ十分に小さいコストでのスライス計算 静的スライスに比べ高い解析精度のスライス結果

20 まとめ 細粒度Javaスライシングシステムの試作 今後の課題 ソースコード・バイトコードの対応表の出力
バイトコードに対する静的制御依存関係解析 JVMを用いた動的データ依存関係解析 PDGによるスライス計算 高精度のスライスを低コストで抽出可能 今後の課題 バイトコードの最適化に対応したバイトコード・ソースコード対応表の作成 実際のプログラム開発におけるシステムの適用 まとめ 今回、バイトコードを単位とする細粒度Javaスライスシステムの試作として ソースコード・バイトコードの対応表の出力、バイトコードに対する依存関係解析、PDGによるスライス計算を行いました。 今後の課題として バイトコードの最適化に対応したバイトコード・ソースコード対応表の作成、実際のプログラム開発におけるシステムの適用が 挙げられます。