クローン検出ツールを用いた ソフトウェアシステムの類似度調査 山本哲男†, 松下誠†, 神谷年洋‡, 井上克郎† †大阪大学, ‡PRESTO

背景 ソフトウェアシステム間の相違の度合を調べることによって、 ソフトウェアシステム間の違いがどれぐらいあるか、客観的に知ることは重要 システムの保守の様子や進化の度合を知ることができる。 システムのリリース時期の目安になる。 システムを改変する際の有益な指針になる。 ソフトウェアシステム間の違いがどれぐらいあるか、客観的に知ることは重要

背景(つづき) ドキュメントなどが存在すれば、システム間の相違点を知ることは可能であろうが，定量的な値を得ることは容易ではない。 システムが小規模な場合、そのシステムの個々の構成要素を人間が調べ値を出すことも可能 構造が複雑で大規模なシステムでは、何らかの機械的な処理により、自動的に求めることが必須

目的 二つのソフトウェアシステムの類似度メトリクスと自動的に計測するツールの提案 類似度の形式的な定義を与え、それを求めるための現実的な方法を示す。 実際に類似度を種々のUNIX系OSのいくつかのバージョンに適用した結果を示す。

類似度の定義(1/2) ファイルやソフトウェアシステムを抽象的に表したものをプロダクトと呼ぶ。 プロダクトは要素の集合とし、P={p1,…,pm}とあらわす。 Pをファイルとすると、piは各行になる。 Pをシステムとすると、piはファイルになる。

類似度の定義(2/2) 二つのプロダクトP={p1,…,pm},Q={q1,…,qm}に対し、等価な要素の対応R⊆P×Qが得られるとする。 PとQのRに対する類似度S(0≦S≦1)を以下のように定義する。 ≡

類似度の適用 定義した類似度を実際のソフトウェアシステムやファイルに適用する。 プロダクトや要素をシステム、ファイル、ファイルの行のいずれかにし、4種類の適用を考えた。 プロダクト 要素 対応 適用1 ファイル ファイルの行 同一行 適用2 システム ファイル名 適用3 ファイルの類似度 適用4

類似度の適用1 プロダクトをファイルし、要素をファイルの各行とする。 対応Rは同一行の対応とする。 単一ファイルの対応で、複数のファイルには適用できない。

類似度の適用2 プロダクトをソフトウェアシステムし、要素をシステムを構成するファイルとする。 対応Rは同じファイル名を持つファイルの対応とする。 ファイル名だけの対応なので容易に計算できる。 ファイルの大きさを考慮しない。

類似度の適用3 プロダクトをソフトウェアシステムし、要素をシステムを構成するファイルとする。 P Q プロダクトをソフトウェアシステムし、要素をシステムを構成するファイルとする。 全てのファイルの組み合わせに対して適用1のSを求める。あるファイルに対してSが0より大きく最も高い組み合わせをRとする。 ファイル名に依存しない。 ファイルの大きさが反映されない。全ての組み合わせでSを計算するため、手間がかかる。

類似度の適用4 プロダクトをソフトウェアシステムし、要素をシステムを構成するファイルの行とする。 対応Rは各行の対応とする。 ファイル名やファイルの大きさに影響されない。 この類似度をCSR(Corresponding Source-line Ratio)と呼ぶ。

CSRの要素の対応 CSRを計算するためのRを求める方法 CCFinderとdiffを組み合わせ対応Rを求める。 ソースコードを入力としてコードクローンを出力する。 diff — ファイルの差分抽出ツール 二つのファイル間の行単位の差分を求める。 CCFinderでクローンが見つかったファイルのペアに対してdiffを実行する。

ツールの処理概要 P 前処理 CCFinder の実行 diff の実行 Q 対応の 抽出 CSRの 計算 CSR Step1 Step2 の実行結果 diff の実行 Q diff の実行結果 前処理後のQ Step4 対応の 抽出 抽出結果 Step5 CSRの 計算 CSR

CCFinder と diff を用いる理由 diff だけを用いると、すべての組み合わせに対して実行する必要がある。 CCFinder だけを用いると、CCFinderが対応していない構文が抽出できない。 CCFinder でクローンを持つファイルの組を見つけ、その組に diff を実行する。

CSRの適用 UNIX系OSを用いてCSRを計算した。 23個のOSのすべての組み合わせでCSRを求めた。 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のすべての組み合わせでCSRを求めた。 カーネル部分のC言語のソースのみ。 前処理としてコメントと空白行を削除する。

適用結果(1/2) 同一種類のOS間での類似度を求めた。

適用結果(2/2) 異なる種類のOS間での類似度を求めた。 FreeBSD3.0とNetBSD1.3で4.4BSDLite2が取り込まれている。

CSRを用いたクラスタ分析 CSRを距離と考え、クラスタ分析を行った。

ファイル名を用いたクラスタ分析 ファイル命名規則や階層構造が同じならファイル名を用いた類似度もシステムの分類には使用可能である。

FreeBSDとLinuxの類似度 由来が異なるOSであるFreeBSD4．0, Linux2.2.15の間の類似度を求めた。 同一ファイル名はなく、実際には若干類似部分が存在する。 ファイル名が対応する類似度はの値は0 CSRは0.066

CSRとリリース間隔の相関 FreeBSDのリリース間隔との相関を求めた。 CSRが最も高い相関を持つ。 対応の数だけでは相関が低い。 適用2 行数差 CSR×全行数（対応の数） -0.973 -0.964 0.937 -0.577

まとめ 二つのソフトウェアシステムの類似度メトリクスCSR(Corresponding Source-line Ratio) の提案を行った。 CSRをUNIX系OSに適用した。 CSRはソフトウェアシステム間の類似性を正しくあらわす。 CSRとリリース間隔の間に高い相関を持つ。

今後の課題 さらなる類似度の妥当性の検証 類似度と再利用プログラミングとの関係の計測