ネットワーク共生環境を築く情報技術の創出 テーマ4:高信頼性・高安全性を有するネットワーク共生環境の構築技術の創出

Presentation on theme: "ネットワーク共生環境を築く情報技術の創出 テーマ4:高信頼性・高安全性を有するネットワーク共生環境の構築技術の創出"— Presentation transcript:

1 ネットワーク共生環境を築く情報技術の創出 テーマ4:高信頼性・高安全性を有するネットワーク共生環境の構築技術の創出
ネットワーク共生環境を築く情報技術の創出 テーマ4:高信頼性・高安全性を有するネットワーク共生環境の構築技術の創出 大阪大学大学院情報科学研究科 大阪大学サイバーメディアセンター 21世紀COEプログラム（平成14年度採択分） 情報・電気・電子分野 （拠点番号: C12） 井上克郎 最終成果報告会 平成19年3月1日

2 高信頼性・高安全性を有するネットワーク共生環境の 構築技術の創出
メンバー構成 高信頼性・高安全性を有するネットワーク共生環境の 構築技術の創出 増澤利光 情報科学研究科コンピュータサイエンス専攻 教授 井上克郎 菊野 亨 情報科学研究科情報システム工学専攻 教授 藤原 融 情報科学研究科マルチメディア工学専攻 教授

3 テーマ［4］：高信頼性・高安全性を有するネットワーク共生環境の構築技術の創出 安全で安心なサイバー社会
応用・検証 情報家電 社会システムの復旧（支援） 自律性 (Autonomy) 情報の漏洩・不正使用の阻止 強靭性 (Resiliency) 携帯機器 セーフクリティカルシステム 強力な暗号・ 認証手続き オブジェクト指向設計・分析 ディペンダビリティ ソフトウェア工学 個人情報 セキュリティ 暗号・認証技術 セキュリティ工学 信頼性評価 自律的 再構成 ディペンダビリティ工学 分散アルゴリズム・通信プロトコル 分散システム工学

4 井上克郎、楠本真二、神谷年洋、“市村学術賞貢献賞”、(2003年4月).
代表的な論文、受賞 Inoue, K., Yokomori, R., Yamamoto, T., Matsushita, M., and Kusumoto, S., “Ranking Significance of Software Components Based on Use Relations,” IEEE Transactions on Software Engineering, Vol. 31, No. 3, pp. 213–225 (Mar. 2005). Takagi, Y., Mizuno, O., and Kikuno, T., “An Empirical Approach to Characterizing Risky Software Projects Based on Logistic Regression Analysis,” Empirical Software Engineering, Vol. 10, No. 4, pp. 495–515 (Oct. 2005). Izumi, T., and Masuzawa, T., “Condition Adaptation in Synchronous Consensus,” IEEE Transactions on Computers, Vol. 55, No. 7, pp. 843–853 (July 2006). Yasunaga, K., and Fujiwara, T., “Determination of the Local Weight Distribution of Binary Linear Block Codes,” IEEE Transactions on Information Theory, Vol. 52, No. 10, pp. 4444–4454 (Oct. 2006). 井上克郎、楠本真二、神谷年洋、“市村学術賞貢献賞”、(2003年4月). 水野修, 安部誠也, 菊野亨, “SECジャーナル創刊記念論文優秀賞”(2005 年11 月).

5 コードクローン (コード)クローン(Code Clone) ≒ 他に類似したコード片を持つコード片

6 大規模なソースコードからクローンを効率よく検出・分析するシステムが必要
クローンが引き起こす問題 コピー＆ペーストを繰り返すと増加 クローンはソフトウェア保守を困難にする クローンにフォールトが存在する場合、すべてのクローンについて修正を行わなければならない 機能追加も同様 大規模なソースコードからクローンを効率よく検出・分析するシステムが必要 　→　塩基配列の分析法を応用

7 塩基配列の分析 塩基配列 マイコプラズマ

8 同形部分列の高速検出アルゴリズム 塩基配列の同形部分列 分布図

9 大阪大学大学院情報科学研究科松田研究室提供
マイコプラズマの中の同形部分列 大阪大学大学院情報科学研究科松田研究室提供

10 Suffix-treeによるマッチングアルゴリズム
以下の条件を満たす木 (1)木の葉は部分文字列の開始位置 (2)根から葉までラベルをたどると部分文字列になる (3)ひとつの節点から出る辺のラベルはすべて異なる文字で始まる →共通のパス＝クローン

11 1. static void foo() throws RESyntaxException {
例題コード 1. static void foo() throws RESyntaxException { String a[] = new String [] { "123,400", "abc", "orange 100" }; org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); int sum = 0; for (int i = 0; i < a.length; ++i) if (pat.match(a[i])) sum += Sample.parseNumber(pat.getParen(0)); System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { RE exp = new RE("[0-9,]+"); int sum = 0; for (int i = 0; i < a.length; ++i) if (exp.match(a[i])) sum += parseNumber(exp.getParen(0)); System.out.println("sum = " + sum); 17. }

12 ステップ(1)：ソースコードを入力しトークンの列にする

13 ステップ(2)：変形ルールによりトークン列を変形する

14 ステップ(3)：パラメータ置換を行う

15 ステップ(4)：サフィックス木アルゴリズムによりクローンを検出

16 検出結果（右下方向への直線としてクローンが出現）
対角線を中心とした線対称 短いクローンは多数 対角線は常に＊ 長いコードクローン

17 ステップ(5)：元のソースコード上にマップ
1. static void foo() throws RESyntaxException { String a[] = new String [] { "123,400", "abc", "orange 100" }; org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); int sum = 0; for (int i = 0; i < a.length; ++i) if (pat.match(a[i])) sum += Sample.parseNumber(pat.getParen(0)); System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { RE exp = new RE("[0-9,]+"); int sum = 0; for (int i = 0; i < a.length; ++i) if (exp.match(a[i])) sum += parseNumber(exp.getParen(0)); System.out.println("sum = " + sum); 17. }

18 CCFinder/ICCAを150以上の組織に配布
クローン分析の適用 CCFinder/ICCAを150以上の組織に配布 開発したソフトウェアの品質チェック 開発の問題発見 下請け，受け入れチェック コードの改良（リファクタリングツールAries) 著作権侵害の検査 民事裁判（ソースコードの盗用訴訟）の証拠 システムの類似度，進化 Kamiya, T., Kusumoto, S., Inoue, K., “CCFinder: A Multilinguistic Token-Based Code Clone Detection System for Large Scale Source Code”, IEEE Trans. on Software Engineering, Vol. 28, No. 7, (July 2002).

19 FreeBSD, Linux, NetBSDのクローン散布図
Linuxと他の２つのOSの間にはクローンが少ない 　　→　Linuxは独自 　　　　 開発による FreeBSDとNetBSDの間には多数のクローン 　　→　共通の祖先

20 学生Bと学生Eの間に多くのコードクローン
学生の演習結果の分析 学生Bと学生Eの間に多くのコードクローン A B C D E B A B C D E E

21 ソフトウェアの進化の分析に応用 BSD Unixの歴史

22 クローン含有比率を類似度と考え、クラスタ分析

23 CCFinderの適用限界を超えた分析 80台の学生演習用PC-WS上で 問題を小さなタスクに分割 分割された各タスクを分散実行
超大規模分析の試み CCFinderの適用限界を超えた分析 80台の学生演習用PC-WS上で 分割された各タスクを分散実行 問題を小さなタスクに分割

24 対象：UNIX Portsの全ソースプログラム
超大規模コードクローン分析(!) 対象：UNIX Portsの全ソースプログラム （10.8GB, 4億行のCプログラム） Livieri, S., Higo, Y., Matsushita, M., Inoue, K., “Very-Large Scale Code Clone Analysis and Visualization of Open Source Programs Using Distributed CCFinder: D-CCFinder“, International Conference on Software Engineering, Minneapolis, MN. (May 2007, to appear)

25 超大規模コードクローン分析(2) 対象：Linuxのカーネル136バージョン (7.4GB,　2.6億行のCプログラム）

26 大規模なコードクローン分析 ソフトウェアの流用、再利用の関係を大局的に把握 ソフトウェアの利用関係をより系統的に分析
ソフトウェアの利用関係グラフの調査 大規模なコードクローン分析　 　　ソフトウェアの流用、再利用の関係を大局的に把握 ソフトウェアの利用関係をより系統的に分析

27 A B ソフトウェア部品 (部品) ソフトウェア部品グラフ (部品グラフ) ソフトウェア部品グラフ ソフトウェアの構成単位
クラス，関数，… 互いに利用関係が存在 変数宣言，呼び出し，… ソフトウェア部品グラフ (部品グラフ) ソフトウェア部品を頂点・利用関係を 有向辺としたグラフ ソフトウェアの静的な構造を反映 class A { public void exec () { … } class B { … A.exec(); } A B 背景としてソフトウェア部品グラフについて。 まずソフトウェア部品とは，クラスや関数といったソフトウェアの構成単位のことを指す． 部品間には，変数宣言や，呼び出しなどの利用関係が存在する 例えばJavaのクラスを部品とすると，これらのクラスA,Bはそれぞれ部品になる． 　クラスAにはexec()というメソッドがあり，Bには，そのメソッドに対する呼び出しが存在する． 　このとき，BからAへの利用関係が存在する． ソフトウェア部品グラフは，ソフトウェア部品を頂点，利用関係を有効辺としたグラフのことを言う． 先ほどの部品と利用関係は，このような2頂点からなるグラフとして表される． 実際にはソフトウェア全体などでグラフを構成する． ソフトウェアの静的な構造を反映していて， ソフトウェア工学の様々な手法に用いられる． 本研究では，ソフトウェアをソフトウェア部品グラフとして表し， その特徴から，ソフトウェアの性質を得ることを目標とする． ソフトウェア部品の利用特性？ ソフトウェア部品グラフ ソフトウェア群

28 ソフトウェア部品グラフの例 あるC++のライブラリの部品グラフ

29 ソフトウェア部品グラフの調査 酵母内のタンパク質相互関連 各タンパク質の関連次数の分布 ？ C++の部品の利用関係

30 対象：Javaソフトウェアに基づく部品グラフ
準備: 部品グラフと部品集合 対象：Javaソフトウェアに基づく部品グラフ 部品（頂点）：Javaのクラス 利用関係（辺）: Javaクラス間の静的な利用関係 継承,実装,変数宣言,生成,フィールド参照,メソッド呼び出し 概要 クラス数 JDK Java 基本ライブラリ JDK1.4 約11,000 ECLIPSE Java統合開発環境 Eclipse 3.0.1 約14,000 NETBEANS Java統合開発環境 NetBeans 3.6 約13,000 APACHE Apache Projectから収集したソフトウェア集合 約59,000 ALL 上記の全て 約180,000 部品集合 詳細な利用関係に基づく部品グラフ・複数のソフトウェア集合に基づく部品グラフの次数分布は，べき乗則に従うか？ 入力次数・出力次数を調査

31 ALLの入力次数上位の部品 メトリクスとの相関 JDKなど，基礎的な役割をもつ部品 String,Objectは特に大きな値
調査1：入力次数 ALLの入力次数上位の部品 JDKなど，基礎的な役割をもつ部品 String,Objectは特に大きな値 クラス名 行数 出力次数 入力次数 1 java.lang.String 675 21 116,326 2 java.lang.Object 35 4 98,377 3 java.lang.Class 605 41 29,767 java.lang.Exception 15 21,057 5 java.lang.Throwable 136 12 19,536 メトリクスとの相関 行数、複雑度とは相関なし メソド数とやや相関 出力次数 行数 複雑度 メソッド数 入力次数 0.00 0.07 0.08 0.24

32 JDK ALL べき乗則に従う 調査1: 入力次数の分布 a R*2 JDK ALL 2.1 ±8.6×10-3 0.99
・グラフ，表の見方 ・きれいに直線上にならんでいる ・寄与率も高い →べき乗則に従う． ・べきの乗数であるaの値は，他の分野で観測されることの多い 2 に近い値. 　例えばWWW上のページのリンク数もこの辺． ・最大値はJDKは約6400だが，対してALLは約11万 →部品数の違いを考慮しても，大きな差が出ている a R*2 JDK 2.1 ±8.6×10-3 0.99 ALL 2.0 ±1.4×10-3 1.00 べき乗則に従う

33 ALLの出力次数上位の部品 メトリクスとの相関 調査2: 出力次数 単純に大きな部品 行数や複雑度・メソッド数と高い相関 クラス名 行数
入力次数 1 org.apache.poi… …FunctionEval 364 354 2 org.jgraph.GPGraphpad 2,196 255 130 3 com.jgraph.GPGraphpad 2,200 253 131 4 542 252 209 5 org.eclipse.jdt… …ASTConverter 4,520 223 ALLの出力次数上位の部品 単純に大きな部品 メトリクスとの相関 行数や複雑度・メソッド数と高い相関 入力次数 行数 複雑度 メソッド数 出力次数 0.00 0.83 0.75 0.64 ・出力次数に関して，部品との関連をみていくことで， 　べき乗則に従わなかった要因を調べる． ・表(上)の説明 ・単純に規模の大きな部品が並んでいる ・表(下)の説明 　・出力次数と，入力次数，行数，複雑度，メソッド数と相関を取った結果 　・．．． →出力次数は，他の部品の存在にあまり影響されず， 　部品の規模や複雑さと関係するため 　・部品に記述された内容に基づいている 　・極端に大きな部品＝規模が大きく複雑な部品は非現実的で，あまり存在せず， 　　存在してもたかだか200～300程度ということ．

34 JDK ALL べき乗則には従わない 値の小さな部分は曲線 調査2: 出力次数の分布 a R*2 JDK ALL 3.1 ±8.2×10-2
・図，表の見方． ・値の大きな範囲では入力と同様に直線だが， 　値の小さな範囲で曲線になっている →べき分布では無い <s>・参考程度に直線に回帰してみると，かなり大きな傾き． 　極端な値が出にくい．</s> ・最大値はJDKが140でALLは350で，あまり大きな違いは無い a R*2 JDK 3.1 ±8.2×10-2 0.88 ALL 3.7 ±6.9×10-2 0.90 べき乗則には従わない 値の小さな部分は曲線

35 この結果を利用して、有用な部品を効率よく検索できる方法は？
調査のまとめ 入力次数 べき乗則に従う 高い度合い 部品の役割に関連し，基礎的な役割の部品が大きな次数をもつ 多くにとって有用な部品は多数の部品から利用される 出力次数 べき乗則には従わない 値の小さな部分が異なる 部品の規模や複雑さと関連し，極端に大きな部品はあまり存在しない 大きくなりすぎると使いづらい ・入力次数 　・高い度合いでべき乗則に従い，部品集合により値域に大きな差 　・これは，部品の役割に関連し，基礎的な部品は大きな次数をもつため． ・出力次数 　・べき乗則に従わず，部品集合がかわっても値域はあまり変わらない 　・これは，出力次数が部品そのものの規模や複雑さに関係し，極端に大きな部品は存在しないため， この結果を利用して、有用な部品を効率よく検索できる方法は？

36 重要な部品 ≒ 入力次数の大きいもの 問題点 コンポーネントランクCR法 入力次数が低いものが多数あり、分解能悪い
部品グラフの特性を利用した部品検索法 重要な部品　　≒　　入力次数の大きいもの 問題点 入力次数が低いものが多数あり、分解能悪い 入力次数が高いものの近傍の部品は、重要にしたい コンポーネントランクCR法 他分野のランク付け参考 Influence Weight (学術論文誌の重要度評価） PageRank (GoogleにおけるＷｅｂページの評価） 重要な部品 多数の部品から参照されている 重要な部品から参照されている 部品グラフの隣接行列の固有ベクトルの要素　＝　重要度

37 SPARS-J Software Product Archive, analysis Retrieval System for Java Javaソフトウェア部品検索システム 大量のJavaのソースコードから部品を切り出す 部品を解析し，自動的に情報を抽出 検索要求と検索結果 SPARS-Jのアーキテクチャ

38 SPARS-Jの実行画面

39 SPARS-Jを用いることでソフトウェア検索の能力が飛躍的に向上し、ソフトウェア開発や保守が効率化
実用的なソフトウェア検索システムとして世界に先駆けて公開 “Ranking Significance of Software Components Based on Use Relations,” IEEE Transactions on Software Engineering, Vol. 31, No. 3, pp. 213–225 (Mar. 2005) Google Code Searchより先行し、優れたコード分析能力 ソフトウェアの再利用に有効 再利用によりソフトウェアの生産性は47％向上 Boehm, B., “Managing Software Productivity and Reuse”, IEEE Computer, Vol.32, No. 9, pp (Sep. 1999). 今までソフトウェア再利用のための自動リポジトリ構築システムはなかった SPARS-Jが世界に先駆けて実用化 サントリー㈱の社内ソフトウェア資産管理にSPARS-Jを適用し、有効性の確認 SPARS-Jを用いることでソフトウェア検索の能力が飛躍的に向上し、ソフトウェア開発や保守が効率化

40 塩基配列の分析技術を応用したソフトウェア分析技術 コードクローン分析
生物に学ぶソフトウェア工学技術 塩基配列の分析技術を応用したソフトウェア分析技術 コードクローン分析 ネットワークの性質：Power Law 生物界ネットワーク 計算機ネットワーク ソフトウェア利用関係ネットワーク ソフトウェアの再利用支援技術 検索性能の向上　→　ソフトウェア開発や保守の効率向上