__attribute__((constructor))

main()が呼ばれる前に関数を呼ぶ方法として,一般にgcc拡張である__attribute__((constructor))が利用されている.
例えば次のコードでは,main()の前にconstructor()が呼び出される.

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
__attribute__((constructor)) void constructor(){
printf("constructor\n");
}
int main(){
printf("main\n");
return 0;
}

__libc_start_main()

gccが内部で呼び出すldは,glibcの初期化を行うためにcrt*.oを静的リンクする.これによって,_start()などのシンボルがバイナリに埋め込まれることになる.
ここで埋め込まれるシンボルには未定義なものが存在する.その一つとして,crt1.oに含まれる__libc_start_main()が挙げられる.
これはmain()より先んじて呼び出される関数であり,暗黙的にcrt1.oがリンクの対象となる.しかし未定義であるがゆえに,先にソースコードに__libc_start_main()が宣言されていた場合,ldはこちらをシンボルとして採用してしまう.

どちらが先か

上記を踏まえて,次のコードではどちらの関数が先に呼び出されるだろうか.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
__attribute__((constructor)) void constructor(){
printf("constructor\n");
}
int __libc_start_main(){
printf("__libc_start_main\n");
return 0;
}
int main(){
printf("main\n");
return 0;
}

正解は__libc_start_main()だ.私は実行するまで分からなかった.

__do_global_ctors_aux()

なぜ__libc_start_main()__attribute__((constructor))よりも先に呼び出されるのか.それは__attribute__((constructor))が,__do_global_ctors_aux()によって実現されているからだ.
__do_global_ctors_aux()_start(), __libc_start_main(), __libc_csu_init(), _init()を通ってようやく呼び出される.そのため,__libc_start_main()の方がより先んじて呼び出されるのだ.

__libc_csu_init()

Sigreturn-oriented Programmingでにわかに脚光を浴びている__libc_csu_init()__libc_start_main()の引数にセットされるコンストラクタだが,シンボルを上書きして__libc_start_main()の代わりにこちらをmain()ないし__attribute__((constructor))の先に呼び出すこともできる.
当初私は__attribute__((constructor))はこの辺りから呼び出されるものだと誤解していた.

Windowsでは

今回は触れないが,.CRT$X??のセクションやThread Local Storageのコールバックによって同様の機能を実現できる.

参考文献

はじめに

LibVMIはXenならびにKVMを対象としたVMIライブラリである.ここでは,その基盤と応用についてまとめる.

libxc

そもそもXenにおけるVMIの研究ではかねてより,各ドメインの制御機能ないしハイパーコールを提供するlibxcというライブラリが用いられてきた.libxcという名称はthe Xen Control libraryの略称であり,Xenによって公式に提供されている(tools/libxc/).なお,libxcとして提供されている関数はxc_というprefixを備えている.
このうち,VMIと密接に関連があるのはxenctrl.hxenguest.hである.なかでもxenctrl.hはlibxenctrlとも呼ばれ,PFNの参照やハイパーコールの追加などの機能が提供されている.
LibVMIのソースコードにgrepを掛けると,libxcに由来する構造体と関数が多く用いられていることが分かる.

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
% grep -rhoe "xc_[a-zA-z]*_[a-zA-z]*" . | grep -v "]" | sort | uniq
xc_domain_debug_control
xc_domain_decrease_reservation_exact
xc_domain_getinfo
xc_domain_getinfolist
xc_domain_hvm_getcontext
xc_domain_hvm_getcontext_partial
xc_domain_hvm_setcontext
xc_domain_maximum_gpfn
xc_domain_pause
xc_domain_populate_physmap_exact
xc_domain_set_access_required
xc_domain_unpause
xc_domaininfo_t
xc_dominfo_t
xc_evtchn_bind_interdomain
xc_evtchn_close
xc_evtchn_fd
xc_evtchn_notify
xc_evtchn_open
xc_evtchn_pending
xc_evtchn_t
xc_evtchn_unbind
xc_evtchn_unmask
xc_get_hvm_param
xc_hvm_get_mem_access
xc_hvm_inject_trap
xc_hvm_set_mem_access
xc_interface_close
xc_interface_open
xc_map_foreign_batch
xc_map_foreign_range
xc_mem_access_disable
xc_mem_access_enable
xc_mem_access_resume
xc_mem_event_disable
xc_mem_event_enable
xc_memory_op
xc_set_hvm_param
xc_set_mem_access
xc_vcpu_getcontext
xc_vcpu_setcontext

とりわけVMIにおいて重要なのはxc_map_foreign_range()という関数である.

1
2
3
void *xc_map_foreign_ranges(xc_interface *xch, uint32_t dom,
size_t size, int prot, size_t chunksize,
privcmd_mmap_entry_t entries[], int nentries);

Xenの各ドメインにはドメインや仮想CPUの構造体(xen/include/xen/sched.h)のほか,マシンメモリ(物理メモリ)と擬似物理メモリが割り当てられる.ドメインにおけるページングは,このマシンフレーム番号(MFN)と疑似物理フレーム番号(PFN)とを対応付けるP2Mテーブルによって実現されている.つまり,ドメインの仮想アドレスは擬似物理メモリフレーム番号に対応し,その疑似物理フレーム番号はさらにマシンフレーム番号に対応する.なお,Intel EPTが有効な環境においてはP2MはEPTによって代替される(ept-p2m.c).
xc_map_foreign_range()はこうした仕組みに基づき,ページテーブルを辿ってDom0のメモリ空間にDomUのマシンフレームを割り当てる.
VMIに求められるデータ構造の解釈はXenにおいて,この関数があることから成り立つものである.また,これによるフォールトインジェクションに関してもかつて研究が行われていたようだ.

libxenstore

Xenではxenstore-lsやxenstore-readなどのコマンドからxenstoredというデーモンを経由して各ドメインの情報を読み出すことができる.この仕組みをXenStoreといい,関連してlibxenstoreというライブラリが提供されている.(tools/xenstore/).libxsと呼ばれることもある.
XenStoreは名の通りKVSとしてドメインのUUIDやドメイン名,メモリのコミット状況などを格納している.
LibVMIにおいても,xenstordへのアクセスのため用いられている(xen_private.h).

libxenlight

libxenlightはlibxcとlibxenstoreのラッパとして公式に開発されているライブラリである(tools/libxl/).
LibVMIでは用いられていないものの,Xen Projectの本流ではこちらが推進されているように見受けられる.

XenAccess

XenAccessはlibxcのラッパであり,LibVMIの前身にあたる.
目的としてセマンティックギャップの解決が掲げられており,任意のPIDに対応するEPROCESS構造体を取得することができる.
EPROCESS構造体はWindowsの各プロセスに割り当てられる構造体であり,Windowsのプロセスリストはこの構造体のActiveProcessLinksメンバからなる双方向リンクリストによって成り立っている.タスクマネージャが参照するのはこの構造体である.
XenAccessはこの構造体を手掛かりにカーネルのベースアドレスを取得する.
まず,メモリ空間をPEヘッダの先頭すなわちMZという文字列で検索する.そして,発見したアドレスについてシステムプロセス固有のPsInitialSystemProcessのオフセットを加算し,EPROCESS構造体の先頭メンバである_EPROCESS.Pcb.headerにあたるシグネチャと比較する.一致した場合,発見したアドレスがベースアドレスということになる(windows_memory.c, windows_core.c, windows_process.c).
これによって,プロセスリストと任意のプロセスの情報を取得することができるようになった.

LibVMI

LibVMIはXenAccessの後継であり,かつてvmitoolsとも呼ばれていた.
先述したようなカーネル空間の解析機能をLibVMIはフォレンジックツールに委譲した.フォレンジックツールを導入するメリットとして,より詳細な構造体の解析を低い実装コストで実現できるという点が挙げられる.
さて,LibVMIはVolatilityRekallという二種類のフォレンジックツールに対応している.RekallはGoogleによるVolatilityの拡張であり,かつてはLibVMIのサポート外だったものの,commit a4f065a31b986562dc39c9a10d9dff080792f3f4にて導入された.
では,両者の差異はどこにあるのか.

Kernel Debugger Block

XenAccessが行っていたようなEPROCESS構造体のスキャンについて考えてみよう.
VolatilityとRekallはいずれも,まずリンクリストの先頭であるPsActiveProcessHeadを特定しようとする.
x86において,このPsActiveProcessHeadは,KPCR(Kernel Processor Control Region)構造体のKdVersionBlockメンバが示すKDDEBUGGER_DATA32構造体から取得することができる.
このKPCR構造体だが,x86ではFSレジスタ,x86_64ではGSレジスタが先頭アドレスを保持しており,Windows XPでは0xFFDFF000というマジックナンバーを用いて検索することができる.
では,KdVersionBlockはどうか.なんと,Windows 7の64-bit版からこのメンバは空になってしまっている.ゆえに,x86_64ではKDDEBUGGER_DATA64構造体をKdVersionBlockに頼らず検索する必要が生ずる.
ここで,VolatilityはKDDEBUGGER_DATA64構造体のヘッダに存在するKDBGシグネチャをスキャンするのに対し(kdbgscan.py),Rekallはカーネルのバージョンに対応したプロファイル情報を用いて構造体にアクセスする.

DRAKVUF

DRAKVUFはTamas K Lengyelによって開発されたサンドボックスであり,論文のオーサーにはXenAccessとLibVMIの開発者であるBryan D. Payneも名を連ねている.
LibVMIにRekallのサポートを追加したのがほかでもないTamas K Lengyelその人である.
Volatilityは前述の通りメモリからKDBG構造体を検索する.だが,ゲストOSのメモリはマルウェアによって改竄されてしまうおそれがあることに加え,Windows 8の64-bit版ではKDBG構造体が難読化されているという問題点がある.
一方で,Rekallのプロファイルはゲストから不可視であり,改竄の影響を受けないため,この問題を解決することができる.
DRAKVUFはマルウェア解析を目的としてLibVMIを拡張しており,当然プログラムの実行をトラップする機能を備えている.
特筆すべきは,Intel EPTを用いたメモリアクセスの監視である(vmi.c).

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
// Now we can set the EPT permissions
if (!container->guard) {
container->guard = g_malloc0(sizeof(vmi_event_t));
SETUP_MEM_EVENT(container->guard, container->pa, VMI_MEMEVENT_PAGE,
VMI_MEMACCESS_RW, trap_guard);
if (VMI_FAILURE == vmi_register_event(vmi, container->guard)) {
printf("*** FAILED TO REGISTER MEMORY GUARD @ PAGE %lu ***\n",
pa >> 12);
free(container->guard);
free(container);
continue;
}
container->guard->data = g_hash_table_new(g_int64_hash,
g_int64_equal);
printf("\t\tNew memory event trap set on page %lu\n", pa >> 12);
} else {
printf("\t\tMemory event trap already set on page %lu\n", pa >> 12);
}
struct memevent *test = g_hash_table_lookup(container->guard->data,
&container->pa);
if (!test) {
g_hash_table_insert(container->guard->data, &container->pa,
container);
} else if (test->sID == SYMBOLWRAP) {
printf("Address is already guarded\n");
} else {
printf("Address is trapped by another feature! ERROR/TODO!\n");
}

このアイデア自体はKVMをベースとして開発されたCXPInspectorを下敷きにしている.
かつては任意のアドレスについてNX bitを設定し,ページフォルトハンドラをブレークポイントとする手法が一般的であった.これがカーネル空間から可視であるのに対し,EPTは不可視であるためよりカーネルルートキットの解析に適している.

おわりに

LibVMIの登場と洗練によってもはや,セマンティックギャップは過去の問題になりつつある.XenにおけるVMIにおいて,これを用いない手はないだろう.

参考文献

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を用いた仮想マシンモニタよりも検出されにくいといったことはない.逆もまた然りである.
そしてそもそも,ネットワーク経由で仮想マシンモニタを検出するという手法がある以上,完全に「透明」なサンドボックスは実現不可能であるとされる.
ゆえにそれぞれのアプローチについて「透明」性の他にもメリット・デメリットを検討し,なおかつ両者を接合するようなシステムこそが望ましい.

参考文献

はじめに

2014.12.07~08にわたって開催されたSECCON CTF 2014の予選(英語版)にて,ROP: Impossibleというpwn問題が出題された.タイトルの通り,この問題ではROPが制限されている.
ここでは,その実現手法として用いられていたIntel Pin(pintool)について,またこの問題にあった欠陥について述べる.
したがって,このエントリはROP: Impossibleのネタバレを兼ねている.注意されたし.

問題の概要

問題文は以下の通り.Pinによって保護された脆弱なバイナリからフラグを読み出せというものだ.

ropi.pwn.seccon.jp:10000
read /flag and write the content to stdout, such as the following pseudo code.
open("/flag", 0);
read(3, buf, 32);
write(1, buf, 32);
Notice that the vuln executable is protected by an Intel Pin tool, the source code of which is norop.cpp.

パッと見,バイナリは良心的な構成であるように思われる.

1
vuln: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, for GNU/Linux 2.6.26, BuildID[sha1]=0xcb671b1dc0409082c3f3962818d366fcb8771ead, not stripped

有効になっているのはNXだけだ.

1
2
RELRO STACK CANARY NX PIE RPATH RUNPATH FILE
No RELRO No canary found NX enabled No PIE No RPATH No RUNPATH vuln

だからといって,解法が自明であるわけではない.この問題の肝は,いかにしてPinによる保護をかい潜るかにある.

Pin

Pinは,Intelによって開発されたDBI(dynamic binary instrumentation)フレームワークである.
DBIとは,プログラムにコードを挿入することで実行時の情報を取得・操作する技術であり,プログラムのパフォーマンス測定やエラー検出,CPUキャッシュの分析や未定義命令のエミュレーションなど,多方面で応用されている.
さて,ROP: Impossibleは以下のコードによって保護されている.

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
#include <stdlib.h>
#include "pin.H"
ADDRINT shadow_stack[4096];
int shadow_sp = -1;
VOID push_retaddr(ADDRINT esp, ADDRINT eip)
{
if(shadow_sp >= (int)sizeof(shadow_stack) - 1){
// cannot push retaddr to shadow stack
exit(-1);
}
PIN_SafeCopy(&shadow_stack[++shadow_sp], (VOID*)esp, sizeof(ADDRINT));
}
VOID pop_retaddr(ADDRINT esp, ADDRINT eip)
{
ADDRINT retaddr;
PIN_SafeCopy(&retaddr, (VOID*)esp, sizeof(ADDRINT));
while(shadow_sp >= 0 && shadow_stack[shadow_sp--] != retaddr);
if(shadow_sp < 0){
exit(-1);
}
}
VOID check_syscall(ADDRINT eax)
{
switch(eax){
// syscalls for exploit
case 3: // sys_read
case 4: // sys_write
case 5: // sys_open
case 6: // sys_close
// syscalls executed until entry point
case 45: // sys_brk
case 122: // sys_newuname
case 192: // sys_mmap2
case 197: // sys_fstatfs64
case 243: // sys_set_thread_area
break;
// invalid syscalls
default:
exit(-1);
}
}
VOID insert_hooks(INS ins, VOID *val)
{
if(INS_IsCall(ins)){
// push retaddr to shadow stack
if(XED_ICLASS_CALL_FAR == INS_Opcode(ins)){
exit(-1);
}
INS_InsertCall(ins, IPOINT_TAKEN_BRANCH,(AFUNPTR)push_retaddr,
IARG_REG_VALUE, REG_ESP, IARG_INST_PTR, IARG_END);
}else if(INS_IsRet(ins)){
// pop retaddr from shadow stack, and then check it
if(XED_ICLASS_RET_FAR == INS_Opcode(ins)){
exit(-1);
}else{
INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)pop_retaddr,
IARG_REG_VALUE, REG_ESP, IARG_INST_PTR, IARG_END);
}
}else if(INS_IsSyscall(ins)){
// check syscall
INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)check_syscall,
IARG_REG_VALUE, REG_EAX, IARG_END);
}
}
int main(int argc, char *argv[])
{
PIN_Init(argc, argv);
INS_AddInstrumentFunction(insert_hooks, NULL);
PIN_StartProgram();
return 0;
}

このプログラムが,vulnの共有ライブラリとして噛まされている.INS_*は命令単位のinstumentationのために提供されているPinのAPIである.
要するに,リターンアドレスの検証によって,ROPが制限されているのだ.

JOP

ROPができない環境ならば,どうすればよいのか.
そもそも,ROPに用いられるretは,スタックの最上位アドレスに対するpopjmpと等価であると見做せる.ゆえにjmpによってchainを構築すれば,retを用いること無くROPと同様なコードを作成することができる.これをJOP(Jump-oriented programming)という.
さらに,スタックに対するアドレスのpushjmpは,callと等価であると見做せる.ゆえにcallpopによってROPを代替することができる.
つまり,ROP: Impossibleはret制限下の環境を前提にjmpcallでchainを構築しろというストイックな問題だった.
Pinに起因する欠陥がなければ.

writeup

この問題を最初に解いたのは,TOEFL BEGINNERという謎のチームだった.続いてbinja, PPPと続いている.
優勝チームであるPPPメンバーのRicky Zhouが公開しているwriteupを見てみよう.

明らかにおかしい.bssセグメントにシェルコードを置いて実行しているだけではないか.
だが,このバイナリはNXが有効だったはずだ.ローカルでこのコードを実行しても,SIGSEGVが発生する.
これは一体どうしたことだろう.

JITコンパイルの弊害

結論から言うと,Pinの制御下にあるバイナリのNXは無効化されるようになっている.
/proc/pid/mapsを確認すると,一見nonexecであるように見える.

1
bf984000-bf9a5000 rw-p 00000000 00:00 0 [stack]

だが,実際はそうではない.
PinはJITコンパイルによってinstrumentationを実現している.そのため,バイナリはPinによってmmapされ,execされる.このとき,Pinは元来バイナリに付与されていた実行権限を無視してしまう.
つまり,ROPを制限するためのPinが,NXを無効化してしまっていたのだ.
そもそも,LinuxにおいてNXの状態をmaps以外から取得するのは難しい.強いて挙げるならば,checksecのようにreadelf -W -l file | grep 'GNU_STACK'を叩くといったところだろうか.だが,これだけではmmapやmprotectに追随することができない.WindowsのVirtualQueryに相当する機能はないのだろうか.

おわりに

XSS Bonsaiも同様だが,CTFについてもテストは重要であるということを気付かされた.
運営の穴を突くのもCTFの醍醐味のひとつなのだろうが,しかし厄介な問題である.
最近はPinやDynamoRioによるマルウェア解析が流行っているように見受けられるが,やがてはDBIツールのデメリットについても検討を加えなければならなくなるだろう.

はじめに

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形式への変換が必要となるようだ.

おわりに

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

参考文献

はじめに

Return-oriented programming(ROP)が提唱されて久しい.CTFにおいても,ROPは当たり前のように要求される技術となってきている.一方で,ROPに代わる新たな攻撃手法も模索されている.ここでは,そういったROP以後の攻撃手法を概観する.

Return-oriented programming

コンセプト

まずは簡単にROPをおさらいする.
ROPは主にハードウェアDEPという脆弱性対策技術に対抗するために編み出された攻撃手法である.ハードウェアDEPはCPUのNX bitを有効化することで,スタック上でコードを実行する攻撃を無効化する.
そこで,ROPはコード領域のretで終わる命令列(gadget)を実行することによってこれを回避する.単体のgadgetではわずかな処理しか行えないが,スタックに次のgadgetのアドレスを積むことで,gadgetを組み合わせたchainを構築することができる.ROPの作成にはコード領域からgadgetを探索する段階とgadgetを組み合わせる段階を要する.レジスタの操作はpopによって行う.

ASLR/PIEの迂回

ASLRはスタックやヒープなどが読み込まれる位置を実行ごとにランダマイズすることで,アドレスを決め打ちした攻撃を困難にする.だが,ASLRはROPに対処しうる技術ではない.
まず,LinuxにおいてASLRはコード領域のランダマイズを行わないため,スタックオーバーフローなどをROPの起点とすることができる.また,bssセグメントに存在する変数のアドレスを取得することができるのは,ASLRの重大な欠陥である.さらに,32bitの場合は総当りによってアドレスを特定できるほか,ulimit -s unlimitedによってASLRを無効化することができる.
PIEはASLRに加えてgadgetのアドレスまでランダマイズの対象となるため,攻撃にあたってはleakが前提となる.

RELROの迂回

RELROはセクションをread onlyに設定する機能である.Partial RELROとFull RELROがあり,前者の場合はGOTを利用した攻撃が可能である.後者の場合はread onlyにしうる全てのセクションがread onlyとなるが,ROPによって攻撃を成立させることができる.

Stager

攻撃に使える領域のサイズが制限されている場合,readなどの関数を用いて再度メモリに書き込む方法をstagerと呼ぶ.

Stack Pivot

スタックのサイズ上,リターンアドレスの下にROP chainを構築できないような場合,xchg esp,eaxなどのgadgetを用いてスタックのアドレスを移動させる方法をstack pivotと呼ぶ.

論文

BROP: Blind return-oriented programming

コンセプト

以下の要件を満たすサーバープログラムの場合は,バイナリが手元になくてもROPを試みることができる.

  • listen,forkを行う
  • スタックオーバーフローで子プロセスが落ちた場合も動き続ける
  • GOTにstrcmpなど第三引数を操作できる関数が存在する
  • GOTにwriteなどleakさせることができる関数が存在する
  • 総当りなどでGOTのアドレスが分かる

目的は,自身をwriteによってダンプさせることである.
まず,リターンアドレスを総当りして,無限ループに陥るようなgadget(STOP gadgetと呼称)を探す.次に,関数にinnvalidな引数を渡した場合であっても,GOTに正しく飛んだ場合はSEGVしないという点に着目し,0x08040000周辺に存在しているはずのGOTセクションの位置を推定する.推定にあたっては,+0x6のアドレスや次のGOTエントリに飛んだ場合もSEGVしないという特性を用いる.そして,fdを総当りするか,多数のコネクションからwriteを探り当てる.
GOTエントリは要素数のサイズが同じであるため,スタックのleakからゴリ押しできる,といった内容のようだが,実際のところどうなのだろうか.CTFのネタとしては面白いのではないか.

論文

実例

SROP: Sigreturn-oriented Programming

コンセプト

vdsoには,シグナル割り込みから復帰する際に,ユーザーランドのスタック上に作成したsignal frameに保存している値を全てのレジスタへ戻すsigreturnという命令が存在する.つまり,popadが廃止されたx64においても,sigreturnによってスタック上の値を複数のレジスタにセットすることができる.これによって,任意のシステムコールを呼び出すことが可能となるほか,関数の呼び出しがレジスタ渡しの場合においてもROPが容易になる.なお,vsyscallはASLRが有効であっても固定アドレスである.
ulimit -s unlimitedを用いてvdsoのマッピングアドレスを固定できる場合はCTFでも活用できそうだ.

論文

実例

JOP: Jump-oriented programmingとCOP: Call-oriented programming

コンセプト

通常,retの次にはそのサブルーチンを呼び出したcallの次の命令が存在する.そこで,コールスタックを辿ることでROPによってretが使われていないか検出するROPguardが考案された.ROPguardはMicrosoftの脆弱性対策ツールであるEMET 3.5の根幹を成す理論だった.
そこで,retの代わりにjmpを用いるJump-oriented programmingが考案された.また,retやjmpの代わりにcallを用いるCall-oriented programmingも可能である.例えば以下のコードスニペットにおいて,callはjmpと実質的に等価である.

pop esi;
ret;
push eax;
call esi;

; call先
pop esi ;retアドレスを除去
;eaxを用いる処理

COPでは,pushのような表現力の高い命令を用いることができる.

論文

ROPguard

JOP

COP

実例

COP

おわりに

ざっとROP以後の攻撃手法を列挙した.これ以外にも,AlphanumericなROPを作成する技術やバイナリから自動的にROPを作成する技術などが研究されている.また,roputilsBAPなど,ROPを支援するフレームワークも開発されている.これらについてもいずれ理解したい.