F11 - qwik.jp

F11: Analysis III
(このセッションは論文２本です)
石尾隆，鹿島悠
大阪大学
Inferring Data Polymorphism
in Systems Code
大阪大学情報科学研究科
井上研究室石尾隆
論文の概要
• “Data Polymorphism” を解析する手法を提案
– ポインタのダウンキャストの安全性をチェックする
手法
– 技術的にはポインタ／エイリアス解析の一種
• Linux カーネルを対象に構築，実験
– カーネルのコードの書き方を想定した手法
– C言語だけを対象にした手法
– 4.4MLOC のコードから，28,767か所のダウン
キャストのうち75％の安全を確認
3
Data Polymorphism
• 一般的な型の変数（long や void*）として，特定の
データ型のポインタを扱うこと
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;
…
}
渡された関数ポインタと
データの利用側
void __run_timers(…) {
…
timer = …
fn = timer-> function;
data = timer-> data;
fn(data);
}
4
解析の目的
• データ型へのダウンキャストが安全かどうか
を静的に知りたい
/* 引数を，必要なデータ型にダウンキャストして利用 */
void buffer_timeout(unsigned long data) {
struct my_datatype *my_data = (my_datatype*)data;  このキャストは安全か？
…
}
– 関連研究には，C言語自体の型安全性・メモリ安
全性の向上や，動的な型検査が挙げられている
5
解析の手法
構造体に，関数ポインタと引数が組で設定されることが多い
mydata.timeout.function = buffer_timeout;
mydata.timeout.data = (unsigned long)(&mydata);
1. 上記のような同時に代入されるデータの組 (Structural
Relationship) を検出
– 型 my_datatype， “.function” と “.data” を組として記録
2. 抽出された組が使われる場所に実際に到達するデータの組
(Structural Correlation) をすべて取り出す
– 「.function = buffer_timeout 関数，.data = init 関数の
mydata という変数」という組を抽出
– 引数(.data)の型とダウンキャストの型が一致すればよい
6
解析の特徴
• 構造体メンバーに対するエイリアス解析 (5章)
– Global Points-to Graph を作らず，メモリ使用量を抑制する
– そのかわり，手続き間のデータフローを毎回探索
• Linux カーネル解析に 50コアのクラスタで 3時間40分
• CPU時間の合計は 130時間
– Linux カーネルのサイズに対応できる，ヒープ構造を考慮した解析であ
ることに新規性がある
• ただし，調べる対象を void* などに限っている
• うまく解析できない場所は，手動の annotation で対応(6章)
アノテーションは２種類：
– 既知の Structural Relationship/Correlation を手動で割り当てる
– 特定の関係を調査対象から除外するもの
7
実験結果
• Linux 2.6.17.1, 4.4MLOC
• Data Polymorphism と思われる呼び出しは7,850か所
– 11,976 箇所に，関数ポインタを使った呼び出し
– うち 7,850 箇所 (66%) で，引数が void* 型か，void* 型の
フィールドを含む構造体となっていた
• ダウンキャストは28,767か所，うち75％の安全を確認
• 177か所のアノテーションが必要だった
– アノテーションなしでどこまで正確だったのかは不明
– アノテーションが解析に必要だと判断する方法は与えられてい
ない
8
Boosting the Performance of
Flow-sensitive Points-to Analysis
using Value Flow
大阪大学情報科学研究科
井上研究室 M2 鹿島悠
高速なFlow-senstiveポインタ解析の提案
SSA形式に
変換された
ソースコード
A = alloc_A
B = alloc_B
t1 = alloc_a
t2 = alloc_b
store t1, A
store t2, B
…
Value Flow Graph : ポインタ・メモリーオブジェクトのフローを表現
ポインタ
変数・store load命令
alloc_A
alloc_B
A
B
store t1, A
store t2, B
Direct Edge
代入によるフロー
を表す
Indirect Edge
a1 = load t1
s1 = load p
store q,s1
s2 = load q
ポインタを介して
のフローを表す
store p, s2
a3 = load t1
a2 = load t1
あるポインタが代入される変数 = ポインタノードから到達可能な変数 10
SSAからVFGへの変換 (1/2)
• VFGにDirect Edgeを引くルール
SSAの命令
VFGに引かれるエッジ
a = alloc_o
alloc_o → a
a=b
a → b
• VFGにIndirect Edgeを引くルール
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される
11
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 とする
• メソッド呼び出しの扱い
– 予備変数を導入し，参照を渡している場合でも，値渡
しのように扱う
12
実験
• 実験設計
– 本手法(VF-PA)と，Flow-Insensitiveなポインタ解析(IPA)，
既存のFlow-Sensitiveなポインタ解析(SS-PA)を比較
• 実験結果 (Timeは分:秒)
IPA
Time
SS-PA
Mem
Time
VF-PA
Mem
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
232:23
6672 MB
-
-
76:27
14 GB
Solaris
• 本手法は既存のFlow-Sensitiveな解析よりも高速に動作した
• メモリ使用量は既存手法より増大する場合が多い
• 大規模なソースコードが対象の場合，Flow-Insensitiveな解析よりも高速であった
13
おわり

Download Report