ClangのSanitizerCoverageで手軽にコード挿入(Code Instrumentation)する

[Aptpod Advent Calendar](https://qiita.com/advent-calendar/2018/aptpod) 4日目です。

本日の担当は、エンベデッドチームの矢部です。組み込みSW開発をメインでやっています。
昨今は組み込みといっても、様々な言語を利用するシーンが増えてきましたが、まだまだC/C++が主流です。
ということで、今日はLLVM/Clangを利用してC/C++でCode Instrumentationする方法を簡単に紹介します。

# はじめに
## Code Instrumentation とは？
ソースやバイナリに対して、パフォーマンス計測やエラー診断、トレースなどのためにコードを埋め込むテクニックのことを、Instrumentationと呼びます[^1]。
[^1]: https://en.wikipedia.org/wiki/Instrumentation_(computer_programming)
実現手段がソースコードの挿入である場合は、Code Instrumentationと表現されるようです。
ちなみにCode injectionという表現で検索するとインジェクション攻撃がまず出てきます。ここでやっていることもCode injectionではあると思いますが、きな臭い感じがするのでこの表現はやめました。

## 環境
今回は、以下のような環境で行いました。

* Ubuntu 18.04.1 LTS
* Clang 7.0.0

# 実現方法
利用するのはLLVM/Clangがもつ機能の一つ、**Sanitizer Coverage**です。
https://clang.llvm.org/docs/SanitizerCoverage.html

これはClangでカバレッジ計測をするための機能ですが、計測のために埋め込んだコードを利用して、ユーザが定義した関数を呼び出すことができます。
今回はその中のうち、以下について紹介いたします。

| 種別       | 概要 |
|:-----------------|:------------------|
| Tracing PCs | ソースコードのすべてのエッジに対してコードを埋め込む |
| Tracing PCs with guards  | 基本はTracing PCsと同じだが、各エッジが変数を持つ点が異なる
| Tracing data flow | 値の比較やswitch、除算、配列アクセスが行われる部分に対してコードを埋め込む |

Tracing PCs は設定によっては埋め込み対象がエッジではなくコードブロックや関数エントリになりますが、これについては後述します。

# デモ
SanitizerCoverageのドキュメントに書かれているサンプルコードをベースに進めます。

## Tracing PCs
Tracing PCsでは`__sanitizer_cov_trace_pc()`が各エッジに埋め込まれます。

### ソースコード

```c++:trace-pc-sample.cpp
void foo() {
}

int main(int argc, char* argv[]) {
    if (argc > 1) {
        foo();
    }
    return 0;
}
```
```c++:trace-pc-cb.cpp
#include <stdint.h>
#include <stdio.h>
#include <sanitizer/coverage_interface.h>

extern "C" void __sanitizer_cov_trace_pc() {
    void *PC = __builtin_return_address(0);
    char PcDescr[1024];
    __sanitizer_symbolize_pc(PC, "%p %F %L", PcDescr, sizeof(PcDescr));
    printf("trace: PC %s\n", PcDescr);
}
```
### 実行
```console
$ clang++ -g -fsanitize-coverage=trace-pc trace-pc-sample.cpp -c
$ clang++ trace-pc-cb.cpp trace-pc-sample.o -fsanitize=address
```
※`-fsanitize=address`は`__sanitizer_symbolize_pc`を呼ぶためのもの

```shell-session
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out
trace: PC 0x4f4b13 in main trace-pc-sample.cpp:6
trace: PC 0x4f4b37 in main trace-pc-sample.cpp:7:9
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out with-foo
trace: PC 0x4f4b13 in main trace-pc-sample.cpp:6
trace: PC 0x4f4b41 in main trace-pc-sample.cpp:8:9
trace: PC 0x4f4af8 in foo() trace-pc-sample.cpp:3
```

### 埋め込み位置に関するオプション
コードの埋め込み位置は、以下のようなオプションで設定が可能です。

- `edge`(default): 全エッジが対象
- `bb`: コードブロックが対象
- `func`: 関数エントリが対象

上記と併用するオプションとして、以下があります。

- `indirect-calls`: 間接呼び出し(関数ポインタ経由)に対してコードを埋め込む
- `no-prune`: edge/bbでは余剰として刈り取られるエッジ(ブロック)があり、この設定を併用すると刈り取り(pruning)が無効になる

以下で、edge以外の設定でどのように検出結果が変わるかを見てみます。

- `bb`の場合、if文の中に入らない場合の出力が減る。

```shell-session
$ clang++ -g -fsanitize-coverage=bb,trace-pc trace-pc-sample.cpp -c
$ clang++ trace-pc-cb.cpp trace-pc-sample.o -fsanitize=address
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out
trace: PC 0x4f4b13 in main trace-pc-sample.cpp:6
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out with-foo
trace: PC 0x4f4b13 in main trace-pc-sample.cpp:6
trace: PC 0x4f4b37 in main trace-pc-sample.cpp:8:9
trace: PC 0x4f4af8 in foo() trace-pc-sample.cpp:3
```
- `func`の場合、エントリポイントのみの表示。

```shell-session
$ clang++ -g -fsanitize-coverage=func,trace-pc trace-pc-sample.cpp -c
$ clang++ trace-pc-cb.cpp trace-pc-sample.o -fsanitize=address
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out
trace: PC 0x4f4b13 in main trace-pc-sample.cpp:6
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out with-foo
trace: PC 0x4f4b13 in main trace-pc-sample.cpp:6
trace: PC 0x4f4af8 in foo() trace-pc-sample.cpp:3
```
- `no-prune`を追加すると、main関数のreturn文が追加される。

```shell-session
$ clang++ -g -fsanitize-coverage=edge,no-prune,trace-pc trace-pc-sample.cpp -c
$ clang++ trace-pc-cb.cpp trace-pc-sample.o -fsanitize=address
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out
trace: PC 0x4f4b13 in main trace-pc-sample.cpp:6
trace: PC 0x4f4b37 in main trace-pc-sample.cpp:7:9
trace: PC 0x4f4b4b in main trace-pc-sample.cpp:10:5
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out with-foo
trace: PC 0x4f4b13 in main trace-pc-sample.cpp:6
trace: PC 0x4f4b41 in main trace-pc-sample.cpp:8:9
trace: PC 0x4f4af8 in foo() trace-pc-sample.cpp:3
trace: PC 0x4f4b4b in main trace-pc-sample.cpp:10:5
```
この例では分かりづらいですが、`no-prune`を指定すると埋め込み位置がかなり増えます。

- `indirect-calls`を設定すると、`__sanitizer_cov_trace_pc_indir(void *callee)`が間接呼び出し位置に追加される。

サンプルコードを変更して実行してみます。

```c++:trace-pc-indir-sample.cpp
void foo() {
}

void bar(void (*fn)(void)) {
    fn();
}

int main(int argc, char* argv[]) {
    bar(&foo);
    return 0;
}
```
```c++:trace-pc-indir-cb.cpp
#include <stdint.h>
#include <stdio.h>
#include <sanitizer/coverage_interface.h>

extern "C" void __sanitizer_cov_trace_pc() {
    void *PC = __builtin_return_address(0);
    char PcDescr[1024];
    __sanitizer_symbolize_pc(PC, "%p %F %L", PcDescr, sizeof(PcDescr));
    printf("trace: PC %s\n", PcDescr);
}

extern "C" void  __sanitizer_cov_trace_pc_indir(void *callee) {
    void *PC = __builtin_return_address(0);
    char PcDescr[1024];
    __sanitizer_symbolize_pc(PC, "%p %F %L", PcDescr, sizeof(PcDescr));
    printf("indirect: PC %s (callee 0x%lx)\n", PcDescr, (unsigned long)callee);
}
```
```
$ clang++ -g -fsanitize-coverage=trace-pc,indirect-calls trace-pc-indir-sample.cpp -c
$ clang++ trace-pc-indir-cb.cpp trace-pc-indir-sample.o -fsanitize=address
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out with-bar
trace: PC 0x4f4d13 in main trace-pc-indir-sample.cpp:10
trace: PC 0x4f4cd0 in bar(void (*)()) trace-pc-indir-sample.cpp:6
indirect: PC 0x4f4ce8 in bar(void (*)()) trace-pc-indir-sample.cpp:7:5 (callee 0x4f4cb0)
trace: PC 0x4f4cb8 in foo() trace-pc-indir-sample.cpp:3
```
関数ポインタ経由で呼び出しを行っている箇所にコードが埋め込まれています。

#### エッジとブロックの違い
例えば以下のようなコードがあった場合

```
void foo(int *a) {
    if (a)
        *a = 0;
}
```
コードブロックとしては

- foo entry
- `*a = 0;`の部分
- foo exit

となりますが、コードブロックだけでカバレッジを見た場合、`if(a)`にマッチしないケースが実行されたかどうかがわかりません。
そこでエッジ埋め込みでは、ダミーブロックを生成してそこにコードを埋め込むことで、上記のようなケースでも検出することを可能にしています。
https://clang.llvm.org/docs/SanitizerCoverage.html#edge-coverage

## Tracing PCs with guards
Tracing PCs with guardsは、基本的にTracing PCsと同じですが、各エッジに専用の変数が与えられる点が異なります。
デフォルト実装では、この変数を同一エッジ呼び出しを防ぐために使用しているため、ガード変数と呼んでいるのだと思います。
この変数は、初期化時(`__sanitizer_cov_trace_pc_guard_init`)および呼び出し時(`__sanitizer_cov_trace_pc_guard`)にポインタ引数で渡されます。

### ソースコード
```c++:trace-pc-guard-sample.cpp
#include <stdio.h>

void bar(int arg) {
    printf("%d\n", arg);
}

void foo() {
    for(int i=0; i<3; ++i) {
        bar(i);
    }
}

int main(int argc, char* argv[]) {
    if (argc > 1) {
        foo();
    }
    return 0;
}
```
```c++:trace-pc-guard-cb.cpp
#include <stdint.h>
#include <stdio.h>
#include <sanitizer/coverage_interface.h>

extern "C" void __sanitizer_cov_trace_pc_guard_init(uint32_t *start,
                                                    uint32_t *stop) {
    if (start == stop || *start) return;  // Initialize only once.
    printf("INIT: %p %p\n", start, stop);
}

extern "C" void __sanitizer_cov_trace_pc_guard(uint32_t *guard) {
    void *PC = __builtin_return_address(0);
    char PcDescr[1024];
    __sanitizer_symbolize_pc(PC, "%p %F %L", PcDescr, sizeof(PcDescr));
    printf("guard: %p %x PC %s\n", guard, *guard, PcDescr);
}
```
### 実行
```shell-session
$ clang++ -g -fsanitize-coverage=trace-pc-guard trace-pc-guard-sample.cpp -c
$ clang++ trace-pc-guard-cb.cpp trace-pc-guard-sample.o -fsanitize=address
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out -with-foo
INIT: 0x72ac10 0x72ac2c
guard: 0x72ac20 1 PC 0x4f4d40 in main trace-pc-guard-sample.cpp:13
guard: 0x72ac28 1 PC 0x4f4d90 in main trace-pc-guard-sample.cpp:15:9
guard: 0x72ac14 1 PC 0x4f4cc6 in foo() trace-pc-guard-sample.cpp:7
guard: 0x72ac10 1 PC 0x4f4c8c in bar(int) trace-pc-guard-sample.cpp:3
0
guard: 0x72ac18 1 PC 0x4f4cf5 in foo() trace-pc-guard-sample.cpp:8:23
guard: 0x72ac10 1 PC 0x4f4c8c in bar(int) trace-pc-guard-sample.cpp:3
1
guard: 0x72ac18 1 PC 0x4f4cf5 in foo() trace-pc-guard-sample.cpp:8:23
guard: 0x72ac10 1 PC 0x4f4c8c in bar(int) trace-pc-guard-sample.cpp:3
2
guard: 0x72ac18 1 PC 0x4f4cf5 in foo() trace-pc-guard-sample.cpp:8:23
guard: 0x72ac1c 1 PC 0x4f4d19 in foo() trace-pc-guard-sample.cpp:11:1
```
とくに何もやっていないので、ループ分だけトレースログが出ています。

### with guardっぽくする
このままではTracing PCsと変わらないので、callback側のコードを少し修正します。

```diff
@@ -7,9 +7,14 @@
                                                     uint32_t *stop) {
     if (start == stop || *start) return;  // Initialize only once.
     printf("INIT: %p %p\n", start, stop);
+    for (uint32_t *x = start; x < stop; x++) {
+        *x = 1;  // Guards should start from 1.
+    }
 }
 
 extern "C" void __sanitizer_cov_trace_pc_guard(uint32_t *guard) {
+    if (!*guard) return;  // Duplicate the guard check.
+    *guard = 0;
     void *PC = __builtin_return_address(0);
     char PcDescr[1024];
     __sanitizer_symbolize_pc(PC, "%p %F %L", PcDescr, sizeof(PcDescr));
```
```shell-session
$ clang++ trace-pc-guard-cb.cpp trace-pc-guard-sample.o -fsanitize=address
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out -with-foo
INIT: 0x72ac10 0x72ac2c
guard: 0x72ac20 0 PC 0x4f4df0 in main trace-pc-guard-sample.cpp:13
guard: 0x72ac28 0 PC 0x4f4e40 in main trace-pc-guard-sample.cpp:15:9
guard: 0x72ac14 0 PC 0x4f4d76 in foo() trace-pc-guard-sample.cpp:7
guard: 0x72ac10 0 PC 0x4f4d3c in bar(int) trace-pc-guard-sample.cpp:3
0
guard: 0x72ac18 0 PC 0x4f4da5 in foo() trace-pc-guard-sample.cpp:8:23
1
2
guard: 0x72ac1c 0 PC 0x4f4dc9 in foo() trace-pc-guard-sample.cpp:11:1
```
guardチェックに引っかかるようになり、一度通ったパスだと表示されなくなりました。

## Tracing data flow
Tracing data flowを利用すると、いくつかのシチュエーションにおいて、利用された値を取得することができます。具体的な設定内容は、以下の通りです。

- `trace-cmp`: 値の比較やswitch文が対象
- `trace-div`: 除算が対象。ただし取れるのは除数のみ。
- `trace-gep`: 変数によって配列インデックスを指定した場合、その値が取れる

これらの設定は併用することで、同時に有効にすることが可能です。

### ソースコード
トレースと違ってある程度処理がないと分かりづらいので、与えられた引数の数によって処理を変えるプログラムを用意しました。

```c++:trace-data-flow-sample.cpp
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
    int idx=1;
    switch(argc) {
    case 2:
        printf("%s\n", argv[idx]);
        break;
    case 3:
        int a = atoi(argv[idx]);
        int b = atoi(argv[++idx]);
        if (b == 0) {
            return -1;
        }

        int ret = a/b;
        printf("%d / %d = %d\n", a, b, ret);
        break;
    }
    return 0;
}
```
```c++:trace-data-flow-cb.cpp
#include <stdint.h>
#include <stdio.h>
#include <sanitizer/coverage_interface.h>

extern "C" void __sanitizer_cov_trace_pc() {}

extern "C" void __sanitizer_cov_trace_const_cmp4(uint32_t Arg1, uint32_t Arg2) {
    void *PC = __builtin_return_address(0);
    char PcDescr[1024];
    __sanitizer_symbolize_pc(PC, "%L", PcDescr, sizeof(PcDescr));
    printf("%s const cmp4: %u <-> %u\n", PcDescr, Arg1, Arg2);
}

extern "C" void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases) {
    void *PC = __builtin_return_address(0);
    char PcDescr[1024];
    __sanitizer_symbolize_pc(PC, "%L", PcDescr, sizeof(PcDescr));
    printf("%s switch: val %lu\n",PcDescr, Val);
}

extern "C" void __sanitizer_cov_trace_div4(uint32_t Val) {
    void *PC = __builtin_return_address(0);
    char PcDescr[1024];
    __sanitizer_symbolize_pc(PC, "%L", PcDescr, sizeof(PcDescr));
    printf("%s div4: val %u\n",PcDescr, Val);
}

extern "C" void __sanitizer_cov_trace_gep(uintptr_t Idx) {
    void *PC = __builtin_return_address(0);
    char PcDescr[1024];
    __sanitizer_symbolize_pc(PC, "%L", PcDescr, sizeof(PcDescr));
    printf("%s gep: index %lu\n",PcDescr, Idx);
}
```
### 実行
Tracing data flowで扱える全オプションを設定して実行します。なお、ここで`trace-pc`オプションを忘れるとInstrumentationが行われず、何も動きません。

```shell-session
$ clang++ -g -fsanitize-coverage=trace-pc,trace-cmp,trace-div,trace-gep trace-data-flow-sample.cpp -c
$ clang++ trace-data-flow-cb.cpp trace-data-flow-sample.o -fsanitize=address
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out foo
trace-data-flow-sample.cpp:6:5 switch: val 2
trace-data-flow-sample.cpp:8:24 gep: index 1
foo
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out 256 16
trace-data-flow-sample.cpp:6:5 switch: val 3
trace-data-flow-sample.cpp:11:22 gep: index 1
trace-data-flow-sample.cpp:12:22 gep: index 2
trace-data-flow-sample.cpp:13:15 const cmp4: 0 <-> 16
trace-data-flow-sample.cpp:17:20 div4: val 16
256 / 16 = 16
$ ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out 16 0
trace-data-flow-sample.cpp:6:5 switch: val 3
trace-data-flow-sample.cpp:11:22 gep: index 1
trace-data-flow-sample.cpp:12:22 gep: index 2
trace-data-flow-sample.cpp:13:15 const cmp4: 0 <-> 0
```

# おわりに
今回紹介した機能はgccでもある程度は実装されています。
また、LLVM/Clangには静的/動的解析に利用できる多種多様な機能があるため、世の中にあるツールでは物足りないという方は、ぜひ調べてみてください。

# 参考
- [Clang Documentation](https://clang.llvm.org/docs/index.html)
 - [SanitizerCoverage](https://clang.llvm.org/docs/SanitizerCoverage.html) 
- https://github.com/llvm-mirror/compiler-rt
 - `lib/sanitizer_common/sanitizer_coverage_libcdep_new.cc`にSanitizerCoverageのデフォルト実装[^2]があります

[^2]: https://bcain-llvm.readthedocs.io/projects/clang/en/latest/SanitizerCoverage/#default-implementation