大規模ソフトウェアリポジトリにおける ソフトウェア部品間の 依存関係解析に関する研究 大学院情報科学研究科 コンピュータサイエンス専攻 井上研究室 市井 誠 [email protected] 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 1 ソフトウェアとソフトウェア部品 ソフトウェアはソフトウェア部品（部品）から構成される ソフトウェア部品は互いに依存関係を持つ クラスや関数など 変数宣言やメソッド呼び出しなど ソフトウェア部品グラフ（部品グラフ） ソフトウェア部品間の依存関係をグラフで表現したもの 構築方法に応じて，ソフトウェアの様々な特徴が反映される ソースコードの静的な解析に基づくグラフ: 設計などの静的な構造 実行結果のトレースに基づくグラフ: オブジェクト間の相互作用などの振舞い ソフトウェア 2008/12/24 ソフトウェア部品グラフ 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 2 ソフトウェア部品検索システム ソフトウェア再利用 ソフトウェア開発に，既存の部品を用いること 効率的な再利用によりソフトウェア開発コストを削減できる ソフトウェア部品検索システム ソフトウェアを収集してソフトウェアリポジトリを構築 ユーザの問い合わせに対し，適合する部品を提供 オープンソースソフトウェ ア (OSS) ソフトウェア部品検索システム 収集・蓄積 検索 ソフトウェアリポジトリ 2008/12/24 開発現場で 過去に開発されたソフトウェア 取得 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3 ソフトウェアリポジトリでの 依存関係 既存研究では，個々のソフトウェアで閉じた依存関係のみを解析 ソフトウェアリポジトリには，ソフトウェアをまたがった依存関係が存在 ライブラリの再利用など ソフトウェアリポジトリ全体の依存関係に着目 ソフトウェアをまたがった依存関係を含む 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 4 研究内容 大局的な依存関係の性質の調査 部品グラフのスケールフリー性に関する調査 局所的な依存関係の理解支援 部品を再利用する時に必要な，部品間の依存関係の理解を支援 する手法を提案 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 5 論文の構成 第1章 まえがき 第2章 Javaソフトウェアの部品グラフにおけるべき乗則の調査 [1-1][1-4] 第3章 再利用支援のためのソフトウェア部品の依存関係解析手 法 [1-2][1-3][1-5] 第4章 むすび [1-1] 市井誠, 松下誠, 井上克郎, “Java ソフトウェアの部品グラフにおけるべき乗則の調査”, 電子情報通信学会論文誌D-I, Vol.J90-D, No.7, pp.1733 – 1743, 2007 年7 月（学術論文） [1-2] 市井誠, 横森励士, 早瀬康裕, 井上克郎, “再利用支援のためのソフトウェア部品の依存関係解析手法”, 電子情報通信学 会論文誌D-I 投稿中（2008 年8 月受付）（学術論文） [1-3] Makoto Ichii, Reishi Yokomori, Katsuro Inoue, “Towards Effective Reference Analysis for Software Component Retrieval System”, Proc. Workshop on Accountability and Traceability in Global Software Engineering (ATGSE2007), pp.51– 52, Dec. 2007 （国際会議録） [1-4] Makoto Ichii, Makoto Matsushita, Katsuro Inoue, “An Exploration of Power-law in Use-relation of Java Software Systems”, Proc. 19th Australian Software Engineering Conference (ASWEC2008), pp.422 – 431, Mar. 2008 （国際会議録） [1-5] Makoto Ichii, Takashi Ishio, Katsuro Inoue, “Cross-application Fan-in Analysis for Finding Applicationspecific Concerns”, Proc. 4th Asian Workshop on Aspect-Oriented Software Development (AOAsia4), http://appsrv.cse.cuhk.edu.hk/~aoasia/workshop/APSEC08 , Dec. 2008 （国際会議録） 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 6 Javaソフトウェアの部品グラフにおける べき乗則の調査 第2章 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 7 べき乗則 グラフの特徴が現れる次数分布に関する調査を行う スケールフリー性 次数分布にべき乗則が成り立つ性質 様々な分野で注目されている ウェブページのリンク関係 社会ネットワーク グラフが特徴的な性質を持つことが多い 耐障害性 自己相似性 既存研究により，部品グラフが べき乗則に従うことが示されている [47][64]… 既存研究の問題点 個々のソフトウェアで閉じた依存関係のみを解析 部品グラフが静的な依存関係を表現できていない 継承などの「代表的な」参照関係のみを解析 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 8 調査方針 より詳細な静的解析に基づく部品グラフを用いる ソフトウェアをまたがる依存関係を含む部品グラフを調査 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 9 調査方法 対象の部品集合を解析して部品グラフを構築 部品グラフの入次数・出次数の分布を調査 部品グラフ 頂点（部品）: Java クラス 辺（依存関係）: 静的に解析される参照関係 継承・実装・変数宣言・オブジェクト生成 ・メソッド呼出し・フィールド参照 class A { void exec() { … } class B { } … A.exec(); … } 2008/12/24 入次数: 2 出次数: 0 A class C { … Aa= new A(); … } B 入次数: 0 出次数: 1 C 入次数: 0 出次数: 1 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 10 次数分布の調査 両対数軸を用い，累積度数を プロット 分布がべき乗則に従えば，直 線状になる 回帰直線を求め，α の値と寄与 率 R*2 を得る α 回帰直線の値から求める 寄与率 p(x) = Cx-α 傾き : -(α-1) 傾き : -α R*2 モデルへの適合度を表す値 [0..1] degree 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 11 調査対象の部品集合 単一のソフトウェア ANT ANT: Apache Ant 1.6.2 (ビルドツール) JBOSS JBOSS: JBoss Application Server 3.2.5 (サー バー) JDK JDK: Java Development Kit 1.4 (Java標準ライブ ECLIPSE ラリ) ASF ECLIPSE: Eclipse 3.01 (開発環境) SPARS_DB ソフトウェア集合 ASF: Apache Software Foundationのソースコー ド管理システムから取得したソフトウェア集合 RND REL KWD 頂点数 辺数 1,260 4,995 5,752 23,636 11,556 107,198 13,941 140,678 59,486 303,755 180,637 1,808,982 10,000 9,286 8,938 6,184 17,201 24,317 LOC 95K 424K 1.1M 1.3M 4.5M 14M 780K 2.1M 1.6M 約100種類のソフトウェアを含む SPARS_DB: ソフトウェア部品検索システム SPARS-J のリポジトリに蓄積されたソフトウェア 集合 約750種類のソフトウェア SPARS_DB の 部分集合 RND: ランダムに選択した部品集合 REL: ある部品を利用する部品集合 基準の部品はランダムに選択 KWD: ある単語をソースコード中に含む部品集合 単語はランダムに選択 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 12 結果 – 入次数 ANT ECLIPSE JBOSS ASF JDK SPARS_DB X: 入次数, Y: 累積度数 ANT JBOSS JDK ECLIPSE ASF SPARS_DB RND REL KWD RND 2008/12/24 REL α ± 2.0×102 ± 2.0×102 ± 8.2×103 ± 1.6×102 ± 1.1×102 ± 1.5×103 R*2 0.98 0.98 0.99 0.96 0.98 1.00 2.0 ± 2.1×102 2.3 ± 2.0×102 2.1 ± 9.3×102 0.98 0.99 0.99 2.0 2.3 2.1 2.2 2.4 2.0 入次数は， α ≒2のべき乗則に従う KWD 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 13 結果 – 出次数 ANT ECLIPSE JBOSS ASF JDK SPARS_DB X: 出次数, Y: 累積度数 ANT JBOSS JDK ECLIPSE ASF SPARS_DB RND REL KWD RND 2008/12/24 REL α ± 1.4×101 ± 1.0×101 ± 8.2×102 ± 7.7×102 ± 6.4×102 ± 6.9×102 R*2 0.87 0.91 0.88 0.86 0.94 0.90 4.4 ± 3.3×101 4.0 ± 2.5×101 3.5 ± 8.7×102 0.91 0.87 0.96 2.9 3.2 3.1 3.0 3.4 3.7 出次数は， べき乗則には従わない KWD 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 14 考察 – 入次数はべき乗則に従う 単一のソフトウェアだけでなく，ソフトウェアリポジトリや， その部分集合においてもべき乗則に従うことが示された 既存研究よりも，理想的な分布に近い 標準ライブラリを中心とした，階層的な依存関係が存在する と考えられる 大小様々なソフトウェアが，互いに依存している 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 15 考察 – 出次数はべき乗則に従わない 既存研究と比較して，より妥当な結果が示された 既存研究は，出次数もべき乗則に従うと主張 出次数は，部品の規模と強い相関を持ち，複雑度とも弱い相関 をもつ 対数正規分布とべき乗則の中間の分布 ファイルサイズに見られる分布 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 16 再利用支援のための ソフトウェア部品の依存関係解析手法 第3章 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 17 軽量な再利用 再利用に対するアプローチ 組織的な再利用 軽量な再利用 計画的に再利用可能な部品を開発する 開発プロセスに再利用を組み込んだ，無駄のないアプローチ × 組織の改編を含む，再利用に対する大規模な投資を必要とする 必要に応じて，既存の部品の中から検索する 事前の投資を必要とせず，容易に導入できる × 部品の取得や，ソフトウェアへの組み込みに支援を必要とする 既存の大量の資産を活用できる，軽量な再利用に着目 WWWを通じて入手可能なオープンソースソフトウェア Apache Software Foundation, SourceForge.net, Eclipse, … 開発現場で過去に開発されたソフトウェア 依存関係が複雑になりやすい，オブジェクト指向ソフトウェアを対象 とする 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 18 軽量な再利用の手順 1. 部品の取得 ソフトウェア部品検索システムなどを用い，再利用可能な部品を取得する 様々な検索システムを利用可能 SPARS-J: 部品再利用に特化した検索結果の順位付け Google code search: 大規模なデータベースと，正規表現検索 Koders: OSS開発プロジェクトとの連携 2. 依存関係の理解と処理 取得した部品が依存する部品を調査 追加で取得，もしくは，部品を修正して依存関係を変更 限定的な支援のみ: ソフトウェアをまたがった依存関係や，類似部品の存在を考慮していない 依存関係の理解支援手法 [26] B.foo(); A 2008/12/24 B 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 19 ソフトウェアリポジトリにおける 部品の依存関係の理解 手作業での調査および理解は，困難 ソフトウェアリポジトリ中には，類似したAPIを持つ部品が複数存在 直接ソースコード上に現れない，間接的な依存関係が存在 依存関係の整合性を取る必要が有る 同じ名前で参照され，同一もしくは類似した操作や属性を所有 継承されたメンバの参照など 部品は一般に複数箇所で参照される 依存する部品同士にも，依存関係が存在 B.foo(); B.foo(); B.bar(); A B ? ? ? B B2 Cを継承 B 2008/12/24 B1 Cを継承 void foo() {…} A1 B1 & C1 Cを継承 void foo() {…} void bar() {…} B1 & C2 C B2 & C1 C1 void foo() {…} C B3 B2 & C2 B3 & C2 C2 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 20 研究の目的 利用者が選択可能な形式で再利用対象のクラスの依存関係の候補を 抽出し，再利用を支援する 入力: 再利用対象のクラス集合 出力: 再利用単位 互いに等価なクラス集合を要素とする集合 利用者は，得られた再利用単位から選択することで， 再利用対象のクラスの依存関係を得ることが出来る B A B B1 B2 C C1 (B1 | B2 ) & C1 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 21 提案手法の概略 再利用対象のクラスから参照されるクラスを取得し，それら の関連を依存グラフとして表現 依存グラフを用いて，再利用対象のクラスが依存する部品集 合の候補である再利用単位の集合を抽出 依存グラフ 対象クラス A A 再利用単位 AB C A AB C B C A B C ソフトウェアリポジトリ AB B 2008/12/24 CC 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 22 依存グラフの構築 (1/2) 対象クラスから，他のクラス/メンバへの参照を抽出し，参照先を特定 候補が複数存在する場合は，全てを用いる 頂点: クラス 辺：参照名をラベルとして持つ 参照元クラスから参照先クラスへの有向辺 特定の際に経由したクラスを用いて，中間グラフを構築 クラスへの参照のみ 参照先 対象クラス B.foo(); B.bar(); A A1 2008/12/24 依存グラフ（中間グラフ） •B B1 B2 B3 •foo() B1のfoo() B2のfoo() C2のfoo() • B3の継承先CをC2に特定 •bar() C1のbar() • B1の継承先CをC1に特定， または • B2の継承先CをC1に特定 B A1 B1 B B2 B B3 C C1 C C 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University C2 23 依存グラフの構築 (2/2) 中間グラフの頂点をグループ化し，依存グラフを構築 以下の条件を満たす頂点をグループ化 入力辺と出力辺の集合が一致 特定可能な参照の集合が一致 依存グラフ（中間グラフ） 依存グラフ B, foo() B A1 B1 B B2 B, foo() B B3 C C1 C bar() C C2 A1 B B B1 B2 C B3 C C1 C2 foo() 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 24 再利用単位の抽出 依存グラフを探索することで再利用単位を抽出 再利用対象のクラスが始点 一つの頂点から，重複する複数のラベルをもつ辺を利用しない 衝突する部品を選択することを避ける 依存グラフ B A1 B 2008/12/24 B1 B2 B3 再利用単位 C C1 C C2 A1 B1 B2 C1 A1 B3 C2 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 25 完全性の判定 完全な再利用単位 参照先を特定すべき参照が，すべて特定される 依存グラフ上のいずれかのクラスを用いることで特定可能な参照 不完全な再利用単位 特定できない参照が存在する 再利用単位 参照先 完全性 B foo() bar() A1 B1 B2 C1 B1 ,B2 {B1, B2}の foo() C1のbar() A1 B3 C2 B3 C2のfoo() × 2008/12/24 ○ × 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 26 ヒューリスティクスによるフィルタリング 1. 事実上意味のない再利用単位をヒューリスティクスにより除外する 入力所属の優先（依存グラフ構築時） グループ内のいずれかのクラスが入力クラスと同じ所属なら，それ以外を 除去 所属: クラスの取得元（ソフトウェアの配布パッケージなど） 2. 入力クラスと同じ所属のクラスが利用出来るなら，それを使うべき 経由する頂点の所属に一貫性を持たせる 不必要に異なるパッケージにまたがることを防ぐ 所属の一貫性（再利用単位抽出） P D1 D2 2008/12/24 D A1 D X B B Q Y B1 B ×2 C B3 C C1 C2 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 27 適用例 OSSを用いて構築したソフトウェアリポジトリに対し，提案 手法を適用 ソフトウェアリポジトリ Java Standard API のソースコード 3 バージョン JDK 1.2.2, JDK 1.3.1, JDK 1.4.2 の配布パッケージ Apache commons のライブラリ 127パッケージ 33種類のライブラリの異なるバージョン 総クラス数: 2008/12/24 22,005 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 28 適用例 SCInstance (commons-scxml-0.5) の例 2個の再利用単位が得られた 手作業での調査には労力を要する 一方は不完全: "getCause()"メソッドが不足 いずれも 22種類のクラスに依存 継承関係を追う必要が有る 依存クラス数が多い 依存グラフ（一部） SCInstanceのソースコード（一部） InstanciationException(Java 1.4) InstanciationException(Java 1.3) InstanciationException(Java 1.2) public Throwable getCause() {…} Throwable(Java 1.4) Exception Throwable InstanciationException SCInstance Exception(Java 1.4) (getCause()を持た Exception(Java 1.3) ない) Exception(Java 1.2) Throwable Throwable(Java1.3) Exception Throwable(Java1.2) IllegalArgumentException IllegalArgumentException(Java 1.4) IllegalArgumentException(Java 1.3) IllegalArgumentException(Java 1.2) … 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 29 むすび ソフトウェアリポジトリに含まれるソフトウェア部品間の依 存関係に着目した研究 ソフトウェアリポジトリを用いた部品グラフの次数分布の調査 入次数はべき乗則に従い，出次数はべき乗則に従わないことが示 された 再利用支援を目的とした，部品の依存関係解析手法を提案 ソフトウェアリポジトリから，依存する部品の候補である再利用 単位の集合を抽出 2008/12/24 博士学位論文公聴会 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 30
© Copyright 2024 ExpyDoc
