kleeでパスワードを言い当てる

はじめに

kleeなるものがあると聞き，パスワードの特定をやってみたので備忘録を残す．具体的なところは全く理解できていないので，とりあえず動いたところまで．

解いてみる問題

kleeチュートリアルのUsing symbolic environmentに紹介されているcheck_password()関数をターゲットにしてみた．
この関数はパスワードhelloを入力すると1を，それ以外の場合は0を返す．

password.c

#include <stdio.h>

int check_password(char *buf) {
  if (buf[0] == 'h' && buf[1] == 'e' &&
      buf[2] == 'l' && buf[3] == 'l' &&
      buf[4] == 'o')
    return 1;
  return 0;
}

int main(int argc, char **argv) {
  if (argc < 2)
     return 1;
  
  if (check_password(argv[1])) {
    printf("Password found!\n");
    return 0;
  }

  return 1;
}

チュートリアルでは，コマンドライン引数を含む形でテストケースを生成することを解説しているが，この記事では実際にパスワードを求めることを目標とした．

実際にパスワードを求める

ここからは実際にパスワードをシンボリック実行によって求めていく．

実行するコード

今回使うkleeの関数は2つ．

• klee_make_symbolic: 変数をシンボリックとしてマークする
• klee_assert: C言語のassertと同じ．偽ならそこでプログラムを強制終了する．

サンプルコードではコマンドライン引数char **argvを取っているが，今回はシンボリック実行ができればいいのでchar pass[6]に書き換えている．

password.c

#include <stdio.h>
#include "klee/klee.h"

int check_password(char *buf) {
    if (buf[0] == 'h' && buf[1] == 'e' &&
        buf[2] == 'l' && buf[3] == 'l' &&
        buf[4] == 'o')
        return 1;
    return 0;
}

int main(void) {
    char pass[6];

    klee_make_symbolic(pass, sizeof(pass[0]) * 6, "pass");
    if (check_password(pass)) {
        printf("Password found!\n");
    	klee_assert(0);
        return 0;
    }
    return 1;
}

実行方法

clang実行後にkleeコマンドをたたくだけ．
/home/klee/klee_src/includeの部分は，kleeのパスを各自環境に合わせて指定する．dockerを使っている場合は下の例のままで問題ないと思う．

$ clang -I /home/klee/klee_src/include -emit-llvm -c -g -O0 -Xclang -disable-O0-optnone password.c
$ klee password.bc

実行結果とパスワード

　実行すると下のような結果が出てくる．

この内容からklee-out-0というディレクトリに結果が出力されたことが分かるので覗いてみる．

.ktestというファイルが複数出力されているが，それぞれが1つ1つのテストケースとなっている．この.ktestファイルを見るにはktest-toolコマンドを使う．

　今回実行したコードでは，パスワードが一致したらklee_assertで処理を中断している．ということでテストケースの中で.assert.errが存在するもの(test000005.ktest)を見ればパスワードが得られる．

さいごに

最初に聞いた時，kleeはangrのようにバイナリを渡したら解析してくれるツールなのかなと思っていたが，今回の方法ではソースコードにklee/klee.h等々を追記する手順が必要らしい．バイナリだけしか手元にないときにも簡単に使える方法はないか探してみたい．