---
marp: false
paginate: false
author: Konishi Shogo
date: 24/12/10
style: |
blockquote > blockquote > blockquote {
font-size: 50%;
font-weight: 400;
padding: 0;
margin: 0;
border: 0;
border-top: 0.1em dashed #555;
position: absolute;
bottom: 70px;
left: 70px;
}
.columns {
display: grid;
grid-template-columns: repeat(2, minmax(0, 1fr));
gap: 1rem;
}
math: mathjax
---
# プログラム解析系の論文紹介 - SMLTA
### "DeepType: Refining Indirect Call Targets with Strong Multi-layer Type Analysis", USENIX Security 2024
**Title**:
[DEEPTYPE: Refining Indirect Call Targets with Strong Multi-layer Type Analysis](https://www.usenix.org/conference/usenixsecurity24/presentation/xia)
**Authors**:
Tianrou Xia, Hong Hu, and Dinghao Wu
**Presented at**:
33rd USENIX Security Symposium
**Year**:
2024
## 1. Summary
- 従来のMulti-Layer Type Analysis(MLTA)よりも粒度を上げた解析を行うことで，間接呼び出し先を解決する精度を向上させる手法: Strong Multi-Layer Type Analysis(**SMLTA**)を提案し，PoC実装: DeepTypeの評価を行った.
- Multi-layer typeを分割して解析するMLTAに対し，SMLTAは**multi-layer type全体を**直接的に解析し，間接呼び出し先を算出する．
- 従来手法の実装(TypeDive)と本手法の実装(DeepType)を比較したところ，間接呼び出し解決の平均候補数(Average Number of Targets, or ANT)が**約43%減少**し,False Positiveの大幅な減少が示唆された.
- Runtime overheadに関しても従来手法と比較して効率が向上しており,time overheadは平均で**約37%減少**し,memory overheadは評価した全てのケースにおいてわずかに減少した.
## 2. Background
### Indirect Call Tracking for CFG Construction
(注: 本記事では参照論文の表記に従ってinter-procedural CFG,あるいはcall graphにあたるものを含めてCFGと呼ぶ.)
Control-Flow Graph(CFG)は:
- 静的解析によるバグの検知
- 機密性の高い計算の分離を目的としたプログラムの分割
- 記号実行におけるパス刈り
- Directed Fuzzing(DGF)による実行の誘導
- Control-Flow Integrity(CFI)のソフトウェア実装
など，プログラム解析分野の多様なユースケースにおいて活用されている. おのずとCFGの精度はそれらのツールの性能に直結するわけだが，CFGの構築において主要な課題がある; 間接呼び出しの解決である. 構文によってではなく，プログラムの構成によって定まるため，間接呼び出し先の特定は容易ではない．実際，GCCやClangはこれらの間接呼び出し先を割り出してはくれず，CFGの構築のためには追加で解析を行う必要がある.
最初に思いつくナイーブな方法はアドレス参照操作を受ける関数(address-taken function)を全て呼び出し先候補としてCFG edgeに追加するものであるが，実際には呼び出されない関数(false positive)を候補としてしまう．動的な解析によって追跡する手法は基礎とするtaint解析等の精度に依存はするが正確である．しかし非常に時間がかかり，さらに解析漏れの懸念が拭えない．関数型の一致するものを呼び出し先とする手法は(type-based approach)は効率的だが,同じ型を持った大量の関数から実際の呼び出し先を割り出すことはできない．
### Multi-Layer Type Analysis (MLTA)
間接呼び出し先の関数がアドレス参照操作を受け，どこかに代入されるという性質を活かして，関数型と代入先の変数型を組み合わせた複合型(multi-layer type)による識別を提案したのが，type-based approachのSOTAとされてきた[MLTA[CCS'19]](https://dl.acm.org/doi/10.1145/3319535.3354244)である. 具体例を以下に示す．
```c
1 struct NetworkOps { void (*write)(char* data); };
2 struct FileOps { void (*write)(char* data); };
3
4 void network_write(char* data) { /* ... */ }
5 void file_write(char* data) { /* ... */ }
6
7 NetworkOps net_ops;
8 FileOps file_ops;
9 net_ops.write = &network_write;
10 file_ops.write = &file_write;
```
最初の2行で関数ポインタ型の`write`というメンバを持つ構造体が2つ定義されている.9行目と10行目で関数のアドレス参照を取り，それぞれの構造体メンバに代入している．MLTAはこのようなコードを解析し,以下のテーブルを作成する.関数ポインタやそれを内部に持つ構造体型の型情報，構造体の場合は関数ポインタメンバのindex,そして呼び出し先の候補となる関数の集合からなる. MLTAは,例えば9行目の`net_ops.write`という変数の型を`void (char*)*`として単に見るのではなく,`void (char*) | struct.NetworkOps` という複合型で解釈する.これによって別々の構造体メンバに代入された`network_write`と`file_write`を区別することができる.
| Type | Index | Functions |
|------|--------|------------|
| void (char*)* | - | {network_write, file_write} |
| struct.NetworkOps | 0 | {network_write} |
| struct.FileOps | 0 | {file_write} |
Table 1. Mappings between types and functions in MLTA for a simple example
以上を踏まえ，著者はMLTAの課題を以下の例を用いて指摘し,SMLTAと呼ぶ新たな間接呼び出し解決手法を提案した.
## 3. SMLTA
#### Motivating Example
```c
1 typedef void (*fp)(char*);
2 struct Write {fp low_priv; fp high_priv;};
3 struct User {struct Write *uw; ...};
4 struct Kernel {struct Write *kw; ...};
5
6 void func_init(struct Write *w_op, struct Kernel *k) {
7 w_op->low_priv = &write_to_shared_mem;
8 w_op->high_priv = &write_to_protected_mem;
9 k->kw->low_priv = &write_to_protected_mem;
10 k->kw->high_priv = &write_to_kernel_mem;
11 }
12
13 void user_priv_write(fp icall_ptr, char *buf) {
14 ...
15 (*icall_ptr)(buf);
16 }
17
18 void write_to_mem (char *msg) {
19 struct Kernel *k;
20 struct User *u;
21 struct Write *w_op;
22 char buf[MAX_LEN];
23 func_init(w_op, k);
24 strcpy(buf, msg); // buffer overflow
25 u->uw = w_op;
26 ...
27 if (user_mode()) {
28 if (low_priv()) (*u->uw->low_priv)(buf);
29 else user_priv_write(u->uw->high_priv, buf);
30 }
31 }
```
24行目の`strcpy`にて，ユーザーからの任意長の`msg`文字列をcopyするbuffer overflow脆弱性を抱えていると仮定する.`buf`とstack上で隣接する`w_op`変数は25行目で`u->uw`に代入されており，したがって攻撃者は`u->uw->low_priv`の下位バイトを任意に書き換えることが可能である(ちなみに，null-terminatedであるC-stringの特性上,データ構造を破壊せずに他の変数を書き換えることはできない)．このような脆弱性の防御のために，例えばソフトウェアCFIを導入したとしても，基礎となるCFGの精度が悪ければ，28行目の間接呼び出しが不正な関数(つまり`write_to_shared_mem`以外の関数)に飛んだことを検知できないかもしれない.
#### case of MLTA
さて，MLTAにこのコードを渡すと以下のようなテーブルを返す.
| Type | Index | Functions |
|-----------------|-------|---------------------------------------------|
| void (char*)* | - | write_to_shared_mem(7) |
| | | write_to_protected_mem(8,9) |
| | | write_to_kernel_mem(10) |
| struct.Write | 0 | write_to_shared_mem(7) |
| | 0 | write_to_protected_mem(9) |
| | 1 | write_to_protected_mem(8) |
| | 1 | write_to_kernel_mem(10) |
| struct.User | 0 | - |
| | ... | - |
| struct.Kernel | 0 | write_to_protected_mem(9) |
| | 0 | write_to_kernel_mem(10) |
| | ... | - |
Table 2. Mappings between types and functions in MLTA for a motivating example
Functions列は表示の都合上集合ではなく行に展開した．なお，カッコの中は関連する行番号を示している．例えば，10行目の
```c
k->kw->high_priv = &write_to_kernel_mem;
```
という複合型`void(char*)* | struct.Write | struct.Kernel`への代入文を見て,MLTAは`write_to_kernel_mem`関数を3つの型: `void(char*)*`, `struct.Write`, `struct.Kernel`のエントリに追加する．
このテーブルをもとに問題の28行目の間接呼び出しを解決しようとするとどうなるだろうか．代入先の関数ポインタ`u->uw->low_priv`に対応する複合型は
```c
void(char*)* | struct.Write | struct.User
```
である. まず空欄となっている`struct.User` with index 0のエントリを計算する．第1層の`void(char*)*`型に紐付いた関数の集合は `{*shared*, *protected*, *kernel*}`である(一部略記). 第2層の`struct.Write`に紐付いたそれは`{*shared*, *protected*}`である. 第3層の`struct.User`に直接紐付いた関数はないが，下位層から候補となる関数の集合を計算する．したがって，`struct.User`に紐づくのは`{*shared*, *protected*, *kernel*}`である. 最後に,各層に紐付いた集合の積を取ることで28行目の間接呼び出し先の候補を`{*shared*, *protected*}`と算出する．結果的にこれは不正確で,ground truthである`{*shared*}`とは異なり, `*protected*`が余分に候補として追加されている.
#### case of SMLTA
次に提案手法であるSMLTAの作成するテーブルを示す.
| Type | Functions |
|-----------------|-----------------------------------------------|
| void (char*)* \| s.Write#0 | write_to_shared_mem(7) |
| void (char*)* \| s.Write#1 | write_to_protected_mem(8) |
| void (char*)* \| s.Write#0 \| s.Kernel#0 | write_to_protected_mem(9) |
| void (char*)* \| s.Write#1 \| s.Kernel#0 | write_to_kernel_mem(10) |
Table 3. Mappings between types and functions in SMLTA
SMLTAはType列に複合型をそのまま入力していることが分かる．つまり，複合型をKeyとして関数集合を管理する．この利点は件の28行目における間接呼び出しの解決時に現れる．SMLTAでは代入先の複合型は
```c
void(char*)* | struct.Write#0 | struct.User#0
```
のように表される．`struct.User#0`は`struct.User`の0番目のメンバという意味である．SMLTAはこの複合型に対する型情報の伝播(information flow, e.g. casting)が発生しうる型(friend type)を検索する.この場合は
```c
void(char*)* | struct.Write#0
```
のみが該当する.したがって呼び出し先の関数候補は`{*shared*}`と定まり，これはground truthに一致する.
#### Infomation Flow
ところで,SMLTAの方が比較的精度が良さそうだということは分かったが，この原因の一つはMLTAが複合型を分割して記録してしまっている点にある. では，なぜMLTAは複合型を分割したのだろうか．ざっくり言うと，分割して記録することで型キャストなどを含む複雑な型情報の伝播の追跡を回避し，処理を単純化するためである．一方で今回紹介する論文の著者らはこの型情報の伝播を細かに追跡する技術を開発しており，これをもってして複合型をKeyとしたテーブルからの間接呼び出し解決を実現しているのである．詳細は次章以降にて述べる.
#### Fuzzy Type
最後に,実際は間接的に呼び出されるような関数を候補から外してしまう(false negative)可能性を減らすためのアプローチを確認しておく. 先のコードの15行目を参照されたい.
```c
1 typedef void (*fp)(char*);
...
13 void user_priv_write(fp icall_ptr, char *buf) {
14 ...
15 (*icall_ptr)(buf);
16 }
```
`icall_ptr`の型に関する情報は`void(char*)*`ということ以上に何も分かることはない.このような場合は,呼び出されうる関数を保守的に全て列挙することが望ましい.MLTAはテーブルの対応するエントリを参照して直接的に`{*shared*, *protected*, *kernel*}`と関数候補を算出する．しかし,SMLTAは直接対応するエントリをテーブルに持たない.この時,`icall_ptr`が`user_priv_write`関数の引数として渡されていることに着目する.SMLTAは,引数として渡される曖昧な型(fuzzy type)に対して,終端の型を含む任意の複合型を関連する型(friend type)であるとして呼び出し先の候補を計算する.`void(char*)*`がfuzzy typeである今回は,
```c
void (char*)* | s.Write#0 | write_to_sh
void (char*)* | s.Write#1 | write_to_pr
void (char*)* | s.Write#0 | s.Kernel#0
void (char*)* | s.Write#1 | s.Kernel#0
```
これら全ての複合型のエントリから集合和を取り,`{*shared*, *protected*, *kernel*}`を算出する.
## 4. DeepType: Architecture Overview
著者らは提案手法をDeepTypeというプロトタイプに実装した.DeepTypeの全体図を以下に示す.
```mermaid
graph TD
A[Input: Program bitcode] --> B[Phase 1]
B[
Phase 1:
Information Collection
] --> C
B --> D
B --> E
C[Type Lookup Maps] --> F
D[Type-Func Map] --> F
E[Type-Type Map] --> F
F[
Phase 2:
Target Identification
] --> G
G[
Output:
I-call 1 loc ...
Target set
I-call 2 loc ...
Target set
]
```
Figure 1. DeepType architecture overview
### Information Collection Phase
1. **Type-Function Confinements**: 関数ポインタの初期化文から複合型と関数のテーブル(Type-Function Map)を作成する.関数の引数(fuzzy types)とネストしたグローバル変数(nested global variables)に関して保守的な処理を行う.
2. **Multi-Layer Organization**: 複合型同士の階層構造を効率的に参照するために,型情報に関する複数のテーブルからなる構造体(Type Lookup Maps)を作成する.
3. **Type Relationship Resolving**: 複合型をまたぐような代入文(type assignments)や型キャストなどから,型情報の伝播を表すグラフ(Type-Type Map)を作成する.
### Target Identification Phase
1. **Friend Type Discovery**: 対象の複合型を分解して得られる任意の複合型(fragment)について，Type-Type Mapを用いて型情報の伝播を計算し，関連する複合型の集合(friend types set)を得る.
2. **Type Verification**: Friend types setの各要素から,実際に間接呼び出し先として正当な複合型をType-Func Mapsを用いて抽出し,候補となる呼び出し先の関数集合をType-Func Mapによって計算する.
## 5. Components in Detail
### Information Collection (Phase 1)
以下に示す3種類の解析によって，複合型に関する情報をまとめた3つの構造体(: Type-Func Map, Type Lookup Maps, and Type-Type Map)を作成する.
#### Type-Function Confinements
間接呼び出し先の関数がコード内のどこかにあるという仮定をすると，必ずそのアドレス参照を右辺にとり，関数ポインタを初期化する文,あるいはそれと同等の代入文があるはずである．DeepTypeは初期化文を網羅的に調べることで，Type-Func Map(: 先のmotivating exampleにて登場した，複合型と関数集合からなるテーブル)を作成する．局所変数の初期化文ならば処理は直線的である.左辺値の複合型をKeyとしたエントリに，右辺値の関数シンボルを追加してやれば良い．そのほかの場合は少し保守的な処理を行う.
1. 引数である場合(Fuzzy Type):
代入先の関数ポインタ変数が引数である場合，当然代入文を見るだけでは関数ポインタの本当の複合型(間接呼び出し時にどのような複合型でアクセスされるのか)を正確に特定することはできない.引数に渡され得る変数もまた別の構造体のメンバである可能性があるためだ．
DeepTypeはこのような型をFuzzy Typeと呼び，例外的にFuzzy Type以下の層を含む任意の複合型に対するマッチングを許す．例えば，`void(int)*|<fuzzy type>`型の関数ポインタの初期化文を見つけた時は，右辺の関数を`void(int)*|struct.A#0`であったり`void(int)*|struct.A#0|struct.B#0`などといった複合型のエントリにも対応しうるとみなす．
2. 配列のインデックスが変数である場合(Fuzzy Index):
関数テーブルなど，何らかの配列に関数ポインタが代入されることは往々にしてある．DeepTypeは構造体の何番目のメンバであるか追跡したのと同様に，配列の何番目に関数が代入されたかという情報も追跡する(実装に使用したLLVM IRの都合上どちらも似た処理で扱えるという話もある(c.f. `getelementptr`命令))．配列の何番目に代入されたか静的に特定できるならば何の問題はないが，そうでない場合もある．つまり，配列のインデックスを変数によって指定する場合である．このようなインデックス変数を著者らはFuzzy Indexと呼び，対象の関数を，配列の任意のインデックスのエントリについて対応しうると見なす．
3. ネストしたグローバル変数である場合:
話が少しややこしいので具体例だけで説明する.下のコードを見て欲しい(binutils/bfdより).
`x86_64_elf32_vec`変数のメンバ`_bfd_read_ar_hdr_fn`に初期化される関数の複合型は`void(bfd*)*|struct.bfd_target#53`だと通常は判断される(`bfd_target`構造体は巨大でその53番目のメンバが`_bfd_read_ar_hdr_fn`である).しかし実際は，13行目の代入を介して別のグローバル変数:`_bfd_target_vector`からアクセスされる可能性を持っている. つまり，Type-Func Mapの複合型:`void(bfd*)*|struct.bfd_target#53|vector.bfd_target#237`のエントリも対象の関数を保持する必要があるということである.
```c
1 typedef struct bfd_target
2 {
3 ...
4 void* (*_bfd_read_ar_hdr_fn) (bfd *);
5 ...
6 } bfd_target;
7
8 extern const bfd_target x86_64_elf32_vec;
9 ...
10 static const bfd_target * const _bfd_target_vector[] =
11 {
12 ...
13 &x86_64_elf32_vec, // nested global variable
14 ...
15 };
```
#### Multi-Layer Organization
前節にて発見された複合型について，その階層構造を高速に参照するために，以下のような複数のテーブルからなる構造体を構築する．具体的には，Type-Func MapにKeyとして追加された全ての複合型について，それらを分解し，最左の型を第1層，それを包含する型を第2層として，第1層の型をKey,第2層の型を要素とする集合をValueとしたテーブル(The First Map)を構築する．それ以上の層についても同様のテーブルを作成することで，複数テーブルの総体(Type Lookup Maps)として複合型内の階層構造を表現する．
 Figure 2. Type Lookup Maps (参照論文より引用)
なお論文では，評価対象としたプログラム(Linuxを含む)について，(関数ポインタの初期化時に使用される複合型のうち)最大で何層の複合型が登場しているのか統計を取っており，8層が最大であると結論して，7つのテーブルをもってしてType Lookup Mapsを構築していた.もちろん層の数は実装に応じて拡張可能であるが，DeepTypeを使用される際は注意されたい．
#### Type Relationship Resolving
関数ポインタの初期化文で使用された複合型と，間接呼び出し時に使用される複合型が同じであるとは限らない．ある型が別の型に代入されたり(type assignment),型のキャストが行われたり(type casting)することで型の情報が伝播し得るためである.DeepTypeはプログラム内で発生した型情報の伝播(information flow)を記録したグラフ(Type-Type Func)を作成する．ここでは，Type Assignment, Type Castingそれぞれの処理について具体例を交えて説明する．
- Type Assignment:
ある構造体の参照を別の構造体のポインタメンバに代入するなどの操作を指す．下の10行目を見てほしい.
```c
1 struct section_add {...; asection *section;};
2
3 asection *bfd_get_section_by_name (bfd *abfd, const
ch ar *name);
4
5 copy_object (bfd *ibfd, bfd *obfd, const bf d_arch_info_type *input_arch)
6 {
7 ...
8 struct section_add *pupdate;
9 ...
10 pupdate->section = bfd_get_section_by_name (ibfd,
pupdate->name);
11 ...
12 }
```
`asection*`型を返す関数`bfd_get_section_by_name`の返り値を`struct.section_add`型の変数`pupdate`内のメンバ`pupdate->section`に代入している．このようなType Assignmentは，`asection`複合型において初期化されるメンバが，`asection|struct.section_add#5`複合型内で利用される可能性を示唆している．したがってDeepTypeは`asection|struct.section_add#5`から`asection`(代入先の型から代入元の型)へ伸びる有向辺をType-Type Mapに記録する
- Type Casting:
型キャストへの対応である．次の例の4行目を見てほしい.
```c
1 static struct bfd_hash_entry *
2 string_hash_newfunc (struct bfd_hash_entry *entry, struct bfd_hash_table *table, const char *string)
3 {
4 struct string_hash_entry *ret = (struct string_hash_entry *) entry;
5 ...
6 return (struct bfd_hash_entry *) ret;
7 }
```
`struct.bfd_hash_entry`型の変数`entry`が`struct.string_hash_entry`型へのキャストを受けて`ret`変数へと代入されている(なお,6行目で`ret`変数は逆方向の型キャストを受けている).注意したいのは，型キャストが関数ポインタ初期化の前後どちらで発生するのか不明であることだ(DeepTypeの解析はdata-flow insensitive)．そこで，DeepTypeは型キャスト元/先の複合型同士を双方向に紐付けてType-Type Mapに記録する．
### Target Identification (Phase 2)
ある間接呼び出し文が与えられたとき，関数ポインタの複合型をもとに以下の処理を経て呼び出し先の関数集合を算出する.
#### Friend Type Discovery
まず，間接呼び出し文における関数ポインタの複合型に対し，複合型の分解，置換，結合といった操作を経て，関数ポインタの初期化が発生し得る複合型(Friend Type)の候補を計算する．順を追って説明する．
1. 分解:
Fragmentと呼ばれる対象の複合型を含む任意の複合型を列挙し，対象の複合型をFragmentおよびその前後で分解する.例えば`A|B|C`という複合型を対象にした場合，`B`, `A|B`, `A|B|C`, etc...といったようにFragmentを列挙し，それぞれについて`A|B|C`を，`A+B+C`, `A|B+C`, `A|B|C`などと分解する．
2. 置換:
分解したそれぞれの複合型について，Type-Type Mapを用いてFriend Typeの集合を計算する．このときの処理はType-Type Mapを有向辺の集合とみなした時の幅優先探索(BFS)による連結成分の計算に近いが，循環した型情報の伝播を考慮しなければならない点に注意したい．DeepTypeはiterationごとにqueue内が空になるまで調べたうえで,既に探索した複合型の集合に変化がなければ即座にbreakすることで循環した伝播を考慮しつつ，無限ループを回避している．(ところで，無限あるいは長大に循環した複合型についての考慮漏れが発生するのではと心配するかもしれないが，その必要はあまりない．そのような意地の悪い関数ポインタの初期化文(e.g. `node->next->next->...->next = func`)は通常存在しないからである．とはいえ，この種の打ち切りが全くFalse Negativeの発生に影響しないとも思えないので，何度か循環するまでbreakしないといったように，条件を多少緩める検討もすべきかもしれない．)
3. 結合:
あるFragmentを固定した時に得られた複数(Fragmentおよびその前後で最大3つ)のFriend Types Setについて，それらの直積を取り，連結することで，構成可能な複合型の集合を計算する.この集合の要素のいずれかに関数ポインタの初期化時の複合型が存在するはず，という訳である．
#### Type Verification
前節で最終的に得られた複合型の集合(仮にこの集合を $S$ と呼ぶ)から，以下の要件に従って型の選別と展開を行う．
1. $S$に含まれる複合型のうち，実際はプログラムに登場しない，あるいは関数ポインタの初期化に使用されないものが存在する．つまり，Type-Func MapのエントリにKeyとして存在する必要がある．
2. Fuzzy Type, Fuzzy Indexを含む複合型について，実はまだ展開がされていない(例えばFuzzy Indexは`#?`などと表記して内部で管理されている)．つまりType Lookup Mapsに記録された型の階層に沿って，Type-Func Mapあるいは$S$に点在する曖昧な複合型の表記を確定させる必要がある.
上記の条件を満たした型が最終的な"間接呼び出しに関連する複合型"である(: verified type)，Type-Func Mapから紐づけられた関数集合を引き出し，集合和を取って出力することで，DeepTypeは間接呼び出しの解決を終了する．
### Implementation
実装はLLVM15.0の上に2.8k LoCのC++を記述することで行われた．ソースコードは[公開済](https://github.com/s3team/DeepType)．
#### Special Handlings
解析中に著者らは4つのエッジケースを見つけ，それらへの対処法を追加している．
##### 1. Composite Instruction
LLVM IRの話をする．下のリストはsqlite3内のとある複数の関数ポインタからなる構造体を初期化する文をコンパイルした際のLLVM IR命令である．
```llvm
store <2 x i64> %12,
<2 x i64>* bitcast (i32 ()**
getelementptr inbounds (
%struct.Sqlite3Config,
%struct.Sqlite3Config* @sqlite3Config,
i64 0, i32 13, i32 0)
to
<2 x i64>*),
align 8, !dbg !56905, !tbaa !11590
```
命令全体としては，は`%12`に格納されている`<2 x i64>` 型の値 (64ビット整数を2つ持つベクトル)を，`sqlite3Config`というグローバル変数の特定のメンバに格納する.`getelementptr`は書き込み先のアドレスを計算している.`bitcast`は型のキャストを行っている．注意したいのは，これらの命令が`store`という1つの命令のオペランドに埋め込まれていることだ．これらの親子関係を図に示すと下図のようになる．
```mermaid
graph TD
A(store) --> B(<2xi64>)
A --> C
C(bitcast) --> D(getelementptr)
C --> E(<2xi64>*)
```
Figure 3. Composite Instruction
DeepTypeはこのような複合的な命令の解析も行うように実装されている(わざわざ論文に書くということは簡単ではなかったのだろう)．この例で言えば，`bitcast`で発生した型キャスト情報をもとに，`i32()* | struct.sqlite3_mutex_methods#0 |struct.Sqlite3Config#13`型と`i32()*| struct.sqlite3_mutex_methods#0`型の双方向の型情報の伝播をType-Type Mapに登録する．
##### 2. Anonymous structures
LLVMは最適化の過程でコードでは名前のついていた構造体を無名構造体に落とし込んでしまう場合がある．DeepTypeは解析中の構造体に識別子がついていないことが分かると，構造体のメンバ型の連結によって代替となる識別子を与えることで無名構造体同士を極力区別するように工夫している．
##### 3. Dead functions
LLVMは`use_empty()`メソッドによってある関数が使用されているかどうか簡単に教えてくれる．そのような未使用の関数(dead function)について解析をすっとばすということである．
##### 4. Empty type
LLVMには無名構造体とは別に，メンバすらも持たない空構造体(: `{}`型)というものが存在する．メンバすらないので基本的にこの型を識別することはできない．ただし，型キャスト命令内で使われている場合は別である．DeepTypeは`bitcast`命令のオペランドの片方に空構造体が現れた場合，キャスト先，あるいはキャスト元の複合型と空構造体が一方向の関連を持つとしてType-Type Mapに登録する(キャスト先が`{}`の場合は，`{}`からキャスト元の複合型への有向辺を伸ばす, vice versa)．
#### Caches
DeepTypeは効率のために２つのキャッシュを利用する．すなわち:
1. Verified Typeの集合
この集合に含まれる複合型はtype verificationをbypassできる
3. 間接呼び出し時の複合型をKey, 解決時の関数集合をValueとするテーブル
同じ複合型を持つ間接呼び出しの解決処理をbypassできる
## 6. Evaluation
- 比較対象: TypeDive(MLTAのPoC, commit id: `acb8f4c`)
- 評価対象: Linux kernel、5つのWeb server、14のuser application
- Web server: nginx, httpd, openVPN, proftpd, sshd
- User application: GNU Binutils内の15個のプログラムから13個を選択$^1$，SQLite
- 実験環境: Ubuntu 20.04，8-core Intel Core i9-9880H CPU @ 2.30GHz，16GB DDR4 RAM
- コンパイル: WLLVM with LLVM-15，`-g -O0` Flags(Debug Symbols included, Lowest optimization level)
> 1. 残りの2つ:`sysinfo`, `elfedit`が含む間接呼び出しの数はそれぞれ0,53個とかなり小さく，提案手法と既存手法との結果に相違がなかったため評価対象から外したようだ．
### Effectiveness
間接呼び出し先の候補数(: Average Number of Targets, or ANT)の平均によってDeepTypeがどれだけ候補を絞り込めたのかを評価した．
- 既存手法に対するANT減少率の平均：43.11%
- 評価対象別の結果：
- 減少：binutils (77.50%), httpd (49.23%), linux (61.30%)
- 増加：nginx (-13.93%), openvpn (-45.06%), proftpd (-4.73%)
- 増減の要因
- 実装時のSpecial HandlingによるFalse Positive(FP)およびFalse Negative(FN)を排除したことの影響
- Fuzzy Typeなどにおける保守的な処理がFPを増やしすぎたため増加
- TypeDiveの結果を手動で分析すると，(原著の主張とは異なり)先行研究はField-Sensitivityが不十分だったため相対的に減少
(e.g. `i64(i8*)* | struct.bfd_target#13`と`i64(i8*)* | struct.bfd_target#23`の区別がついていなかった)
- コンパイル時の最適化レベルの影響
- 最適化レベルを上げるとANTは増加
- DeepTypeが解析のために依存したIR命令がoptimize outした
- `-O3`の結果でもTypeDiveよりANTは減少した(`-O0`時に減少していた評価対象に限り)
### Runtime Performance
- Time overhead:
- 5.45%~72.95%,平均37.02%の削減
- Memory overhead:
- 全評価対象でTypeDiveよりメモリ使用量をわずかに下回った
- Linux kernelで最大の使用量(4.2GB-4.3GB)を記録
### Ablation
Special Handlingsを除いた実装(:DT-noSH), およびType-Func Mapの構築に際して複合型を分割して記録する実装(:DT-weak)とDeepTypeの比較を行った．
| Program | DEEPTYPE | DT-noSH | DT-weak |
|-----------|----------|----------|----------|
| binutils | 2.47 | 2.48 | 2.70 |
| sqlite | 6.24 | 6.33 | 6.97 |
| nginx | 6.38 | 8.62 | 12.99 |
| httpd | 6.23 | 6.23 | 7.66 |
| openvpn | 2.35 | 2.39 | 2.35 |
| proftpd | 3.10 | 3.13 | 4.22 |
| sshd | 5.43 | 5.42 | 5.43 |
| linux | 9.74 | 9.72 | 13.09 |
Table 4. ANT values of DeepType, DT-noSH, and DT-weak (参照論文より引用)
- DT-noSHについてはわずかにANTが減少した
- エッジケースへの対処という性質から，精度の向上がANTでは見えにくい可能性
- FPの減少とFNの減少が相殺した可能性
- DT-weakに対してはわかりやすくANTが減少した
### Case Study
libcueに存在したCVE-2023-43642の脆弱性の例を用いて，SMLTAによるCFG精度の向上がCFIによる脆弱性の防御を強化することを実際に示す．
```c
1 void track_set_index (...) {
2 ...
3 track->index[i] = ind;
4 }
5
6 static gboolean get_file_metadata (...) {
7 TrackerExtractInfo *info;
8 ...
9 tracker_extract_info_unref(info);
10 ...
11 }
12
13 gboolean g_option_context_parse (...) {
14 ...
15 if (!(* group->pre_parse_func) (context, group, group->user_data, error))
16 ...
17 }
```
3行目の`i`は符合付き整数かつ`ind`と共にUser-controllableであり，`i`を負の数にすることで，heap object:`track->index`のheap chunk size等を書き換えることができるout-of-bounds脆弱性を持つ．PoCに従うと，そのあと何やかんやあり(発見者による親切丁寧なexploitの解説記事が[こちら](https://github.blog/security/vulnerability-research/cueing-up-a-calculator-an-introduction-to-exploit-development-on-linux/)にある．概要は以下)，
> House of Spirit x2 to overlap a heap object and an internal(`libcue`) function pointer
--> Craft a value adding offset to another external (`glib`) function pointer
--> Forge the overlapped internal function pointer with it
--> Trigger indirect function call
--> Chain the above process to call `system`-like target function (`initable_init`)
汚染された2つの関数ポインタ`info->dispose`,`group->pre_parse_func`を経由することで任意のコマンドを実行する関数`initable_init`を発火できる.
ところでGNOME環境には,ユーザの`~/Downloads`ディレクトリ内にダウンロードされた`*.cue`ファイルをこのlibcueを使って自動処理するプログラム(`track-miner`)がpre-installされているらしい．つまりCVE-2023-43642は，相当な確率でone-click RCEが発生する危険性を持つ重大な脆弱性である．
さて，著者らはこの脆弱性について調査を行い，`initable_init`関数の発火に悪用可能な関数ポインタを新たに5つ提示した．そしてこの5つ全ての関数ポインタの間接呼び出し文についてMLTAおよびSMLTAで解析したところ，MLTAは全ての関数ポインタに対して`initable_init`を間接呼び出し先の候補として数え上げてしまったのに対しSMLTAは正確に候補から除外したのである．例えば5つのうちの1つ:`traverse_func`変数は`gboolean (gpointer*, gpointer*, gpointer*)*`という型を持つが，MLTAは`initable_init`関数の型を`gboolean (Ginitable*, GCancellable*, GError**)*`と解釈し，これらの型同士で情報が伝播可能，つまり呼び出し先の候補であると判断する．一方SMLTAは`initable_init`の型を`gboolean (Ginitable*, GCancellable*, GError**)*| struct._GInitableIface#1`のように解釈することで，このような重大なFalse Positiveを回避するのである．
## 7. Limitation and Future Work
まず実装上の制限について：
- LLVM IRの型情報の制限:
IR上で型の解析を行うが，たとえソースコードでは明らかであっても，決まって関数の型情報が命令内に現れるわけではない(論文で直接言及はされていないが先程示したsqlite3の関数ポインタテーブル:`struct.sqlite3_mutex_methods`の例はそれにあたるかもしれない)．この傾向はグローバル変数の複雑な初期化について特に顕著であり，このような型の見落としはFalse Negativeの発生につながる．あるいはLLVM(Clang)向けのLinkerは`lld`だが，GNU Linker: `ld`内の関数が解析対象のプログラムから間接呼び出しを受ける場合もあり，その追跡は難しいようだ．
次に精度の制限について：
- エッジケースへのSpecial Handlingsが現在の実装で十分である保証はない．
- プログラム全体を通して複合型の階層が浅い場合や，そもそもサイズが小さく間接呼び出しの数が少ない場合は，SMLTAの利点は現れにくく，むしろFuzzy Typeなどの保守的な処理によってFalse Positiveが増加する可能性がある.
- そもそも同じ複合型を用いた別々の関数ポインタの初期化があった場合，現手法では区別ができないのでFPである.
そして評価における制限について：
- 間接呼び出し先の関数集合に関するground truthの情報が不足している．実際，そのようなデータがないためにFP/FNの定量的な評価が行えていなかった．
- 動的解析手法の結果を疑似的にground truthとすることも考えたようだが，結局動的解析側の精度に何ら保証がないため，ANTというmetricsを用いた.
最後に著者の予定している改善方針を述べる:
- 軽量な関数内Data-Flow解析による精度の改善
- 間接呼び出しに関する包括的なground truth benchmarkの整備
Sign in with Wallet
Connect another wallet