複数の仮想ページに同じ物理ページをマッピングする方法 (Linux)

小ネタ.

Linuxで複数の仮想ページを一つの物理ページにマッピングする方法です.

連続した仮想ページを全て同じ物理ページにマッピングしたいということがあって,原理的にはページテーブルで同じ領域を指すだけです.でもユーザ空間からはどうするんだっけ?と思ったらそういえばspectreのPOCでそんなことやっていたなと思い出したのでそれを参考に作ってみました.

#define _GNU_SOURCE

#include <assert.h>
#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

void *map(int num_pages) {
    int fd, pagesize = getpagesize();
    void *area;
    char *start, *end, *p, *q;
    size_t length = pagesize * num_pages;

    // reserve virtual address space
    area = mmap(NULL, length, PROT_NONE,
                MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0);
    assert(area != MAP_FAILED);
    assert(munmap(area, length) == 0);

    // create temp file whose size is a pagesize
    fd = open("/tmp", O_TMPFILE | O_RDWR, 0600);
    assert(fd != -1);
    assert(ftruncate(fd, pagesize) == 0);

    // mmap each virtual page to the same physical page
    start = area;
    end = start + length;
    for (p = start; p < end; p += pagesize) {
        q = mmap(p, pagesize, PROT_READ | PROT_WRITE | PROT_EXEC,
                 MAP_SHARED | MAP_FIXED | MAP_POPULATE | MAP_NORESERVE, fd, 0);
        assert(p == q);
    }
    assert(close(fd) == 0);

    return area;
}

仕組みとしてはサイズがページサイズのファイルをopen(ここではtempfileを作成)し,そのfdに対してmmapするだけです.mmapの第一引数で仮想アドレスが指定できます.

ここでは連続した仮想アドレスを同じページにmmapするということをしています. ここで問題となるのは,空いている仮想アドレス空間が確保できるかどうかという点です. ユーザが適当に仮想アドレスを決めた場合,すでにそのアドレスが使用されている可能性があります(mmapは失敗する).

そこでここでは最初に必要な仮想アドレス空間の領域をmmapしています. mmapの第一引数をNULLにすればOSが適当な領域を見つけてくれます. また,MAP_NORESERVE指定することで,物理ページの割り当てなしに領域の確保が可能です. 使用可能なアドレスが分かったら,その領域にmmapするために一旦unmapしてあとは先述の方法でmmapしていきます.

本当に同じアドレスにマッピングされているかは/proc/self/pagemapから確認できます(ちなみにproc/self/pagemapの参照にはCAP_SYS_ADMIN(root権限)が必要です).

static uintptr_t virt_to_phys(void *virt) {
    long pagesize = getpagesize();
    int fd = open("/proc/self/pagemap", O_RDONLY);
    assert(fd != -1);
    off_t ret =
        lseek(fd, (uintptr_t)virt / pagesize * sizeof(uintptr_t), SEEK_SET);
    assert(ret != -1);
    uintptr_t entry = 0;
    ssize_t rc = read(fd, &entry, sizeof(entry));
    assert(rc > 0);
    assert(entry != 0);
    assert(close(fd) == 0);

    return (entry & 0x7fffffffffffffULL) * pagesize +
           ((uintptr_t)virt) % pagesize;
}

int main() {
    int pagesize = getpagesize();
    int i, num_pages = 100;
    char *p = map(num_pages);

    for (i = 0; i < num_pages; i++, p += pagesize) {
        printf("%016llx, %016llx\n", (unsigned long long)p,
               (unsigned long long)virt_to_phys(p));
    }

    return 0;
}

実行結果

% sudo ./a.out
00007f6e950f7000, 0000000fe7773000
00007f6e950f8000, 0000000fe7773000
00007f6e950f9000, 0000000fe7773000
00007f6e950fa000, 0000000fe7773000
00007f6e950fb000, 0000000fe7773000
00007f6e950fc000, 0000000fe7773000
00007f6e950fd000, 0000000fe7773000
00007f6e950fe000, 0000000fe7773000
...

上記コードはここにあります.

American Fuzzy Lop (AFL)の構造

AFLとは

American Fuzzy Lop (AFL)はファジングツールの一つです.

ファジングとはプログラムの脆弱性検査手法の一つで,簡単に言ってしまえばあるプログラムをランダムな引数で実行することを繰り返して,プログラムがクラッシュするような入力を探そうという方法です. なんとも場当たり的な対応で心許ない気もしますが,実際には洗練されたアルゴリズムを利用することで一般に良く機能します.

世の中ファジングツールは数多く存在しますが,AFLはその利用の簡単さと,何よりも何百何千というバグを実際に見つけている運用実績で有名です. 最近は更新が止まっているようですが,AFLはコードが簡潔にまとまっており,AFLを参考に作られてたファジングツールも多く存在します.

AFLの技術的詳細はAFLの作者がtechnical_details.txtにまとめています. これを読むとAFLの概要は分かりますが,実際のコードに関する情報はあまりないように思うので,ここに簡単に書いてみます.

対象のAFLのバージョンは2.52bです. AFLはとりあえず実際に動かしてみた方が以下の文章の理解が進むと思います(とても簡単に利用できます).

ソースの概要

まず,AFLのソースディレクトリには,afl-xxx.cというファイルがありますが,特にメインになるのは,

  • afl-gcc.c, afl-as.c, afl-as.h
  • afl-fuzz.c

です.前者をファジング対象のプログラムのコンパイルに利用,後者を実際のファジングに利用します.

その他のものはAFLの補助ツールになります. 引数なしで実行すればそれぞれのツールのhelpが見れます. ここでは各ツールの詳細は省略して,上記の主処理部分をみていきます.

コンパイル処理 / カバレッジ計算

AFLはcoverage-based fuzzingあるいはgray-box fuzzingなどと呼ばれるファジング手法に分類されます. これは,ある入力でプログラムを実行したときのコードカバレッジを測定し,その情報を利用して次の入力を決定していく手法です.

AFLでは条件付分岐を区切りとしたコードのまとまり単位でカバレッジを計算します(branch coverage). このために,AFLはコンパイル時にカバレッジ計算のコードをプログラムに挿入します. 例えば,以下のようなプログラムがあった場合,

if (...) {
    ...
}
...

afl-gccコンパイルすると,以下のようになります.

__log_coverage()
if (...) {
    __log_coverage()
    ...
}
__log_coverage()
...

AFLはこのcode instrumentationを,アセンブラの段階でおこないます.

afl-gccgccの単純なラッパーで,アセンブラとしてafl-asを呼び出します. afl-asadd_instrumentation()で,出力されたアセンブリを行ごとに処理して,条件付ジャンプ命令 (jから始まる命令)の直後にカバレッジ計算のコードを挿入します. この辺り,構文解析している訳ではないので処理がかなりシンプルです.

カバレッジ計算のコードの本体は,afl-as.hで以下のように定義されています. このコードは,適当にレジスタの退避をして,rcxコンパイル時に生成した値を入れたあとに,__afl_maybe_logを呼び出します.

static const u8* trampoline_fmt_64 =

  "\n"
  "/* --- AFL TRAMPOLINE (64-BIT) --- */\n"
  "\n"
  ".align 4\n"
  "\n"
  "leaq -(128+24)(%%rsp), %%rsp\n"
  "movq %%rdx,  0(%%rsp)\n"
  "movq %%rcx,  8(%%rsp)\n"
  "movq %%rax, 16(%%rsp)\n"
  "movq $0x%08x, %%rcx\n"        # ここの部分($0x%08xはフォーマッタ)にfprintf()で乱数が挿入される
  "call __afl_maybe_log\n"
  "movq 16(%%rsp), %%rax\n"
  "movq  8(%%rsp), %%rcx\n"
  "movq  0(%%rsp), %%rdx\n"
  "leaq (128+24)(%%rsp), %%rsp\n"
  "\n"
  "/* --- END --- */\n"
  "\n";

afl_maybe_logmain_payload_64内で定義されます.

technical_details.txtに書いてある通り,AFLのカバレッジの計算は以下のようになります.

cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;

ここでまず,共有メモリ(shared_mem)領域は,後述のafl-fuzzがプログラムを実行する際に確保して,環境変数経由(SHM_ENV_VAR)でファジング対象のプログラムと共有します. この共有メモリ上に,プログラムがどこにアクセスしたのかを記録していきますが,AFLでは上記のように,("今の場所" ^ "直前の場所">>1)をキーとして利用します. つまり,AFLではある地点から別の地点への遷移を記録していきます. 直前の場所の値をシフトをする理由はA -> BB -> A の遷移や,A -> AB -> B の遷移を区別するためです. ドキュメントでは遷移 A -> B(A, B)と,タプルとして表現されています.

AFLでは,A -> B -> CA -> C -> B の遷移は区別されます. 一方で,時系列情報は含まれていないので,A -> B -> C -> AB -> C -> A -> B は同じカバレッジとして扱われることになります.

AFLで使用する共有メモリのサイズは64KBです.当然ながらキーが衝突する可能性がありますが,AFLは衝突は無視します(単純に同じ遷移として扱う). ドキュメントには以下のように分岐の数が10kを超えるプロジェクトでも衝突確率が10%前後ということが書いてあります.

   Branch cnt | Colliding tuples | Example targets
  ------------+------------------+-----------------
        1,000 | 0.75%            | giflib, lzo
        2,000 | 1.5%             | zlib, tar, xz
        5,000 | 3.5%             | libpng, libwebp
       10,000 | 7%               | libxml
       20,000 | 14%              | sqlite
       50,000 | 30%              | -

カバレッジの測定には,コスト(スピードや必要メモリ量)と精度の関係にトレードオフがあります. 今回カバレッジを測定する目的は,ファジング実行時の入力選択のアルゴリズムで利用するからであって,それに十分であれば厳密にカバレッジ情報を取得する意味はありません. AFLでは経験的にファジングにいい感じのカバレッジ測定をおこないます.

なお,AFLにはLLVM中間言語レベルでcode instrumentationするafl-clang-fastや,ソースコードがないプログラムのために,QEMUのuser mode emulationを利用してカバレッジを計算するqemu-mode(ただし遅い)もあります.

ファジング処理

ファジングの本体であるafl-fuzz.cをみていきます.

main関数はおおまかには以下のようになっています.

int main(int argc, char** argv) {
  // 初期化処理
  ...
  setup_shm();
  ...
  read_testcases();
  ...
  perform_dry_run(use_argv);
  ...
  // ファジング処理
  while (1) {
    cull_queue();
    ...
    skipped_fuzz = fuzz_one(use_argv);
    ...
  }
  ...

初期化処理

いくつか主要な処理を以下で説明します.

なお,AFLは一旦中断したファジングを再開することができるので,そのための処理もおこなっています(ここでは説明は省略).

setup_shm()

カバレッジ計算用の共有メモリを確保して,それを環境変数に設定します.

EXP_ST void setup_shm(void) {
  ...
  shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);
  ...
  shm_str = alloc_printf("%d", shm_id);
  if (!dumb_mode) setenv(SHM_ENV_VAR, shm_str, 1);
  ...
  trace_bits = shmat(shm_id, NULL, 0);
  ...
}

trace_bitsが作成した共有メモリで,これにカバレッジの情報が記録されます. この共有メモリのサイズはu8 [65536]です. trace_"bit"という名称ですが,実際には遷移(A,B)のタプルの出現回数を8bitで計数します.

ちなみにdumb_modeコンパイル時のcode instrumentationを使用しないモードです(当然効率は落ちる).

read_testcases()

inputで指定したディレクトリから全てのテストケースを読み込みます. AFLでは,以下のqueueでテストケースを管理します. queueのエントリはファイルの情報の他に,そのファイルに対するファジングの情報を保持しています.

struct queue_entry {

  u8* fname;                          /* File name for the test case      */
  u32 len;                            /* Input length                     */

  u8  cal_failed,                     /* Calibration failed?              */
      trim_done,                      /* Trimmed?                         */
      was_fuzzed,                     /* Had any fuzzing done yet?        */
      passed_det,                     /* Deterministic stages passed?     */
      has_new_cov,                    /* Triggers new coverage?           */
      var_behavior,                   /* Variable behavior?               */
      favored,                        /* Currently favored?               */
      fs_redundant;                   /* Marked as redundant in the fs?   */

  u32 bitmap_size,                    /* Number of bits set in bitmap     */
      exec_cksum;                     /* Checksum of the execution trace  */

  u64 exec_us,                        /* Execution time (us)              */
      handicap,                       /* Number of queue cycles behind    */
      depth;                          /* Path depth                       */

  u8* trace_mini;                     /* Trace bytes, if kept             */
  u32 tc_ref;                         /* Trace bytes ref count            */

  struct queue_entry *next,           /* Next element, if any             */
                     *next_100;       /* 100 elements ahead               */

};

perform_dry_run()

static void perform_dry_run(char** argv) {
  struct queue_entry* q = queue;
  ...
  while (q) {
    ...
    res = calibrate_case(argv, q, use_mem, 0, 1);
    ...
    q = q->next;
  }
  ...
}

ファジングを始める前にinputのtest caseを使ってターゲットプログラムを実行します. これの目的は,test caseのカバレッジ情報を取得することの他に,inputにクラッシュするようなテストケースがないか(AFLはクラッシュするテストケースは,ファジングの入力候補としては利用しません)や,test caseがタイムアウトしてしまわないか(この場合は,afl-fuzzに与えたタイムアウト条件が厳しすぎるかもしれない)などを調べるためです.

実際にプログラム実行を担当するのは後述のcalibrate_case()です.

calibrate_case()

static u8 calibrate_case(char** argv, struct queue_entry* q, u8* use_mem,
                         u32 handicap, u8 from_queue) {
  ...
  // forkserverの初期化
  if (dumb_mode != 1 && !no_forkserver && !forksrv_pid)
    init_forkserver(argv);
  ...
  for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {
    ...
    // ターゲットの実行
    fault = run_target(argv, use_tmout);
    ...
    // カバレッジのbitmapのハッシュ値の比較
    cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

    if (q->exec_cksum != cksum) {

      u8 hnb = has_new_bits(virgin_bits);
      if (hnb > new_bits) new_bits = hnb;

      if (q->exec_cksum) {

        u32 i;

        for (i = 0; i < MAP_SIZE; i++) {

          // 最初のトレース結果と異なるbitmapの箇所はマークする
          // この情報はstatsに使用
          if (!var_bytes[i] && first_trace[i] != trace_bits[i]) {

            var_bytes[i] = 1;
            stage_max    = CAL_CYCLES_LONG;

          }

        }

        var_detected = 1;

      } else {

        // 一番最初の実行結果は`first_trace`に保存
        q->exec_cksum = cksum;
        memcpy(first_trace, trace_bits, MAP_SIZE);

      }

    }

  }
  ...
}

まず,この関数を最初に実行した場合は,init_forkserver()で後述のfork serverの初期化をおこないます.

その後,ループで複数回ターゲットプログラムを実行し,コードのカバレッジや実行時間を測定します. 複数回実行する理由は,プログラムによっては同じ入力でも実行する度にコードパスや実行時間が変化する可能性があるからです(例えば内部で何か乱数に応じた処理をしている場合など).

run_target()を実行すると,trace_bitsに実行したカバレッジのbitmapが格納されます. その後,前に実行したtrace_bitsハッシュ値と,新規に得られたtrace_bitsハッシュ値が異なる場合は,has_new_bits(virgin_bits)で新規のパスがカバレッジのbitmapに含まれているかを確認します.

virgin_bitsは最初全て1のglobalなbitmapです. has_new_bits()trace_bitsに今まで観測しいていない情報が含まれているかを調べ,もしあったらvirgin_bitsを更新します. has_new_bits()trace_bitsに新しいタプル(遷移)が含まれていたら2を,すでにタプルは観測済みだが計数結果が更新された場合は1を返します.

run_target()およびfork server

run_target()はファジング対象のプログラムを実行します. fork serverを使う方法と使わない方法がありますが,ここでは使う場合を説明します.

まず,そもそもの話として,ファジング対象のプログラムをどうやって実行するのかという話があります. 代表的な方法はfork+execveを使用してファジング対象のプロセスを生成して実行する方法で,AFLもデフォルトでこの方式を利用します. この方式はターゲットのプログラムの修正が必要がなく,簡単に利用できる一方で,fork+execveはオーバヘッドが大きいことで知られており,また,そもそもプログラムの初期化に時間がかかり,ファジングしたい箇所に到達するまでに時間がかかるということもあります.

別の方法として,もしファジングしたい処理が関数として呼び出し可能であれば,それをファジングするプロセスから呼び出すという方法が考えられます. この方式はファジング対象のプログラムを呼び出すための処理を自分で書く必要がありますが,fork+execveや初期化のオーバヘッドが無く,高速にファジング対象を実行することができます.ただし,何か関数がグローバルな状態に依存するような場合は注意が必要です. クラッシュ時の対応も別途考える必要があります. 例えばLibFuzzerはデフォルトでこの方式でファジングをします. AFLも,"persistent mode"という名称でこの機能をサポートしています.

さて,前述のようにAFLではデフォルトではfork+execveでプロセスを実行しますが,少しでもオーバヘッドを削減するために,fork serverという仕組みを利用します. これは,fork+execveでターゲットプログラムを実行しますが,ターゲットプログラムはエントリポイント(正確には最初にカバレッジを記録する箇所)でファジング側の指示を待つために停止します. その後,ファジング側の指示を受信すると,ターゲットプログラムはその止まっていた箇所から新たにfork()して,子プロセスが処理を続けます. こうすることで,execveやダイナミックリンクのオーバヘッドを避けてターゲットプログラムを実行することができます. ファジングプロセスとの通信やforkするためのコードはafl-gccコンパイルした際に仕込みます.

AFLはinit_forkserver()でforkしたのち,メモリ制限などをかけた上でexecveでターゲットプログラムを起動します. このとき,dup(2)を使って制御通信用のfile descriptorを用意しています.

EXP_ST void init_forkserver(char** argv) {
  ...
  forksrv_pid = fork();
  ...
  if (!forksrv_pid) {

    struct rlimit r;

    /* Umpf. On OpenBSD, the default fd limit for root users is set to
       soft 128. Let's try to fix that... */

    if (!getrlimit(RLIMIT_NOFILE, &r) && r.rlim_cur < FORKSRV_FD + 2) {

      r.rlim_cur = FORKSRV_FD + 2;
      setrlimit(RLIMIT_NOFILE, &r); /* Ignore errors */

    }

    if (mem_limit) {

      r.rlim_max = r.rlim_cur = ((rlim_t)mem_limit) << 20;

      setrlimit(RLIMIT_AS, &r); /* Ignore errors */

    }

    /* Dumping cores is slow and can lead to anomalies if SIGKILL is delivered
       before the dump is complete. */

    r.rlim_max = r.rlim_cur = 0;

    setrlimit(RLIMIT_CORE, &r); /* Ignore errors */

    /* Isolate the process and configure standard descriptors. If out_file is
       specified, stdin is /dev/null; otherwise, out_fd is cloned instead. */

    setsid();

    dup2(dev_null_fd, 1);
    dup2(dev_null_fd, 2);

    if (out_file) {

      dup2(dev_null_fd, 0);

    } else {

      dup2(out_fd, 0);
      close(out_fd);

    }

    /* Set up control and status pipes, close the unneeded original fds. */

    if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed");
    if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed");

    close(ctl_pipe[0]);
    close(ctl_pipe[1]);
    close(st_pipe[0]);
    close(st_pipe[1]);

    close(out_dir_fd);
    close(dev_null_fd);
    close(dev_urandom_fd);
    close(fileno(plot_file));

    /* This should improve performance a bit, since it stops the linker from
       doing extra work post-fork(). */

    if (!getenv("LD_BIND_LAZY")) setenv("LD_BIND_NOW", "1", 0);

    /* Set sane defaults for ASAN if nothing else specified. */

    setenv("ASAN_OPTIONS", "abort_on_error=1:"
                           "detect_leaks=0:"
                           "symbolize=0:"
                           "allocator_may_return_null=1", 0);

    /* MSAN is tricky, because it doesn't support abort_on_error=1 at this
       point. So, we do this in a very hacky way. */

    setenv("MSAN_OPTIONS", "exit_code=" STRINGIFY(MSAN_ERROR) ":"
                           "symbolize=0:"
                           "abort_on_error=1:"
                           "allocator_may_return_null=1:"
                           "msan_track_origins=0", 0);

    execv(target_path, argv);

    /* Use a distinctive bitmap signature to tell the parent about execv()
       falling through. */

    *(u32*)trace_bits = EXEC_FAIL_SIG;
    exit(0);

  }

  ...
}

ターゲットプログラム側の処理はafl-as.hで定義されています. run_target()では,init_forkserver()で用意したfile descriptorを利用してターゲットのプロセスにメッセージを送ることで実際のファジングを開始します.

static u8 run_target(char** argv, u32 timeout) {
  ...
    s32 res;

    /* In non-dumb mode, we have the fork server up and running, so simply
       tell it to have at it, and then read back PID. */

    // ターゲットプログラム側に処理実行をリクエスト
    if ((res = write(fsrv_ctl_fd, &prev_timed_out, 4)) != 4) {

      if (stop_soon) return 0;
      RPFATAL(res, "Unable to request new process from fork server (OOM?)");

    }

    if ((res = read(fsrv_st_fd, &child_pid, 4)) != 4) {

      if (stop_soon) return 0;
      RPFATAL(res, "Unable to request new process from fork server (OOM?)");

    }

    if (child_pid <= 0) FATAL("Fork server is misbehaving (OOM?)");
  ...
    // 実行結果のstatus codeをターゲットプログラムから受信する
    if ((res = read(fsrv_st_fd, &status, 4)) != 4) {

      if (stop_soon) return 0;
      RPFATAL(res, "Unable to communicate with fork server (OOM?)");

    }
  ...
  classify_counts((u64*)trace_bits);
}

run_target()では最後にclassify_counts()という関数を読んでいますが,この関数はカバレッジの計数結果を以下の8つに分類します.

  1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+

つまり,AFLでは例えばあるA -> Bという遷移を5回実行したものと,6回実行したものは区別しません. これは例えばたくさんループ処理するような場合で,少しだけループ回数が変わってもそれは別のパスとは考えないということになります.

このfork serverを応用すると,プログラムの途中まで処理を進めておいて,ファジングを開始したい箇所まできたら実行を中断し,あとはafl-fuzzの指示に応じてfork()してファジングするということが考えられます. AFLはこの"deferred mode"をサポートしており,LLVMを利用してinstrumentationする場合に利用できます(参考: llvm_mode).

ちなみに,fork serverを使ってもファジングを実行する度にforkはすることになります. AFLはマルチコアでのファジングをサポートしていますが,fork(や結果の同期)が遅くてスケールしにくいということが研究で指摘されています[1].

Culling

AFLはキューの先頭から一つ一つ順番に入力を選択し,ファジングをしていきます. そして,ファジングによって新しいカバレッジを持つを入力が得られたらそれをキューに新規に追加します.

AFLは一度追加したエントリを削除することはしませんが,効率良くファジングを実行するために,エントリの中で特に有力そうなものをfavoredとして優先的に処理するようにチェックします. この処理をcullingと呼び,cull_queue()および,update_bitmap_score() (この関数はcalibrate_case()から呼ばれる)がその処理を実行します. アルゴリズムはtechnical_details.txtの4 Culling the corpusに書いてあります.

ざっくりというと,AFLは (プログラムの実行時間) * (入力のサイズ)をスコアとして,それぞれのカバレッジのbitに対して,そのスコアが最も小さいものをfavoredであるとします.

culling処理は新規に入力がキューに追加される度にに実行されます.

ファジング処理

fuzz_one() がファジング処理の本体です. AFLは遺伝的アルゴリズムをベースとして,おおまかには以下のようにファジング処理をおこないます.

fuzz_one(){
    1. favoredなtest caseが存在するかを確認
    2. calibration
    3. input trimming
    4. performance scoreの計算
    5. deterministic phase
       - bitflip
       - interest
       - dctionary
    6. non-deterministic phase
       - havoc
       - splice
}

AFLは,ファジングで使用する入力を一つキューから選択した後,その入力に対して,ある変換を適用+ファジング対象のプログラムを実行する,ということを複数回おこないます. そして,得られたカバレッジが今まで観測してたことのないパスを含んでいた場合にのみ,その新しい入力をキューに追加します. 名前が紛らわしいかもしれまんせんが,fuzz_one()では一回だけ入力を改変して実行する,ということをおこなっている訳ではありません.

一般的な遺伝的アルゴリズムでは,世代ごとにどんどん個体が入れ替わっていきますが,AFLでは積極的にtest caseを入れ替えることはしません. 実験的にその方が結果が良いようです.

以下でそれぞれの処理を説明します.

favoredなtest caseが存在するかを確認

前述したculling処理で,キューのエントリはそれぞれfavoredであるかどうかチェックされています. もしfavoredでない場合は,一定確率に応じてその入力に対するファジングをスキップします.

calibration

perform_dry_runで実行したcalibrationと同じです. 事前のcalibrate_case()が失敗した場合,もう一度ここでcalibrationを試みるようです. それでもcalibrationに失敗したら,このtest caseについてはファジングを諦めます.

input trimming

ファジングの入力はサイズが小さい方が,一般にターゲットプログラムの実行時間が短くなるので望ましいです. fuzz_one()ではこの後なんどもファジングをしていくので,その前に入力のファイルサイズの削減を試みます. これは単純に適当の連続領域を削除して,実行のカバレッジハッシュ値が同じであったら実行結果が同じと判断するという戦略になっています.

なお,afl-tmin.cにもう少し良いアルゴリズム(ただし時間がかかる)が実装されています.

performance scoreの計算

平均実行時間などからperformance scoreを計算します. この値は後述のhavoc stageで入力の改変のパラメータとして利用されます. (実行時間が長いと,havoc stageの回数を減らす).

Deterministic / Non-deterministic phase

ここからいよいよファジングを実行していきます.

AFLが施す入力に対する変換は,決定的なもの(deterministic)と,非決定的なものの二種類に分けられます. 決定的な処理にはbitflipであったり,事前に与えたdictionaryの情報を使った書き換えなどをします. この決定的な処理によって,効率よく入力のmagic number領域や,データ領域を推定することができます. 非決定的な処理は,一般の遺伝的アルゴリズムに近い,ランダムな変換処理をおこないます.

この処理はAFLで一番重要とも言える処理ですが,具体的なアルゴリズムは参考文献に詳しく書いてあるので,そちらを参照してください.

一度deterministic phaseをおこなうと,キューのpassed_detが1になるので,それに対しては今後deterministic phaseはおこなわなくななります.

common_fuzz_stuff()

deterministic phase, non-deterministic phaseともに,common_fuzz_stuff()という関数で実際のファジング処理を実行します. この関数は前述のrun_target()でターゲットプログラムを実行したのち,save_if_interesting()で実行結果を確認します.

EXP_ST u8 common_fuzz_stuff(char** argv, u8* out_buf, u32 len) {
  ...
  fault = run_target(argv, exec_tmout);
  ...
  queued_discovered += save_if_interesting(argv, out_buf, len, fault);
  ...
}

save_if_interesting()は前述したhas_new_bits()で実行結果が新しいコードパスを含んでいるかどうかを調べ,そうであればキューに新規にエントリを追加します. また,このタイミングでcalibrate_case()でcalibrationもおこないます.

/* Check if the result of an execve() during routine fuzzing is interesting,
   save or queue the input test case for further analysis if so. Returns 1 if
   entry is saved, 0 otherwise. */

static u8 save_if_interesting(char** argv, void* mem, u32 len, u8 fault) {
    ...
    if (!(hnb = has_new_bits(virgin_bits))) {
      if (crash_mode) total_crashes++;
      return 0;
    }    
    ...
    add_to_queue(fn, len, 0);
    ...
    res = calibrate_case(argv, queue_top, mem, queue_cycle - 1, 0);
    ...
}

ここでは省略していますが,もしクラッシュした場合は,その旨を記録します.

まとめ

AFLの構造について簡単に説明しました. ソースを見ればわかる通り,AFLは効率的なファジングのために様々なヒューリスティクスの塊となっています. ファジングのアルゴリズム本体以外にも,どう効率よくファジングをするかという工夫が随所に入っており,非常に面白いと思います.

最近はAFLよりももっと活発に開発され,より効率の良いとされるファジングツールもありますが,AFLは非常に使いやすく,まだまだ十分有用だと思います.

AFLの拡張

最後にAFLを拡張したものについて,いくつか紹介します,

近年AFLをベースにしたファジングツールの研究・開発が多く存在します. ソースが公開されていて著名なものには以下のようなものがあります(他にもあります).

  • aflfast
    • Marcel Boehme et al., Coverage-based Greybox Fuzzing as Markov Chain, CCS'16
    • AFLのシード選択方法(スケジューラ)の改善
  • driller
    • Nick Stephens et al., Driller: Augmenting Fuzzing Through Selective Symbolic Execution, NDSS'16
    • AFLとSymbolic executionの組み合わせ
  • aflgo
    • Marcel Boehme et al., Directed graybox fuzzing, CCS'17
  • FairFuzz
    • Caroline Lemieux et al., FairFuzz: A Targeted Mutation Strategy for Increasing Greybox Fuzz Testing Coverage, ASE'18
  • aflsmart
  • winafl

AFL以外にもファジングツールは多く存在します. 例えばgithubで検索すればたくさん見つかります. AFLは一般のユーザランドアプリケーションが対象ですが,最近は他の用途に特化したもの,例えばネットワークプロトコルや,Javascriptエンジン,さらにはカーネル向けのものなど,様々なものが開発されています.

参考文献

NVDIMMとACPI

DIMMに刺せる不揮発性メモリ(NVDIMM*1 )はACPIからどのように扱われるかというメモ.

TL;DR

ACPIのNFIT (NVDIMM Firmware Interaface Table)に情報が入っています.

QEMUでのエミュレーション

QEMUのNVDIMMエミュレーションで確認します.

今回は以下のようなオプションで試しました.

     -machine pc,nvdimm \
     -m 16G,slots=2,maxmem=32G \
     -object memory-backend-file,id=mem1,share,mem-path=/home/work/vm/nvdimm-2,size=4G,align=128M \
     -device nvdimm,memdev=mem1,id=nv1,label-size=2M \
     ...

オプションの詳細は上記のQEMUのドキュメントを確認ください. 詳細は確認していませんが,どうもQEMU的には最初hotplug可能なメモリスロットを用意しておいて,そこにNVDIMMのデバイスを接続するという形態を取っているようです.

mem-pathで指定したパスに,指定したサイズだけのファイルが作成されます.

これでLinuxを起動すると,自動でNVDIMMが認識されます.

$ dmesg | grep pmem
[    7.284102] pmem0: detected capacity change from 0 to 4160749568
$ ls /dev/pmem0
/dev/pmem0

ACPIの情報は以下のように確認できます(iaslubuntuならsudo apt install acpica-toolsで入ります).

% sudo cp /sys/firmware/acpi/tables/NFIT .
% sudo iasl -d NFIT
% cat NFIT.dsl

/*
 * Intel ACPI Component Architecture
 * AML/ASL+ Disassembler version 20180105 (64-bit version)
 * Copyright (c) 2000 - 2018 Intel Corporation
 * 
 * Disassembly of NFIT, Tue Apr  2 06:10:17 2019
 *
 * ACPI Data Table [NFIT]
 *
 * Format: [HexOffset DecimalOffset ByteLength]  FieldName : FieldValue
 */

[000h 0000   4]                    Signature : "NFIT"    [NVDIMM Firmware Interface Table]
[004h 0004   4]                 Table Length : 000000E0
[008h 0008   1]                     Revision : 01
[009h 0009   1]                     Checksum : 40
[00Ah 0010   6]                       Oem ID : "BOCHS "
[010h 0016   8]                 Oem Table ID : "BXPCNFIT"
[018h 0024   4]                 Oem Revision : 00000001
[01Ch 0028   4]              Asl Compiler ID : "BXPC"
[020h 0032   4]        Asl Compiler Revision : 00000001

[024h 0036   4]                     Reserved : 00000000

[028h 0040   2]                Subtable Type : 0000 [System Physical Address Range]
[02Ah 0042   2]                       Length : 0038

[02Ch 0044   2]                  Range Index : 0002
[02Eh 0046   2]        Flags (decoded below) : 0003
                   Add/Online Operation Only : 1
                      Proximity Domain Valid : 1
[030h 0048   4]                     Reserved : 00000000
[034h 0052   4]             Proximity Domain : 00000000
[038h 0056  16]           Address Range GUID : 66F0D379-B4F3-4074-AC43-0D3318B78CDB
[048h 0072   8]           Address Range Base : 0000000440000000
[050h 0080   8]         Address Range Length : 00000000F8000000
[058h 0088   8]         Memory Map Attribute : 0000000000008008

[060h 0096   2]                Subtable Type : 0001 [Memory Range Map]
[062h 0098   2]                       Length : 0030

[064h 0100   4]                Device Handle : 00000001
[068h 0104   2]                  Physical Id : 0000
[06Ah 0106   2]                    Region Id : 0000
[06Ch 0108   2]                  Range Index : 0002
[06Eh 0110   2]         Control Region Index : 0003
[070h 0112   8]                  Region Size : 00000000F8000000
[078h 0120   8]                Region Offset : 0000000000000000
[080h 0128   8]          Address Region Base : 0000000000000000
[088h 0136   2]             Interleave Index : 0000
[08Ah 0138   2]              Interleave Ways : 0001
[08Ch 0140   2]                        Flags : 0000
                       Save to device failed : 0
                  Restore from device failed : 0
                       Platform flush failed : 0
                            Device not armed : 0
                      Health events observed : 0
                       Health events enabled : 0
                              Mapping failed : 0
[08Eh 0142   2]                     Reserved : 0000

[090h 0144   2]                Subtable Type : 0004 [NVDIMM Control Region]
[092h 0146   2]                       Length : 0050

[094h 0148   2]                 Region Index : 0003
[096h 0150   2]                    Vendor Id : 8086
[098h 0152   2]                    Device Id : 0001
[09Ah 0154   2]                  Revision Id : 0001
[09Ch 0156   2]          Subsystem Vendor Id : 0000
[09Eh 0158   2]          Subsystem Device Id : 0000
[0A0h 0160   2]        Subsystem Revision Id : 0000
[0A2h 0162   1]                 Valid Fields : 00
[0A3h 0163   1]       Manufacturing Location : 00
[0A4h 0164   2]           Manufacturing Date : 0000
[0A6h 0166   2]                     Reserved : 0000
[0A8h 0168   4]                Serial Number : 00123456
[0ACh 0172   2]                         Code : 0301
[0AEh 0174   2]                 Window Count : 0000
[0B0h 0176   8]                  Window Size : 0000000000000000
[0B8h 0184   8]               Command Offset : 0000000000000000
[0C0h 0192   8]                 Command Size : 0000000000000000
[0C8h 0200   8]                Status Offset : 0000000000000000
[0D0h 0208   8]                  Status Size : 0000000000000000
[0D8h 0216   2]                        Flags : 0000
                            Windows buffered : 0
[0DAh 0218   6]                    Reserved1 : 000000000000

Raw Table Data: Length 224 (0xE0)

  0000: 4E 46 49 54 E0 00 00 00 01 40 42 4F 43 48 53 20  // NFIT.....@BOCHS 
  0010: 42 58 50 43 4E 46 49 54 01 00 00 00 42 58 50 43  // BXPCNFIT....BXPC
  0020: 01 00 00 00 00 00 00 00 00 00 38 00 02 00 03 00  // ..........8.....
  0030: 00 00 00 00 00 00 00 00 79 D3 F0 66 F3 B4 74 40  // ........y..f..t@
  0040: AC 43 0D 33 18 B7 8C DB 00 00 00 40 04 00 00 00  // .C.3.......@....
  0050: 00 00 00 F8 00 00 00 00 08 80 00 00 00 00 00 00  // ................
  0060: 01 00 30 00 01 00 00 00 00 00 00 00 02 00 03 00  // ..0.............
  0070: 00 00 00 F8 00 00 00 00 00 00 00 00 00 00 00 00  // ................
  0080: 00 00 00 00 00 00 00 00 00 00 01 00 00 00 00 00  // ................
  0090: 04 00 50 00 03 00 86 80 01 00 01 00 00 00 00 00  // ..P.............
  00A0: 00 00 00 00 00 00 00 00 56 34 12 00 01 03 00 00  // ........V4......
  00B0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  // ................
  00C0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  // ................
  00D0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  // ................

ちなみに,Proximity DomainがNUMAドメインの情報です.

(補足) SRATとの関連

ACPIのSRAT (System Resource Affinity Table)に,NUMAノードの情報や,メモリの物理アドレス,サイズなどの情報が格納されています.このテーブルはNUMAなマシンでないと存在しないかもしれません.

Linuxでは以下のようにしてSRATのMemory Affinityの情報が確認できます. 先ほどと同じQEMU上のゲストで実行すると以下のようになります.

% sudo cp /sys/firmware/acpi/SRAT .
% sudo iasl -d SRAT
% cat SRAT.dsl | grep -A13 "Memory Affinity" | grep -B10 -A3 "Enabled : 1"
[1B0h 0432   1]                Subtable Type : 01 [Memory Affinity]
[1B1h 0433   1]                       Length : 28

[1B2h 0434   4]             Proximity Domain : 00000000
[1B6h 0438   2]                    Reserved1 : 0000
[1B8h 0440   8]                 Base Address : 0000000000000000
[1C0h 0448   8]               Address Length : 00000000000A0000
[1C8h 0456   4]                    Reserved2 : 00000000
[1CCh 0460   4]        Flags (decoded below) : 00000001
                                     Enabled : 1
                               Hot Pluggable : 0
                                Non-Volatile : 0
[1D0h 0464   8]                    Reserved3 : 0000000000000000

[1D8h 0472   1]                Subtable Type : 01 [Memory Affinity]
[1D9h 0473   1]                       Length : 28

[1DAh 0474   4]             Proximity Domain : 00000000
[1DEh 0478   2]                    Reserved1 : 0000
[1E0h 0480   8]                 Base Address : 0000000000100000
[1E8h 0488   8]               Address Length : 00000000BFF00000
[1F0h 0496   4]                    Reserved2 : 00000000
[1F4h 0500   4]        Flags (decoded below) : 00000001
                                     Enabled : 1
                               Hot Pluggable : 0
                                Non-Volatile : 0
[1F8h 0504   8]                    Reserved3 : 0000000000000000

[200h 0512   1]                Subtable Type : 01 [Memory Affinity]
[201h 0513   1]                       Length : 28

[202h 0514   4]             Proximity Domain : 00000000
[206h 0518   2]                    Reserved1 : 0000
[208h 0520   8]                 Base Address : 0000000100000000
[210h 0528   8]               Address Length : 0000000340000000
[218h 0536   4]                    Reserved2 : 00000000
[21Ch 0540   4]        Flags (decoded below) : 00000001
                                     Enabled : 1
                               Hot Pluggable : 0
                                Non-Volatile : 0
[220h 0544   8]                    Reserved3 : 0000000000000000

[228h 0552   1]                Subtable Type : 01 [Memory Affinity]
[229h 0553   1]                       Length : 28

[22Ah 0554   4]             Proximity Domain : 00000000
[22Eh 0558   2]                    Reserved1 : 0000
[230h 0560   8]                 Base Address : 0000000440000000
[238h 0568   8]               Address Length : 0000000440000000
[240h 0576   4]                    Reserved2 : 00000000
[244h 0580   4]        Flags (decoded below) : 00000003
                                     Enabled : 1
                               Hot Pluggable : 1
                                Non-Volatile : 0
[248h 0584   8]                    Reserved3 : 0000000000000000

で,ここのMemory Affinity StructureにNonVolatileというフィールドがあります. なのでこのフィールドからもNVDIMMかどうか判定できるのでは? という気がしますが,とりあえずQEMUでは上記のようにNonVolatileな領域はありません(一番最後のフィールドがアドレス的にNVDIMMデバイスが追加されるhotplug可能領域だと思います).

これはQEMUがhotplug可能領域にNVDIMMデバイスを指すという構成を取っているからであり,他のデバイスでは異なるのかもしれません.よく分かりません.

とりえず,NVDIMMの情報を取得するにはNFITを見るのが確実そうです.

(補足) Linuxでのエミュレーション

Linuxはブートオプションでmemmap=16G!16Gなどとすると,LinuxDRAMのアドレス16Gから始まる16GBの領域をPMEMの領域として管理するようになります(パラメータの詳細はこちら *2).

これはACPI的には何も変化しておらず,あくまでLinuxがメモリの一部の領域をNVDIMMとして扱っていることになります. このことは/sys/firmware/acpi/tables以下にNFITがないことからも分かります.

参考文献

*1:最近はNVDIMMよりpersistent memoryとかNVMM(Non-volatile main memory)という言い方の方が多いような気がしなくもないですが,ACPIはNVDIMMという単語を使っているのでそれに倣います.

*2:ちなみにmemmapオプションで特定のNUMAノードから領域の確保が指定できないのか探してみたのですが,よく分かりませんでした.自分でSRATの物理アドレスを確認して指定するしかないのでしょうかね .

クロスプラットフォームなハイパーバイザ Intel HAXM

HAXM (Hardware Accelerated Execution Manager)Intelが作成しているハイパーバイザです.もとはAndroid Emulatorのバックエンドとして開発が開始されたもののようです. 以下のような特徴があります.

細かい違いは当然ありますが,HAXMはKVMやHypervisor.Frameworkのようなインタフェースを提供します. WindowsではデバイスドライバMacではkernel extension, Linuxではカーネルモジュールとして実装されており,それに対してioctlでやりとりすることになります.

HAXMはもともとWindowsMacがサポート対象でしたが,気づいたら昨年にLinuxのサポートが追加されていたので,今回試してみました.

ドキュメント

HAXMといえばドキュメントが全く無くて一体どうやって使うんだという感じでしたが,Linuxサポート追加と同時期にドキュメントも(少し)追加されて,人間に多少は優しくなりました.

特に,HAXMのAPIに関するドキュメントはここにあります.

Linuxでの利用

インストール

マニュアルに従ってインストール(make && make install)するだけです.簡単.

インストールが完了すると,/dev/HAXというデバイスが作成されています. Linuxではこのデバイスに対してioctlでやりとりすることになります.

QEMUからの利用

QEMUのHAXMサポートはもともとWindows用に前からありましたが,Linux向けの対応は昨年の11月と比較的最近に入ったので,おそらく自分でQEMUコンパイルする必要があると思います. ./configure --enable-haxをつけてコンパイルします.

QEMUからHAXMを利用する場合は起動オプションとして-accel haxをつけます (KVMの場合は-accel kvm). とりあえず,Ubuntuなゲストは普通に起動しました.

ちなみに,原因は調査していませんが,vcpuを17個以上作成しようとするとsegvしました (2019-3-23追記: QEMUのソースの中で最大のvCPU数が16個になっていました). また,-cpu hostKVMでないと使用できないようです. KVMとHAXMの共存(同時実行)はできません.

HAXMを使ってVMを起動すると,以下のようなデバイスが作成されます.

/dev/hax_vm/vm00
/dev/hax_vm00/vcpu0

それぞれVMやvCPUの設定に利用します.

性能比較

KVMとHAXMで簡単なベンチマークを取ってみました. いま手元にNAS Parallel Benchmarks (NPB)の評価スクリプトがあったので,それを利用しました. vcpu数は16,メモリは32GB, KVMはVMCS shadowing及びAPICVや準仮想化機能を有効にしています. ホストのLinuxは5.0, HAXM及びQEMUは現時点のmasterのものを利用しています.

f:id:mm_i:20190322210330p:plain
NPB-OMP ベンチマーク結果

左側のグラフは実行時間のグラフ,右側はKVMを基準とした相対値のグラフ(数字はKVMの実行時間)です.3回実行の中央値をプロットしています. NPBは基本的にOpenMPを利用した数値計算ベンチマークであまりI/Oは関係ないので,今回は単純に計算中に生じたタイマ割り込みなどのVMEXITのハンドリングの速度差が出るのかと思いますが,HAXMの方が20%程度遅いベンチマークが結構あります.

機能・性能的にはやはりKVMの方がいろいろと上のようです. コードを軽くみた感じ,VMCS ShadowingやAPICVなどの機能や,KVMの準仮想化機能のようなものは入っていないように思います. ネステッドのサポートも現時点ではありません.

本当はもっといろんなマイクロベンチマークや,sysbenchなどの結果を比較をして,速度低下の要因が特定できるとよいのですが,まぁそれはまたの機会に.

APIについて

ドキュメントによると以下のようなAPIがあるようです.

  • System IOCTLs
    • HAX_IOCTL_VERSION
    • HAX_IOCTL_CAPABILITY
    • HAX_IOCTL_SET_MEMLIMIT
    • HAX_IOCTL_CREATE_VM
  • VM IOCTLs
    • HAX_VM_IOCTL_VCPU_CREATE
    • HAX_VM_IOCTL_ALLOC_RAM
    • HAX_VM_IOCTL_ADD_RAMBLOCK
    • HAX_VM_IOCTL_SET_RAM
    • HAX_VM_IOCTL_SET_RAM2
    • HAX_VM_IOCTL_NOTIFY_QEMU_VERSION
  • VCPU IOCTLs
    • HAX_VCPU_IOCTL_SETUP_TUNNEL
    • HAX_VCPU_IOCTL_RUN
    • HAX_VCPU_IOCTL_SET_MSRS
    • HAX_VCPU_IOCTL_GET_MSRS
    • HAX_VCPU_IOCTL_SET_FPU
    • HAX_VCPU_IOCTL_GET_FPU
    • HAX_VCPU_SET_REGS
    • HAX_VCPU_GET_REGS
    • HAX_VCPU_IOCTL_INTERRUPT

EPTの細かい設定だったり,VMCALLの追加だったりは直接ソースをいじる必要があるみたいです. コンパイル自体はKVMより楽だと思います.

所感

QEMUが対応していてマルチプラットフォームかつBSDライセンスなハイパーバイザはHAXMだけだと思います. 個人的にはIntel CPUに新しい機能が入った時に,リファレンス実装的な感じでその機能のサポートがHAXMに入るといろんなプロジェクトで参考にできて便利になるなと思いました. 現状は特別機能的なアドバンテージがある訳ではないようですけれども.

IntelといえばIoT向けのARCN hypervisorも作っていて,Intel的にHAXMの優先度がどうなのかはよく分かりませんが,今後も開発続くと良いですね.

KVMの準仮想化機能

KVMにはいくつか準仮想化インタフェースが存在します. KVMはHWによる仮想化支援機構を利用してゲストを実行するので,準仮想化機能を使用しなくても任意のOSが実行できますが,準仮想化機能を利用することでVMのパフォーマンスを向上できる場合があります.以下のような機能があります.

  • Paravirtualized clock
  • Asynchronous page fault
  • Paravirtualized EOI
  • Paravirtualized spin lock
  • Paravirtualized tlb shootdown
  • Paravirtualized send IPI

当然といえば当然ですがLinuxKVMの準仮想化機能をサポートしているので,KVM上でLinuxを実行する際はこれらの機能が利用可能です.

以下,x86についての話です.Linux v4.20, QEMU v3.10のコードをベースにしています.

KVM準仮想化機能の確認

KVM上のゲストはcpuid命令を利用してKVMの準仮想化機能が利用できるかどうかを調べることができます. 以下がKVMのcpuidに関するドキュメントです.

KVMではcpuidの0x40000000と0x40000001を利用して情報をゲストに伝えます. 本来この領域はcpuid的にはreserved領域です. cpuid 0x40000001のeaxにKVMの準仮想化機能のどれが利用可能化のフラグが格納されています.

cpuidの値はcpuidコマンドを利用して取得できます.(Ubuntuの場合はapt install cpuid)

% cpuid
...
   hypervisor_id = "KVMKVMKVM   "
   hypervisor features (0x40000001/eax):
      kvmclock available at MSR 0x11          = true
      delays unnecessary for PIO ops          = true
      mmu_op                                  = false
      kvmclock available a MSR 0x4b564d00     = true
      async pf enable available by MSR        = true
      steal clock supported                   = true
      guest EOI optimization enabled          = true
      stable: no guest per-cpu warps expected = true
...

ただし,このcpuidコマンドはこの記事執筆段階ではKVMのfeatures全てに対応していません. 例えば,上の出力例からはparavirtualized spinlockやparavirtualized TLB shootdown等の有効無効は分かりません.

cpuid -rを実行すると実際のレジスタの値が確認できるのでこれを使用するのが確実です.

% cpuid -r
...
   0x40000000 0x00: eax=0x40000001 ebx=0x4b4d564b ecx=0x564b4d56 edx=0x0000004d
   0x40000001 0x00: eax=0x01000afb ebx=0x00000000 ecx=0x00000000 edx=0x00000000
...

また,一部機能はMSRを利用してデータをやりとりします.MSRに関しては以下にドキュメントがあります.

以下でKVMが提供する準仮想化インタフェースについて簡単に説明します.

Paravirtualized clock

  • 関連するFeature
    • KVM_FEATURE_CLOCKSOURCE
    • KVM_FEATURE_CLOCKSOURCE2

カーネルのclocksourceとして準仮想化クロックを提供します.いわゆるkvm-clockです. kvm-clockはMSRを利用してホストにメモリアドレスを通知し,ホストがそのメモリに必要に応じて時刻を書き込むことで時刻を取得する仕組みです. 利用するMSRのアドレスはKVM_FEATURE_CLOCKSOURCEKVM_FEATURE_CLOCKSOURCE2で異なりますが,多分KVM_FEATURE_CLOCKSOURCEはdeprecatedです.

clocksourceは以下のように確認できます.

$ cat /sys/devices/system/clocksource/clocksource0/available_clocksource
kvm-clock tsc hpet acpi_pm
$ cat /sys/devices/system/clocksource/clocksource0/current_clocksource
kvm-clock

kvm-clockが利用可能な環境であればkvm-clockが利用されるようになっています.

なお,頻繁にclocksourceにアクセスするような場合はkvm-clockアクセスのオーバヘッドが無視できなくなるようなので,注意が必要です:

余裕があればkvm-clockについてはもう少し調べたいと思っています.

Asynchronous page fault

  • 関連するFeature
    • KVM_FEATURE_ASYNC_PF, KVM_FEATURE_ASYNC_PF_VMEXIT

これはゲスト的にはpage faultではないがhost側でpage faultした際,そのpage fault処理中にゲストのvCPUが別の処理を実行することを可能にする機能です.

Asynchronous page fault (APF)に関しては以下が詳しいです.

また,KVM_FEATURE_ASYNC_PF_VMEXITという機能がありますが,これはnested virtualization時にL1のKVMに対してL2のAPFを#PF VMEXITとして伝える機能のようです.

Paravirtualized EOI

  • 関連するFeature
    • KVM_FEATURE_PV_EOI

割り込みが発生した際,OSはAPICのEOI (End of Interrupt)レジスタに書き込むことで割り込み処理の完了を通知します. 仮想環境においてはAPICは仮想化されているので,ゲストがEOIにアクセスするとVMEXITが発生します.

PV-EOIはこのVMEXITを削減する機能です.

  • KVM_FEATURE_PV_EOIが利用可能な場合,特定のMSRにゲストのメモリアドレスを書き込む
  • ホストは割り込みをゲストに挿入する際,ゲストのEOIレジスタへの書き込みが必要なければMSRが指すメモリの最下位ビットに1をたてる
  • ゲストは割り込み時処理時にホストが書き込んだ内容をチェックして,その値が1ならばビットをクリアする.EOIにはアクセスしない
  • 必要であればあとでホストがそのフラグを確認して処理をおこなう.(実際のEOI書き込みをおこなうなど)

ちなみにこれはVT-xにあるAPICvとは別の機能です. APICvを利用することでAPICレジスタそのものがHW的に仮想化され多くの場合VMEXITなしでアクセスできるようになります. APICvに関しては以下に参考になります.

TODO: PV-EOIとAPICvの現在の使われ方の調査

Paravirtualized spin lock

  • 関連するFeature
    • KVM_FEATURE_PV_UNHALT

この機能を利用すると,ゲストのあるvCPUがspinlockを獲得しようとする際,ある一定時間spinしてもlockが獲得できなければ一旦そのvCPUはスリープします. 別のvCPUがlockを解放した際,もしlock待ちでsleepしているvCPUがいたら,そのvCPUをhypercall(KVM_HC_KICK_CPU)で起こします.(実際の動作はもう少し複雑)

これにより,スピン時間を他のvCPUの処理に当てることができる他,Lockを待っているvCPUがうまくスケジューリングされないという問題(Lock Waiter Preemption)も改善できます.

仮想化環境においてスピンロックを以下に効率よくハンドリングするかというのは仮想化における課題の一つで,ここ十年ほど研究が盛んにおこなわれています. VMのspinlockの話はまた別途記事にしようと思います.

Paravirtualized TLB flush

  • 関連するFeature
    • KVM_FEATURE_PV_TLB_FLUSH
  • 導入時期

x86ではコア間でTLBのコヒーレンシが保たれません. すなわち,あるコアでページテーブルを変更した場合,別のコアからもそのページテーブルを利用する場合はそのコアのTLBを明示的にフラッシュする必要があります. これをTLB shootdownと呼びます.

LinuxではTLB shootdownはIPIを用いておこないます. TLB shootdown IPIを送信したコアは,別のコアからの応答を待ちます. しかしながら,仮想化環境では以下のような問題があります.

  • あるvCPUがIPI送信時に実際に動作しているとは限らない
  • 結果としてIPIの応答が遅くなる.最悪の場合IPIを送信したvCPUがスケジューリングされてしまい,より遅延が増大する

そこで,Paravirtualized TLB flushは以下のように動作します.

  • 現在実行中のvCPUに対してはIPIを送信する
  • それ以外のvCPUに対しては次回vCPUがスケジューリングされたときに最初にTLBフラッシュするようにハイパーコールでハイパーバイザに指示する

現在どのvCPUが実行中かどうかはMSR_KVM_STEAL_TIMEから分かります.

以下に開発者による説明があります.

もともと仮想化環境でTLB shootdownが性能的に問題になるというのは,いくつかの研究でも報告されていました.

また,2012年には実際にLKMLでもアイディアが提示されています.

2012年の段階で何故入らなかったのか詳しい議論は追っていませんが,コア数の多いサーバの普及が進んだことで最近はこれらの問題がより鮮明になってきているのではないかと思います.

完全な予想ですがクラウド事業者はこの辺りはパッチ当てて運用してたんじゃないかなぁというような気もします.

Paravirtualized IPI

  • 関連するFeature
    • KVM_FEATURE_PV_SEND_IPI
  • 導入時期

x2APICでIPIを送信する際,ICRというレジスタにアクセスしますが,これはVMEXITが発生します. x2APICでIPIを送信する方法は,physical modeとcluster modeの二種類あり,後者の場合は複数のCPUに一斉にIPIを送ることができます. しかし,実際には前者が主に用いられているようです. この場合,複数のvCPUにIPIを送信する度にVMEXITが発生します.

Paravirtualized IPIでは直接ゲストから逐一IPIを送る代わりに,ハイパーコール(KVM_HC_SEND_IPI)でvCPUに対するIPIをハイパーバイザに依頼します. これにより一回のVMEXITで複数のvCPUにIPIを送ることができます.

この機能に関しても前述のPV TLB Flushと同じ以下の資料に説明があります.

Paravirtualized driver

いわゆるvirtioドライバです.準仮想化というとこのことを思い浮かべる方も多いかもしれません. 複雑な実際のデバイスのエミュレーションをする代わりに,仮想化環境での動作に十分なインタフェースを提供して仮想環境でのI/Oを高速化しようというのが基本的な考えです. また,ホストとゲスト間の共有メモリを利用してデータ転送を効率化することもあります.

以下のようなドライバがあります.

  • ネットワーク
    • virtio-net
    • vhost-net
  • ストレージ
  • その他
    • virtio-balloon

これらのデバイスvirt-managerのインタフェース等からvirtioドライバを追加して,必要に応じてドライバをインストールすれば使えるようになると思います.

KVMのvirtioデバイスの処理に関してはまた別途書こうと思います.

Linuxでの取り扱い

Linuxはブート時にハイパーバイザ上で動作しているかどうかを確認し,ハイパーバイザ上で動作していた場合はそれに応じた初期化処理を実施します.

ハイパーバイザの検知

arch/x86/kernel/setup.c:setup_arch() => kernel/cpu/hypervisor.c:init_hypervisor_platform()

ここでコールバック関数を利用してハイパーバイザの検知をしますが,KVMの場合はarch/x86/kernel/kvm.cで定義されています. 0x40000000のCPUIDが"KVMKVMKVM"であればKVM上で動作していると判断します.

準仮想化機能の利用

初期化時に,kvm_para_has_feature()を使ってそのfeatureが利用できるか確認し,もし利用できたらそれを使うように設定しています. 例えば,PV tlb flushの設定はkvm_setup_pv_tlb_flush()でおこなわれています

ブートオプションで特定の準仮想化機能をオフにできるような感じにはなっていないように見えます.

QEMUでの取り扱い

前回説明したように,KVMにおけるcpuid命令はKVM_SET_CPUID ioctlで制御されます. これを変更することで,ゲストに特定の準仮想化機能を見せないことが可能です. コードの正確な確認はできていませんが,基本的にQEMUはホストが対応している機能はゲストに見せているような気がします.

QEMUで特定の機能をオフにしたい場合は,-cpu host,-kvm-pv-tlb-flushなどと指定すれば対応するCPUIDのfeature flagがクリアされると思います. QEMUが利用するオプションについてはこちらで分かります.

またQEMUのオプションで-cpu host,kvm=off (libvirt的には<kvm><hidden state="on"></kvm>)をすると0x40000000のCPUIDはKVMを隠蔽するので,結果としてKVMの準仮想化機能は利用できなくなります.

まとめ

KVMの準仮想化機能について簡単に説明しました. 2018年にはPV TLB ShootdownやPV Send IPIなどが導入されました. 比較的最近の変更なので,現時点で利用するには自分でカーネル(とQEMU)をコンパイルする必要があるかもしれません. 多コアかつ過剰にオーバコミットしている環境で特に効果があると思われます.

KVMにおけるcpuid命令の取り扱い

前提

x86/Intelの話です.AMDでも多分同様.

cpuid命令の取り扱い

cpuid命令はKVM内で処理されます.

具体的には arch/x86/kvm/vmx.c:handle_cpuid() => arch/x86/kvm/cpuid.c:kvm_emulate_cpuid() => arch/x86/kvm/cpuid.c:kvm_cpuid() => arch/x86/kvm/cpuid.c:kvm_find_cpuid_entry()

ここで,kvm_find_cpuid_entry()で対応するcpuidのエントリがあるか探し,あれば それを返します.

このcpuidのエントリはKVM_SET_CPUIDあるいはKVM_SET_CPUID2 ioctlによって登録します.

KVM_SET_CPUID2はデータを連結リストの形で受け取るので,一回のioctlで複数の cpuidエントリが登録できます.

また,KVM_GET_SUPPORTED_CPUID iotclにより,KVMが実際にサポートするcpuidを取得できます.

QEMUでの取り扱い

target/i386/kvm.c:kvm_arch_init_vcpu()内でcpuidの設定をしています.

例えば,cpu->expose_kvmのとき (-cpu kvm=onのとき) 0x40000000にのクエリに対して"KVMKVMKVM"を返すように設定しています.

本来この領域はcpuid的にはreserved領域です.KVMはゲストにKVMの存在を伝えるために利用しています.

rustのIteratorの実装

関連するトレイト

Iterator

libcore/iter/traits/itetarot.rs

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    ...
}
  • イテレータの関数のためのトレイト
  • next()さえ実装すれば,あとはデフォルト定義が存在

IntoIterator

libcore/iter/traits/collect.rs

pub trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item=Self::Item>;
    fn into_iter(self) -> Self::IntoIter;
}

impl<I: Iterator> IntoIterator for I {
    type Item = I::Item;
    type IntoIter = I;

    fn into_iter(self) -> I {
        self
    }
}
  • IntoIteratorイテレータを得るためのトレイト
  • for _ in x としたとき,xに対してinto_iter()が呼ばれる
  • IteratorにはIntoIteratorが実装されている (単純に自分自身を返すだけ)

Slice ([T])

iter(), iter_mut()

libcore/slice/mod.rs

impl<T> [T] {
    ...
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn iter(&self) -> Iter<T> {
        unsafe {
            let ptr = self.as_ptr();
            assume(!ptr.is_null());

            let end = if mem::size_of::<T>() == 0 {
                (ptr as *const u8).wrapping_add(self.len()) as *const T
            } else {
                ptr.add(self.len())
            };

            Iter {
                ptr,
                end,
                _marker: marker::PhantomData
            }
        }
    }
    ...
}
  • sliceのiter()Iter<T>を返す
    • iter_mut()も同様
  • Iter<T>の定義は以下の通り

libcore/slice/mod.rs

pub struct Iter<'a, T: 'a> {
    ptr: *const T,
    end: *const T, // If T is a ZST, this is actually ptr+len.  This encoding is picked so that
                   // ptr == end is a quick test for the Iterator being empty, that works
                   // for both ZST and non-ZST.
    _marker: marker::PhantomData<&'a T>,
}

macro_rules! iterator {
    ...
        impl<'a, T> Iterator for $name<'a, T> {
            type Item = $elem;

            #[inline]
            fn next(&mut self) -> Option<$elem> {
                // could be implemented with slices, but this avoids bounds checks
                unsafe {
                    assume(!self.ptr.is_null());
                    if mem::size_of::<T>() != 0 {
                        assume(!self.end.is_null());
                    }
                    if is_empty!(self) {
                        None
                    } else {
                        Some(& $( $mut_ )* *self.post_inc_start(1))
                    }
                }
            }
        ...
        }
    ...
}

iterator!{struct Iter -> *const T, &'a T, const, {/* no mut */}, {...
  • Iter<T>に対してIteratorが実装されている
    • 各要素の参照を返す
  • iter()iter_mut()で実装を共通化するためマクロで定義されている

into_iter()

  • iter(), iter_mut()を呼ぶ形で&'a [T], &'a mut [T]に実装
    • let x = [1,2,3];のとき,for loopにおいては,for _ in x.iter()for _ in &xも同じ意味
      • 前者の場合, x.iter()Iteratorを実装するIter<T>を返し,それに対してIntoIteration::into_iter()が呼ばれる
      • 後者の場合は&[T]に対してIntoIteration::into_iter()が呼ばれる.
    • [T]に対してはinto_iter()の実装なし (そもそもsliceで実際に使えるのはshared (&[T]) かmutable (&mut [T]) の形のみ)

libcore/slice/mod.rs

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a [T] {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a mut [T] {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> IterMut<'a, T> {
        self.iter_mut()
    }
}

Array ([T; N])

iter(), iter_mut()

  • coerceによってsliceのiter(), iter_mut()が呼ばれる

into_iter()

  • sliceと同様に,iter(), iter_mut()を呼ぶ形で&'a [T; N], &'a mut [T; N]に実装
    • [T; N]に対する実装はない

libcore/array.rs

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a [T; $N] {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a mut [T; $N] {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> IterMut<'a, T> {
        self.iter_mut()
    }
}

Vec (Vec<T>)

iter(), iter_mut()

  • deref coerceによってsliceのiter(), iter_mut()が呼ばれる

into_iter()

src/liballoc/vec.rs

impl<T> IntoIterator for Vec<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    #[inline]
    fn into_iter(mut self) -> IntoIter<T> {
        unsafe {
            let begin = self.as_mut_ptr();
            assume(!begin.is_null());
            let end = if mem::size_of::<T>() == 0 {
                arith_offset(begin as *const i8, self.len() as isize) as *const T
            } else {
                begin.add(self.len()) as *const T
            };
            let cap = self.buf.cap();
            mem::forget(self);
            IntoIter {
                buf: NonNull::new_unchecked(begin),
                phantom: PhantomData,
                cap,
                ptr: begin,
                end,
            }
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a Vec<T> {
    type Item = &'a T;
    type IntoIter = slice::Iter<'a, T>;

    fn into_iter(self) -> slice::Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a mut Vec<T> {
    type Item = &'a mut T;
    type IntoIter = slice::IterMut<'a, T>;

    fn into_iter(self) -> slice::IterMut<'a, T> {
        self.iter_mut()
    }
}
  • &'a Vec<T>, &'a mut Vec<T>の場合はiter(), iter_mut()を呼ぶ
  • Vec<T>の場合はIntoIter<T>を返す
    • IntoIter<T>は以下の様に定義
    • これにより,Vec<T>では要素そのものをに対してイテレーションすることが可能 (vec自身は消費される)

src/liballoc/vec.rs

#[stable(feature = "rust1", since = "1.0.0")]
pub struct IntoIter<T> {
    buf: NonNull<T>,
    phantom: PhantomData<T>,
    cap: usize,
    ptr: *const T,
    end: *const T,
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        unsafe {
            if self.ptr as *const _ == self.end {
                None
            } else {
                if mem::size_of::<T>() == 0 {
                    // purposefully don't use 'ptr.offset' because for
                    // vectors with 0-size elements this would return the
                    // same pointer.
                    self.ptr = arith_offset(self.ptr as *const i8, 1) as *mut T;

                    // Make up a value of this ZST.
                    Some(mem::zeroed())
                } else {
                    let old = self.ptr;
                    self.ptr = self.ptr.offset(1);

                    Some(ptr::read(old))
                }
            }
        }
    }
    ...
}

Arrayに[T; N]IntoIteratorが実装されていない理由

まとめ

  • trait/struct
    • Iterationトレイト
      • next()を実装することでイテレータとして利用できるようになる
    • IntoIteratorトレイト
      • イテレータが欲しい時にtrait boundとして利用する
      • for loopはIntoIteratorが実装されているものを受け取るようになっている
    • Iter
      • sliceの&T, &mut Tに対するIterationのために存在
    • IntoIter
      • vecのTに対するIterationのために存在
  • 一般にstdでのcollectionでは
  • 現状Arrayに関してはTに対してイテレーションはできない