クローン検出ツールを用いたソフトウェアシステムの類

版管理とソフトウェアの再利用
における支援に関する研究
大阪大学大学院基礎工学研究科
情報数理系専攻ソフトウェア科学分野
山本哲男
1
背景
ハードウェアの価格の低下とその機能の向上にともな
い、ソフトウェアシステムは年々大規模化・複雑化し
ている
ソフトウェアの構築や保守にかかるコストが増大し、
多くの労力が必要

保守支援手法
 版（バージョン）管理、プログラム理解支援、・・・

構築支援手法
 再利用、設計方法論、・・・
2
問題点
既存のバージョン管理手法



プロダクトの作成，変更作業の逐次的な記録や
追跡を支援するシステム
ユーザの負担が大きい
保存する間隔が粗い
3
問題点続き
既存の再利用手法


粒度の細かい再利用（ライブラリ等）
より大規模なシステムレベルでの再利用が求めら
れている
B社
D社
A社
C社
C社
4
目的
新しい版管理手法・版管理システムの提案

ユーザの保存したファイルを特別な操作を必要と
せず自動的に記録するシステム
大規模システムレベルでの再利用のためのシ
ステム類似度の提案

ソフトウェアシステム間の類似度を用いた派生関
係を計測するシステム
5
論文の構成
第１章まえがき
第２章堆積型ファイルシステムMoraineの提
案と実装[3,4]
第３章メトリクス環境MAMEの提案と実装
[1,5]
第４章類似度計測ツールSMMTの提案と実
装[2]
第５章むすび
6
堆積型ファイルシステムMoraineと
メトリクス計測システムMAME[2,3章]
1995年のHDD容量 -------- 0.54Gbytes
空き容量
0.39Gbytes
Linux (Slackware2.2[Basic
Applications+X window])
0.15Gbytes
7
HDD容量の変遷
2001年のHDD容量 --------0.39Gbytes
80Gbytes
200倍
空き容量
79Gbytes
Linux (RedHat7[Basic
Applications+X window])
1Gbytes
6倍
0.15Gbytes
8
空き容量の使用
一般ユーザ

JPEG, MPEG, MP3, HTML, ...
ソフトウェア工学に携わる者

?
バージョン管理手法は限られたＨＤＤ容量の
基で考案、開発されている
ユーザが手動で保存
9
ソフトウェアプロダクトの保存
昔のHDDは高価で現実的に不可能
FreeBSD 2.0
100Mbytes
1994
FreeBSD 4.4
27 リリース
320Mbytes
2001
履歴の総サイズ 1.2Gbytes
現在のHDD容量はソフトウェアの履歴を保存
するのに十分な容量を持っている
10
MoraineとMAMEの開発
二つのシステムを構築した
自動的にプロダクトを保存する
⇒堆積型ファイルシステム Moraine
定量的なメトリクス計測基盤
⇒メトリクス計測システム MAME
(Moraine As a Metrics Environment)
11
Moraineの設計方針
自動的に保存

すべてのファイルを細粒度で自動的に保存する
容易な操作

開発者はMoraineについて特別な知識を必要としない。
通常の読み出し、書き込み操作をシステムがつかまえるこ
とで以前と同じ環境で作業が行える
オープンな構造

Moraine で保存するファイルは既存のツールを利用して行
う
12
Moraineの特徴
Moraine は常に最新のバージョンのみを開発
者に見せる
Newer
実際のファイル構造
リポジトリ
開発者
操作
最新バージョン
開発者の視点
13
Moraineのアーキテクチャ
User
Process
VFS
Vertical File System
UFS
Unix File system
VCD
Version Control Daemon
バージョン管理サブシステム
RCS
VCS
VFS を実際のファイルシステムの上に論理
管理コマンド群
的なファイルシステムとして存在するように
-retrieve versions
HDD
-show a delta
実現
14
VCD はバージョン管理サブシステムを結ぶ
役割を果たすプロセス
Moraineのアーキテクチャ
User
Process
VFS
Vertical File System
VCD
Version Control Daemon
管理コマンド群は通常の操作では行えない
バージョン管理サブシステム
UFS
操作を行うコマンド群
Unix File system
RCS
VCS
管理コマンド群
バージョン管理サブシステムはバージョン間の
-retrieve versions
HDD
-show a delta
差分計算といった実際にバージョンを記録す
る作業を行う部分
15
実験
Moraineが実用的かどうかについて実験を
行った
システムの性能と保存データサイズ
UFS (UNIX file system) と比較
計測環境

Pentium 166MHZ/48MB RAM
16
実験（読み出し）
時間 (Sec.)
ファイルの読み出しにかかるプロセスの実行時間
10
9
8
7
6
5
4
3
2
1
0
Moraine
UFS
1
2
3
4
5
6
7
8
１MBファイルの連続読み出し回数
9
10
17
実験（書き込み）
ファイルの書き込みにかかるプロセスの実行時間
35
時間 (Sec.)
30
Moraine
UFS
25
20
15
10
5
0
1
2
3
4
5
6
7
8
１MBファイルの連続書き込み回数
9
10
18
実験（サイズ）
学生のプログラム演習に適用
Student1 Student2 Student3
LOC
9339
4067
2543
45
20
18
ファイル数
225
117
73
最終ファイルサイズ
(KB)
総バージョン数
ソースコードの
総バージョン数
533
249
357
311
147
247
19
実験（サイズ）続き
1400
1388
UFS
1200
Moraine
1000
KB
800
600
400
225
200
0
604
546
Student1
117
Student2
73
Student3
20
メトリクス計測システムMAME
ファイルの開発者，バージョン数，日時などを
指定し，プロダクトに関するメトリクスを計測す
る
時間軸やバージョンの数の推移によって、メトリ
クスがどう推移しているか分かる
21
MAMEの設計方針
開発者の環境を変更する必要はない
様々なデータを自動的に収集する
粒度自在
開発中、開発後にかかわらずメトリクスが取得
可能
22
MAMEのアークテクチャ
開発者
開発活動
開発環境
メトリクスデータ
MAME
開発ツール
ファイルの読み書き
メトリクス計算
VFS
UFS
HDD
Moraine
VCD
RCS
保存ファイルの取得
Commands
23
実験
MAMEを学生のプログラム演習に適用
メトリクスは演習終了後に取得した
任意のファイルが更新された時の下記メトリク
スの推移を取得



ファイル数
ファイルの全行数
C言語でかかれたソースコードの関数の数
24
実験結果
横軸はソースコードの累積バージョン数
LOC
ファイル数
5000
20
4000
15
3000
lines
数
25
10
2000
5
1000
0
0
0
50
100
147
0
バージョン数
50
147
100
バージョン数
バージョン数20-50 で開発は停滞
25
実験結果続き
C言語の関数の数
120
100
数
80
60
40
20
0
0
50
100
147
バージョン数
開発者は関数のスケルトンを作った後、中身
を書いている
26
関連研究
ClearCase, PVCS, Visual Source Safe



開発者はシステムを理解する必要がある
バージョンの記録は手動で行う
保存したバージョンの二次利用が困難
27
まとめ
自動的にファイルを保存するファイルシステムMoraine
の提案と実装を行った
プロダクトに関するメトリクスを収集するシステムMAME
の提案と実装を行った



開発者に余分な負担をかけない
実用的な速度で動作可能
いつでも取りたいときに取得可能
今後の課題


大規模ソフトウェアによる評価実験
メトリクス問い合わせ言語の構築
28
類似度計測システムSMMT[4章]
ドキュメントなどが存在すれば、複数の類
似システム間の相違点を知ることは可能
であろうが，定量的な値を得ることは容易
ではない


システムが小規模な場合、そのシステムの
個々の構成要素を人間が調べ値を出すことも
可能
構造が複雑で大規模なシステムでは、何らか
の機械的な処理により、自動的に求めること
が必須
29
目的
二つのソフトウェアシステムの類似度メトリクス
自動的に計測するシステムSMMT(Similarity
Metrics Measuring Tool)の提案と実装


類似度の形式的な定義を与え、それを求めるた
めの現実的な方法を示す
実際に類似度を種々のUNIX系OSのいくつかの
バージョンに適用した結果を示す
30
ソフトウェアプロダクトに対する類似
度の一般的定義(1/2)
ファイルやソフトウェアシステムを抽象的に表し
たものをプロダクトと呼ぶ
プロダクトは要素の集合とし、P={p1,…,pm}と
あらわす


Pをファイルとすると、piは各行になる
Pをシステムとすると、piはファイルになる
31
ソフトウェアプロダクトに対する類似
度の一般的定義(2/2)
P
Q
二つのプロダクト
P={p1,…,pm},Q={q1,…,qm}に対し、等価
な要素の対応R⊆P×Qが得られるとする
PとQのRに対する類似度S(0≦S≦1)を以下の
ように定義する
|{pi|(pi,qj)  R}|  |{qj|(pi,qj)  R}|
S(P,Q)
PQ
32
具体的なメトリクス
等価な行を用いた類似度Sline


プロダクトPをソフトウェアシステムし、要素をシステ
ムを構成するファイルの行とする
対応Rは各行の対応とする
ファイル名やファイルの大きさに影響されない
33
Slineの要素の対応
Slineを計算するためのRを求める方法

CCFinderとdiffを組み合わせ対応Rを求める
 CCFinder — コードクローン検出ツール

ソースコードを入力としてコードクローンを出力する
 diff — ファイルの差分抽出ツール


二つのファイル間の行単位の差分を求める
CCFinderでクローンが見つかったファイルのペアに
対してdiffを実行する
34
CCFinder と diff を用いる理由
diff だけを用いると、すべてのファイルの組み合
わせに対して実行する必要がある
CCFinder でクローンを持つファイルの組を見つ
け、その組に対してのみ diff を実行する
35
SMMTの処理概要
P
SMMT
前処理後のP
Step1
Step2
前処理
Q
Step3
CCFinder CCFinder
diff
の実行結果
の実行
の実行
前処理後のQ
diff
の実行結果
Step4
対応の
抽出
抽出結果
Step5
類似度
類似度の
計算
36
実験
UNIX系OSを用いて類似度を計算した




4.4BSDLite, 4.4BSDLite2
FreeBSD2.0, 2.0.5, 2.1, 2.2, 3.0, 4.0
NetBSD1.0, 1.1, 1.2, 1.3, 1.4, 1.5
OpenBSD2.0, 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 2.8
23個のOSのすべての組み合わせでSlineを求めた
カーネル部分のC言語のソースのみ
37
38
同一種類のOS間での類似度
FreeBSD 2.2との間の類似度
39
異なる種類のOS間での類似度
FreeBSD3.0とNetBSD1.3で4.4BSDLite2が取り込まれてい
る
0.5
NetBSD 1.0
0.45
NetBSD 1.1
0.4
NetBSD 1.2
0.35
NetBSD 1.3
0.3
0.25
0.2
0.15
0.1
0.05
0
FreeBSD 2.0 FreeBSD 2.0.5 FreeBSD 2.1
FreeBSD 2.2
FreeBSD 3.0
FreeBSD 4.0
40
クラスタ分析
Slineを距離と考え、クラスタ分析を行った
41
まとめ
二つのソフトウェアシステムの類似度を提案し、
計測システムSMMTを構築した
SMMTをUNIX系OSに適用した
今後の課題

類似部分から再利用可能な部品の抽出
42
むすび
堆積型ファイルシステムMoraine、および
MAMEの提案と実装

開発者に特別な操作を必要とせず、自動的に細
かい粒度で保存する
類似度計測システムSMMTの提案と実装

ソフトウェア間の類似度を計測し、類似度からソフ
トウェアの派生を知ることが可能になる
43
終
44
実験（書き込み）続き
Moraine+Sync: 完全に書き込みが終わる間の時間
35
Moraine+Sync
Moraine
UFS
時間 (Sec.)
30
25
20
15
10
5
0
1
2
3
4
5
6
7
8
１MBファイルの連続書き込み回数
9
10
45

Download Report