クローン検出ツールを用いたソフトウェアシステムの類似度調査山本哲男†, 松下誠†, 神谷年洋‡, 井上克郎† †大阪大学, ‡PRESTO 1 背景ソフトウェアシステム間の相違の度合を調べることによって、    システムの保守の様子や進化の度合を知ることができる。システムのリリース時期の目安になる。システムを改変する際の有益な指針になる。ソフトウェアシステム間の違いがどれぐらいあるか、客観的に知ることは重要 2 背景(つづき) ドキュメントなどが存在すれば、システム間の相違点を知ることは可能であろうが，定量的な値を得ることは容易ではない。   システムが小規模な場合、そのシステムの個々の構成要素を人間が調べ値を出すことも可能構造が複雑で大規模なシステムでは、何らかの機械的な処理により、自動的に求めることが必須 3 目的二つのソフトウェアシステムの類似度メトリクスと自動的に計測するツールの提案   類似度の形式的な定義を与え、それを求めるための現実的な方法を示す。実際に類似度を種々のUNIX系OSのいくつかのバージョンに適用した結果を示す。 4 類似度の定義(1/2) ファイルやソフトウェアシステムを抽象的に表したものをプロダクトと呼ぶ。プロダクトは要素の集合とし、P={p1,…,pm}とあらわす。   Pをファイルとすると、piは各行になる。 Pをシステムとすると、piはファイルになる。 5 類似度の定義(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 6 類似度の適用定義した類似度を実際のソフトウェアシステムやファイルに適用する。プロダクトや要素をシステム、ファイル、ファイルの行のいずれかにし、4種類の適用を考えた。プロダクト要素対応適用1 ファイルファイルの行同一行適用2 システムファイルファイル名適用3 システムファイルファイルの類似度適用4 システムファイルの行同一行 7 類似度の適用1 プロダクトをファイルし、要素をファイルの各行とする。対応Rは同一行の対応とする。単一ファイルの対応で、複数のファイルには適用できない。 8 類似度の適用2 プロダクトをソフトウェアシステムし、要素をシステムを構成するファイルとする。対応Rは同じファイル名を持つファイルの対応とする。ファイル名だけの対応なので容易に計算できる。ファイルの大きさを考慮しない。 9 P 類似度の適用3 Q プロダクトをソフトウェアシステムし、要素をシステムを構成するファイルとする。全てのファイルの組み合わせに対して適用1のSを求める。あるファイルに対してSが0より大きく最も高い組み合わせをRとする。ファイル名に依存しない。ファイルの大きさが反映されない。全ての組み合わせでSを計算するため、手間がかかる。 10 類似度の適用4 プロダクトをソフトウェアシステムし、要素をシステムを構成するファイルの行とする。対応Rは各行の対応とする。ファイル名やファイルの大きさに影響されない。この類似度をCSR(Corresponding Sourceline Ratio)と呼ぶ。 11 CSRの要素の対応 CSRを計算するためのRを求める方法  CCFinderとdiffを組み合わせ対応Rを求める。  CCFinder — コードクローン検出ツール  ソースコードを入力としてコードクローンを出力する。  diff — ファイルの差分抽出ツール   二つのファイル間の行単位の差分を求める。 CCFinderでクローンが見つかったファイルのペアに対してdiffを実行する。 12 ツールの処理概要 P 前処理後のP Step1 Step2 前処理 Q Step3 CCFinder CCFinder diff の実行結果の実行の実行前処理後のQ diff の実行結果 Step4 対応の抽出抽出結果 Step5 CSR CSRの計算 13 CCFinder と diff を用いる理由 diff だけを用いると、すべての組み合わせに対して実行する必要がある。 CCFinder だけを用いると、CCFinderが対応していない構文が抽出できない。 CCFinder でクローンを持つファイルの組を見つけ、その組に diff を実行する。 14 CSRの適用 UNIX系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言語のソースのみ。前処理としてコメントと空白行を削除する。 15 16 適用結果(1/2) 同一種類のOS間での類似度を求めた。 17 適用結果(2/2) 異なる種類の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 18 CSRを用いたクラスタ分析 CSRを距離と考え、クラスタ分析を行った。 19 ファイル名を用いたクラスタ分析ファイル命名規則や階層構造が同じならファイル名を用いた類似度もシステムの分類には使用可能である。 20 FreeBSDとLinuxの類似度由来が異なるOSであるFreeBSD4．0, Linux2.2.15の間の類似度を求めた。同一ファイル名はなく、実際には若干類似部分が存在する。   ファイル名が対応する類似度はの値は0 CSRは0.066 21 CSRとリリース間隔の相関 FreeBSDのリリース間隔との相関を求めた。 CSRが最も高い相関を持つ。対応の数だけでは相関が低い。 CSR 適用2 行数差 CSR×全行数（対応の数） -0.973 -0.964 0.937 -0.577 22 まとめ二つのソフトウェアシステムの類似度メトリクス CSR(Corresponding Source-line Ratio) の提案を行った。 CSRをUNIX系OSに適用した。 CSRはソフトウェアシステム間の類似性を正しくあらわす。 CSRとリリース間隔の間に高い相関を持つ。 23 今後の課題さらなる類似度の妥当性の検証類似度と再利用プログラミングとの関係の計測 24