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

Slides:



Advertisements
Similar presentations
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 1 ソフトウェア部品推薦のための.
Advertisements

背景 ソフトウェアの大規模化・複雑化 生産性と品質の向上 ↓ オブジェクト指向分析設計の適用 開発ツールの投入.
ソースコードの編集内容を入力とした ソフトウェア部品の自動検索
利用実績に基づくソフトウェア部品検索システムSPARS-J
メソッド名とその周辺の識別子の 相関ルールに基づくメソッド名変更支援手法
Graduate School of Information Science and Technology, Osaka
ソースコードの静的解析による ソフトウェア保守支援に関する研究
ソースコードの利用関係を用いた 再利用性評価手法の提案
Java ソフトウェア部品検索システム SPARS-J のための リポジトリ自動更新機能の実現
ソフトウェア部品間の利用関係を用いた 再利用性評価手法の提案
プログラム実行履歴を用いたトランザクションファンクション抽出手法
プログラム実行時情報を用いたトランザクションファンクション抽出手法
ソースコードの変更履歴における メトリクス値の変化を用いた ソフトウェアの特性分析
静的情報と動的情報を用いた プログラムスライス計算法
オブジェクト指向プログラムのための 動的結合メトリクスの評価
Javaソフトウェア部品 解析・検索システムSPARS-Jの構築
メソッド間の依存関係を利用した プログラム理解支援手法の提案と実現
Javaクラスの利用関係を用いた ソフトウェア部品のカテゴリ階層構築法
コードクローンに含まれるメソッド呼び出しの 変更度合の分析
コードクローンに含まれるメソッド呼び出しの 変更度合の調査
識別子の命名支援を目的とした動詞-目的語関係の辞書構築
ソードコードの編集に基づいた コードクローンの分類とその分析システム
Javaソースコード蓄積・ 検索システムSPARS-Jの概要
類似度を用いたプログラムの再利用性尺度の提案と実現
動的情報を利用したソフトウェア 部品評価手法
ソフトウェアを取り巻く環境の変化がメトリクスに及ぼす影響について
利用関係に基づく類似度を用いたJavaコンポーネント分類ツールの作成
ソフトウェア部品分類手法への コンポーネントランク法の応用
実行時情報に基づく OSカーネルのコンフィグ最小化
Javaプログラムの変更を支援する 影響波及解析システム
コードクローン検出ツールを用いた ソースコード分析システムの試作と プログラミング演習への適用
利用実績に基づくソフトウェア部品検索システムSPARS-J
TIME SIGNAL: 集合知を利用した赤信号点灯時間の取得手法
コンポーネントランク法を用いたJavaクラス分類手法の提案
Javaを対象としたソフトウェア部品 検索システムSPARS-Jの実験的評価
ソフトウェア保守性を評価する メトリクス間の関連分析
オープンソース開発支援のための ソースコード及びメールの履歴対応表示システム
ソースコードの特徴量を用いた機械学習による メソッド抽出リファクタリング推薦手法
オープンソース開発支援のための リビジョン情報と電子メールの検索システム
コードクローンに対する一貫性のない変更に起因する欠陥の検出
Token Comparison Approach to Detect Code Clone-related Bugs
ハッシュ値比較による Javaバイトコードに含まれる ライブラリの検出手法
Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
バイトコードを単位とするJavaスライスシステムの試作
Javaソフトウェア部品検索システムSPARS-Jの実験的評価
○ 後藤 祥1,吉田 則裕2 ,井岡 正和1 ,井上 克郎1 1大阪大学 2奈良先端科学技術大学院大学
類似度メトリクスを用いた Javaソースコード間類似度測定ツールの試作
コードクローン分類の詳細化に基づく 集約パターンの提案と評価
Javaバーチャルマシンを利用した 動的依存関係解析手法の提案
コーディングパターンの あいまい検索の提案と実装
JAVAバイトコードにおける データ依存解析手法の提案と実装
ソフトウェアプロダクト集合に対する 派生関係木の構築
Q3 On the value of user preferences in search-based software engineering: a case study in software product lines Abdel Salam Sayyad (West Virginia University,
福岡工業大学 情報工学部 情報工学科 種田研究室 于 聡
プログラムスライスを用いた凝集度メトリクスに基づく 類似メソッド集約候補の順位付け手法
設計情報の再利用を目的とした UML図の自動推薦ツール
依存関係の局所性を利用した プログラム依存グラフの 効率的な構築法
ソースコードの差分を用いた関数呼び出し パターンの抽出手法の提案と実装
クローン検出ツールを用いた ソフトウェアシステムの類似度調査
メソッドの同時更新履歴を用いたクラスの機能別分類法
欠陥検出を目的とした類似コード検索法 吉田則裕,石尾隆,松下誠,井上克郎 大阪大学 大学院情報科学研究科
Webページタイプによるクラスタ リングを用いた検索支援システム
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
複雑度メトリクスを用いた JAVAプログラム品質特性の実験的評価
回帰テストにおける実行系列の差分の効率的な検出手法
ソースコードの利用関係を用いた 再利用性評価手法の提案
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
オブジェクト指向メトリクスを用いた 開発支援に関する研究 --- VC++とMFCを用いた開発を対象として ---
Presentation transcript:

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

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

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

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

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

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.

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

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

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

類似度判定法(トークン構成メトリクス) ∑ ∑ 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の場合)

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

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

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

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

Ttotalをハッシュキーに適応するときの問題点 類似判定の条件 diff(A,B) トークンの差分が Ttotalの3%以内 < 0.03 min(Ttotal(A), Ttotal(B)) Ttotal =30 ⇒ 29~31 Ttotal =150 ⇒ 145~155 DB [ 0. 0. 0]= null [ 10. 62.145]= 部品A [ 10. 62.146]= null [ 10. 62.147]= null [ 10. 62.148]= 部品B [ 10. 62.149]= 部品C [ 10. 62.150]= 部品D,部品E [ 10. 62.151]= null [ 10. 62.152]= 部品F [ 10. 62.153]= null [ 10. 62.154]= 部品G [ 10. 62.155]= 部品H,部品I [255.255.255]= 部品Z ・ DB [ 0. 0. 0]= null [ 10. 62. 29]= 部品A [ 10. 62. 30]= 部品B,部品C [ 10. 62. 31]= null [255.255.255]= 部品Z ・

ハッシュ関数を用いた解決法 ハッシュ関数 h(Ttotal) を用いた加工 |h(Ttotal) - h(Ttotal×0.97)|≦ 1  log1.04(Ttotal) h(Ttotal) 6 5 4 3 2 1 Ttotal Ttotal

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

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

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

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

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

h(Ttotal)は,閾値1の主メトリクスとして機能する ハッシュ関数を用いた解決法 ハッシュ関数 h(Ttotal) を用いた加工 |h(Ttotal) - h(Ttotal×0.97)|≦ 1 |h(Ttotal×1.03) - h(Ttotal)|≦ 1 h(Ttotal) h(Ttotal)は,閾値1の主メトリクスとして機能する 6 5 4 3 2 1 Ttotal

実験結果 文字列比較を用いた類似度測定ツールの計算コスト: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 [ 0. 0. 0]= null [ 10. 62.124]= 部品A [ 10. 62.125]= 部品B,部品C [ 10. 62.126]= null [255.255.255]= 部品Z ・ C:サイクロマチック数 M:宣言メソッド数 T : f(Ttotal)

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) トークン構成度+複雑度の両方で類似と判定され、最終的に類似と判定された部品群の数

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) 類似度の測定精度を落とすことなく 効率だけが上がっている

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)

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)

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

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

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