retrage.github.io

ccov: printfデバッグを支援するツール

ここではコードカバレッジ計測を元にしたprintfデバッグ支援ツールであるccovを作ったので紹介する.

コードは以下で公開している.

gcov, llvm-covなどはコードカバレッジを測定できるツールである. これらは基本的にOS上で動き,簡単にコンパイラを入れ替えたりログを生成できること前提としている. 一方でOSや組み込みの開発ではデバッガが利用できずprintfデバッグをせざるを得ない場合がある.

printfデバッグでは対象のコードに対して どこまでコードが実行されているかを調べるためにprintfを挿入していく. このときprintfの挿入方法にはいくつかある.

以下のようなコラッツの問題を元にした関数を考える.

void collatz(int n)
{
  while (n != 1) {
    if (n % 2 == 0) {
      n /= 2;
    } else {
      n = 3 * n + 1;
    }
  }
}

一つは二分探索できるように2箇所以上にprintfを挿入していく方法である. この方法では関数collatz()に対して次のようにprintfを挿入する.

void collatz(int n)
{
  while (n != 1) {
    printf("#1\n");
    if (n % 2 == 0) {
      n /= 2;
    } else {
      n = 3 * n + 1;
    }
    printf("#2\n");
  }
}

デバッグ時には#1と#2が表示されているかでこの関数の処理がなされたかを判断する. もし#2が表示されない場合,#1と#2の間の処理において問題が発生したと判断でき, 二分探索の要領でprintfの挿入位置を変えることで問題の箇所を特定できる.

しかし,組み込み開発などではデバイスへのデプロイに時間がかかるため 繰り返しを多く行うこの方法は効率的でない.

もう一つはLLVMでのBasicBlock単位でprintfを挿入していく方法である. BasicBlockは分岐がないInstructionのまとまりの単位である. collatz()への適用例を以下に示す.

void collatz(int n)
{
  printf("#1\n");
  while (n != 1) {
    printf("#2\n");
    if (n % 2 == 0) {
      printf("#3\n");
      n /= 2;
    } else {
      printf("#4\n");
      n = 3 * n + 1;
    }
    printf("#5\n");
  }
  printf("#6\n");
}

この方法ではprintfの挿入数は多いものの,1度に全てのcode pathを網羅することができ, 実行時の表示からどのようなcode pathを通っているかがわかる.

一方で,この方法ではprintfの挿入が煩雑であるという問題がある. 全ての分岐に対してprintfを挿入していく必要があるため人手で行う場合には時間もかかり, また挿入を誤ってしまう場合もありうる. 挿入が煩雑になる例として次のようなコードを考える.

  if (n == 0)
    return;

このコードに人手でprintfを挿入する場合,以下のように変更する必要があり, 1行printfを入れるために3行の変更を行うこととなる.

  if (n == 0) {
    printf("#n\n");
    return;
  }

そこで,このようなprintfの挿入を自動で行うLLVM passであるccovを作成した.

ccovの使い方

__log_coverage()関数の用意

ccovを利用するには以下のような__log_coverage()関数を用意する必要がある.

void __log_coverage(const char *file, const char *func, const int line, const int attr);

各引数はccovによって自動的に与えられるため, ユーザは何らかの形でログを出力する__log_coverage()関数を定義するだけでよい. attrは現在関数の始まりを示すccov_entryと終わりを示すccov_retの2つをサポートしている.

printfを使う場合の定義の例を以下に示す.

#define SIG "#CCOV"

enum ccov_attribute {
  ccov_entry = 0x01,
  ccov_ret = 0x02,
};

void __log_coverage(const char *file, const char *func, const int line, const int attr)
{
  printf("%s:%s:%s:%d", SIG, file, func, line);
  if (attr & ccov_entry)
    printf(":entry");
  if (attr & ccov_ret)
    printf(":ret");
  printf("\n");
}

ログが出力保存ができればどのような定義でも構わないため, printfの代わりにシリアルへの出力を行ったり,何らかの形でエンコードして出力を圧縮してもよい.

ccovのビルドと実行

ccovは以下のようにビルドを行う. これによりccov/build/CCov/libCCov.soが生成される.

$ git clone https://github.com/retrage/ccov.git
$ cd ccov
$ mkdir build
$ cd build
$ cmake ..
$ make

clangでは次のようにccovをロードして有効にする. ccovはLLVM IRの持っているデバッグ情報を利用するため,-gオプションが必要であり, Optimization Level 0で有効になるよう設定されているため-O0オプションが必要となる.

$ clang -g -O0 -Xclang -load -Xclang ~/src/ccov/build/CCov/libCCov.so -c -o main.o main.c

ccovによる実行時出力

先の定義例を用い,ccovを有効にしてビルドしたものを実行すると次のようなログが得られる.

#CCOV:main.c:collatz:10
#CCOV:main.c:collatz:18:ret
#CCOV:main.c:collatz:7:entry

最初の#CCOVはccovにより生成出力された行であることを示し, ファイル名,関数名,行番号が並んでいる.最後のentryretattrの入力に由来する.

この出力をソースコードと比較するだけでもどのようなcode pathを通ったかは分かるものの, 対応する行を見つけるのを簡単にするための簡単なスクリプトを付属している. これを用いると次のような出力が得られる.

    30|    10|  while (n != 1) {
    31|    18|}
    32|     7|void collatz(int n)

左から実行順番号,行番号,対応するコード,となっている. ここではattrの情報を利用していないが,スタックなどを用いて 各関数の開始と終了をトレースするようなスクリプトも考えられる. これらの周辺ツールはあくまで例であり,目的に応じて自作していくのが望ましい.

コードカバレッジ計測の手法

コードカバレッジは主にソフトウェアテストとfuzzingの2種類の文脈で用いられることが多い. ソフトウェアテストでは,コードカバレッジを計測してテストを実行し, テストがどれだけの対象のコードパスを網羅できているかの指標として利用されている. しかし,gcovなどは基本的にユーザ空間でカバレッジ情報を出力できることを前提としているため 組み込みなどでは直接適用することが難しい. なお,過去にgcovをファームウェアに適用した例もある[1]. ここではカバレッジ情報をメモリの特定領域に出力させることであとから結果を取得できるようにしている.

一方,fuzzingのうちgraybox fuzzingではfuzzerの生成した入力を実行したときの コードカバレッジを計測し,その変化を元に次にどのように入力を変化させていくかを決定する. ここではgraybox fuzzingの代表的なfuzzerであるAmerican Fuzzy Lop (AFL)についてみていく. AFLではafl-gccというコンパイラのラッパで対象をコンパイルする. このときアセンブリで条件分岐の命令の前にカバレッジ計測のためのコードを挿入している[2][3]. コードカバレッジ計測の手法としてはやや乱暴であるが,経験的にこの程度の粒度でもよいとのことである.

Limitations

ccovは単純にcode pathを通ったときにログを出力するだけの実装となっており, その前後関係を出力しない. あくまでログの出力順序からどのようなcode pathを通ったかを判別することになっている. このため,ccovをプリエンティブに動作するようなプログラムに対して適用した場合, 複数の異なるコンテキストを持ったログが出力するため正しくcode pathを追跡することができない.

この問題に対して実行時にコンテキストを判別できるような乱数をを生成して コンテキストを追跡できるようにする,という解決方法が考えられる.

参考文献