はじめに

 今年のセキュリティ・キャンプでは,うっかり「なぜマルウェア解析は自動化できないのか」という題の講義を行ってしまったが,それだけセキュリティの世界には自動化の波が来ている.本稿では,脆弱性分析の自動化をめざして開発されているangr, AFL, Drillerをざっくり紹介する.

angr

 angrはUCSBの研究チームにしてCTFチームShellphishを中心に開発されているバイナリ解析フレームワーク.論文[PDF]はIEEE S&P 2016に採択されている.手法の新規性というよりは実装力でゴリ押しするタイプ.評価には,アメリカ国防高等研究計画局が5,500万ドル(約56億円)の資金を投じてまで開催した脆弱性分析・修正の自動化コンペ,DARPA Cyber Grand Challenge (CGC) のデータセットが用いられている.CGCの決勝戦に進出したチームには75万ドル(約7,600万円),優勝したチームは200万ドル(約2億円)が与えられる.angr開発の目的のひとつが,CGCでの勝利にあることは疑いようもない———最終的な戦績は,CMUのツールMAYHEMに優勝を譲って3位だったが.
 さて,angrはシンボリック実行やプログラムスライシングを通して,プログラムの特定位置に到達するための入力値を抽出することができる.次のコードで雰囲気をつかめるだろうか:

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
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import sys
import angr
import simuvex

# 解析対象を指定
p = angr.Project(sys.argv[1])

# 制御フローグラフの生成
cfg = p.analyses.CFG()
print [x for x in cfg.functions.iteritems()]

# シンボルを取得
target_addr = p.loader.main_bin.get_symbol("main").addr

# パス分析クラスのインスタンス
pg = p.factory.path_group()

# シンボルへのパスを分析
pg.explore(find = target_addr)

# avoidを避け,findに到達する入力値を探索してくれる
a = p.surveyors.Explorer(find = FIND_ADDR, avoid = AVOID_ADDR).run()

# フック
p.hook_symbol('strlen', simuvex.SimProcedures['stubs']['ReturnUnconstrained'])

# 実行結果のダンプ
a.found[0].state.posix.dumps(1)

 解析対象の規模が大きい場合,エントリポイントを起点とした解析に時間を要するあるいは失敗することがあるが,プログラムの途中から解析を始めることも可能だ.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p = angr.Project(sys.argv[1])

# 解析の起点となるアドレス
state = p.factory.blank_state(addr = START_ADDR)
# その地点までプログラムを実行したときのスタックの状態
state.regs.ebp = BASE_ADDR
state.regs.esp = STACK_ADDR

# 入力値の設定
for i in range(INPUT_LENGTH):
s = state.se.BVS('Var[{}]'.format(i), 32, explicit_name = True)
state.memory.store(INPUT_ADDR + i * 4, s)

path = p.factory.path(state)
a = p.surveyors.Explorer(start = path, find= FIND_ADDR, avoid= AVOID_ADDR)
a.found[0].state.posix.dumps(1)

 シンボリック実行はSSA形式の中間表現を前提とするが,angrはValgrindのVEX IRを用いている.バックエンドのSMTソルバはZ3だが,claripyという自前のラッパが噛ませてある.
 これ以上の説明は公式ドキュメントに譲ろう.

AFL

 AFL (American Fuzzy Lop) はGoogleのエンジニアlcamtufを中心に開発されているファジングツール.遺伝的アルゴリズムによって正常な入力を次々と変異させていき,自動的にプログラムのバグを検出する.AFLにはbashやtcpdump, OpenSSHといったさまざまなソフトウェアのバグを検出した実績があり,いまや脆弱性分析の研究になくてはならない存在だ.一般的なファジングはプログラムの浅い箇所にしか到達できない.AFLは,大量の正常な入力をトリミングしてシードとするコーパス蒸留 (corpus distillation) と,遺伝的アルゴリズムを用いてシードを変異させるGAFuzzingのいいとこ取りを図ったものだ.その実行フローは次のようになる:

  1. ユーザーから与えられた初期テストケースをキューに入れる
  2. キューから次の入力テストケースをひとつ取り出し,
  3. プログラムの振る舞いに影響を与えない最小サイズにトリミングする
  4. バランスのよい探索となるよう,さまざまな変異戦略を用いて入力を繰り返し変異させる
  5. 新たな状態遷移が計測されたら,出力をキューに入れる
  6. 2に戻る

 ここでAFLはカバレッジ計測のため,解析対象のプログラムに計測用のコードを埋め込む.これには,解析対象のソースコードが手元にある場合gccやclangの独自フロントエンドが,解析対象のソースコードが手元にない場合QEMUが用いられる.
 ファジング機能の中核は,afl-fuzz.cmain()から呼び出されるfuzz_one()にある.実装されている変異戦略は次の通り:

  • SIMPLE BITFLIP
  • ARITHMETIC INC/DEC
  • INTERESTING VALUES
  • DICTIONARY STUFF
  • RANDOM HAVOC
  • SPLICING

 CGCで優勝したCMUのMAYHEMは,このAFLにシンボリック実行機能を追加していたようだ.MAYHEMといえば同名のシンボリック実行エンジンの論文[PDF]がIEEE S&P 2012で発表されているが,当時からの変更点がどれほどなのかはわからない.
 また,AFLの拡張に,解析対象のパスを枝刈りすることで高速化を図ったAFLFastがある.これもCGC決勝進出チームによるもので,論文[PDF]はACM CCS 2016に採択されている.600行程度のパッチでトップカンファレンス.ちょっと妬ましい.

Driller

 Drillerはangrの開発陣によるAFLの拡張.論文[PDF]はNDSS 2016に採択されている.AFLのREADMEには次のようにある:

Other, more sophisticated research has focused on techniques such as program flow analysis (“concolic execution”), symbolic execution, or static analysis. All these methods are extremely promising in experimental settings, but tend to suffer from reliability and performance problems in practical uses - and currently do not offer a viable alternative to “dumb” fuzzing techniques.

 シンボリック(コンコリック)実行は実用的ではないと切って捨てている.DrillerはangrとAFLを組み合わせることで,この批判を克服し,ファジングとシンボリック実行のいいとこ取りを図ったものだ:

 たとえば,次のコードの解析には,ファジングよりシンボリック実行が適している:

1
2
3
4
5
6
7
int main(void)
{

int x;
read(0, &x, sizeof(x));
if(x == 0x123ABCD)
vulnerable();
}

 なぜなら,ファジングによって0x123ABCDという値を生成するには大量の試行を必要とするからだ.一方で,次のコードの解析には,シンボリック実行よりファジングが適している:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int check(char *x, int depth)
{

if(depth >= 100){
return 0;
}else{
int count = (*x == 'B') ? 1 : 0;
count += check(x+1, depth+1);
return count;
}
}

int main(void)
{

char x[100];
read(0, x, 100);

if(check(x, 0) == 25)
vulnerable();
}

 なぜなら,単純なシンボリック実行ではパス爆発を解決できないからだ.
 Drillerは両手法の長所と短所を踏まえた上で,それらを堅実に組み合わせている.やはりハッシュ関数の充足はDrillerをもってしても難しいようだが,現行MAYHEMもAFLとシンボリック実行を併用しているようだし,このアプローチが現在の着地点なのだろう.

おわりに

 CGCとそれにともなう研究によって,脆弱性分析の自動化手法は大きな進歩を遂げつつあることが伝わっただろうか.学会のOSS重視傾向も相まって,さまざまなツールを手元で試せるようになってきている.大変ありがたいことだ.

 ※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
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
...
>>> 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本体の実装を読んでいく.

 これはマルウェアに感染した端末の基板で構成されたトロイの木馬.国際会議Cyber Weekの展示の一環.

はじめに

 先週,イスラエル外務省からの招待でイスラエルのサイバーセキュリティ産業の視察に参加した.
 視察の参加者は日本政府・重要インフラ・セキュリティ業界関係に大別される.視察の目的は彼らにイスラエルの起業文化とサイバーセキュリティ技術を伝え,相互理解を図ることにあった.そんな視察になぜ一介のモラトリアム大学生でしかない私が潜り込めたのかというと,イスラエル外務省をハックしたから———というのは嘘.昨年発表したCODEBLUEというセキュリティカンファレンスのオーガナイザーにイスラエル大使館から打診があり,若者枠に組み込まれたという経緯である.なんと旅費はイスラエル外務省の負担.
 そういうわけで,記憶が錆びつかないうちに,イスラエルのサイバーセキュリティ事情を紹介したい.

総括

 最初にまとめてしまうと,イスラエルのサイバーセキュリティ産業は小国ゆえのフットワークの軽さがあってこそ成り立っている.とりわけ,以下の要素に負うところが大きい:

  • 徴兵制による人的つながり
  • R&Dを重視したスタートアップのエコシステム
  • 危機感

したがって,そのまま日本にあてはめて考えることはできないが,柔軟な組織間連携の体制は間違いなく参考になるはずだ.

徴兵制による人的つながり

 イスラエルでは,18歳から男性は36ヶ月,女性は21ヶ月にわたる兵役が義務づけられている.高校を卒業して大学に進学するのではなく,まず国防軍 (IDF) に組み込まれるというわけだ.ツアーガイドの方が「6ヶ月間の基礎訓練が終わってはじめて教官が名前を教えてくれる.それからは下の名前で呼び合う,生涯にわたる仲になる」というエモい話を聞かせてくれたが,この兵役での人的つながりが,イスラエルのサイバーセキュリティ産業に多大な影響を及ぼしている.分野を越えたコネクションが形成され,小国ゆえに誰がどのように優秀か国が一元的に把握できるためである.
 とりわけ優秀な人材はタルピオットという3年で数学と物理学の学位および中尉の階級を取得する人材育成プログラムに組み込まれるか,8200部隊という諜報部隊———かのStuxnetをNSAと共同で開発したといういわくつきの———に配属され,それらの出身者であることがキャリアパス上の絶大なアピールポイントとなっている.
 このように兵役による能力のフィルタリングがあるため,学生は日本のように就職活動をするのではなく,優秀だった順に政府機関や企業から声がかかるという.多くの企業は軍との直接的なつながりを持たないが,重要インフラ事業者や政府のサイバーセキュリティ関連機関,軍需企業は軍と密接に結びついていて,盛んに情報を共有しているという.
 軍との関係は兵役が終わったらそれきりというわけではない.たとえば視察時に開催されていたCyber Week併設の全年齢対象CTFでは,空軍が(おそらくリクルートを兼ねて)作成した問題が用いられていた.開始早々に見学した問題の内容としてはMetasploitを用いるペンテストのようなものや,Androidアプリケーションのリバースエンジニアリングなど.

R&Dを重視したスタートアップのエコシステム

 さて,イスラエル政府が擁するサイバーセキュリティ関連機関は軍を除くと次のような構造になっている:

 国家サイバー局は日本でいうところの内閣サイバーセキュリティセンター (NISC) 的な立ち位置で,サイバーセキュリティ関連の産業育成と防衛について政府に進言する立場を担っている.国家サイバーセキュリティ委員会は各種標準化団体のほかCSIRTとしてIL-CERTを抱える機関である.IL-CERTではSTIX/TAXIIを用いた情報共有体制が確立されており,検体の挙動をタグベースで共有することで,機微情報を漏らすことなく複数機関にまたがったインシデントに対応できるようになっているらしい.視察では,ウェブベースの情報共有ツールも紹介された.
 国家サイバー局の下部にあるCyberSparkはイスラエル南部の中心都市ベエルシェバにある研究開発特区・機関で,ベンチャーキャピタル,国内のスタートアップ企業のほか,IBMやLockheed Martinといった多国籍企業,隣接するベン・グリオン大学から構成される.ネゲブ砂漠の開発を進めつつ,競合他社を大学との共同研究という形でまとめ,その研究をスタートアップとして興すことを目的としているようだ.ICRCもまたテルアビブ大学を中心とした同様の学際的研究機関で,Cyber Weekのオーガナイザーでもあった.これらは東大京大と産総研やNII, NICTが直接つながっているようなものだと思えばよいが,研究内容を即座にスタートアップ化する点は興味深い.
 IC3は国営の軍需企業IAI (Israel Aerospace Industries) を中心としたジョイントベンチャーで,2020年の東京オリンピックに向けた日本市場開拓を虎視眈々とねらっている.
 この構造には,政府機関のほか次のようなベンチャーキャピタルとスタートアップ推進企業が噛んでいる:

 BVPはアメリカ最古のベンチャーキャピタルだが,イスラエルのサイバーセキュリティ産業に熱視線を投げかけており,後述のTeam8やillusive networksなどに投資している.
 JVPはイスラエルのベンチャーキャピタルで,CyberSparkを構成する企業のひとつである.Cyber Labsという研究部門も設けており,軍と連携を図りつつ,国内のスタートアップをいくつも育成してきた.興味深かったのはCyActiveなる企業の取り組み.遺伝的アルゴリズムを用いて既存のマルウェアを変異させることで,亜種そして未来のマルウェアに対して頑強なヒューリスティックエンジンを開発するといった研究を行っているそうだ.折しも今年のはじめに国際会議NDSSにおいて(PDFファイルに限定してはいるものの)類似の研究が発表されており,今後の動向に注目したい.
 Team8はサイバーセキュリティのR&Dをスタートアップ化することを目的としたインキュベーション企業で,illusive networksの母体である.Team8の創設者はかの8200部隊出身者であり,軍で培った問題意識やマネジメント能力が糧となっていると語る.
 これらの企業の支援のもと興ったスタートアップは,狭いイスラエル国内でシェアを握るのではなく,海外市場の開拓とCyberSparkに参画しているような多国籍企業へのイグジットを目的としている.
 しかしこうした産学軍連携のスタートアップ促進体制は,イスラエルが小国であり,かつ物騒な隣人に恵まれていて,軍が産業の中核に食い込んでいるという特性(それは同時に「だからこそイスラエルはサイバーセキュリティ先進国である」というイメージを抱かせることにも寄与している)あってこそだろう.

危機感

 彼らの口ぶりからすると,やはり周辺諸国との関係がサイバーセキュリティ産業の発展を後押ししているようだ.
 たとえば,イスラエル電力公社は国内の電力を一手に担っており,発電所がサイバー攻撃によって停止してしまえばイスラエルの国防は壊滅的な打撃を被る(もちろん周辺諸国からの給電は望めない).したがって彼らのサイバーセキュリティに対する意識はきわめて高い.彼らのSOCは各施設に派遣されたオペレーターとそこからのアラートを分析する本社施設に分散して設置されており,情報の集約(縮約)と即時共有に力を入れている様子がうかがえた.
 また,電力公社の子会社として,電力制御システムに対するサイバー攻撃とその防御の訓練施設CyberGymがある.CyberGymは電力公社における訓練のみならず,他社からの依頼に応じてその運用環境を可能な限り再現,かつ攻撃ベクタを強調した環境を用いた5日ほどの演習サービスを提供している.演習場には小型のプラント装置が設置されており,攻撃によってはそこから水が噴き出してくるという.そうした物理的な(!)非常事態への対応力を養うことも,演習の目的であるようだ.
 電力公社のほか,IAIは企業のネットワークに対するサイバー攻撃演習サービスを提供している.IAIの演習では,仮想マシン・仮想ネットワーク上の演習環境を用いて,シナリオベースで攻撃への対応を学べるようになっている.
 電力公社・IAIとも,ベンダを問わずハードウェア・サーバソフトウェアを柔軟に組み替えられる環境を提供しており,有事———つねに有事ともいえる———に備えた訓練に余念がない.

おわりに

 ざっくりとではあるが,イスラエルのサイバーセキュリティ事情を紹介してきた.
 国防上の要請があるため,どうしても緊張感は漂っているし,そこばかり強調したような文章になってしまったが,いい国だと思う.海は綺麗だし,食事も野菜が多く健康的で美味(帰国したらすぐに口内炎ができてしまった).なにより,技術者が必要とされ,尊敬される風土である.サイバーセキュリティ関連の事業を興したいのであれば,移住を十分検討していい.とりあえずビザ申請しておくか…….
 はじめに断ったとおり,私はインテリジェンス活動や最新の脅威分析に携わっているわけではない,しがない学生なので,提示できる情報の解像度はこの程度である.同行したソフトイーサ登さんのレポートも参照されたし.
 そのほかメモと感想:

  • テルアビブ大学の学生のポスターセッション,みんな(セキュリティ分野なのに)機械学習やってて海外でも流行ってるんだなと思った
  • 何の変哲もない(外には看板など一切なし)アパートの一区画を徴発して国家サイバー局が運営されていて流石にクソ興奮した,まあ見学者向けのダミーかもしれないが
  • イスラエル電力公社のSOCではおよそオペレーターの役には立たないだろう攻撃元の国をGoogle Mapにマッピングするシステムが表示されていたが,「可視化はきわめて重要だ.なぜなら,視察にきた海外政府関係者におたくの国からこれほど攻撃されている.ゆえに~とアピールできるからだ」と語っていたのがよかった.nicterやWADJETもそんな感じに使えるのかな
  • 在イスラエル日本国大使館大使公邸にお邪魔したら入口の扉が3つあってモンティ・ホール問題かよと思った
  • 飲み屋でチェイサーに水 (water) を頼んだら毎回ウォッカ (vodka) が出てくるので英語力の低さを呪っていたらロシア系移民のふざけた風習だった
  • エルサレムもテルアビブも治安としては渋谷とかその辺程度
  • 人工知能による意思決定の文脈でadversarial examplesの問題を引き合いに出していた人がいて,やはりセキュリティ分野ではルールベースというか決定木に起こせないとトリアージが効かないから難しいなと思った
  • 死海の名前の由来は「塩分濃度が高すぎて魚が住めないから」だそうだが,湖水の比重が高く多少の風では波立たないため時間が停まっているように見える様子が死を連想させる
  • IED兵士はみんなタボールを抱えているのかと思ったらベエルシェバの検問を除いて警察と同様みなCAR-15系にジェリコだった
  • イスラエルはLGBTに寛容で多様性を尊重する国であるというイメージ戦略なのだろうか,カーナビの地図上でLGBT区域が緑色に表示されるらしい
  • ベン・グリオン国際空港の端末はWindows + IE9でアエロフロート機内の端末はLinuxベース
  • トランジットで立ち寄ったシェレメチェボ空港での入出国審査はロシアだし「Papers, Please」のような感じだと思っていたらそんなことはなかった
  • イスラエル出国審査時にパスポートの顔写真と顔が一致するかスキャンする(?)装置があったが,しっかりaccuracyが出るわけないのでおそらくはハリボテで,裏で人間がチェックしているのだろう
  • アラブ諸国に入国できなくなるという噂のパスポートへのスタンプは廃止されていた

 はい.


これはなに

 @img2cap fileという形式で画像を投げつけると説明文をつけ加えて返信するだけのTwitter bot.

しくみ

 CNN + LSTM.
 以下の論文や実装を参考にした.裏ではChainerが動いている.

 はじめは論文通りの活性化関数と勾配法を試してみたが,dsanno氏のいうようにSGDよりAdamの方が高速.MomentumSGDと比べてもみたが即Adam最高! という気分にさせられた.AdamがそもそもAdaGradとRMSPropのいいとこどりらしいので,その両者は試していない.なおネットワーク構成は論文のまま.
 データセットに含まれているのは写真8万枚とその説明文だけ.よってTwitterの各位がいくらイラストを投げつけようと無駄な話で,その手のニーズに対応するにはニコニコ静画のデータセットあたりを使う必要がありそう.これには画像とそのタグ,コメントを学習したモデルが含まれているそうだが,説明文の生成というタスクに向けてどう転移学習させるか目処は立っていない.
 当然ながら学習データと実際に各位が投げつけてくるデータの分布は全く異なるし,困ったものだ.

謝辞

 お遊びにGPU環境を貸してくれた@georgioush, @dasoran両氏に感謝.

 読書メモ.

はじめに

 人間の脳を模したニューラルネットの手法,深層学習ディープラーニングがめざましい成果を挙げている—といった謳い文句をよく目にする.だが機械学習の専門書を紐解いても出てくるのはロジスティック回帰のお化けばかり.
 われらがPRMLのニューラルネットを扱う章にはこうある.

しかしながら,パターン認識という実際的な応用の観点からは,生物学的な現実性などは全く不要な制約である.
                        — C.M.ビショップ『パターン認識と機械学習 上』 (p.226)

 では,機械学習の文脈で言うところのニューラルネットと脳はどれほど異なっているのだろうか?

ニューラルネットと脳の違い

 結論から言えば全然違うわけだが,ざっくり以下の三点から整理できる(と思う):

  • ニューロンのモデル
  • ネットワーク構造
  • 微分計算の手法

ニューロンのモデル

 現在広く普及している多層パーセプトロンは,単純な差分方程式であるMcCulloch-Pittsモデルをベースに,層を重ねたとき微分できるような活性化関数を組み合わせている.だがそれ以外にも膜電位が変動するメカニズムを考慮した:

  • Hodgkin-Huxleyモデル
  • FitzHugh-Nagumoモデル
  • Izhikevichモデル

などが提案されている—というようなことは機械学習の道具としてニューラルネットを扱っている本にはあまり書かれていない.ひとまず手元にあった:

はモデル名に言及しておらず,McCulloch-Pittsモデルを紹介していたのは:

だけだった.
 ちなみにこの中だと機械学習マジで何もわからんって人はまずサンプルコードを動かしながら『ITエンジニアのための機械学習理論入門』を読むとよい.深層学習については紫色の本が好み.青色の本は数式が追いにくい(どっちもどっちだが)上,深層学習以前と以後でどのような変遷があったのか不明瞭で,『進化計算と深層学習』は概論のみ.『イラストで学ぶディープラーニング』は読みやすく,汎化性能を向上させる方法も載っていて実践的ではあるが,RNNに触れられていないのが惜しい.
 さて,それではニューロンのモデルが複雑であれば脳に近いのかというと,どうやらそういうわけでもないらしい.たとえば複雑かつイオンコンダクタンスの挙動が緻密なHodgkin-Huxleyモデルは,ヤリイカの軸索のニューロンをモデル化したものだが,これはヒトの大脳皮質とはタイプが異なるようだ.
 しかし,McCulloch-Pittsモデルには,STDP (Spike Timing Dependent Plasticity, スパイク時刻依存シナプス可塑性) を表現できていないという問題点がある.STDPはニューロンの発火タイミングに応じて重みを更新する規則で,脳はこれにより時系列を学習しているとされる.
 こういったことを把握するためにいくつか神経科学の本を読んでみた.だいたいの書籍がまず最初にニューロンのモデルを紹介し,それからニューロンの同期に章を割き,つづいて脳の任意の部位の詳説という体裁をとっている.

など.全部読んだ感想としては『脳の計算論』が最も明快かつ簡潔で,STDPにも詳しく,この記事で触れている範囲のことはほぼカバーしている.
 Izhikevichモデルの考案者も『Dynamical Systems in Neuroscience: The Geometry of Excitability and Bursting』という本を書いているのだが,これは難しそう.
 本腰を入れて学ぶには「シナプス可塑性の初心者へ 推薦論文リスト」を消化すべきなのだろう.

ネットワーク構造

 パーセプトロンは小脳に,BESOMは大脳皮質に,畳み込みニューラルネットは受容野に,TD学習は大脳基底核に似ていると言われている.ではどこが.
 小脳についてはさきほど挙げた『脳の計算理論』がよい.この著者は小脳による運動の内部モデル獲得というテーマの大家だそうで,公開されている無料のPDFでその足跡が追える.Hodgkin-Huxleyモデルの解説も丁寧.あわせて“現代の小脳パーセプトロン仮説”も読みたい.
 大脳皮質についてはBESOMの人の「大脳皮質と deep learning の類似点と相違点」がとにかくわかりやすい.やはり正則化が重要なようだが,それについては「脳とネットワーク/The Swingy Brain:まとめてスパースコーディング - livedoor Blog(ブログ)」に挙げられている論文を読むとよさそう.
 さらなる部位との関連については,「全脳アーキテクチャ解明に向けて」から辿れる資料が親切だった.特に「海馬神経回路の機能ダイナミクス」で触れられている内容は元論文の古さとは裏腹にあまり書籍では見ない.

微分計算の手法

 みんな大好き誤差逆伝播法は脳では使われていない.じゃあどうすればいいかというと:

がある.後者2つは深層学習の大家であるBengioらの研究で,ここでSTDPが重要となってくるらしい.生物学的な妥当な深層学習まであと何年だろうか.

おわりに

 機械学習のことは多少わかるけど(計算論的)神経科学については何から勉強すればいいのかもわからないというところから,騙し騙しとはいえ論文を読める程度になるにはこのあたりを読むとよいのではないかと思います.
 なお,このブログに貼られているAmazonリンクはいずれも素のリンクです.ご安心ください.アフィリエイトリンクを貼りまくって小銭を稼ごうと画策しましたが審査に落ちました.

 わざわざブログに書くほどでもないことから書いていかないとなまるので書く.

はじめに

 寿司 虚空編[1]第2話で登場したアッカーマン関数というかS変換を実装する.

定義

 $x, y$を非負整数として,

$$Ack(x,y)= \begin{cases} y+1 & \text{if}\ x=0, \\ Ack(x-1,1) & \text{if}\ x>0, y=0, \\ Ack(x-1,Ack(x,y-1)) & \text{otherwise}. \end{cases}$$

 恥ずかしながら「Union-Find木のならし計算量はアッカーマン関数の逆関数となる」といった説明でしか見たことがない.

実験

 何も考えずに$Ack(3, 3)$を実装.なお記号は寿司 虚空編に準拠.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def f(x):
return x + 1

def b(m, n):
if m == 0 and n > 0:
return f(n)
elif m > 0 and n == 0:
return b(m - 1, 1)
else:
return b(m - 1, b(m, n - 1))

def g(x):
return b(x, x)

def main():
print g(3) # Ack(3, 3)

if __name__ == "__main__":
main()

 実行してみる.ついでにプロファイリング.

1
# python -m cProfile -s time ./sushi.py
61
         3624 function calls (1193 primitive calls) in 0.006 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   2432/1    0.005    0.000    0.006    0.006 sushi.py:4(b)
     1188    0.001    0.000    0.001    0.000 sushi.py:1(f)
        1    0.000    0.000    0.006    0.006 sushi.py:15(main)
        1    0.000    0.000    0.006    0.006 sushi.py:1(<module>)
        1    0.000    0.000    0.006    0.006 sushi.py:12(g)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

 このプログラムで$Ack(x, y)$を計算しようとするとRuntimeError: maximum recursion depth exceededとなって死ぬ.
 そこで次の手法を導入する:

  • スタック制限の緩和
  • 再帰深度制限の緩和
  • メモ化再帰
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
import sys, threading, thread

memo = {}

def f(x):
return x + 1

def b(m, n):
if (m, n) not in memo:
memo[(m, n)] = (
f(n) if m == 0 and n > 0 else
b(m - 1, 1) if m > 0 and n == 0 else
b(m - 1, b(m, n - 1))
)
return memo[(m,n)]

def g(x):
return b(x, x)

def main():
print g(3) # 61

if __name__ == "__main__":
sys.setrecursionlimit(1024*1024)
thread.stack_size(128*1024*1024)
threading.Thread(target=main).start()

 やる.

1
# python -m cProfile -s time ./sushi.py
61
         415 function calls in 0.002 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.002    0.002 threading.py:1(<module>)
        1    0.000    0.000    0.000    0.000 collections.py:1(<module>)
        1    0.000    0.000    0.002    0.002 sushi.py:1(<module>)
        7    0.000    0.000    0.000    0.000 {method 'acquire' of 'thread.lock' objects}
        1    0.000    0.000    0.000    0.000 heapq.py:31(<module>)
       91    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        2    0.000    0.000    0.000    0.000 sre_parse.py:379(_parse)
       28    0.000    0.000    0.000    0.000 sre_parse.py:182(__next)
        2    0.000    0.000    0.000    0.000 sre_compile.py:359(_compile_info)
       73    0.000    0.000    0.000    0.000 {len}
        2    0.000    0.000    0.000    0.000 sre_compile.py:32(_compile)
       26    0.000    0.000    0.000    0.000 sre_parse.py:201(get)
       22    0.000    0.000    0.000    0.000 sre_parse.py:138(append)
        1    0.000    0.000    0.000    0.000 {thread.start_new_thread}
        4    0.000    0.000    0.000    0.000 threading.py:259(__init__)
        2    0.000    0.000    0.000    0.000 threading.py:656(__init__)
        2    0.000    0.000    0.001    0.000 re.py:226(_compile)
       21    0.000    0.000    0.000    0.000 {ord}
        2    0.000    0.000    0.001    0.000 sre_compile.py:493(compile)
        1    0.000    0.000    0.001    0.001 warnings.py:45(filterwarnings)
        1    0.000    0.000    0.000    0.000 threading.py:308(wait)
        8    0.000    0.000    0.000    0.000 threading.py:58(__init__)
        2    0.000    0.000    0.000    0.000 sre_parse.py:675(parse)
        2    0.000    0.000    0.000    0.000 threading.py:560(__init__)
        1    0.000    0.000    0.000    0.000 threading.py:640(Thread)
        4    0.000    0.000    0.000    0.000 threading.py:241(Condition)
        2    0.000    0.000    0.000    0.000 sre_parse.py:140(getwidth)
        2    0.000    0.000    0.000    0.000 sre_parse.py:301(_parse_sub)
       12    0.000    0.000    0.000    0.000 {_sre.getlower}
       10    0.000    0.000    0.000    0.000 {isinstance}
        1    0.000    0.000    0.000    0.000 threading.py:726(start)
        2    0.000    0.000    0.000    0.000 sre_compile.py:478(_code)
        4    0.000    0.000    0.000    0.000 sre_compile.py:472(isstring)
        1    0.000    0.000    0.000    0.000 threading.py:1090(__init__)
        2    0.000    0.000    0.000    0.000 {method 'setter' of 'property' objects}
        1    0.000    0.000    0.000    0.000 collections.py:26(OrderedDict)
        6    0.000    0.000    0.000    0.000 {thread.allocate_lock}
        1    0.000    0.000    0.000    0.000 threading.py:602(wait)
        1    0.000    0.000    0.000    0.000 threading.py:124(_RLock)
        2    0.000    0.000    0.000    0.000 sre_parse.py:178(__init__)
        1    0.000    0.000    0.000    0.000 threading.py:627(_newname)
        1    0.000    0.000    0.000    0.000 threading.py:575(set)
        4    0.000    0.000    0.000    0.000 {min}
        2    0.000    0.000    0.001    0.000 re.py:188(compile)
        3    0.000    0.000    0.000    0.000 {thread.get_ident}
        1    0.000    0.000    0.000    0.000 keyword.py:11(<module>)
        1    0.000    0.000    0.000    0.000 threading.py:372(notify)
        1    0.000    0.000    0.000    0.000 {thread.stack_size}
        1    0.000    0.000    0.000    0.000 threading.py:709(_set_daemon)
        2    0.000    0.000    0.000    0.000 threading.py:541(Event)
        2    0.000    0.000    0.000    0.000 threading.py:299(_is_owned)
        2    0.000    0.000    0.000    0.000 {_sre.compile}
        3    0.000    0.000    0.000    0.000 {method 'release' of 'thread.lock' objects}
        1    0.000    0.000    0.000    0.000 threading.py:296(_acquire_restore)
        1    0.000    0.000    0.000    0.000 {sys.setrecursionlimit}
        2    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
        2    0.000    0.000    0.000    0.000 sre_parse.py:67(__init__)
        1    0.000    0.000    0.000    0.000 threading.py:399(notifyAll)
        1    0.000    0.000    0.000    0.000 collections.py:387(Counter)
        2    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
        2    0.000    0.000    0.000    0.000 sre_parse.py:90(__init__)
        1    0.000    0.000    0.000    0.000 threading.py:293(_release_save)
        1    0.000    0.000    0.000    0.000 threading.py:551(_Event)
        2    0.000    0.000    0.000    0.000 sre_parse.py:195(match)
        3    0.000    0.000    0.000    0.000 threading.py:63(_note)
        1    0.000    0.000    0.000    0.000 threading.py:1152(currentThread)
        1    0.000    0.000    0.000    0.000 threading.py:254(_Condition)
        2    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 threading.py:789(_set_ident)
        1    0.000    0.000    0.000    0.000 threading.py:1058(_Timer)
        1    0.000    0.000    0.000    0.000 threading.py:1088(_MainThread)
        1    0.000    0.000    0.000    0.000 {method 'insert' of 'list' objects}
        1    0.000    0.000    0.000    0.000 threading.py:422(_Semaphore)
        1    0.000    0.000    0.000    0.000 threading.py:1097(_set_daemon)
        1    0.000    0.000    0.000    0.000 threading.py:569(isSet)
        1    0.000    0.000    0.000    0.000 threading.py:56(_Verbose)
        1    0.000    0.000    0.000    0.000 threading.py:1128(_DummyThread)
        1    0.000    0.000    0.000    0.000 threading.py:1008(daemon)
        1    0.000    0.000    0.000    0.000 {issubclass}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 threading.py:514(_BoundedSemaphore)

 関数呼び出し回数が3624回から415回まで減り,4msec高速化.

おわりに

 それでも$Ack(4, 2)$でSEGVするのでこのお話はなかったことに.$2^{65536}-3$は遠い.

参考文献

 凧揚げの様子.

TL;DR:

 新年なので凧揚げをやる.
 具体的にはCylon.jsを用いてLeap MotionからRolling Spiderを操作し,ついでにSlackに通知する.
 依存関係は次の通り.

1
# npm install cylon cylon-keyboard cylon-leapmotion cylon-rolling-spider node-slack

Cylon.js

 Cylon.jsはロボティクス向けに開発されているJavaScriptのラッパーライブラリ.
 マイコンボードやドローン,スマートウォッチなど,さまざまなガジェットのSDKを統一されたインターフェイスで利用できる.反面,バグを踏み抜くと少ししんどい.
 たとえばキーボードに接続するには,次のように書く.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var Cylon = require('cylon');

Cylon.robot({
connections: {
'keyboard': { adaptor: 'keyboard' }
},
devices: {
keyboard: {driver: 'keyboard', connection: 'keyboard'}
},

work: function (my) {
my.keyboard.on('a', function(key) {
my.log("A PRESSED!");
});
}
}).start();

 これでお手軽キーロガーのできあがりだ.内部ではkeypressというモジュールが呼ばれる.

Leap Motion

 Leap Motionは人間の手の動きを入力に変換できるモーションセンサー.
 以前から研究室に転がっていたものの,これまでケツ叩きゲームにしか使われてこなかった.
 Cylon.jsで複数のガジェットを扱うときは,connectionsdevicesに追記していけばよい.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var Cylon = require('cylon');

Cylon.robot({
connections: {
'keyboard': { adaptor: 'keyboard' },
'leapmotion': { adaptor: 'leapmotion' }
},
devices: {
keyboard: {driver: 'keyboard', connection: 'keyboard'},
leapmotion: { driver: 'leapmotion', connection: 'leapmotion'},
},

work: function (my) {
my.leapmotion.on('gesture', function(g) {
my.log(g.type.toString());
if (g.type == "circle") {
...
}
});
}
}).start();

 これで手の動きが取れる.内部ではleapjsというモジュールが呼ばれる.
 次はドローンだ.

Rolling Spider

 Rolling SpiderはParrot社の小型ドローン.というとすぐドローンの定義は自律航行可能であるとかないとかクアッドコプターという呼称がどうとか言いだすやつがいるけど,ここではドローンと呼んでいる.
 それでは,Rolling SpiderをLeap Motionで操作してみよう.

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
var Cylon = require('cylon');

Cylon.robot({
connections: {
'keyboard': { adaptor: 'keyboard' },
'leapmotion': { adaptor: 'leapmotion' },
'rolling-spider': { adaptor: 'rolling-spider', uuid: '***' }
},
devices: {
keyboard: {driver: 'keyboard', connection: 'keyboard'},
leapmotion: { driver: 'leapmotion', connection: 'leapmotion'},
drone: { driver: 'rolling-spider', connection: 'rolling-spider' }
},

work: function (my) {
my.leapmotion.on('gesture', function(g) {
my.log(g.type.toString());
if (g.type == "circle") {
my.drone.takeOff();
} else if (g.type == "swipe" && !flag) {
var isHorizontal = Math.abs(g.direction[0]) > Math.abs(g.direction[1]);
if(isHorizontal){
if(g.direction[0] > 0){
my.drone.right();
} else {
my.drone.left();
}
} else {
if(g.direction[1] > 0){
my.drone.up();
} else {
my.drone.down();
}
}
} else if (g.type == "keyTap") {
my.drone.land();
}
});

my.keyboard.on("down", function() {
my.drone.land();
});
my.keyboard.on("m", function() {
my.drone.emergency();
});
my.keyboard.on("q", function() {
Cylon.halt();
});

}
}).start();

 とりあえずこれで動く.指を回すとドローンが飛び上がり,スワイプに応じて移動する.内部ではnode-rolling-spiderというモジュールが呼ばれる.
 複数台の機体に接続できるから,ドローンの編隊飛行も夢ではない.とはいえ,Bluetoothを経由した中央集権的な制御なので,自律飛行にはいたらないが.ほんとうに自律させたければ,ドローン側のファームウェアに手を入れる必要がある.Parrot社が公開しているRollingSpiderEduによると,どうやら共有ライブラリを用いてドローンのファームウェアに機能を追加できるようだ.いずれはレクサスのPVのように美しく飛ばしてみたいが,いっそドローンから自作したほうがいいかもしれないな.

 なおRolling Spiderの総重量は65gなので,空港等の周辺や人口中心地区の上空でのドローン飛行を制限する改正航空法の対象とはならない.

Slack

 凧揚げもChatOpsの時代.
 node-slackというモジュールと,ドローンのコールバック機能を用いれば,バッテリー残量をSlackに通知できる.SlackのWebHooks URLに投げるだけだ.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var Cylon = require('cylon'),
Slack = require('node-slack'),
slack = new Slack('https://hooks.slack.com/services/***');
...
work: function (my) {
...
my.drone.on('battery', function(){
slack.send({
text: ':battery:: ' + my.drone.getBatteryLevel() + '%',
channel: '#drone',
username: 'Drone'
});
});
...

 こんなふうに通知される.

 ちなみに,ドローンが移動するたびに通知なんかしていると「短期間に送信されたメッセージが多すぎるから表示しないよ!」と怒られる.

その他の凧揚げ

 Leap Motionによるドローンの操作はたぶんこの人が初.

 やっぱデカいドローンを飛ばしたいっすね.

おわりに

 ジェスチャーでドローンを操作できるようになったことだし,フォースの力みたいでかっこいいと思って,年始にRolling Spiderを多摩川の土手で飛ばしていたらドローン嫌いっぽい人にクソ怒られた.すいません.
 あとドローンといえば『伊藤計劃トリビュート』所収の藤井太洋「公正的戦闘規範」がおもしろいぞ!!!

謝辞

  • Leap Motionは@shunki9から借りた.
  • Rolling SpiderはGehirn Inc.に買ってもらった.

 本稿は慶應義塾大学SFC村井&徳田研 Advent Calendar 2015の19日目である.

TL;DR:

 村井研・徳田研の卒論・修論・博論アーカイブから過去の論文タイトルを収集し,RNNLM(Recurrent Neural Network Language Model, 再帰型ニューラルネット言語モデル)[1]を用いて論文タイトルを自動生成する.

手順

  1. 論文アーカイブを雑にスクレイピング.
  2. 簡単のため英語タイトルを削る.データサイズは540行・16294字.
  3. MeCabの-Owakatiオプションで分かち書き.単語数は6272と少ない.
  4. RNNLMで学習,出力.

 生成した論文タイトルは次の通り.

1
改変適応機環境におけるインターネット化の設計と実装
暮らし計算発見を利用したUDL機器
インターネットを用いた機器プローブ体系のVoDについて開発な攻撃運用手法
自律計算ネットワークの行動に-移動システムに関する研究
衛星情報を用いたビジュアライゼーション定義アーキテクチャ表をする検出ユビキタスノードのファイル構成に関する研究
あしあと適応セキュリティネットワークを用いた負荷議事取り入れたセンサNEMOMANET解決
ユーザエンティティに適した仮想な通信接近による制御対象の設計と実装
蓄積学校利用性のための再作業に関する持続
型連携ネットワークのインターネットに基づく遠隔コードの向けたデジタル機構の構築
アプリケーション:型と時間特定を用いた利用型路準拠相関の構築
自律電話教育における異種品質空間支援システムの設計と実装
位置AV端末著作授業特殊トポロジ型し分析高速構築
広域を利用した次応用におけるレイヤーな授業に関する研究プロシステムに関する研究
次制御対するカメラを利用したAd型間屋外パブリック構築
協調:不sネットワークにおけるOSストリーミングの考慮機器コミュニケーション配信システムの設計と実装
センサ環境におけるデバイスソフトウェア文字通信システム
無線作業めぐるにおけるパケットIP発信・支援機構
ELA上環境に応じたしたコンピュータ測定に関する研究
インターネット型プラットホームの遠隔パケットとシステム
無線コントロールセンサを考慮する参加参加サービスの研究
移動者における位置適応オブジェクト手法の研究
インターネットグルーピングの回覧性をシステムした経路消耗性の実現
自己情報を用いた実を量子よる協調表行動流通
デジタル前遠隔しるしの情報共有支援機構
ネットワークト可視ネットワークを車的基盤」関数の分析
環境Computing通信DVB携帯性に関する移動同期利用の設計と実装
マルチパスFunction無線センサノードを用いた技術マルチ支援支援促進に関する研究
スマート世代ネットワークにおける相互ブリッジ家電システムの設計と実装
インターネット情報のための興味無支援システムの構築
オペレーティング型IP環境のプロファイリング的な信頼に関する研究
実方向自動ポロジにおける同期機器性における研究
センサ-抽出生成を支援情報登録抽出機構の構築
アドホックOSにおけるOS環境のGlass性基盤機構の構築
DV地アプリケーションの者による最適いアルゴリズム
商上のための選択なMobile効率システムの構築
ユビキタス世代環境における効率Wireless情報のMarkit
系列演奏位置スレッドサービス二マッチングマルチプロアクティブモデルの構築
パケット適応付け利用を考慮したネットワークブログモデルの設計と実装
TranS情報環境におけるグループホスト同期への安全履歴と分散
の情報対象でのMediatorコラボレーションに関する研究
類似Allシステム
情報グループを利用するデジタル制御動画像配送システムの構築
RFIDを利用したネットワークのプラットフォーム転送に関する研究
周辺上セキュリティにおけるコンテキスト者基無線の提案に関する研究
Link型服行動RCSにおける効率しない機構
クラシック型車載インターネットを解決した分散音声なりすましシステム
Dynamic特徴解析に基づく仮想制御機構の設計と実装
多段CSMAにおける多様な解析管理機構の設計と実装
移動機:を用いた-コンテンツシステムの構築
技術センサ環境におけるホーム化による経路サーバ
アプリケーション回線に基づく薦環境におけるする作成への行動利用に関する研究
インターネットを用いたしたな動画ルールに関する研究
機器協調利用Efficientのネットワーク解決のエンド映像構築
計算情報を利用した家電抽象の迷い連携への構築
関連情報教育における動的メールイベント収集の研究
通知におけるデータベース方式購買によるした状態時間グループに関する研究
コンテキスト:6のためのための設計と実装
電子ネットワークのための提案と実装
自己電話を利用したオブジェクト分散型授業属性制御機構の実現
ネットワークの抽出化環境の向上圧縮システムの構築
Networks対戦ネットワークにおける家庭テリトリー手法の構築
広バイト依存患者のための収集及び積極システム
IPコンテキスト精度点のデータベース的と-発見環境動画像モデル行動-
通信作業システムの含む属性センサノード付け可能メディアの提案と開発
情報世代環境時による最適視点環境機構の設計と実装
協調蓄積モバイルバッテリ支援Shumu機器型設置インシデントIrma保護量
分散回線にセンサデータ適応をマッチングと基準化に関する研究
環境さ時複数用方式と審議に関する研究
自律リンク環境におけるインターネット・属性品質
オブジェクトしにおけるインタフェース技法化推薦機構の研究
インターネットにおける光を用いた最適遠隔支援環境の構築
モーバイルs利用とへの実現自動手法の設計と実装
インターネットに適した時端末型TCP型データ基準の内
インターネットを用いた受信・辞書収集
DOS的利用環境におけるbased配信システムの構築
i:と利用した情報モーダルの作成に関する研究
APIの情報におけるソフトウェアするをシステムの自律
インターネットを用いたセル内回避手法アプリケーションFunction選択制御機構
マルチ:ユーザ時のLooking支援競合の参加情報に関する研究
マルチネットワークによる動的リモコンアーキテクチャの分析に関する研究
インターネット:文字を含むと対策軽減地理ファイルの構築
アプリケーションのデジタル行動環境における負荷教育の設計と実装
移動制御型メディア取り入れたにおける自律トポロジモデルの提案
日本回線時におけるセンサのアーキテクチャ
『世代sionを支援情報ユーザの実現
Mobileの行動空間に基づくするコンポーネントシステムの設計と構築
キットライブラリのアドレス利用を支援するアプリケーションの行動に関する研究
間:環境における認証検出の考察
鍵盤を用いた基盤経路トポロジ支援手法の研究
RFIDネットワークを用いたとユーザ
自律型機的な支援レイヤー手法の設計と実装
アドホックを用いたデジタル最適暗号システムの研究
WWW人IPvシステムの動的2を化フローインフォメーション配送化手法
次的機タフェース6システムの実現
IPレイヤーネットワークにおけるグループ取得遠隔システムに関する研究
二通信ユニバーサルにおける複数共有再についての研究
Tapirus上の情報的実現あるの構築
環境上における仮想指機構の構築
インターネットにおけるRFID経路エンドノードデータベース付けモデルの設計と実装
2回線学習への効率的型環境の提案と構築
...

 これはRNNLMが生成した論文タイトルを100件無作為抽出したもの.全リストはgistに置いている.この程度のデータサイズでRNNLMの性能を云々するのはいささか危うい気がするが,論文タイトルの末尾はえてして「~の構築」「~の研究」「~の実現」になるというルールを獲得できている,ということだろうか.
 同じデータセットから,ありがちな2単語プリフィックスのマルコフ連鎖で生成した論文タイトルは次の通り.

1
注目した二点間接続基盤ソフトウエアの構築インターネット
地域における高等教育協力手法の研究ホームネットワークにおける多様
かつスケーラブルな識別子管理システムゲームコンソールに対応する管理
運用基盤分析に関する研究ポリシ経路制御に関する研究大
任意の物理的量子ビットに対する効率的な情報閲覧
脳疲労検知システムの提案次世代インターネット経路制御を用い
鍵交換機構の実装と評価初等中等教育におけるWWW
プロセスデザイン片方向ブロードキャストメディアを用いたユビキタスコンピューティング環境に適し
連携システムの設計と実装exPhoto:周辺機器と撮影
に関する研究分散環境におけるプロアクティブ制御方式に関する研究アドホック
...

 パッと見でRNNLMが生成した論文タイトルの方がより自然に思える.で,RNNLMって何なの?

RNNLM

 読んで字のごとくRNNLMはRNNの言語モデルへの応用である.
 RNNは内部に有向閉路をもつニューラルネット.系列データの各時刻$t$につき1つの入力$x^t$をとり1つの出力$y^t$を返す.ふつう順伝播型ニューラルネットは入力1つをとり1つの入力を与える写像を表現するが,RNNは任意の系列—すなわち過去のすべての入力から任意の系列への写像を表現する.
 これは時刻$t-1$の隠れ層の出力を,時刻$t$の隠れ層の入力に与えることで実現される.

 文章は系列データであり,文章に含まれる各単語は直前の単語の並びに依存している.そこで,1990年のエルマンネット[2]以来,RNNを用いた文章の分析が試みられてきた—近頃「RNNは深層学習の一種」というような言辞を見かけるが,RNN$\in$深層学習ではない
 RNNLMと既存手法との相違点は,単語を潜在空間に写像して単語の意味を獲得しようとしているところだ.
 上図において隠れ層のベクトルは単語の潜在ベクトルとその履歴より$\begin{split}s(t) =& f(Uw(t) + Ws(t-1))\end{split}$となる.次の単語の確率は$\begin{split}y(t) =& g(Vs(t))\end{split}$となる.
 ここで活性化関数$f(z)$は標準シグモイド関数で,$g(z)$はソフトマックス関数$\dfrac {e^{zm}} {\Sigma _{k}e^{zm}}$である.
 学習では確率的勾配降下法を用いて重み$U$, $W$, $V$を更新していくが,このときRNNLMは各層を時間方向に展開し,最後の時刻$t$から誤差逆伝播計算をおこなう(BPTT, Backpropagation through time法).
 ここにおいてRNNは多層の順伝播型ニューラルネットのようにみなせる.

 BPTT法において,ある時刻$t$における出力層の誤差は正解ベクトル$d(t)$から出力$y(t)$を引いた出力誤差$e_{o}(t)$と,時刻$t+1$から伝播してきた誤差の和となる.ここでたとえば$V(t+1) = V(t) + s(t)e_{o}(t)^t\alpha - V(t)\beta$$\alpha$は学習率であり,各層で行列の勾配に掛かる.$\beta$はL2正則化の係数.
 このBPTT法で長い系列を扱うとき勾配が消失してしまう問題[3]があり,解決策としてLSTM(Long Short-Term Memory, 長・短期記憶)[4]が提案されているが,割愛する.
 なお今回のパラメータは次の通り.

1
last probability of validation data: -441.610349
number of finished iterations: 14
current position in training data: 0
current probability of training data: -441.576456
save after processing # words: 0
# of training words: 6272
input layer size: 1295
hidden layer size: 200
compression layer size: 0
output layer size: 1096
direct connections: 0
direct order: 3
bptt: 6
bptt block: 10
vocabulary size: 1095
class size: 1
old classes: 0
independent sentences mode: 1
starting learning rate: 0.100000
current learning rate: 0.000195
learning rate decrease: 1

おわりに

 恥知らずのクソ野郎なので何番煎じともわからない記事を書いてしまった.元ネタはNLP論文ネタ一覧
 このほか青空文庫やなろう小説[5]をRNNに学習させてはいるが,LSTM込みでもいまだ人間が見て自然に思える文章の生成は難しく思える.
 いずれは論文タイトルばかりか論文の内容も自動生成して知の欺瞞をもう一発カマしたいのだが.SFC自体が知の欺瞞っぽいところはさておき.
 物語の自動生成なら円城塔がなんとかしてくれるだろう.

参考文献

 本稿は情報セキュリティ系論文紹介 Advent Calendar 2015の11日目である.

TL;DR:

 テイント解析(taint analysis)やプログラムスライシング(program slicing),記号的実行(symbolic execution)やファジング(fuzzing)といったバイナリ解析技術を総動員して,マルウェアが通信するC&CサーバのフィンガープリントをC&Cサーバと通信せずとも生成する手法—AUTOPROBE[1]を紹介する.

背景

 マルウェアによるサイバー犯罪はC&Cサーバやコンフィグファイルの配布元,二次検体の配布元など様々な悪性サーバ(malicious server)からなるインフラによって支えられている.攻撃者はこれらの悪性サーバを頻繁に閉鎖・移転させて対策から逃れようとする.とりわけ攻撃者の命令を送信してマルウェアの動作を決定するC&Cサーバはその後の攻撃の起点となるため早期発見が望ましい.したがって不審なサーバがC&Cサーバかどうか判定するフィンガープリントが必要となる.
 しかしながら従来のフィンガープリント生成手法にはC&Cサーバとの長期的な通信を前提としている[2],サーバとして動作するマルウェアを前提としている[3]といった問題点があった.

問題定義

 あるマルウェアのファミリFに属する検体Pを入力として受け取り,Fが用いるC&Cサーバのフィンガープリントφを出力することがAUTOPROBEの目的である.C&Cサーバ側のコードは参照できず,マルウェアの検体はシンボル情報やソースコードを含んでいなくともよい.またマルウェアは複数のリクエストをC&Cサーバに送信するものとする.

提案手法

 あるサーバにマルウェアと同様のリクエストを送って,マルウェアがコマンドとして解釈できるレスポンスが返ってきたら,そのサーバは疑いようもなくC&Cサーバである—AUTOPROBEの鍵となる発想は至極単純だ.
 AUTOPROBEは検体の命令・API・システムコールの実行を—おそらくQEMUによって—トレースし,リクエストを生成する処理とレスポンスをハンドルする処理をそれぞれマルウェアから抽出する.つづいて前者によって不審なサーバに対するリクエストを生成し,後者によってレスポンスをハンドルする.レスポンスハンドリングの可否をもってフィンガープリントとするから,その処理の抽出さえできれば不審なサーバがC&Cサーバかどうか判定するまで実際のC&Cサーバと通信する必要はない—でもどうやって?

リクエスト生成

 マルウェアの多くは時間や擬似乱数,OS情報などの環境依存の値によって動作を変更する.たとえばWin32/LoadMoney.AFはレジストリキーの有無によって送信するリクエストを変更する.

 不審なサーバがC&Cサーバかどうか判定するためには攻撃者の期待するリクエストをより多く送信しより多くレスポンスを得たい.そこでAUTOPROBEは以下のアルゴリズムにしたがって複数の実行トレースを得る.これは条件分岐の度に直前のシステムコールを参照する,ある種の深さ優先探索として実装される.

 さらにAUTOPROBEはトレースをスライスし,システムコールの結果に依存する値を環境依存の値として決定論的な値・定数と区別する.ここで環境依存の値を書き換えれば攻撃者の期待するリクエストを送信できるようになる.また環境依存の値に影響するシステムコールの戻り値に時間,IPアドレス,擬似乱数,OS情報など200種類のラベルを設定しているとのことだ.

レスポンスハンドリング

 生成したリクエストをC&Cサーバに送信してレスポンスを得たら,AUTOPROBEはレスポンスの各バイトを記号値として扱い,実行トレースから検体の分岐制約を充足する解およびスライスθ1を得る.ここで探索の終了条件はclosesocketexitprocessに到達した場合,データを受信してから50個の条件分岐にわたってそのデータを参照するものが存在しない場合である.つづいてレスポンスとして正しく解釈できない値を検体に与え,実行トレースから分岐制約を充足する解およびスライスθ2を得る.ここでηは以下の式によって得られる実行経路の類似度である.

 bnとfnはそれぞれ各スライスに含まれるユニークなコードブロックとシステムコールの数を示す.AUTOPROBEはηが閾値10を下回ればレスポンスを正しく解釈していない実行経路とみなしてスライスを破棄し,上回れば別々のハンドラであるとしてそれぞれの分岐制約をフィンガープリントとして保持する.たとえばこんなふうに.

 C&Cサーバからレスポンスを得られなければ,AUTOPROBEは記号的実行とファジング,フラグレジスタの書き換えによる強制実行(forced execution)を併用してレスポンスに依存する実行経路を探索する.

 このファジングでは検体にランダム値を与えるが,検体が用いるアルゴリズムがHTTPなど既知のものであればエラーメッセージのハンドラを起点に探索する.
 AUTOPROBEはこのように探索したレスポンスのハンドラをフィンガープリントとするが,期待されるレスポンスが得られずさきほどのアルゴリズムによって探索した場合は以下のようにC&Cサーバの尤もらしさを算出する.

評価

 論文ではふたつのデータセットを用いてAUTOPROBEの性能を評価している.ひとつはSality, ZeroAccess, Ramnit, Bamital, Taidoorを含む37ファミリ10亜種計370検体.もうひとつはネットワーク通信の特徴量に基づいてフィンガープリントを生成する既存研究—CYBERPROBE[2]で用いられた19ファミリ. “which have been kindly provided to us by the authors of CYBERPROBE”って書いてるけどAUTOPROBEと同じメンバーじゃねえか.
 検体の実行時間は5分.

リクエスト生成

 まずはリクエストの生成から.可能であればC&Cサーバとの接続をともなうがAlexaトップ10,000サイトは除外している.ここでAUTOPROBEはC&Cサーバに接続せずとも検体のバイナリを分析してCYBERPROBEと同様の結果を得ている.

 AUTOPROBEはふたつのデータセットに含まれる56ファミリのトレースから105のリクエストを生成した.生成にかかった時間は平均13.2分.リクエストはすべてHTTPであったとのこと.

レスポンスハンドリング

 生成したリクエストのうち76件がC&Cサーバからのレスポンスを引き出した.さらにAUTOPROBEはHTTP 200レスポンスコードを含む同数のランダムなレスポンスを生成し,検体に与えた.これはレスポンスハンドリングの可否によって検体の異なる挙動を確認したいためだ.結果として76件のテストケース中71件(93%)で検体は異なる挙動を示した—期待される受信データを得たマルウェアは一般に10以上のシステムコールと50以上のコードブロックを実行する.残りの5件はC&Cサーバではなかった.つまりAUTOPROBEはマルウェアの通信先がC&Cサーバかどうか正しく判定できている.

ケーススタディ

 たとえばBamitalのリクエストはファイル名・GetVersionExによって得たOS情報・DGA (domain generation algorithm) によって生成したホスト名を含んでいた.AUTOPROBEはこれらの値が依存するシステムコールを得ている.

 C&Cサーバと接続せずともHTTP/1.1 200 OKを与えればBamitalのハンドラは分析できるとのこと.
 また標的型攻撃に用いられるTaidoorのリクエストはGetAdaptersInfoによって得たMACアドレスに依存する値を含んでいた.これによってTaidoorのC&Cサーバは感染端末のみで動作するレスポンスを送信していたようだ.
 ドライブバイダウンロード検体であるSalityのC&Cサーバはspm/s_tasks.php, logos_s.gif, 231013_d.exeというファイルをレスポンスに含んでいた.AUTOPROBEはこれらのファイルの存在するサーバをSalityのC&Cサーバとみなす.などなど.

限定的な探索

 Malware Domain Listに含まれる9,500アドレスの近傍/24サブネット・2.6Mアドレスのスキャン結果.

 VirusTotal, Malware Domain List, そしてURLQueryに発見されていないC&Cサーバを特定できている.

インターネット全体の探索

 ここではBGPからインターネット全体をスキャンし,7,100万ものHTTPサーバを発見している.

 このうちマルウェア3ファミリのC&Cサーバをどれだけ発見できるかCYBERPROBEと比較した結果.

 CYBERPROBEが40件のC&Cサーバを特定しているのにたいしてAUTOPROBEは54件のC&Cサーバを特定している.
 高度化するマルウェアが通信内容を難読化・秘匿する傾向にあることを鑑みると,CYBERPROBEのようにネットワーク通信の特徴量を用いる手法よりもAUTOPROBEのようにバイナリ解析を応用した手法こそ吟味されるべきだろう.

感想

 AUTOPROBEは折しも私が昨年度のインターンシップでほとんど同じようなテーマに取り組んでいたとき発表された.テイント解析のソースを受信データではなくシステムコールの結果に設定することで,リクエストのセマンティクスを復元しようとするAUTOPROBEの発想は野心的であり,さまざまなバイナリ解析技術を結集して未知のC&Cサーバを発見する手際は鮮やかというほかない.
 私は来年書くことになる卒業論文のテーマとして,インターネット接続のない閉環境におけるマルウェアの分析に本手法を応用できないか検討している.Ryzhykら[4]はデバイスドライバと環境(デバイスおよびOS)との相互作用を有限オートマトンを用いて表現し,デバイスドライバを半自動的に合成する手法を提案している.問題領域は異なるがこうした手法も検討したい.

用語解説

  • テイント解析
    • 任意のデータに設定したタグをルールにしたがって伝搬させることで,データ間の依存関係を分析する手法
  • プログラムスライシング
    • 任意のデータに依存する処理部分をプログラムから抽出する手法
  • 記号的実行
    • プログラムの分岐条件を充足論理問題とし,制約を充足する解を得る手法
  • ファジング
    • 開発者が意図しない入力を自動生成してプログラムに与えることで脆弱性を顕在化させる手法

参考文献

TL;DR:

 ソフトウェアの多くは外部からの入力に依存する実行パス(trigger-based code)をもつ.
 これを記号的実行(symbolic execution, シンボリック実行)などの解析手法から隠蔽する手法として,コラッツの問題を用いた線型難読化(linear obfuscation)がある[1].
 本稿ではしかし,線型難読化されたコードはコンパイラ最適化によってある程度除去できることを示す.

コラッツの問題

 コラッツの問題は数論の未解決問題のひとつである.
 任意の1でない自然数nに対して,nが偶数ならば2で割り,nが奇数ならば3倍して1を足す.この操作を繰り返していくと,どのような自然数nから出発しても,有限回の操作のうちに必ず1に到達する.
 この定理は経験則的に正しいと考えられているが,いまだ証明はなされていない.

線型難読化

 たとえば次のプログラムtr.cは外部からの入力に依存する実行パスをもつ.

1
2
3
4
5
6
7
8
9
10
11
// tr.c
#include <stdio.h>

int main(int argc, char *argv[])
{

int x=argc;
if(x==2)
printf("triggered!\n");

return 0;
}

 LLVM bitcodeレベルでのtr.cの制御フローグラフは次のようになる.

1
# clang -emit-llvm -c -g tr.c
# opt tr.bc -dot-cfg > /dev/null
# dot -Tpng cfg.main.dot > tr.png

 この単純なプログラムにたいして,コラッツの問題にもとづくループを挿入する.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// tr2.c
#include <stdio.h>

int main(int argc, char *argv[])
{

int x = argc;
int y = x + 1000;

while(y > 1)
{
if(y % 2 == 1)
y = 3 * y + 1;
else
y = y / 2;

if((x - y > 0)&&(x + y < 4))
{
printf("triggered!\n");
break;
}
}

return 0;
}

 変数yは必ず1に到達する,いわば偽の変数である.
 難読化されたtr2.cの制御フローグラフは次のようになる.

 ループが挿入されたことによって実行パスが複雑化していることが見て取れる.

記号的実行

 では,線型難読化がどれほど記号的実行にたいして効力をもつか見てみよう.
 今回はLLVM bitcodeを扱う記号的実行ツールKLEEを用いる.
 まず次のコードを解析対象のソースに追記する必要がある.これは,変数xにたいして記号的実行を適用するという意味である.

1
@@ -3,6 +3,7 @@
 int main(int argc, char *argv[])
 {
     int x=argc;
+    klee_make_symbolic(&x, sizeof(x), "x");
     if(x==2)
         printf("triggered!\n");

 次に,LLVM bitcodeを生成する.

1
# clang -emit-llvm -c -g tr.c
tr.c:6:5: warning: implicit declaration of function 'klee_make_symbolic' is
      invalid in C99 [-Wimplicit-function-declaration]
    klee_make_symbolic(&x, sizeof(x), "x");
    ^
1 warning generated.

 警告が出るが,気にしてはいけない.この関数呼び出しがKLEEにトラップされることになるのだ.
 ソースコードのないマルウェアなどを分析するにあたっては,IDAなどのデコンパイラでソースを出力し,型情報やシグナルハンドラなどの記述を整えたのち上記のようなコードを挿入するか,あるいはS2EやPANDAといった動的解析環境を頼ることになるだろう.
 それはさておき,KLEEを動かしてみよう.少し前までKLEEをビルドして動かすのはとても面倒だったが,いまではDocker Imageが提供されている.

1
# sudo docker pull klee/klee
# sudo docker run --rm -ti klee/klee

 線型難読化をおこなう前のtr.cについて記号的実行をおこなった結果を示す.

1
klee@4d625535c122:~$ time klee tr.bc
KLEE: output directory is "/home/klee/klee-out-1"
KLEE: WARNING: undefined reference to function: printf
KLEE: WARNING ONCE: calling external: printf(39707328)
triggered!

KLEE: done: total instructions = 17
KLEE: done: completed paths = 2
KLEE: done: generated tests = 2

real    0m0.032s
user    0m0.009s
sys     0m0.012s

 パスは2つしか存在しないため,32msecで解析が終わっている.
 ならば,線型難読化を施した後のtr2.cについてはどうか.

1
klee@4d625535c122:~$ time klee tr2.bc
KLEE: output directory is "/home/klee/klee-out-2"
KLEE: WARNING: undefined reference to function: printf
KLEE: WARNING ONCE: calling external: printf(49859696)
triggered!
triggered!
triggered!
triggered!
triggered!
...

KLEE: done: total instructions = 285809
KLEE: done: completed paths = 158
KLEE: done: generated tests = 158

real    6m11.933s
user    3m56.240s
sys     2m14.245s

 さきほどに比べ,実行パスは158に増加し,解析に11622.9倍(!)もの時間がかかっている.
 今回の単純なプログラムでさえこのようになるならば,複数の入出力に依存する実行パスに線型難読化が施されたらどうなることか.

コンパイラ最適化

 難読化とはえてしてコンパイラ最適化の逆写像である.
 KLEEがLLVMにもとづいているということもあって,LLVMの最適化が線型難読化を除去できるかどうか興味をもった.検証してみよう.

1
# opt -O3 tr2.bc -o tr3.bc

 -O3をもって最適化した後の制御フローグラフは次のようになる.

 最初のtr.cほどではないが,いくらか単純になっていることがわかる.printf()puts()に変換されている.
 では,実行パスは減少しているだろうか.記号的実行をおこなった結果は次の通り.

1
klee@4d625535c122:~$ time klee tr3.bc
KLEE: output directory is "/home/klee/klee-out-4"
KLEE: WARNING: undefined reference to function: puts
KLEE: WARNING ONCE: calling external: puts(32090720)
triggered!
triggered!
triggered!
triggered!
triggered!
triggered!
triggered!
triggered!
triggered!

KLEE: done: total instructions = 3383
KLEE: done: completed paths = 10
KLEE: done: generated tests = 10

real    0m2.845s
user    0m2.490s
sys     0m0.357s

 実行パスは10とさきほどのtr2.cよりも減少している.実行時間はtr.cの88.9倍であった.

おわりに

 線型難読化は脅威ではないことがわかった—少なくとも提唱者の思惑ほどには.
 塵も積もれば山となるように,線型難読化を多数の箇所に施せばその効力は増すだろう.しかしそれはクラスタリングなどの手法で対処される可能性を高めるだけである.もちろん,どれほどの範囲で難読化を適用すれば効果的かという閾値を探ることに価値はある.
 LLVMの-O3最適化は複数の最適化パスを組み合わせ,再帰的に適用することによっておこなわれる.どのパスが線型難読化の除去にもっとも寄与しているか調べてみるとおもしろいかもしれない(やる気がない).

参考文献