ポインタ解析におけるライブラリの スタブコードへの置換の効果 井上研究室 B4 山本 佑也

ポインタ解析とは 変数の値やオブジェクトの流れを解析するデータフロー解析の一種 変数にどこで生成されたオブジェクトが代入されるのかを解析する a = new Hoge(); b = new Fuga(); c = a; if (…) d = b; else d = c; e = d; new Hoge() a この後内部辺・外部辺の定義？ b c d e new Fuga()

内部辺・外部辺 内部辺 外部辺 グラフ上で変数からオブジェクトを指す有向辺 解析が出来ないメソッドの戻り値などの正体の分からない”外部オブジェクト”を指す有向辺 外部辺の数が少ないほどデータフローについて正確な情報が得られている 関係するメソッドを調査するとスタブコードの有用性や必要箇所が分かる

内部辺・外部辺の例 ？ ？ 内部辺 外部オブジェクト 変数 オブジェクト new Hoge() a a = new Hoge(); b = new Fuga(); c = a; if (…) d = b; else d = c; e = d; a.set(b); f = a.get(); b c 解析が出来ない部分の ポインタグラフは作成されない d e new Fuga() ？ ？ f Hoge#getの戻り値 追加された二行のコードでは，Hogeのset,getメソッドが呼び出されています． これらのメソッドはsetの引数がgetの戻り値として返るという挙動をしますが，もしHogeクラスのソースコードが解析対象に含まれない場合はそれが分かりません． その場合はfに何が代入されるのか特定できず，bと同じFugaのオブジェクトを指すことが出来ません． なので，代わりに"Hoge#getの戻り値"を1つの外部オブジェクトと考え，それに対して辺を引きます．これが外部辺です． 外部オブジェクト 外部辺

研究背景 ポインタ解析において、ライブラリの中身は解析が困難な場合が多い ライブラリを解析対象外にすると外部辺が増えて解析の精度が犠牲になる 計算コストが大きい (Javaのクラスライブラリなど) ネイティブメソッドのソースコードが入手できない ライブラリを解析対象外にすると外部辺が増えて解析の精度が犠牲になる 解析対象外とは？

既存研究における外部ライブラリの扱い Arztら[1]によると3つのパターンがある 本研究では3つ目の手法で扱うサマリーの表現方法を提案する 外部ライブラリをそのまま解析に含める データフローの規則を定義し，その規則で外部ライブラリを扱う 外部ライブラリの解析に必要な情報をサマリー（要約）としてまとめ，それを解析で利用する 本研究では3つ目の手法で扱うサマリーの表現方法を提案する [1] Steven Arzt and Eric Bodden. Stubdroid: Automatic inference of precise data-flow summaries for the android framework. ICSE '16

提案手法：スタブコード表現 オリジナルのコードから，外部から見たデータフローのみを表現するスタブコードを作成し代わりに解析する 作成するスタブコード public class ArrayList<E>{ 　　public E content; 　　public boolean add(E e){ 　　　　content = e; 　　　　return true; 　　} 　　public E get(int a){ 　　 return content; } add()の引数とget()の戻り値に依存関係があることは分かる

スタブコードの作成方法 publicなフィールドを実装する publicなメソッドの外部と関係するデータフローのみを表現する形で実装する publicなフィールドへの代入や，return文など 内部実装はオリジナルに忠実である必要はない

スタブコードの利点 オリジナルのコードより解析が軽い 元々の解析に手を加える箇所が少なくて済む 内部のメソッド呼び出しが少ない ポインタ解析でメソッド呼び出しを処理するのは高コスト 元々の解析に手を加える箇所が少なくて済む 解析対象のコードに混ぜて一緒に解析してしまえる

評価実験 Andersenのポインタ解析のJava実装 6種類のインターフェースのスタブコードを用意 Collection, List, Set, Map, Queue, Deque 対象は6つの比較的小規模な Java プロジェクト ANTLR, DrawSWF, Jasml, JavaCC, JMoney, JUnit スタブコードの適用の有無で以下のデータを比較 内部辺・外部辺数 解析時間 インターフェースの外部辺 インターフェースの使い方

対象としたインターフェース Collectionインターフェースのサブインターフェースをメインに選出 Collection, List, Set, Map, Queue, Deque オブジェクトの管理をするインターフェース 拡張for文で頻繁に使われる for(String str : list){ … } 対応 for (Iterator iterator = list.iterator(); iterator.hasNext();) { String str = iterator.next(); … }

外部辺に関係するメソッド 対象インターフェースの関係する外部辺が大半 2プロジェクトについての外部辺に関係するメソッドの上位3つ ANTLR JavaCC メソッド名 外部辺数 java.util.List#iterator 540,874 17,319 java.util.Collection #iterator 184,710 java.util.List#get 9,912 127,529 java.util.Map#keySet 1,663 上位3メソッド合計 853,113 28,894 総外部辺数 985,676 29,748 (注)メソッド名の欄には　"クラス名#メソッド名"の形式で表記している 対象インターフェースの関係する外部辺が大半

評価実験の結果 スタブコード適用の有無ごとの解析結果比較 外部辺数 内部辺数 解析時間(ms) スタブ有無 なし あり ANTLR 985,676 225,782 919,744 1,259,490 5,461,238 6,363,944 DrawSWF 7,490 5,011 32,801 40,589 2,577 4,668 Jasml 108 38 1,528 1,706 1,702 1,812 JavaCC 29,749 6,123 27,688 36,603 4,107 12,693 JMoney 563 465 4,568 4,581 719 844 JUnit 14,491 5,269 10,909 16,158 3,857 8,105

スタブコード適用後の 外部辺に関係するメソッド 2プロジェクトについての外部辺に関係するメソッドの上位3つ ANTLR JavaCC メソッド名 外部辺数 java.util.Stack#peek 70,100 java.util.Enumeration #nextElement 4,078 java.util.Arrays#asList 54,433 java.util.Vector#elementAt 2,016 java.util.Arrays#copyOf 23,365 java.util.Hashtable#keys 13 上位3メソッド合計 147,899 6,107 総外部辺数 225,787 6,129 スタブ適用前は？ (注)メソッド名の欄には　"クラス名#メソッド名"の形式で表記している

考察(1/2) 提案手法により解析の精度は向上 解析時間は2~3倍 スタブコードとして実装したインターフェースはわずか6つながら大きな効果 許容範囲 ライブラリ丸ごと解析する場合より明らかに低コスト Javaのクラスライブラリを含めた場合数週間かかると思われる

考察(2/2) 外部辺に関係するメソッドにはオブジェクトを管理するクラスのものが未だに多い Stack,VectorはCollectionインターフェースを持つクラス Arraysは配列操作用のメソッドを提供するユーティリティクラス オブジェクトを管理するクラスのスタブコードのみを実装すればほとんどの外部辺は消える可能性がある

まとめと今後の課題 ポインタ解析におけるサマリーの表現方法としてスタブコードを提案 他のデータフロー解析に適用出来るか 実験の結果少数のスタブコードで大幅な精度向上が期待できると判明 他のデータフロー解析に適用出来るか より情報量の多いスタブコードが必要 多様な外部ライブラリの調査 Javaクラスライブラリはどんなソフトウェアでも使う汎用的な機能を実装 各目的に特化したライブラリでは別の傾向が出る可能性