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

Presentation on theme: "制御フローを考慮しない データ依存関係解析の実験的評価"— Presentation transcript:

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

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

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

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

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

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

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

8 従来のデータ依存関係解析 データ依存関係 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; }

9 制御フローを考慮しない データ依存関係解析
データ依存関係 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）である

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

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

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

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

14 対象プログラム バイナリ配布パッケージを解析 パッケージ同梱の ライブラリのコード, サンプルコード含む 重複クラスは排除
　ライブラリのコード, 　サンプルコード含む 重複クラスは排除 クラスファイル単位， 　 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 6,739 41,822 101,912 合計(※) 72,575 584,353 1,339,110 ※プログラム間で重複したクラスを除く

15 変数単位の分類結果 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 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%)

16 メソッド単位の分類結果 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 39,260 (93.9%) 876 (2.1%) 1,686 (4.0%) Total 543,260 (90.9%) 22,324 (3.7%) 32,234 (5.4%)

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

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

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

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

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

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

23

24 解析の実行時間 [柳, 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 505,715 490 71 561 Azureus 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