研究速報
2. プログラム依存グラフと依存関係の解析
エイリアス関係を考慮した Java スライシングツール
山中祐介†

井上克郎††（正員）

横森励士†（学生員）構築した上で，プログラム依存グラフ上でスライス基準に対応する節点からの到達可能節点を求める手法がJava Slicing Tool using Alias Relation
Yuusuke YAMANAKA† , Nonmember,

一般的に用いられている [3], [4]．PDG 上の節点はプ

Reishi YOKOMORI† , Student Member, and††

Katsuro INOUE†

プログラムスライスの計算には，プログラム文間の依存関係からプログラム依存グラフ（以下，PDG）をログラム上の文を表し，辺はプログラム文間の依存関, Member

大阪大学大学院基礎工学研究科，大阪府係を表す．PDG 上の辺は，変数間のデータのやり取

Graduate School of Engineering Science, Osaka University,りの把握を目的としたデータ依存辺と，プログラム文1–3, Machikaneyama-cho, Toyonaka-shi, Osaka, 560–8531,
Japan†† 大阪大学大学院情報科学研究科，大阪府間の制御構造のやり取りを目的とした制御依存辺の２種類の辺に大別される．

Graduate School of Information Science and Technology, Osaka University, 1–3, Machikaneyama-cho, Toyonaka-shi, Os-

一般の依存関係解析手法では，メソッドや手続き単位での解析を，実行順を考慮しながら依存関係の変化

aka, 560–8531, Japanが起こらなくなるまで繰り返し行う．メソッド間の呼複数の変数が同一空間を指すエイリアス

び出し関係は，呼び出される側のメソッド内で必要な関係の解析は，オブジェクト指向言語におけるスライメンバ変数や引数に関する特殊節点を，呼び出し側とス計算には必須である．本論文では，エイリアス関係呼び出される側双方に用意し，特殊節点間に辺を引くを考慮した Java 向けの静的スライシングツールの実ことで表現される [3], [4]．

あらましメソッド内での依存関係解析では，プログラムの現について述べる．

キーワード

プログラムスライシング，エイリアス

各実行時点（文）における到達定義集合（Reaching関係，静的解析，JavaDefinition Set）[1] を計算することで，プログラム1. ま え が きの各実行時点（文）において参照される変数がどの文

近年の大規模化・複雑化するプログラムに対して，で定義されたかを識別する．到達定義集合は，（変数名，プログラムスライシング [2] がデバッグの効率化を目最後に定義された場所）を要素とした集合で，解析の的として提案されている．プログラムスライシング

際には，到達定義集合を変数表として管理し，プログとは，プログラム文中においてある文 s のある変数 v

ラムの実行順に従って変数表の更新やデータ依存辺の（スライス基準< s, v > と呼ぶ）の値に影響を与える抽出を行っていく手法が用いられる．しかしオブジェ

文の集合（プログラムスライス，以下スライス）を抽

クト指向言語の場合，参照変数を用いることが多いた出する技術であり，プログラム文間の依存関係を解析め，同一メモリ空間を指す可能性のある式間の同値関することで求められる．これまでオブジェクト指向言係であるエイリアス関係が発生しやすく，すべての実語において，様々なプログラムスライシング手法の提行経路を考慮した解析手法である静的解析を行う際に案・実現がなされてきた [3]．オブジェクト指向言語の正しい結果が得られないという問題がある．

場合，参照変数を用いることが多いため，同一メモリ

3. エイリアス関係を考慮した依存関係解析空間を指す可能性のある式間の同値関係であるエイリ提案手法では，エイリアス関係にある変数の組からアス関係が発生しやすい．しかし，既存の手法では十なるエイリアス表を作成した上で，変数表を拡張する分に考慮されていないため，結果が正しくないなどのことで，エイリアス関係を考慮した静的依存関係解析問題があり，考慮されていてもエイリアス関係の解析を行う．提案手法に基づく PDG 構築の手順を以下に（エイリアス解析）について曖昧である．

示す．

そこで，本論文では Java を対象としてエイリアス関

Phase 1: 構文解析・意味解析を行い，プログラム内係を考慮した静的依存解析手法を提案する．エイリアの各文で定義・参照されている変数を把握する．

ス関係を考慮することで，オブジェクト指向言語特有

Phase 2: 各インスタンス生成式およびメインメソッの実行時決定要素の解析を含めた，詳細なスライス計

ドの引数とエイリアス関係にある変数の組を求め，エ算が期待できる．また，提案手法をスライシングツー

イリアス表を作成する．

ルとして実装し，本手法の有効性について検証する．

Phase 3: PDG の節点を作成し，実行制御構造から

電子情報通信学会論文誌

X

Vol. Jxx–X No. xx

pp. 1–4

xxxx 年 xx 月

1

電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx

制御依存辺を求める．

（ID，メンバ変数名，最後に定義された場所，メンバ

Phase 4: プログラム中の全メソッドを依存関係の変変数が参照しうる ID （メンバ変数が参照変数であ化が起こらなくなるまで実行順を考慮しながら繰り返る場合））で表される．これにより，複数の参照変数し解析を行う．提案手法では，静的初期化ブロックやを用いてある一つオブジェクトのメンバ変数が操作さコンストラクタなども，メソッドと同等にみなす．

れたとしても，依存関係の抽出が可能となる．

3. 1 エイリアス表について

Step 1: 変数表およびメンバ変数表の作成

エイリアス関係とは，同じメモリ空間を指す可能性

メソッド内の解析においては前処理として，まずメがある式間の同値関係を指す．提案手法では，[5] で提ソッドの引数および，そのメソッドが属するクラスの案されている手法を用いて，プログラム内に存在するメンバ変数から変数表およびメンバ変数表を作成する．

それぞれのインスタンス生成式およびメインメソッド• 引数が存在する場合，メソッドの宣言部を定義の引数に対して，その式とエイリアス関係にあるオ行とみなして変数表に登録する．引数に参照型の変数ブジェクトへの参照式（参照変数，参照変数を返すメを利用した場合，エイリアス表を参照してどの ID をソッド呼び出し文）の集合を求める．インスタンス生参照しうるかを解析し，その ID を変数表に登録する．

成式により宣言されたオブジェクトのメモリ領域が確

また，引数のオブジェクト中に参照可能なメンバ変数保されるため，インスタンス生成式それぞれに対してがあれば，そのメンバ変数をメンバ変数表に登録する．

異なる ID を割り振り，エイリアス表として保存する．

• メソッドが属するクラスのメンバ変数は，特殊エイリアス表は，ID と，（メソッド・行番号・変数名）節点を定義行とみなして，定義行のみを変数表に登録で表される参照式の集合で構成されている．メソッドする．参照型のメンバ変数の場合，メソッド中で初め内の依存関係解析時に参照変数が定義された際に，どて参照された時点でエイリアス表を参照し，その IDのメモリ領域を指しうるかをエイリアス表を用いて判を変数表に登録する．また，参照型のメンバ変数が指定する事で，どの参照変数が各実行時点においてどのすオブジェクト中に参照可能なメンバ変数があるならメモリ領域を参照しうるかを把握できる．図 1 に，サば，そのメンバ変数をメンバ変数表に登録する．

ンプルプログラムにおけるエイリアス表を示す．

Step 2: 文の解析

3. 2 メソッド内の依存関係解析について提案手法では，既存の手法と同様に実行順に従って変数表を更新することで，メソッド内のデータ依存辺実行順に従いメソッド内の文を先頭から解析していき，変数表を更新しながら，データ依存辺を抽出する．
解析の概略を以下に示す．

を抽出する．しかし，参照変数に関するエイリアスを

Case 1: 解析中の文において変数が宣言された場合，考慮するために，変数表を拡張し，メンバ変数表を追変数名だけを変数表に登録する．

加している．以下では，変数表の拡張およびメンバ変Case 2: 解析中の文において変数の定義が行われて数表について述べたうえで，メソッド内の解析の概略

いる場合，対応する変数表の定義行を解析中の行に更を説明する．

新する．参照型の変数が定義されている場合，エイリ変数表の拡張:

アス表を参照してどの ID を持ちうるかを解析し変数提案手法では，同じオブジェクトが複数生成された表に登録する．インスタンス化式、オブジェクトを返場合を考慮して，オブジェクトを生成元（インスタンすメソッドによって参照変数が定義された場合，返さス生成式）ごとに区別した上で参照変数の解析を行う．

れたオブジェクト中に参照可能なメンバ変数があれば，解析においては，変数表における参照変数に関する要そのメンバ変数を ID および定義行と共にメンバ変数素を（変数名，オブジェクトが参照しうる ID，最後表に登録する．に定義された場所）と拡張することで，どのインスタ解析例: 図 1 の Sample クラスの main メソッドの 2ンス化式で生成されたオブジェクトを参照しうるかと行目では，変数 b が定義されている．b は参照型の変いう情報を付帯する．

数であるため，エイリアス表を参照したところ，ID が01 の領域を参照していることがわかる．そのため，2行目の解析において (a) の変数表が (b) の変数表に更メンバ変数表:提案手法では，メソッド内で利用されるオブジェクト内に存在するメンバ変数を生成元毎に区別するた新される．

め，メンバ変数表を用意する．メンバ変数表の要素はCase 3: 解析中の文において変数が参照されている

2

レター

場合，変数表中の対応する変数の定義行から解析中のSample program

行へデータ依存関係が存在するとみなし，データ依存

class A {public int n;public A() {AA1: n=0;}}

辺を引く．
解析例: 図 1 の Sample クラスの main メソッドの 2
行目では，変数 a が参照されている．2 行目の解析時の変数表である (a) の変数表を用いて変数 a が特殊節点 a.in で定義された事を把握し，a.in から 2 行目にデータ依存辺を引く．

Case 4: 参照変数のメンバ変数を参照している場合，参照変数の ID を変数表を用いて特定した上で，対応するメンバ変数表の変数の定義行から解析中の行へ

ID
01
02
03

Table of Aliases

equation(SA1,a)(SA1,new)(Sm2,b)(Sm2,a)(Sm3,a)(Sm4,b)(Sm1,b)(Sm1,new)(Sm0,argv)
Table of Variables(a) The status during theanalysis of Sm2(= After analysis of Sm1)

データ依存関係が存在するとみなし，データ依存辺を引く．
解析例: 図 1 の Sample クラスの main メソッドの 4行目では，変数 b.n が参照されている．4 行目の解析時の変数表である (c) の変数表を用いることで，変数b が ID が 01 の領域を指していることがわかる．メン
バ変数表で ID が 01 である変数 n の定義行を参照し，3 行目から 4 行目へデータ依存辺を引く．
Case 5: If 文，while 文などのように制御構造中で分岐が存在する場合，変数表およびメンバ変数表を複製し，それぞれの実行経路に対して解析を行う．また，実行経路が合流する地点では，それぞれの実行経路に変数 定義行
ab
argv

a.in
Sm1
Sm0

ID
010203

Table of Variables(b) The status during theanalysis of Sm3(= After analysis of Sm2)(c) The status during theanalysis of Sm4(= After analysis of Sm3)

PDG of main
Special Vertex(member variable,argument,….)Statement
Data dependency

おける表を合成する．また繰り返し文の場合，繰り返し地点において各表が変化しなくなるまで文の解析を

class Sample {SA1: static A a = new A();
Sm0: public static void main(String argv[]) {Sm1: A b = new A();
Sm2: b = a;
Sm3: a.n += 1;
Sm4: System.out.println(b.n);}}Fig. 1

変数 定義行
abargva.in
Sm2Sm0ID010103

Table of Variables

変数 定義行abargv

argv
Sm1a.in
Sm2Sm0ID010103Table of Member Variables

ID0102

変数 定義行
nna.inSm1

Table of Member Variables

ID0102

変数 定義行
nna.inSm1

Table of Member Variables

ID0102

変数 定義行nn

Sm3
Sm1

Entryaa.in
a.out
a,nna
Sm3 n
Sm2
Sm4b

図 1 提案手法の概略
the Outline of the Proposal Technique繰り返す．

Case 6: メソッド呼び出し文では，メソッドの呼び出(c) の変数表より，2 行目で定義されていることがわかし中に定義された変数に関して変数表およびメンバ変るため，変数 b に関して 2 行目から 4 行目へのデータ数表を更新する．

依存関係を抽出できる．しかし．メンバ変数 n への処

Step 3: 解析後の処理理を行うためには変数 n がどのオブジェクト上の n でメソッド内の文を最後まで解析した後には，メソッあるかの判別が必要である．

ド呼び出し実行後の状態を保持するための特殊節点に提案手法では，変数表中で参照変数が参照しうるオ

対して変数表を用いてデータ依存辺を引く．その後に，ブジェクトを ID として保存する事で，どのメンバ変メソッドが属するクラスのメンバ変数や変数渡しの引数表を参照すべきであるかを特定できる．この場合，数の値が更新された場合，呼び出し元の特殊節点に変b は ID が 01 である領域を参照していることがわかる
ため，ID が 01 のオブジェクトのメンバ変数 n を参照数が定義された事を記録する．

3. 3 エイリアスを考慮した依存関係解析の例

することで 3 行目から 4 行目へのデータ依存関係を抽提案手法では，既存の手法における依存関係解析手出できる．このように参照しうるオブジェクトの特定法に，参照変数に関する処理を追加することでエイリを行うことで，テキスト情報だけでは判断し難いエイアス関係を考慮した解析を行っている．図 1 の Sample

リアス関係を考慮した依存関係の抽出が可能となる．

クラスの main メソッドの 4 行目の解析を行う場合を4. スライシングツールの実現
我々の研究グループでは，Java プログラム解析フレームワーク (JAF) に関する研究を行っている．JAFは意味解析木を構築する 解析木構築部，構文木情報考える．4 行目では変数 b とそのメンバ変数である nが参照されており，b と n に関してデータ依存関係が存在する．変数 b は 4 行目の解析時の変数表である

3

電子情報通信学会論文誌 ’xx/xx Vol. Jxx–X No. xx
表1
Table 1

[Slice subsystem][Alias subsystem]PDG[UI subsystem]

MFG

Slice
analyzer

User

AFG

Alias
analyzerGUI[Building Tree subsystem]

Syntaxanalyzer
Source file

Semanticanalyzer
Parse tree

Program Analysis time（ms）
P117,206
P267,791Semantic tree-XML
converter

Used memory（MB）
149457

表 2 スライスサイズの比較（単位：行）
Table 2 Comparison of Slice Size
ProgramP1P2

Semantic tree

[XML database subsystem]

解析コスト
Analysis Cost

Use alias
842

Not use alias
630

XML-HTML
converter
Source text with HTML tags

XML-Java
converter
User
Source file

XML-XML
converter
XML database

ス関係を考慮した場合は，考慮しない場合に比べてスライスサイズが大きい．しかし，いずれの場合もエイ

図 2 Java プログラム解析フレームワーク (JAF)
Fig. 2 Java Program Analysis Framework(JAF)

リアス関係にある参照変数がもたらした依存関係が存在するため，考慮しない場合のスライスは実際には正しくないものであった．このことから，正確なスライなどを XML データベース化する XML データベー

ス計算を行う上で提案手法は必須であるといえる．

ス部 [6]，エイリアス解析を行うエイリアス解析部 [5]，5. まとめと今後の課題

UI 部などの Java プログラムの静的解析を行うため

本論文では，オブジェクト指向言語を対象とするエのライブラリ，ツール群から構成されている．

イリアス関係を考慮した静的プログラムスライス計算

提案手法の実現においては，この JAF にスライス手法を提案し，Java プログラム解析フレームワーク計算部をライブラリとして追加実装することで，スラにスライシングツールとして実現した．提案手法によイシングツールを試作した．スライシングツールを含り，正確で実用的なスライス計算が可能になる．

めた JAF を図 2 に示す．スライス計算ライブラリで今後の課題として，スレッド，例外を含めた複雑なは，意味解析木を読み込み，エイリアス解析部からエ制御構造の解析への対応，大規模システムに対する適イリアス関係情報の抽出をしながら PDG を構築する．

用実験などが挙げられる．

また，ユーザ要求として与えられたスライス基準に対してスライスを計算し，結果を表示する．

4. 1 評価実装したスライシングツールを用いて解析コストおよびスライスの正確性について評価実験を行った．対文

献[1] Aho, A.V., Sethi, S. and Ullman, J.D., “Compilers :Principles, Techniques, and Tools”, 1986.
[2] M. Weiser, “Program slicing,” Proceedings of the
5th International Conference on Software Engineering, pp.439–449, San Diego, California, 1981.

象プログラムの概要は，実験用に作成したプログラム[3] D. Liang and M. J. Harrold, “Slicing objects us-（P1，クラス数 272（内 JDK は 270）），簡易ドローing system dependence graphs,” Proceedings of theツール（P2，クラス数 876（内 JDK は 873））であInternational Conference on Software Maintenance,
pp.358–367, Bethesda, MD, 1998.

る．解析においては，JDK を含む，全ての参照してい[4] S. Horwitz and T. Reps, “The use of program depen-

るソースコード全てに対して PDG を構築している．

dence graphs in software engineering,” Proceedings□ 解析コストof the 14th International Conference on Software En-

解析時間，メモリ使用量の結果を表 1 に示す．現在の計算機環境で，十分解析を行うことが可能であるといえるが，効率化のため JDK を PDG 構築の対象に含めるかの選択が必要になると考えられる．
□ スライスの正確性
エイリアス関係を考慮した場合としない場合とで，同じスライス基準に対してスライス計算を行った．得られたスライスサイズの違いを表 2 に示す．エイリア
4gineering, pp.392-411, Melbourne, Australia, 1992.
[5] 大畑 文明，近藤 和弘，井上 克郎，“エイリアスフローグラ

フを用いたオブジェクト指向プログラムのエイリアス解析
手法，” 信学論（D-I）, vol.J84-D-I, no.5, pp.443–453,
2001.
[6] 山中 祐介，大畑 文明，井上 克郎，“プログラム解析情報の XML データベース化 –提案と実現–，” コンピュータ
ソフトウェア, vol.19, no.1, pp.39–43, 2002.
（平成 x 年 xx 月 xx 日受付）