提案手法の概要

目的: データの保護
  • 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は，静的解析 + 動的解析を組み合わせ，非常に正確な型(Effective Type)を求める
    • 構造体の要素とその要素を区別できる
    • 動的にサイズが決まる型を実行時に求められる
  • 提案手法も，Shadow Memoryを利用して正確に保護できる
1
2
3
4

int n = InputLength();
char str[n];  // VLA
Input(str);
return str[100];
Def-Use
DEF USE
str[i] L.3 L.4
Shadow Memory
  • 一方，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解析
    • データフローの実行時チェック
    • 外部(標準)ライブラリへの対応
  • 実験
    • Motivating Exampleを含むテストコード
    • 合成検体: cfi-eval
    • リアル検体
      • gravity
      • GNU cflow

外部ライブラリへの対応

定義関数
  • read(), scanf()など，外部入力による変数の定義をShadow Memoryに反映させる
    • 引数・返り値から，どこに，何バイト書き込んだかを取得する
1
2
3
4
5
6
7
8
9

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

struct operation op;
op.func = func1;
read(0, op.opd, 0x30);  // overwrite op.func
op.func();
Shadow Memory
提案手法によるDef-Use
DEF USE
op.func L.7 L.9
op.opd L.8 -
malloc(), free()
  • malloc()時に，確保したオブジェクトの情報を保存する
    • 引数・返り値から，どこに，何バイトのオブジェクトを確保したか取得する
    • Effective Typeから着想を得た
  • free()時に，malloc()で確保されたオブジェクトに"FREE"とマーク
    • 既にfreeされていた場合，Double Freeとして報告
1
2
3
4
5
6

char *secret = malloc(n); // 0x1000
...
free(secret);

char *uaf = malloc(0);    // 0x1000
printf("secret = %s\n", uaf);
L.1: malloc(n)
L.3: free()
L.6: Use

実験結果

cfi-eval: Control-Flow Attackの保護評価

Classification CBench Testsuite 提案手法
Indirect Call Code Pointer Overwrite ✓
Reuse ✗
Indirect Jump Tail Call Overwrite ✓
Reuse ✗
setjmp/longjmp ✗ (対応可)
Return Address Return Address Overwrite ✓
Type Confusion Function Type Confusion ✗
Assembly Support Indirect Call/Jump ✗
Cross DSO Support Dynamic Shared Objects △
  • Type Confusion, Assembly Support
    • サポート対象外
  • Cross DSO Support
    • DSOファイルのLLVM IRと一緒に解析・コンパイルできる場合のみ有効
Reuse: Def-Useの保護では防げない攻撃
  • もし，Input()が1の場合，配列の範囲外であるy[0]が読まれる
  • しかし，xとyのどちらもグローバル変数であり，定義元を判別できない
1
2
3
4
5
6
7
8
9
10

struct Vec {
  int x[1];
  int y[1];
};

struct Vec g = {100, 200};  // global variable

int main() {
  return v.x[Input()];
}
Def-Use
DEF USE
g.x[0] Global init (L.0) L.9
g.y[0] Global init (L.0) -

リアル検体: gravity, GNU cflow

解析結果

リアル検体への適応・解析の報告予定だったが間に合わず，，，

リアル検体のビルド ⇒ LLVM IRファイルの取得
  • 多くのC,C++プロジェクトには，ビルドシステムによるビルドの自動化がされる
    • gravity: CMake
    • GNU cflow: Autotools
  • ビルドシステムに手を加え，LLVM IRを取得する
  • コンパイルオプション: Link Time Optimization (LTO)
    • リンク時に最適化するためのオプション
    • LLVM IRがコンパイルされる
  • リンカー: gold
    • LLVM IRのLTOに対応しているリンカー
    • プロジェクト全体を一つのLLVM IRファイルにまとめられる

C,C++を解析対象にしている & LLVMを使用する人の手助けはできるかも

今後について