F11: Analysis III (このセッションは論文２本です) 石尾 隆，鹿島 悠 大阪大学

Inferring Data Polymorphism in Systems Code 大阪大学 情報科学研究科 井上研究室 石尾 隆

論文の概要 “Data Polymorphism” を解析する手法を提案 Linux カーネルを対象に構築，実験 ポインタのダウンキャストの安全性をチェックする手法 技術的にはポインタ／エイリアス解析の一種 Linux カーネルを対象に構築，実験 カーネルのコードの書き方を想定した手法 C言語だけを対象にした手法 4.4MLOC のコードから，28,767か所のダウンキャストのうち75％の安全を確認

Data Polymorphism 一般的な型の変数（long や void*）として，特定のデータ型のポインタを扱うこと 渡された関数ポインタと データの利用側 void __run_timers(…) { … timer = … fn = timer-> function; data = timer-> data; fn(data); } 2章 EXAMPLE の簡易版： buffer_timeout 関数を呼び出してもらうように登録する． void init(…) { … mydata.timeout.function = buffer_timeout; mydata.timeout.data = (unsigned long)(&mydata); } /* 引数 を，必要なデータ型にダウンキャストして利用 */ void buffer_timeout(unsigned long data) { struct my_datatype *my_data = (my_datatype*)data;

解析の目的 データ型へのダウンキャストが安全かどうかを静的に知りたい 関連研究には，C言語自体の型安全性・メモリ安全性の向上や，動的な型検査が挙げられている /* 引数 を，必要なデータ型にダウンキャストして利用 */ void buffer_timeout(unsigned long data) { struct my_datatype *my_data = (my_datatype*)data; … }  このキャストは安全か？

解析の手法 構造体に，関数ポインタと引数が組で設定されることが多い mydata.timeout.function = buffer_timeout; mydata.timeout.data = (unsigned long)(&mydata); 上記のような同時に代入されるデータの組 (Structural Relationship) を検出 型 my_datatype， “.function” と “.data” を組として記録 抽出された組が使われる場所に実際に到達するデータの組 (Structural Correlation) をすべて取り出す 「.function = buffer_timeout 関数，.data = init 関数の mydata という変数」という組を抽出 引数(.data)の型とダウンキャストの型が一致すればよい

解析の特徴 構造体メンバーに対するエイリアス解析 (5章) うまく解析できない場所は，手動の annotation で対応(6章) Global Points-to Graph を作らず，メモリ使用量を抑制する そのかわり，手続き間のデータフローを毎回探索 Linux カーネル解析に 50コアのクラスタで 3時間40分 CPU時間の合計は 130時間 Linux カーネルのサイズに対応できる，ヒープ構造を考慮した解析であることに新規性がある ただし，調べる対象を void* などに限っている うまく解析できない場所は，手動の annotation で対応(6章) アノテーションは２種類： 既知の Structural Relationship/Correlation を手動で割り当てる 特定の関係を調査対象から除外するもの

実験結果 Linux 2.6.17.1, 4.4MLOC Data Polymorphism と思われる呼び出しは7,850か所 11,976 箇所に，関数ポインタを使った呼び出し うち 7,850 箇所 (66%) で，引数が void* 型か，void* 型のフィールドを含む構造体となっていた ダウンキャストは28,767か所，うち75％の安全を確認 177か所のアノテーションが必要だった アノテーションなしでどこまで正確だったのかは不明 アノテーションが解析に必要だと判断する方法は与えられていない

大阪大学 情報科学研究科 井上研究室 M2 鹿島悠 Boosting the Performance of Flow-sensitive Points-to Analysis using Value Flow 大阪大学 情報科学研究科 井上研究室 M2 鹿島悠

高速なFlow-senstiveポインタ解析の提案 Value Flow Graph : ポインタ・メモリーオブジェクトのフローを表現 SSA形式に 変換された ソースコード ポインタ 変数・store load命令 alloc_B alloc_A A = alloc_A B = alloc_B t1 = alloc_a t2 = alloc_b store t1, A store t2, B … Direct Edge B 代入によるフロー を表す A store t2, B store t1, A Indirect Edge a1 = load t1 s2 = load q ポインタを介して のフローを表す s1 = load p store p, s2 store q,s1 a3 = load t1 a2 = load t1 あるポインタが代入される変数 = ポインタノードから到達可能な変数

SSAからVFGへの変換 (1/2) VFGにDirect Edgeを引くルール VFGにIndirect Edgeを引くルール a = alloc_o alloc_o → a a = b a → b SSAの命令 VFGの操作 store x, b … a = load y x,yが同じポインタを指していてかつ，store命令が他のstore命令でkillされていなければ， b ⇢ a store x, b1 1: x = alloc_o 2: y = x 3: store x, b1 4: store x, b2 5: a = load y store x, b2 a3 = load t1 4のstore命令により， 3のstore命令はkillされる

SSAからVFGへの変換 (2/2) store命令のkillの求め方 メソッド呼び出しの扱い strong update を用いる store (X, …)があり， Xがalloc_oのみを指すとき，このstore命令以前に存在する，alloc_oに対するstore命令を全てkillする 正確性を持たせつつ，不必要な計算を省くため，ポインタにEscape Orderを定め，その順にstrong updateを行う store X, Y ( X ← alloc_A, Y ← alloc_B ) のとき， alloc_A < alloc_B とする メソッド呼び出しの扱い 予備変数を導入し，参照を渡している場合でも，値渡しのように扱う

実験 実験設計 実験結果 (Timeは 分:秒) 本手法(VF-PA)と，Flow-Insensitiveなポインタ解析(IPA)，既存のFlow-Sensitiveなポインタ解析(SS-PA)を比較 実験結果 (Timeは 分:秒) IPA SS-PA VF-PA Time Mem sendmail 0:57 228 MB 2:15 292 MB 1:09 881 MB 403.gcc 7:31 2590 MB 22:15 1466MB 3:05 8147 MB Solaris 232:23 6672 MB - 76:27 14 GB 本手法は既存のFlow-Sensitiveな解析よりも高速に動作した メモリ使用量は既存手法より増大する場合が多い 大規模なソースコードが対象の場合，Flow-Insensitiveな解析よりも高速であった

おわり