ソースコードの静的特性を用いたJavaプログラム間類似

ソースコードの静的特性を用いた
Javaプログラム間類似度測定ツールの試作
基礎工学部情報科学科
井上研究室
小堀一雄
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
背景
ソフトウェア開発効率を飛躍的に
向上するための手法として、再利
用が注目されている
インターネットの普及により大量の
ソースコードが比較的容易に入手
可能となった
再利用とは既存の類似ソフトウェ
ア部品を参照し，一部手直しをし
て用いること
再利用を活用するためには，過去に開発さ
れた類似なソフトウェア部品に関する情報
を入手することが必要
これらのソースコードは，開発者にとって
有益な再利用部品である可能性がある
ソフトウェアを収集して
再利用部品検索システムを構築
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
3
背景
ソフトウェア開発効率を飛躍的に
向上するための手法として、再利
用が注目されている
インターネットの普及により大量の
ソースコードが比較的容易に入手
可能となった
再利用とは既存の類似ソフトウェ
ア部品を参照し，一部手直しをし
て用いること
再利用を活用するためには，過去に開発さ
れた類似なソフトウェア部品に関する情報
を入手することが必要
これらのソースコードは，開発者にとって
有益な再利用部品である可能性がある
ソフトウェアを収集して
再利用部品検索システムを構築
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
SPARS-J（1/2）
利用実績に基づくソフトウェア部品検索システム
SPARS-J
（Software Product Archiving, analyzing ,and Retrieving System for Java）
システムの特徴
対象：Javaプログラムソースコード
利用実績に基づいた評価値(Component Rank*)を計算し，
利用実績によるランク付けを行う事で，利用実績の高い部品を，
ユーザに提供可能
* Katsuro Inoue, Reishi Yokomori, Hikaru Fujiwara, Tetsuo Yamamoto, Makoto Matsushita, Shinji Kusumoto: "Component
Rank: Relative Significance Rank for Software Component Search", to be appeared in Proceedings of 25th International
Conference on Software Engineering (ICSE 2003), Portland, Oregon, 2003.
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
6
SPARS-J（2/2）
Component Rankの計算では，部品間のコピー関係を把握するた
めに類似度を測定している
類似部品を一つの部品群として扱い，利用関係を合成する
評価値にコピー関係を反映させることが可能
B
部品A
C
D
類似
B
D
合成
+
部品A´
E
部品群A
F
C
E
F
これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
7
問題と研究の目的
文字列比較を用いた類似度測定手法の問題点
類似度測定の一回当たりの計算コストが高い
新しい部品が入ってきた場合、毎回全部品に対して比
較を行わなくてはならない
SPARS-Jのような大量の部品を対象とした類似度測
定には不向きである
より低コストな類似度測定手法が必要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
8
類似度メトリクスを用いた類似度測定手法
類似度メトリクス：類似判定の定量的基準（数値）
2つの視点から類似度メトリクスを計測する
トークン構成
メトリクス：ソースコードにおける各トークンの出現数
トークン＝予約語 + 記号 + 演算子 + 識別子
（96種）（49種）（9種）（37種）（１種）
ソフトウェア部品の表層的特徴を表す
複雑度
メトリクス：クラス内のメソッド数, サイクロマチック数（分岐の数）など
ソフトウェア部品の構造的特徴を表す
数値の比較なのでコストの低下が期待できる
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
9
類似度判定法（トークン構成メトリクス）
部品Xのトークン構成メトリクス＝（Xm1,・・・,Xmn)
部品X の全トークン数
n
＝ Ttotal（X）＝ ∑ ( Xmk)
k=1
n
部品A,Bの各トークンの差分の和＝ diff(A,B) ＝∑ ( Amk Bmk )
k=1
■部品Aと部品Bの非類似度を D（A,B) とする
D(A,B)
diff(A,B)
min(Ttotal（A）, Ttotal（B）)
D(A,B) ＜ 0.03 なら類似と判定
（SPARS-Jの場合）
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
10
類似度判定法（複雑度メトリクス）
各メトリクスの差分が対応する閾値以内に収まったら類似
メトリクス名
閾値
サイクロマチック数
0
メソッドの宣言数
1
メソッド呼び出し数
2
ネストの深さ
0
“class”トークン数
0
“interface”トークン数
0
トークン構成度：0.03未満
and
複雑度：全て閾値以内
部品AとBは類似部品である
このメトリクス値が閾値以内でないと最終的に類似とは判定されない
事前にこのメトリクスと閾値を用いて比較対象を絞り込めないか？
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
11
類似度判定法（複雑度メトリクス）
各メトリクスの差分が対応する閾値以内に収まったら類似
メトリクス名
閾値
サイクロマチック数
0
メソッドの宣言数
1
メソッド呼び出し数
2
ネストの深さ
0
“class”トークン数
0
“interface”トークン数
0
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
12
類似度判定法
2つのメトリクスが閾値以内なら類似していると判定
トークン構成度：0.03未満
and
部品AとBは類似部品である
複雑度：全て閾値以内
新しい部品が入ってきた場合、全部に対して比較計算をしないとならない
結果に直接影響を与えるメトリクス（＝主メトリクス）
をキーとしてハッシュを利用し、事前に分類をする．
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
13
類似度比較回数の効率化
メトリクス計測時に、いくつかの主メトリク
スでハッシュキーを作成する
ハッシュキー＝
(24bit)
8bit
8bit
8bit
新しく類似測定をしたい部品Pが入ってきた
時
 部品Pのハッシュキー＝[10.62.125]
 主メトリクス[A,B,C]の閾値＝[0.0.1]
主メトリクス主メトリクス主メトリクス
A
B
C
類似比較の対象となるのは部品
A，B，Cの3つ
ハッシュキーと部品を対応させた
データベースを構築
[
0. 0]= null
・・
・
[ 10. 62.124]= 部品A
[ 10. 62.125]= 部品B，部品C
[ 10. 62.126]= null
・・
・
[255.255.255]= 部品Z
最終結果を変えずに効率を上げる
ことが可能
0.
DB
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
14
Ttotalをハッシュキーに適応するときの問題点
 類似判定の条件
トークンの差分が
Ttotalの3％以内
diff(A,B)
min(Ttotal（A）, Ttotal（B）) ＜ 0.03
Ttotal =30 ⇒ 29～31
Ttotal =150 ⇒ 145～155
[ 0.
[
0.
0. 0]= null
・・
・
[ 10. 62. 29]= 部品A
[ 10. 62. 30]= 部品B，部品C
[ 10. 62. 31]= null
・・
・
[255.255.255]= 部品Z
DB
[
[
[
[
[
[
[
[
[
[
[
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
0.
0]= null
・
・
・
62.145]= 部品A
62.146]= null
62.147]= null
62.148]= 部品B
62.149]= 部品C
62.150]= 部品D，部品E
62.151]= null
62.152]= 部品F
62.153]= null
62.154]= 部品G
62.155]= 部品H,部品I
DB
・
・
・
[255.255.255]= 部品Z
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
15
ハッシュ関数を用いた解決法
ハッシュ関数 h(Ttotal) を用いた加工
｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
｜h(Ttotal×1.03) － h(Ttotal)｜≦ １
log1.04（Ttotal）
h(Ttotal)
6
5
4
3
2
1
Ttotal
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
16
ハッシュ関数を用いた解決法
ハッシュ関数 h(Ttotal) を用いた加工
｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
｜h(Ttotal×1.03) － h(Ttotal)｜≦ １
h(Ttotal)
6
5
4
3
2
1
Ttotal×0.97
Ttotal×1.03
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
17
ハッシュ関数を用いた解決法
ハッシュ関数 h(Ttotal) を用いた加工
｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
｜h(Ttotal×1.03) － h(Ttotal)｜≦ １
h(Ttotal)
6
5
4
3
2
1
Ttotal
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
18
ハッシュ関数を用いた解決法
ハッシュ関数 h(Ttotal) を用いた加工
｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
｜h(Ttotal×1.03) － h(Ttotal)｜≦ １
h(Ttotal)
6
5
4
3
2
1
Ttotal×0.97
Ttotal×1.03
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
19
ハッシュ関数を用いた解決法
ハッシュ関数 h(Ttotal) を用いた加工
｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
｜h(Ttotal×1.03) － h(Ttotal)｜≦ １
h(Ttotal)
6
5
4
3
2
1
Ttotal
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
20
ハッシュ関数を用いた解決法
ハッシュ関数 h(Ttotal) を用いた加工
｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
｜h(Ttotal×1.03) － h(Ttotal)｜≦ １
h(Ttotal)
6
5
4
3
2
1
Ttotal×0.97
Ttotal×1.03
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
21
ハッシュ関数を用いた解決法
ハッシュ関数 h(Ttotal) を用いた加工
｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
｜h(Ttotal×1.03) － h(Ttotal)｜≦ １
h(Ttotal)
h(Ttotal)は，閾値1の主メトリクスとして機能する
6
5
4
3
2
1
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
22
実験結果
SPARS-Jの類似度測定部「Luigi」として実装
対象： JDK431クラス
文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec）
主メトリクス
類似クラスタ
最終クラスタ計算コスト(sec)
未使用
1
278
05.02
[C]
21
278
00.56
[ C,M ]
85
278
00.29
[ C,M,T ]
232
278
00.16
[
C：サイクロマチック数
M：宣言メソッド数
T : f(Ttotal)
0.
0. 0]= null
・・
・
[ 10. 62.124]= 部品A
[ 10. 62.125]= 部品B，部品C
[ 10. 62.126]= null
・・
・
[255.255.255]= 部品Z
DB
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
23
実験結果
SPARS-Jの類似度測定部「Luigi」として実装
対象： JDK431クラス
文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec）
主メトリクス
類似クラスタ
最終クラスタ計算コスト(sec)
未使用
1
278
05.02
[C]
21
278
00.56
[ C,M ]
85
278
00.29
[ C,M,T ]
232
278
00.16
C：サイクロマチック数
M：宣言メソッド数
T : f(Ttotal)
トークン構成度+複雑度の両方で類
似と判定され、最終的に類似と判定
された部品群の数
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
24
実験結果
SPARS-Jの類似度測定部「Luigi」として実装
対象： JDK431クラス
文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec）
主メトリクス
類似クラスタ
最終クラスタ計算コスト(sec)
未使用
1
278
05.02
[C]
21
278
00.56
[ C,M ]
85
278
00.29
[ C,M,T ]
232
278
00.16
C：サイクロマチック数
M：宣言メソッド数
T : f(Ttotal)
類似度の測定精度を落とすことなく
効率だけが上がっている
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
25
実験結果
SPARS-Jの類似度測定部「Luigi」として実装
対象： JDK431クラス
文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec）
主メトリクス
類似クラスタ
最終クラスタ計算コスト(sec)
未使用
1
278
05.02
[C]
21
278
00.56
[ C,M ]
85
278
00.29
[ C,M,T ]
232
278
00.16
メトリクス比較により，コストは1/5
C：サイクロマチック数
M：宣言メソッド数
T : f(Ttotal)
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
26
実験結果
SPARS-Jの類似度測定部「Luigi」として実装
対象： JDK431クラス
文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec）
主メトリクス
類似クラスタ
最終クラスタ計算コスト(sec)
未使用
1
278
05.02
[C]
21
278
00.56
[ C,M ]
85
278
00.29
[ C,M,T ]
232
278
00.16
C：サイクロマチック数
M：宣言メソッド数
T : f(Ttotal)
メトリクス比較により，コストは1/5
ハッシュキーにより，コストは1/30
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
27
実験結果
SPARS-Jの類似度測定部「Luigi」として実装
対象： JDK431クラス
文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec）
主メトリクス
類似クラスタ
最終クラスタ計算コスト(sec)
未使用
1
278
05.02
[C]
21
278
00.56
[ C,M ]
85
278
00.29
[ C,M,T ]
232
278
00.16
C：サイクロマチック数
M：宣言メソッド数
T : f(Ttotal)
メトリクス比較により，コストは1/5
ハッシュキーにより，コストは1/30
トータルでコストは1/150
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
28
まとめと今後の課題
まとめ
メトリクスを用いた類似度測定手法を提案した
比較一回当たりの低コスト化
ハッシュキーを用いることによる類似度測定回数の効率化
SPARS-Jにおける類似度測定部「Luigi」として実装し，
適用実験を行い，有効性を検証した
既存の文字列比較による類似度測定手法に比べ，十分低コ
ストかつ効率的な手法であることを確認した
今後の課題
類似度判定精度の向上
Java以外の言語への対応
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
29
SPARS-J（2/2）
Component Rankの計算では，部品間のコピー関係を把握するた
めに類似度を測定している
類似部品を一つの部品群として扱い，利用関係を合成する
評価値にコピー関係を反映させることが可能
類似
部品A
+
部品A´
合成
⇒
部品A
部品群A
これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
30

Download Report