Javaバーチャルマシンを利用した 動的依存関係解析手法の提案 大阪大学 大学院基礎工学研究科 誉田 謙二，梅森 文彰，大畑 文明，井上 克郎

フォールト位置の特定を効率よく行う一手法 背景 ソフトウェアの大規模化・複雑化 テスト工程のコストの増大 フォールトの検出 フォールト位置の特定・修正（デバッグ） フォールト位置の特定を効率よく行う一手法 プログラムスライス 2002/01/30 ソフトウェアサイエンス研究会

プログラムスライス プログラム中のある文sのある変数v (スライス基準)の値に影響を与えうる文の集合 スライスの他の用途 プログラム再利用・プログラム理解 1: a = 5; 2: b = a + a; 3: if (b > 0) { 4: c = a; 5: } 6: d = b; 1: a = 5; 2: b = a + a; 3: if (b > 0) { 4: c = a; 5: } 6: d = b; スライス基準(6, b)のスライス 2002/01/30 ソフトウェアサイエンス研究会

スライスの計算過程 ソースコード 定義・参照変数抽出 依存関係解析 プログラム依存グラフ構築 スライス （ソースコード） スライス（PDG） プログラム依存グラフ （PDG） スライス計算(グラフ探索) 2002/01/30 ソフトウェアサイエンス研究会

プログラム依存グラフ（PDG） プログラムの各文を節点、文間に存在する依存関係を有向辺としたグラフ プログラムの文間の依存関係 制御依存関係(Control Dependence, CD) 条件節～述部 データ依存関係 (Data Dependence, DD) 同一変数の定義～参照 a=5; b=3; if (b>0) { c=a; } else { d=b; } DD CD 2002/01/30 ソフトウェアサイエンス研究会

静的スライス PDG節点：プログラムの各文 CD解析：静的 DD解析：静的 1: a[1]=1; 2: a[2]=2; 3: a[3]=3; 4: read(c); 5: while (c>0) { 6: b=a[c]+1; 7: c=c-1; 8: } 9: write(b); s9 s1 s2 s4 s6 s7 s5 CD DD s3 s1 s2 s4 s6 s7 s5 s3 s9 スライス基準<9,b> 2002/01/30 ソフトウェアサイエンス研究会

動的スライス PDG節点：実行系列の各点 CD解析：動的 DD解析：動的 e1: a[1]=1; e2: a[2]=2; e4: read(c); e5: while (c>0) { e6: b=a[c]+1; e7: c=c-1; e9: write(b); e3: a[3]=3; CD DD 1: a[1]=1; 2: a[2]=2; 3: a[3]=3; 4: read(c); 5: while (c>0) { 6: b=a[c]+1; 7: c=c-1; 8: } 9: write(b); 2002/01/30 ソフトウェアサイエンス研究会

Dependence Cache（DC）スライス PDG節点：プログラムの各文 CD解析：静的 DD解析：動的 入力c=2を与えて実行 1: a[1]=1; 2: a[2]=2; 3: a[3]=3; 4: read(c); 5: while (c>0) { 6: b=a[c]+1; 7: c=c-1; 8: } 9: write(b); s1 s2 s4 s6 s7 s5 s9 s1 s2 s4 s6 s7 s5 s3 CD DD s9 2002/01/30 ソフトウェアサイエンス研究会

各スライス手法の比較 スライスサイズ（精度）: 静的 ³ DC ³ 動的 依存関係解析コスト: 動的 ≫ DC > 静的 静的スライス 動的スライス 制御依存関係 静的 動的 データ依存関係 PDG節点 プログラム文 実行系列の各点 スライスサイズ（精度）: 静的 ³ DC ³ 動的 依存関係解析コスト: 動的 ≫ DC > 静的 2002/01/30 ソフトウェアサイエンス研究会

オブジェクト指向言語 Java 近年ソフトウェア開発環境で多く利用される Javaにおける実行時決定要素 静的解析の限界・動的解析の必要性 配列の添字・オブジェクト参照変数・動的束縛・例外・並列処理 静的解析の限界・動的解析の必要性 2002/01/30 ソフトウェアサイエンス研究会

関連研究（1/2） バイトコード埋め込みによる動的解析† バイトコードに解析命令を埋め込み、それを実行することによりバイトコードの動的情報を抽出 ソース Java Virtual Machine プログラムの動的情報 ・実行系列のトレース ・分岐の成功比率 ・実行命令数 など Javaコンパイラ バイトコード + 解析コード バイトコード 変換ツール 変換記述コード † “BIT:A Tool for Instrumenting Java Bytecode”, Han Bok Lee and Benjamin G.Zorn 2002/01/30 ソフトウェアサイエンス研究会

関連研究（2/2） ソースコード埋め込みによる動的解析†† ソースコードに解析命令を付加し、コンパイル・実行することにより動的情報を持つPDGを構築 ソース Java Virtual Machine プログラム依存グラフ （PDG） プリプロセッサ バイトコード + 解析コード ソース + 解析命令 Javaコンパイラ ††“A Slicing Method for Object-Oriented Programs Using Lightweight Dynamic Information”, Fumiaki OHATA, Kouya HIROSE, Masato FUJII and Katsuro INOUE 2002/01/30 ソフトウェアサイエンス研究会

既存手法の問題点（1/2） バイトコードの埋め込みによる動的解析 埋め込むバイトコードをユーザが記述 抽出される動的情報は、主に統計量の測定を目的としており、依存関係解析といった複雑な解析は非現実的 ソースプログラムの情報を取得するのが困難 2002/01/30 ソフトウェアサイエンス研究会

既存手法の問題点（2/2） ソースコードの埋め込みによる動的解析 Javaの構文制約によるソースコードの埋め込み位置の制限が厳しく、十分な精度の解析が困難 解析の際にソースコードの存在が必須であり、クラスファイルしか存在しないクラス（JDKライブラリ等）を介した依存関係の解析では精度低下が著しい 2002/01/30 ソフトウェアサイエンス研究会

提案する手法 実利用を考慮したJavaスライスシステムの構築 JVMに基づいたDCスライスのJavaへの適用 動的情報の利用による精度の高いスライス計算 動的情報の抽出をユーザに意識させない JVMに基づいたDCスライスのJavaへの適用 ソースコード・バイトコードに解析命令を挿入しない バイトコードに対し、JVM上での動的データ依存関係解析・静的制御依存関係解析を行い、PDGを構築、スライスを計算し、ソースコードへ反映 2002/01/30 ソフトウェアサイエンス研究会

方針 コンパイル時に、バイトコードの各命令とソースコードのトークン集合との対応表*を生成 バイトコードに対し、依存関係解析を行う データ依存関係解析 ： 動的（JVMを用いる） 制御依存関係解析 ： 静的（JVMとは独立に） バイトコードに対しPDG構築、スライス計算 対応表*をもとにバイトコードでのスライスをソースコードに対応付ける 2002/01/30 ソフトウェアサイエンス研究会

手順 Javaコンパイラ ソースコード スライス結果 j= istore_1 + iadd j iload_1 2 iconst_2 対応表 class A スライス結果 j= istore_1 + iadd j iload_1 2 iconst_2 対応表 class A Javaコンパイラ バイトコードレベルのPDG class A iconst_2 iload_1 iadd istore_1 クラスファイル Java Virtual Machine 通常の実行結果 2002/01/30 ソフトウェアサイエンス研究会

動的データ依存関係解析の実現 データ依存関係 命令tの実行時に、値vがどの命令で定義されたかが分かれば動的データ依存関係解析が可能 命令sで定義された値vが命令tで参照されるとき、 　　sからtへ、vに関するデータ依存関係が存在する 命令tの実行時に、値vがどの命令で定義されたかが分かれば動的データ依存関係解析が可能 各値ごとにデータキャッシュを用意し、 最後にその値を定義した命令を記憶しておく 2002/01/30 ソフトウェアサイエンス研究会

JVMでの動的データ依存関係解析 方針 アルゴリズム 各データ（スタック領域・ローカル変数・フィールド変数など）と1対1対応するようにデータキャッシュを用意 データキャッシュは各データを最後に定義した命令を保持 アルゴリズム データが定義されたとき 定義した命令をデータキャッシュに保存 データが参照されたとき その値を最後に定義した命令をデータキャッシュから取得 取得した命令と、実行中の命令との間のデータ依存関係を抽出 2002/01/30 ソフトウェアサイエンス研究会

動的データ依存関係解析（例） 1: iconst_1 1: iconst_1 2: iconst_2 3: iadd 4: istore_0 Java Virtual Machine データ依存 2: iconst_2 3: iadd ローカル変数 スタック 4: istore_0 3 1 2 1 3 対応するデータキャッシュ s4 s1 s2 s3 s1 2002/01/30 ソフトウェアサイエンス研究会

JVMを用いることによる利点 解析精度の向上 ユーザに特別な知識を要求しない コードの埋め込みを行わないため、構文制約の影響を受けず、解析精度の低下を防止 バイトコードの命令をPDG節点とするため、ソースコードの各文を節点とするより解析精度が向上 クラスファイルしか存在しないクラス（JDKライブラリ等）を介したデータ依存関係も抽出可能 ユーザに特別な知識を要求しない 2002/01/30 ソフトウェアサイエンス研究会

静的制御依存関係解析の実現 ソースコードで定義された制御依存関係の定義を、バイトコードに対して適用するのは困難 バイトコードにおける制御依存関係 以下の条件を満たすとき、命令 s と命令 t の間に制御依存関係が存在する s は分岐命令 t は、s から直接到達する基本ブロック内の命令 2002/01/30 ソフトウェアサイエンス研究会

バイトコードの静的制御依存関係解析 方針 アルゴリズム データ依存関係解析とは独立に解析 バイトコードを基本ブロックに分割する 各基本ブロックの最終命令が分岐命令なら、その命令から直接到達可能な基本ブロック内の各命令に対し発生する制御依存関係を抽出する 2002/01/30 ソフトウェアサイエンス研究会

バイトコードでのスライス計算 local_1 ≠ null で実行 aload_1 ifnull L10 iload_2 iconst_1 iadd goto L20 ireturn aload_1 CD DD ifnull L10 iconst_1 iload_2 iadd aload_1 aload_1 ifnull L10 iload_2 iconst_1 iadd goto L20 L10: iconst_1 L20: ireturn ireturn 2002/01/30 ソフトウェアサイエンス研究会

提案手法の実現 コンパイラ・JVM JDK付属の javac，java にそれぞれ機能追加 Java Compiler Java Virtual Machine 実装言語：C言語（約70,000行） 2002/01/30 ソフトウェアサイエンス研究会

システム構成 ソースコード スライス（ソースコード） スライス基準 スライス ソースコード⇔バイトコード （バイトコード） 対応表 スライス （バイトコード） Javaコンパイラ バイトコード PDG（バイトコード） スライサ Java Virtual Machine 2002/01/30 ソフトウェアサイエンス研究会

まとめ・今後の課題 JVMを用いたDCスライス計算手法の提案 今後の課題 JVMによる動的データ依存関係解析 バイトコードに対する静的制御依存関係解析 バイトコードでのスライスをソースコードに対応付け 今後の課題 提案手法の実装 提案手法の実験的評価 スライスサイズ（精度）・時間コスト・空間コスト 2002/01/30 ソフトウェアサイエンス研究会

センキュ センキュ 2002/01/30 ソフトウェアサイエンス研究会