制御フローを考慮しない データ依存関係解析の実験的評価

Slides:



Advertisements
Similar presentations
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 保守支援を目的とした コードクローン情報検索ツール.
Advertisements

シーケンス図の生成のための実行履歴圧縮手法
XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム
Javaプログラムの開発履歴における アクセス修飾子過剰性の分析
情報伝播によるオブジェクト指向プログラム理解支援の提案
アクセス修飾子過剰性の変遷に着目したJavaプログラム部品の分析
データフロー情報を用いたコード ナビゲーションツールの実装と評価
変数間データフローグラフを用いた ソースコード間の移動支援
F11: Analysis III (このセッションは論文2本です)
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
メソッド名とその周辺の識別子の 相関ルールに基づくメソッド名変更支援手法
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
プログラム静的解析手法の効率化と 解析フレームワークの構築に関する研究
プログラム実行履歴を用いたトランザクションファンクション抽出手法
静的情報と動的情報を用いた プログラムスライス計算法
細かい粒度でコードの再利用を可能とするメソッド内メソッドのJava言語への導入
コードクローンに含まれるメソッド呼び出しの 変更度合の分析
コードクローンに含まれるメソッド呼び出しの 変更度合の調査
細かい粒度で コードの再利用を可能とする メソッド内メソッドと その効率の良い実装方法の提案
オブジェクト指向 プログラミング 第十三回 知能情報学部 新田直也.
動的スライスを用いた バグ修正前後の実行系列の比較
暗黙的に型付けされる構造体の Java言語への導入
動的依存グラフの3-gramを用いた 実行トレースの比較手法
ポインタ解析におけるライブラリの スタブコードへの置換の効果
オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現
オブジェクト指向プログラムにおける エイリアス解析について
インラインスクリプトに対するデータフロー 解析を用いた XHTML 文書の構文検証
動的スライスを用いたバグ修正前後の実行系列の差分検出手法
利用関係に基づく類似度を用いたJavaコンポーネント分類ツールの作成
Javaプログラムの変更を支援する 影響波及解析システム
リファクタリング支援のための コードクローンに含まれる識別子の対応関係分析
動的データ依存関係解析を用いた Javaプログラムスライス手法
ソースコードの特徴量を用いた機械学習による メソッド抽出リファクタリング推薦手法
コードクローンの動作を比較するためのコードクローン周辺コードの解析
Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
コードクローン検出に基づくデザイン パターン適用支援手法の提案と実現
プログラム理解におけるThin sliceの 統計的調査による有用性評価
バイトコードを単位とするJavaスライスシステムの試作
○ 後藤 祥1,吉田 則裕2 ,井岡 正和1 ,井上 克郎1 1大阪大学 2奈良先端科学技術大学院大学
ソフトウェア保守のための コードクローン情報検索ツール
コードクローンの理解支援を目的としたコードクローン周辺コードの解析
コードクローン分類の詳細化に基づく 集約パターンの提案と評価
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
Javaバーチャルマシンを利用した 動的依存関係解析手法の提案
コーディングパターンの あいまい検索の提案と実装
JAVAバイトコードにおける データ依存解析手法の提案と実装
インスタンスの型を考慮したJavaプログラムの実行経路の列挙手法の提案
JavaScriptを含んだHTML文書に対する データフロー解析を用いた構文検証手法の提案
アルゴリズムとプログラミング (Algorithms and Programming)
静的情報と動的情報を用いた Javaプログラムスライス計算法
プログラムスライスを用いた凝集度メトリクスに基づく 類似メソッド集約候補の順位付け手法
保守請負時を対象とした 労力見積のためのメトリクスの提案
オープンソースソフトウェアに対する コーディングパターン分析の適用
アスペクト指向プログラミングの 動的プログラムスライスへの応用
状況に応じて適切な 例外処理が行なえる アスペクト指向分散環境実験の 支援ツール
統合開発環境のための プログラミング言語拡張 フレームワーク
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
プログラムの一時停止時に 将来の実行情報を提供するデバッガ
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
動的スライスを用いたバグ修正前後の実行系列の差分検出手法の提案
ソフトウェア工学 知能情報学部 新田直也.
コードクローン解析に基づく デザインパターン適用候補の検出手法
回帰テストにおける実行系列の差分の効率的な検出手法
Javaとは Javaとはオブジェクト指向言語でJava VM(Java仮想マシン)と呼ばれるプログラム上で動作します。
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラム依存グラフを用いた ソースコードのパターン違反検出法
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
計算機プログラミングI 第2回 2002年10月17日(木) 履習登録 複習 ライブラリの利用 (2.6-7) 式・値・代入 (2.6-8)
Presentation transcript:

制御フローを考慮しない データ依存関係解析の実験的評価 石尾 隆    井上 克郎 Osaka University

研究の概要 データ依存関係解析 単純化した解析の効果を評価 役立つと言われつつも,実際にはあまり活用されていない 実装,計算には時間がかかる 実用的なツールといえばコンパイラ,一部静的解析ツールぐらい? 単純化した解析の効果を評価 すべての代入がすべての参照に影響を与えるとみなした 90.9%のJavaのメソッドで,正しい結果が得られる 速度重視で,正確さがそれほど必要なければ,十分役立つ可能性がある

研究の背景 データ依存関係解析は様々な解析技術の基盤 解析の実装,実行のコスト プログラムスライシング 影響波及解析 コードクローン検出 構文解析,シンボルテーブルの作成 制御フロー解析 データ依存関係解析

依存関係解析のコスト Soot フレームワークを使ってスライシングツールを実装した場合 [2006年頃の話] 日々のタスクに使うには長い JEdit 4.2 (140KLOC) を解析するのに20分 ポインタ解析など,プログラム全体解析のコストが高い 実用的になるには,近似計算等が必要 日々のタスクに使うには長い 開発者の1タスクは30分~2時間程度 [Parnin, 2011]

関連研究: 解析の簡略化 大規模解析に向けた様々な簡略化手法 データ依存関係の制御フローでの近似 [Jasz, 2008] 制御フローで到達可能 = 依存関係あり 同一のデータを順番に加工していく処理に強い メッセージループを使ったプログラムに弱い メソッド呼出し系列マイニング用の表現 [Nguyen, 2009] 同じ変数を使っていて,構文的に並んでいるところに依存関係があるとみなす

単純化したデータ依存関係解析 制御フローを考慮しない解析 [柳, 2010] 速度向上: 2分でJEdit (140KLOC)を解析 Control-flow insensitive, Object insensitive Javaを対象 速度向上: 2分でJEdit (140KLOC)を解析 正確さの犠牲: 余計な(実際には起こらない) データ依存関係を出力する プログラム理解には悪影響はなかった [悦田, 2011] 定量的な評価は未実施だった

本研究の概要 目的: データ依存関係解析2手法の比較 方法 制御フローグラフを使った従来の解析 制御フロー解析なしの近似計算 従来手法を正解とみなしたとき,近似計算では不正解となる変数,メソッドの割合を計算 手続き内の依存関係のみ 対象はローカル変数のみ 10個の Java プログラムを対象に実験

従来のデータ依存関係解析 データ依存関係 s → t の定義 文 s が変数 v に値を代入する. 文 t が変数 v の値を参照する. 文 s から文 t まで,変数 v の値を書き変えない実行経路が少なくとも1つ存在する. v public File getFile() { 1: String f = getFileName(); 2: if (f == null) { 3: f = getDefaultFile(); 4: } 5: File file = new File(f); 6: return file; }

制御フローを考慮しない データ依存関係解析 データ依存関係 s → t の定義 文 s が変数 v に値を代入する. 文 t が変数 v の値を参照する. 文 s から文 t まで,変数 v の値を書き変えない実行経路が少なくとも1つ存在する. v public File getFile() { 1: String f = getFileName(); 2: if (f == null) { 3: f = getDefaultFile(); 4: } 5: File file = new File(f); 6: return file; } 全代入から全参照へ辺を引く この方法で追加で出てくるデータ依存関係は 不適切なパス(infeasible path)である

「正解」の判定方法 Split Incorrect Correct 1つの変数について,従来の解析で得られるデータ依存関係から求める 代入 参照 代入 参照 代入 参照 元々,全代入から全参照に 到達可能な変数. 制御フロー解析なしでも 不適切なパスは発生しない 開発者が変数の名前を 付け替えれば,2つ以上の Correct 変数にできる. Correct, Split 以外の すべての変数. int x = getX(); use(x); x = anotherX;

結果の集計 ローカル変数について Correct / Split / Incorrect の個数をカウント メソッド単位で分類結果を集計 Correct: メソッド内のすべての変数が Correct Split: 1つ以上の変数が Split, 他はCorrect Incorrect: 1つ以上の変数が Incorrect

集計の実装 (1/2) Java バイトコード解析を採用 例外発生を仮定した制御フローグラフ メソッド単位で構築 try ブロックの中では全命令が任意の例外を投げてcatch, finally に移動しうると仮定

集計の実装 (2/2) ローカル変数に関する仮定 メソッドの引数はメソッド先頭で代入されると解釈 “this” は変数とみなさない デバッグ用ローカル変数情報を使用 同一記憶域が2つ以上の変数に対応する場合を認識

対象プログラム バイナリ配布パッケージを解析 パッケージ同梱の ライブラリのコード, サンプルコード含む 重複クラスは排除  ライブラリのコード,  サンプルコード含む 重複クラスは排除 クラスファイル単位,   MD5ハッシュ比較 Program #Class #Methods #Variables ANTLR 3.3 1,063 10,930 26,129 Apache Ant 1.8.2 1,177 11,033 20,282 Apache Tomcat 7.0.8 2,368 25,632 60,422 Batik 1.7 5,877 46,326 100,485 Eclipse SDK 3.6.2 33,270 258,073 610,099 JDK 1.6.0 15,951 134,497 308,239 JEdit 4.3.2 1,045 7,521 18,417 和歌山大学教務システム 3,788 36,484 70,842 Torque 3.3 2,106 21,468 40,340 Vuze 4.6.0.2 6,739 41,822 101,912 合計(※) 72,575 584,353 1,339,110 ※プログラム間で重複したクラスを除く

変数単位の分類結果 Total (3.9%) (3.4%) Program #Correct #Split #Incorrect ANTLR 3.3 22,754 (87.1%) 2,275 (8.7%) 1,100 (4.2%) Apache Ant 1.8.2 18,976 (93.6%) 529 (2.6%) 777 (3.8%) Apache Tomcat 7.0.8 56,136 (92.9%) 1,760 (2.9%) 2,526 (4.2%) Batik 1.7 90,415 (90.0%) 5,298 (5.3%) 4,772 (4.7%) Eclipse SDK 3.6.2 577,535 (94.7%) 13,667 (2.2%) 18,897 (3.1%) JDK 1.6.0 273,458 (88.7%) 22,971 (7.5%) 11,810 (3.8%) JEdit 4.3.2 17,383 (94.4%) 379 (2.1%) 655 (3.6%) 和歌山大学教務システム 66,048 (93.2%) 2,474 (3.5%) 2,320 (3.3%) Torque 3.3 37,238 (92.3%) 1,782 (4.4%) 1,320 (3.3%) Vuze 4.6.0.2 97,566 (95.7%) 1,817 (1.8%) 2,529 (2.5%) Total 1,240,879 (92.7%) 52,279 (3.9%) 45,952 (3.4%)

メソッド単位の分類結果 Total (90.9%) Program #Correct #Split #Incorrect ANTLR 3.3 9,480 (86.7%) 482 (4.4%) 968 (8.9%) Apache Ant 1.8.2 10,218 (92.6%) 262 (2.4%) 553 (5.0%) Apache Tomcat 7.0.8 23,163 (90.4%) 722 (2.8%) 1,747 (6.8%) Batik 1.7 41,641 (89.9%) 1,752 (3.8%) 2,933 (6.3%) Eclipse SDK 3.6.2 237,420 (92.0%) 7,064 (2.7%) 13,589 (5.3%) JDK 1.6.0 130,518 (88.2%) 9,373 (6.3%) 8,071 (5.5%) JEdit 4.3.2 6,817 (90.6%) 219 (2.9%) 485 (6.4%) 和歌山大学教務システム 33,620 (92.1%) 1,018 (2.8%) 1,846 (5.1%) Torque 3.3 19,690 (91.7%) 819 (3.8%) 959 (4.5%) Vuze 4.6.0.2 39,260 (93.9%) 876 (2.1%) 1,686 (4.0%) Total 543,260 (90.9%) 22,324 (3.7%) 32,234 (5.4%)

結果 最悪時 86.7%,平均 90.9% のメソッドで 正しいデータ依存関係を取得できた なぜ有効に働くのか? 最悪時 86.7%,平均 90.9% のメソッドで  正しいデータ依存関係を取得できた 開発者が変数の名前を適切に変更してくれれば,94.6% のメソッドで正しい結果を取得可能 なぜ有効に働くのか?  84.2%のメソッドは,各変数に高々1回しか値を 代入していなかった 「1変数は1つの用途に」という経験則 Java は1メソッドが短く,新しい変数をすぐ宣言できる

手続き内での配列・フィールドの影響 今回の解析では無視したけれども… 1メソッドの中で,1つのフィールドや配列に 値を書き,かつ値を読むものは少ない フィールドを読み書きするメソッド: 36,732 個(6.1%) 配列を読み書きするメソッド:   9,290 個(1.6%)  手続き内のデータ依存関係への影響は   元々少ない

手続き間解析への影響 手続き間のデータ依存関係は2種類 メソッド呼び出しに関するデータ依存関係 フィールド,配列に関するデータ依存関係 動的束縛の解決に依存 よく使われる手法(CHA, RTA, VTA)は制御フロー情報を使っていないので,競合しない フィールド,配列に関するデータ依存関係 ポインタ解析に依存 flow-insensitive な解析方法は存在する Object-insensitive に解決する方法もある

結果の使い道 正確な結果にこだわりたい人は: 各変数に高々1回しか値を代入しない 84.2% の メソッドに対して,制御フローグラフの構築を省略 正確な結果が不要な人は: 変数の一致だけで簡易データフロー解析をして, 実行時性能を大幅に向上できる Eclipse 上で変数をクリックして変数をハイライト表示  → 代入位置を辿る,というデータフローの追跡方法は,   9割のメソッドでは完全に正しい

成功の条件: 開発者が良いコードを書いてること 開発者が変なコードを書くと解析結果も悪くなる 解析しやすいコードを書く  開発環境からサポートを得られる … という状況でインセンティブが働くと期待 プログラミング言語の良さの影響 Java にはポインタ,参照変数がない ローカル変数に対するエイリアスを警戒しなくてよい C言語などでは異なる結果となる可能性がある C言語でも,1関数内で変数に別名をつける人は少ないはず

まとめ 制御フロー情報なしの簡易データ依存解析も, 58万メソッドのうち 90.9% では正確な結果を出した 今後の課題 制御フロー情報なしの簡易データ依存解析も,   58万メソッドのうち 90.9% では正確な結果を出した 開発者の努力で 94.6% までは上昇する見込みあり 残り 9.1% がどれくらいひどい結果になるかは未評価 今後の課題 不適切な辺の有無だけでなく,推移性の変化の評価 プログラムスライシングなどの応用手法への影響評価 C言語など異なる言語での実験

解析の実行時間 [柳, 2010] プログラム サイズ (LOC) AST構築,シンボルテーブル構築時間 (sec.) データフロー解析時間 (sec.) 解析 合計時間(sec.) ANTLR 3.0.1 71,845 39 11 50 JEdit 4.3pre11 168,872 108 17 125 Apache Batik 1.6 297,320 155 33 188 Apache Cocoon 2.1.11 505,715 490 71 561 Azureus 3.0.3.4 552,295 353 115 468 Jboss 4.2.3GA 696,761 703 348 1,051 JDK 1.5 885,887 1,054 1,001 2,055 on Windows Vista SP2, Intel® Core2 Duo 1.80 GHz, 2GB RAM