コードクローンを用いたコンポーネントランク拡張手法の有効性評価〜部品グラフの変化についての分析〜
2009SE229

奥田黎哉

2011SE132 小林登夢 2011SE179 村瀬慶紀
指導教員：横森励士

はじめに

1

近年のソフトウェアは規模が大規模化しており，それに伴いソフトウェア部品の数も増大し，内部の関係も複雑化している．このような大量の部品下においては，ソフトウェアをモデル化し，メトリクスに基づいてある特性を持つ部品を抽出するという方法を用いることで，目的に沿った部品を効率的に選び出せると考えられる．千賀は部品間の関係をモデル化し，部品の評価をおこなう手法であるに基づいて評価を行う．重みとは，次のように定義される．
頂点の重み
部品グラフ G 上の各頂点 v は 0 ≦ w(v) ≦ 1 の重みを持ち, G の頂点の重みの総和は 1 とする．
辺の重み
頂点 vi から vj への辺 eij に関する辺の重み w′ (eij ) 式(1) のように定義する．

コンポーネントランクにコードクローンの関係を取り込

w′ (eij ) = dij × w(vi )むことで拡張する手法 [1] を提案した．この方法は既存の(1)トウェアでのみしか検証を行っておらず，一般的なソフト

dij は配分率と呼び, 0 ≦ dij ≦ 1 かつ Σi dij = 1 を満たす値とする．頂点 vi から vj へ利用関係が存在しない場合，
dij = 0 とする. この配分率 dij は，次に示す頂点の重みのウェア部品グラフにおいても有効であるかどうかを検証し定義において，有向辺の終点となる頂点の重みの決定に利ていない．

用される．

コードクローンが共通して利用している部品を抽出するのに有効であると思われるが，現段階では小規模の仮想ソフ

本研究では，一般的なソフトウェアに対する提案手法の有効性を確認するために評価実験を行う．実際に存在する多数のオープンソースプロジェクトのソースコードに対して提案手法を適用し，適用前後で部品グラフの評価値がどう変化するかに着目する．コードクローンの関係を取り込

頂点の重みの再計算

IN (vi ) を vi を終点とする有向辺の集合とする．この時，頂点 vi の重みは vi が終点となる有向辺 eki の重みの総和とする． 式 (2) で頂点の重みを再計算する．

む前と後での評価値の変動率の変化の割合や，変動率の平均の算出という評価実験を行い，結果の妥当性を考察する．
この結果を元に，提案手法が一般的なソフトウェアに対しても有効であることを確認する．

2

背景技術

2.1

部品グラフ

一般に，ソフトウェア部品とはモジュールや関数，クラスなどのソフトウェアの構成要素を指す．以降，ソフトウェア部品を単に部品と呼ぶ．ソフトウェアは構成要素の部品間で相互に属性や振る舞いを利用しあうことで一つの機能を提供する．

∑w′ (eij ) =dij × w(vk )(2)eki ∈IN (vi )繰り返しの計算の手順

1．評価値の初期値として，各頂点に正の値を与える．
2．値の変化が一定以下になるまで，次の計算を繰り返す．
(a) 辺の重みを現在の頂点の重みから決定する．
(b) 頂点の重みを再計算する．
3．収束後の各頂点の重みを対応する部品の評価値とする．
2.3

コードクローン関係をコンポーネントランクに反映させる手法について

本研究では，ある部品がある部品を利用する時，部品間コードクローンとは，ソースコード中での類似または一に利用関係が存在すると考え，部品グラフとしてモデル化致した部分であり，同一の部品内だけにとどまらず，異なする．部品を頂点，利用関係を有向辺で表したグラフを部る部品間に存在する場合もある．コードクローンは無意味品グラフと呼ぶ．以降，V を部品 (頂点) の集合，E を有に出現するものではなく，同一処理や似た処理が必要にな向辺の集合として，部品グラフを G = (V, E) と表現する． るなど，開発者の何らかの意図によって作りこまれる場合が多い．コードクローンはソフトウェアの保守工程におい2.2 コンポーネントランクてプログラム管理の手間を増大させる可能性を持つので，コンポーネントランク [2] は，利用頻度に基づいて部品コードクローンとなる部品を有する部品は，常に着目するグラフからそのソフトウェアにおける各部品の評価値を算必要がある．

出する手法である．コンポーネントランクでは，部品グラ先行研究 [1] では，コンポーネントランクの拡張方法とし

フ G = (V, E) 上の個々の辺および頂点に対して重みを計てコードクローンの関係を持つ頂点の統合を行う手法を提算し，対応する頂点の重みを各部品の評価値として，順位案した．小規模な仮想ソフトウェアを対象としてコードク

ローンを考慮した評価値計算を行い，評価値の変化を調査

1. プロジェクト単位で見た時の A，B，C の各グルーした．さらに，実際のソフトウェアにおいて評価値が減少プの部品の評価値の変動率の平均を調査する．プする部品がコードクローンを持つ部品から共通の方法で利ロジェクト毎に部品数が異なるので，プロジェク用される部品であるかどうかを調査した．これにより以下

ト単位の平均変動率という観点から分析する．の結果が得られた．

2. プロジェクト単位で見た時の GroupA と GroupBに属する部品の評価値の平均変動率の差，GroupAと GroupC に属する部品の平均変動率の差を調査 す る ．こ れ に よ り GroupA に 属 す る 部 品 がGroupB，C に属する部品よりも評価値の減少• 小規模な仮想ソフトウェアを対象とした実験では，部品グラフ上で部品の統合が行われた時，統合された部品の 1 つからのみ利用している部品や関係のない部品よりも統合された部品群の 2 つ以上の部品から共が大きいことを確認する．

通して利用されている部品の方が評価値が大きく減少

3. プロジェクト毎に評価値の減少が大きくなる部品の Top5，Top10，TOP15，TOP20 を選出し，その中での GroupA，GroupB，GroupC に属するする．

• 評価値が減少する部品がコードクローンを持つ部品から利用される部品となっている事例が存在する．

部品の割合を調査する．これにより評価値が大きただし，この研究では評価値の減少について小規模の仮想く下がる部品の傾向を確認する．

ソフトウェアでのみしか検証を行っておらず，分析としては不十分である．先行研究 [1] の手法が一般的に有効であ

3.3

ることを示すために，より多くのプロジェクトについて調査する必要がある．

3

コンポーネントランク拡張手法の有効性評価

3.1

目的

本研究では，先行研究 [1] の手法の有効性を評価するた
めに，部品グラフ上で部品の統合が行われた時，1 つからのみ利用している部品やその他の部品よりも 2 つ以上の部評価値の変動率評価値の増減の判定には，統合前後の各頂点の重みの変動率を用いる．部品数により１つの頂点あたりの重みが異なるので，変動率にはグラフにおける頂点の総数を考慮する．ある頂点 vi の頂点統合前のグラフでの評価値をw(vi )，頂点統合後のグラフでの評価値を w(vi′ )，また，頂点統合前のグラフにおける頂点の総数を |V |，頂点統合後のグラフにおける頂点の総数を |V ′ | とする．このとき頂点 vi の評価値の変動率を式（3）で定義する．

品から共通して利用されている部品の方が評価値が大きくw(vi′ ) × |V ′ |× 100w(vi ) × |V |減少することが実際のソフトウェアにおいても成り立つのかを調査する．

3.2

分析手順

(3)

評価値の変動率の調査

4

リストアップした 45 個のプロジェクトに対し，分析手(1) オープンソースのプロジェクトを収集し，各プロジェクトからソースコードを 1 バージョン分入手する．

順を元に調査を行った．実験ではソースコード中の各クラ(2) CCfinder[3] を用いてクローン関係を，Classycle[4]4.1を用いて利用関係を解析する．

(3) (2) で得たクローン関係，利用関係を元に，千賀が提案した手法 [1] を適用し，部品一覧と結合前後の各部品のコンポーネントランクを求める．

(4) 適用前後の部品グラフから，結合した部品群それぞれに着目し，結合されなかった部品を次のように分類する．

GroupA 統合した部品群のどれかから利用されており，ある部品群内の 2 つ以上の部品から利用されていスを部品として扱っている．
プロジェクト単位での評価値の変動率

プロジェクト毎に部品数が異なることを考慮し，ABC各グループに属する部品の平均変動率を求めた．それらの平均・標準偏差を表 1，各グループの変動率の分布を図 1，
図 2，図 3 に示す．GroupA，B，C が存在しなかったプロジェクトがあるのでプロジェクト数は 45 より小さい数となっている．
表 1 より，手法の適用前後での変動率の平均は GroupAの減少が最も大きく，GroupB と GruopC はあまり変化は見られなかった．また変動率が減少したプロジェクトの割る部品．

合は，GroupA が約 93% と最も高く，GroupB は約 54%，

GroupB 統合した部品群のどれかから利用されているが，どの部品群からも高々 1 つの部品からしか利用と GroupC は約 53% となった．

されていない部品．

変動率の分布を比較すると次のようなことが確認出来る．

GroupC 統合した部品群から全く利用されていない部品．

(5) 部品グラフの評価値の変化として以下の項目を分析する．

図 1，2，3 より，GroupA，B，C の各プロジェクトの平均• GroupA の分布の山は，GroupB，C よりも左に存在する．ただし，GroupA に属している部品でも評価値が大きく増加した部品が一部あり，平均値を押し上げる結果となったプロジェクトも存在する．

• GroupB の分布をみると，大部分のプロジェクトが90% 以上となっている．ただし大きく減少したプロジェクトも存在する．

ぞれ求めた．結果を表 2 に，B-A の変動率の分布，C-A の変動率の分布をそれぞれ図 4，図 5 に示す．

• GroupC の大部分のプロジェクトは，90% から 110%の範囲に存在している．
表 1 各プロジェクトの評価値の変動率の平均と標準偏差評価値の増減

GroupAGroupB
GroupCトに対して A の平均変動率と C の平均変動率の差をそれ

プロジェクト数

平均標準偏差増加

減少

4341
43

88.5%
107.8%
104.3%

19.7
166.4

31920402223

表 2 より，B-A の平均変動率の差の平均と C-A の平均変動率の差の平均はともに 15〜20% のプラス値になり，GroupA に属する部品の評価値が下がりやすいことが分かる．この結果が統計的に有意な差があるかを Welch の t検定を用いて，GroupA と GroupB，GroupA と GroupCの二つの対応するグループにおける評価値の変動率を比較したところ，GroupA と GroupB についての t 検定 (α=0.01) では，効果量 d=1.04000，検定力 1-β=0.9998752，一方，GroupA と GroupC についての t 検定 (α=0.01) では，効果量 d=0.94610，検定力 1-β=0.9993245，といずれの場合も十分大きな値が得られ，有意な差があることを確認できた。これらの結果から，統合した部品群のどれかから利用されており，ある部品群内の２つ以上の部品から利用されている部品は１つのみ，あるいはその他の部品に比べ評価値が大きく減少することが成り立つことを示している．一方で，GroupA の評価値の低下より，B，C の評価値の低下の方が大きいプロジェクトも 1 割強存在したので，それらの原因も調査し考察する．

図 1 プロジェクト単位での GroupA の分布
表 2 プロジェクト単位で見た時の変動率の差
B-AC-A

プロジェクト数差の平均標準偏差363720.8%
15.8%

2016.70 以上
35

図 2 プロジェクト単位での GroupB の分布

図 4 B-A の変動率の分布

図 3 プロジェクト単位での GroupC の分布

4.2

プロジェクト単位で見た時の変動率の差GroupA と GroupB が両方とも存在する 36 のプロジェクトに対して A の平均変動率と B の平均変動率の差，GroupA と GroupC が両方とも存在する 37 のプロジェク

図 5 C-A の変動率の分布

0 未満
3332

4.3

プ ロ ジ ェ ク ト 毎 の TOP5，TOP10，TOP15，TOP20

合，プロジェクトによっては距離の設定を適切にすることで精度が向上する可能性があることがわかる．
表 4 CardMe

各プロジェクトで，評価値が減少した部品のみを対象に，その中で減少度合いの大きい部品の TOP5 と TOP10，TOP15，TOP20 までを抽出し，それらの部品が GroupA，B，C のどれに属するかを調査した．ただし GroupA の部

abc

部品数

変化前変動率1431994%
93.1%
94.7%

部品数

変化前変動率

23325596.9%
91.2%
84.7%

部品数

変化前変動率105693.1%
90.2%
93.1%

品が全て抽出された段階で，それ以下の順位の部品は無視

TOP10，TOP15，TOP20 を対象にした場合，その割合がabc下がることも確認した．

GroupC の割合
総部品数164267391
501

変化後変動率310
2470.4%113.9%
92.3%

A との差
0%
43.5%
22%

A との差0%-5.7%-12.14%変化後部品数変化後変動率213756

94.3%
98.7%
99.6%

A との差
0%
4.4%
5.3%

表 6 vietime

表 3 TOP5，TOP10 の部品が属する GroupA，GroupB，TOP5
TOP10TOP15TOP20

変化後部品数

表 5 jackcess

している．結果を表 3 に示す．表 3 より，TOP5 の部品が属する割合では，GroupA が 76.8% と大部分を占めるが，A との差
0%
-0.9%
0.7%

GroupA
76.8%
73.4%
62.4%
53.7%

GroupB
17.7%
19.9%
20.5%
20.6%

GroupC
5.5%
6.7%
17.1%
25.7%

abc

A との差
0%
-2.9%
-0.1%

変化後部品数変化後変動率

41241

69.6%
92%
99.3%

A との差
0%
22.4%
29.7%

おわりに

6

本研究では，実際のオープンソースプロジェクトのソースコードを対象に，コンポーネントランク計算において，部品グラフ上のコードクローン関係を持つ部品を統合する

5考察

5.1

プロジェクト単位での評価値の変動率

手法を適用し，適用前後で統合する内部の 2 つ以上の部品から利用されている部品は，統合する内部の部品の 1 つからのみ利用している部品や関係のない部品より，大きな評

図 1 より，グループごとの評価値の平均値を押し上げる価値の減少が見られることを確認した．結果からは，既存結果となっているプロジェクトが３つ存在することが分かのコードクローンが共通して利用している部品を検出する

り，プロジェクト単位で原因を調査した結果，以下のこと

仕組みを実現する上で，部品グラフ上の評価値の変化といがわかった．

う観点からは，コンポーネントランク計算において，部品• 統合した部品の評価値が統合する前と比べて大幅に増加したことで利用先の評価値も大きく増加した．

• 統合した部品内で他の部品を大量に使っている部品がが有効であると考えられる．

参考文献

存在し，その部品は統合した内部の部品も使っていた[1] 千賀英佑． コードクローンを利用したソフトウェア部

ことから，統合した内部の部品が他の内部の部品を大品の評価手法についての考察． ，南山大学大学院数理量に使用していたことにより，利用先の評価値が大き情報研究科 2013 年度修士論文，2014．

く増加した．
以上のことから，部品グラフの内部構造を変化が大きい
場合，想定以上に評価値が変動する場合があるということがわかった．

5.2

グラフ上のコードクローン関係を持つ部品を統合する手法

プロジェクト単位で見たときの変動率の差[2] Katsuro Inoue，Reishi Yokomori，Tetsuo Yamamoto，
Makoto Matsushita，and ShinjiKusumoto． Ranking
Significance of SoftwareComponents Based on Use
Relations ，IEEE Trans．SoftwareEngineering，vol．
31，no．3，pp．213-225，2005．と推測できた．そこで，３つのプロジェクトに対し，パッ[3] Toshihiro Kamiya，Shinji Kusumoto，and KatsuroInoue． CCFinder:．A Multi-Linguistic Token-based
Code Clone Detection System for Large ScaleSource
Code ，IEEE Trans．SoftwareEngineering，vol．28，
no． 7，pp．654-670，2002．

ケージ間の距離が２以内の部品を統合するよう再設定し分[4]

GroupA の評価値の低下より，B，C の評価値の低下の方が大きいプロジェクトが 3 つ存在した．この 3 つのプロジェクトの共通点を調査すると，統合する部品間の距離が遠く，部品グラフの内部構造が劇的に変化しすぎたため析した．ここで距離とはあるパッケージ階層からあるパッClassycle: Analysing Tools for Java Class andPackage Dependencies，

ケージ階層まで到達するためのパッケージ階層の移動回数

http://classycle.sourceforge.net/である．その結果を次の表 4，5，6 に示す．
表 4，5，6 より A の評価値は減少し B，C の評価値は増加の傾向にあることがわかる．よってこの手法を用いる場[5]

検定力分析のすすめ，

http://www.relak.net/psy/power/.