エイリアス関係を用いたJava静的依存解析ツールの試作

エイリアス関係を利用した
Javaスライシングツールの実現
山中祐介*，横森励士*，井上克郎**
*大阪大学大学院基礎工学研究科
**大阪大学大学院情報科学研究科
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
背景
ソフトウェアの大規模化・複雑化
プログラム言語の高級化
プログラムの理解や保守が困難なものになっている
プログラム解析
プログラムスライス
エイリアス解析
‥
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
1
プログラム解析
静的解析
すべての実行系列を考慮した解析
入力データがソースコードのみで十分
動的解析に比べはるかにコストが小さい
動的解析
特定の入力データにおける実行系列に対する解析
あらかじめプログラムを実行しておく必要がある
実行系列が限定されているため解析結果の精度が高い
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
2
プログラムスライス
プログラムにおける、ある文のある変数（スライス基
準）の値に影響を与える文の集合
特定の機能やエラーに関係ある部分の抽出が可能
1:
2:
3:
4:
5:
6:
a = 3;
if(a > 0)
b = a;
スライス基準<6, b>に
else
対するスライス
c = a;
a = b + 2;
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
3
スライスの計算過程
1. 依存関係解析
データ依存関係
ある変数に対する定義、参照の関係
制御依存関係
制御文により生じるプログラム文間の関係
2. プログラム依存グラフ(PDG)の
構築
節点：各プログラム文
有向辺：文間の依存関係
3. PDG探索
スライス基準に対応する節点から
有向辺を逆向きに探索
1:
2:
3:
4:
5:
6:
a
a = 3;
a
if(a > 0)
b = a;
a
else
c = a;
a = b + 2; b
1
2
3
5
6
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
4
オブジェクト指向言語
オブジェクトを基本単位として扱うプログラム言語
オブジェクト
データとそれを操作するコードの組み合わせ
クラスのインスタンス化によりメモリ領域に確保
オブジェクトを指す変数を参照変数と呼ぶ
実行時決定要素が数多くある
実行時決定要素：動的束縛、多態など
近年ソフトウェア開発環境でよく使われる
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
5
オブジェクト指向プログラムの動作例
1: class A {
2: int n;
3: }
1:
2:
3:
4:
5:
a = new A();
b = new A();
b = a;
a.n += 1;
System.out.println(b.n);
クラスA
a
n: 1
0
クラスA
b
n: 0
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
6
エイリアス関係
同じメモリ空間を指す可能性がある式間の同値関係
エイリアス関係が発生する箇所
引数の参照渡し
参照変数の代入
ポインタを介した間接参照
エイリアス集合
エイリアス関係にある式の集合
1:
2:
3:
4:
5:
a = new A();
b = new A();
b = a;
a.n += 1;
System.out.println(b.n);
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
7
エイリアス解析
静的解析によりエイリアス集合を求めること
依存関係解析において正確な解析を行うためには必要
不可欠
オブジェクト指向言語における実行時決定要素の特定
がある程度可能
C言語におけるポインタを対象にした依存解析手法は見受けられるが、
オブジェクト指向言語に対する依存解析手法は見受けられない
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
8
エイリアスを考慮しない解析例
変数の定義情報を保持した変数表を用いて、依存関係解
析を行う
クラスA
1: class A {
2: int n;
3: }
a
1:
2:
3:
4:
5:
a = new A();
a
b = new A();
b = a;
b
a.n += 1;
System.out.println(b.n);
n: 1
0
a
クラスA
n: 0
b
変数表
変数
定義行
a
4
1
b
2
3
5行目の出力は4行目の演算に依存しているが
データ依存関係の抽出ができていない
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
9
研究の目的
Javaを対象とするエイリアス関係を考慮した依存関
係解析手法の提案、実装
より正確なデータ依存関係の抽出が期待できる
オブジェクト指向言語特有の実行時決定要素に対
する解析が容易になる
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
10
提案手法の方針
参照式に対する処理を既存の依存関係解析手法に追加
参照式：参照変数、インスタンス化式、参照変数を返すメソッド
前提：エイリアス解析済み
変数表
変数が最後にどこで定義されたか、さらに参照変数であればどのオブジェクト
を指しているかを表現
定義された文の情報と、参照変数であれば指しているオブジェクトを区別す
るための情報(オブジェクトID)を保持
エイリアス表
参照式がどのオブジェクトを指しているかを区別
オブジェクトIDに対する参照式の集合を保持
メンバ変数表
オブジェクト上に存在するメンバ変数を表現
オブジェクトに対するメンバ変数それぞれの変数表を保持
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
11
提案手法の概要(1/2)
インスタンス化
インスタンス化式が含まれているエイリアス表のオブジェクトIDに対す
るメンバ変数表を用意
インスタンス化によってオブジェクトが生成されるため
変数の定義
変数表の定義情報を変更
参照変数であれば、それ自身が含まれているエイリアス表のオブ
ジェクトIDに変更
定義されることで参照領域が変更されうるため
変数の参照
変数表の定義情報からデータ依存関係を抽出
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
12
提案手法の概要(2/2)
メンバ変数である場合
参照変数のオブジェクトIDに対応するメンバ変数表を用
いて処理する
メンバ変数が参照変数であれば、それ自身が指している
オブジェクトのメンバ変数表を持つ
a.b
メンバ変数表
変数表
変数
定義行
ID
ID
変数
定義行
a
2
01
01
b
4
02
b
6
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
13
適用例(1行目)
クラスA
1: class A {
2: int n;
3: }
1:
2:
3:
4:
5:
n: 0
a
a = new A();
b = new A();
b = a;
a.n += 1;
System.out.println(b.n);
エイリアス表
式
ID
01 (1,a)(1,new)(3,b)(3,a)(4,a)(5,b)
02
(2,b)(2,new)
変数表
メンバ変数表
変数
定義行
ID
ID
変数
定義行
a
1
01
01
n
1
b
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
14
適用例(2行目)
クラスA
1: class A {
2: int n;
3: }
1:
2:
3:
4:
5:
n: 0
a
クラスA
a = new A();
b = new A();
b = a;
a.n += 1;
System.out.println(b.n);
n: 0
b
エイリアス表
式
ID
01 (1,a)(1,new)(3,b)(3,a)(4,a)(5,b)
02
(2,b)(2,new)
変数表
メンバ変数表
変数
定義行
ID
ID
変数
定義行
a
1
01
01
n
1
b
2
02
02
n
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
15
適用例(3行目)
クラスA
1: class A {
2: int n;
3: }
a 1:
2:
3:
4:
5:
n: 0
a
クラスA
a = new A();
b = new A();
b = a;
a.n += 1;
System.out.println(b.n);
n: 0
b
エイリアス表
式
ID
01 (1,a)(1,new)(3,b)(3,a)(4,a)(5,b)
02
(2,b)(2,new)
変数表
メンバ変数表
変数
定義行
ID
ID
変数
定義行
a
1
01
01
n
1
b
2
3
02
01
02
n
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
16
適用例(4行目)
クラスA
1: class A {
2: int n;
3: }
a 1:
2:
3:
a,n4:
5:
n: 1
0
a
クラスA
a = new A();
b = new A();
b = a;
a.n += 1;
System.out.println(b.n);
n: 0
b
エイリアス表
式
ID
01 (1,a)(1,new)(3,b)(3,a)(4,a)(5,b)
02
(2,b)(2,new)
変数表
メンバ変数表
変数
定義行
ID
ID
変数
定義行
a
1
01
01
n
1
4
b
3
01
02
n
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
17
適用例(5行目)
クラスA
1: class A {
2: int n;
3: }
a 1:
2:
3:
a,n4:
5:
n: 1
0
a
クラスA
a = new A();
b = new A();
b
b = a;
n
a.n += 1;
System.out.println(b.n);
n: 0
b
エイリアス表
式
ID
01 (1,a)(1,new)(3,b)(3,a)(4,a)(5,b)
02
(2,b)(2,new)
変数表
メンバ変数表
変数
定義行
ID
ID
変数
定義行
a
1
01
01
n
4
b
3
01
02
n
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
18
スライシングツールの実現
我々の研究グループで開発しているJavaプログラム解析フ
レームワークに機能追加で実現
Javaプログラム解析フレームワーク
解析木構築部
構文解析、意味解析を行い意味解析木を構築
XMLデータベース部
Javaプログラムの構文木情報、意味情報をXML文書として保持
エイリアス解析部*
エイリアス解析、ユーザ要求に応じたエイリアス集合の計算を実行
ユーザインターフェース部
*大畑文明, 近藤和弘, 井上克郎: “エイリアスフローグラフを用いたオブジェクト指向プログラムの
エイリアス解析手法“, 電子情報通信学会論文誌D-1, Vol.J84-D-1, No.5, pp.443-453
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
19
スライシングツール
スライス計算ライブラリをJavaプログラム解析フレーム
ワークに追加
スライス計算ライブラリ
PDG構築
入力：Javaプログラムの意味解析木とエイリアス集合情報
出力：プログラム依存グラフ
スライス計算
入力：ユーザ要求によるスライス基準
出力：スライス
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
20
Javaプログラム解析フレームワーク
ソースコード
XML
データベース
エイリアス
フローグラフ
プログラム依存グラフ
Java
構文解析
ライブラリ
XML-意味解析木
変換ライブラリ
エイリアス解析
ライブラリ
スライス計算
ライブラリ
ユーザ
意味解析
ライブラリ
意味解析木
GUI
抽象構文木
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
21
評価実験
解析対象プログラム
P1：サンプルプログラム(2クラス、24行)
P2：簡易ドローツール(3クラス、323行)
実験環境
CPU：Pentium4 1.5Ghz
メモリ：512MB
OS：FreeBSD 5.0-CURRENT
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
22
評価(解析コスト)
PDG構築までのコスト
解析対象が参照しているJDKクラスライブラリを含む
P1の総クラス数:272クラス、P2の総クラス数：876クラス
メモリ使用量(MB)
解析時間(秒)
プログラム
総時間
プログラム
合計
P1
17.2
P1
149
P2
67.8
P2
457
P2はP1と比べて遥かにコストが大きい
コスト削減のためには、どのライブラリを
PDG構築の対象に含めるか選択が必要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
23
評価(スライスサイズ)
解析対象プログラムのみ(JDKクラスライブラリは含まない)
スライスサイズ(行)
プログラム
エイリアス考慮
エイリアス無視
P1
8
6
P2
42
30
エイリアスを考慮した方がスライスサイズが大きい
増加した文はエイリアス関係にある参照変数がもたらす依存関係
エイリアスを無視した場合のスライスは正確な
ものといえないため考慮することが重要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
24
まとめと今後の課題
オブジェクト指向言語を対象とするエイリアス関係を考慮した
依存関係解析手法の提案、実装
より正確な依存関係の抽出が可能
Javaプログラム解析フレームワークへの追加実装でスライシングツー
ルとして実現
今後の課題
スレッド、例外を含めた複雑な制御構造の解析への対応
大規模システムに対する適用実験
PDG構築対象の選択を可能にすることでのコスト削減
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
25

Download Report