※Rackサーバの方のUnicornではない.

はじめに

 UnicornQEMUベースの軽量,マルチプラットフォーム・マルチアーキテクチャ・JIT対応のCPUエミュレータ.周辺機器をエミュレーションしないため用途は限られるが,GoやPythonなど複数言語のバインディングを備えている.現在システムセキュリティ分野で最も注目されているOSSのひとつと言っても過言ではなく,AsiaCCS 2016で発表されたROPチェーン解析ツールROPMEMUや,遺伝的アルゴリズムによってROPチェーンを自動生成するツールroperのバックエンドとして用いられたり,Unicornと同じように注目を集めているバイナリ解析ツールangrとの連携が進められたりと,一大コミュニティを形成しつつある.
 コンセプトの説明はBlack Hat USA 2015の発表スライドに譲るとして,ここではその利用方法と内部実装にふれる.

Pythonバインディング

 情報セキュリティに興味があり,セキュリティ関係の仕事に携わりたいという人には,Pythonはうってつけの言語だ.その理由は,リバースエンジニアリングと攻撃コード作成のためのライブラリが充実しているためだ.
       – Justin Seitz『サイバーセキュリティプログラミング———Pythonで学ぶハッカーの思考』序文

 リバースエンジニアリングというタスクにUnicornを用いることを考える.他言語を選ぶ積極的な理由やPythonへのアレルギーがなければ,他のライブラリとの連携も考慮して,Pythonバインディングを活用すべきだろう.

エミュレーション

 最もシンプルな用例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#!/usr/bin/env python
#-*- coding:utf-8 -*-
# unicorn/bindings/python/sample_x86.pyを抜粋・改変
from __future__ import print_function # Python 2.7を利用
from unicorn import *
from unicorn.x86_const import *
# エミュレーション対象の機械語
X86_CODE32 = b"\x41\x4a" # INC ecx; DEC edx
# 各基本ブロックに対するコールバック
def hook_block(uc, address, size, user_data):
print(">>> Tracing basic block at 0x%x, block size = 0x%x" %(address, size))
# 各命令に対するコールバック
def hook_code(uc, address, size, user_data):
print(">>> Tracing instruction at 0x%x, instruction size = %u" %(address, size))
# x86 32bitのコードをエミュレーション
def test_i386():
print("Emulate i386 code")
try:
# x86-32bitモードでエミュレータを初期化
mu = Uc(UC_ARCH_X86, UC_MODE_32)
# エミュレーション用に2MBのメモリを割り当て
mu.mem_map(ADDRESS, 2 * 1024 * 1024)
# 割り当てられたメモリに機械語を書き込み
mu.mem_write(ADDRESS, X86_CODE32)
# レジスタ初期化
mu.reg_write(UC_X86_REG_ECX, 0x1234) # エミュレーション中に加算される
mu.reg_write(UC_X86_REG_EDX, 0x7890) # エミュレーション中に減算される
# 各基本ブロックに対するコールバックを設定
mu.hook_add(UC_HOOK_BLOCK, hook_block)
# 各命令に対するコールバックを設定
mu.hook_add(UC_HOOK_CODE, hook_code)
# エミュレーション開始
mu.emu_start(ADDRESS, ADDRESS + len(X86_CODE32))
# レジスタの表示
print(">>> Emulation done. Below is the CPU context")
r_ecx = mu.reg_read(UC_X86_REG_ECX)
r_edx = mu.reg_read(UC_X86_REG_EDX)
print(">>> ECX = 0x%x" %r_ecx)
print(">>> EDX = 0x%x" %r_edx)
# メモリから命令列を読む
tmp = mu.mem_read(ADDRESS, 2)
print(">>> Read 2 bytes from [0x%x] =" %(ADDRESS), end="")
for i in tmp:
print(" 0x%x" %i, end="")
print("")
except UcError as e:
print("ERROR: %s" % e)
if __name__ == '__main__':
test_i386()

 これを実行すると次のような出力が得られる.

1
2
3
4
5
6
7
8
Emulate i386 code
>>> Tracing basic block at 0x1000000, block size = 0x2
>>> Tracing instruction at 0x1000000, instruction size = 1
>>> Tracing instruction at 0x1000001, instruction size = 1
>>> Emulation done. Below is the CPU context
>>> ECX = 0x1235
>>> EDX = 0x788f
>>> Read 2 bytes from [0x1000000] = 0x41 0x4a

 はい.
 なおエミュレーション時に各命令のトレースを得たければ,同じ開発陣による逆アセンブラCapstoneのPythonバインディングを併用して (詳細は割愛) 次のようなフックを用意すればよい:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
...
from capstone import *
...
class SimpleEngine:
def __init__(self):
self.capmd = Cs(CS_ARCH_X86, CS_MODE_32) # アーキテクチャ指定
def disas_single(self, data):
for i in self.capmd.disasm(data, 16): # 逆アセンブル
print("\t%s\t%s" % (i.mnemonic, i.op_str))
break
disasm = SimpleEngine()
...
def hook_code(uc, address, size, user_data):
print(">>> Tracing instruction at 0x%x, instruction size = %u, " %(address, size), end="")
# メモリから実行される命令を読む
ins = uc.mem_read(address, size)
disasm.disas_single(str(ins))

 実行すると命令のトレースが得られる.

1
2
3
4
...
>>> Tracing instruction at 0x1000000, instruction size = 1, inc ecx
>>> Tracing instruction at 0x1000001, instruction size = 1, dec edx
...

 このように,Unicornではプラグイン側のエントリポイントからQEMUの機能を呼び出していくことになる.

Pythonバインディングの内部

 この内部では,ctypesによる共有ライブラリのロードが行われている.unicorn/bindings/python/unicorn/unicorn.pyを見よう:

1
2
3
4
5
6
7
8
9
10
11
12
13
for _lib in _all_libs:
try:
if _lib == "unicorn.dll":
for dll in _all_windows_dlls: # load all the rest DLLs first
_lib_file = os.path.join(_lib_path, dll)
if os.path.exists(_lib_file):
ctypes.cdll.LoadLibrary(_lib_file)
_lib_file = os.path.join(_lib_path, _lib)
_uc = ctypes.cdll.LoadLibrary(_lib_file)
_found = True
break
except OSError:
pass

 ここで_ucunicorn.dll (環境によって異なるがいずれにせよ共有ライブラリ) がロードされている.
 さて,これまで利用してきた関数のプロトタイプ宣言はunicorn/bindings/python/unicorn/unicorn.pyにある:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# setup all the function prototype
def _setup_prototype(lib, fname, restype, *argtypes):
getattr(lib, fname).restype = restype
getattr(lib, fname).argtypes = argtypes
ucerr = ctypes.c_int
uc_engine = ctypes.c_void_p
uc_hook_h = ctypes.c_size_t
_setup_prototype(_uc, "uc_version", ctypes.c_uint, ctypes.POINTER(ctypes.c_int), ctypes.POINTER(ctypes.c_int))
_setup_prototype(_uc, "uc_arch_supported", ctypes.c_bool, ctypes.c_int)
_setup_prototype(_uc, "uc_open", ucerr, ctypes.c_uint, ctypes.c_uint, ctypes.POINTER(uc_engine))
_setup_prototype(_uc, "uc_close", ucerr, uc_engine)
_setup_prototype(_uc, "uc_strerror", ctypes.c_char_p, ucerr)
_setup_prototype(_uc, "uc_errno", ucerr, uc_engine)
_setup_prototype(_uc, "uc_reg_read", ucerr, uc_engine, ctypes.c_int, ctypes.c_void_p)
_setup_prototype(_uc, "uc_reg_write", ucerr, uc_engine, ctypes.c_int, ctypes.c_void_p)
_setup_prototype(_uc, "uc_mem_read", ucerr, uc_engine, ctypes.c_uint64, ctypes.POINTER(ctypes.c_char), ctypes.c_size_t)
_setup_prototype(_uc, "uc_mem_write", ucerr, uc_engine, ctypes.c_uint64, ctypes.POINTER(ctypes.c_char), ctypes.c_size_t)
_setup_prototype(_uc, "uc_emu_start", ucerr, uc_engine, ctypes.c_uint64, ctypes.c_uint64, ctypes.c_uint64, ctypes.c_size_t)
_setup_prototype(_uc, "uc_emu_stop", ucerr, uc_engine)
_setup_prototype(_uc, "uc_hook_del", ucerr, uc_engine, uc_hook_h)
_setup_prototype(_uc, "uc_mem_map", ucerr, uc_engine, ctypes.c_uint64, ctypes.c_size_t, ctypes.c_uint32)
_setup_prototype(_uc, "uc_mem_map_ptr", ucerr, uc_engine, ctypes.c_uint64, ctypes.c_size_t, ctypes.c_uint32, ctypes.c_void_p)
_setup_prototype(_uc, "uc_mem_unmap", ucerr, uc_engine, ctypes.c_uint64, ctypes.c_size_t)
_setup_prototype(_uc, "uc_mem_protect", ucerr, uc_engine, ctypes.c_uint64, ctypes.c_size_t, ctypes.c_uint32)
_setup_prototype(_uc, "uc_query", ucerr, uc_engine, ctypes.c_uint32, ctypes.POINTER(ctypes.c_size_t))
# uc_hook_add is special due to variable number of arguments
_uc.uc_hook_add = _uc.uc_hook_add
_uc.uc_hook_add.restype = ucerr
UC_HOOK_CODE_CB = ctypes.CFUNCTYPE(None, uc_engine, ctypes.c_uint64, ctypes.c_size_t, ctypes.c_void_p)
UC_HOOK_MEM_INVALID_CB = ctypes.CFUNCTYPE(
ctypes.c_bool, uc_engine, ctypes.c_int,
ctypes.c_uint64, ctypes.c_int, ctypes.c_int64, ctypes.c_void_p
)
UC_HOOK_MEM_ACCESS_CB = ctypes.CFUNCTYPE(
None, uc_engine, ctypes.c_int,
ctypes.c_uint64, ctypes.c_int, ctypes.c_int64, ctypes.c_void_p
)
UC_HOOK_INTR_CB = ctypes.CFUNCTYPE(
None, uc_engine, ctypes.c_uint32, ctypes.c_void_p
)
UC_HOOK_INSN_IN_CB = ctypes.CFUNCTYPE(
ctypes.c_uint32, uc_engine, ctypes.c_uint32, ctypes.c_int, ctypes.c_void_p
)
UC_HOOK_INSN_OUT_CB = ctypes.CFUNCTYPE(
None, uc_engine, ctypes.c_uint32,
ctypes.c_int, ctypes.c_uint32, ctypes.c_void_p
)
UC_HOOK_INSN_SYSCALL_CB = ctypes.CFUNCTYPE(None, uc_engine, ctypes.c_void_p)

 メモリ・レジスタを読み書きできることがわかる.
 さきほどは基本ブロック・命令単位のコールバック関数——フック——を設置した.その他のフックも次のように書ける:

1
2
3
4
5
6
7
8
9
10
11
12
mu.hook_add(UC_HOOK_BLOCK, hook_block) # 基本ブロック単位
mu.hook_add(UC_HOOK_CODE, hook_code) # 命令単位
mu.hook_add(UC_HOOK_CODE, hook_code, None, ADDRESS, ADDRESS+20) # 指定範囲[ADDRESS, ADDRESS+20]の全命令
mu.hook_add(UC_HOOK_INSN, hook_in, None, 1, 0, UC_X86_INS_IN) # IN命令
mu.hook_add(UC_HOOK_INSN, hook_out, None, 1, 0, UC_X86_INS_OUT) # OUT命令
mu.hook_add(UC_HOOK_MEM_WRITE, hook_mem_access) # メモリ書き込み
mu.hook_add(UC_HOOK_MEM_READ, hook_mem_access) # メモリ読み込み
mu.hook_add(UC_HOOK_MEM_READ | UC_HOOK_MEM_WRITE, hook_mem_access) # その両方
mu.hook_add(UC_HOOK_MEM_READ_UNMAPPED | UC_HOOK_MEM_WRITE_UNMAPPED, hook_mem_invalid) # 無効なメモリアクセス
mu.hook_add(UC_HOOK_INSN, hook_syscall, None, 1, 0, UC_X86_INS_SYSCALL) # システムコール
mu.hook_add(UC_HOOK_INTR, hook_intr) # 割り込み
...

 こうしたフックや,これまで用いてきたレジスタやメモリの読み書き・エミュレーションといった機能はUcクラスのメソッドとして用意されている:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
class Uc(object):
def __init__(self, arch, mode):
# verify version compatibility with the core before doing anything
(major, minor, _combined) = uc_version()
if major != uc.UC_API_MAJOR or minor != uc.UC_API_MINOR:
self._uch = None
# our binding version is different from the core's API version
raise UcError(uc.UC_ERR_VERSION)
self._arch, self._mode = arch, mode
self._uch = ctypes.c_void_p()
status = _uc.uc_open(arch, mode, ctypes.byref(self._uch))
if status != uc.UC_ERR_OK:
self._uch = None
raise UcError(status)
# internal mapping table to save callback & userdata
self._callbacks = {}
self._ctype_cbs = {}
self._callback_count = 0
...
# emulate from @begin, and stop when reaching address @until
def emu_start(self, begin, until, timeout=0, count=0):
status = _uc.uc_emu_start(self._uch, begin, until, timeout, count)
if status != uc.UC_ERR_OK:
raise UcError(status)
...
# return the value of a register
def reg_read(self, reg_id):
if self._arch == uc.UC_ARCH_X86:
if reg_id in [x86_const.UC_X86_REG_IDTR, x86_const.UC_X86_REG_GDTR, x86_const.UC_X86_REG_LDTR, x86_const.UC_X86_REG_TR]:
reg = uc_x86_mmr()
status = _uc.uc_reg_read(self._uch, reg_id, ctypes.byref(reg))
if status != uc.UC_ERR_OK:
raise UcError(status)
return reg.selector, reg.base, reg.limit, reg.flags
if reg_id in range(x86_const.UC_X86_REG_FP0, x86_const.UC_X86_REG_FP0+8):
reg = uc_x86_float80()
status = _uc.uc_reg_read(self._uch, reg_id, ctypes.byref(reg))
if status != uc.UC_ERR_OK:
raise UcError(status)
return reg.mantissa, reg.exponent
# read to 64bit number to be safe
reg = ctypes.c_int64(0)
status = _uc.uc_reg_read(self._uch, reg_id, ctypes.byref(reg))
if status != uc.UC_ERR_OK:
raise UcError(status)
return reg.value
...
# read data from memory
def mem_read(self, address, size):
data = ctypes.create_string_buffer(size)
status = _uc.uc_mem_read(self._uch, address, data, size)
if status != uc.UC_ERR_OK:
raise UcError(status)
return bytearray(data)
...
# add a hook
def hook_add(self, htype, callback, user_data=None, begin=1, end=0, arg1=0):
_h2 = uc_hook_h()
# save callback & user_data
self._callback_count += 1
self._callbacks[self._callback_count] = (callback, user_data)
cb = None
if htype == uc.UC_HOOK_INSN: # 特定の命令に応じた内部処理
insn = ctypes.c_int(arg1)
if arg1 == x86_const.UC_X86_INS_IN: # IN命令
cb = ctypes.cast(UC_HOOK_INSN_IN_CB(self._hook_insn_in_cb), UC_HOOK_INSN_IN_CB)
if arg1 == x86_const.UC_X86_INS_OUT: # OUT命令
cb = ctypes.cast(UC_HOOK_INSN_OUT_CB(self._hook_insn_out_cb), UC_HOOK_INSN_OUT_CB)
if arg1 in (x86_const.UC_X86_INS_SYSCALL, x86_const.UC_X86_INS_SYSENTER): # SYSCALL/SYSENTER命令
cb = ctypes.cast(UC_HOOK_INSN_SYSCALL_CB(self._hook_insn_syscall_cb), UC_HOOK_INSN_SYSCALL_CB)
status = _uc.uc_hook_add(
self._uch, ctypes.byref(_h2), htype, cb,
ctypes.cast(self._callback_count, ctypes.c_void_p),
ctypes.c_uint64(begin), ctypes.c_uint64(end), insn
)
elif htype == uc.UC_HOOK_INTR: # 割り込み
cb = ctypes.cast(UC_HOOK_INTR_CB(self._hook_intr_cb), UC_HOOK_INTR_CB)
status = _uc.uc_hook_add(
self._uch, ctypes.byref(_h2), htype, cb,
ctypes.cast(self._callback_count, ctypes.c_void_p),
ctypes.c_uint64(begin), ctypes.c_uint64(end)
)
else:
if htype in (uc.UC_HOOK_BLOCK, uc.UC_HOOK_CODE): # 基本ブロック・命令単位
# set callback with wrapper, so it can be called
# with this object as param
cb = ctypes.cast(UC_HOOK_CODE_CB(self._hookcode_cb), UC_HOOK_CODE_CB)
status = _uc.uc_hook_add(
self._uch, ctypes.byref(_h2), htype, cb,
ctypes.cast(self._callback_count, ctypes.c_void_p),
ctypes.c_uint64(begin), ctypes.c_uint64(end)
)
elif htype & (uc.UC_HOOK_MEM_READ_UNMAPPED | # 無効なメモリアクセス
uc.UC_HOOK_MEM_WRITE_UNMAPPED |
uc.UC_HOOK_MEM_FETCH_UNMAPPED |
uc.UC_HOOK_MEM_READ_PROT | # 保護された領域へのメモリアクセス
uc.UC_HOOK_MEM_WRITE_PROT |
uc.UC_HOOK_MEM_FETCH_PROT):
cb = ctypes.cast(UC_HOOK_MEM_INVALID_CB(self._hook_mem_invalid_cb), UC_HOOK_MEM_INVALID_CB)
status = _uc.uc_hook_add(
self._uch, ctypes.byref(_h2), htype, cb,
ctypes.cast(self._callback_count, ctypes.c_void_p),
ctypes.c_uint64(begin), ctypes.c_uint64(end)
)
else: # メモリ読み書き
cb = ctypes.cast(UC_HOOK_MEM_ACCESS_CB(self._hook_mem_access_cb), UC_HOOK_MEM_ACCESS_CB)
status = _uc.uc_hook_add(
self._uch, ctypes.byref(_h2), htype, cb,
ctypes.cast(self._callback_count, ctypes.c_void_p),
ctypes.c_uint64(begin), ctypes.c_uint64(end)
)
# save the ctype function so gc will leave it alone.
self._ctype_cbs[self._callback_count] = cb
if status != uc.UC_ERR_OK:
raise UcError(status)
return _h2.value

おわりに

 PythonからUnicornを利用する方法を紹介した.
 結局のところctypesでラップされており,こうした機能がどのようにして実行されるのかは本体のコードを読まなければ理解できない.そういうわけで,そのうちUnicorn本体の実装を読んでいくことにする.

はじめに

2015.08.11~15にわたって開催されたセキュリティ・キャンプ全国大会 2015に解析トラックの講師として参加した.講義では「仮想化技術を用いてマルウェア解析」と題して,QEMUをベースに開発が行われているDECAFという解析プラットフォームを用いて演習を行った.

講義資料

講義内容

演習では実際のマルウェアに用いられている解析妨害機能を備えたサンプルプログラムを扱った.素のDECAFには解析妨害機能への対策が施されていない.そこで,受講者にはDECAFのプラグインを拡張し,対策手法を実装して頂いた.
演習で用いたプログラムはGitHub上で公開している.

  • 解析妨害機能を備えたサンプルプログラム
  • DECAFプラグインのひな形

ひな形にある通り,IsDebuggerPresent()をフックするDECAFプラグインは以下のように書ける.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static DECAF_Handle isdebuggerpresent_handle = DECAF_NULL_HANDLE;
typedef struct {
uint32_t call_stack[1]; //paramters and return address
DECAF_Handle hook_handle;
} IsDebuggerPresent_hook_context_t;
/*
* BOOL IsDebuggerPresent(VOID);
*/
static void IsDebuggerPresent_ret(void *param)
{
IsDebuggerPresent_hook_context_t *ctx = (IsDebuggerPresent_hook_context_t *)param;
hookapi_remove_hook(ctx->hook_handle);
DECAF_printf("EIP = %08x, EAX = %d\n", cpu_single_env->eip, cpu_single_env->regs[R_EAX]);
free(ctx);
}
static void IsDebuggerPresent_call(void *opaque)
{
DECAF_printf("IsDebuggerPresent ");
IsDebuggerPresent_hook_context_t *ctx = (IsDebuggerPresent_hook_context_t*)malloc(sizeof(IsDebuggerPresent_hook_context_t));
if(!ctx) return;
DECAF_read_mem(NULL, cpu_single_env->regs[R_ESP], 4, ctx->call_stack);
ctx->hook_handle = hookapi_hook_return(ctx->call_stack[0], IsDebuggerPresent_ret, ctx, sizeof(*ctx));
}
static void geteip_loadmainmodule_callback(VMI_Callback_Params* params)
{
if(strcmp(params->cp.name,targetname) == 0)
{
DECAF_printf("Process %s you spcecified starts \n", params->cp.name);
target_cr3 = params->cp.cr3;
isdebuggerpresent_handle = hookapi_hook_function_byname("kernel32.dll", "IsDebuggerPresent", 1, target_cr3, IsDebuggerPresent_call, NULL, 0);
}
}

現在のプロセスがデバッガのコンテキストで実行されていない場合,IsDebuggerPresent()は0を返す.ここで,IsDebuggerPresent()の戻り値を0にするには,モジュール(この場合はkernel32.dll)から戻る段階でeaxを書き換えてやればよい.

1
2
3
4
5
6
7
8
static void IsDebuggerPresent_ret(void *param)
{
IsDebuggerPresent_hook_context_t *ctx = (IsDebuggerPresent_hook_context_t *)param;
hookapi_remove_hook(ctx->hook_handle);
cpu_single_env->regs[R_EAX] = 0; // 追加
DECAF_printf("EIP = %08x, EAX = %d\n", cpu_single_env->eip, cpu_single_env->regs[R_EAX]);
free(ctx);
}

このようにDECAFのプラグインを書くことで,ゲストOSに解析用のエージェントを挿入することなくAPIの戻り値を書き換えることができる.
APIの引数を書き換えたい場合はモジュールに入る段階でコンテキスト構造体のcall_stack[]を書き換えてやればよい.

おわりに

受講者にサンドボックス開発の楽しさと難しさを実感してもらえたなら,講師として冥利に尽きる.
サンプルプログラムには4種類の解析妨害機能を実装しており,APIフックで対処できるのはうち前半2つだけとなっている.限られた演習時間の制約上,3つ目以降の解析妨害機能を回避できた受講者はいなかった.解析トラックリーダーの岩村さんから,受講者の2割がギリギリ解けないような問題を作るようにと仰せつかっていたが,やや意地悪な問題設定だったと思う.
なお,今回は拙作のサンプルを用いたが,より多くの解析妨害機能を備えたOSSにpafishがある.pafishはBackdoor.Win32.Agent.dkbp(MD5: de1af0e97e94859d372be7fcf3a5daa5)など一部のマルウェアに流用されている.

はじめに

QEMUは動的バイナリ変換を用いた完全仮想化式のハイパーバイザである.
QEMUは実行対象の命令列を逆アセンブルし,いちど中間表現に変換したうえで,ホストのアーキテクチャの命令列に変換して実行する.これによりQEMUは異なるアーキテクチャのバイナリを実行することができる.
しかしQEMUは遅かったため,アクセラレータとしてkqemuが開発された.
kqemuはユーザーモードのコードをホストのCPUに実行させる準仮想化ドライバであり,やがてKVMへと変貌を遂げた.さらにKVMはハードウェアによる仮想化支援機能を用いることで,さらなる高速化を実現した.もはやKVMにおいてQEMUはハードウェアのエミュレーションにしか用いられていない.
かわいそうなQEMU!
しかしQEMUの活躍する場面はいまだ多く残されている.たとえばマルウェア解析で.
それでも遅いのは困りものだ.QEMUはどこが遅いのだろうか.
ここではperfを用いてQEMUのボトルネックを雑に特定する.

実験

今回はARMエミュレーションについて調査した.ホスト・ゲストともOSにはUbuntu 12.04(3.2.0-23-generic)を用いた.perfでQEMUのプロファイリングを行っている間,ゲストではgccを用いてコンパイルを実行した.

  • ARM版Ubuntu 12.04のインストール

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # sudo apt-get install qemu
    # wget http://odroid.us/odroid/users/osterluk/qemu-example/qemu-example.tgz
    # tar xzf qemu-example.tgz ./zImage
    # wget http://releases.linaro.org/12.04/ubuntu/precise-images/developer/linaro-precise-developer-20120426-86.tar.gz
    # tar xzf linaro-precise-developer-20120426-86.tar.gz
    # qemu-img create -f raw rootfs.img 3G
    # mkfs.ext3 rootfs.img
    # mkdir mnt
    # sudo mount -o loop rootfs.img mnt
    # rsync -a binary/boot/filesystem.dir/ mnt/
    # sudo umount mnt
  • QEMUのビルド

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # sudo apt-get build-dep qemu
    # git clone git://git.qemu-project.org/qemu.git
    # cd qemu
    # git log | grep '^commit' | head -1 | awk '{print $2}'
    6169b60285fe1ff730d840a49527e721bfb30899
    # git submodule update --init dtc
    # git submodule update --init pixman
    # ./configure --extra-ldflags=-pg --target-list=arm-softmmu
    # make
  • perfのインストール

    1
    2
    # sudo apt-get install linux-tools
    # sudo echo 0 > /proc/sys/kernel/perf_event_paranoid
  • perfによるプロファイリング

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # perf record -a -g -F100000 qemu/arm-softmmu/qemu-system-arm -M vexpress-a9 -m 512 -kernel zImage -sd rootfs.img -append "root=/dev/mmcblk0 rw physmap.enabled=0 console=ttyAMA0" -monitor stdio
    WARNING: Image format was not specified for '../../rootfs.img' and probing guessed raw.
    Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.
    Specify the 'raw' format explicitly to remove the restrictions.
    QEMU 2.3.90 monitor - type 'help' for more information
    (qemu) audio: Could not init `oss' audio driver
    (qemu) q
    [ perf record: Woken up 37 times to write data ]
    [ perf record: Captured and wrote 9.465 MB perf.data (~413514 samples) ]
    Failed to open /tmp/perf-6993.map, continuing without symbols
    Failed to open [vmxnet], continuing without symbols
    Failed to open [vmci], continuing without symbols
    Failed to open [vsock], continuing without symbols
    no symbols found in /bin/dash, maybe install a debug package?
    no symbols found in /usr/bin/xargs, maybe install a debug package?
    no symbols found in /usr/bin/updatedb.mlocate, maybe install a debug package?
    no symbols found in /usr/bin/dpkg-query, maybe install a debug package?
  • Flame Graphsによる可視化

    1
    2
    3
    4
    # wget https://raw.githubusercontent.com/brendangregg/FlameGraph/master/stackcollapse-perf.pl
    # wget https://raw.githubusercontent.com/brendangregg/FlameGraph/master/flamegraph.pl
    # perf script> perf_data.txt
    # perl stackcollapse-perf.pl perf_data.txt|perl flamegraph.pl --title "Flame Graphs - qemu-system-arm" > flamegraphs-qemu-system-arm.svg

perfの結果をFlame Graphsを用いて可視化すると下図のようになった.Flame GraphsはUSENIX LISA’2013にて発表された可視化ツールである.

x軸は時系列,y軸はコールスタックを意味する.横幅が広く上位に位置する関数がボトルネックであるといえる.
よってボトルネックはclear_page()すなわちTCGの各関数で発生しているページフォルトである.

おわりに

ページフォルトだけは勘弁してほしい.

参考文献

Dynamic Binary Instrumentation

Dynamic Binary Instrumentation(DBI)とは,実行中のプログラムにコードを挿入する技術である.
その目的は,プログラムの性能評価であったり,アーキテクチャのシミュレーションであったり,プログラムのデバッグであったり,プログラムのsheparding(ポリシを用いたセキュリティ制限)であったり,プログラムの最適化であったり,テイント解析などのデータフロー解析であったり,リバースエンジニアリングであったり,マルウェア解析であったり,……と多岐にわたっている.
デバッガとDBIを区別することは難しく,ニュアンスの問題になってしまうが,DBIはより「挿入するコードがプログラマブルであること」を重視している.また,instrumentation(名詞)/instrument(動詞)という語は,コードの挿入を通してプログラムの情報を取得したり,プログラムを制御したりといったニュアンスを含んでいる.
DBIのメリットとして,言語に依存しないこと,古いソフトウェアに対しても適用できること,再コンパイルの必要がないこと,動的に生成されるコードを扱うことができること,実行中のプロセスにアタッチできることが挙げられる.

Pin

Intelによって開発されているPinは,DBIフレームワークの中でも最も成功している一つであり,そのAPIの数は450種類を越える.
Pinにおけるinstrumentationの手法は,コードの実行時にinstrumentするjust-in-time Instrumentation(JITI)と,イメージ(実行ファイルや共有ライブラリ,構造体)のロード時にinstrumentするahead-of-time-insturumentation(AOTI)の二種類に大別される.
これらのinstrumentにあたって,Pinは解析対象のプログラムにpinvm.dllを挿入する.

JITI

JIITは以下の三種類を単位として行うことができる.

Instruction Level

第一に,最も低い粒度として,命令単位のinstrumentationがサポートされている.
これは,INS_AddInstrumentFunctionのコールバックとして実現される.関連するAPIは,Pin 2.1.3の時点で142種類存在する.

Basic Block Level(BBL)

第二に,Basic Block(BB)単位のinstrumentationがサポートされている.
ここでのBBとは,一つの入口と一つの出口を持ち,内部に分岐を含まない命令列のことであり,コンパイラ最適化におけるそれと同義である.Pinでは,BBL_InsHeadBBL_InsTailBBL_NextBBL_Prevといった関数を用いてBBの有向グラフを操作することができる.一方でBBL_AddInstrumentationFunctionのコールバックは存在しない.関連するAPIは,Pin 2.1.3の時点で14種類存在する.

Trace Level

第三に,Trace単位のinstrumentationがサポートされている.
Traceとは,Pin独自の単位であり,分岐命令を入り口とし,無条件分岐(jmp, call, retなど)を出口とする命令列のことである.つまり,Traceは複数のBBを含みうる.これは,TRACE_AddInstrumentFunctionのコールバックとして実現される.関連するAPIは,Pin 2.1.3の時点で14種類存在する.
Pinでは,objdumpなどと同様に線型分析法によってバイナリを逆アセンブルし,Traceを取得する.ここで,JITIに用いるVMをトラップすることなく別のTraceに分岐を行うためのtrace-linking optimization[PDF]が行われる.そのため,Trace単位のinstrumentationが命令単位のinstrumentationよりも高速になる場合がある.

AOTI

AOTIは以下の二種類を単位として行うことができる.

IMG instrumentation

第一に,IMG単位のinstrumentationがサポートされている.
IMGは,特定の実行ファイルないし共有ライブラリ,構造体に相当する単位である.これは,IMG_AddInstrumentFunction APIによって実現される.また,IMGのセクション(SEC)についてもinstrumentを行うことができる.関連するAPIは,IMGについて27種類,SECについて16種類が存在する.

RTN instrumentation

第二に,RTN単位のinstrumentationがサポートされている.
RTNとは関数(Routine)に相当する単位である.これは,RTN_AddInstrumentFunction APIによって実現される.関連するAPIは,Pin 2.1.3の時点で39種類存在する.

Transparency

このように様々な機能を備えるPinだが,マルウェア解析においてはどれほど有用なのだろうか.
Pinのinstrumentationは,素朴なDLLインジェクションによって成り立っており,Anti-Debuggingについては考えられていない.そのためPinは,親プロセス,引数,ロードされるpinvm.dll, エクスポート関数であるCharmVersionC, ZwAllocateVirtualMemoryの実行権限,KiUserApcDispatcher, KiUserCallbackDispatcher, KiUserExceptionDispatcher, LdrInitializeThunkのインラインフック,命令のパターン,セクション名,FSTENV命令,FSAVE命令,FXSAVE命令,……といった様々な要素から検出される危険性を孕んでいる.
これらは,eXaitを用いてテストできる.なお,筆者の環境ではint2e/SYSENTERについてfalse positiveが発生した.
Pinを検出するマルウェアの存在は寡聞にして知らないが,Pinをマルウェア解析に用いるのであれば,現状の構造は不適切である.
Anti-Debuggingのイタチごっこから脱するためには,エージェントをゲストOSに挿入するin-VMではなく,エージェントをゲストOSに挿入しないout-of-VMな解析環境でなければならない.

QEMU

さらにPinにはカーネルへのinstrumentationが不可能であるという欠点が存在する.
翻ってQEMUは,フルシステムエミュレーションを行うため,アーキテクチャに依存することなくカーネルへのinstrumentationを行うことができる.しかしながら,QEMUのソースコードは難解であり,PinのようにユーザーフレンドリーなAPIが提供されていない.QEMUはC言語によるメタプログラミングとオブジェクト指向の良質なサンプルであるとも言えるが,できることなら避けて通りたい道である.

TEMU

QEMUにテイント解析機能を搭載し,これまで多くの研究で用いられてきたTEMUは,QEMUのソースコードを理解するための労力を削減することに成功した(と,後述するPEMUの論文にすら書かれている)が,APIの充実度はPinに劣っている.また,カーネルモジュールをゲストOSに挿入する必要があり,マルウェアから検出される可能性があること,いまや時代遅れのQEMU 0.9.1をベースとしていることから,現代的なマルウェア解析環境の候補からは外れつつある.
後継のDECAFはQEMU 1.0.0をベースとしており,カーネルモジュールを必要としないものの,APIの充実度はTEMUと変わらない.

PEMU

こうした流れを汲んで開発されたのが,VEE’15にて新たに発表されたPEMUである.嬉しい事にオープンソースとして提供されている.
Pinはin-VMであり,マルウェアの解析やカーネルへのinstrumentationに適さない.QEMUやTEMUはout-of-VMだが,Pinほど充実したAPIを用いることができない.そこでPEMUは,両者の利点と欠点を踏まえた上で,以下の四点を目的として開発された.

  1. Rich APIs
    • Pinの既存APIをそのまま流用できること
  2. Cross-OS
    • WindowsとLinuxをサポート
  3. Strong Isolation
    • ゲストOSのRing 3やRing 0ではなく,out-of-VM(Ring -1)から監視(VM Introspection)を行うこと
  4. VM Introspection
    • ゲストOSのプロセスやカーネルのセマンティクス情報を取得するAPIを提供すること

これらを達成するため,PEMUはQEMUの動的バイナリ変換器Tiny Code Generator(TCG)に手を加えてPin APIのサポートを追加した.

Instrumentation Engine

さて,PEMUにおけるinstrumentationはどのようになっているのだろうか.
問題となるのは,QEMUとPinとの差異である.QEMUは命令とBB単位でしかinstrumentできず,PinにおけるTrace単位をサポートしていない.また,PEMUのベースとなっているQEMU 1.5.3では,BBの数が640までと制限されている.
そこで,PEMUではBBとTraceを対応付けるTRACE Constructorと,PinのAPIを通じてinstrumentするCode Injectorが導入された.

TRACE Constructor

TRACE Constructorは,複数のBBを組み合わせてTraceの単位に抽象化するものである.
まずXED2ライブラリを用いて,ゲストの実行前にQEMUでBBの先頭から条件分岐命令まで逆アセンブルを行う(/target-i386/PEMU/DISAS.c).スワップされたか,ロードされていない命令については,ページフォルトを通じて取得する.さらに,コードを挿入する命令の位置をglobal hooking point hash-table(HPHT)にキャッシュする(/target-i386/PEMU/hashTable.c).
ここにおけるアルゴリズムは以下のようになっている.

まず,Trace単位の開始アドレスであるPCの度にXED2を呼び出し,PCをTPCという保存領域に保存する.次に,全命令を逆アセンブルし,命令単位のinstrumentationが必要な場合はそのアドレスをHPHTに保存する.さらに,無条件分岐の度にBBとTraceを対応付け,BB単位のinstrumentationが必要な場合はそのアドレスをHPHTに保存する.そして,新しいBBを割り当て,次のTrace単位が始まるアドレスを探す.Trace単位のinstrumentationが必要な場合はそのアドレスをHPHTに保存する.そして,さらなるTraceを逆アセンブルしていくといった仕組みになる.

Code Injector

TraceとBBの対応が取れた後は,QEMUのTCGが提供するtcg_gen_helperを用いてHPHTを参照し,instrumentを行えばよい(/target-i386/PEMU/pemu_hook_helper.c).
IMGやSEC単位のinstrumentはmallocなどの引数を確認する(セマンティクス情報を復元する)ことで実現している.
全体像は以下のようになる.

Introspection Engine

PEMUでは,Page Global Directory(PGD)とCR3レジスタの対応を用いてプロセスの識別を行う(target-i386/PEMU/pemu_helper.h).ここでは,プロセス作成時に発生するCR3レジスタへのMOVを検出して利用する.終了したプロセスのCR3は再利用されるため,プロセスの終了を検出する必要があるが,これはexit syscallを監視することで実現できる.スレッドは,kernel stack pointerのマスクから識別する.
ゲストとのセマンティックギャップの解決にあたっては,一時的にゲストを停止してシステムコールを挿入する手法を用いる.PEMU_というprefixでsyscallに相当するAPIが提供され,getpid, gettimeofdayなどゲストOSの情報を取得するためのAPI 28種類と,open, fstat, lseekなどゲストOSを操作するためのAPI 15種を用いることができる.これらは都度レジスタコンテキストの退避と復元を伴って実行される.

評価

論文での性能評価では,32-bit Ubuntu 12.04(Linux kernel 3.0.0-31-generic-pae)をホストとし,Intel Core i7, メモリ8GBのマシンが用いられた.速度の評価には32-bit Ubuntu 11.04(Linux kernel 2.6.38-8-generic)がゲストとして用いられた.
その結果として,PEMUではQEMUよりも4.33倍,Pinよりも83.61倍のオーバーヘッドが生じることが明らかになっている.

また,eXaitを用いた検出テストのため,Windows XP 32bitがゲストとして用いられた.論文ではeXaitの17手法全てがPinを検出した一方で,いずれの手法もPEMUを検出することができなかった.

関連研究

PEMUがQEMUにPin APIのサポートを追加したのに対して,PinOSはXenにPin APIのサポートを追加した.だがPinOSのinstrumentationは貧弱であり,セマンティクス情報を取得するAPIが提供されていない.また,解析ルーチンがカーネルや解析対象からアクセスできるため,isolationとして不十分である.
また,PinOS以外にカーネルへのinstrumentationをサポートしているDRKは,LKMとして実装されているため,in-VMな手法に留まっている.

おわりに

こうして,Pin APIを用いてout-of-VMにマルウェアを解析するための道標が示された.
今後のPEMUを用いた研究に期待したい,と他人事のように言っている場合ではなく,そろそろ論文を書かなければ.

補足

PEMUは新しいといえどQEMU 1.5.3をベースとしており,やがてはQEMU 0.9.1をベースとしているTEMUのように技術的負債となるだろう.
そこで,PEMUをforkしQEMU 1.5.3からQEMU 2.2.1にアップデートを試みた.が,QEMU 2.2.1に至るまでcpu_single_env変数が廃止されたことと,謎のコンパイルエラーが発生することから頓挫中である.そのうち何とかする.

参考文献

VMI

仮想マシンモニタからゲストのリソースを監視・制御する技術をVMI(Virtual Machine Introspection)という.
その発祥は2003年に遡る.当時はハニーポットの研究が盛んな時期であり,VMIは仮想マシンにおける侵入検知を実現する手法として提案された.これはマルウェア解析の自動化に応用されており,仮想マシンモニタによるサンドボックスを構築し,VMIによってマルウェアの挙動を監視するというアプローチが一般的となっている.
さて,VMIにおける問題点にセマンティックギャップというものがある.原義は高級言語とハードウェアとの乖離であるが,OSと同じ粒度で情報を取得することのできるゲスト内部(in-the-box)とハードウェアの粒度で情報を取得することしかできないゲスト外部(out-of-the-box)の乖離という意味でも援用される.

Transparent Sandbox

セマンティックギャップを解決する方法として,ゲスト内部にエージェントを挿入し,仮想マシンモニタに情報を送信するというアプローチが考えられる.
だがマルウェア解析において,ゲスト内部にエージェントを挿入することは,自らの姿を曝け出していることにほかならない.ファイルやサービス名,フックによって変化するAPIの挙動といったものは,マルウェアがエージェントと同じ権限で動作する限り避けられない.そもそも仮想マシンモニタは特権を有していたところでRDTSCICEBPなどの命令,あるいはハードウェア名やIDTといった要素から検出される可能性を孕んでいる.そのため,ゲスト内部にエージェントを挿入することは,仮想マシンモニタがマルウェアから検出される可能性を高めることに繋がる.フォレンジックにおける完全性(integrity)のためにも,ゲスト内部にエージェントを挿入すべきではないと私は考える.
この議論に関して,マルウェアから検出されない仮想マシンモニタをtransparent sandbox(透明なサンドボックス?)といい,仮想マシンモニタの検出を試みるマルウェアをevasive malwareという.
ではどのような仮想マシンモニタがより「透明」に近いのか.

仮想マシンモニタの歴史

ここでPopekとGoldbergの仮想化要件に立ち返ると,ベアメタルな仮想マシンモニタは等価性(equivalence),資源管理(resource control),効率性(efficiency)の三原則を実現しており,なおかつユーザセンシティブ命令が特権命令でなければならない.センシティブ命令かつ特権命令でなければ,例外によって仮想マシンモニタに通知することができないためである.
だが,以前のx86アーキテクチャはこの要件を満たしていなかった.そこで,ニ種類の解決方法が編み出された.
一つ目はバイナリ変換(binary translation)による完全仮想化である.これはソフトウェアで命令をエミュレートする手法で,QEMUやVMwareが該当する.QEMUは全ての命令を中間コードに変換するのに対し,VMwareはPopekとGoldbergの仮想化要件を満たさない命令をライブラリ呼び出しに変換する.
二つ目は準仮想化である.これはPopekとGoldbergの仮想化要件を満たさない命令に差し掛かると仮想マシンモニタに通知されるようゲストOSのカーネルを修正する手法で,Xenが該当する.
ではバイナリ変換による完全仮想化とカーネル書き換えによる準仮想化のどちらがより「透明」に近いのか.
その前にIntel VT-xについて考えなければならない.Intel VT-xはCPUのモード切り替えによってセンシティブ命令かつ特権命令でない命令のトラップを実現する拡張機能である.すなわちPopekとGoldbergの仮想化要件を満たすハードウェア側からのアプローチである.これにより準仮想化カーネルの必要はなくなった.エージェントの挿入が「透明」性に関わるのと同様,カーネルの書き換えは仮想マシンモニタを検出する手掛かりとなる.
そのためマルウェア解析においては,バイナリ変換による完全仮想化か,Intel VT-xによる完全仮想化が前提となる.なおKVMはIntel Vt-xを前提としているが,部分的にQEMUを用いている.
ではどちらの手法がより「透明」に近いのか.

バイナリ変換とIntel VT-x

Christopher KruegelはWineのようなシステムコール単位のエミュレーションあるいはフックは情報量として不十分であり,またIntel VT-xによる完全仮想化はRedPillのようなアプローチで検出可能であることから,バイナリ変換による完全仮想化すなわちQEMUを支持している.
システムコール単位の監視はIsDebuggerPresentのようなカーネルモードに遷移せず構造体を参照するだけの処理を見逃してしまう.システムコールのフックを用いた研究や製品は多数存在するが,それらは不完全である.この点で私は氏と意見を一にするが,バイナリ変換がより「透明」に近いかどうかは検討の余地があるだろう.寧ろ氏は実行パスの拡張がより容易に行えるがゆえにバイナリ変換を支持しているのだろうということは読み取れるが,氏がチーフサイエンティストを務めるLastlineの製品がQEMUをベースとしていることもあり,些かポジショントークのようにも感じられる.
このような論調でバイナリ変換とIntel VT-xを二項対立の図式に落とし込んでいる論文が数多く見られる.しかし,どちらがより「透明」に近いのかという議論はナンセンスであろう.
ゲスト内部にエージェントを挿入することで,果たして本当にマルウェアから検出されやすくなるのかと言うと,それは飽くまで可能性でしかない.だがゲスト内部にエージェントを挿入しないという選択で,その問題は検討項目から外すことができる.一方で,バイナリ変換であるという理由でIntel VT-xを用いた仮想マシンモニタよりも検出されにくいといったことはない.逆もまた然りである.
そしてそもそも,ネットワーク経由で仮想マシンモニタを検出するという手法がある以上,完全に「透明」なサンドボックスは実現不可能であるとされる.
ゆえにそれぞれのアプローチについて「透明」性の他にもメリット・デメリットを検討し,なおかつ両者を接合するようなシステムこそが望ましい.

参考文献

はじめに

V2E: Combining Hardware Virtualization and Software Emulation for Transparent and Extensible Malware Analysis[PDF]“という論文を通して,Record and Replayを用いた解析環境の設計を学ぶ.

著者

この論文のラストオーサーであるYinはSyracuse Universityの助教である.彼はテイント解析の第一人者として知られ,現在はDECAFの開発を主導している.またBitBlaze ProjectのDawn Songや,マルウェア解析の大御所であるChristopher Kruegelと過去に共著を出している.
ファーストオーサーのYanは提案手法をAndroidに適用し,2013年に博士論文を著している.Android向けの拡張にあたっては,DECAFのサブプロジェクトであるDroidScopeを用いているようだ.

Record and Replay

あるいはLogging and Replay, Lockstep, 順序再演法,最小情報トレースなどと呼ばれるこれらは,仮想マシンモニタ上のイベントを記録し,再生するための技術である.乱暴に言うとhistoryからdockerfileやvagrantfileを作成し,deployするようなものだ.
一般にステートマシンにおける命令の出力は,内部状態から一意に与えられる.そこで,ある環境の初期状態と入力のみを記録(Record)し,同じ環境を別の環境の上に再生(Raplay)するといった試みがなされてきた.実マシンにおいては,時刻や割り込みなどの非決定性とその記録の困難性からRecord and Replayは不可能であるとされる.だが,仮想マシンモニタの世界ではこれらの問題をある程度無視できる.実際,VMware Workstationなどにこの機能は実装されている.
本論文では,マルウェア解析に求められるサンドボックスの特性を加味したRecord and Replayについて論じられている.かつて大居さん(@a4lg)が研究されていた内容に近い.

背景

マルウェアを解析するためのサンドボックスは検出不可能(transparent)であり,なおかつ拡張可能であるべきだ.
いかに仮想マシンモニタの存在を隠蔽しようと,Timing Attackなどが成り立つ以上,transparentなサンドボックスを実現することは不可能である.しかし,Intel VTなどハードウェア仮想化技術を用いることで,ほぼtransparentな環境を作り出すことは可能である.例えば,Etherは命令・システムコール単位の解析機能を備えているが,Xenをベースに高いtransparent性を実現している.
だが,ハードウェア仮想化技術に依存した解析環境には拡張性の点で問題がある.特に,instrumentationによる詳細な解析が不可能であるという点は,大きな痛手である.
他方,QEMUなどのソフトウェアエミュレーションは動的バイナリ変換を用いることでDBI(dynamic binary instrumentation)と解析効率の向上を実現している.しかし,transparentなサンドボックスには至れない.
QEMUの動的バイナリ変換はバイナリをコードブロック単位で変換し,softmmuからTLBを参照してアドレス変換を行うというものだ.
そしてその性質から,以下のような自己書き換えコードによって検出されうる.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
__asm{
xor eax, eax
mov edi, target
mov esi, copy_insn
mov ecx, 3
target:
rep movsw // f3 66 a5
jmp qemu_found // eb XX
nop // 90
non_qemu:
...
qemu_found:
...
copy_insn:
_emit 0xeb // eb
_emit 0x01 // 01
_emit 0x90 // 90
_emit 0xeb
_emit 0x01
_emit 0x90
}

実マシンでは,ecx*word=6バイトが1回で書き換わるが,QEMUの動的バイナリ変換では2バイトずつ3回で書き換わる.そのため,1回目の書き換えで0xeb 0x01 0xa5すなわちjmp +01になってしまい,qemu_foundにジャンプしてしまう.
その他には,ページ境界を越えてブロックの変換が行われた場合にページフォルトが発生してしまうことも考えられるし,ブロック境界でのみ割り込みが行われる,CPUサイクルの消費が著しいといった実マシンとの相違点もある.
さらに問題なのが,フラグの遅延評価だ.例えば,cmpjzの組み合わせなどの条件分岐は,EFLAGSを更新する.だが,QEMUにおいてはcmpが実行される段階でEFLAGSの計算は行われない.実際に計算されるのはjzの実行時,それも分岐を決定するためのZFのみが計算される.この設計はエミュレーションの高速化に寄与しているが,もちろん検出に用いることが可能だ.
当然ながら命令のエミュレーション自体にも限界がある.SIMDさえ厳しいのだ,システム管理モードやIntel TXTなんてものは考えたくないだろう.
このように,QEMUによるエミュレーションが検出される余地は枚挙に暇がない.
なお,解析環境検出をテーマとした最近の研究では,第2回システム系論文輪読会で紹介したBareCloudや忠鉢さん(@yuzuhara)のTENTACLEなどがある.

研究目的

ハードウェア仮想化技術を用いる解析環境とソフトウェアエミュレーションを用いる解析環境にはそれぞれ問題がある.そこで,ハードウェア仮想化技術を用いる解析環境でRecordを行い,ソフトウェアエミュレーションを用いる解析環境でReplayを行うことで,検出不可能性と拡張可能性という二つの目的について達成したのが,今回紹介するV2Eである.

形式的定義

本論文におけるRecord and Replayの設計はどのようなものか.
Recorderにおける遷移関数fについて,毎時iにおけるプログラムの状態をSiとし,入力をIiとする.すなわちfSi= f(Si-1, Ii-1)と表される.
次にReplayerにおける遷移関数f'についてプログラムの初期状態をS0とし,全ての入力をIとしたとき,f = f'と言えないだろうか.
これは二つのチューリング機械の同値性が解決可能であるかという問題に相当する.だがEQTM= {(M1, M2)|M1とM2はTMであり,L(M1) = L(M2)}は判定不可能とされ(『計算理論の基礎』における定理5.4),実装上でもハードウェアの割り込みなどの要因からf != f'となってしまう.
そこでV2Eは,プログラムの初期状態と全ての入力を保存することに加え,Sj= S'jとなるようなjについて状態の変化を保存することにした.これはj= Sj- Sj-1と表される.
ここで,新たな遷移関数f'rS'i= f'r(S'i-1, Ii-1, ⊿i)として定義する.これは,i!= nullのときS'i-1+ ⊿iと同値であり,それ以外についてf'(Si-1, Ii-1)と同値をとる.
なお,S0, I, およびf'r, S'i= Sii ∈ [0, n]について恒真である.
これを実装に起こすと,特定の命令やイベントが正しくエミュレート可能な場合は単にそれらをエミュレートし,そうでなければ状態の変化を記録し,Replayにあたって変更を適用するというアプローチになる.

理論と実際

プログラムの大部分を占めるmov, push, popなどのデータ転送命令,call, ret, jz, jmpなどの制御転送命令,add, shlなどの整数演算命令におけるエミュレーションは失敗しないものと見做せる.これらはそのままRecorderでエミュレートされる.
一方で,割り込み,MMIO, Port IO, DMA, TSCについては,V2Eは既存研究を踏襲し,監視領域においてのみこれらをRecordするようになっている.
では,例外,モデル固有レジスタ,cpuidはどうすべきだろうか.既存手法は,これらのエミュレーションは困難であるという理由から,そもそも入力として扱わない戦略を採っていたようだ.V2Eではこれらを, すなわちエミュレートが困難な状態の変化としてRecordすることで,Replayの正確性を高めている.
次に問題となるのが浮動小数点演算とSIMDの扱いだ.MMXやSSEを正確にエミュレートするのは難しい.だが,として命令の結果を記録する設計は大幅なパフォーマンスの低下を招く.そこでV2EはReplayにあたってこれらの命令をパススルーする.もちろん,ReplayerはSIMDをサポートしているマシンで実行されることが前提にある.

Transparent Recorder

RecorderはKVMを用いて実装されている.
V2EはRecord対象の領域とそれ以外のシステムを分割するため,TDP(two dimensional paging)を用いている.何のことかと思ったら,Intel EPTやAMD NPTの総称らしい.

要するに,TDPとは仮想マシンと物理マシン間のページテーブルのことだ.通常のページングでは,メモリアクセスに応じてMMUによってページテーブルが参照され,仮想アドレスが物理アドレスへと変換される.TDPでは,ゲストマシンからの仮想メモリ空間へのアクセスに応じてCR3にセットされたページテーブルが参照され,ゲスト物理アドレスがホスト物理アドレスへと変換される.
この仕組を用いたV2Eは,監視対象用のTDPテーブルと,それ以外用のTDPテーブルを別々に作成する.マルウェアに属するページはCR3の監視に基づき監視対象用のTDPテーブルに書き込まれる.マルウェアとそれ以外の部分のインタラクションはTDPページフォルトやVMExitによって媒介される.共有されるデータは読み取り専用として双方に与えられる.なお,TDPページフォルトに応じてCPUの状態が入力Iiとして保存される.

Precise Replayer

ReplayerはTEMUを用いて実装されている.バイナリ変換器に中間表現がなく,単純に古いQEMU 0.9.1をベースとしているのが玉に瑕だが,TEMUは動的テイント解析に求められる機能をほぼ網羅している.
TEMUはプラグインを共有ライブラリとしてロードし,コールバック関数からテイント解析の機能を呼び出すプラットフォームとなっている.V2EのReplayerは既存のプラグインであるtracecap, unpackerを用いる.だがRecordされたログには監視対象の情報のみが記述されているため,
return ((*TEMU_cpu_hflags & HF_CPL_MASK) != 3)といった,現在実行しているコードが解析対象のものかどうか判定するコードは除去されているようだ.TEMUのプラグインについては,こうした僅かな変更しか施されていない.
一方でその下で動くQEMUには結構手が加えられている.フラグの遅延評価は廃止され,ページフォルト以外の例外は除去されており,SIMDについては独自のヘルパー関数が追加されたようだ.QEMUのdyngenに手を加えるのはなかなか骨の折れる作業だと思う.
さて,Replayを行うためには,ReplayerはRecorderと同様のページングの仕組みをエミュレーションによって再現しなければならない.そこで,V2Eは物理ページコンテナという仕組みを用いている.これは,物理ページがログからロードされていることを示すものである.通常,物理ページコンテナは監視対象用のTDPテーブルを複製する.Replayされたプログラムが物理ページコンテナに存在しないページにアクセスした場合,Replayerは適切なタイミングでログからCPUの状態を復元し,ロードするようになっている.
V2Eにおけるテイント解析はおそらく,マルウェアのメモリ領域を正確に把握するためのものではない.それは,Recorderの段階でTDPテーブルの分割というアプローチによって実現されるべきものだからだ.TEMUのプラグインを使いたかったのだろうが,論文中からはあまりテイント解析を導入することのメリットが読み取れなかった.ここでのテイント解析は解析環境検出の対策に先立つものとして設定されているのだろうか.

評価

解析環境検出については問題なし.cpuid, rdtsc, cmpxch8b, icbp, rep stosb, fnstcwといった命令や,一般保護例外などについてテストされている.なお,rdtscについてはVMRESUME前にホストのTSCを参照することで対応している.
in-the-wildのマルウェアについても実験が行われており,アンパッカーとして期待できるパフォーマンスを見せている.
Recordにおける速度だが,コンテキストスイッチが頻繁に発生するカーネルモードルートキットで17倍,Internet Explorerで5倍と高速だ.KVMのシングルステップモードには3000倍のオーバーヘッドがあると言うのに.
全体的にpositiveな結果で,かなり良い.

おわりに

マルウェアによる解析環境検出に対して,復数の環境を組み合わせたRecord and Replayを用いる研究について紹介した.何より,監視対象とそれ以外で別個にTDPテーブルを作るというアプローチが素晴らしい.自分も研究でテイント解析を扱っているが,この流れを包摂していきたい.
ただ,これはサンドボックス全般に言えることなのだが,感染ホストにおけるユーザーのブラウザ操作が条件分岐に影響するMITBマルウェアについて,どう対処すべきなのだろうか.正常系のユーザーのブラウザ操作をデータセットとしてRecorderに与えたいところだが,果たしてどうなるのか.
このエントリはシステム系論文紹介 Advent Calendar 2014の9日目として書かれた.

参考文献

はじめに

選択的シンボリック実行について紹介する.

シンボリック実行

シンボリック実行とは,プログラムに含まれる変数に具体値を入力せず,その代わりとして値を代表するシンボルの操作を通じてプログラムを模擬的に実行し,結果を評価する技術である.シンボリック実行の目的は,コードカバレッジの拡大にある.シンボリック実行は全てのケースに対してforkする,あるいは,条件分岐の制約をもとにテストケースを生成するといった形態でソフトウェアテストに用いられている.
ひとまず,以前書いたシンボリック実行に入門しようとしたをご覧頂きたい.

選択的シンボリック実行

選択的シンボリック実行(selective symbolic execution)は,シンボリック実行の弱点を改善すべくS2Eにて提案,実装された.
シンボリック実行には実行パスにおける計算爆発(path explosion)の問題があった.プログラム中の全ての実行パスを通るための制約はあまりにも多い.そして,全ての実行パスというのは解析対象の実行パスだけではない.考えてもみよう,実システムでプログラムを実行した際,プログラムは自身以外の様々なものを呼び出す.呼び出されるlibcなどのライブラリ,そしてカーネルやデバイスドライバ,さらにそのファームウェアは,一体どこまで解析対象における実行パスの分岐に影響を与えるのか.
この頭が痛い問題に対応するべく編み出されたのが選択的シンボリック実行,すなわちシンボリック実行を行う範囲の限定である.S2Eはシンボリック実行を行いたい部分以外に具体値(concrete value)を用いることで,解析対象のプログラムだけにシンボリック実行を適用する(concolic testing).具体的には,S2Eは指定した変数が使用されている部分のみシンボリック実行を適用している.

S2E

動的バイナリ変換

S2Eは,QEMUをベースに開発された.QEMUはエミュレーションを実現するべく,以下のような流れで動的バイナリ変換を行う.

1.ゲストコードの逆アセンブル
2.マイクロオペレーションに変換
3.コード辞書を参照してホストコードに変換

S2Eはこのコード辞書をLLVM bitcodeに差し替えることで,x86のバイナリをLLVM bitcodeに変換する.そして,変換後のLLVM bitcodeをKLEEに渡すことで,シンボリック実行を行う.
このとき,解析対象の全部分がLLVM bitcodeに変換されるわけではない

指定した変数が使用されている部分のみシンボリック実行を適用すると書いたように,S2Eはシンボル化したデータにアクセスしているか否かによって,解析対象の実行方式を切り替えている.実行方式は以下の二通りだ.

  1. 具体値にアクセスしている場合,通常通り実行
  2. シンボルにアクセスしている場合,LLVM bitcodeに変換してKLEE上で実行

これは,解析対象を多数のコードブロックに分割するというQEMUのバイナリ変換方式に極めて依存している.

S2E opcodes

S2Eは独自の拡張命令S2E opcodesを用いてシンボリック実行のための機能をinstrumentする.S2E opcodesは以下のような機能を提供する.

  • S2SYM: データのシンボル化
  • S2ENA: 複数パスの実行を有効化
  • S2DIS: 複数パスの実行を無効化
  • S2OUT: デバッグ情報の出力

この中身はs2e-x86.hs2e.hに記述されている.例としてS2SYMの実装を見てみよう.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define S2E_INSTRUCTION_COMPLEX(val1, val2) \
".byte 0x0F, 0x3F\n" \
".byte 0x00, 0x" #val1 ", 0x" #val2 ", 0x00\n" \
".byte 0x00, 0x00, 0x00, 0x00\n"
#define S2E_INSTRUCTION_SIMPLE(val) \
S2E_INSTRUCTION_COMPLEX(val, 00)
~ 略 ~
static inline void s2e_make_symbolic(void *buf, int size, const char *name)
{
__s2e_touch_string(name);
__s2e_touch_buffer(buf, size);
__asm__ __volatile__(
S2E_INSTRUCTION_SIMPLE(03)
: : "a" (buf), "d" (size), "c" (name) : "memory"
);
}

例えば,解析対象のソースコード上でs2e_make_symbolic()の引数にシンボル化したい変数を渡すことで,この関数を利用することができる.

Windowsデバイスドライバに対する選択的シンボリック実行

Analyzing Windows Drivers: Step-by-Step Tutorialという公式チュートリアルでは,プラグインを用いてWindowsデバイスドライバにアノテーションを付加する方法が紹介されている.

1
2
3
4
5
6
7
8
9
10
11
12
13
function annotation_example(state, plg)
-- Write custom Lua code here (e.g., to inject symbolic values)
end
pluginsConfig.Annotation =
{
init1 = {
active=true,
module="pcntpci5_sys_1",
address=0x169c9,
instructionAnnotation="annotation_example"
}
}

チュートリアルの例ではpcntpci5.sysというドライバが0x169c9というアドレスを呼び出す際にannotation_example()が実行される.BSoDもフックできるので,NotMyFaultドライバで遊ぼう.

オーバーヘッド

いつだって問題となるのは実行速度だ.論文によると,S2Eは具体値による実行時(concrete mode)にQEMUの6倍,シンボリック実行時にQEMUの78倍のオーバーヘッドが生ずるとされている.注意したいのは,実機の78倍ではなくQEMUの78倍である点だ.

おわりに

S2Eについて紹介した.
このエントリはソフトウェアテストあどべんとかれんだー2014の3日目として書かれた.

参考文献

より詳しくは以下の論文を参照されたい.これも全てVitaly Chipounovって奴の仕業なんだ.

はじめに

ここでは,BitBlazeのうち,静的解析に特化したコンポーネントであるVineを動かしてみる.

BitBlaze

BitBlazeはDawn Songらによるバイナリ解析プラットフォームで,2008年にBitBlaze: A New Approach to Computer Security via Binary Analysis [PDF]が発表されて以来,数多くの研究に用いられてきた.BitBlazeは,動的解析コンポーネントのTEMU,静的解析コンポーネントのVine,動的シンボリック実行コンポーネントのRudderから構成される.このうち,TEMUとVineのソースコードが公開されている.

TEMU: The BitBlaze Dynamic Analysis Component

TEMUはQEMUをベースとしたエミュレータで,テイント解析(taint analysis)の機能を備えている.テイント解析とは,タグを設定したデータの伝搬を追跡することで,データ同士の依存関係を解析する技術である.TEMUはtracecapというプラグインを用いて,ゲストOS上で動作するアプリケーションのトレースログを取得することができる.

Vine: The BitBlaze Static Analysis Component

Vineは,逆アセンブリやTEMUのトレースファイルから,中間表現VineILや最弱事前条件,STP formulaなどを出力する.公開されているVineには,TEMU/tracecapのトレースファイルとしてfive.traceが同梱されている.これを例にVineの機能を見てみよう.

Vineのインストール

Vine installation and user manualの通り.OCamlで記述されているため,関連のパッケージを導入する必要がある.また,32bit環境での動作を前提としている.

1
2
3
4
sudo apt-get install g++ ocaml ocaml-findlib libgdome2-ocaml-dev camlidl \
libextlib-ocaml-dev ocaml-native-compilers \
libocamlgraph-ocaml-dev binutils-dev texlive \
texlive-latex-extra transfig hevea

trace_reader

TEMU/tracecapが出力するトレースファイルはhuman-readableではなく,閲覧はVineのtrace_readerを介して行う必要がある.five.traceでは,T1がタグの識別子となっており,T0はデータに設定されたタグが存在しないことを意味する.なお,ここではキーボードからの入力にタグが設定されている.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
../trace_utils/trace_reader -trace five.trace | grep T1 | head -n 20
42075911: movzbl (%eax),%eax R@eax[0x40014000][4] T0 M@0x40014000[0x00000035][1] T1 {1 (1001, 0) ()()()}
42077e0c: cmp $0xffffffff,%eax I@0x00000000[0xffffffff][1] T0 R@eax[0x00000035][4] T1 {1 (1001, 0) ()()()}
42077e14: movzbl (%edx),%eax R@eax[0x00000035][4] T1 {1 (1001, 0) ()()()} M@0x40014000[0x00000035][1] T1 {1 (1001, 0) ()()()}
4205abc5: mov %eax,-0xac(%ebp) R@eax[0x00000035][4] T1 {1 (1001, 0) ()()()} M@0xbffff69c[0x00000000][4] T0
4205abce: mov -0xa8(%ebp),%eax R@eax[0x00000035][4] T1 {1 (1001, 0) ()()()} M@0xbffff6a0[0x00000000][4] T0
4205abd5: cmpl $0xffffffff,-0xac(%ebp) I@0x00000000[0xffffffff][1] T0 M@0xbffff69c[0x00000035][4] T1 {1 (1001, 0) ()()()}
4205abf5: mov -0xac(%ebp),%edx R@edx[0x40014001][4] T0 M@0xbffff69c[0x00000035][4] T1 {1 (1001, 0) ()()()}
4205ac0b: cmpl $0xffffffff,-0xac(%ebp) I@0x00000000[0xffffffff][1] T0 M@0xbffff69c[0x00000035][4] T1 {1 (1001, 0) ()()()}
4205ac14: movzbl -0xac(%ebp),%eax R@eax[0x42130b80][4] T0 M@0xbffff69c[0x00000035][1] T1 {1 (1001, 0) ()()()}
4205ac24: push %eax R@eax[0x00000035][4] T1 {1 (1001, 0) ()()()} M@0xbffff604[0x4213030c][4] T0
4205ac25: mov 0x8(%ebp),%eax R@eax[0x00000035][4] T1 {1 (1001, 0) ()()()} M@0xbffff750[0x4212d980][4] T0
4207793a: mov 0xc(%ebp),%edx R@edx[0x00000035][4] T1 {1 (1001, 0) ()()()} M@0xbffff604[0x00000035][4] T1 {1 (1001, 0) ()()()}
42077945: cmp %dl,-0x1(%eax) R@dl[0x00000035][1] T1 {1 (1001, 0) ()()()} M@0x40014000[0x00000035][1] T1 {1 (1001, 0) ()()()}
42077974: movzbl %dl,%eax R@dl[0x00000035][1] T1 {1 (1001, 0) ()()()} R@eax[0x40014000][4] T0
42077960: cmp $0xffffffff,%eax I@0x00000000[0xffffffff][1] T0 R@eax[0x00000035][4] T1 {1 (1001, 0) ()()()}
4205ac39: movzbl -0x9d(%ebp),%eax R@eax[0x00000035][4] T1 {1 (1001, 0) ()()()} M@0xbffff6ab[0x00000064][1] T0
4205c550: mov $0xa,%edx I@0x00000000[0x0000000a][4] T0 R@edx[0x00000035][4] T1 {1 (1001, 0) ()()()}
4205c566: cmpl $0xffffffff,-0xac(%ebp) I@0x00000000[0xffffffff][1] T0 M@0xbffff69c[0x00000035][4] T1 {1 (1001, 0) ()()()}
4205dcd1: movzbl (%eax),%edi R@edi[0x00000000][4] T0 M@0x40014000[0x00000035][1] T1 {1 (1001, 0) ()()()}
4205dcd8: mov %edi,-0xac(%ebp) R@edi[0x00000035][4] T1 {1 (1001, 0) ()()()} M@0xbffff69c[0x00000035][4] T1 {1 (1001, 0) ()()()}

VineIL

Vineが生成するVineILは静的単一代入形式の中間表現であり,CFGの情報が損なわれることはない.中間表現の生成をinstruction liftingという.なお,VineILはValgrindの中間表現を扱うライブラリVEXをもとに生成される.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
~/vine/examples$ ../trace_utils/appreplay -trace five.trace -ir-out five.ir
~/vine/examples$ cat five.ir | awk 'NR==1000,NR==1020'
R_CC_OP_16:reg32_t = 0xd:reg32_t;
T_32t9_1114:reg32_t = cast(T_8t3_1108:reg8_t)U:reg32_t;
R_CC_DEP1_17:reg32_t = T_32t9_1114:reg32_t;
R_CC_DEP2_18:reg32_t = 0:reg32_t;
R_CC_NDEP_19:reg32_t = 0:reg32_t;
/*eflags thunk: logic*/
R_CF_10:reg1_t = false;
T_7_1115:reg8_t = cast(T_32t9_1114:reg32_t)L:reg8_t;
R_PF_11:reg1_t =
!cast(
((T_7_1115:reg8_t >> 7:reg32_t ^ T_7_1115:reg8_t >> 6:reg32_t)
^ (T_7_1115:reg8_t >> 5:reg32_t ^ T_7_1115:reg8_t >> 4:reg32_t))
^
((T_7_1115:reg8_t >> 3:reg32_t ^ T_7_1115:reg8_t >> 2:reg32_t)
^ (T_7_1115:reg8_t >> 1:reg32_t ^ T_7_1115:reg8_t))
)L:reg1_t;
R_AF_12:reg1_t = false;
R_ZF_13:reg1_t = T_32t9_1114:reg32_t == 0:reg32_t;
R_SF_14:reg1_t = 1:reg32_t == (1:reg32_t & T_32t9_1114:reg32_t >> 7:reg32_t);
R_OF_15:reg1_t = false;

出力している行の番号は適当.

最弱事前条件

最弱事前条件(weakest precondition)はDijkstraによる述語変換意味論の基礎を成す概念である.Sを条件,式をRとした際,最弱事前条件WP(S, R)は,Rを実行する前にS’が成り立っていればSの実行後にSが成り立つ最も弱い条件S’を表す.単純な例だと,以下のように表現される.

1
2
3
WP(S, x=e) = S[e/x]
WP(new == org, new = new+taint)
= new+taint == org

Vineにおける最弱事前条件の出力は,以下のようになる.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
~/vine/examples$ ../trace_utils/appreplay -trace five.trace -wp-out five.wp
~/vine/examples$ grep let five.wp | head -n 20
let post_1681:reg1_t = true in
let R_EAX_1682:reg32_t = 0x40014000:reg32_t in
let idx_1683:reg32_t = 0x40014000:reg32_t in
let val_1684:reg8_t = INPUT_1001_0000_61:reg8_t in
let temp_1685:reg8_t = val_1684:reg8_t & 0xff:reg8_t in
let temp_1686:reg8_t = temp_1685:reg8_t >> 0:reg8_t in
let towrite_1688:reg8_t = cast(temp_1686:reg8_t)L:reg8_t in
let mem_arr_1687:reg8_t[4294967296] =
let mem_arr_57[0x40014000:reg32_t]:reg8_t = towrite_1688:reg8_t in
mem_arr_57:reg8_t[4294967296]
in
let R_EAX_1689:reg32_t = 0x40014000:reg32_t in
let R_GDT_1690:reg32_t = 0xc02dbd80:reg32_t in
let R_LDT_1691:reg32_t = 0xc02dcc58:reg32_t in
let R_DFLAG_1692:reg32_t = 1:reg32_t in
let T_32t0_1693:reg32_t = R_EAX_1689:reg32_t in
let T_8t2_1694:reg8_t = mem_arr_1687[0x40014000:reg32_t]:reg8_t in
let T_32t1_1695:reg32_t = cast(T_8t2_1694:reg8_t)U:reg32_t in
let R_EAX_1696:reg32_t = T_32t1_1695:reg32_t in
let temp_1697:reg32_t = R_EAX_1696:reg32_t & 0xffff00ff:reg32_t in
let temp_1698:reg32_t = cast(0:reg8_t)U:reg32_t in
let temp_1699:reg32_t = temp_1698:reg32_t << 8:reg8_t in

このような手法でソースコードの存在しないバイナリから最弱事前条件を抽出し,仕様書を復元する試みがあるらしい.ゾッとする.

STP formula

Vineは,TEMUのトレースファイルからSTP formulaを出力する.STP formulaとはSMTソルバであるSTP用のフォーマットである.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
~/vine/examples$ ../trace_utils/appreplay -trace five.trace -stp-out five.stp
~/vine/examples$ head -n 20 five.stp
% free variables:
mem_arr_57 : ARRAY BITVECTOR(64) OF BITVECTOR(8);
INPUT_1001_0000_61 : BITVECTOR(8);
% end free variables.
ASSERT( 0bin1 =
(LET post_1681 =
0bin1
IN
(LET R_EAX_1682 =
0hex40014000
IN
(LET idx_1683 =
0hex40014000
IN
(LET val_1684 =
INPUT_1001_0000_61
IN
(LET temp_1685 =

SMTソルバは充足可能性問題を解く.では,ここで与えられる命題とは何か.それは,任意の初期値がトレースファイルの結果と一致するというものだ.STPは命題が充足可能か解こうとし,充足不能であった場合は反例を出力する.

1
2
3
~/vine/examples$ cat >>five.stp
QUERY(FALSE);
COUNTEREXAMPLE;

ここで出力される反例は,実行経路に影響を与えた入力値となるようだ.five.traceでは,0x35(ASCIIで5)という入力値が分岐に影響を与えている.

1
2
3
~/vine/examples$ ../stp/stp five.stp
Invalid.
ASSERT( INPUT_1001_0_61 = 0hex35 );

これはトレースファイルに対する静的なシンボリック実行だと言える.シンボリック実行とは,記号によって表現したプログラムの変数を操作することで,実行経路に影響する制約を抽出する静的解析の手法である.シンボリック実行は到達定義の解析などモデルベーステストの領域で発展してきたが,マルウェアの挙動解析に役立てられないだろうか.

BAP

BAPはDavid BrumleyらによるVineの再実装である.彼らはCMUに所属しており,PPPのメンバーでもある.彼らは脆弱性解析の自動化をmotivationとしてBitBlazeを扱ってきた.BAPはVineをより発展させたプロジェクトであり,逆アセンブリやTEMUのトレースファイルから中間表現BILを生成するほか,CFGのみならずCDG(control dependence graphs)やDDG(data dependence graphs)の出力をサポートしているようだ.

おわりに

TEMUのトレースファイルについて,ざっくりVineによる静的解析を行った.とりあえず動かしてみただけなので,コードを噛み砕く必要がある.気になるのはやはり中間表現のフォーマットだ.一度,QEMU,Valgrind,DynamoRIO,LLVM,Vine,BAPなどの中間表現について,対応を整理したほうが良いかもしれない.

はじめに

シンボリック実行(symbolic execution)という用語をセキュリティ系の論文でよく見かけるようになった.ここでは,シンボリック実行の基礎となる理論を辿る.筆者はソフトウェアテストの研究には疎く,おそらく本稿には若干以上の誤謬と誤解が含まれているだろう.ぜひ識者の教示を乞いたい.

発祥

シンボリック実行は主にソフトウェアテストの領域で古くから研究されてきたトピックである.シンボリック実行という用語の初出は遡ること38年前,James C. KingらによるSymbolic Execution and Program Testing [PDF]という論文だ.Dijkstraがgoto文の濫用による大域脱出を批判したのが1968年であり,Guarded Command Languageを提案したのが1975年のことである.この論文が発表された1976年当時はまさに構造化プログラミングというパラダイムがコンピュータサイエンスの世界を席捲していた時代であった.私が生まれる20年以上前のことで,当時の問題意識を肌身で感じることができないのが少し残念に思える.感覚としては白亜紀のようなもので,主要な登場人物もDijkstraやらKnuthやら,恐竜かよ.
さて,シンボリック実行とはどのような提案だったか.まず,シンボリック実行の目的は「どの入力値でどの実行経路を通るか特定する」ことである.そのためにはどうすればよいだろうか?シンボリック実行はその名の通り,プログラムの変数をシンボル(記号)として表現する.論文中のスニペットはあまりにも古めかしいので,Symbolic execution - Wikipedia, the free encyclopediaを例に考えよう.残念ながら日本語記事はないものの,原理は単純明快.

y = read()
y = 2 * y
if (y == 12)
    fail()
print("OK")

シンボリック実行では入力に具体値を与えない.例えば,変数yに割り当てられる入力値をsというシンボルで表現する.見ての通り,このルーチンはif文で2つの実行経路に分岐するが,この分岐の条件を制約と呼ぶ.ここでの制約は2 * s == 12となる.実行経路を分岐させる条件となる入力値は,式を解けば分かる.言うまでもなく6だ.おっと,これは充足可能性問題というやつじゃないか?その通り,シンボリック実行では制約を解くにあたって制約充足ソルバ(constraint solver)を用いる.ここでは,2 * s == 12という制約が¬s1 ∧ ¬s2 ∧ ¬s3 ∧ ¬s4 ∧ s5 ∧ s6 ∧ ¬s7 ∧ ¬0という連言標準形で表される.2 * ss1s2s3s4s5s6s70に,1200001100となる.
このように,具体値を与えないまま,必ず1つの実行経路を通る制約(path constraints)を求め,条件分岐に影響する入力値の制約を特定する手法がシンボリック実行である.シンボリック「実行」と銘打っていても,実際にプログラムを実行しているわけではない.飽くまでシンボルの操作を通して,擬似的にプログラムを実行しているのだ.

Concolic Testing/Dynamic Symbolic Execution

では,シンボリック実行は銀の弾丸たりえるか?そんなわけがない.真っ先に以下の課題に直面してしまう.

  • 計算爆発
  • 制約充足ソルバで解くことができない制約
  • 入力値が一意に定まらない

そこで,CUTE: A Concolic Unit Testing Engine for C [PDF]において,concolic testingという手法が提案された.concolicとは耳慣れない言葉だが,どういった意味だろうか?これは,symbolic(シンボル)とconcrete(具体値)からなる造語で,concolic testingとはシンボリック実行に具体値(concrete value)を持ち込んだ手法である.またの名を動的シンボリック実行.
具体値を持ち込むとはどういうことか?動的シンボリック実行では,制約充足ソルバが不得手とする非線形な制約に到達した場合,その箇所だけ実際に実行(concrete execution)することで,具体値を代入する.これによって,コードカバレッジを拡大するというのが狙いである.現在「シンボリック実行」と呼ばれているのは概ね動的シンボリック実行である.

KLEE

KLEEはシンボリック実行にLLVM bitcodeを導入したプロジェクトである.チュートリアルはThe Symbolic Maze! - Feliam’s Blogが秀逸.
使い方は簡単で,解析対象のソースコードに#include <klee/klee.h>klee_make_symbolic()とを追加するだけで準備は完了する.klee_make_symbolic()にはシンボリック実行を適用したい変数のアドレスとサイズ,名前を引数として与える.

llvm-gcc --emit-llvm -c -g [file].c
klee [file].o

LLVM bitcodeとしてコンパイルし,KLEEに与えて実行すると,ktestという形式のテストケースが生成される.

ktest-tool --write-ints klee-last/[file].ktest 

ktest-toolを実行すると,入力値が出力される.

ktest file : ‘klee-last/test000001.ktest’
args : ['[file].o']
num objects: 1
object 0: name: ‘hoge’
object 0: size: 4
object 0: data: ‘fuga′

これによって,KLEEは90%以上のコードカバレッジを実現する.論文の評価実験では,Coreutilsについて,15年に渡って作成されてきたテストスイートよりも高いカバレッジをたったの89時間で達成している.
KLEEは多くの研究者に利用されており,シンボリック実行に関する研究のstate-of-the-artはKLEEを分散化したKleeNetだと聞いている.
しかし,もちろんKLEEは万能ではない.特にループ文の解釈がうまくいかないことが多く,これはシンボリック実行が抱える永年の課題である.

STP

KLEEはSTP Constraint Solverという制約充足ソルバを用いている.STPは制約充足ソルバの中でもSMT(Satisfiable Modulo Theories)ソルバと呼ばれるものに相当する.SAT(SATisfiability problem)ソルバはブール式のみを扱うが,SMTソルバはこれに加えて配列やビットベクトル,加減算大小比較など様々な背景理論を用いることができる.STPではAND,OR,NOT,XORといった演算についてもサポートされ,式の最適化についても工夫されているようだ.

S2E

少しばかり,リバースエンジニアリングにも目を向けてみよう.解析対象のソースコードが存在しない場合,どうやってシンボリック実行を適用すればよいだろうか?解決策のひとつとして挙げられるのがS2Eである.
S2EはQEMUの動的バイナリ変換(dynamic binary translation)を用いる.QEMUの動的バイナリ変換機能をTCG(Tiny Code Generator)といい,これによって例えばARM向けにビルドされたバイナリをx86の計算機で動かすといった機能が実現される.
まず,QEMUは対象のバイナリを逆アセンブルし,複数のブロックに分割する.このブロックをTB(translation block)といい,定義はtranslate-all.hに記述されている.TBは分岐命令やページの境界によって区切られる.そして,ブロック単位で逆アセンブルしたコードをgen_intermediate_code()という関数で中間コードに変換し,tcg_gen_code()という関数で他のアーキテクチャの命令とマッピングする.これらはtarget-[arch]/translate.cおよびtcg/tgc.cに記述されている.こうして変換されたコードは,TB単位でキャッシュされる.実行にあたっては,変換されたTBをchainとして繋いでいく.この処理は,main()からcpu_exec()を経由して呼ばれるtb_find_fast()tb_find_slow()に記述されている.こうして,QEMUは異なるアーキテクチャ向けバイナリの実行を可能にしている.
S2Eは,QEMUのTCGを用いてPEファイルをLLVM bitcodeに変換し,KLEEに受け渡す.TCGは,中間コードを変換するにあたって,変換先のアーキテクチャの命令が記述された辞書を参照する.S2Eはこの辞書にLLVM bitcodeを登録することで,実行ファイルをLLVM bitcodeに「逆アセンブル」するのだ.
このようにして,S2Eはシンボリック実行を実現しているが,そもそもLLVM bitcodeに変換する必要はあるのだろうか?KLEEは確かに優れたツールだが,バイナリに直接シンボリック実行を適用すれば良いのではないか?
これには理由がある.QEMUの中間コードも,LLVM bitcodeもレジスタが無限個存在するSSA(Static Single Assignment form,静的単一代入)形式をとっている.一方で,x86アーキテクチャはSSA形式ではない.x86における逆アセンブルコードにシンボリック実行を適用する例を考えよう.

mov esi, 0x09
mov edx, 0x2014

この場合,制約は(esi == 0x09) and (edx == 0x2014)となる.これなら問題はないが,以下の例はどうだろう.

mov esi, 0x09
...
mov esi, 0x2014

同じレジスタに違う値が代入されている.この場合,制約は(esi == 0x09) and (esi == 0x2014)となってしまう.こうした理由から,シンボリック実行にはSSA形式への変換が必要となるようだ.

おわりに

シンボリック実行の基礎を学んだつもりになった.この技術が情報セキュリティの分野でどう活きてくるのかについては,また改めて.進捗だめです.

参考文献