提案手法の概要

目的: データの保護
  • Buffer Overflowの検知
  • Use After Freeの検知
  • etc
手法: Data-Flow Integrity + Field-sensitiveポインタ解析

以下の２つを組み合わせて，構造体の要素を区別したデータフローの保護を実現する:

  • Data-Flow Integrity: データフローの保護
    • 静的解析: 定義と使用の関係(DefUse)を求める
    • 動的解析: 実行時に各変数の定義と使用の関係が正しいのか確認する
  • Field-sensitiveポインタ解析: 構造体の要素を区別したポインタ解析
    • 構造体を区別したDefUseを求める
Step1: 静的解析

Field-sensitiveなDef-Useを求める．

1
2
3
4
5
6
7
8

struct Vec {
  int x, y;
};

struct Vec v;
v.x = 100;
v.y = 200;
return v.x + v.y;
定義と使用の関係(Def-Use)
DEF USE
v.x L.6 L.8
v.y L.7 L.8
Step2: 動的解析

Shadow Memoryを用いて以下を行う:

  • 変数の定義場所の保存
  • 変数の使用時，定義場所が正しいかどうかのチェック
1
2
3
4
5
6
7
8

struct Vec {
  int x, y;
};

struct Vec v;
v.x = 100;
v.y = 200;
return v.x + v.y;
定義と使用の関係(Def-Use)
DEF USE
v.x L.6 L.8
v.y L.7 L.8
Memory
Shadow Memory
Motivating Example
vs Data-Flow Integrity[OSDI'06]
  • DFIは，構造体の要素を区別して保護できない(Field-insensitive)
  • 提案手法は，Field-sensitiveポインタ解析を用いることで，構造体の要素を区別して保護する
1
2
3
4
5
6
7
8
9

struct operation{
  char opd[8];
  void (*func)();
};

struct operation op;
op.func = func1;
Input(op.opd);  // overwrite op.func
op.func();
Shadow Memory
DFIによるDef-Use
DEF Use
op L.7, L.8 L.9
提案手法によるDef-Use
DEF USE
op.func L.7 L.9
op.opd L.8 -
vs EffectiveSan[PLDI'18] (Type-Based Sanitizer)
  • EffectiveSanは，Use-After-Freeを正確に検知できない
  • 提案手法は，定義と使用の関係から，Use-After-Freeを検知する
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int createKey() {
  int key;
  key = ...   // DEF key
  return key; // USE key
}

void readKey() {
  int illegal_key;
  printf("key = %d\n", illegal_key);
}

int main() {
  createKey();
  readKey();
}
Def-Use
DEF USE
key L.3 L.4
illegal_key - L.9
Shadow Memory

リアル検体解析機　進捗

  • 静的解析: Def-Use解析
    • Value-Flow Graph構築
    • Reaching Definition解析 (Strong Update)
    • 外部ライブラリへの対応を充実
  • 動的解析: データフローの実行時チェック using Pin
    • テストケース
    • リアル検体

静的解析: Def-Use解析

  1. Value-Flow Graph構築
  2. Reaching Definition解析 on VFG

Value-Flow Graph構築

SVFを利用してVFGを構築．
  • ポインタ解析: Field-sensitive Andersen
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

struct Vec2D {
  int x, y;
};

struct Vec2D v;
int *p;

p   = &v.x;
*p  = 100;
v.x = 200;

p   = &v.y;
*p  = 300;
v.y = 400;

*p + v.x + v.y;
graph TD store_p --> store_x --> store_p2 store_p --> store_p2 store_p2 --> store_y store_p2 --> load_p store_p2 --> load_x store_y --> load_y store_y --> load_p classDef Store stroke: blue, stroke-width: 2px; class store_p,store_x,store_p2,store_y Store; classDef Load stroke: red, stroke-width: 2px; class load_p,load_x,load_y Load; store_p["*p = 100"] store_x["v.x = 200"] store_p2["*p = 300"] store_y["v.y = 400"] load_p["*p"] load_x["v.x"] load_y["v.y"]

Reaching Definition解析 (Strong Update)

VFG上でReaching Definition解析を行い，Use-Def情報を計算．
  • Store命令: Def情報を更新
    • Strong Updateの条件を満たす場合: 古いDef情報をkillし，新しいDef情報を追加
      • 条件1: Singletonオブジェクトである
      • 条件2: ヒープオブジェクトでない
      • 条件3: 配列でない
      • 条件4: 再帰関数内のローカル変数でない
    • その他: Def情報に追加
  • Load命令: Use-Def情報を求める
Example
graph TD store_p -->|100| store_x -->|200| store_p2 store_p -->|100| store_p2 store_p2 -->|100, 200, 300| store_y store_p2 -->|100, 200, 300| load_p store_p2 -->|100, 200, 300| load_x store_y -->|400| load_y store_y -->|400| load_p classDef Store stroke: blue, stroke-width: 2px; class store_p,store_x,store_p2,store_y Store; classDef Load stroke: red, stroke-width: 2px; class load_p,load_x,load_y Load; store_p["WU: *p = 100"] store_x["SU: v.x = 200"] store_p2["WU: *p = 300"] store_y["SU: v.y = 400"] load_p["*p"] load_x["v.x"] load_y["v.y"]
  • SUにより，v.yのUse-Defが正確に
  • 一方で，*pのUse-Defは保守的に
  • Field-sensitiveなUse-Defが求まる
Use Def Set
v.x { 100, 200, 300 }
v.y { 400 }
*p { 100, 200, 300, 400 }

解析時間

Program LoC Analysis Time
gravity 16k 9 m 50 s
lua 18k 1 m 15 s
nasm 102k 70 m

(wllvmめちゃ便利)

動的解析: データフローの実行時チェック

  1. デバッグ情報にDef(Use)-IDを埋め込む
  2. SqliteにUse-Def情報を保存
  3. バイナリへコンパイル
  4. Intel Pinでデバッグ情報 + SqliteのUse-Def情報を確認

実行時データフローチェック

  • Store命令: ShadowメモリにDef-IDを書き込む
  • Load命令: ShadowメモリからDef-IDを読み，Use-Def Mapに含まれるデータフローかどうかを確認
Example
C code → 
n = 100;
use n;
LLVM IR(デバッグ情報にID埋め込み) → 
store 100, n  // DEF-ID: 1
load n        // USE-ID: 2
Binary 
mov [rbp - 0x8], 100  // DEF-ID: 1
mov eax, [rbp - 0x8]  // Use-ID: 2
Use-Def Map in sqlite
Use DefSet
2 { 1 }
難しいポイント
  • LLVM IR → Binaryの対応関係
    • 対応関係を加味して，IDを埋め込む必要あり
  • デバッグ情報による制限
    • 複数命令に一つのデバッグ情報
    • デバッグ情報の紐付いていない命令
上記の問題に対して，確実に対処するには以下が必要．
  • コンパイラ(Backend)の情報
  • デバッグ情報の伝搬規則

上記の問題に対して，アドホックに対処してきた．
→ リアル検体解析で多くの動かないパターンが見つかる，，，

解決案
  • 現状維持: 見つかったパターンを一つ一つ潰していく
  • 方向転換: 動的チェックを静的計装で済ます
    • +: LLVM IR → Binaryの対応関係不要(?)，デバッグ情報による制限なし
    • -: 学習コスト高め
    • (修論は静的計装で実装する予定)
n = 100;
use n;
store 100, n  // DEF-ID: 1
load n        // USE-ID: 2
store 100, n    // DEF-ID: 1
SET_DEF(n, 1)

CHECK_DEF(n, 1) // USE-ID: 2
load n

今後の予定

  • 動的解析
    • Intel Pinでの実装
    • or 静的計装
  • リアル検体への対応・実験
    • 検体の決定(gravity, GNU cflow)
    • 実験/評価
  • 最適化の検討・実装