---
marp: false
paginate: false
author: Konishi Shogo
date: 24/06/23
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
---
# プログラム解析系の論文紹介 - DAFL
### "DAFL: Directed Grey-box Fuzzing guided by Data Dependency", USENIX Security 2023
**Title**:
[DAFL: Directed Grey-box Fuzzing guided by Data Dependency](https://www.usenix.org/conference/usenixsecurity23/presentation/kim-tae-eun)
**Authors**:
Tae Eun Kim, Jaeseung Choi, Kihong Heo and Sang Kil Cha
**Presented at**:
32nd USENIX Security Symposium
**Year**:
2023
## 1. Summary
- データの依存関係の情報を利用して,Directed Grey-box Fuzzingを改善する手法(DAFL)を提案する.
- 計装前の静的解析において,Control-Flow Graph(CFG)の代わりにDef-Use Graph(DUG)を構築,活用することで,複雑な制御フローを追跡しようとするのではなく，到達目標周辺のコードに関係したデータフローに着目する.
- 計装対象の関数をDUGのノードに限定し(Selective coverage instrumentation)，さらにDUG上で目標により近いノードを優先するようにFuzzerにフィードバックを与える(Semantic relevance scoring)ことで,無駄を省きながらも目標に積極的に近づくようにFuzzerを誘導する.
## 2. Background and Motivation
### Directed Grey-box Fuzzing (DGF)
*Directed Grey-box Fuzzing* (DGF)は,[AFLGo[CCS'17]](https://dl.acm.org/doi/10.1145/3133956.3134020)で最初に提案されたFuzzingの手法の一つである.DGFの目的は,プログラム内の特定の目標位置に到達する具体的な入力を生成することにある.例えば,
- 報告されたバグをスタックトレースなどの情報から再現する。
- 新たに変更されたコードや,バグの修正パッチを検証する。
- 静的解析が検知したバグのある箇所に到達可能な具体的入力を与える。
といった用途で活用される.
### Challenges in Existing DGF Approaches
従来のDGFは,以下のような入力を優先的に生成する.
1) 新たな実行パスに到達するもの,あるいはコードカバレッジを上昇させるもの(as in undirected grey-box fuzzing).
2) CFGにおいて実行したノードから目標ノードまでの距離を計算し,その平均が短いもの.
これらのアプローチに対して,著者は２つの課題を指摘する.
#### Challenge 1
コードカバレッジの上昇は,到達目標だけではなく,到達する必要のないパスを実行する可能性も高めてしまう.
この問題に対処した先行研究として[Beacon[S&P'22]](https://ieeexplore.ieee.org/document/9833751)が挙げられる:
- 目標への分岐条件から各変数の取りうる値を計算し,早期にassertionを設けることで,関係のない実行パスを枝刈りする.
- 実際のプログラムは規模が大きく,複雑な分岐を持ったループなどが存在するため,枝刈り条件の正確な計算が困難な場合がある.
#### Challenge 2
ある入力(seed)に対する目標までの距離の評価を*seed distance*と呼ぶ. 従来のDGF(e.g. [AFLGo[CCS'17]](https://dl.acm.org/doi/10.1145/3133956.3134020),[Hawkeye[CCS'18]](https://dl.acm.org/doi/10.1145/3243734.3243849),[Beacon[S&P'22]](https://dl.acm.org/doi/10.1145/3133956.3134020))は,実行した全てのノードから目標ノードまでの平均距離でseed distanceを計算し,seed distanceが短い入力を優先的に実行する. しかしこの評価方法は,実行しても目標への到達に影響がないノードを評価に入れてしまう.したがって実行パスが長くなる場合(実際のプログラムは得てしてそうであるが)には間違った誘導を行う恐れがある.
この問題に対処した先行研究として[WindRanger[ISCE'22]](https://ieeexplore.ieee.org/document/9793549)が挙げられる:
- CFGにおける目標ノードへのパスから逸脱するような分岐先(e.g エラー処理)を持つbasic block: *Deviation Basic Block*(DBB) を決定する.
- 実行したDBBから目標ノードまでの距離の平均をseed distanceとすることで,目標ノードへの到達に関係のあるノードに着目してschedulingを行う.
- しかし複雑なループなどが絡むと,AFLGoなどと同様に誤ったseedの評価をしてしまう.
#### Motivating Example: CVE-2017-7578
次のFigure1にあるコード片は,libming: Flash(SWF)ファイルの出力に関するライブラリ にて発見されたbuffer overflow bug(CVE-2017-7578)を含む.
```c
1 struct SWFblock {
2 int type;
3 SWFParseFunc parser;
4 };
5
6 struct SWFblock blks[80] ={ { 46, parseSWF_DEFINEMORPHSHAPE }, ... };
7
8 int main(int argc, char *argv[]) {
9 FILE *f = fopen (argv[1], "r");
10 SWF_Parserstruct *block;
11 for (;;) {
12 if(/* not enough data in the file */)
13 break;
14 int type = fgetc(f);
15 int length = fgetc(f);
16 if (length == 63) {
17 if(/* not enough data in the file */)
18 break;
19 ...
20 } else {
21 block = blockParse(f, type);
22 }
23 ...
24 }
25 }
26
27 SWF_Parserstruct *blockParse(FILE *f, int type) {
28 for (int i = 0; i < 80; i++) {
29 if (blks[i].type == type)
30 return blks[i].parser(f);
31 }
32 }
33
34 SWF_Parserstruct *parseSWF_DEFINEMORPHSHAPE(FILE *f) {
35 SWF_MORPHGRADREC GradientRecords[8];
36 int i = fgetc(f);
37 parseSWF_RGBA(f, &GradientRecords[i]);
38 ...
39 }
40
41 void parseSWF_RGBA(FILE *f, struct SWF_MORPHGRADREC *gradient) {
42 gradient->StartColor = ...; // crash location
43 ...
44 }
```
Figure1. Motivating Example
この脆弱性のProof of Concept(PoC)は変数`type`(14行目)に`46`を代入した後に,以下の実行パスを通る.
- パーサー関数`parseSWF_DEFINEMORPHSHAPE`を関数テーブル`blk`を介して呼び出す(30行目)
- 関数`parseSWF_RGBA`が呼び出され,色情報が長さ8の固定長配列`GradientRecords`(35行目)に保存される(42行目).
この時,固定長配列の添字`i`がユーザーの入力によって与えられる(36行目)ため,buffer overflowが発生する.
#### Challenge 1: Negative Feedback
先ほどのPoCによって実行される関数の一部を,Figure2にcall graphの形でまとめている. 太字の矢印で繋がっている実行パスが問題のバグを引き起こすことになる.
```mermaid
graph TD
A[main] --> B(filelen_check)
A ==> C[blockParse]
A --> D(outputBlock)
A --> E(SWF_warn)
C ==> F[parseSWF_DEFINEMORPHSHAPE]
C --> G(...80 other functions...)
C --> G
F ==> H[parse_SWF_RGBA]
```
Figure 2: Call graph of the program
`blockParse`がユーザーの入力に応じて呼び出し得る関数の数は80もある(6行目)が,その中でtarget bugを引き起こすものは1つ(`parseSWF_DEFINEMORPHSHAPE`)だけである.
[Beacon[S&P'22]](https://ieeexplore.ieee.org/document/9833751)は変数の取りうる値に制約を設けることでtargetに到達しない実行パスを削減することを目的としたが,この例ではうまくいかない.Beaconは理想的には変数`type`が46以外だとtargetに到達しないことを計算するはず(`assert( type==46 )`)であるが,実際は複雑な制御フローの前に計算は失敗してしまう.
Challenge 2: Misleading Distance Metrics
例のプログラムに対して2つの異なるファイル入力$S_A,S_B$を仮定する.下のFigure3.aはそれぞれの入力に対する実行がCFGをどのように辿ったかを示す.ただし,各ノード内の番号はFigure1の行番号に対応する.
Figure 3.a: Scores of seeds based on AFLGo's evaluation criteria.
$S_A$ はファイルが壊れており12行目のエラーチェック(sanity check)に失敗する一方, $S_B$ のファイルは12行目のsanity checkは通るが17行目のcheckを踏むようなファイルであるものとする. 直感的には $S_B$ の比較的壊れていないファイルの方が目標の到達に近く,入力としては望ましい. DGFを最初に実装した[AFLGo[CCS'17]](https://dl.acm.org/doi/10.1145/3133956.3134020)は, $S_A$ のseed distance(入力seedの目標targetまでの距離)を実行ノード(`9`,`12`がこの場合の実行ノード.`13`は除外)から目標ノードまでの距離の平均で計算する.したがってseed distanceは $\frac{35+34}{2}=34.5$ となる.一方で $S_B$ のそれを同様に計算すると, $36.75$ と計算される. つまりAFLGoは $S_A$ を $S_B$ よりも優先して実行してしまう.
WindRangerもAFLGoと同様の課題を持つ. WindRangerはDeviation Basic Blockと呼ばれる,あるseedの実行が目標から逸脱する直前のノードの集合を計算し、そこから目標ノードまでの平均距離をseed distanceとしている.下図: Figure3.bを見ると,WindRangerが目標ノードへの距離を付与(ノードの左上の数値のこと)しているノードが,Figure3.aのそれらと比べて限られていることが分かる.しかし,seed distanceを計算してみると, $S_A$ は $34$ , $S_B$ は $45$ となり,AFLGoと同様にWindRangerも $S_A$ を優先することとなってしまう.
Figure 3.b: Scores of seeds based on Windranger's evaluation criteria.
## 3. DAFL: Key Ideas and Techniques
著者は2節で提示されたDGFの問題に対処するため,２つの技術を導入したAFLの拡張実装:DAFLを提案する.
### Selective Coverage Instrumentation
DAFLの計装はCFGノードの単位では行わない. 代わりにDef-Use Graph(DUG)と呼ばれるデータフローを表したグラフを元に,関数単位での計装を行う. したがって,到達目標が使用するデータを触っている部分から選択的にcoverage feedbackを得ることができ,目標に関係のない部分からのnegative feedbackを抑えることができる.
DAFL.svg)
Figure 3.c: Scores of seeds based on DAFL's evaluation criteria.
Figure3.cはMotivating Exampleとして例示したプログラムにおけるDUGの一部を示している. このグラフに現れたノードを含む関数のみに,DAFLは計装する. 関数単位で計装を行う理由は,計装の粒度を粗くすることで制御フローの面で依存している部分を考慮するためである.例えば,Figure1において関数エントリ`blk[i].type`と入力`type`を比較する箇所(29行目)は目標の42行目に到達するために重要であるが,データ的な依存関係はない.
まとめると以下のようになる:
1. 関数間静的解析を実行し,目標箇所がデータ的に依存する文を特定する.
2. Def-Use Graphを構築する.
3. DUGのノードを含む関数を選択的に計装する.
### Semantic Relevance Scoring
DAFLはCFG上のseed distanceによる入力の評価を行わない.代わりに,DUG上の距離の合計を元に入力の評価値を計算する(semantic relevance scoring). Figure3.cを見ると,ノードの左上に整数値が付与されていることが分かる.これは各ノードの評価値(semantic relevance score)であり,DUG上での最長路の長さと目標ノードとの距離の差に相当する. つまり,最も目標ノードから遠い(つまり辿る辺の数が多い)ノードの評価を $1$ とし,そこから目標ノードに近づくにつれて評価値が上がるように割り振られる.当然,目標ノードの評価値は最大となる. 距離の平均が小さいほど優先度が高まるseed distanceとは異なり,semantic relevance scoringは,各ノードの評価値の合計が高い入力を優先する. この指標に基づき入力 $S_A,S_B$ の評価を行うと, $S_A$ はノード`9`のみを通過したため評価値は $1$ であるのに対し, $S_B$ は`9`と`14`を通過したため $1+1=2$ となり,初めて $S_B$ は $S_A$ より高い評価を得る.
まとめると以下のようになる:
1. ある入力がDUG上で実行したノードから目標ノードまでの距離を計算する.
2. 距離と最長路長さの差をノードの評価値とし,実行したノードの評価値の総和によって入力を評価する.
3. 高い評価値を持つ入力を優先的に選択して変異,および実行する.
## 4. DAFL Architecture and Workflow
DAFLの全体図をFigure4に示す.
```mermaid
graph TD
A[Input: Program + Target Location] --> C[Thin Slicing]
C --> |Relevant Functions| E[Selective Instrumentation]
C --> |Def-Use Graph| F[Semantic Relevance Scoring]
F --> G[Seed Scheduling]
G --> I[Mutate and Execution]
I --> |Selective Coverage Feedback| F
E --> |Instrumented Program| F
```
Figure4: DAFL architecture
入力として対象のプログラムと到達目標箇所を受取り,静的解析およびFuzzingを実行する.
### Static Analysis Phase
1. **Thin Slicing**: 関数間のデータフロー解析によって到達目標箇所と関係のあるコード断片(slice)を計算する.
2. **Def-Use Graph Construction**: 得られたsliceを元に,Def-Use Graph(DUG)を構築する.
3. **Selective Instrumentation**: sliceを含む関数を選択的に計装する.
### Fuzzing Phase
1. **Semantic Relevance Scoring**: DUG及び実行結果を元にseedの評価値を計算する.
2. **Seed Scheduling**: 評価値の高いseedを選択し,変異回数を決定する.
3. **Selective Coverage Measurement**: プログラムを実行し,計装した関数のみからカバレッジを取得する.
## 5. Components in Detail
### [Thin Slicing[PLDI'07]](https://dl.acm.org/doi/10.1145/1250734.1250748)
> Simply stated, a thin slice contains all statements flowing values to the seed(i.e. statement of interest), ignoring uses of base pointers - [Thin Slicing[PLDI'07]](https://dl.acm.org/doi/10.1145/1250734.1250748)
DAFLはDUGの構築時に*thin slicing*と呼ばれる技術を用いている. Slicingとは,プログラム内のコードに対し,影響を与え得る全てのコード位置(slice)を解析する技術のことである. そして[Thin Slicing[PLDI'07]](https://dl.acm.org/doi/10.1145/1250734.1250748)は,ポインターの解決(pointer dereference)を行うコードをsliceに含めない.なぜなら,データのポインターを取り,その解決を行う動作はプログラム内に無数に存在するが,それ自体がデータを直接変更することはないからだ.
例)
```c
1 x = f();
2 y = g();
3 p = &y;
4 z = x + *p;
```
上記のサンプルについて,slicingによって変数`z`に影響を与え得るコード(行番号)を特定しようと考えてみる. 通常のslicingは {1,2,3} を結果として出力する. しかし,3行目の文は変数`y`の参照を取るのみで実際に値のコピー処理を行っているのは1,2行目の文である. Thin Slicingは結果としては冗長な3行目を除き, {1,2} を出力する.
DAFLはsliceを元に計装を行うため,thin slicingの技術は必要な計装を減らすことに貢献する.
ただし,thin slicingが出力結果にポインターの解決に関する部分を含めなかったとしても,どのポインタがどの変数を指し示しているのかといった情報自体は,変数がどこで定義され,(時にポインタを介して)どこで使用され得るのかといったことを理解するために必要である. そこでDAFLは,flow-insensitve かつ context-insensitiveなポインタ解析によってデータの依存関係を導出している.
#### DUG and relevant functions
CFGを,ノード集合: $\mathbb C$及びcontrol flow edgesの集合: $(\rightarrow): \subseteq \mathbb C \times \mathbb C$のペア: $(\mathbb C, \rightarrow)$ によって表す. 到達目標箇所を $t \in \mathbb C$ とした時,DGFは $t$ に辿り着くような入力を生成しようとする. プログラム $P$ 全体のDUGは,CFGと同じノード集合 $\mathbb C$ の要素を,data dependency edges: $\hookrightarrow$ で結ぶことで表される: $(\mathbb C, \hookrightarrow)$. Thin slicingの技術を踏まえてDAFLがDUGを構築する.ある2つのノード $c_1, c_2 \in \mathbb C$ を結ぶ data dependency edge $\hookrightarrow$ は,
$$
\begin{aligned}
c_1 \hookrightarrow c_2 \Leftrightarrow c_1 & \rightarrow^+ c_2 \land x \text{ is defined at } c_1 \quad \land \\
& x \text{ is used at } c_2, \text{ but not for pointer dereference} \quad \land \\
& x \text{ is not defined at any node between } c_1 \text{ and } c_2, \\
\end{aligned}
$$
のように定義される.
到達目標 $t$ についてスライスされたDUG: G = $(\mathbb C_t, \hookrightarrow_t)$ は,
$$
\begin{aligned}
\mathbb C_t &= \{c \in \mathbb C| c \hookrightarrow^+ t\} \\
(\hookrightarrow_t) &= \{(c_1, c_2)| c_1 \in \mathbb C_t \land c_2 \in \mathbb C_t \land c_1 \hookrightarrow c_2\}
\end{aligned}
$$
のように表される.
最後に得られたsliceから,計装対象の関数の集合 $F$ を,
$$F = \{f | f \text{ is the function that contains } c \land c \in \mathbb C_t\}$$
のように決定する.
### Seed Scheduling
#### Semantic Relevance Score
DUGノードに付与されるsemantic relevance score: $\rm Score_{G,t}(c)$は,以下の式で表される.
$$\rm Score_{G,t}(c) = L - |c-t| + 1$$
ただし, $L$ はDUGの最長路長さ, $|c-t|$ は目標ノードまでの距離を表している.また,実行されたノードの総数をseedの評価: $\rm Score_{G,t}(s) = \sum_{c\in\mathbb C}\rm Score_{G,t}(c)$ に加味するために,式の最小値が $1$ となるように平行移動させている.
#### Seed Pool Management
- 変異前の入力(seed)の管理を行う構造体をseed poolと呼ぶ.
- DAFLのseed poolは循環キューで実装されている.
- 新たにseedが追加されるたびに,seed poolがsemantic relevance scoreでソートされる.
#### Energy Assignment
DAFLにおいて,選択したseedの変異回数は以下のように計算される.
$$E_{DAFL}(s) = \frac{scr_s}{scr_{avg}} * E_{AFL}(s)$$
ただし,
- $scr_s$ は seed $s$の評価値
- $scr_{avg}$ は poolにあるseedの評価値の平均
- $E_{AFL}(s)$ は AFLの元々の実装が割り当てた変異回数
#### Implementation
DAFLは静的解析器の[SPARROW](https://github.com/ropas/sparrow),及びFuzzerの[AFL](https://github.com/google/AFL)を拡張する形で実装された.
ソースコードは[公開済](https://github.com/prosyslab/DAFL-artifact).
## 6. Evaluation
- **RQ1.** DAFLがバグを再現するのにどのくらい時間がかかるのか.
- **RQ2.** DAFLの性能に対するThin Slicingの影響
- **RQ3.** Selective Coverage Instrumentation & Semantic Relevance Scoringの誘導性能への影響
### Benchmark
- いくつかのCプログラム(binutils, libxml2, libjpegなど)から41個のCVEを対象とした. これらのCVEはBeaconのベンチマークでも使用されたものである.
- 脆弱性の種類としては,buffer overflow(BOF), null dereference(ND), stack overflow(SO), use-after-free(UAF), integer overflowが存在する.
### Experimental Setup
- 比較対象: AFL、AFLGo、WindRanger、Beacon
- 対象プログラムをASANを起動させて実行.ただしBeaconはbinary compiled with ASANに非対応のため別で追加実験.
- Fuzzingの実行時間と繰り返し: $24 \text{ hours }\times 40 \text{ times}$ (中央値で評価)
- 評価指標: 静的解析とFuzzingの両方にかかった時間 (Time-to-Exposure or TTE)
### Evaluation Criteria
CVEをDGFによって再現するにあたって,target location(どこでバグが発生するか)の特定が必要となる. PoCが与えられたものとして,ASANを起動したプログラムでPoCを走らせてcrashさせることで,stack traceを取得し,target locationを特定した.
DGFが同じバグを再現したかどうかは,以下の基準によって判断した:
- Same crash type and crash line to those of PoC.
- For a crash location with multiple bugs, additionally checked if the caller of the crash line matches.
- For stack overflow cases (i.e. infinite recursion), checked if all the functions in the stack trace of PoC are included DGF's crashing input.
### Result
Table 2 は各DGFがそれぞれのバグの再現に要した時間の中央値を並べている.
Fuzzingおよび事前の静的解析を含めた全ての実行時間(Time-to-Exposure or TTE)を $T_{f+sa}$ と表記する. 単位は秒である. Fuzzingに絞った場合は $T_f$ と表す. $T_{f+sa} > 24 \text{hours}$ の場合にタイムアウトとみなし,40回の試行の内20回以上でタイムアウトした場合は $\text{N.A.}(n)$ と表記する.ただし $n$ は再現に成功した試行回数である.
> Table 2: Crash reproduction results of DAFL and the baseline tools. Tf denotes the time purely spent in the fuzzing process. Tf+sa is the total time spent, considering both static analysis and fuzzing. Note that we only report Tf for WindRanger as its static analysis time is negligible. Each reported number is a median over 40 repeated experiments. N.A. indicates that the tool could not produce a median TTE, which means that it was not able to reproduce the bug for more than half of the repeated experiments. The parentheses denote how many times the fuzzer was able to reproduce the bug. Unlike TTE, this number is better when bigger. For each target (i.e., each row), the best result is marked with bold font and an asterisk. # Best perf. denotes the number of targets for which the tool has the best performance among all the other tools.
| Program | CVE | AFL Tf | AFLGo | | WindRanger | DAFL | | Without ASAN | |
|---------|-----|--------|--------|------------|------------|------|------------|-----------|-----------|
|| | | Tf | Tf+sa | Tf | Tf | Tf+sa | Beacon Tf+sa | DAFL Tf+sa |
| swftophp | 2016-9827 | 71 | 67 | 409 | 66 | 54 | *61 | 1,925 | *308 |
| swftophp | 2016-9829 | 272 | 188 | 519 | 5,304 | 144 | *151 | N.A.(16) | *485 |
| swftophp | 2016-9831 | 361 | 326 | 663 | 46,920 | 136 | *143 | 208 | *117 |
| swftophp | 2017-9928 | 1,920 | 1,834 | 2,168 | 1,828 | 1,741 | *1,748 | 1,371 | *768 |
| swftophp | 2017-11728 | 1,536 | 1,304 | 1,649 | 1,758 | 267 | *274 | *32,402 | N.A.(13) |
| swftophp | 2017-11729 | 507 | 333 | 678 | 661 | 126 | *133 | 3,396 | *370 |
| swftophp | 2017-7578 | 283 | 298 | 636 | N.A.(17) | 132 | *139 | 1,058 | *361 |
| swftophp | 2018-7868 | N.A. (0) | - | N.A. (0) | N.A. (1) | - | *N.A.(13) | N.A. (3) | *N.A.(20) |
| swftophp | 2018-8807 | N.A. (0) | - | N.A. (0) | N.A. (0) | - | *N.A. (1) | N.A. (0) | *N.A. (1) |
| swftophp | 2018-8962 | N.A. (0) | - | N.A. (0) | N.A. (0) | - | *N.A. (4) | N.A. (0) | *N.A. (3) |
| swftophp | 2018-11095 | 3,362 | 2,662 | 3,009 | 776 | 598 | *606 | 10,977 | *565 |
| swftophp | 2018-11225 | 40,725 | - | N.A.(13) | N.A.(16) | 17,772 | *17,780 | N.A.(16) | *38,277 |
| swftophp | 2018-11226 | 65,439 | - | N.A.(13) | N.A.(18) | 16,445 | *16,453 | N.A.(14) | *N.A.(19) |
| swftophp | 2018-20427 | *4,918 | 4,853 | 5,202 | 8,070 | 12,893 | 12,901 | *3,595 | 7,109 |
| swftophp | 2019-9114 | 33,240 | - | N.A.(19) | *17,696 | 37,135 | 37,142 | 34,817 | *31,576 |
| swftophp | 2019-12982 | N.A.(20) | 46,907 | 47,256 | N.A. (5) | 5,427 | *5,435 | N.A. (1) | *N.A. (8) |
| swftophp | 2020-6628 | 62,171 | - | N.A.(11) | N.A.(12) | 14,646 | *14,654 | N.A.(15) | *46,601 |
| lrzip | 2017-8846 | N.A. (0) | - | N.A. (0) | N.A. (0) | - | N.A. (0) | N.A. (0) | *N.A. (8) |
| lrzip | 2018-11496 | 11 | 12 | 185 | 11 | 13 | 17 | N.A. (0) | *7 |
| cxxfilt | 2016-4487 | 560 | 571 | 776 | 461 | 257 | *273 | 2,771 | *71 |
| cxxfilt | 2016-4489 | 1,105 | 1,181 | 1,384 | *310 | 868 | 885 | 4,902 | *207 |
| cxxfilt | 2016-4490 | 269 | 255 | 460 | 148 | 56 | *72 | 3,977 | *30 |
| cxxfilt | 2016-4491 | N.A. (2) | - | N.A. (4) | N.A. (1) | - | *N.A. (6) | N.A. (0) | *N.A.(15) |
| cxxfilt | 2016-4492 | 1,463 | 3,118 | 3,326 | 3,265 | 735 | *752 | 4,807 | *181 |
| cxxfilt | 2016-6131 | N.A. (0) | - | N.A. (0) | N.A. (0) | - | N.A. (0) | N.A. (0) | *N.A. (1) |
| objcopy | 2017-8393 | 1,425 | 1,399 | 3,054 | 1,311 | 458 | *630 | N.A. (3) | *N.A. (6) |
| objcopy | 2017-8394 | 826 | 878 | 2,525 | 916 | 292 | *484 | 4,789 | *240 |
| objcopy | 2017-8395 | *115 | 105 | 1,770 | 108 | 10 | 262 | 4,607 | *254 |
| objdump | 2017-8392 | *277 | 325 | 2,141 | N.A. (4) | 39 | 294 | N.A. (6) | *41,806 |
| objdump | 2017-8396 | N.A. (4) | - | N.A. (4) | N.A. (1) | - | N.A. (0) | N.A. (4) | N.A. (7) |
| objdump | 2017-8397 | 24,835 | 28,607 | 30,403 | N.A. (2) | 18,699 | *18,960 | N.A. (3) | *N.A.(13) |
| objdump | 2017-8398 | 1,857 | 2,620 | 4,426 | *1,006 | 1,640 | 2,068 | N.A. (0) | N.A. (0) |
| objdump | 2018-17360 | N.A. (2) | - | N.A. (0) | N.A. (3) | - | *N.A. (6) | N.A. (6) | N.A. (6) |
| strip | 2017-7303 | *122 | 125 | 3,691 | 1,758 | 156 | 214 | 3,913 | *112 |
| nm | 2017-14940 | *19,582 | 30,009 | 33,443 | N.A.(16) | - | N.A. (6) | N.A. (0) | *N.A. (5) |
| readelf | 2017-16828 | 221 | 192 | 729 | *44 | 239 | 254 | N.A.(15) | *64,516 |
| xmllint | 2017-5969 | *320 | 395 | 2,558 | 587 | 172 | 1,159 | 1,099 | *1,015 |
| xmllint | 2017-9047 | N.A.(19) | - | N.A.(14) | N.A. (8) | 26,558 | *33,647 | *25,388 | 27,977 |
| xmllint | 2017-9048 | N.A. (2) | - | N.A. (7) | N.A. (0) | 6,739 | *7,722 | *N.A. (4) | N.A. (0) |
| cjpeg | 2018-14498 | N.A.(16) | - | N.A.(12) | N.A. (0) | 16,940 | *16,943 | N.A. (0) | N.A. (0) |
| cjpeg | 2020-13790 | N.A. (6) | - | N.A. (3) | N.A. (0) | - | *N.A.(10) | N.A. (0) | N.A. (0) |
| #Best perf. | | 6 | 0 | | 4 | | *27 | 4 | *32 |
- DAFL(提案手法)はwith ASANの実験において27/41のケースで最短の実行時間または最多の試行回数でバグを再現.
- DAFLはwithout ASANの実験において32/41のケースで(Beaconと比較してより速い実行時間または多くの試行回数で)バグを再現した.
- Beaconはしばしば静的解析(Weakest Preconditionの計算)に時間をとられて結果を落としていた.(especially cases of cxxfilt, according to the paper)
その他の実験
- Thin Slicing
- Thin Slicingを使用したDAFLは通常のSlicingのそれと比較して2.01倍速い.
- Ablation
- Selective Coverage Intrumentationのみ: AFLより1.73倍速い
- Semantic Relevance Scoringのみ: AFLより1.39倍速い
- 両方を組み合わせた場合：AFLより1.93倍速い
## 7. Limitations and Future Work
1. 現在の実装はCプログラムのみをサポートしている.
- Javaなどのオブジェクト指向言語への拡張の可能性.
2. 関数間の制御依存関係の捕捉に限界があるため,一部のケースでパフォーマンスが低下.
- 例：CVE-2018-20427では,複雑な制御フローのため関連する関数を見逃した.
3. 潜在的な拡張:
- 複数の到達目標を同時に追う.
- 関数間解析を改善し,より多くの関連関数を捕捉.
- 他のプログラム解析やテストにこのアプローチを適用.
#### The case study of CVE-2018-20427
DAFLは関数同士のcontrol flow dependencyを計算できないという課題がある. このことを以下の例で確認する.
下のFigure 6 はDAFLが他のDGFと比べて最もパフォーマンスの低かったケースの一つである,swftophpのCVE2018-20427に関するコードを示している. Target Locationは29行目の`getInt(idx)`に存在する.
```c
1 int stack[100];
2 int stack_pointer = 0;
3
4 void push(int* idx){
5 stack[stack_pointer++] = *idx;
6 }
7
8 int* pop(){
9 int idx = stack[--stack_pointer];
10 return idx;
11 }
12
13 int decompileAction(int n, SWF_ACTION *actions){
14 switch(actions[n].ActionCode){
15 ...
16 case SWFACTION_GETPROPERTY:
17 decompileGETPROPERTY(n, actions);
18 break;
19 case SWFACTION_PUSH:
20 int* data = actions[n].data;
21 push(data);
22 break;
23 ...
24 }
25 }
26
27 int decompileGETPROPERTY(int n, SWF_ACTION *actions){
28 int idx = pop();
29 getInt(idx); // Crashing function
30 }
```
Figure 6: Simplified code snippet relevant to CVE-2018-20427.
Target locationを含む関数`decompileGETPROPERTY`を眺めると,`pop`が呼び出されていることから,この関数を呼び出す前に`push`が呼び出される必要があることが直感的に分かる.そして`decompileGETPROPERTY`と`push`の二つを呼び出しているのは`decompileAction`内のswitch文である.したがって`decompileAction`に対して, target locationが強いcontrol-flow dependencyを持つことが分かる.しかし, DAFLはdata flow dependencyしか追跡しないため,この重要な関数を計装できず,非常に低いパフォーマンスを出してしまうのである.
Sign in with Wallet
Connect another wallet