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

類似度メトリクスを用いた
Javaソースコード間類似度測定ツールの試作
小堀一雄，山本哲男，松下誠，井上克郎（大阪大学）
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
1
背景（1/2）
ソフトウェア開発効率を飛躍的に向上するための手法として
再利用が注目されている
再利用とは新規のソースコードを書く際に，既存のソース
コードを参照し，一部手直しをして用いること
再利用を活用するためには，過去に開発されたソー
スコードに関する情報を入手することが必要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
2
背景(2/2）
インターネットの普及により大量のソースコードが
比較的容易に入手可能となった
これらのソースコードは，開発者にとって
有益な再利用部品である可能性がある
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
3
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
4
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
5
既存の手法の問題点
文字列比較を用いた類似度測定手法の問題点
類似度測定の一回当たりの計算コストが高い
類似度測定の回数が膨大（毎回、全部品総当り）
JDK430クラスの類似分類に23秒程度かかる
SPARS-Jのような大量の部品を扱うシステムにおける
類似度測定には不向き
もっと低コストな類似度測定手法が必要
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
6
研究の目的
メトリクスを用いた類似度測定手法の提案
類似度メトリクス：類似判定の定量的な基準（数値）
ソースコードの静的特性をメトリクスとして抽出
メトリクスを用いた類似比較を実現
提案手法を実装したツールの試作
JDKのJavaソースコードに対し適用実験を行う
解析精度，コストの評価を行う
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
7
提案手法の特徴
比較一回当たりのコストの低下
ソースコードの静的特性をメトリクスして抽出する
メトリクスの比較のみを用いて類似判定を行う
文字列比較より数値比較の方が低コスト
比較回数の低下
明らかに「類似でない」ものは比較対象から排除する
事前に主要なメトリクスによる分類を施す
事前排除した部品は類似であってはならない
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
8
比較一回あたりのコストを下げる手法
類似度メトリクス：類似判定の定量的基準（数値）
2つの視点から類似度メトリクスを計測する
複雑度
メトリクス：クラス内のメソッド数, サイクロマチック数（分岐数）etc
ソフトウェア部品の構造的特徴を表す
トークン構成
メトリクス：ソースコードにおける各トークンの出現数
トークン＝予約語 + 記号 + 演算子 + 識別子
（96種）（49種）（9種）（37種）（１種）
ソフトウェア部品の表層的特徴を表す
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
9
メトリクス抽出の流れ
public class sample{
int a,b,s;
char c;
public void main( ){
c = ‘m’;
if(c = = ‘m’){
s = sum(a, b);
}
else{
s = a + b;
}
複雑性
サイクロマチック数
値
2
メソッド宣言数
・
・
・
interfaceの数
トークン
値
int
void
public void sum(int p, int q){
return( p + q );
}
}
・
・
・
identifer
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
10
メトリクス抽出の流れ
public class sample{
int a,b,s;
char c;
public void main( ){
c = ‘m’;
if(c = = ‘m’){
s = sum(a, b);
}
else{
s = a + b;
}
複雑性
サイクロマチック数
メソッド宣言数
・
・
・
複雑性
メトリクス
・・
・
0
interfaceの数
トークン
値
2
2
値
int
void
public void sum(int p, int q){
return( p + q );
}
}
・
・
・
identifer
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
11
メトリクス抽出の流れ
public class sample{
int a,b,s;
char c;
public void main( ){
c = ‘m’;
if(c = = ‘m’){
s = sum(a, b);
}
else{
s = a + b;
}
複雑性
値
2
2
サイクロマチック数
メソッド宣言数
・
・
・
・・
・
0
interfaceの数
トークン
int
値
3
void
public void sum(int p, int q){
return( p + q );
}
}
・
・
・
identifer
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
12
メトリクス抽出の流れ
public class sample{
int a,b,s;
char c;
public void main( ){
c = ‘m’;
if(c = = ‘m’){
s = sum(a, b);
}
else{
s = a + b;
}
複雑性
サイクロマチック数
メソッド宣言数
・
・
・
}
・・
・
0
interfaceの数
トークン
int
void
public void sum(int p, int q){
return( p + q );
}
値
2
2
値
3
2
・
・
・
identifer
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
13
メトリクス抽出の流れ
public class sample{
int a,b,s;
char c;
public void main( ){
c = ‘m’;
if(c = = ‘m’){
s = sum(a, b);
}
else{
s = a + b;
}
複雑性
サイクロマチック数
メソッド宣言数
・
・
・
}
・・
・
0
interfaceの数
トークン
int
void
public void sum(int p, int q){
return( p + q );
}
値
2
2
値
3
2
・
・
・
・
・
・
identifer
23
Ttotal
75
トークン構成
メトリクス
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
14
類似度判定法（複雑性メトリクス）
各メトリクスの差分が対応する閾値以内に全て収まったら類似
メトリクス名
閾値
サイクロマチック数
0
メソッドの宣言数
1
メソッド呼び出し数
2
ネストの深さ
0
classの数
0
interfaceの数
0
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
15
類似度判定法（トークン構成メトリクス）
トークン
int
void
値
3
2
・
・
・
・
・
・
identifer
23
Ttotal
75
部品A
トークン
m１
int
m２
void
値
4
2
・
・
・
・
・
・
・
・
・
m96 identifer
25
76
Ttotal
部品B
96
部品A,Bの各トークンの差分の和＝ diff(A,B) ＝∑ ( Amk Bmk )
k=1
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
16
類似度判定法（トークン構成メトリクス）
トークン
int
void
値
3
2
・
・
・
・
・
・
identifer
23
Ttotal
75
トークン
m１
int
m２
void
値
4
2
・
・
・
・
・
・
・
・
・
m96 identifer
部品A
25
76
Ttotal
部品B
■部品Aと部品Bの非類似度を D(A,B) とする
D(A,B)
diff(A,B)
min(Ttotal（A）, Ttotal（B）)
＜ 0.03
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
17
類似度判定法（総合）
どちらの類似度においても，類似であると判定されなくてはならない
複雑性：A,Bのメトリクスの差が全て閾値以内
and
部品A，Bは類似部品
トークン構成：非類似度D(A,B)が0.03未満
この判定法は数値比較しか用いていない
比較一回当たりのコストを下げることが可能
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
18
提案手法の特徴
比較一回当たりのコストの低下
ソースコードの静的特性をパラメータ化して抽象化する
パラメータの比較のみを用いて類似判定を行う
文字列比較より数値比較の方が低コスト
比較回数の低下
明らかに「類似でない」ものは比較対象から排除する
事前に主要なパラメータによる分類を施す
事前排除した部品は類似であってはならない
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
19
比較回数を減らす手法
いくつかの主メトリクス値のハッシュキーを部品に持たせる
主メトリクス：類似判定の必要条件となるメトリクス
ハッシュキーの値の差が主メトリクスの閾値を超える部品
＝明らかに｢類似でない｣部品
これらを比較対象から排除することにより，比較回数
を減らすことが可能となる
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
20
ハッシュによる事前分類
メトリクス計測時に、いくつかの主メトリクス
でハッシュキーを作成する
ハッシュキー＝
(24bit)
8bit
8bit
8bit
新しく類似測定をしたい部品Pが入ってきた
時
 部品Pのハッシュキー＝[10.62.125]
 主メトリクス[A,B,C]の閾値＝[0.0.1]
主メトリクス主メトリクス主メトリクス
A
B
C
[10.62.124]
[10.62.125] この３つのキーをひく
[10.62.126]
ハッシュキーと部品を対応させたハッシュ
テーブルを構築する
[
0. 0]= null
・・
・
[ 10. 62.124]= 部品A
[ 10. 62.125]= 部品B，部品C
[ 10. 62.126]= null
・・
・
[254.254.254]= 部品Z
類似比較の対象となるのは部品
A，B，Cの3つに絞り込める
0.
DB
解析精度を落とさずに
比較回数を減らす
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
21
主メトリクスの候補
主メトリクス：類似判定の必要条件，閾値を持つ
複雑性メトリクス：各々のメトリクスが閾値を持った類似判定の必要条件
そのまま主メトリクスとして適用可能
トークン構成メトリクス：各々のメトリクスは類似判定の必要条件ではなく，
非類似度を算出する要素に過ぎない
主メトリクスとして，複雑性メトリクスしか採用しない場合
単純な構造の部品が同じ分類に入り、大きく偏る
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
22
主メトリクスの候補
トークン構成メトリクスに関する類似判定の条件
diff(A,B)
min(Ttotal（A）, Ttotal（B）) ＜ 0.03
トークン構成の差分が
Ttotalの3％未満
Ttotal（B）
この部分が全てdiffになる
Ttotal（A）
Ttotalの差が3％以上の部品は
比較対象から排除できる
⇔
部品A
部品B
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
23
主メトリクスの候補
トークン構成メトリクスに関する類似判定の条件
diff(A,B)
min(Ttotal（A）, Ttotal（B）) ＜ 0.03
トークン構成の差分が
Ttotalの3％未満
Ttotal（B）
この部分が全てdiffになる
Ttotal（A）
Ttotalの差が3％以上の部品は
比較対象から排除できる
⇔
部品A
部品B
Ttotalは閾値３％の主メトリクス
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
24
比較回数を減らす手法
複雑性メトリクス+トークン構成メトリクスの両面から主メトリクスを
採用することにより効率的に事前分類することが可能となった
主メトリクス値の閾値以内の全キーを引き，部品を絞り込む
比較回数を低下させることが可能
閾値が大きいと，キーを引く回数（DBアクセス回数）が増加する
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
25
DBアクセスに関するコスト問題
DBアクセス回数は閾値に比例して増加する
•主メトリクスの閾値＝ [0.0.1]
•主メトリクスの閾値＝ [0.0.5]
[ 0.
[
0.
0. 0]= null
・・
・
[ 10. 62. 29]= 部品A
[ 10. 62. 30]= 部品B，部品C
[ 10. 62. 31]= null
・・
・
[254.254.254]= 部品Z
DB
[
[
[
[
[
[
[
[
[
[
[
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
0.
0]= null
・
・
・
62. 25 ]= 部品H
62. 26 ]= null
62. 27 ]= null
62. 28 ]= 部品A
62. 29 ]= 部品B
62. 30 ]= 部品C，部品D
62. 31 ]= null
62. 32 ]= 部品E
62. 33 ]= null
62. 34 ]= null
62. 35 ]= 部品F,部品G
DB
・
・
・
[254.254.254]= 部品Z
DBアクセス回数＝（閾値A×２ +１）×（閾値B×２ +１）×（閾値C×２ +１）
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
26
マッピングによる解決法
主メトリクス値をマッピングして閾値を1にする
主メトリクス値＝主メトリクス値 / 閾値
[ 0.
[
[
[
[
[
[
[
[
[
[
[
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
0.
0]= null
・
・
・
62. 25 ]= 部品H
62. 26 ]= null
62. 27 ]= null
62. 28 ]= 部品A
62. 29 ]= 部品B
62. 30 ]= 部品C，部品D
62. 31 ]= null
62. 32 ]= 部品E
62. 33 ]= null
62. 34 ]= null
62. 35 ]= 部品F,部品G
・
・
・
[ 0. 0. 0]= null
・・
・
[ 10. 62. 5 ]= 部品H,A,B
[ 10. 62. 6 ]= 部品C,D,E
[ 10. 62. 7 ]= 部品F,G
・・
・
[255.255. 50]= 部品Y,Z
DB
[254.254.254]= 部品Z
閾値＝5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
27
マッピングによる解決法
主メトリクス値をマッピングして閾値を1にする
主メトリクス値＝主メトリクス値 / 閾値
[ 0.
[
[
[
[
[
[
[
[
[
[
[
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
0.
0]= null
・
・
・
62. 25 ]= 部品H
62. 26 ]= null
62. 27 ]= null
62. 28 ]= 部品A
62. 29 ]= 部品B
62. 30 ]= 部品C，部品D
62. 31 ]= null
62. 32 ]= 部品E
62. 33 ]= null
62. 34 ]= null
62. 35 ]= 部品F,部品G
・
・
・
[ 0. 0. 0]= null
・・
・
[ 10. 62. 5 ]= 部品H,A,B
[ 10. 62. 6 ]= 部品C,D,E
[ 10. 62. 7 ]= 部品F,G
・・
・
[255.255. 50]= 部品Y,Z
DB
[254.254.254]= 部品Z
閾値＝5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
28
マッピングによる解決法
主メトリクス値をマッピングして閾値を1にする
主メトリクス値＝主メトリクス値 / 閾値
[ 0.
[
[
[
[
[
[
[
[
[
[
[
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
0.
0]= null
・
・
・
62. 25 ]= 部品H
62. 26 ]= null
62. 27 ]= null
62. 28 ]= 部品A
62. 29 ]= 部品B
62. 30 ]= 部品C，部品D
62. 31 ]= null
62. 32 ]= 部品E
62. 33 ]= null
62. 34 ]= null
62. 35 ]= 部品F,部品G
・
・
・
[ 0. 0. 0]= null
・・
・
[ 10. 62. 5 ]= 部品H,A,B
[ 10. 62. 6 ]= 部品C,D,E
[ 10. 62. 7 ]= 部品F,G
・・
・
[255.255. 50]= 部品Y,Z
DB
[254.254.254]= 部品Z
閾値＝5
閾値＝１
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
29
閾値とDBアクセス回数
閾値が３％の場合（トークン構成メトリクス）
Ttotal = 40 ⇒ 39～41
Ttotal =180 ⇒ 175～185
[ 0.
[
0.
0. 0]= null
・・
・
[ 10. 62. 39]= 部品A
[ 10. 62. 40]= 部品B，部品C
[ 10. 62. 41]= null
・・
・
[254.254.254]= 部品Z
DB
[
[
[
[
[
[
[
[
[
[
[
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
10.
0.
0]= null
・
・
・
62.175]= 部品A
62.176]= null
62.177]= null
62.178]= 部品B
62.179]= 部品C
62.180]= 部品D，部品E
62.181]= null
62.182]= 部品F
62.183]= null
62.184]= 部品G
62.185]= 部品H,部品I
DB
・
・
・
[254.254.254]= 部品Z
閾値＝１
閾値＝ 5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
30
マッピングによる解決法
マッピング関数
h(Ttotal) = logｒ（Ttotal）
(r＝1 / 0.97)
h(Ttotal)は，閾値1の主メトリクスとして機能する
h(Ttotal)
6
5
4
3
2
1
Ttotal
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
31
実験結果
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 : 全トークン数
0.
0. 0]= null
・・
・
[ 10. 62.124]= 部品A
[ 10. 62.125]= 部品B，部品C
[ 10. 62.126]= null
・・
・
[254.254.254]= 部品Z
DB
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
32
実験結果
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 :全トークン数
トークン構成度+複雑度の両方で類
似と判定され、最終的に類似と判定
された部品群の数
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
33
実験結果
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 :全トークン数
類似度の測定精度を落とすことなく
効率だけが上がっている
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
34
実験結果
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 :全トークン数
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
35
実験結果
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 :全トークン数
メトリクス比較により，コストは1/5
ハッシュキーにより，コストは1/30
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
36
実験結果
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 :全トークン数
メトリクス比較により，コストは1/5
ハッシュキーにより，コストは1/30
トータルでコストは1/150
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
37
実験結果（スケーラビリティ）
主メトリクスとして [C,M,T] を用いた場合の実験結果
6
5
秒
4
3
2
1
0
0
1000
2000
3000
4000
5000
6000
部品数
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
38
まとめと今後の課題
まとめ
メトリクスを用いた類似度測定手法を提案した
比較一回当たりの低コスト化
ハッシュキーを用いることによる類似度測定回数の効率化
SPARS-Jにおける類似度測定部「Luigi」として実装し，
適用実験を行い，有効性を検証した
既存の文字列比較による類似度測定手法に比べ，十分低コ
ストかつ効率的な手法であることを確認した
今後の課題
類似度判定精度の向上
Java以外の言語への対応
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
39

Download Report