大規模ソフトウェアリポジトリにおけるソフトウェア部品間の依存関係解析に関する研究

(1)

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

大規模ソフトウェアリポジトリにおける

ソフトウェア部品間の

依存関係解析に関する研究

大学院情報科学研究科

コンピュータサイエンス専攻

井上研究室

市井誠

[email protected]

2008/12/24

博士学位論文公聴会

1

(2)

ソフトウェアとソフトウェア部品



ソフトウェアはソフトウェア部品（部品）から構成される



クラスや関数など



ソフトウェア部品は互いに依存関係を持つ



変数宣言やメソッド呼び出しなど



ソフトウェア部品グラフ（部品グラフ）



ソフトウェア部品間の依存関係をグラフで表現したもの



構築方法に応じて，ソフトウェアの様々な特徴が反映される



ソースコードの静的な解析に基づくグラフ : 設計などの静的な構造



実行結果のトレースに基づくグラフ : オブジェクト間の相互作用などの振舞い

2 ソフトウェア

ソフトウェア部品グラフ

(3)

ソフトウェア部品検索システム



ソフトウェア再利用



ソフトウェア開発に，既存の部品を用いること



効率的な再利用によりソフトウェア開発コストを削減できる



ソフトウェア部品検索システム



ソフトウェアを収集してソフトウェアリポジトリを構築



ユーザの問い合わせに対し，適合する部品を提供

2008/12/24

博士学位論文公聴会

3 オープンソースソフトウェ

ア (OSS)

開発現場で

過去に開発されたソフトウェア

検索

収集・蓄積

取得

ソフトウェア部品検索システム

ソフトウェアリポジトリ

(4)

ソフトウェアリポジトリでの

依存関係



既存研究では，個々のソフトウェアで閉じた依存関係のみを解析



ソフトウェアリポジトリには，ソフトウェアをまたがった依存関係が存在



ライブラリの再利用など



ソフトウェアリポジトリ全体の依存関係に着目



ソフトウェアをまたがった依存関係を含む

4

(5)

研究内容



大局的な依存関係の性質の調査



部品グラフのスケールフリー性に関する調査



局所的な依存関係の理解支援



部品を再利用する時に必要な，部品間の依存関係の理解を支援する

手法を提案

2008/12/24

博士学位論文公聴会

5

(6)

論文の構成

第 1 章

まえがき

第 2 章

Java ソフトウェアの部品グラフにおけるべき乗則の調査

[1-1][1-4]

第 3 章

再利用支援のためのソフトウェア部品の依存関係解析手

法

[1-2][1-3][1-5]

第 4 章

むすび

6 [1-1]

市井誠 , 松下誠 , 井上克郎 , “Java ソフトウェアの部品グラフにおけるべき乗則の調査” , 電子情報通信学会論文誌

D-I, Vol.J90-D, No.7, pp.1733 – 1743, 2007

年 7 月（学術論文）

[1-2]

市井誠 , 横森励士 , 早瀬康裕 , 井上克郎 , “ 再利用支援のためのソフトウェア部品の依存関係解析手法” , 電子情報通

信学会論文誌 D-I 投稿中（ 2008 年 8 月受付）（学術論文）

[1-3] Makoto Ichii, Reishi Yokomori, Katsuro Inoue, “Towards Effective Reference Analysis for Software

Component Retrieval System”, Proc. Workshop on Accountability and Traceability in Global Software

Engineering (ATGSE2007), pp.51– 52, Dec. 2007

（国際会議録）

[1-4] Makoto Ichii, Makoto Matsushita, Katsuro Inoue, “An Exploration of Power-law in Use-relation of Java

Software Systems”, Proc. 19th Australian Software Engineering Conference (ASWEC2008), pp.422 – 431, Mar.

2008

（国際会議録）

[1-5] Makoto Ichii, Takashi Ishio, Katsuro Inoue, “Cross-application Fan-in Analysis for Finding

Application-specific Concerns”, Proc. 4th Asian Workshop on Aspect-Oriented Software Development (AOAsia4),

http://appsrv.cse.cuhk.edu.hk/~aoasia/workshop/APSEC08 , Dec. 2008

（国際会議録）

(7)

Java ソフトウェアの部品グラフにおける

べき乗則の調査

第 2 章

(8)

べき乗則



グラフの特徴が現れる次数分布に関する調査を行う



スケールフリー性



次数分布にべき乗則が成り立つ性質



様々な分野で注目されている



ウェブページのリンク関係



社会ネットワーク



グラフが特徴的な性質を持つことが多い



耐障害性



自己相似性



既存研究により，部品グラフが

べき乗則に従うことが示されている

[47][64]…



既存研究の問題点



個々のソフトウェアで閉じた依存関係のみを解析



部品グラフが静的な依存関係を表現できていない



継承などの「代表的な」参照関係のみを解析

8

(9)

調査方針



より詳細な静的解析に基づく部品グラフを用いる



ソフトウェアをまたがる依存関係を含む部品グラフを調査

(10)

class A {

void exec() {

…

}

調査方法



対象の部品集合を解析して部品グラフを構築



部品グラフの入次数・出次数の分布を調査



部品グラフ



頂点（部品） :

Java クラス



辺（依存関係） :

静的に解析される参照関係



継承・実装・変数宣言・オブジェクト生成

・メソッド呼出し・フィールド参照

10 class B {

…

A.exec();

…

}

A

B

class C {

…

A a =

new A();

…

}

C

入次数 : 2

出次数 : 0

入次数 : 0

出次数 : 1

入次数 : 0

出次数 : 1

(11)

次数分布の調査



両対数軸を用い，累積度数をプ

ロット



分布がべき乗則に従えば，直

線状になる



回帰直線を求め， α

の値と寄

与率

R

*2

を得る



_α



_{回帰直線の値から求める}



寄与率

_R

*2



_{モデルへの適合度を表す値}



_[0..1]

2008/12/24

博士学位論文公聴会

11 傾き : -α

傾き : -(α-1)

p(x) = Cx

-α

degree

(12)

調査対象の部品集合



単一のソフトウェア

ANT

: Apache Ant 1.6.2 ( ビルドツール )

JBOSS

: JBoss Application Server 3.2.5 ( サーバー )

JDK

: Java Development Kit 1.4 (Java 標準ライブラリ )

ECLIPSE

: Eclipse 3.01 ( 開発環境 )



ソフトウェア集合

ASF

: Apache Software Foundation のソースコード管理シ

ステムから取得したソフトウェア集合



約 100 種類のソフトウェアを含む

SPARS_DB

: ソフトウェア部品検索システム SPARS-J の

リポジトリに蓄積されたソフトウェア集合



約 750 種類のソフトウェア



SPARS_DB の部分集合

RND

: ランダムに選択した部品集合

REL

: ある部品を利用する部品集合



基準の部品はランダムに選択

KWD

: ある単語をソースコード中に含む部品集合



単語はランダムに選択

12 頂点数

辺数

LOC

ASF

59,486

303,755

4.5M

SPARS_DB

180,637 1,808,982

14M

RND

10,000

6,184

780K

REL

9,286

17,201

2.1M

KWD

8,938

24,317

1.6M

ANT

1,260

4,995

95K

JBOSS

5,752

23,636

424K

JDK

11,556

107,198

1.1M

ECLIPSE

13,941

140,678

1.3M

(13)

結果 – 入次数

2008/12/24

博士学位論文公聴会

13 ANT

JBOSS

JDK

ECLIPSE

ASF

SPARS_DB

RND

REL

KWD

α

R

*2

ANT

2.0 ± 2.0×10

2

_0.98

JBOSS

2.3 ± 2.0×10

2

_0.98

JDK

2.1 ± 8.2×10

3

_0.99

ECLIPSE

2.2 ± 1.6×10

2

_0.96

RND

2.0 ± 2.1×10

2

_0.98

REL

2.3 ± 2.0×10

2

_0.99

KWD

2.1 ± 9.3×10

2

_0.99

ASF

2.4 ± 1.1×10

2

_0.98

SPARS_DB

2.0 ± 1.5×10

3

_1.00



入次数は，

α 2

≒

_{のべき乗則に従う}

X:

入次数 , Y: 累積度数

(14)

結果 – 出次数



出次数は，

べき乗則には従わない

14 ANT

JBOSS

JDK

ECLIPSE

ASF

SPARS_DB

RND

REL

KWD

α

R

*2

ANT

2.9 ± 1.4×10

1

_0.87

JBOSS

3.2 ± 1.0×10

1

_0.91

JDK

3.1 ± 8.2×10

2

_0.88

ECLIPSE

3.0 ± 7.7×10

2

_0.86

RND

4.4 ± 3.3×10

1

_0.91

REL

4.0 ± 2.5×10

1

_0.87

KWD

3.5 ± 8.7×10

2

_0.96

ASF

3.4 ± 6.4×10

2

_0.94

SPARS_DB

3.7 ± 6.9×10

2

_0.90

X:

出次数 , Y: 累積度数

(15)

考察 – 入次数はべき乗則に従う



単一のソフトウェアだけでなく，ソフトウェアリポジトリや

，その部分集合においてもべき乗則に従うことが示された



既存研究よりも，理想的な分布に近い



標準ライブラリを中心とした，階層的な依存関係が存在する

と考えられる



大小様々なソフトウェアが，互いに依存している

2008/12/24

博士学位論文公聴会

15

(16)

考察 – 出次数はべき乗則に従わない



既存研究と比較して，より妥当な結果が示された



既存研究は，出次数もべき乗則に従うと主張



出次数は，部品の規模と強い相関を持ち，複雑度とも弱い相関

をもつ



対数正規分布とべき乗則の中間の分布



ファイルサイズに見られる分布

16

(17)

再利用支援のための

ソフトウェア部品の依存関係解析手法

第 3 章

(18)

軽量な再利用



再利用に対するアプローチ



組織的な再利用



_{計画的に再利用可能な部品を開発する}



_{開発プロセスに再利用を組み込んだ，無駄のないアプローチ}

×

_{組織の改編を含む，再利用に対する大規模な投資を必要とする}



軽量な再利用



_{必要に応じて，既存の部品の中から検索する}



_{事前の投資を必要とせず，容易に導入できる}

×

部品の取得や，ソフトウェアへの組み込みに支援を必要とする



既存の大量の資産を活用できる，軽量な再利用に着目



WWW を通じて入手可能なオープンソースソフトウェア



_{Apache Software Foundation, SourceForge.net, Eclipse, …}



開発現場で過去に開発されたソフトウェア



依存関係が複雑になりやすい，オブジェクト指向ソフトウェアを対象とする

(19)

軽量な再利用の手順

1. 部品の取得



ソフトウェア部品検索システムなどを用い，再利用可能な部品を取得する



様々な検索システムを利用可能



_{SPARS-J: 部品再利用に特化した検索結果の順位付け}



Google code search: 大規模なデータベースと，正規表現検索



Koders: OSS 開発プロジェクトとの連携

2. 依存関係の理解と処理



取得した部品が依存する部品を調査



追加で取得，もしくは，部品を修正して依存関係を変更



限定的な支援のみ :

ソフトウェアをまたがった依存関係や，類似部品の存在を考慮していない



_{依存関係の理解支援手法}

_[26]

2008/12/24

博士学位論文公聴会

19 A

B.foo();

B

(20)

ソフトウェアリポジトリにおける

部品の依存関係の理解



手作業での調査および理解は，困難



ソフトウェアリポジトリ中には，類似した API を持つ部品が複数存在



同じ名前で参照され，同一もしくは類似した操作や属性を所有



直接ソースコード上に現れない，間接的な依存関係が存在



_{継承されたメンバの参照など}



依存関係の整合性を取る必要が有る



_{部品は一般に複数箇所で参照される}



_{依存する部品同士にも，依存関係が存在}

20 A

B.foo();

B

?

B.foo();

B.bar();

void foo() {…}

C

を継承

B

1 & C

1 B

₁

& C

₂

B

₂

& C

₁

B

₂

& C

₂

B

₃

& C

₂

B

?

void foo() {…}

C

void foo() {…}

void bar() {…}

B

₁

B

₂

B

₃

C

₁

C

₂

C

を継承

C

を継承

A

₁

(21)

研究の目的



利用者が選択可能な形式で再利用対象のクラスの依存関係の候補を抽出し，再利

用を支援する



入力 : 再利用対象のクラス集合



出力 : 再利用単位



互いに等価なクラス集合を要素とする集合



利用者は，得られた再利用単位から選択することで，

再利用対象のクラスの依存関係を得ることが出来る

2008/12/24

博士学位論文公聴会

21 A

(B

₁

| B

₂

) & C

₁

B

₁

B

₂

C

_C

1

(22)

提案手法の概略



再利用対象のクラスから参照されるクラスを取得し，それら

の関連を依存グラフとして表現



依存グラフを用いて，再利用対象のクラスが依存する部品集

合の候補である再利用単位の集合を抽出

22 A

A

AB

B

C

A

_AB

C

A

B

C

対象クラス

依存グラフ

再利用単位

ソフトウェアリポジトリ

AB

_B

_CC

(23)

依存グラフの構築 (1/2)



対象クラスから，他のクラス / メンバへの参照を抽出し，参照先を特定



候補が複数存在する場合は，全てを用いる



特定の際に経由したクラスを用いて，中間グラフを構築



頂点 : クラス



辺：参照名をラベルとして持つ

参照元クラスから参照先クラスへの有向辺



_{クラスへの参照のみ}

2008/12/24

23 A

B.foo();

B.bar();

B

₁

B

₂

B

₃

C

₁

C

₂

A

₁

A

₁

•B



B

₁



B

₂



B

₃

•foo()



B

₁

の foo()



B

₂

の foo()



C

₂

の foo()

• B

₃

の継承先 C を C

2

に特

定

•bar()



C

₁

の bar()

• B

₁

の継承先 C を C

1

に特

定，

または

• B

₂

の継承先 C を C

1

に特

定

B

C

対象クラス

参照先

博士学位論文公聴会

依存グラフ（中間グラフ）

(24)

依存グラフの構築 (2/2)



中間グラフの頂点をグループ化し，依存グラフを構築



以下の条件を満たす頂点をグループ化



_{入力辺と出力辺の集合が一致}



_{特定可能な参照の集合が一致}

24 B

₁

B

₂

B

₃

C

₁

C

₂

A

₁

B

C

A

₁

B

₁

B

₂

B

₃

C

₁

C

₂

B

C

依存グラフ

依存グラフ（中間グラフ）

B, foo()

bar()

foo()

(25)

再利用単位の抽出



依存グラフを探索することで再利用単位を抽出



再利用対象のクラスが始点



一つの頂点から，重複する複数のラベルをもつ辺を利用しない



_{衝突する部品を選択することを避ける}

2008/12/24

博士学位論文公聴会

25 A

₁

B

₁

B

₂

B

₃

C

₁

C

₂

B

C

A

₁

B

₁

B

₂

C

₁

A

₁

B

₃

C

₂

依存グラフ

再利用単位

(26)

完全性の判定



完全な再利用単位



参照先を特定すべき参照が，すべて特定される



_{依存グラフ上のいずれかのクラスを用いることで特定可能な参照}



不完全な再利用単位



特定できない参照が存在する

26 A

₁

B

₁

B

₂

C

₁

A

₁

B

₃

C

₂

○ ×

再利用単位

参照先

_完全性

B

foo()

bar()

B

₃

C

₂

の foo()

×

B

₁

,B

₂

{B

1,

B

2

}

の

foo()

C

1

の bar()

(27)

ヒューリスティクスによるフィルタリング



事実上意味のない再利用単位をヒューリスティクスにより除外する

1. 入力所属の優先（依存グラフ構築時）



グループ内のいずれかのクラスが入力クラスと同じ所属なら，それ以外を除去



_{所属 : クラスの取得元（ソフトウェアの配布パッケージなど）}



入力クラスと同じ所属のクラスが利用出来るなら，それを使うべき

2. 所属の一貫性（再利用単位抽出）



経由する頂点の所属に一貫性を持たせる



不必要に異なるパッケージにまたがることを防ぐ

2008/12/24

博士学位論文公聴会

27 A

₁

B

₁

B

₂

B

₃

C

₁

C

₂

B

C

D

₁

D

₂

D

×

X

Y

P

Q

(28)

適用例



OSS を用いて構築したソフトウェアリポジトリに対し，提案手

法を適用



ソフトウェアリポジトリ



Java Standard API のソースコード 3 バージョン



_{JDK 1.2.2, JDK 1.3.1, JDK 1.4.2 の配布パッケージ}



Apache commons のライブラリ 127 パッケージ



_{33 種類のライブラリの異なるバージョン}



総クラス数 : 22,005

(29)

適用例



SCInstance (commons-scxml-0.5) の例



2 個の再利用単位が得られた



一方は不完全 : "getCause()" メソッドが不足



_{いずれも 22 種類のクラスに依存}



手作業での調査には労力を要する



継承関係を追う必要が有る



_{依存クラス数が多い}

2008/12/24

博士学位論文公聴会

29 SCInstance

InstanciationException

_{(Java 1.4)}

Exception

_{(Java 1.4)}

Exception

_{(Java 1.3)}

Exception

_{(Java 1.2)}

Throwable

_{(Java 1.4)}

Throwable

_(Java1.3)

Throwable

_(Java1.2)

InstanciationException

Exception

Throwable

(getCause()

を持

たない )

IllegalArgumentException

_{(Java 1.4)}

IllegalArgumentException

_{(Java 1.3)}

IllegalArgumentException

_{(Java 1.2)}

IllegalArgumentException

Exception

InstanciationException

_{(Java 1.3)}

InstanciationException

_{(Java 1.2)}

public Throwable

getCause() {…}

…

SCInstance

のソースコード（一部）

依存グラフ（一部）

(30)

むすび



ソフトウェアリポジトリに含まれるソフトウェア部品間の依

存関係に着目した研究



ソフトウェアリポジトリを用いた部品グラフの次数分布の調査



_{入次数はべき乗則に従い，出次数はべき乗則に従わないことが示}

された



再利用支援を目的とした，部品の依存関係解析手法を提案



_{ソフトウェアリポジトリから，依存する部品の候補である再利用}

単位の集合を抽出

30

大規模ソフトウェアリポジトリにおけるソフトウェア部品間の依存関係解析に関する研究

大規模ソフトウェアリポジトリにおける

ソフトウェア部品間の

依存関係解析に関する研究

大学院情報科学研究科

コンピュータサイエンス専攻

井上研究室

市井 誠

[email protected]

2008/12/24

博士学位論文公聴会

1

ソフトウェアとソフトウェア部品



ソフトウェアはソフトウェア部品（部品）から構成される



クラスや関数など



ソフトウェア部品は互いに依存関係を持つ



変数宣言やメソッド呼び出しなど



ソフトウェア部品グラフ（部品グラフ）



ソフトウェア部品間の依存関係をグラフで表現したもの



構築方法に応じて，ソフトウェアの様々な特徴が反映される



ソースコードの静的な解析に基づくグラフ : 設計などの静的な構造



実行結果のトレースに基づくグラフ : オブジェクト間の相互作用などの振舞い

2

ソフトウェア

ソフトウェア部品グラフ

ソフトウェア部品検索システム



ソフトウェア再利用



ソフトウェア開発に，既存の部品を用いること



効率的な再利用によりソフトウェア開発コストを削減できる



ソフトウェア部品検索システム



ソフトウェアを収集してソフトウェアリポジトリを構築



ユーザの問い合わせに対し，適合する部品を提供

2008/12/24

博士学位論文公聴会

3

オープンソースソフトウェ

ア (OSS)

開発現場で

過去に開発されたソフトウェア

検索

収集・蓄積

取得

ソフトウェア部品検索システム

ソフトウェアリポジトリ

ソフトウェアリポジトリでの

依存関係



既存研究では，個々のソフトウェアで閉じた依存関係のみを解析



ソフトウェアリポジトリには，ソフトウェアをまたがった依存関係が存在



ライブラリの再利用など



ソフトウェアリポジトリ全体の依存関係に着目



ソフトウェアをまたがった依存関係を含む

4

研究内容



大局的な依存関係の性質の調査



部品グラフのスケールフリー性に関する調査



局所的な依存関係の理解支援



市井誠