スライド 1

ソフトウェアの類似性の分析とその
応用に関する研究
大学院情報科学研究科
コンピュータサイエンス専攻
井上研究室
川口真司
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
1
ソフトウェアリポジトリ
ソースコードや
ドキュメントなどの
開発中に発見した
ネットワーク上の開発基盤サービス
管理を行う
バグの管理を行う
大量のソフトウェア
版管理システム
バグ追跡システム
(SourceForge: 約 10 万
プロジェクト)
一般ユーザ
開発者
ソフトウェアリポジトリ
掲示板
ユーザの要望等を
2005/12/21
受け付ける
ML管理システム
開発者間で行われた
議論を保存
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
2
ソフトウェアの持つ類似性
膨大な数の成果物
これまでに作成された大量のソフトウェア
大規模なソフトウェアに含まれる大量のコンポーネント、ソースコード
成果物がもつ類似性とその活用
ソフトウェア
類似の定義、発見
付属ドキュメントを用いて
ソースコードを用いて
コンポーネント継承関係、利用関係、ソー
スコード等を用いて
コード片
コードクローンに関する研究
類似の応用
ソフトウェアライブラリ
派生ソフトウェアの分類
コンポーネントライブラリ
ソフトウェアクラスタリング
クローン削除作業の支
援、リファクタリング
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
3
ソフトウェアの類似性
GURU (Maarek ら [46])
Unix の各コマンドを、man を利用して分類
IR メソッドを利用
Ugurel らの手法 [62]
ソフトウェアに付随するドキュメントを利用して分類
support vector machine (SVM) を利用
SMMT (山本ら [64])
ソースコードそのものを直接用いて分類
CCFinder を利用
ソフトウェアライブラリの構築 [46, 62]
派生ソフトウェア群の分類 [64]
4.4BSD Lite から派生した、FreeBSD, NetBSD, OpenBSD の各バージョン
間の類似度を比較
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
4
コンポーネントの類似性
継承関係から (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
Engineering 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
Relations”, IEEE Transactions on Software Engineering, Vol.31, No.3, pp.213-225 (2005)
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
5
コード片の類似性
コードクローン
字句解析ベース [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. 863871 (2003-12).
** 肥後芳樹, 植田泰士, 神谷年洋, 楠本真二, 井上克郎, "コードクローン解析に基づくリファクタリングの試み", 情報処理学会論文誌, no. 45, vol. 5, pp. 13571366 (2004-5).
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
6
ソフトウェアの持つ類似性
膨大な数の成果物
これまでに作成された大量のソフトウェア
大規模なソフトウェアに含まれる大量のコンポーネント、ソースコード
成果物がもつ類似性とその活用
ソフトウェア
類似の定義、発見
付属ドキュメントを用いて
ソースコードを用いて
コンポーネント継承関係、利用関係、ソー
スコード等を用いて
コード片
コードクローンに関する研究
類似の応用
ソフトウェアライブラリ
派生ソフトウェアの分類
コンポーネントライブラリ
ソフトウェアクラスタリング
クローン削除作業の支
援、リファクタリング
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
7
論文の構成
第1章: まえがき
第2章: MUDABlue: ソフトウェアシステム自動分類
手法 [1-1, 1-2, 1-3, 1-4]
第3章: 版管理システムを用いたクローン履歴抽出
手法 [1-5]
第4章: むすび
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
8
MUDABlue: ソフトウェア自動分類システム [2章]
ソフトウェアそのものの分類の重要性
大量のソフトウェア → 分類、整理が必要
ML の議論や、掲示板やバグ追跡情報も有用
既存のソフトウェアライブラリ構築手法は不十分
分類先はあらかじめ用意する必要あり
分類結果は排他的
ドキュメントに依存
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
9
MUDABlue の構成
ソフトウェア自動分類部
大量のソフトウェアを自動的に分類する
潜在的意味解析手法 LSA に基づく手法
自然言語文書の類似性を計測する手法
分類結果提示ユーザインタフェース
キーワード検索、ディレクトリ型検索の両方をサポート
Unifiable Cluster Map 手法による描画
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
10
提案手法の特徴
1. 階層構造も自動的に作成
カテゴリの作成には、さまざまなライブラリ・アーキテクチャに関する
深い知識が必要
日々新しいカテゴリが誕生
2. 非排他的な分類
ソフトウェアの分類には、複数個の基準が存在
ソフトウェアの用途
利用しているライブラリ、依存アーキテクチャ、等々
3. ソースコードのみを用いて分類
既存手法はソフトウェアに付属するドキュメントに基づいて分類
ドキュメントの量や質（特に均一性）に大きく依存
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
11
非排他的分類
regexp
エディタ
表計算
GUI (MFC)
GUI (MFC)
正規表現サポート
(regexp)
正規表現サポート
(regexp)
ソフトウェア3
ソフトウェア1
MFC
エディタ
表計算
GUI (GTK)
GUI (GTK)
正規表現サポート
(regexp)
ソフトウェア2
ソフトウェア4
GTK
2005/12/21
エディタ
表計算
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
12
潜在的意味解析法 LSA
Latent Semantic Analysis [41, 42]
自然言語で書かれた文書、単語の類似度を計測
する
ベクトル空間モデルに従った手法の一つ
ベクトル空間モデルでは検出できない間接的な関連
の抽出を可能にしている
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
13
LSA の例
文書1
文書4
A B B F
文書2
B
文書ベクトル
文書5
A B C D E
文書3
G G
F G H H
単語頻度行列を
文書間、単語間の類似度は
文書6
Cベクトル間の角度の
C C D
E G H
cos作成
や、
相関係数によって表す
単語ベクトル
A
B
C
D
E
F
G H
1
1
2
0
0
0
1
0
0
2
1
1
1
1
1
0
0
0
3
0
1
3
1
0
0
0
0
4
0
0
0
0
0
0
2
0
5
0
0
0
0
0
1
1
2
6
0
0
0
0
1
0
1
1
LSA
A
B
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
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
14
LSA の効果
間接的に関連している文書間の類似度も高い
文書間の類似度がより鮮明になる
文書間の相関係数行列
1
2
3
4
5
6
1
2
3
4
5
6
1
1.0
0.2
-0.1
-0.3
-0.3
-0.5
1
1.0
1.0
0.9
-0.6
-0.6
-0.5
2
0.2
1.0
0.5
-0.5
-0.9
-0.5
2
1.0
1.0
1.0
-0.8
-0.8
-0.7
3
-0.1
0.5
1.0
-0.2
-0.4
-0.5
3
0.9
1.0
1.0
-0.8
-0.8
-0.8
4
-0.3
-0.5
-0.2
1.0
0.3
0.5
4
-0.6
-0.8
-0.8
1.0
1.0
1.0
5
-0.3
-0.9
-0.4
0.3
1.0
0.5
5
-0.6
-0.8
-0.8
1.0
1.0
1.0
6
-0.5
-0.5
-0.5
0.5
0.5
1.0
6
-0.5
-0.7
-0.8
1.0
1.0
1.0
LSA適用前
LSA適用後
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
15
識別子による分類
ソースコード中の識別子は、その動作を表している
window という識別子があるプログラム文の周辺は、なんらかの
GUI に関する操作を行っている
識別子のうち特に類似しているものを結びつけて、それらをひ
とつのグループとみなして分類を行う
エディタ
window
cmdButton
2005/12/21
表計算
menuBar
window
GUI (MFC)
GUI (MFC)
ソフトウェア1
ソフトウェア3
MFC
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
16
提案手法(1/2)
Sof1
Soft1 Soft4
A B B F
Soft2 Soft5
J
Soft2
1.トークン
抽出
Soft3 Soft6
Soft4
G G
J
Soft5
A B C D E
Soft3
I
F G H H
J
Soft6
B C C C D
E G H J
2.共起行列の作成
I
J
0
0
1
0
0
0
0
0
0
0
0
2
0
0
1
0
1
0
A
B
C
D
E
F
G H
A
B
C
D
E
F
G H
1
1
2
0
0
0
1
0
1
1
2
0
0
0
1
0
0
2
1
1
1
1
1
0
0
2
1
1
1
1
1
0
0
0
3
0
1
3
1
0
0
0
3
0
1
3
1
0
0
0
0
4
0
0
0
0
0
1
1
4
0
0
0
0
0
0
2
0
5
0
0
0
1
2
0
1
5
0
0
0
0
0
1
1
2
6
0
0
0
1
1
0
1
6
0
0
0
0
1
0
1
1
3.孤立トークン,
普遍トークンの
削除
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
17
提案手法(2/2)
A
B
C
D
E
F
G H
1
1
2
0
0
0
1
0
0
2
1
1
1
1
1
0
0
0
3
0
1
3
1
0
0
0
4
0
0
0
0
0
0
5
0
0
0
0
0
6
0
0
0
0
1
A
B
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
0
3
0.6
1.5
2.3
1.0
0.4
0.2
-0.2
-0.2
2
0
4
0.1
0.1
-0.2
0.0
0.2
0.4
0.9
0.9
1
1
2
5
0.1
0.2
-0.2
0.0
0.4
0.6
1.5
1.4
0
1
1
6
0.1
0.2
-0.1
0.0
0.3
0.4
1.0
0.9
1
2
3
4.LSA
5.トークン間の類似度計測、
クラスタ分析
D
A B C
F G
1
H
2
3
ClusterName1
6.ソフトウェア
クラスタの
作成
1
4
5
6
7.クラスタ
タイトルの
作成
1
4
5
6
ClusterName2
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
18
ケーススタディ
実験を通じて以下のことを示す
MUDABlue システムの実際のカテゴリ描画
抽出したカテゴリの評価
抽出カテゴリの概要
既存手法との適合率、再現率の比較
テストデータ
SourceForge から無作為に選んだ 6 つのジャンル
boardgames, compilers, database, editor, videoconversion, xterm
以上の 6 ジャンルに含まれる C プログラム 41 個
計 164,102 個の識別子
孤立トークン、普遍トークンを除く 22,048 識別子を LSA の入力として利用
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
19
分類結果
40 個のカテゴリ
SourceForge のカテゴリに合致するカテゴリ
ライブラリ、アーキテクチャに関するカテゴリ
18
11
はずれのカテゴリ
11
ライブラリ、アーキテクチャに関するカテゴリの内訳
GTK(2 カテゴリ)
win32(3 カテゴリ)
yacc
SSL
regexp
getopt
JNI
Python/C
GUI ライブラリ
Windows32 API
構文解析ライブラリ
SSL 通信用ライブラリ
正規表現用ライブラリ
コマンドラインオプション読み取り用ライブラリ
Java Native Interface
Python インタプリタ拡張用インタフェース
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
20
適合率、再現率の評価
GURU
1
IR メソッドを利用
Unix の各コマンドを、man を利用して
分類
Precision
0.8
Ugurel らの手法
0.6
support vector machine (SVM) を
利用
ソフトウェアに付随するドキュメントに対
して SVM を適用
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
Recall
MUDABlue
GURU
Ugurel
MUDABlue は既存の研
究に対して同程度の信頼
性を保っている
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
21
考察
適合率、再現率は既存研究と同程度の水準を保っている
MUDABlue は前提知識の入力が必要ない
MUDABlue はカテゴリやライブラリを自動的に抽出する
ドキュメントに依存しない
非排他的な分類の実現
今後の課題
「その他」カテゴリを減らす
識別子を選別する部分の改善が必要
カテゴリタイトルをよりわかりやすく
分かりやすいものもあれば、分かりにくいものも
ライブラリに基づくカテゴリには分かりやすいタイトルがつく傾向
カテゴリの粒度をより適正に
細粒度にすぎる傾向
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
22
クローン履歴分析手法 [3章]
既存のクローン抽出手法
exact なコピーだけではなく、多少の変更があってもクロー
ンとして抽出
過去に exact にコピーされた時点の状態を見れば
明白
版管理システムが持つ履歴情報
版管理システムは、これまでにおこわなわれた変更の履
歴を全て保持
過去の任意の時点のプロダクトを取得可能
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
23
コードクローン
コードクローン（あるいは単に
クローン）
類似文字列が存在するコー
ド片
クローンの位置は (ファイル名、
開始行番号、終了行番号)
で指定
クローンペア
クローンA-1 とクローンA-2 が
類似文字列であるときに、こ
れらをクローンペアとよぶ
Clone A-1
Clone A-3
Clone A-2
Clone B-2
Clone B-1
クローンセット
クローンペア関係において推
移関係が成り立つクローンの
集合
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
24
履歴を考慮したクローン分析
過去にクローン関係にあったコード片の抽出
過去の時点でのクローン解析情報
現在のクローンは、過去のどのクローンに対応するか？
Clone A-3 追加
Clone A-1
Clone A-1
Clone B-1
Clone B-1
Clone A-3
Clone A-1
Clone B-1
Clone A-3
Clone A-4
Clone A-4, A-5 追加
Clone A-2
Clone B-2
Clone B-3
Clone A-2
Clone B-5
Clone B-4
Clone B-2
Clone B’-3
Clone A-2
Clone B’-2
Clone B’-1
Clone B’-3
Clone B-3, B-4, B-5 が編集
されて別クローンセットに
2005/12/21
Clone B’-2
Clone B-2
Clone A-5
Clone B’-1
Clone B’-3 削除
クローンセット B, B’ を
「分離クローンセット」と呼ぶ
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
25
クローン履歴関係
クローン履歴関係（過去のコード片, 現在のコード片）のペア
ファイル1
ファイル1
挿入
Clone A
Clone A
Clone A
クローン関係
CCFinder に
よって発見され
たクローンペア
ファイル2
ファイル2
Clone A
Clone A
ファイル3
Clone B
2005/12/21
削除
ファイル3
Clone B
Clone B
Vt-1
Vt
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
26
クローン履歴関係抽出手法(1/2)
指定された期間 [0, t]、間隔Δt について期間 [0, t] を Δt ごとに分割、
それぞれの時のファイルの状態をバージョン V0, V1, ..., Vt と表す
過去のプロダクトの取得には版管理システム (ex. cvs, subversion, ...) を用いる
となりあうバージョン間について分析
V0, V1 をリポジトリから取得
V0, V1 間のクローン履歴関係を分析
Vt をリポジトリから取得
Vt-1, Vt 間を分析
・・・
V0
V1
Vt-1
Vt
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
27
クローン履歴関係抽出手法(2/2)
隣あうバージョン Vt-1, Vt について以下を行う
1. クローン分析
クローン分析には CCFinder を使用する
クローンの行数、総行数に対する割合も計算
2. クローン履歴関係分析
1. HCt : バージョン間でクローン関係に変化のない履歴関
係抽出
2. HAt: Vt において新規に追加されたクローンの履歴関係
抽出
3. HTt: Vt において片方が削除されたクローンの履歴関係
抽出
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
28
2-1: クローン関係に変化のない履歴関係抽出
行番号
行番号
ファイル1
Clone A
ファイル1
25
31
HCt
7
18
Clone A
37
43
Clone A
ファイル2
Clone A
クローン
関係
クローン
履歴関係
ファイル2
22
28
ファイル3
Clone B
11
22
Clone B
42
48
HCt
22
28
Clone A
Vt の各クローンについて、Vt-1 の
「写像先」にクローンが存在す
ファイル3
るかどうか検索
Vt-1
Vt
写像先の決定には、編集操作による行番号のズレを考慮
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
29
2-2: 追加されたクローンの履歴関係抽出
ファイル1
ファイル1
HAt
Clone A
クローン
関係
Clone A
Clone A
HAt
ファイル2
ファイル2
Clone A
Clone A
クローン
履歴関係
ファイル3
Clone B
ファイル3
Clone B
Vt-1
2005/12/21
Vt-1 と差分との間で
CCFinder を適用
V
t
発見したクローンに対応する部分を履歴関係とする
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
30
2-3:片方が削除されたクローン候補の抽出
行番号
行番号
ファイル1
ファイル1
Clone A
クローン
関係
Clone A
Clone A
ファイル2
ファイル2
Clone A
Clone A
ファイル3
Clone B
Clone B
Vt-1
クローン
履歴関係
Vt-1 において、対応がないクローンについて、
Vt との対応行とテキスト比較
ファイル3
HTt
Clone B
Vt
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
31
提案手法の特徴
となりのバージョン同士でのつながり
任意の二点間の分析を行うのはコス
トが大きい
計算量を極力抑える
バージョン間の diff に対してのみク
ローン分析を適用
Vt-1, Vt 全体に対して CCFinder を
適用するのはコストが大きい
各バージョンごとにクローン分析を適
用
正確なクローン分析
差分情報のみからクローン情報の類
推を行わない
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
32
PostgreSQL のクローン履歴分析
1. 分離クローンセットを漏れなく抽出できているかどうかの検
証
•
•
PostgreSQL の src 部分を 2005/01/01 ~ 2005/06/30 の期
間、一週間ごとに解析
クローンセット中のクローン数が減少している部分、時間に着目
•
•
その時間の差分を確認して、分離クローンセットか、縮退クローンセットか
を目視で判定
分離クローンセットであれば、各クローンに正しくクローン履歴関係が抽出
されているかどうかを検証
2. クローン全体の履歴
•
•
PostgreSQL の開発工程におけるクローンの増加量をグラフ化
1998年7月から2005年7月の6年分を一月区切りで解析
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
33
縮退クローンセット調査結果
分岐クローンセット
4
本来は分岐クローンセットなのに、クローン減少と判定
0
クローンが削除されたクローンセット
5
価値のないクローンセット
15
全 24 クローンセットを調査
誤判定はなし
15箇所のクローンセットは、定数定義が連続している部分
など無意味なクローン
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
34
過去に関連のあったクローンセットの例
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);
conversioncmds.c
793
aggregatecmds.c
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 */
opclasscmds.c
operatorcmds.c
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);
functioncmds.c
810
CatalogUpdateIndexes(rel, newtuple);
tablespace.c
811
}
812
813
systable_endscan(scan);
814
heap_close(rel, NoLock);
815 }
pgsql/src/backend/commands/dbcommands.c 08/04
765 /*
766 * ALTER DATABASE name OWNER TO newowner
767 */
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
*/
pgsql/src/backend/commands/aggregatecmds.c
07/01
796
if (datForm->datdba
!= newOwnerSysId)
aggregatecmds.c
291 /* 797
{
292 * Change
aggregate
owner
798
Datum
repl_val[Natts_pg_database];
293 */ 799
char
repl_null[Natts_pg_database]; conversioncmds.c
294 void
800
char
repl_repl[Natts_pg_database];
295 AlterAggregateOwner(List
*name,
TypeName *basetype, AclId newOwnerSysId)
801
Acl
*newAcl;
296 { 802
Datum
aclDatum;
297 803
Oid
bool basetypeOid;
isNull;
298 804
Oid
procOid;
opclasscmds.c
HeapTuple
newtuple;
・・・ 805
321 806
if (!HeapTupleIsValid(tup))
/* should
not happen
*/
/* changing owner's
database
for someone
else: must be superuser */
322 807 elog(ERROR,
failed
forneed
function
%u",any
procOid);
/* note "cache
that thelookup
someone
else
not have
permissions */
323 808
procForm =if(Form_pg_proc)
(!superuser()) GETSTRUCT(tup);
opratorcmds.c
324 809
ereport(ERROR,
325 810
/*
(errcode(ERRCODE_INSUFFICIENT_PRIVILEGE),
326 811* If the new owner is the same
as the existing
owner, consider
the
errmsg("must
be superuser
to change
owner")));
327 812* command to have succeeded.
This is for dump restoration purposes.
tablecmds.c
328 813*/
memset(repl_null, ' ', sizeof(repl_null));
329 814
if (procForm->proowner
!= newOwnerSysId)
memset(repl_repl,
' ', sizeof(repl_repl));
330 815
{
331 816 /* Otherwise,
must be superuser to change object
*/
repl_repl[Anum_pg_database_datdba
- 1] =ownership
'r';
functioncmds.c
332 817 if (!superuser())
repl_val[Anum_pg_database_datdba - 1] = Int32GetDatum(newOwnerSysId);
333 818
ereport(ERROR,
334 819
(errcode(ERRCODE_INSUFFICIENT_PRIVILEGE),
tablespace.c
/*
335 820
errmsg("must
be superuser
to change
owner")));
* Determine
the modified
ACL for the
new owner.
This is only
336 821
* necessary when the ACL is non-null.
337 822 /* Modify
*/ the owner --- okay to scribble on tup because it's a copy */
338 823 procForm->proowner
= newOwnerSysId;
aclDatum = heap_getattr(tuple,
339 824
Anum_pg_database_datacl,
schemacmds.c
340 825 simple_heap_update(rel, &tup->t_self,
tup);
RelationGetDescr(rel),
341
CatalogUpdateIndexes(rel,
dbcommands.c tup);
342
}
343
344
heap_close(rel, NoLock);
345
heap_freetuple(tup);
346 }
pgsql/src/backend/commands (SQL 文解釈・実行部の実装)
Clone A
Clone A
Clone A
Clone A
Clone A
Clone A
schemacmds.c
dbcommands.c
Clone A
Clone A
2005/12/21
Clone A
Clone A
Clone A
Clone A
Clone B
Clone B
Clone B
Clone B
Clone B
2005/03/04
2005/04/01
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
35
考察
分離クローンセットを漏れなく抽出できているかどうかの検証
縮退クローンセットに的を絞って検証
過去に関係のあったクローンの例
実際に関連性が高い
手動で履歴を探索していくのは手間がかかる
分析を行うための対話的ユーザインタフェースの作成
クローン量の変遷グラフ
PostgreSQL の開発工程ではクローン含有率は安定
→ 良好な開発パターン
ただし src/backend/command 以下では上昇傾向
→ 危険な傾向
危険なパターン、良好なパターンの列挙
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
36
関連研究
クローンの生存期間に着目した分析* (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)
** M. W. Godfrey and L. Zou: “Using origin analysis to detect merging and splitting of source code entities”,
IEEE Trans. Software Engineering, 31, 2, pp.166-181 (2005)
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
37
むすび
ソフトウェアリポジトリに存在する大量のソフトウェアか
ら、類似性を抽出しソフトウェア開発への応用を行っ
た
ソフトウェア自動分類システム MUDABlue の構築
事前知識なしでカテゴリを自動的に抽出し、分類
SourceForge から得たソフトウェアの分類実験
クローン履歴抽出手法の提案
コードクローンの履歴を抽出する手法の提案
PostgreSQL からの履歴抽出
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
38
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
39
特異値分解
特異値分解は、行列の次元
を削減する
b
l
誤差は最小二乗誤差になるよ
うにする。
高次元配列の次元削減を行
うメリット
a
2 次元データ (a, b) を 1 次元
データ (l) に削減する例
データサイズ削減
同じ値の分布をする次元（相関
の高い次元）から優先的に一つ
の次元に併合される
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
40
行番号の調整
行番号
ft-1
ft
9
9
削除
22
Clone A
31
Clone A
ft
行番号
8
Clone A
15
18
24 29 34 39
行番号
挿入
8
18
衝突
Clone A
15
18
18
24
22
29
34
31
36
ft-1
行番号
衝突時には対応行が一意でない
2005/12/21
最小、最大の推定値両方を考慮
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
41
0.2
1800000
0.18
1600000
0.16
1400000
0.14
1200000
0.12
1000000
0.1
800000
0.08
600000
0.06
400000
0.04
200000
0.02
0
クローン含有率
2000000
その他-クローン
その他-非クローン
configure-クローン
configure-非クローン
contrib-クローン
contrib-非クローン
doc-クローン
doc-非クローン
src-クローン
src-非クローン
クローン含有率
0
19
9
19 8年
98 7月
年
19 11
99 月
19 年3
9 月
19 9年
99 7月
年
20 11
00 月
20 年3
0 月
20 0年
00 7月
年
20 11
01 月
20 年3
0 月
20 1年
01 7月
年
20 11
02 月
20 年3
0 月
20 2年
02 7月
年
20 11
03 月
20 年3
0 月
20 3年
03 7月
年
20 11
04 月
20 年3
0 月
20 4年
04 7月
年
20 11
05 月
年
3月
行数
分析2: PostgreSQL 全体のコード量
クローン含有率は開発工程全体をとおして安定
2005/12/21
src 以下が全体の8割を占めている
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
42
分析2: PostgreSQL コア部分のコード量
1200000
その他-クローン
その他-非クローン
src/backend/commands-クローン
src/backend/commands-非クローン
src/backend/access-クローン
src/backend/access-非クローン
src/backend/po-クローン
src/backend/po-非クローン
src/backend/utils-クローン
src/backend/utils-非クローン
2000年11月、utils 以下のクローン含有率
1000000
800000
utils には文字コード変換用データの大量追加
600000
400000
200000
2005年4月
2005年1月
2004年10月
2004年7月
2004年4月
2004年1月
2003年10月
2003年7月
2003年4月
2003年1月
2002年10月
2002年7月
2002年4月
2002年1月
2001年10月
2001年7月
2001年4月
2001年1月
2000年10月
2000年7月
2000年4月
2000年1月
1999年10月
1999年7月
1999年4月
1999年1月
1998年10月
1998年7月
0
commands 以下のクローン率は徐々に上昇
0.2
0.18
0.16
0.14
その他
src/backend/commands
src/backend/access
src/backend/po
src/backend/utils
0.12
0.1
0.08
0.06
0.04
0.02
02005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
43
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
44
今後の研究方針
クローン以外のエンティティに対する、過去情報を考
慮した類似度測定
開発進捗度を考慮したソフトウェア類似判定
過去の開発過程を考慮したコンポーネント分類
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
45
ソースコードや
ドキュメントなどの
管理を行う
版管理システム
開発中に発見した
バグの管理を行う
バグ追跡システム
ソフトウェアリポジトリ
掲示板
ユーザの要望等を
2005/12/21
受け付ける
ML管理システム
開発者間で行われた
議論を保存
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
46
クローン履歴の活用法
2.コード中に含まれるコード
クローンの変化を分析
Clone A-3 追加
Clone A-1
Clone A-1
Clone B-1
Clone B-1
Clone A-3
Clone A-1
Clone B-1
Clone A-3
Clone A-4
Clone A-4, A-5 追加
Clone A-2
Clone B-2
Clone B-3
Clone A-2
Clone B-5
Clone B-4
Clone B-2
Clone B’-3
Clone A-2
Clone B’-2
Clone B’-1
Clone B-3, B-4, B-5 が編集
されて別クローンセットに
Clone B’-2
Clone B-2
Clone B’-3
Clone A-5
Clone B’-1
Clone B’-3 削除
1.過去に同じクローンセットだった
クローンセットの発見
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
47
クローン履歴
2. ひとつのクローンセットを
クローン発生時期から分類
Clone A-3 追加
Clone A-1
Clone A-1
Clone B-1
Clone B-1
Clone A-3
Clone A-1
Clone B-1
Clone A-3
Clone A-4
Clone A-4, A-5 追加
Clone A-2
Clone B-2
Clone B-3
Clone A-2
Clone B-5
Clone B-4
Clone B-2
Clone B’-3
Clone A-2
Clone B’-2
Clone B’-1
Clone B-3, B-4, B-5 が編集
されて別クローンセットに
3.コード中に含まれるコード
クローンの変化を分析
Clone B’-2
Clone B-2
Clone B’-3
Clone A-5
Clone B’-1
Clone B’-3 削除
1.過去に同じクローンセットだった
クローンセットの発見
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
48
1: クローン分析
ファイル1
ファイル1
Clone A
クローン
関係
Clone A
Clone A
Vt 全体を
CCFinder で分析
ファイル2
Clone A
クローン
履歴関係
ファイル2
Clone A
ファイル3
Clone B
ファイル3
Clone B
Clone B
Vt-1
Vt
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
49
Step1: クローン分析
ファイル1
ファイル1
Clone A
クローン
関係
Clone A
Clone A
Vt 全体を
CCFinder で分析
ファイル2
Clone A
クローン
履歴関係
ファイル2
Clone A
Clone B
ファイル3
Clone B
ファイル3
Clone B
Clone B
Vt-1
Vt
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
50
Step2-1: 編集されていないクローンの
履歴関係抽出
行番号
行番号
ファイル1
Clone A
ファイル1
25
31
7
18
Clone A
37
43
Clone A
ファイル2
Clone A
クローン
関係
クローン
履歴関係
ファイル2
22
28
22
28
Clone A
編集操作による行番号のズレを吸収Clone B
ファイル3
Clone B
11
22
Clone B
42
48
Vt-1
ファイル3
30
36
Clone B
Vt の各クローンについて、Vt-1 の対応する
Vt
行にクローンが存在するかどうか検索
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
51
行番号の調整
行番号
ft-1
ft
9
9
削除
22
Clone A
31
Clone A
ft
行番号
8
Clone A
15
18
24 29 34 39
行番号
挿入
8
18
衝突
Clone A
15
18
18
24
22
29
34
31
36
ft-1
行番号
衝突時には対応行が一意でない
2005/12/21
最小、最大の推定値両方を考慮
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
52
Step2-2: 追加されたクローンの
履歴関係抽出
ファイル1
ファイル1
Clone A
クローン
関係
Clone A
Clone A
ファイル2
ファイル2
Clone A
Clone A
クローン
履歴関係
Clone B
ファイル3
Clone B
ファイル3
Clone B
Clone B
Vt-1
2005/12/21
Vt-1 と差分との間で CCFinder を適用
Vt
発見したクローンに対応する部分を履歴関係とする
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
53
まとめと今後の課題
自動ソフトウェア分類システム MUDABlue の提案
事前知識なしでカテゴリを自動的に発見し、ソフトウェアをカ
テゴライズすることを示した
今後の課題
「その他」カテゴリを減らす
識別子を選別する部分の改善が必要
カテゴリタイトルをよりわかりやすく
分かりやすいものもあれば、分かりにくいものも
ライブラリに基づくカテゴリには分かりやすいタイトルがつく傾向
カテゴリの粒度
生成カテゴリの粒度は細粒度にすぎる傾向
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
54
まとめ
コードクローンの履歴を抽出する手法の提案
PostgreSQL から抽出した履歴の例の提示
課題
となりのバージョンだけで分析できないクローン履歴の抽
出
一度削除されてまた後で復活したクローン
活用方法の考察
分析用ユーザインタフェースの作成
2005/12/21
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
55
過去に関連のあったクローンセットの例
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);
conversioncmds.c
793
aggregatecmds.c
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 */
opclasscmds.c
operatorcmds.c
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);
functioncmds.c
810
CatalogUpdateIndexes(rel, newtuple);
tablespace.c
811
}
812
813
systable_endscan(scan);
814
heap_close(rel, NoLock);
815 }
pgsql/src/backend/commands/dbcommands.c 08/04
765 /*
766 * ALTER DATABASE name OWNER TO newowner
767 */
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
*/
pgsql/src/backend/commands/aggregatecmds.c
07/01
796
if (datForm->datdba
!= newOwnerSysId)
aggregatecmds.c
291 /* 797
{
292 * Change
aggregate
owner
798
Datum
repl_val[Natts_pg_database];
293 */ 799
char
repl_null[Natts_pg_database]; conversioncmds.c
294 void
800
char
repl_repl[Natts_pg_database];
295 AlterAggregateOwner(List
*name,
TypeName *basetype, AclId newOwnerSysId)
801
Acl
*newAcl;
296 { 802
Datum
aclDatum;
297 803
Oid
bool basetypeOid;
isNull;
298 804
Oid
procOid;
opclasscmds.c
HeapTuple
newtuple;
・・・ 805
321 806
if (!HeapTupleIsValid(tup))
/* should
not happen
*/
/* changing owner's
database
for someone
else: must be superuser */
322 807 elog(ERROR,
failed
forneed
function
%u",any
procOid);
/* note "cache
that thelookup
someone
else
not have
permissions */
323 808
procForm =if(Form_pg_proc)
(!superuser()) GETSTRUCT(tup);
opratorcmds.c
324 809
ereport(ERROR,
325 810
/*
(errcode(ERRCODE_INSUFFICIENT_PRIVILEGE),
326 811* If the new owner is the same
as the existing
owner, consider
the
errmsg("must
be superuser
to change
owner")));
327 812* command to have succeeded.
This is for dump restoration purposes.
tablecmds.c
328 813*/
memset(repl_null, ' ', sizeof(repl_null));
329 814
if (procForm->proowner
!= newOwnerSysId)
memset(repl_repl,
' ', sizeof(repl_repl));
330 815
{
331 816 /* Otherwise,
must be superuser to change object
*/
repl_repl[Anum_pg_database_datdba
- 1] =ownership
'r';
functioncmds.c
332 817 if (!superuser())
repl_val[Anum_pg_database_datdba - 1] = Int32GetDatum(newOwnerSysId);
333 818
ereport(ERROR,
334 819
(errcode(ERRCODE_INSUFFICIENT_PRIVILEGE),
tablespace.c
/*
335 820
errmsg("must
be superuser
to change
owner")));
* Determine
the modified
ACL for the
new owner.
This is only
336 821
* necessary when the ACL is non-null.
337 822 /* Modify
*/ the owner --- okay to scribble on tup because it's a copy */
338 823 procForm->proowner
= newOwnerSysId;
aclDatum = heap_getattr(tuple,
339 824
Anum_pg_database_datacl,
schemacmds.c
340 825 simple_heap_update(rel, &tup->t_self,
tup);
RelationGetDescr(rel),
341
CatalogUpdateIndexes(rel,
dbcommands.c tup);
342
}
343
344
heap_close(rel, NoLock);
345
heap_freetuple(tup);
346 }
pgsql/src/backend/commands (SQL 文解釈・実行部の実装)
Clone A
Clone A
Clone A
Clone A
Clone A
Clone A
schemacmds.c
dbcommands.c
Clone A
Clone A
2005/12/21
Clone A
Clone A
Clone A
Clone A
Clone B
Clone B
Clone B
Clone B
Clone B
2004/07/01
2004/08/04
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
56

Download Report