ソフトウェアの類似性の分析とその応用に関する研究

(1)

ソフトウェアの類似性の分析

とその応用に関する研究

大学院情報科学研究科

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

井上研究室

川口真司

(2)

ソフトウェアリポジトリ

ネットワーク上の開発基盤サービス

版管理システム

ML

管理システム

バグ追跡システム

掲示板

ソースコードや

ドキュメントなどの

管理を行う

開発中に発見した

_{バグの管理を行う}

ユーザの要望等を

開発者間で行われた

開発者

一般ユーザ

大量のソフトウェア

(SourceForge:

約 10

万

プロジェクト )

(3)

2005/12/21

3

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

ソフトウェアの持つ類似性

膨大な数の成果物

これまでに作成された大量のソフトウェア

大規模なソフトウェアに含まれる大量のコンポーネント、ソースコ

ード

成果物がもつ類似性とその活用

類似の定義、発見

類似の応用

ソフトウェ

ア

付属ドキュメントを用い

て

ソースコードを用いて

ソフトウェアライブ

ラリ

派生ソフトウェアの

分類

コンポーネ

ント

継承関係、利用関係、ソ

ースコード等を用いて

コンポーネントライ

ブラリ

ソフトウェアクラス

タリング

コード片

コードクローンに関する

研究

クローン削除作業の

支援、リファクタリ

(4)

ソフトウェアの類似性

GURU (Maarek

ら [46])

Unix

の各コマンドを、 man を利用して分類

IR

メソッドを利用

Ugurel

らの手法 [62]

ソフトウェアに付随するドキュメントを利用して分類

support vector machine (SVM)

_を利用

SMMT (

山本ら [64])

ソースコードそのものを直接用いて分類

CCFinder

_を利用

ソフトウェアライブラリの構築 [46, 62]

派生ソフトウェア群の分類 [64]

4.4BSD Lite

から派生した、 FreeBSD, NetBSD, OpenBSD の各バー

ジョン間の類似度を比較

(5)

コンポーネントの類似性

継承関係から (Spanoudakis ら *)

利用関係から (SPARS **)

コンポーネントのソースコードに機械学習手法を適用

LSA(

潜在的意味解析手法 ) を用いて (Maletic ら [47])

自己組織化マップを用いて (Chan ら [15])

コンポーネントライブラリの構築 (SPARS **)

ソフトウェアクラスタリング [47]

ひとつのソフトウェアを、いくつかのコンポーネント群に分割

* Giorgos Spanoudakis, Panos Constantopoulos, Measuring Similarity Between Software Artifacts 1994, Proc. of the 6th International Conference on Software Enginee

ring and Knowledge Engineering - SEKE '94, Jurmala, Latvia, June 1994.

** Katsuro Inoue, Reishi Yokomori, Tetsuo Yamamoto, Makoto Matsushita, Shinji Kusumoto, “Ranking Significance of Software Components Based on Use Relation

s”, IEEE Transactions on Software Engineering, Vol.31, No.3, pp.213-225 (2005)

(6)

コード片の類似性

コードクローン

字句解析ベース [5, 6, 7, 11, 20, 33, 39, 40, 43, 53, 55]

CCFinder (

神谷ら [33] )

CloneDr (Baxter

ら [11] )

メトリクスベース [8, 9, 10, 32, 49, 51]

メソッド単位でメトリクスを定義 (Balazinska ら [8, 9, 10])

クローン削除作業の支援

コードクローンは保守工程における重大な障害のひとつ

ある部分に修正が必要 → その部分のクローン全ての修正を検討

コードクローン分析環境 Gemini ( 植田ら *)

リファクタリング支援 ( 肥後ら **)

*

植田泰士 , 神谷年洋 , 楠本真二 , 井上克郎 , " 開発保守支援を目指したコードクローン分析環境 ", 電子情報通信学会論文誌 D-I, Vol. J86-D-I, No.

12, pp. 863-871 (2003-12).

**

肥後芳樹 , 植田泰士 , 神谷年洋 , 楠本真二 , 井上克郎 , " コードクローン解析に基づくリファクタリングの試み ", 情報処理学会論文誌 , no. 45,

vol. 5, pp. 1357-1366 (2004-5).

(7)

2005/12/21

7

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

ソフトウェアの持つ類似性

膨大な数の成果物

これまでに作成された大量のソフトウェア

大規模なソフトウェアに含まれる大量のコンポーネント、ソースコ

ード

成果物がもつ類似性とその活用

類似の定義、発見

類似の応用

ソフトウェ

ア

付属ドキュメントを用い

て

ソースコードを用いて

ソフトウェアライブ

ラリ

派生ソフトウェアの

分類

コンポーネ

ント

継承関係、利用関係、ソ

ースコード等を用いて

コンポーネントライ

ブラリ

ソフトウェアクラス

タリング

コード片

コードクローンに関する

研究

クローン削除作業の

支援、リファクタリ

(8)

論文の構成

第 1 章 : まえがき

第 2 章 : MUDABlue: ソフトウェアシステム

自動分類手法 [1-1, 1-2, 1-3, 1-4]

第 3 章 : 版管理システムを用いたクローン履

歴抽出手法 [1-5]

第 4 章 : むすび

(9)

MUDABlue:

ソフトウェア自動分類システム

[2

章 ]

ソフトウェアそのものの分類の重要性

大量のソフトウェア → 分類、整理が必要

ML

_{の議論や、掲示板やバグ追跡情報も有用}

既存のソフトウェアライブラリ構築手法は不

十分

分類先はあらかじめ用意する必要あり

分類結果は排他的

ドキュメントに依存

(10)

MUDABlue

の構成

ソフトウェア自動分類部

大量のソフトウェアを自動的に分類する

潜在的意味解析手法 LSA に基づく手法

自然言語文書の類似性を計測する手法

分類結果提示ユーザインタフェース

キーワード検索、ディレクトリ型検索の両方をサ

ポート

(11)

提案手法の特徴

1. _{階層構造も自動的に作成}

カテゴリの作成には、さまざまなライブラリ・アーキテ

クチャに関する深い知識が必要

日々新しいカテゴリが誕生

2. _{非排他的な分類}

ソフトウェアの分類には、複数個の基準が存在

ソフトウェアの用途

利用しているライブラリ、依存アーキテクチャ、等々

3. ソースコードのみを用いて分類

既存手法はソフトウェアに付属するドキュメントに基づ

いて分類

ドキュメントの量や質（特に均一性）に大きく依存

(12)

ソフトウェア 1

ソフトウェア 2

ソフトウェア 3

ソフトウェア 4

非排他的分類

エディタ

GUI (MFC)

正規表現サポート

(regexp)

表計算

エディタ

正規表現サポート

(regexp)

GUI (GTK)

表計算

GUI (GTK)

GUI (MFC)

正規表現サポート

(regexp)

エディタ

表計算

MFC

GTK

regexp

(13)

潜在的意味解析法 LSA

Latent Semantic Analysis [41, 42]

自然言語で書かれた文書、単語の類似度を計

測する

ベクトル空間モデルに従った手法の一つ

ベクトル空間モデルでは検出できない間接的

な関連の抽出を可能にしている

(14)

LSA

の例

LSA

1

2

0

0 1 0

0

2

1

1 0 0

0

3

0

1

3

1

0 0 0

0

4

0

0 0 2

0

5

0

0 1 1

2

6

0

1 0 1

1 B

A

C D

E

F

G H

1 0.3

0.7

0.9 0.4 0.3

0.2

0.3

0.3 2 0.4

1.0

1.4 0.6 0.3

0.2

0.1

0.1 3 0.6

1.5

2.3 1.0 0.4

0.2 -0.2 -0.2

4 0.1

0.1 -0.2

0.0 0.2

0.4

0.9

0.9 5 0.1

0.2 -0.2

0.0 0.4

0.6

1.5

1.4 6 0.1

0.2 -0.1

0.0 0.3

0.4

1.0

0.9 B

A

C

D

E

F

G

H

文書 1

文書 3

文書 2

A

D

B

A B

文書 4

文書 5

H

G

F

C

文書 6

G

E

C D E

H

単語頻度行列を

作成

B B F

C C

H

G G

文書ベクトル

単語ベクトル

文書間、単語間の類似度は

ベクトル間の角度の cos や、

相関係数によって表す

(15)

LSA

の効果

間接的に関連している文書間の類似度も高い

文書間の類似度がより鮮明になる

1

2

3

4

5

6

1

1.0 0.2 -0.1 -0.3 -0.3 -0.5

2

0.2

1.0 0.5 -0.5 -0.9 -0.5

3 -0.1

0.5 1.0 -0.2 -0.4 -0.5

4 -0.3 -0.5 -0.2

1.0

0.3

0.5 5 -0.3 -0.9 -0.4

0.3

1.0

0.5 6 -0.5 -0.5 -0.5

0.5

1.0

1

2

3

4

5

6

1

1.0

1.0 0.9 -0.6 -0.6 -0.5

2

1.0

1.0 1.0 -0.8 -0.8 -0.7

3

0.9

1.0 1.0 -0.8 -0.8 -0.8

4 -0.6 -0.8 -0.8

1.0

1.0 5 -0.6 -0.8 -0.8

1.0

1.0 6 -0.5 -0.7 -0.8

1.0

1.0 LSA

_適用前

LSA

_適用後

文書間の相関係数行列

(16)

識別子による分類

ソースコード中の識別子は、その動作を表している

window

_{という識別子があるプログラム文の周辺は、な}

んらかの GUI に関する操作を行っている

識別子のうち特に類似しているものを結びつけて、

それらをひとつのグループとみなして分類を行う

ソフトウェア 1

ソフトウェア 3

エディタ

GUI (MFC)

表計算

GUI (MFC)

window

cmdButton

window

menuBar

MFC

(17)

提案手法 (1/2)

2. 共起行列の作成

3. 孤立トークン ,

普遍トークンの

削除

Soft1

Soft2

Soft3

Soft4

Soft5

1. トークン

抽出

I

J

Soft6

Sof1

Soft3

Soft2

A B

Soft4

Soft5

Soft6

G

E

C D E

H

D

B

H

G

F

C C C

H

G G

A B B F

1

2

0

0 1 0

0

2

1

1 0 0

0

3

0

1

3

1

0 0 0

0

4

0

0 0 2

0

5

0

0 1 1

2

6

0

1 0 1

1 B

A

C D

E

F

G H

1

2

0

0 1 0

0

1

2

1

1 0 0

0

3

0

1

3

1

0 0 0

0

4

0

0 0 2

0

1

5

0

0 1 1

2

0

1

6

0

1 0 1

1

0

1 B

A

C D

E

F

G H

J

I

(18)

提案手法 (2/2)

B

A

G

F

1 C

2

3

4

5

6

1

2

3

4

5

6 ClusterName1

ClusterName1

ClusterName2

D

H

1

5. トークン間の類似度計測、

クラスタ分析

6. ソフトウェア

クラスタの

作成

7. クラスタ

タイトルの

作成

1 0.3

0.7

0.9 0.4 0.3

0.2

0.3

0.3 2 0.4

1.0

1.4 0.6 0.3

0.2

0.1

0.1 3 0.6

1.5

2.3 1.0 0.4

0.2 -0.2 -0.2

4 0.1

0.1 -0.2

0.0 0.2

0.4

0.9

0.9 5 0.1

0.2 -0.2

0.0 0.4

0.6

1.5

1.4 6 0.1

0.2 -0.1

0.0 0.3

0.4

1.0

0.9 B

A

C

D

E

F

G

H

1

2

0

0 1 0

0

2

1

1 0 0

0

3

0

1

3

1

0 0 0

0

4

0

0 0 2

0

5

0

0 1 1

2

6

0

1 0 1

1 B

A

C D E

F

G H

4.LSA

(19)

ケーススタディ

実験を通じて以下のことを示す

MUDABlue

システムの実際のカテゴリ描画

抽出したカテゴリの評価

抽出カテゴリの概要

既存手法との適合率、再現率の比較

テストデータ

SourceForge

_{から無作為に選んだ 6 つのジャンル}

boardgames, compilers, database, editor, videoconversion, xterm

以上の 6 ジャンルに含まれる C プログラム 41 個

計 164,102 個の識別子

孤立トークン、普遍トークンを除く 22,048 識別子を LSA の入力とし

て利用

(20)

分類結果

40 個のカテゴリ

ライブラリ、アーキテクチャに関するカテゴリの内訳

GTK(2

カテゴリ )

GUI

ライブラリ

win32(3

カテゴリ )

Windows32 API

yacc

構文解析ライブラリ

SSL

通信用ライブラリ

regexp

正規表現用ライブラリ

getopt

_{コマンドラインオプション読み取り用ライブラリ}

JNI

Java Native Interface

Python/C Python

インタプリタ拡張用インタフェース

SourceForge

のカテゴリに合致するカテゴリ

18 ライブラリ、アーキテクチャに関するカテゴリ

11

(21)

適合率、再現率の評価

GURU

IR

_{メソッドを利用}

Unix

の各コマンドを、 man を利

用して分類

Ugurel

らの手法

support vector machine (SVM)

_を

利用

ソフトウェアに付随するドキュメ

ントに対して SVM を適用

MUDABlue

は既存の研

究に対して同程度の信頼

性を保っている

(22)

考察

適合率、再現率は既存研究と同程度の水準を保っている

MUDABlue

は前提知識の入力が必要ない

MUDABlue

はカテゴリやライブラリを自動的に抽出する

ドキュメントに依存しない

非排他的な分類の実現

今後の課題

「その他」カテゴリを減らす

識別子を選別する部分の改善が必要

カテゴリタイトルをよりわかりやすく

分かりやすいものもあれば、分かりにくいものも

ライブラリに基づくカテゴリには分かりやすいタイトルがつく傾向

カテゴリの粒度をより適正に

細粒度にすぎる傾向

(23)

クローン履歴分析手法 [3 章 ]

既存のクローン抽出手法

exact

なコピーだけではなく、多少の変更があっ

てもクローンとして抽出

過去に exact にコピーされた時点の状態を

見れば明白

版管理システムが持つ履歴情報

版管理システムは、これまでにおこわなわれた変

更の履歴を全て保持

過去の任意の時点のプロダクトを取得可能

(24)

コードクローン

Clone A-1

Clone A-2

Clone A-3

Clone B-2

コードクローン（あるい

は単にクローン）

類似文字列が存在するコー

ド片

クローンの位置は ( ファイ

ル名、開始行番号、終了行

番号 ) で指定

クローンペア

クローン A-1 とクローン

A-2

_{が類似文字列であると}

きに、これらをクローンペ

アとよぶ

クローンセット

クローンペア関係において

推移関係が成り立つクロー

ンの集合

Clone B-1

(25)

履歴を考慮したクローン分析

過去にクローン関係にあったコード片の抽

出

過去の時点でのクローン解析情報

現在のクローンは、過去のどのクローンに対応

するか？

Clone A-2

Clone B’-3

Clone A-4

Clone A-3

Clone A-2

Clone A-5

Clone A-1

Clone B’-2

Clone B’-1

Clone B-2

Clone B-1

Clone A-3

Clone A-1

Clone B’-2

Clone B’-1

Clone B-2

Clone B-1

Clone A-1

Clone B-2

Clone B-1

Clone B-4

Clone B-3

Clone B-5

Clone B’-3

Clone A-3

追加

Clone A-3

追加

Clone B’-3

削除

Clone B’-3

削除

Clone A-4, A-5

追加

Clone A-4, A-5

追加

Clone B-3, B-4, B-5

が編集

されて別クローンセットに

Clone B-3, B-4, B-5

が編集

されて別クローンセットに

クローンセット B, B’ を

(26)

クローン履歴関係

Clone A

ファイル 1

Clone A

ファイル 2

Clone A

ファイル 1

ファイル 2

Clone B

ファイル 3

Clone A

V

（過去のコード片 , 現在のコード片）

のペア

クローン履歴関係

挿入

削除

CCFinder

に

よって発見さ

れたクローン

ペア

クローン関係

(27)

クローン履歴関係抽出手法 (1/2)

指定された期間 [0, t] 、間隔 Δt について期間 [0, t] を Δt ごとに

分割、それぞれの時のファイルの状態をバージョン V

0 , V

1 , ..., V

t

と

表す

過去のプロダクトの取得には版管理システム (ex. cvs, subversion, ...) を用いる

となりあうバージョン間について分析

V

0 , V

1 をリポジトリから取得

V

0 , V

1 間のクローン履歴関係を分析

V

t

をリポジトリから取得

V

t-1

, V

t

間を分析

V

・・・

V

(28)

クローン履歴関係抽出手法 (2/2)

隣あうバージョン V

t-1

, V

t

について以下を行う

1. クローン分析

クローン分析には CCFinder を使用する

クローンの行数、総行数に対する割合も計算

2. クローン履歴関係分析

1. HC

t

:

バージョン間でクローン関係に変化のない

履歴関係抽出

2. HA

t

: V

t

において新規に追加されたクローンの履

歴関係抽出

3. HT

t

: V

t

において片方が削除されたクローンの履

歴関係抽出

(29)

2-1:

クローン関係に変化のない履歴関係

抽出

Clone A

ファイル 1

Clone A

ファイル 2

Clone A

ファイル 1

ファイル 2

Clone B

ファイル 3

クローン

関係

クローン

履歴関係

Clone A

V

_t-1

V

_t

25 行番号

31

42

48

37

43

7

18 行番号

11

22

28

22

28 写像先の決定には、編集操作による行番号のズレを考慮

Vt

の各クローンについて、 Vt-1 の

「写像先」にクローンが存在す

るかどうか検索

HC

_t

HC

_t

(30)

2-2:

追加されたクローンの履歴関係

抽出

Clone A

ファイル 1

Clone A

ファイル 2

Clone A

ファイル 1

ファイル 2

Clone B

ファイル 3

クローン

関係

クローン

履歴関係

Clone A

V

_t-1

V

_t

発見したクローンに対応する部分を履歴関係とする

Vt-1

と差分との間で CCFinder を適用

HA

_t

HA

_t

(31)

2-3:

片方が削除されたクローン候補

の抽出

Clone A

ファイル 1

Clone A

ファイル 2

Clone A

ファイル 1

ファイル 2

Clone B

ファイル 3

クローン

関係

クローン

履歴関係

Clone A

V

_t-1

V

_t

行番号

HT

_t

V

_t-1

において、対応がないクローンにつ

いて、

V

_t

との対応行とテキスト比較

(32)

提案手法の特徴

となりのバージョン同士でのつ

ながり

任意の二点間の分析を行うのはコ

ストが大きい

バージョン間の diff に対して

のみクローン分析を適用

V

t-1

, V

t

全体に対して CCFinder

を適用するのはコストが大きい

各バージョンごとにクローン分

析を適用

差分情報のみからクローン情報の

類推を行わない

計算量を極力抑える

正確なクローン分析

(33)

PostgreSQL

のクローン履歴分析

1. 分離クローンセットを漏れなく抽出できているかどうか

の検証

• PostgreSQL

の src 部分を 2005/01/01 ~ 2005/06/30 の期間

、一週間ごとに解析

• _{クローンセット中のクローン数が減少している部分、時間に着}

目

• _{その時間の差分を確認して、分離クローンセットか、縮退クローンセッ}

トかを目視で判定

• _{分離クローンセットであれば、各クローンに正しくクローン履歴関係が}

抽出されているかどうかを検証

2. クローン全体の履歴

• PostgreSQL

の開発工程におけるクローンの増加量をグラフ化

• 1998

年 7 月から 2005 年 7 月の 6 年分を一月区切りで解析

(34)

縮退クローンセット調査結果

分岐クローンセット

4 本来は分岐クローンセットなのに、クローン減

少と判定

0 クローンが削除されたクローンセット

5 価値のないクローンセット

15 全 24 クローンセットを調査

誤判定はなし

15 _{箇所のクローンセットは、定数定義が連続して}

いる部分など無意味なクローン

(35)

過去に関連のあったクローンセッ

トの例

Clone B

Clone A

dbcommands.c

Clone A

Clone B

pgsql/src/backend/commands (SQL

文解釈・実行部の実装 )

schemacmds.c

functioncmds.c

tablespace.c

opclasscmds.c

aggregatecmds.c

conversioncmds.c

operatorcmds.c

aggregatecmds.c

conversioncmds.c

opclasscmds.c

opratorcmds.c

tablecmds.c

dbcommands.c

functioncmds.c

schemacmds.c

tablespace.c

pgsql/src/backend/commands/dbcommands.c 07/01 765 /*

766 * ALTER DATABASE name OWNER TO newowner 767 */

768 void

769 AlterDatabaseOwner(const char *dbname, AclId newOwnerSysId) 770 { 771 HeapTuple tuple, 772 newtuple; ・・・ 790 791 newtuple = heap_copytuple(tuple);

792 datForm = (Form_pg_database) GETSTRUCT(newtuple); 793

794 /*

795 * If the new owner is the same as the existing owner, consider the 796 * command to have succeeded. This is to be consistent with other objects. 797 */

798 if (datForm->datdba != newOwnerSysId) 799 {

800 /* changing owner's database for someone else: must be superuser */ 801 /* note that the someone else need not have any permissions */ 802 if (!superuser())

803 ereport(ERROR,

804 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 805 errmsg("must be superuser to change owner"))); 806

807 /* change owner */

808 datForm->datdba = newOwnerSysId;

809 simple_heap_update(rel, &newtuple->t_self, newtuple); 810 CatalogUpdateIndexes(rel, newtuple); 811 } 812 813 systable_endscan(scan); 814 heap_close(rel, NoLock); 815 } pgsql/src/backend/commands/aggregatecmds.c 07/01 291 /*

292 * Change aggregate owner 293 */

294 void

295 AlterAggregateOwner(List *name, TypeName *basetype, AclId newOwnerSysId) 296 {

297 Oid basetypeOid; 298 Oid procOid; ・・・

321 if (!HeapTupleIsValid(tup)) /* should not happen */

322 elog(ERROR, "cache lookup failed for function %u", procOid);

323 procForm = (Form_pg_proc) GETSTRUCT(tup); 324

325 /*

326 * If the new owner is the same as the existing owner, consider the 327 * command to have succeeded. This is for dump restoration purposes. 328 */

329 if (procForm->proowner != newOwnerSysId) 330 {

331 /* Otherwise, must be superuser to change object ownership */ 332 if (!superuser())

337 /* Modify the owner --- okay to scribble on tup because it's a copy */ 338 procForm->proowner = newOwnerSysId;

339

340 simple_heap_update(rel, &tup->t_self, tup); 341 CatalogUpdateIndexes(rel, tup); 342 } 343 344 heap_close(rel, NoLock); pgsql/src/backend/commands/dbcommands.c 08/04 765 /*

768 void

769 AlterDatabaseOwner(const char *dbname, AclId newOwnerSysId) 770 {

771 HeapTuple tuple; 772 Relation rel; ・・・

792 /*

793 * If the new owner is the same as the existing owner, consider the 794 * command to have succeeded. This is to be consistent with other objects. 795 */ 796 if (datForm->datdba != newOwnerSysId) 797 { 798 Datum repl_val[Natts_pg_database]; 799 char repl_null[Natts_pg_database]; 800 char repl_repl[Natts_pg_database]; 801 Acl *newAcl; 802 Datum aclDatum; 803 bool isNull; 804 HeapTuple newtuple; 805

810 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 811 errmsg("must be superuser to change owner"))); 812 813 memset(repl_null, ' ', sizeof(repl_null)); 814 memset(repl_repl, ' ', sizeof(repl_repl)); 815 816 repl_repl[Anum_pg_database_datdba - 1] = 'r'; 817 repl_val[Anum_pg_database_datdba - 1] = Int32GetDatum(newOwnerSysId); 818 819 /*

820 * Determine the modified ACL for the new owner. This is only 821 * necessary when the ACL is non-null.

822 */

823 aclDatum = heap_getattr(tuple,

824 Anum_pg_database_datacl, 825 RelationGetDescr(rel),

(36)

考察

分離クローンセットを漏れなく抽出できているかどう

かの検証

縮退クローンセットに的を絞って検証

過去に関係のあったクローンの例

実際に関連性が高い

手動で履歴を探索していくのは手間がかかる

分析を行うための対話的ユーザインタフェースの作成

クローン量の変遷グラフ

PostgreSQL

の開発工程ではクローン含有率は安定

→ 良好な開発パターン

ただし src/backend/command 以下では上昇傾向

→ 　危険な傾向

危険なパターン、良好なパターンの列挙

(37)

クローンの生存期間に着目した分析 * (Kim ら )

ある一定間隔ごとにクローン分析を行い、クローンの寿命を調査

クローンの生存期間によってクローンを分類

クローン分析には CCFinder を用いる

クローン履歴を利用したオリジン分析 ** （ Godfrey ら）

関数が、過去のバージョンのどの関数に由来するものかを調べる

関数の統合、分割を半自動的に検出

クローン分析はメトリクスベース

対話的な分析

利用するメトリクスは分析者が決定

* M. Kim and D. Notkin: “Using a clone genealogy extractor for understanding and supporting evolution of code

clones”, MSR 2005, Saint Louis, Missouri, pp. 17-21 (2005)

(38)

むすび

ソフトウェアリポジトリに存在する大量のソ

フトウェアから、類似性を抽出しソフトウェ

ア開発への応用を行った

ソフトウェア自動分類システム MUDABlue の

構築

事前知識なしでカテゴリを自動的に抽出し、分類

SourceForge

から得たソフトウェアの分類実験

クローン履歴抽出手法の提案

コードクローンの履歴を抽出する手法の提案

PostgreSQL

からの履歴抽出

(39)

(40)

特異値分解

特異値分解は、行列の次元

を削減する

誤差は最小二乗誤差になる

ようにする。

高次元配列の次元削減を行

うメリット

データサイズ削減

同じ値の分布をする次元

（相関の高い次元）から優

先的に一つの次元に併合さ

れる

l

b

a

2 次元データ (a, b) を 1 次元

データ (l) に削減する例

(41)

行番号の調整

f

_t

f

_t-1

f

_t-1

8

15

18

22

31

8

15

18

22

31

9

18 24 29 34

36

39 _f

t

9

18

24

29

34 挿入

削除

衝突

行番号行番号行番号行番号

衝突時には対応行が一意でない

最小、最大の推定値両方を考慮

Clone A

(42)

分析 2: PostgreSQL 全体のコード

量

クローン含有率は開発工程全体をとおして安定

(43)

分析 2: PostgreSQL コア部分のコード量

commands

_{以下のクローン率は徐々に上昇}

utils

には文字コード変換用データの大量追加

(44)

(45)

今後の研究方針

クローン以外のエンティティに対する、過去

情報を考慮した類似度測定

開発進捗度を考慮したソフトウェア類似判定

過去の開発過程を考慮したコンポーネント分類

(46)

ソフトウェアリポジトリ

版管理システム

ML

管理システム

バグ追跡システム

掲示板

ソースコードや

ドキュメントなどの

管理を行う

開発中に発見した

_{バグの管理を行う}

ユーザの要望等を

開発者間で行われた

(47)

Clone A-2

クローン履歴の活用法

Clone B’-3

Clone A-4

Clone A-3

Clone A-2

Clone A-5

Clone A-1

Clone B’-2

Clone B’-1

Clone B-2

Clone B-1

Clone A-3

Clone A-1

Clone B’-2

Clone B’-1

Clone B-2

Clone B-1

Clone A-1

Clone B-2

Clone B-1

Clone B-4

Clone B-3

Clone B-5

Clone B’-3

Clone A-3

追加

Clone A-3

追加

Clone B’-3

削除

Clone B’-3

削除

Clone A-4, A-5

追加

Clone A-4, A-5

追加

2. _{コード中に含まれるコード}

クローンの変化を分析

2. _{コード中に含まれるコード}

クローンの変化を分析

Clone B-3, B-4, B-5

が編集

されて別クローンセットに

Clone B-3, B-4, B-5

が編集

されて別クローンセットに

1. _{過去に同じクローンセットだった}

クローンセットの発見

1. _{過去に同じクローンセットだった}

クローンセットの発見

(48)

Clone A-2

クローン履歴

Clone B’-3

Clone A-4

Clone A-3

Clone A-2

Clone A-5

Clone A-1

Clone B’-2

Clone B’-1

Clone B-2

Clone B-1

Clone A-3

Clone A-1

Clone B’-2

Clone B’-1

Clone B-2

Clone B-1

Clone A-1

Clone B-2

Clone B-1

Clone B-4

Clone B-3

Clone B-5

Clone B’-3

Clone A-3

追加

Clone A-3

追加

Clone B’-3

削除

Clone B’-3

削除

Clone A-4, A-5

追加

Clone A-4, A-5

追加

2. _{ひとつのクローンセットを}

クローン発生時期から分類

2. _{ひとつのクローンセットを}

クローン発生時期から分類

3. コード中に含まれるコード

クローンの変化を分析

3. コード中に含まれるコード

クローンの変化を分析

Clone B-3, B-4, B-5

が編集

されて別クローンセットに

Clone B-3, B-4, B-5

が編集

されて別クローンセットに

1. _{過去に同じクローンセットだった}

クローンセットの発見

1. _{過去に同じクローンセットだった}

クローンセットの発見

(49)

1:

クローン分析

Clone A

ファイル 1

Clone A

ファイル 2

Clone A

ファイル 1

ファイル 2

Clone B

ファイル 3

クローン

関係

クローン

履歴関係

Clone A

V

_t-1

V

_t

V

_t

全体を CCFinder で分析

(50)

Step1:

クローン分析

Clone A

ファイル 1

Clone A

ファイル 2

Clone A

ファイル 1

ファイル 2

Clone B

ファイル 3

クローン

関係

クローン

履歴関係

Clone A

V

_t-1

V

_t

V

_t

全体を CCFinder で分析

(51)

Step2-1:

編集されていないクローンの

履歴関係抽出

Clone A

ファイル 1

Clone A

ファイル 2

Clone A

ファイル 1

ファイル 2

Clone B

ファイル 3

クローン

関係

クローン

履歴関係

Clone A

V

_t-1

V

_t

25 行番号

31

30

36

42

48

37

43

7

18 行番号

11

22

28

22

28 編集操作による行番号のズレを吸収

Vt

の各クローンについて、 Vt-1 の対応する

行にクローンが存在するかどうか検索

(52)

行番号の調整

f

_t

f

_t-1

f

_t-1

8

15

18

22

31

8

15

18

22

31

9

18 24 29 34

36

39 _f

t

9

18

24

29

34 挿入

削除

衝突

行番号行番号行番号行番号

衝突時には対応行が一意でない

最小、最大の推定値両方を考慮

Clone A

(53)

Step2-2:

追加されたクローンの

履歴関係抽出

Clone A

ファイル 1

Clone A

ファイル 2

Clone A

ファイル 1

ファイル 2

Clone B

ファイル 3

クローン

関係

クローン

履歴関係

Clone A

V

_t-1

V

_t

発見したクローンに対応する部分を履歴関係とする

Vt-1

と差分との間で CCFinder を適用

(54)

まとめと今後の課題

自動ソフトウェア分類システム MUDABlue の提案

事前知識なしでカテゴリを自動的に発見し、ソフト

ウェアをカテゴライズすることを示した

今後の課題

「その他」カテゴリを減らす

識別子を選別する部分の改善が必要

カテゴリタイトルをよりわかりやすく

分かりやすいものもあれば、分かりにくいものも

ライブラリに基づくカテゴリには分かりやすいタイトルがつく傾向

カテゴリの粒度

生成カテゴリの粒度は細粒度にすぎる傾向

(55)

まとめ

コードクローンの履歴を抽出する手法の提案

PostgreSQL

から抽出した履歴の例の提示

課題

となりのバージョンだけで分析できないクローン

履歴の抽出

一度削除されてまた後で復活したクローン

活用方法の考察

分析用ユーザインタフェースの作成

(56)

過去に関連のあったクローンセッ

トの例

Clone B

Clone A

dbcommands.c

Clone A

Clone B

2004/08/04

2004/07/01

pgsql/src/backend/commands (SQL

文解釈・実行部の実装 )

schemacmds.c

functioncmds.c

tablespace.c

opclasscmds.c

aggregatecmds.c

conversioncmds.c

operatorcmds.c

aggregatecmds.c

conversioncmds.c

opclasscmds.c

opratorcmds.c

tablecmds.c

dbcommands.c

functioncmds.c

schemacmds.c

tablespace.c

pgsql/src/backend/commands/dbcommands.c 07/01 765 /*

768 void

769 AlterDatabaseOwner(const char *dbname, AclId newOwnerSysId) 770 { 771 HeapTuple tuple, 772 newtuple; ・・・ 790 791 newtuple = heap_copytuple(tuple);

792 datForm = (Form_pg_database) GETSTRUCT(newtuple); 793

794 /*

795 * If the new owner is the same as the existing owner, consider the 796 * command to have succeeded. This is to be consistent with other objects. 797 */

798 if (datForm->datdba != newOwnerSysId) 799 {

807 /* change owner */

808 datForm->datdba = newOwnerSysId;

809 simple_heap_update(rel, &newtuple->t_self, newtuple); 810 CatalogUpdateIndexes(rel, newtuple); 811 } 812 813 systable_endscan(scan); 814 heap_close(rel, NoLock); 815 } pgsql/src/backend/commands/aggregatecmds.c 07/01 291 /*

292 * Change aggregate owner 293 */

294 void

295 AlterAggregateOwner(List *name, TypeName *basetype, AclId newOwnerSysId) 296 {

297 Oid basetypeOid; 298 Oid procOid; ・・・

321 if (!HeapTupleIsValid(tup)) /* should not happen */

322 elog(ERROR, "cache lookup failed for function %u", procOid);

323 procForm = (Form_pg_proc) GETSTRUCT(tup); 324

325 /*

326 * If the new owner is the same as the existing owner, consider the 327 * command to have succeeded. This is for dump restoration purposes. 328 */

329 if (procForm->proowner != newOwnerSysId) 330 {

331 /* Otherwise, must be superuser to change object ownership */ 332 if (!superuser())

337 /* Modify the owner --- okay to scribble on tup because it's a copy */ 338 procForm->proowner = newOwnerSysId;

339

340 simple_heap_update(rel, &tup->t_self, tup); 341 CatalogUpdateIndexes(rel, tup); 342 } 343 344 heap_close(rel, NoLock); 345 heap_freetuple(tup); 346 } pgsql/src/backend/commands/dbcommands.c 08/04 765 /*

768 void

769 AlterDatabaseOwner(const char *dbname, AclId newOwnerSysId) 770 {

771 HeapTuple tuple; 772 Relation rel; ・・・

792 /*

793 * If the new owner is the same as the existing owner, consider the 794 * command to have succeeded. This is to be consistent with other objects. 795 */ 796 if (datForm->datdba != newOwnerSysId) 797 { 798 Datum repl_val[Natts_pg_database]; 799 char repl_null[Natts_pg_database]; 800 char repl_repl[Natts_pg_database]; 801 Acl *newAcl; 802 Datum aclDatum; 803 bool isNull; 804 HeapTuple newtuple; 805

810 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 811 errmsg("must be superuser to change owner"))); 812 813 memset(repl_null, ' ', sizeof(repl_null)); 814 memset(repl_repl, ' ', sizeof(repl_repl)); 815 816 repl_repl[Anum_pg_database_datdba - 1] = 'r'; 817 repl_val[Anum_pg_database_datdba - 1] = Int32GetDatum(newOwnerSysId); 818 819 /*

820 * Determine the modified ACL for the new owner. This is only 821 * necessary when the ACL is non-null.

822 */

823 aclDatum = heap_getattr(tuple,

824 Anum_pg_database_datacl, 825 RelationGetDescr(rel),