1870件以上のカーネルの不具合修正に貢献した再現用プログラムを自動生成するsyzkallerのテスト自動化技術

# はじめに
この記事は [Linux Advent Calendar 2019](https://qiita.com/advent-calendar/2019/linux) の 23 日目の記事です。

## 自己紹介
こんにちは。[OSSセキュリティ技術の会](https://secureoss-sig.connpass.com/) の [fujiihda](https://twitter.com/fujiihda) です。これまで Linux カーネルを含む OSS に関連する技術調査、技術講演、開発、サポート等を経験してきました。最近では、技術コミュニティを設立する側や運営側に関わらせていただく機会も増えてきました。

## 本記事で扱うテーマ
カーネルのテスト自動化技術として Google の Dmitry Vyukov さんが開発し OSS として公開した syzkaller (読み方：シスコーラー [^１] ) というファジングツールについて解説します。2019 年 12 月時点では、<font color="Red">内部実装まで踏み込んで調査した日本語の記事は本記事が初</font>となるはずです。

なお、本記事の中身は [OSSセキュリティ技術の会 第七回勉強会](https://secureoss-sig.connpass.com/event/154716/) の前半の内容 [^2] とほぼ同じです。厳密には、ソースコード調査の結果として得られたノウハウは載せているものの、ソースコード自体には言及しないようにして、口頭補足していた説明や QA をほぼ全部載せにして記事にしました。

[^１]: z が濁音にならないのは、開発者がロシア出身の方だからだと思います。

[^2]: 当日の内容を [uchan_nos さん](https://twitter.com/uchan_nos) にメモにしていただきました。[ファジングツール syzkaller は何を検査するものなの？](http://uchan.hateblo.jp/entry/2019/12/13/230549) もあわせてご参照いただければと思います。[uchan_nos さん](https://twitter.com/uchan_nos) ありがとうございます！

## TL;DR
syzkaller は、テスト自動化にソースコードカバレッジを活用したハイブリッドアプローチを採用し、さらに従来であれば人が対応していた不具合修正に至るまでの一連の流れを自動化しました。その結果、リリースから <font color="Red">2</font> 年間が経過してカバレッジを <font color="Red">7</font> ％カバーした時点で、<font color="Red">1500</font> 件以上のカーネルの不具合修正に貢献した実績があります。

syzkaller では、自らが生成した複数の仮想マシンに対して問題の起きそうな入力を送り続けることで未発見の不具合を発見します。最小限の入力で不具合を再現させるための再試行を繰り返し、最終的には不具合を再現するための C 言語のプログラム生成を試みます。

syzkaller には、現在も機能が追加されており [^3]、いまこの瞬間にも不具合を発見し続けています。2019 年 12 月時点では <font color="Red">1870</font> 件以上のカーネルの不具合修正に貢献しています。最新状況は [https://syzkaller.appspot.com/upstream/fixed](https://syzkaller.appspot.com/upstream/fixed) を参照してください。

[^3]: syzkaller 側だけでなく、[カーネル側にも syzkaller に役立つ機能が追加](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=15ff2069cb7f967d) されています。セキュリティ・キャンプに参加できる年齢の方は、参加するとパッチ投稿者に会えるかもしれません。

# 本題

## まずは動かしてみた

動かしてみた結果は次のとおりです。なお、動作確認には手元にあったモバイル向けノートパソコン上で動作する仮想マシン [^4] を使用しました。

[^4]: なにを言いたいのかといいますと、大規模な物理サーバやベアメタルインスタンスなどに大量にお金を使わなくても十分に試せます。ただし、仮想化環境で試す際は、Nested virtualization の有効化が事実上ほぼ必須だと考えます。エミュレーションは私は試していません。

```
# ./bin/syz-manager -config=my.cfg
2019/06/05 03:53:20 loading corpus...
2019/06/05 03:53:20 serving http on http://127.0.0.1:56741
2019/06/05 03:53:20 serving rpc on tcp://[::]:37545
2019/06/05 03:53:20 booting test machines...
2019/06/05 03:53:20 wait for the connection from test machine...
2019/06/05 03:54:08 machine check:
2019/06/05 03:54:08 syscalls                : 1380/2699
2019/06/05 03:54:08 code coverage           : enabled
2019/06/05 03:54:08 comparison tracing      : CONFIG_KCOV_ENABLE_COMPARISONS is not enabled
2019/06/05 03:54:08 extra coverage          : extra coverage is not supported by the kernel
2019/06/05 03:54:08 setuid sandbox          : enabled
2019/06/05 03:54:08 namespace sandbox       : /proc/self/ns/user does not exist
2019/06/05 03:54:08 Android sandbox         : /sys/fs/selinux/policy does not exist
2019/06/05 03:54:08 fault injection         : CONFIG_FAULT_INJECTION is not enabled
2019/06/05 03:54:08 leak checking           : CONFIG_DEBUG_KMEMLEAK is not enabled
2019/06/05 03:54:08 net packet injection    : /dev/net/tun does not exist
2019/06/05 03:54:08 net device setup        : enabled
2019/06/05 03:54:08 corpus                  : 3844 (0 deleted)
2019/06/05 03:54:10 VMs 4, executed 0, cover 0, crashes 0, repro 0
2019/06/05 03:54:20 VMs 4, executed 36, cover 3836, crashes 0, repro 0
2019/06/05 03:54:30 VMs 4, executed 776, cover 20662, crashes 0, repro 0
(中略)
2019/06/05 04:10:00 VMs 4, executed 70734, cover 62967, crashes 0, repro 0
2019/06/05 04:10:05 vm-3: crash: no output from test machine
2019/06/05 04:10:10 VMs 3, executed 70918, cover 62967, crashes 1, repro 0
(中略)
2019/06/05 04:14:02 VMs 4, executed 87377, cover 63959, crashes 1, repro 0
2019/06/05 04:14:05 vm-2: crash: no output from test machine
2019/06/05 04:14:12 VMs 3, executed 87614, cover 63960, crashes 2, repro 0
(中略) 
2019/06/05 04:14:32 VMs 4, executed 87978, cover 63995, crashes 2, repro 0
2019/06/05 04:14:40 vm-3: crash: KASAN: use-after-free Read in blk_mq_free_rqs
2019/06/05 04:14:41 vm-1: running for 20m42.241115632s, restarting
2019/06/05 04:14:41 vm-0: running for 20m33.97704277s, restarting
2019/06/05 04:14:41 vm-2: running for 9.643775512s, restarting
2019/06/05 04:14:42 reproducing crash 'KASAN: use-after-free Read in blk_mq_free_rqs': 1158 programs, 4 VMs, timeouts [15s 1m0s 6m0s]
2019/06/05 04:14:42 VMs 0, executed 87978, cover 63995, crashes 3, repro 1
(以下略)
```

- 2019/06/05 03:53:20 頃に syzkaller を起動しています。
- 2019/06/05 04:10:05 および 2019/06/05 04:14:05 では、クラッシュ時に事象を取り逃しています。そういうことも多々あるようです。
- 2019/06/05 04:14:40 に不具合らしいものを発見しています。ここまで、起動からわずか 20 分程です。
- 2019/06/05 04:14:42 から事象の再現を試みています。

上記の結果、<font color="Red">syzkaller によって自動生成された再現用のプログラム</font>は次のとおりです。一応お伝えしておくと、この不具合は [既に修正されています](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=c3e2219216c92919a6bd1711f340f5faa98695e6)。

```c
// autogenerated by syzkaller (https://github.com/google/syzkaller)

#define _GNU_SOURCE

#include <endian.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/syscall.h>
#include <sys/types.h>
#include <unistd.h>

uint64_t r[1] = {0xffffffffffffffff};

int main(void)
{
    syscall(__NR_mmap, 0x20000000, 0x1000000, 3, 0x32, -1, 0);
    intptr_t res = 0;
    memcpy((void *)0x20000040, "/dev/loop-control\000", 18);
    res = syscall(__NR_openat, 0xffffffffffffff9c, 0x20000040, 0x181000, 0);
    if (res != -1)
        r[0] = res;
    syscall(__NR_ioctl, r[0], 0x4c81, 0);
    return 0;
}
```

上記の実行時に使用したコンフィグファイルは次のとおりです。

```
{
    "target": "linux/amd64",
    "http": "127.0.0.1:56741",
    "workdir": "/root/gopath/src/github.com/google/syzkaller/workdir",
    "kernel_obj": "/root/kernel",
    "image": "/root/wheezy.img",
    "sshkey": "/root/wheezy.img.key",
    "syzkaller": "/root/gopath/src/github.com/google/syzkaller",
    "procs": 8,
    "type": "qemu",
    "vm": {
        "count": 4,
        "kernel": "/root/kernel/arch/x86/boot/bzImage",
        "cpu": 4,
        "mem": 4096
    }
}
```

## なぜ syzkaller を調査してみたのか
なぜファジングを調べたのか、という質問に一言で回答するなら「面白そうだったから」です。細かく分けると、次のような理由になります。

- 日本語の情報が存在しなかったために、逆に興味を持った
- 最新技術が投入されているはずの仕組み、設計、実装に興味を持った
- 考え方や技術が他分野に転用できるかもしれないと期待した
- syzkaller を通じてカーネルのエンジニアとしてレベルアップしたかった
- Go 言語の勉強 (それまでほぼ読んだことがなかったため)

## ファジングと Linux のセキュリティ品質向上
ファジングは、未知の不具合や脆弱性の検出に適したテスト手法です。検査対象にランダムな入力データを送ることで意図的に例外を発生させます。ファジングがセキュリティ品質に与える影響は、世界で話題となっており、Open Source Summit Japan 2019 では、カーネルのリードメンテナの Greg Kroah-Hartman さんをはじめとする複数講演者がファジングの貢献に言及していました。

- 2017 年前後を境としてファジングをはじめとする自動化された高度なテスト技術が普及
- リリース前にセキュリティ脆弱性が修正されるようになり CVE の件数は減少傾向 [^5] 

ソフトウェア全体および Linux の CVE 件数の推移を図に示します。

<img width="500" alt="ソフトウェア全体および Linux の CVE 件数の推移" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519781/6d5cf0ec-fca5-8c12-b4ae-3c99f1f7bf1c.png">

[^5]: CVE の件数はあくまでも推移を測るための指標であり、CVE 件数 = 脆弱性の件数 ではありません。CVE 番号の付いていないセキュリティ脆弱性なんて、、、 うわなにをするやめr

## ファジング技術の肝
高度なファジングの肝となる技術のひとつに、検査対象で問題が起きそうな入力データを生成する仕組みがあります。この仕組みの高度化が発見困難な不具合の発見を可能にします。ファジングの入力データを生成する仕組みを私の独断と偏見で分類した結果は次のとおりで、syzkaller はレベル 4 に該当すると考えます。なお、ファジングのターゲットはネットワーク越し限定からそうでないものまで多岐に渡ります。

表：ファジングの入力データを生成する仕組みの分類

|レベル|仕組み|効率|網羅|備考|
|---|---|---|---|---|---|
|1  |プロトコル等を考慮しない完全なランダム|×  |○  |実際の入力とは程遠い入力パターンが生成される|
|2  |キャプチャしたパケットをテンプレートとしてその一部を改変|△  |×  |キャプチャした範囲内の入力パターンしか生成されない|
|3  |プロトコル仕様や問題の起きそうな入力パターンを人間が実装しておき活用|○  |○  |主要な商用ツールで採用されている手法|
|4  |レベル 3 に加えてソースコードのカバレッジを活用|◎  |○  |syzkaller が採用している手法で、入力を変異させるときの分岐条件にソースコードを活用する|

## syzkaller とは
Google の Dmitry Vyukov さんによって開発されたカーネルのファジングツールです。冒頭でも触れましたが、<font color="Red">2</font> 年間でカバレッジを <font color="Red">7</font> ％カバーした時点で、<font color="Red">1500</font> 件以上のカーネルの不具合修正に貢献した実績を持ちます。特徴は次のとおりです。

- ハイブリッドな仕組みにより効率良くシステムコールのシーケンスを生成
  - 試験対象プロトコル (システムコール) のテンプレートが実装されている
  - ソースコードのコンパイル時にコンパイラが出力するカバレッジを利用して入力を変える
- 不具合発見の一連の流れがほぼすべて自動化
  - 自らが生成した複数の試験対象の仮想マシンに対して問題の起きそうな入力を送り続けて、デバッグ支援機構を活用してその挙動を観測
  - 発見した不具合を最小限の入力で再現させるための再試行を自ら繰り返し、不具合を再現するための C 言語のプログラム生成を試みる

## syzkaller の構成図

丁度良い syzkaller の構成図がなかったので作成してみました。

<img width="500" alt="syzkaller の構成図" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519781/02a14bb4-98df-5608-e1f3-79362123af5a.png">

まずは、大まかな処理の流れだけ説明します。各コンポーネントの詳細は本記事の後半で説明します。

- ユーザはコマンドラインで manager を起動します。
- manager は ssh 経由で fuzzer のプロセスを立ち上げます。また、manager は試験対象となる VM の管理 (起動、監視、再起動) も行います。この VM は試験対象でもあることから、なにかあれば再起動されるため、いつ落ちてもおかしくない不安定な状態です。さらに、manager は workdir 配下のファイルの取得、作成、更新も行います。
- fuzzer は試験対象となる VM の内部に存在するプロセスで、syzkaller 起動時の引数で指定された任意の数の executor を起動します。
- executor は試験対象となる VM の内部に任意の数存在するプロセスで、fuzzer から syscalls のシーケンスを受け取り、ファジング対象のカーネルで syscalls のシーケンスを実行して結果を返します。

なお、一般的なアプリケーションの入力インターフェイスは API かもしれませんが、カーネルの入力インターフェイスはシステムコールです。システムコールは、ユーザ空間で動作するアプリケーションとカーネルを結ぶインターフェイスで、アプリケーションがカーネルの機能を安全に使用するために使用されます。ファイルをオープンする目的で使用される open() など、300 種類ほどのシステムコールとその引数の組合せで構成され、カーネルのファジングでは、何のシステムコールを選択し、どのような引数で、さらにはどのように組み合わせて、どの順番で送るかがポイントになります。

## (参考) Sanitizer とは

syzkaller のコンポーネントではないですが、syzkaller の動作を理解する上で不可欠であるため、Sanitizer を簡単に紹介します。Sanitizer は、カーネルに存在する複数のデバッグ支援機構です。

- 動的テストツール
- コンパイラの機能 (gcc および C 言語で利用可能)
- メモリを破壊したことや違反したことなどをはっきり示すもの
- 不具合を示してくれるのでファジングを補助してくれる
- エラーが起きたら、エラーの深刻度に関わらず、カーネルパニックを発生させる設定を使用する (コンソールにパニックメッセージを出力) [^6] 

[^6]: 厳密には warning などの文字列を syzkaller が検出し、カーネルパニック前に止めることもあります。

syzkaller が使用している Sanitizer の一例は次のとおりです。

- KASAN (Kernel Address Sanitizer)
  - メモリアクセスエラーを検出
- KMSAN (Kernel Memory Sanitizer)
  - 初期化されていない読み取りを検出
- KTSAN (Kernel Thread Sanitizer)
  - 異なるスレッド間のデータの競合状態を検出
- UBSAN (Undefined Behavior Sanitizer)
  - 未定義の動作を引き起こす機能の使用を検出

## (参考) KCOV (Kernel Code Coverage) とは

syzkaller のコンポーネントではないですが、KCOV (Kernel Code Coverage) を簡単に紹介します。これは、コンパイラ (gcc) によって提供される機能です。有効化すると左の図から右の図のようになります。性能劣化を伴います。試験対象のカーネルではこれを有効化する必要があります。

- カバレッジガイドファジングに適した形式でカーネルコードカバレッジ情報を生成
- 使い方：CONFIG_KCOV = y
- 条件：gcc 6.1.0 以降 (バージョン 231296 以降)

<img width="500" alt="KCOV 無効時と KCOV 有効時のイメージ" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519781/cccb2793-0c93-d985-15bc-5fdf99ca0f46.png">

## syz-manager

- 仮想化ホスト上に存在するプロセス
- 試験対象としての VMs の管理 (起動、監視、再起動)
  - この VMs はカーネルパニックのたびに再起動
- 試験対象としての VMs 内で syz-fuzzer プロセスを起動
- syz-fuzzer プロセスに指示を送る
- workdir 上のコーパスとクラッシュ (次節で説明) を更新

<img width="500" alt="syz-manager" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519781/8089e6d2-1db0-565e-18e1-7f9fe0d90ccd.png">

## workdir/crashes/* と workdir/corpus/*

- workdir/crashes/*
  - クラッシュに関わるアウトプット
  - アスタリスクにはハッシュ値が名前のフォルダが生成される
  - フォルダ内に次の情報を含む
     - description  事象を特定する件名
     - logN (N=0～99)  syzkaller のログ
     - reportN (N=0～99)  カーネルクラッシュレポート
     - repro.cprog  再現用の C 言語のプログラム
     - repro.log
     - repro.prog
     - repro.report
     - repro.stats
     - reproM (M=0～9)

- workdir/corpus/*
  - コーパスは、個別ファイルとして格納されているファズターゲットの入力セット
  - 理想的なコーパスは、最大限のコードカバレッジを提供する最小限の入力セット

<img width="500" alt="crashes と corpus" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519781/4f00528b-3d03-fd58-1456-002d405205b4.png">

## syz-fuzzer

- 先述の不安定な試験対象 VMs 内に存在するプロセス
- テストケース (入力) を生成、突然変異、最小化
- 任意の数の syz-executor プロセスを起動
- コーパスの有無で条件分岐して Generate 関数もしくは Mutate 関数のいずれかを呼び出すことでシステムコールのシーケンスを決める

<img width="500" alt="syz-fuzzer" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519781/6787538b-fc55-f4a5-5f16-9ae86f61bf8b.png">

## syz-executor

- 先述の不安定な試験対象 VMs 内に任意の個数存在するプロセス
- syz-fuzzer から syscalls のシーケンスを受け取る
- syscalls のシーケンスを実行する
- syscalls の実行結果を syz-fuzzer に送り返す
- 単一の executor プロセスのことを Proc とも呼ぶ (ソースコードを読むときに役立つ知識)
  - Proc がカーネルに送るデータは ProgData とも呼ぶ (ソースコードを読むときに役立つ知識)

<img width="500" alt="syz-executor" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/519781/31640399-e6a5-ad2a-97af-c47220a2a943.png">

# 最後に
本記事では syzkaller の全体像と大まかな機能を説明しました。なお、ソースコード調査から得られた細かいノウハウは割愛したため、細かいところまで見たい人は、[勉強会の資料](https://secureoss-sig.connpass.com/event/154716/) の 18 ページから 26 ページもあわせて参照してください。

# おまけの QA
Q1：syzkaller は、Linux 以外では、どのような環境に対応していますか。
A1：Akaros、Darwin/XNU、FreeBSD、Fuchsia、NetBSD、OpenBSD、Windows、gVisor などなど

Q2：カーネルではなく、ユーザ空間で動作するアプリケーションをファジングしたいんですけど。
A2：ClusterFuzz を使うと幸せになれるかもしれません。そして、試したら記事を書いて私に教えてくれると嬉しいです。

# お断りとお願い
本記事の掲載内容は個人の見解であり、所属する企業やコミュニティの立場、戦略、意見を代表するものではありません。また、この記事を読んで、ファジングしてみたいと思った場合は、次の点に注意し "必ず自己責任" で実施してください。

- 社内/学内のネットワークではやらないでください
- 社内/学内のマシンではやらないでください
- プライベート環境などの完全に隔離された環境で "自己責任"

本記事によって、製品リリース前の試験段階で見つかる不具合数が増加し、リリースされる製品の品質が少しでも向上することを願っています。