静的解析と動的解析を組み合わせたバイナリーコードの制御フロー解析	
IIJ-­‐II	  技術研究所	  泉田大宗	背景	• 現在もなお多数の正体不明なバイナリプログラムがネット上を飛び交っている	  • 正体不明	  – ソースコードがない	  – 誰がどのように作ったかもわからない(使用したコンパイラなど)	  – 暗号化、難読化など	  • 対策としては	  – アンチマルウェアソフト(シグネチャマッチ)	  – セキュリティ教育	  • 振舞を調べるには	  – サンドボックス環境で実行してトレースを解析	  – すべての実行パスを調べられるわけではない	  制御フローの再構築	
• バイナリプログラムから、最低限の知識だけを用いて制御フローグラフを再構築する	
バイナリプログラム	
fcbe8610400056b8002040005097b280bb701040
00a4ﬀd373833c9ﬀd3731433c0ﬀd3731d41b010ﬀ
d312c073fa7535aaebe2e84300000049e210e839
000000eb21acd1e8743d13c9eb159148c1e008ac
e82300000080fc05730683f87f77024141958bc55
68bf72bf0f3a45eeba602d275058a164612d2c333c941ﬀd313c9ﬀd372f8c3e87002c002ebfe33d2643
9ﬀ328f8922be272c4003b8a180be809334b4539
524e8e4c333201ﬀ1534300093e8536f082ae0c0ac91e305005603f1ebe983ec5473817a18cf288b26
e82a6100536f6674776172650e5c4d6963df1b73
1dd0574142a10434800a61622046696c7565794e756de06ac4c27807008d751481c4a0410bc0f454c
c8bb02972794b004e64e34603766051f2c61c807
e01007512568d7d0c00576a485966adaae20085
85e83c62055e866076d5d14022459e2d8ﬀ758ea1
6c040608a1a7be55bb38068303c45464678f0619
56586a25c2133a000269776f726d2e61786c387a
65f73d62797ca1b330c46e21fe6b1c78326f59314
30dc47768a4ab1d747970cd6e670e9b1a730a87
8ﬀafdf28ddaa38961431676f086164c7df3	

制御フローグラフ（CFG）	

CFGがあると?	
• プログラムの振舞に対する網羅的解析が可能	  – 既存の静的解析の技術を適用:	  抽象実行、モデル検査など	  • グラフから特徴ベクトルを抽出して自動分類	  – 機械学習など	  しかし、	  CFGを作ること自体が難しい!	

難しさ その１	
• 間接ジャンプ命令	  JMP [EAX]	
RET	• レジスタやメモリ状態を決定するためには値解析が必要	  – でも、値解析にはCFGが必要	  • 一般に静的には決定不能	

難しさ その２	
• CALL/RET命令が信用出来ない!	

CALL/RET	CALL labl
IMUL [EBP],6e
GS INSBXOR ESI, [EDX]db
FS “kernel32.dll”	
INSB	
…

labl:

PUSH [EAX]RET 	
LoadLibrary(“kernel32.dll”)	

難しさ その２	
• CALL/RET命令が信用出来ない!	  
– 標準的なコンパイラを使用しているとは限らない	  – CALL/RETが関数呼び出し/復帰となっているとは限らない	  – 従って、事前にプログラムから関数を切り分けることはできない	  • 他にも暗号化、難読化、自己書き換えなど	  対策	• 各機械命令を低レベルな記号式で解釈して記号評価	  • スタックを抽象化せず、ランダムアクセスメモリとして解釈	  CALL [EBX]	

dest	  ←	  Ld（M,	  EBX)	  ESP	  ←	  ESP-­‐4	  M←St(M,	  ESP,	  NextIP)	  EIP←dest	RET	dest	  ←	  Ld（M,	  ESP)	  ESP	  ←	  ESP+4	  EIP←dest	• プログラム全体解析(部分構造に分解しない)	  • 展開型制御フロー解析	

展開型制御フロー解析	
entry	

静的解析	
動的解析	
記号評価	
間接ジャンプ	
未解決	

解決	

未実行領域	

実行時とメモリ内容が異なる	

暗号化	?	

1. 静的解析を開始(CFG作成)	  a. 直接ジャンプを辿ってできるだけ展
開	  b. 間接ジャンプの行き先を記号評価
を用いて解決	  c. もし定数アドレス値に定まったらその先をさらに展開	  d. 解決可能な間接ジャンプがなくなるまで繰り返し	  2. 動的解析を開始	  a. 作成されたCFGを参照しながら動的実行	  b. もしも、	  i. 実行がCFGをはみ出した	  ii. 実行中にコードが書き換わった	  場合はそこから静的解析を行う	
3. 実行が終了するまで繰り返す	

ここまでのまとめ	
• 静的解析でできるだけ頑張ってCFGを作成する	  • 静的には解決できない間接ジャンプのために動的解析を利用する	  • 一回の解析プロセスで静的/動的を切り替えるので、	  – 静的解析は動的な情報を参照可能	  • 変更があったメモリ、途中で読み込まれたDLLなど	  – 動的解析は(その時点での)CFGを参照可能	

システム概観	
StaZc	  Analysis	Dynamic	  Analysis	

Build	  CFG	Symbolic	  EvaluaZon	

Target	  Program	
Loader	(PEB)	
Fake	  Env	 Process	  Thread	Bochs	
Soiware-­‐based	Controller	

FLIRT	  (experimental)	

Windows	  OS	  (Real	  System)	

or	 Ether	  (Xen	  HVM)	

Win32	  API	  DB	

Hardware-­‐based	• Single	  Step	  ExecuZon	  • Memory	  ModiﬁcaZon	  Check	  • Build	  New	  CFG	  if	  any	  discrepancy	  found	出力例	  (Win32/Rustok.B)	
実行トレース	
復号化	CreateSerivceA	

APIテーブル	  作成	

実行されなかったブロック	  ルートキット
導入	

ルートキット未導入	

OpenSCManagerA('', '', 983103)
CreateServiceA(0, 'pe386', 'Win23 lzx
files loader', 16, 1, 1, 0, '‘,'Base',0, '', '', '‘)RegCreateKeyA(2147483650L, 'system\\CurrentControlSet\\Services\\lzx32‘,134580)
lstrcatA('\\??\\', '‘)RegSetValueExA(16, 'ImagePath', 0, 1,134328, 4)
RegSetValueExA(16, 'DisplayName', 0, 1,4201371, 21)
RegSetValueExA(16, 'ErrorControl', 0, 4,4200764, 4)
RegSetValueExA(16, 'Start', 0, 4,4200768, 4)
RegSetValueExA(16, 'Type', 0, 4,4200772, 4)
RtlInitUnicodeString(134328,u'\\registry\\machine\\system\\CurrentControlSet\\Services\\lzx32‘)
ZwLoadDriver(134328,)
ExitThread(0,)	

RegCreateKeyA	

Node:	  253	  Edge:	  284	  Time:	  722s(StaZc)	  392s(Dynamic)	  Indirect	  Jump:	  114(3	  unresolved)	  	静的解析について	
StaZc	  Analysis	Dynamic	  Analysis	

Build	  CFG	Symbolic	  EvaluaZon	

Target	  Program	
Loader	(PEB)	
Fake	  Env	 Process	  Thread	

Bochs	
Soiware-­‐based	Controller	

FLIRT	  (experimental)	

Windows	  OS	  (Real	  System)	

or	 Ether	  (Xen	  HVM)	

Win32	  API	  DB	

Hardware-­‐based	• Single	  Step	  ExecuZon	  • Memory	  ModiﬁcaZon	  Check	  • Build	  New	  CFG	  if	  any	  discrepancy	  found	記号評価	
1.

直接ジャンプを辿ってCFGを展開	  各命令を単純な代入文列に変換	  2.
1	ECX	  1←
ECX	  ←	  0	  	  0	  	   X	   OR	  ECX,	  ECX	  4000
M	  1←M	  ←	  S	  St(M,	  t(MLd(St(MESP40100)	  ,	  ,	  4ESP100)	  ,	  4100),ESP )	  ⇨	  4100	
0E,	  SP,	  4002	  	  MOV	  [ESP],	  EIP	  1←EIP	  ←	  (	  ZF)?4020:400A	  (ZF0)?4020:400A	   4100	  	  ,ESP ),3:Ld(M ,ESP ))	  ⇨	  Ld(M ,ESP )	
4008	  	  JφZ	  (2:Ld(M4020		  04010	  0

10

1

3.

0

CFGを静的単一代入(SSA)形式	  • 定義式が一意となるように変数名を変更	  • Φ関数	  Ld(M1,ESP0)	

Ld(M1,ESP0)	2	• メモリ状態変数:	  M	  • 読出:	  Var←Ld(M,Addr)	  • 書込:	  M←St(M,Addr,Val)	  EBX	  1←	  *	  *	  E	  EBX	  EBX	  ←	  	  	  2	  2ABX0E	   BX,	  EBX	  400A	  DD	  Ld(St(MEAX
BX1)	  )	  ,ESP0)	  M	  2←E0BX)	  M	  ←	  S	  St(M,	  t(M1E,	  AX,	  E1,	  AX,	  0E,	  EBX1⇨	  E
BX	  (if	  E
SP-­‐EAX
100⇨0)	  400B	  MOV	  [EAX],	  EBX	  EIP←400E	  EIP2←400E	  ⇨Ld(M1,	  ESP0)	  (otherwise)	  		400E	  MOV	  E	 CX,	  EBX	  4010	  RET	  Ld(M ,ESP )		
24	0

3	4.

要求駆動型定数伝播	  ESP	  1←–0	  –4	  4	   ECX	  ESP	  ←	  E	  ESP	  SP4020	  P
USH	  • 各変数をその定義式で置換	  M	  3←M	  ←	  S	  St（M,	  t（M1E,	  SP,	  ESPE1CX)	  ,	  ECXLd(St（M1)	  ,	  ESP ,	  ECX ),ESP +4)	   • Use-­‐def鎖をたどる	  4022	  OP	  EBX	  EBX	  2←d(M,	  EBX	  ←	  L	  LPd(ME	  	  SP3E,	  SP)	  1)	  ⇨Ld(M ,	  ESP +4)	  (ESP +4	  –	  ESP ≠0)	  	• 記号代数演算	  ESP	  2←+1	  +4	  4	  	  400E	  ESP	  ←	  E	  ESP	  SP4024	  JMP	  Φ(A,A)	  ⇨	  A	  EIP	  3←Ld(M ,ESP +4)	EIP	  ←	  4	  400E	  00E	  f(φ(A,B),	  φ(X,Y))	  ⇨	  φ(f(A,X),f(B,Y))	  	  	Ld(St(M,A,V),	  A’)	  	  1

13

1

1

1

1

1

1

1

Ld(M3,ESP2)	

EBX3	  ←	  Φ(EBX,	  32:EBX)	  	  EBX←Φ(EBX,	  E1BX)	  ,	  EE1BX)	   E2BX	  4(2:EBX
400E	  MOV	  CX,	  Ld(φ4(2:M2,3:M3),φ4(2:ESP0,3:ESP2))	  ←	  (2:ESP,	  3:ESP)	  	  ESPESP←Φ(ESP,	  ESP)	  Φ(ESP,	  ESP)	  3	  4
20 0 2⇨φ4(2:Ld(M2,ESP0),3:Ld(M3,ESP2))	
4011	  ET	  (2:M
3:M3)	  	  MM←Φ(M,	  M
4	  ←	  Φ(M4R2,	  2,	  )	  M
3)	  ECX2←	  ←	  E	  EBX	  BX3	  ECX	  	  dest	  dest1←
	  ←	  L	  Ld(M,	  d(M4E,	  SP)	  ESP3)	  Ld(M4,ESP3)	
ESP4	  ←	  ESPESP←ESP	  +	  34	  +	   	  4	  dest1	
dest1	  =	  4100	
EIP4	  ←	  dest1	  EIP←dest	  	  ⇨	  V	  (if	  A	  =	  A’)	  	  	  	  	  	  Ld(M,A’)	  (otherwise)	  API	  ブロック	• 行き先アドレスがWin32	  API関数のエントリア
ドレスだった場合、APIブロックを作成	  	  GetProcAddress	
hModule	  ←	  Ld(M,	  ESP	  +	  4)	  addr	  	  ←	  Ld(M,	  ESP	  +	  8)	  – スタックの巻き戻し	  lpProcName	  ←	  LPCSTR(M,	  addr)	  EAX	  ←	  GetProcAddress(hModule,	  lpProcName)	  dest	  	  ←	  	  Ld(M,	  ESP)	  – 返り値を計算する	  ESP	  	  	  ←	  ESP	  +	  12	  	  	  ←	  dest 	  – 必要あれば文字列の評価も	   EIP	  	  	文字列解析	
MOV	  M2←St(M[EBX+0x2],	  ‘e’	  1,	  EBX1+0x2,’e’)	  MOV	  M3←St(M[EBX+0x5],	  ,	  E
BX+0x5,0)	  2
1 	  0x0	  MOV	  M4←St(M[EBX+0x4],	  ‘d’	  3,	  EBX1+0x4,’d’)	  MOV	  M5←St(M[EBX+0x1],	  ‘S’	  4,	  EBX1+0x1,’S’)	  MOV	  M6←St(M[EBX+0x3],	  ,	  E
BX+0x3,’n’)	  51 ‘n’	  	  	  	  	  hModule1	  ←	  Ld(M13,	  ESP	  +	  4)	  addr1	  	  ←	  Ld(M13,	  ESP	  +	  8)	  lpProcName1	  ←	  LPCSTR(M13,	  addr)	  GetProcAddress	  EAX7←GetProcAddress(hModule1,	  lpProcName1)	  dest	 5	  	  ←	  	  Ld(M13,	  ESP15)	  ESP16	  	  	  ←	  ESP15	  +	  12	  EIP3	  	  	  ←	  dest5 	  	  	addr1==EBX1	  +	  1	  lpProcName1←	  “LSen”+LPSTR(M
Send\0”	  Se”+LPSTR(M
S”+LPSTR(MPSTR(M12,	  addr
,	  12a,	  1)	  ddra,	  ddraddr12121+1)	  1+2)	  1+3)	  EAX7←GetProcAddress(hModule1,	  lpProcName1)	  EDX8==EAX7	  EDX8	  CALL	  EIPEBX	  	  EDX8	  5	  ←Send	  

1バイトずつ解析	==	  GetProcAddress(…,	  “Send¥0”)	

ループ		  	  EAXj← 	μX.φx(y:EAXj,z:X	  +	  4)	  EAXk	

EAXi←φx(y:EAXj,z:EAXk)	

φx(y:EAXj,z:EAXi	  +	  4)	  EAXi	  +	  4		  	  EAXk	  ←	  EAXi	  +	  4	各定義式 Vi←φx(y:Vj,	  …)について	  • ループ辺に沿った評価を行う	  • もし、Viが結果に再び現れる場合は、新しい変数Xに置き換えて不動点演算子
μXを導入	  • ループ辺以外の評価を行う.	  
• ループ不変が自明のときだけ簡約	  μX.	  Φ(X,	  A)	  ⇨	  A	  (loop	  invariant)	  	  	  • アドレス比較において不動点演算子が現れた場合は、その時点で比較失敗とする	  EDI2←Φ(EDI1,	  EDI3)	  …	  EDI3←EDI2+	  4	  M2	  ← St(M1,	  EDI3,	  val)	  	  EDI3	  ⇒μ	  X.Φ(EDI1,	  X+4)	
EAX4←Ld(M2,	  	  0x1234)		  	  動的解析について	
StaZc	  Analysis	Dynamic	  Analysis	

Build	  CFG	Symbolic	  EvaluaZon	

Target	  Program	
Loader	(PEB)	
Fake	  Env	 Process	  Thread	

Bochs	
Soiware-­‐based	Controller	

FLIRT	  (experimental)	

Windows	  OS	  (Real	  System)	

or	 Ether	  (Xen	  HVM)	

Win32	  API	  DB	

Hardware-­‐based	• Single	  Step	  ExecuZon	  • Memory	  ModiﬁcaZon	  Check	  • Build	  New	  CFG	  if	  any	  discrepancy	  found	動的解析に求められるもの	
シングルステップ実行	• 1命令ごとに実行	  • CFGとの違いをチェック	

ブレークポイント実行	  	• 不必要なところはスキップ	  • ライブラリ関数内など	  静的解析への	  実行時情報の提供	  	• メモリ上にロードされたコード	  • DLLのインポートテーブルなど	  	書き込み検知		• 復号化の検知	  • 自己書き換えコードの検知	

ステルス性	  	• ターゲットプログラムから実行
環境を検知されない	ソフトウェアベース動的解析	
• Bochs-­‐python	  (E.Carrera)がベース	  – BochsのデバッガインターフェースをフックしてPythonインタープ
リタを起動	  – Bochsの内部情報にアクセスするためのPythonインターフェース	  – CPUとメモリ部分だけ使用	  • 軽量な擬似実装環境	  – PEファイルローダ	  – 実行時情報(TEB,	  PEBなど)	  – Win	  32	  API	  のスタブ実行	  • ヒープ管理、ファイルシステムのエミュレート	  – ターゲットにWindows上で実行されていると勘違いさせるための最低限度の実装	  ハードウェアベース動的解析	
• Ether(ジョージア工科大)がベース	  – 	  Xen	  3.1を改変したイントロスペクションツール	  – SYSENTER命令を監視してシステムコールのトレース(システムコール名、引数、返り値)を出力	  	  – システムコールの終了を検知するためにページフォルト処理を用いたブレークポイントを利用	  • BPの置かれたシャドウページをはずす	  • PFが起きた場合	  – RWなら、一旦戻して、すぐはずす	  – Xで、BPの近くならそのままステップ実行	  	  CR3	

Guest	Shadow	PTE	

PDE	

PAGE	

比較	
シングルステップ	

ソフトウェアベース	

ハードウェアベース	

CPU	  LOOPを適時回数実行	

TFを使用	

ブレークポイント 	

シャドウページ	実行時情報	

Python	  APIを通して読み出し	

Guestページを読み出し	

書き込み検知	

Dirty	  Bitを使用	

xc_shadow_control	

ステルス性	••APIスタブを用意すれば環境はばれにくい	  CPU	  シミュ自体は検知可能	  •Guest側から検知することは困難	

特徴	+	  軽い(並列化可能)	  -­‐	  	  環境のエミュレートが完全ではない	+	  実環境に近い実行	  -­‐	  	  重い	

問題点	

•

•

スタブを用意するのが大変	  不安定!(特にブレークポイント)	

コードベースが古い!	

今後の課題	• 現在はProof	  Of	  Conceptの段階	  • 様々なアーキテクチャや実行モデルへの対応	  – Linux	  – シェルコード、デバイスドライバなど	  • ソフトウェアベース動的解析	  – 静的解析の結果を利用して振舞を変更?	  

• ハードウェアベース動的解析	  – Etherベース	  →	  Drakvuf/Libvmiベース	

Drakvuf(Tamas	  K.	  Lengyel)	
• エージェント無しでマルウェア実行	  – Sandbox側に特別なアプリをインストールしなくていい	  • エージェント無しでカーネルの関数呼び出しをモ
ニター	  – モニタ用DLLをインジェクトする必要無し	  • ファイルやヒープの生成をトレース	  – ファイルが削除される前に内容をコピー	  • VMをCopy-­‐on-­‐writeなクローンを作る	  – スケーラビリティ向上	  Drakvufの構成	
•Libvmi	  (Xen	  backend)	  – XenAccessの後継	  – XC(Xen	  	  Control)ライブラリに依存	  – イベントマネージャ(Register, Memory,	  Interrupt,	  SingleStep)	  – Python用API:	  pyvmi	  •VolaZlity	  – Memory	  Forensicツール(Windows/Linux/Mac	  OSに対応)	  – Pythonで書かれている	  – メモリアクセス用のプラグインとしてpyvmiを用いたものがある(Libvmiが配布)	  – Drakvufではファイルの書き出しに使用	  •Rekall	  – VolaZlityからのブランチプロジェクト(by	  Google)	  – DrakvufおよびLibvmiではPDB情報からNTカーネルのシンボルテーブルを作成するのに使用	  プロセスインジェクション	• 親プロセスのPIDを指定	  – vmi_pid_to_dtb:	  PID→DTB(CR3)	  • CR3の変更を監視(Register	  Event)	  – 親プロセスのCR3を見つける	  • KPCR→PCRB→CurrentThread	  • ユーザランドの復帰ポイントにブレークポイント	  – ユーザランドに戻ったら、スタックとレジスタを保存して、強引にCreateProcessAを呼び出す	  – プロセスの作成が終わったらスタック、レジスタを戻す	  ブレークポイント	• ブレークポイントを置きたい物理アドレスに0xCC(INT3)を書き込む(バックアップを保存)	  • メモリアクセスを監視(Memory	  Event)	  – ブレークポイントを置いたアドレスの読み出し/書き込みがあれば、一旦元に戻し、1ステップ実行後にまたINT3を書き込む	  • 割り込みを監視(Interrupt	  Event)	  – 現時点で監視可能な割り込みはINT3のみ	  – ブレークポイントを置いた場所で、なおかつ監視対象のプロセスであれば、ブレークポイントを除いて適時処理	  – 監視対象でないプロセスの場合は、一旦元に戻してから、1ステップ後にまたINT3を書く	

静的解析との連携	
• Drakvufをそのまま使うのは難しい	  – 現在はNTカーネルの特定のAPI呼び出しを監視するようにハードコードされている	  • 使えそうなのは	  – ブレークポイント機構	  – プロセスインジェクション	  – くらい？	  

• 実装上の問題	  – Pyvmiはイベント関連のAPIを実装していない	  • なので、追加してみた(実験中)	  – Pythonで同等の機能を書くことはできそう	  – シングルステップまわりがちょっと大変?	  
• プロセスの切り替えを監視して、対象以外はシングルステップをOﬀ	  • 対象プロセスでも、カーネルランドなどはOﬀ	  – Pythonで書ければ、VolaZlityやRekallなども使える?	  おわり	

何か良いアイデアやシステムがありましたら、	  いつでも教えてください。	

関連研究	
• 静的バイナリーコード解析	  – CodeSurfer/x86	  [Balakrishnan,	  Reps]	  – BAP	  (formerly	  known	  as	  Vine)	  [Brumley	  et	  al.]	  – Jackstab	  [Kinder]	  – BE-­‐PUM	  [Nguen,	  Quan,	  Ogawa]