2001年度中間発表会

Javaバーチャルマシンを利用した
動的依存関係解析手法の提案
大阪大学大学院基礎工学研究科
誉田謙二，梅森文彰，大畑文明，井上克郎
背景
ソフトウェアの大規模化・複雑化
テスト工程のコストの増大


フォールトの検出
フォールト位置の特定・修正（デバッグ）
フォールト位置の特定を効率よく行う一手法
プログラムスライス
2002/01/30
ソフトウェアサイエンス研究会
1
プログラムスライス
プログラム中のある文sのある変数v (スライス
基準)の値に影響を与えうる文の集合
1:
2:
3:
4:
5:
6:
a = 5;
b = a + a;
if (b > 0) {
c = a;
}
d = b;
スライス基準(6, b)の
スライス
1:
2:
3:
4:
5:
6:
a = 5;
b = a + a;
if (b > 0) {
c = a;
}
d = b;
スライスの他の用途

プログラム再利用・プログラム理解
2002/01/30
ソフトウェアサイエンス研究会
2
スライスの計算過程
ソースコード
定義・参照変数抽出
依存関係解析
プログラム依存グラフ構築
スライス
（ソースコード）
プログラム依存グラフ
（PDG）
スライス（PDG）
スライス計算(グラフ探索)
2002/01/30
ソフトウェアサイエンス研究会
3
プログラム依存グラフ（PDG）
プログラムの各文を節点、文間に存在する依
存関係を有向辺としたグラフ
プログラムの文間の依存関係

制御依存関係(Control Dependence, CD)
 条件節～述部
データ依存関係
(Data Dependence, DD)

 同一変数の定義～参照
2002/01/30
ソフトウェアサイエンス研究会
a=5;
b=3;
if (b>0) {
c=a;
} else {
d=b;
}
DD
CD
4
静的スライス
PDG節点：プログラムの各文
CD解析：静的
DD解析：静的
1:
2:
3:
4:
5:
6:
7:
8:
9:
2002/01/30
a[1]=1;
a[2]=2;
a[3]=3;
read(c);
while (c>0) {
b=a[c]+1;
c=c-1;
}
write(b);
s5
s4
s7
s1
s9
スライス基準<9,b>
ソフトウェアサイエンス研究会
s2
s6
s3
DD
CD
5
動的スライス
PDG節点：実行系列の各点
CD解析：動的
入力c=2の場合の実行系列
e1: a[1]=1;
DD解析：動的
1:
2:
3:
4:
5:
6:
7:
8:
9:
2002/01/30
a[1]=1;
a[2]=2;
a[3]=3;
read(c);
while (c>0) {
b=a[c]+1;
c=c-1;
}
write(b);
e2:
e3:
e4:
e5:
e6:
e7:
e5:
e6:
e7:
e9:
ソフトウェアサイエンス研究会
a[2]=2;
a[3]=3;
read(c);
while (c>0) {
b=a[c]+1;
c=c-1;
while (c>0) {
b=a[c]+1;
c=c-1;
write(b);
DD
CD
6
Dependence Cache（DC）スライス
PDG節点：プログラムの各文
CD解析：静的
DD解析：動的
1:
2:
3:
4:
5:
6:
7:
8:
9:
2002/01/30
a[1]=1;
a[2]=2;
a[3]=3;
read(c);
while (c>0) {
b=a[c]+1;
c=c-1;
}
write(b);
入力c=2を与えて実行
s5
s4
s7
ソフトウェアサイエンス研究会
s1
s2
s6
s9
s3
DD
CD
7
各スライス手法の比較
静的スライス DCスライス
制御依存関係
静的
静的
動的スライス
動的
データ依存関係
静的
動的
動的
PDG節点
プログラム文プログラム文実行系列の各点
スライスサイズ（精度）: 静的  DC  動的
依存関係解析コスト: 動的 ≫ DC > 静的
2002/01/30
ソフトウェアサイエンス研究会
8
オブジェクト指向言語 Java
近年ソフトウェア開発環境で多く利用される
Javaにおける実行時決定要素

配列の添字・オブジェクト参照変数・動的束縛・
例外・並列処理
静的解析の限界・動的解析の必要性
2002/01/30
ソフトウェアサイエンス研究会
9
関連研究（1/2）
バイトコード埋め込みによる動的解析†

バイトコードに解析命令を埋め込み、それを実行
することによりバイトコードの動的情報を抽出
ソース
Java Virtual Machine
Javaコンパイラ
バイトコード + 解析コード
バイトコード
変換ツール
プログラムの動的情報
・実行系列のトレース
・分岐の成功比率
・実行命令数
など
変換記述コード
† “BIT:A
2002/01/30
Tool for Instrumenting Java Bytecode”, Han Bok Lee and Benjamin G.Zorn
ソフトウェアサイエンス研究会
10
関連研究（2/2）
ソースコード埋め込みによる動的解析††

ソースコードに解析命令を付加し、コンパイル・実
行することにより動的情報を持つPDGを構築
ソース
Java Virtual Machine
プリプロセッサ
バイトコード + 解析コード
ソース + 解析命令
Javaコンパイラ
††“A
プログラム依存グラフ
（PDG）
Slicing Method for Object-Oriented Programs Using Lightweight Dynamic Information”,
Fumiaki OHATA, Kouya HIROSE, Masato FUJII and Katsuro INOUE
2002/01/30
ソフトウェアサイエンス研究会
11
既存手法の問題点（1/2）
バイトコードの埋め込みによる動的解析



埋め込むバイトコードをユーザが記述
抽出される動的情報は、主に統計量の測定を目
的としており、依存関係解析といった複雑な解析
は非現実的
ソースプログラムの情報を取得するのが困難
2002/01/30
ソフトウェアサイエンス研究会
12
既存手法の問題点（2/2）
ソースコードの埋め込みによる動的解析


Javaの構文制約によるソースコードの埋め込み位
置の制限が厳しく、十分な精度の解析が困難
解析の際にソースコードの存在が必須であり、クラ
スファイルしか存在しないクラス（JDKライブラリ等）
を介した依存関係の解析では精度低下が著しい
2002/01/30
ソフトウェアサイエンス研究会
13
提案する手法
実利用を考慮したJavaスライスシステムの構築


動的情報の利用による精度の高いスライス計算
動的情報の抽出をユーザに意識させない
JVMに基づいたDCスライスのJavaへの適用


ソースコード・バイトコードに解析命令を挿入しない
バイトコードに対し、JVM上での動的データ依存関
係解析・静的制御依存関係解析を行い、PDGを
構築、スライスを計算し、ソースコードへ反映
2002/01/30
ソフトウェアサイエンス研究会
14
方針
コンパイル時に、バイトコードの各命令とソース
コードのトークン集合との対応表*を生成
バイトコードに対し、依存関係解析を行う


データ依存関係解析：動的（JVMを用いる）
制御依存関係解析：静的（JVMとは独立に）
バイトコードに対しPDG構築、スライス計算
対応表*をもとにバイトコードでのスライスをソー
スコードに対応付ける
2002/01/30
ソフトウェアサイエンス研究会
15
手順
ソースコード
class A
Javaコンパイラ
スライス結果
対応表
class A
iconst_2
2
iload_1
j
iadd
+
istore_1
j=
バイトコードレベルのPDG
クラスファイル
class A
iconst_2
iload_1
iadd
istore_1
Java Virtual Machine
通常の実行結果
2002/01/30
ソフトウェアサイエンス研究会
16
動的データ依存関係解析の実現
データ依存関係

命令sで定義された値vが命令tで参照されるとき、
sからtへ、vに関するデータ依存関係が存在する
命令tの実行時に、値vがどの命令で定義されたかが
分かれば動的データ依存関係解析が可能
各値ごとにデータキャッシュを用意し、
最後にその値を定義した命令を記憶しておく
2002/01/30
ソフトウェアサイエンス研究会
17
JVMでの動的データ依存関係解析
方針


各データ（スタック領域・ローカル変数・フィールド変数など）
と1対1対応するようにデータキャッシュを用意
データキャッシュは各データを最後に定義した命令を保持
アルゴリズム

データが定義されたとき
 定義した命令をデータキャッシュに保存

データが参照されたとき
 その値を最後に定義した命令をデータキャッシュから取得
 取得した命令と、実行中の命令との間のデータ依存関係を抽出
2002/01/30
ソフトウェアサイエンス研究会
18
動的データ依存関係解析（例）
1:
2:
3:
4:
iconst_1
iconst_2
iadd
istore_0
Java Virtual Machine
ローカル変数
0
3
スタック
2
3
1
データ依存
対応するデータキャッシュ
0
2002/01/30
s4
ソフトウェアサイエンス研究会
s2
s1
s3
19
JVMを用いることによる利点
解析精度の向上



コードの埋め込みを行わないため、構文制約の影
響を受けず、解析精度の低下を防止
バイトコードの命令をPDG節点とするため、ソース
コードの各文を節点とするより解析精度が向上
クラスファイルしか存在しないクラス（JDKライブラリ
等）を介したデータ依存関係も抽出可能
ユーザに特別な知識を要求しない
2002/01/30
ソフトウェアサイエンス研究会
20
静的制御依存関係解析の実現
ソースコードで定義された制御依存関係の定
義を、バイトコードに対して適用するのは困難
バイトコードにおける制御依存関係

以下の条件を満たすとき、命令 s と命令 t の間
に制御依存関係が存在する
 s は分岐命令
 t は、s から直接到達する基本ブロック内の命令
2002/01/30
ソフトウェアサイエンス研究会
21
バイトコードの静的制御依存関係解析
方針

データ依存関係解析とは独立に解析
アルゴリズム


バイトコードを基本ブロックに分割する
各基本ブロックの最終命令が分岐命令なら、その
命令から直接到達可能な基本ブロック内の各命
令に対し発生する制御依存関係を抽出する
2002/01/30
ソフトウェアサイエンス研究会
22
バイトコードでのスライス計算
local_1 ≠ null で実行
aload_1
ifnull L10
iload_2
iconst_1
iadd
goto L20
L10: iconst_1
L20: ireturn
aload_1
ifnull L10
iload_2
iconst_1
iadd
goto L20
iconst_1
DD
CD
ireturn
2002/01/30
ソフトウェアサイエンス研究会
23
提案手法の実現
コンパイラ・JVM


JDK付属の javac，java にそれぞれ機能追加
Java Compiler
 実装言語：Java（約45,000行）

Java Virtual Machine
 実装言語：C言語（約70,000行）
2002/01/30
ソフトウェアサイエンス研究会
24
システム構成
ソースコード
スライス（ソースコード）
スライス基準
Javaコンパイラ
バイトコード
ソースコード⇔バイトコード
対応表
スライス
（バイトコード）
PDG（バイトコード）
スライサ
Java Virtual Machine
2002/01/30
ソフトウェアサイエンス研究会
25
まとめ・今後の課題
JVMを用いたDCスライス計算手法の提案



JVMによる動的データ依存関係解析
バイトコードに対する静的制御依存関係解析
バイトコードでのスライスをソースコードに対応付け
今後の課題


提案手法の実装
提案手法の実験的評価
 スライスサイズ（精度）・時間コスト・空間コスト
2002/01/30
ソフトウェアサイエンス研究会
26
センキュ
センキュ
2002/01/30
ソフトウェアサイエンス研究会
27

Download Report