ソフトウェア部品の利用関係におけるスケールフリー性の調査

Presentation on theme: "ソフトウェア部品の利用関係におけるスケールフリー性の調査"— Presentation transcript:

1 ソフトウェア部品の利用関係におけるスケールフリー性の調査
○市井　誠，松下　誠 ，井上　克郎 大阪大学 大学院情報科学研究科 2005/12/20 SIGSS

2 ソフトウェアの部品グラフ ソフトウェア部品 ソフトウェアの部品グラフ C E A B D ソフトウェアの構成単位 互いに利用関係が存在
ソフトウェア部品を頂点・利用関係を有向辺としたグラフ ソフトウェアの静的な構造を反映 クラス図も部品グラフの一種 理解支援などに利用される 呼び出し関係をみる 依存関係の強い部品群の抽出 … C E 背景としてソフトウェアの部品グラフについて。 ソフトウェアは部品から構成され、その部品間には利用関係が存在する。 　例えば、Javaのクラスを部品とすると、変数宣言やメソッド呼び出しなどが利用関係となる。 ソフトウェアの部品グラフとは、部品を頂点、利用関係を有効辺としたグラフ． 　右下のグラフは5個の部品からなる部品グラフ． ソフトウェアの静的な構造を反映しており、ソフトウェアの理解支援などに利用される 例えば、「部品Cは部品A,B,Eから呼び出されている」といった呼び出し関係を得るのに利用されたり、 またさらに深い解析をおこない、依存関係の強い部品群をモジュールとして取り出すために利用される． A B D 2005/12/20 SIGSS

3 スケールフリー性 スケールフリー性: ソフトウェアの部品グラフにみられる性質 グラフの頂点の接続辺数の分布が，べき分布となる性質
p(x) = Cx-a 他にも，様々な分野で見られる性質 例: インターネット上のノードのネットワーク ランダムな障害に強く，攻撃に弱いなどの性質をもつ べき分布 正規分布 極端に大きな値をもつ要素が，ごく少数存在 ソフトウェアの部品グラフに見られる性質の一つであるスケールフリー性について スケールフリー性とは、グラフの頂点の接続辺数の分布がべき分布となる性質 べき分布とは、正規分布のように - 多くの要素が平均値付近に集まる - あまり極端な値はなく、あっても外れ値として無視できる という分布ではなく， - ほとんどの要素は0に近い値 - 値が大きくなるにつれて一気に減少 - 極端に大きな値をもつ要素が，ごく少数存在 という分布. この性質は、ソフトウェア部品グラフだけではなく他の様々な分野で見られて研究されている。 例えば、インターネット上のノードのネットワークがスケールフリー性をもち ランダムな障害に強く，攻撃に弱いなどの性質をもつことがしられている． 多くの要素が平均値付近 ほとんどの要素は，0に近い値をもつ 値が大きくなるにつれ，要素数は一気に減少 2005/12/20 SIGSS

4 部品グラフとスケールフリー性 だから，何? 部品グラフのスケールフリー性に関する既存研究
[Valverde03] JDKなどのクラス図がスケールフリー性をもつことを示している 最適なソフトウェア設計による結果であると考察 [Myers03] いくつかのJavaおよびC++のソフトウェアの部品グラフがスケールフリー性をもつことなど，グラフとしての性質についての調査結果を示している そのような性質をもつグラフを生成するモデルを提案している． グラフとして共通する性質を得ることに主眼がおかれている 対象ソフトウェアによる違いについては触れられていない 個々の部品との関連や，ソフトウェアの設計との関連は調査されていない だから，何? 部品グラフのスケールフリー性に関する研究も，今までにいくつか存在する． 内容としては， ・JavaやC++など、様々なオブジェクト指向アプリケーションに関して 　スケールフリー性、およびその他のグラフとしての性質が示されている ・その要因 ・そのような性質を持つ、ソフトウェア部品グラフを生成するモデル とが示されている。 しかし、論文を読み終わると「だからなんですか？」という疑問が出てくる。 これは論文の内容が悪いのではなく、今までの研究は数学的な興味に基づき「グラフとして共通する性質」に主眼が置かれており， 応用するときに必要となる、 ・対象ソフトウェアによる違い ・個々の部品との関連や，ソフトウェアの設計との関連 は調査されていないため，例えばソフトウェアの分析への応用は難しい Sergi Valverde and Ricard V. Sole, “Hierarchical Small Worlds in Software Architecture”, 2003 2005/12/20 SIGSS Christopher R. Myers, “Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs”, Physical Review E 68, 046116 ,2003

5 研究の目的 対象ソフトウェアの設計や，個々の部品との関連に注目し，部品グラフのもつスケールフリー性を調査する
入力辺数および出力辺数は，個々の部品のどの性質と関連が深いのか？ 対象ソフトウェアによって分布に違いがあるのか？ 違いがあるなら，その違いはどこからきているのか？ 得られた結果をもとに，理解支援手法への応用について考察 そこで本研究では，グラフの分布の特徴などの性質をみることによってソフトウェアに関する「使える」情報を得る ということを最終的な目標として， 対象ソフトウェアの設計や個々の部品との関連に注目し，部品グラフのもつスケールフリー性について調査する． 具体的な注目点としては， ・入力変数および出力辺数は，個々の部品のどの性質と関連が深いのか ・対象ソフトウェアによって，その分布に違いはあるのか ・違いがあるのなら，その違いはどこからきているのか， という点． そして，調査により得られた結果を基に，今回はソフトウェアの理解支援手法への応用について考察． A B C E D このソフトウェアは○○○だ！ 2005/12/20 SIGSS

6 調査内容 [1/3] 調査1: 分布と含まれる部品との関連を調査 調査2: ソフトウェアによる分布の違いを調査
入力辺数と出力辺数の分布の調査 プロット図 上位の部品の内容を確認し，関連を考察 入力辺数と出力辺数，その他のメトリクスとの相関の調査 メトリクス：行数・メソッド数 調査2: ソフトウェアによる分布の違いを調査 外見が類似したソフトウェア同士の分布を比較 用途および規模 具体的な調査内容について．調査は大きく2つに分かれる． 1つめの調査として，入力辺数および出力辺数の分布と，含まれる部品との関連を調査する． まず，分布をプロットしてその特徴をみるとともに， 上位の部品の内容を確認し，関連を考察する． 続いて，入力辺数と出力辺数と，その他のメトリクスとの相関を調査する． ここではメトリクスとして行数およびメソッド数を用いる． 2つめの調査として，ソフトウェアによる分布の違いを調査する． 具体的には，外見，すなわち用途および規模が類似したソフトウェア同士を比較し， 異なる点についての考察をおこなう． 2005/12/20 SIGSS

7 調査内容 [2/3] べき分布の見方 両対数軸でプロットする 値が直線上に並ぶ 値の大きい部分での誤差を吸収するため，累積度数でプロット
p(x) = Cx-a 傾き: -a 傾き: -(a-1) 見づらい ここで，分布をプロットして確認すると言ったが，先駆けてべき分布のプロットの見方について説明 べき分布は，示すように普通に横軸に辺の数，縦軸に部品数をとると， 値が軸に張り付くようにプロットされてしまい，特徴がほとんど分からないという問題点がある． そこで，一般にべき分布は横軸，縦軸ともに対数を取って表示される． このとき，べきの乗数が傾きとなる直線上に値が並ぶ． つまり，このプロット結果を線形回帰することで，パラメータaを求めることができる． ただし，値の大きい部分では，どうしても値にばらつきが出てしまうために， さらに，上位からの累積度数でのプロットが利用される． 累積度数でプロットした場合，それぞれの点は「ある値以上をもつ部品の数」となり， 示すように誤差が吸収されてよりきれいにならぶ． この時の傾きは，詳細は省略するが，1変化したものとなる． 値の大きい部分にばらつき 2005/12/20 線形軸でのプロット 両対数軸でのプロット SIGSS 両対数軸での累積度数プロット

8 調査内容 [3/3] 対象: Javaソフトウェア データセット 4種類 部品：Javaのクラス
継承,実装,変数宣言,生成,フィールド参照,メソッド呼び出し データセット 4種類 内容 説明 クラス数 D1 JDK1.4 Java 基本ライブラリ 約11,000 D2 ソフトウェア集合 JDK, Eclipse, NetBeans, Apache Project, SourceForgeから 約180,000 D3 Eclipse 統合開発環境 約14,000 D4 NetBeans 約13,000 調査1 調査対象について 対象はJavaのソフトウェアとし，部品はJavaのクラスとする．ちなみにインターフェースもクラスに含まれる． 利用関係は全ての利用関係とする． 利用するデータセットは調査1,2にそれぞれ2種類ずつの4種類用意． まず調査1に用いるデータセットとして， Javaの基本ライブラリであるJDKのソースコード　約1万1千クラスおよび， JDKを含むソフトウェア集合 約18万クラスを用意． また，調査2に用いるデータセットとして， Javaの統合開発環境であるEclipseおよびNetBeansを用意．それぞれ約14,000クラスおよび約13,000クラスと類似した規模． では調査1の結果から説明． 調査2 2005/12/20 SIGSS

9 調査1 [1/6] 入力辺数の分布 D1(JDK) a=2.11 べき分布に従う lang パッケージのクラスが上位を占める
左の図は横軸が入力変数，縦軸が部品数で，両対数軸でプロットしたものであり， 右の図は累積度数でプロットしたもの 見て分かるように，良い感じに直線にならんでおり べき分布に従っていることがわかる． 上位の部品をみてみると，JDKのなかでも 基礎的な lang パッケージのクラスが並んでいる． 特に，文字列をあらわすStringクラス，全てのクラスの親クラスとなるObjectクラスが極端に大きな値をもっている 以降は lang パッケージのクラスが上位を占めている --- a=2.11±0.01 クラス名 行数 メソッド数 出力辺数 入力辺数 1 java.lang.String 667 70 21 6420 2 java.lang.Object 34 13 4 5861 3 java.lang.System 169 35 27 1527 java.awt.Component 2792 256 117 1317 5 java.lang.Class 604 74 41 1026 ... … べき分布に従う lang パッケージのクラスが上位を占める String, Objectが極端に大きな値をもつ 2005/12/20 SIGSS

10 調査1 [2/6] 入力辺数の分布 D2(ソフトウェア集合) a=2.02 値域が D1 と大きく異なる
クラス数は約16倍と大幅に増えたが，上位2クラスはかわらずStringとObject． しかし，その値は大きく増えており，20倍近い入力辺数をもつようになり，値域が極端に広くなっている． また，他の上位クラスとしては， langパッケージの占める割合が増え， ここでは欄外だが，10位付近では ユーティリティパッケージのクラスも多くみられる． JDK以外はほとんど無い． このように，基礎的なクラスが多くの入力辺を集めている，という傾向が見られた． --- a=2.02±0.01 クラス名 行数 メソッド数 出力辺数 入力辺数 1 java.lang.String 667 70 21 116239 2 java.lang.Object 34 13 4 98261 3 java.lang.Class 604 74 41 29682 java.lang.Exception 14 21046 5 java.lang.Throwable 134 12 19519 … 値域が D1 と大きく異なる lang, util パッケージのクラスが上位を占める String, Objectが極端に大きな値をもつ 2005/12/20 SIGSS

11 調査1 [3/6] 出力辺数の分布 D1(JDK) べき分布とは異なる分布 入力辺数と比較し，値が小さい
一見，入力辺数と同様のべき分布に見えるが，2箇所大きくことなる点がある． ・べき分布は単調減少なのに対し，こちらは2付近にピークが見られる ・上位も値が小さい 上位クラスの内容としては，GUIなど，複雑なロジックや単に大きい実装を行っているクラスが上位 --- 参) 直線回帰すると，a=3.12 クラス名 行数 メソッド数 出力辺数 入力辺数 1 sun.awt.windows.WToolkit 535 101 140 14 2 com.sun.corba…ORB 1474 135 131 50 3 sun.awt.motif.MToolkit 371 70 130 9 4 sun.jvm.hotspot…BugSpot 1063 68 118 5 java.awt.Component 2792 256 117 1317 … べき分布とは異なる分布 入力辺数と比較し，値が小さい 複雑なロジックを実装するクラスが上位 2005/12/20 SIGSS

12 調査1 [4/6] 出力辺数の分布 D2(ソフトウェア集合) 値域はD1と大きくは変わらない
同様にソフトウェア集合の出力辺数の分布を示す JDKの時と同様，2辺りにピークの見える違った分布 また，値域も2倍程度にしか大きくなっていない． 上位クラスについては，トップは単純に多くのクラスを呼び出すクラスで， 2～3位は大きなサンプルクラス，5位は複雑な実装クラス，となっている． 複雑で大きい，以外の共通点は見られない． 以上のように，単に，複雑で大きなクラスが多くの出力変数をもつ，という傾向が見られた． --- 参) 直線回帰すると，a=3.66 クラス名 行数 メソッド数 出力辺数 入力辺数 1 org.apache.poi…FunctionEval 11 3 354 2 org.jgraph.GPGraphpad 2190 127 255 129 com.jgraph.GPGraphpad 2195 253 130 4 540 56 210 5 org.eclipse.jdt…ASTConverter 4492 159 222 … 値域はD1と大きくは変わらない 上位は複雑な実装をおこなうクラスの他，単純に多くのクラスを呼び出すクラスおよびサンプルのクラスなど 2005/12/20 SIGSS

13 調査1 [5/6] メトリクスとの比較 スピアマンの順位相関係数 入力辺数は，出力辺数や行数，メソッド数と相関が見られない
出力辺数は行数，メソッド数と相関が高い 部品そのものから得られるメトリクス D1(JDK) D2(ソフトウェア集合) 出力辺数 行数 メソッド数 入力辺数 0.075 0.11 0.34 - 0.73 0.63 出力辺数 行数 メソッド数 入力辺数 0.00 0.07 0.24 - 0.83 0.64 値同士の，スピアマンの順位相関係数を取ることで比較する． 　-1～1の値を取る．1に近いほど正の相関が高く，-1に近いほど負の相関が高い．0に近いと相関が低い． 　0.6以上で相関があると言え，0.8以上あると相関が高いと言える． 結果を表にまとめるとこのようになっている． 　入力辺数については，どちらのデータセットでも，どの値も0付近，多くて0.3 と，相関があるとは言えない値が並ぶ 　出力辺数については，行数およびメソッド数と相関が高いといえる．とくに行数と高い． 　　これは，先ほどの上位部品の傾向と一致し，異なる意味で「部品の規模」をあらわしていると言える． 2005/12/20 SIGSS

14 調査1 [6/6] まとめと考察 入力辺数 出力辺数 クラスの役割との関連が強いと考えられる クラス自身との内容とは関連が弱い
調査1 [6/6] まとめと考察 入力辺数 クラスの役割との関連が強いと考えられる 基礎的な役割をもつクラスに利用関係が集中 クラス自身との内容とは関連が弱い 同じクラスでも，データセットにより値が大きく異なる 他のメトリクス(行数，メソッド数)と相関が低い 出力辺数 クラス単体の規模や複雑さと関連 データセットにより，値域にあまり差が無い 他のメトリクス(行数，メソッド数)と相関が高い 以上の調査1の結果をまとめ，考察をおこなう まず入力辺数について， 　クラスの役割との関連が強いと考えられる． 　　調査では，基礎的な役割をもつクラスに利用関係が集中するという傾向がみられた． 　逆に，クラス自身の内容とは関連が弱いと考えられる 　　調査では，同じクラスでも，データセットにより値が大きく異なるという結果，および， 　　行数やメソッド数のメトリクスと相関が低いという結果が出た 続いて出力辺数について 　クラス単体の規模や複雑さと関連 　　調査では，行数やメソッド数といったメトリクスと相関が高く， 　　また，データセットによりあまり値域に差が見られない，という結果があった． 　　　このことは，最大値に上限がある可能性を示している 2005/12/20 SIGSS

15 調査2 [1/4] 対象説明 D3: Eclipse と D4: NetBeans の比較をおこなう 比較内容
どちらも Java の統合開発環境 ほぼ同規模 D3: 14000クラス/120万行, D4: 13000クラス/100万行 比較内容 入力辺数および出力辺数の分布 次に，調査2について まず比較対象について 　D3:Eclipse と D4: NetBeansの比較をおこなう 　これらはどちらも Javaの統合開発環境であり，Javaソースコードの編集およびビルド・デバッグ機能，また構成管理機能をもつ． 　また，D3は14000クラス/120万行, D4は13000クラスで100万行と，ほぼ同規模であるといえる． これらについて，入力辺数および出力辺数の分布を比較する --- Eclipse 3.0 NetBeans 3.5 ダウンロードしてきたアーカイブに含まれるクラス群が対象. 2005/12/20 SIGSS

16 調査2 [2/4] 入力辺数 D3 D4 D3には極端なカットオフ: 傾きの変化がみられる 最大値にも大きな差 D3は利用関係の集中度が低い
最大値:1497 最大値:1921 D3には極端なカットオフ: 傾きの変化がみられる D4にも見られるが，D3ほどでは無い 最大値にも大きな差 D3は利用関係の集中度が低い まず入力辺数の比較 図はどちらも入力辺数の分布を，対数軸かつ累積度数で示したもので， 左側がD3, 右側がD4となっている． どちらも大体直線になるが，D3の方については，約500付近で カットオフとよばれる傾きの変化が極端に見られる． また，最大値をみてみると，D3は最大値1500付近なのに対し，D4では1900以上となっている． これらのことから，D3については，上位でも比較的入力辺数が小さい， すなわち利用関係の集中度が低い，と言える． --- D3: a=2.20 ± 0.02 D4: a=1.99 ± 0.01 ただし平均だと D3: 10.09 D4: 5.14 で逆転. ただし，今の話は上位あたりなので特に問題は無い. (D3は途中まで傾きがやや小さいので，その辺りが効いている) というかD4は単純に辺数が多い． 2005/12/20 SIGSS

17 調査2 [3/4] 出力辺数 D3 D4 分布の形状はほぼ同じ 最大値に大きな差が見られる D3は単位行あたりの利用部品数が多い
最大値:102 最大値:192 分布の形状はほぼ同じ 最大値に大きな差が見られる D3は単位行あたりの利用部品数が多い D3とD4は同程度の総行数 続いて出力辺数を，同様に対数軸かつ累積度数で示す． 先ほどとことなり，分布の形状自体には差がみられない しかし，最大値をみてみると　D3が200近いのに対してD4では100程度と，大きな差がみられる． このことから，D3は全体的に1部品辺りの利用部品数が多いと言える． D3とD4は同程度の総行数であることも考慮すると，D3は単位行あたりの利用部品数が多い，と言える． --- 意味があるかどうか別として，平均だと D2: 10.09 D3: 5.14 こちらも2倍程度の差． (* というか当然入力と同じになる) 2005/12/20 SIGSS

18 調査2 [4/4] まとめと考察 同じ「外見」のソフトウェアD3,D4において，異なる分布の特徴が得られた
また，単位行辺りの利用部品数が多い 得られた特徴には，クラス設計の違いが反映されていると考えられる D3は中心となるクラスの役割が細分化されている 反面，同じ処理を実装するときも，多くの部品を利用する必要がある 調査2まとめ 同様の外見，すなわち同様の機能と，同様の規模をもつソフトウェアD3・D4において， 異なる分布の特徴が得られた．また，その特徴から 　・D3はD4と比較し，利用関係の集中度が低く， 　・また，単位行あたりの利用部品数が多い ということが読み取れた このような得られた特徴には，クラス設計の違いが反映されていると考えられる． つまり， 　・D3は中心となるクラスの役割が細分化されているために利用関係が集中しない， 　・反面，同じ処理を実装するときも，多くの部品を利用する必要がある ということがいえる． #実際に，上位クラスを見てみた結果では，D3では実装をもたないインターフェースが多く， #役割と実装を分けることにより1つのクラスに責任が集中しない設計になっていることがわかった． 以上，調査結果について発表してきたが これだけではやはり「だから何？」という指摘を頂いてしまうので， これらのこと，特に「クラス設計の違いが分布に反映される」ということに注目して ソフトウェアの理解支援への応用について考察する． だから，何? 2005/12/20 SIGSS

19 応用: ソフトウェア理解に対して [1/2] 理解支援を目的とした，クラス設計の分析手法への応用*
クラス設計の理解には，まず中心となる重要クラスを知ることが必要 ソフトウェア中で重要な概念をあらわすクラス Component Rank法により，重要度による順位付けをおこなえる 利用関係に基づく重要度判定手法 入力辺数の多いクラスは重要 重要なクラスから利用されるクラスは重要 順位をもとにクラスのグループ分けをおこない，上位より段階的に理解 グループ分けの閾値の決定方法が確定的で無い 入出力辺数の分布を利用し，グループ分けの閾値を決定する 重要 順位をもとにグループ分け E 1. ………………………………………… 2. ………………………………………… 3. ………………………………………… 4. ………………………………………… 5. ………………………………………… 6. ………………………………………… 7. ………………………………………… … 20.. ……………………………………… 21. ……………………………………… 50. ……………………………………… 51. ……………………………………… 応用として，「理解支援を目的とした，クラス設計の分析手法」への応用を考える 手法自体は8月の研究会で発表．簡単に概要を説明． まず背景として，クラス設計を理解するためには，まず中心となる重要クラスを知ることが必要となってくる． 　ここでいう重要クラスとは，ソフトウェア中で重要な概念をあらわすクラスのこと この意味での重要クラスを見つけるのには，研究室で以前に提案したComponent Rank法が使える． 　Component Rank法は，利用関係に基づく重要度判定手法であり， 　図のDのような，多くのクラスから利用されるクラスは重要， 　Eのような，重要なクラスから利用されるクラスは重要，という概念のもと， 　すべてのクラスについて，重要度での順位付けをおこなうことができる． この手法により得られた順位をもとにして，上位よりグループ分けをおこない， 上位グループから順にクラス図やソースコードを利用して理解することで，効率的にソフトウェアのクラス設計を理解することができる． しかし，この手法は，閾値が重要なのに対して，その決定方法があまり確定的ではなく，「総クラス数をもとに決定して，あとは適度に調整」というもの． ここで，本研究の調査で得られた「クラス設計の違いが入出力辺数の分布に反映される」ということを応用して， 「入出力辺数の分布を利用し，グループ分けの閾値を決定する」ことをかんがえる 重要 D グループごとにクラスを分析 A B C 利用関係をもとに順位付け 2005/12/20 SIGSS *市井, 横森, 松下, 井上, “コンポーネントランクを用いたソフトウェアのクラス設計に関する分析手法の提案”,電子情報通信学会技術研究報告, SS , Vol.105, No.229, pp (2005)

20 応用: ソフトウェア理解に対して [2/2] グループ分けの閾値の決定に，入出力辺数の分布を利用
全クラス数をもとに，閾値を仮決定 入出力辺数の分布をもとに補正 入力辺が特定のクラスに集中 　　　重要クラスは小数: 閾値を高くする 出力辺数が全体的に多い 　　　重要クラスの個数も多い: 閾値を低くする Component Rank法による順位からグループを決定 さらに調査をおこない，具体的な値をもとめる必要がある 最初に仮決定する個数 入力辺数の集中度/出力辺数と，増減の関連 では具体的に説明． まず，全クラス数をもとに，閾値を仮決定． 続いて，入出力辺数の分布をもとにして補正をおこなう ・入力辺数が特定のクラスに集中している傾向があれば，重要クラスは少数であるとし，閾値を高くする ・出力辺数が多ければ，重要クラスも多いとし，閾値を低くする そして，以上により決定された閾値とComponent Rank法により得られた順位をもとに，グループを決定する． しかしこの手法を実現するにはまだこれから具体的な値を調査に基づいて求める必要がある．具体的には， ・まず，最初に仮決定する個数をどう求めるか ・入力辺数の集中度および出力辺数と，閾値の増減をどう関連させるか． ということがある． 2005/12/20 SIGSS

21 まとめと今後の課題 ソフトウェアの部品グラフにおけるスケールフリー性に関して，対象ソフトウェアとの関連に注目して調査を行った
得られた結果をもとにして，ソフトウェア理解支援手法への応用について考察した 今後の課題 重要クラスのグループ分けの閾値を決定する手法を提案 本研究では，ソフトウェアの部品グラフにおけるスケールフリー性に関して，対象ソフトウェアとの関連に注目して調査を行った また，得られた結果をもとにして，ソフトウェア理解支援手法への応用について考察した 今後の課題としては，最後に述べた重要クラスのグループ分けの閾値を決定する手法を詳細に詰めて提案すること 2005/12/20 SIGSS