ソースコードの静的特性を用いた Javaプログラム間類似度測定ツールの試作

Presentation on theme: "ソースコードの静的特性を用いた Javaプログラム間類似度測定ツールの試作"— Presentation transcript:

1 ソースコードの静的特性を用いた Javaプログラム間類似度測定ツールの試作
基礎工学部 情報科学科 井上研究室 小堀 一雄

2 背景 ソフトウェアを収集して 再利用部品検索システムを構築 ソフトウェア開発効率を飛躍的に向上するための手法として、再利用が注目されている
再利用とは既存の類似ソフトウェア部品を参照し，一部手直しをして用いること インターネットの普及により大量のソースコードが比較的容易に入手可能となった 再利用を活用するためには，過去に開発された類似なソフトウェア部品に関する情報を入手することが必要 これらのソースコードは，開発者にとって 有益な再利用部品である可能性がある ソフトウェアを収集して 再利用部品検索システムを構築

3 背景 ソフトウェアを収集して 再利用部品検索システムを構築 ソフトウェア開発効率を飛躍的に向上するための手法として、再利用が注目されている
再利用とは既存の類似ソフトウェア部品を参照し，一部手直しをして用いること インターネットの普及により大量のソースコードが比較的容易に入手可能となった 再利用を活用するためには，過去に開発された類似なソフトウェア部品に関する情報を入手することが必要 これらのソースコードは，開発者にとって 有益な再利用部品である可能性がある ソフトウェアを収集して 再利用部品検索システムを構築

4 背景 ソフトウェアを収集して 再利用部品検索システムを構築 ソフトウェア開発効率を飛躍的に向上するための手法として、再利用が注目されている
再利用とは既存の類似ソフトウェア部品を参照し，一部手直しをして用いること インターネットの普及により大量のソースコードが比較的容易に入手可能となった 再利用を活用するためには，過去に開発された類似なソフトウェア部品に関する情報を入手することが必要 これらのソースコードは，開発者にとって 有益な再利用部品である可能性がある ソフトウェアを収集して 再利用部品検索システムを構築

5 背景 ソフトウェアを収集して 再利用部品検索システムを構築 ソフトウェア開発効率を飛躍的に向上するための手法として、再利用が注目されている
再利用とは既存の類似ソフトウェア部品を参照し，一部手直しをして用いること インターネットの普及により大量のソースコードが比較的容易に入手可能となった 再利用を活用するためには，過去に開発された類似なソフトウェア部品に関する情報を入手することが必要 これらのソースコードは，開発者にとって 有益な再利用部品である可能性がある ソフトウェアを収集して 再利用部品検索システムを構築

6 SPARS-J（1/2） SPARS-J 利用実績に基づくソフトウェア部品検索システム システムの特徴 対象：Javaプログラムソースコード
（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.

7 これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた
SPARS-J（2/2） Component Rankの計算では，部品間のコピー関係を把握するために類似度を測定している 類似部品を一つの部品群として扱い，利用関係を合成する 評価値にコピー関係を反映させることが可能 B D B D 類似 合成 + 部品A 部品A´ 部品群A C E F C E F これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた

8 問題と研究の目的 文字列比較を用いた類似度測定手法の問題点 類似度測定の一回当たりの計算コストが高い
新しい部品が入ってきた場合、毎回全部品に対して比較を行わなくてはならない SPARS-Jのような大量の部品を対象とした類似度測定には不向きである より低コストな類似度測定手法が必要

9 類似度メトリクスを用いた類似度測定手法 類似度メトリクス：類似判定の定量的基準（数値） 2つの視点から類似度メトリクスを計測する
トークン構成 メトリクス ： ソースコードにおける各トークンの出現数 トークン ＝ 予約語 + 記号 + 演算子 + 識別子 （96種） （49種） （9種） （37種） （１種） ソフトウェア部品の表層的特徴を表す 複雑度 メトリクス ：クラス内のメソッド数, サイクロマチック数（分岐の数）など ソフトウェア部品の構造的特徴を表す 数値の比較なのでコストの低下が期待できる

10 類似度判定法（トークン構成メトリクス） ∑ ∑ D(A,B) D(A,B) ＜ 0.03 なら類似と判定 Ttotal（X） ( )
部品Xのトークン構成メトリクス ＝（Xm1,・・・,Xmn) n ∑ 部品X の全トークン数 ＝ Ttotal（X） ＝ ( ) Xmk k=1 n ∑ diff(A,B) ( Amk Bmk ) 部品A,Bの各トークンの差分の和 ＝ ＝ k=1 ■部品Aと部品Bの非類似度を D（A,B) とする diff(A,B) D(A,B) min(Ttotal（A）, Ttotal（B）) D(A,B) ＜ 0.03 なら類似と判定 （SPARS-Jの場合）

11 類似度判定法（複雑度メトリクス） 各メトリクスの差分が対応する閾値以内に収まったら類似 and 部品AとBは類似部品である メトリクス名
サイクロマチック数 メソッドの宣言数 1 メソッド呼び出し数 2 ネストの深さ “class”トークン数 “interface”トークン数 トークン構成度：0.03未満 複雑度：全て閾値以内 and 部品AとBは類似部品である 事前にこのメトリクスと閾値を用いて比較対象を絞り込めないか？ このメトリクス値が閾値以内でないと最終的に類似とは判定されない

12 類似度判定法（複雑度メトリクス） 各メトリクスの差分が対応する閾値以内に収まったら類似 メトリクス名 閾値 サイクロマチック数
メソッドの宣言数 1 メソッド呼び出し数 2 ネストの深さ “class”トークン数 “interface”トークン数

13 類似度判定法 2つのメトリクスが閾値以内なら類似していると判定 and 部品AとBは類似部品である トークン構成度：0.03未満
複雑度：全て閾値以内 and 部品AとBは類似部品である 新しい部品が入ってきた場合、全部に対して比較計算をしないとならない 結果に直接影響を与えるメトリクス（＝主メトリクス） をキーとしてハッシュを利用し、事前に分類をする．

14 類似度比較回数の効率化 DB メトリクス計測時に、いくつかの主メトリクスでハッシュキーを作成する 新しく類似測定をしたい部品Pが入ってきた時
主メトリクス[A,B,C]の閾値＝[0.0.1] ハッシュキー ＝ 8bit 8bit 8bit (24bit) 主メトリクスA 主メトリクス B 主メトリクス C 類似比較の対象となるのは部品A，B，Cの3つ ハッシュキーと部品を対応させたデータベースを構築 最終結果を変えずに効率を上げることが可能 [ ]= null [ ]= 部品A [ ]= 部品B，部品C [ ]= null [ ]= 部品Z ・ ・ ・ DB ・ ・ ・

15 Ttotalをハッシュキーに適応するときの問題点
類似判定の条件 diff(A,B) トークンの差分が Ttotalの3％以内 ＜ 0.03 min(Ttotal（A）, Ttotal（B）) Ttotal =30　⇒ 29～31 Ttotal =150　⇒ 145～155 DB [ ]= null [ ]= 部品A [ ]= null [ ]= null [ ]= 部品B [ ]= 部品C [ ]= 部品D，部品E [ ]= null [ ]= 部品F [ ]= null [ ]= 部品G [ ]= 部品H,部品I [ ]= 部品Z ・ DB [ ]= null [ ]= 部品A [ ]= 部品B，部品C [ ]= null [ ]= 部品Z ・

16 ハッシュ関数を用いた解決法 ハッシュ関数 h(Ttotal) を用いた加工 ｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
　log1.04（Ttotal） h(Ttotal) 6 5 4 3 2 1 Ttotal Ttotal

17 ハッシュ関数を用いた解決法 ハッシュ関数 h(Ttotal) を用いた加工 ｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
6 5 4 3 2 1 Ttotal Ttotal×0.97 Ttotal×1.03

18 ハッシュ関数を用いた解決法 ハッシュ関数 h(Ttotal) を用いた加工 ｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
6 5 4 3 2 1 Ttotal Ttotal

19 ハッシュ関数を用いた解決法 ハッシュ関数 h(Ttotal) を用いた加工 ｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
6 5 4 3 2 1 Ttotal Ttotal×0.97 Ttotal×1.03

20 ハッシュ関数を用いた解決法 ハッシュ関数 h(Ttotal) を用いた加工 ｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
6 5 4 3 2 1 Ttotal Ttotal

21 ハッシュ関数を用いた解決法 ハッシュ関数 h(Ttotal) を用いた加工 ｜h(Ttotal) － h(Ttotal×0.97)｜≦ １
6 5 4 3 2 1 Ttotal Ttotal×0.97 Ttotal×1.03

22 h(Ttotal)は，閾値1の主メトリクスとして機能する
ハッシュ関数を用いた解決法 ハッシュ関数 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

23 実験結果 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） DB SPARS-Jの類似度測定部「Luigi」として実装
対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 DB [ ]= null [ ]= 部品A [ ]= 部品B，部品C [ ]= null [ ]= 部品Z ・ C：サイクロマチック数 M：宣言メソッド数 T : f(Ttotal)

24 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 C：サイクロマチック数 M：宣言メソッド数 T : f(Ttotal) トークン構成度+複雑度の両方で類似と判定され、最終的に類似と判定された部品群の数

25 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 C：サイクロマチック数 M：宣言メソッド数 T : f(Ttotal) 類似度の測定精度を落とすことなく 効率だけが上がっている

26 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） メトリクス比較により，コストは1/5 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 C：サイクロマチック数 M：宣言メソッド数 T : f(Ttotal)

27 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 ハッシュキーにより，コストは1/30 メトリクス比較により，コストは1/5 C：サイクロマチック数 M：宣言メソッド数 T : f(Ttotal)

28 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） トータルでコストは1/150 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 メトリクス比較により，コストは1/5 C：サイクロマチック数 M：宣言メソッド数 T : f(Ttotal) ハッシュキーにより，コストは1/30

29 まとめと今後の課題 まとめ 今後の課題 メトリクスを用いた類似度測定手法を提案した
比較一回当たりの低コスト化 ハッシュキーを用いることによる類似度測定回数の効率化 SPARS-Jにおける類似度測定部「Luigi」として実装し，適用実験を行い，有効性を検証した 既存の文字列比較による類似度測定手法に比べ，十分低コストかつ効率的な手法であることを確認した 今後の課題 類似度判定精度の向上 Java以外の言語への対応

30 これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた
SPARS-J（2/2） Component Rankの計算では，部品間のコピー関係を把握するために類似度を測定している 類似部品を一つの部品群として扱い，利用関係を合成する 評価値にコピー関係を反映させることが可能 類似 部品A 部品群A 部品A 部品A´ 合成 + ⇒ これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた