読書メモ.

はじめに

 人間の脳を模したニューラルネットの手法,深層学習ディープラーニングがめざましい成果を挙げている–といった謳い文句をよく目にする.だが機械学習の専門書を紐解いても出てくるのはロジスティック回帰のお化けばかり.
 われらが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
2
3
4
5
6
7
8
9
10
11
12
13
# 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
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
# 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
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
改変適応機環境におけるインターネット化の設計と実装
暮らし計算発見を利用した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
2
3
4
5
6
7
8
9
10
11
注目した二点間接続基盤ソフトウエアの構築インターネット
地域における高等教育協力手法の研究ホームネットワークにおける多様
かつスケーラブルな識別子管理システムゲームコンソールに対応する管理
運用基盤分析に関する研究ポリシ経路制御に関する研究大
任意の物理的量子ビットに対する効率的な情報閲覧
脳疲労検知システムの提案次世代インターネット経路制御を用い
鍵交換機構の実装と評価初等中等教育における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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
2
3
# 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
2
3
4
5
6
7
@@ -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
2
3
4
5
6
# 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
2
# sudo docker pull klee/klee
# sudo docker run --rm -ti klee/klee

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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最適化は複数の最適化パスを組み合わせ,再帰的に適用することによっておこなわれる.どのパスが線型難読化の除去にもっとも寄与しているか調べてみるとおもしろいかもしれない(やる気がない).

参考文献

はじめに

いわゆるVM床抜きをXenで試す.

Xenのインストール

いつかインストールしたXen 4.4.1を用いた.

  • 依存パッケージ

    1
    # sudo apt-get install wget git bcc bin86 gawk bridge-utils iproute libcurl3 libcurl4-openssl-dev bzip2 module-init-tools pciutils-dev build-essential make gcc libc6-dev libc6-dev-i386 linux-libc-dev zlib1g-dev python python-dev python-twisted python-gevent libncurses5-dev patch libvncserver-dev libssl-dev libsdl-dev iasl libbz2-dev e2fslibs-dev git-core uuid-dev ocaml libx11-dev bison flex ocaml-findlib xz-utils gettext libyajl-dev libpixman-1-dev libaio-dev libfdt-dev cabextract libglib2.0-dev autoconf automake libtool check libjansson-dev libfuse-dev
  • Xenのビルド

    1
    2
    3
    4
    5
    6
    7
    # wget http://bits.xensource.com/oss-xen/release/4.4.1/xen-4.4.1.tar.gz
    # tar xzvf xen-4.4.1.tar.gz
    # cd ./xen-4.4.1
    # export C_INCLUDE_PATH=/usr/include/x86_64-linux-gnu
    # ./configure --enable-systemd --enable-githttp
    # make -j4 dist-xen
    # make -j4 dist-tools
  • DomUの設定

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # sudo su
    # make -j4 install-xen
    # make -j4 install-tools
    # echo "GRUB_CMDLINE_XEN_DEFAULT=\"dom0_mem=4096M,max:4096M dom0_max_vcpus=4 dom0_vcpus_pin=true hap_1gb=false hap_2mb=false\"" >> /etc/default/grub
    # echo "/usr/local/lib" > /etc/ld.so.conf.d/xen.conf
    # ldconfig
    # update-grub
    # echo "none /proc/xen xenfs defaults,nofail 0 0" >> /etc/fstab
    # echo "xen-evtchn" >> /etc/modules
    # echo "xen-privcmd" >> /etc/modules
    # update-rc.d xencommons defaults 19 18
    # update-rc.d xendomains defaults 21 20
    # update-rc.d xen-watchdog defaults 22 23
    # reboot
  • 動作確認

    1
    2
    # sudo xen-detect
    Running in PV context on Xen v4.4.

ハイパーコールの追加

予約済みの__HYPERVISOR_xc_reserved_opに代わって39番目のハイパーコールを定義する.

  • xen-4.4.1/xen/include/public/xen.h

    1
    2
    3
    4
    5
    6
    7
    8
    @@ -100,6 +100,7 @@
    #define __HYPERVISOR_domctl 36
    #define __HYPERVISOR_kexec_op 37
    #define __HYPERVISOR_tmem_op 38
    +#define __HYPERVISOR_rdtsc_hypercall 39
    #define __HYPERVISOR_xc_reserved_op 39 /* reserved for XenClient */
    /* Architecture-specific hypercall definitions. */
  • xen-4.4.1/xen/arch/x86/x86_64/entry.S

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    @@ -757,6 +757,7 @@
    .quad do_domctl
    .quad do_kexec_op
    .quad do_tmem_op
    + .quad do_rdtsc_hypercall
    .rept __HYPERVISOR_arch_0-((.-hypercall_table)/8)
    .quad do_ni_hypercall
    .endr
    @@ -805,6 +806,7 @@
    .byte 1 /* do_domctl */
    .byte 2 /* do_kexec */
    .byte 1 /* do_tmem_op */
    + .byte 1 /* do_rdtsc_hypercall */
    .rept __HYPERVISOR_arch_0-(.-hypercall_args_table)
    .byte 0 /* do_ni_hypercall */
    .endr
  • xen-4.4.1/xen/include/asm-x86/hypercall.h

    1
    2
    3
    4
    5
    6
    7
    8
    9
    @@ -110,4 +110,8 @@
    arch_compat_vcpu_op(
    int cmd, struct vcpu *v, XEN_GUEST_HANDLE_PARAM(void) arg);
    +extern int
    +do_rdtsc_hypercall(
    + char* str);
    +
    #endif /* __ASM_X86_HYPERCALL_H__ */
  • xen-4.4.1/xen/arch/x86/traps.c

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    @@ -3762,6 +3762,14 @@
    __domain_crash_synchronous();
    }
    +int do_rdtsc_hypercall(char* str)
    +{
    + unsigned long long tsc;
    + __asm__ volatile("rdtsc" : "=A" (tsc));
    + printk("str: %s, tsc: %llu\n", str, tsc);
    + return 0;
    +}
    +
    /*
    * Local variables:
    * mode: C

このハイパーコールは引数として受け取った文字列をTSCの値とともにコンソールログに出力する.有効化するには再度make -j4 dist-xenして再起動するとよい.

ハイパーコールの呼び出し

ハイパーコールの呼び出しはlibxcやlibxlによって抽象化されているが,ここではそれらが内部で参照している/proc/xen/privcmdに対してioctlを発行してみる.

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
// rdtsc_hypercall.c
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/ioctl.h>
#include <linux/types.h>
#include <fcntl.h>
#include <string.h>
#include <xenctrl.h>
#include <xen/sys/privcmd.h>
int main(int argc, char *argv[])
{
if(argc != 2)
{
printf("input the param");
exit(1);
}
char *message = malloc(sizeof(char)*(strlen(argv[1])+1));
strcpy(message, argv[1]);
privcmd_hypercall_t my_hypercall = {
39, // __HYPERVISOR_rdtsc_hypercall
{(__u64)message, 0, 0, 0, 0}
};
int fd = open("/proc/xen/privcmd", O_RDWR);
if(fd < 0)
{
printf("cannot open /proc/xen/privcmd");
exit(1);
}
if(!ioctl(fd, IOCTL_PRIVCMD_HYPERCALL, &my_hypercall))
{
printf("cannot call do_rdtsc_hypercall");
exit(1);
}
return 0;
}

このプログラムを実行するとハイパーコールが呼び出されたことが分かる.

1
2
3
4
# gcc -o rdtsc_hypercall rdtsc_hypercall.c
# sudo ./rdtsc_hypercall test
# sudo xl dmesg | less
(XEN) str: test, tsc: 2835883086

おわりに

Xenに追加したハイパーコールを呼び出すことができた.
さしあたってはMirage OSからこのハイパーコールを呼び出す方法を知りたいのだが.

参考文献

はじめに

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

講義資料

講義内容

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

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

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

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

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

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

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

おわりに

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

はじめに

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

実験

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

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

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

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

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

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

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

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

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

おわりに

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

参考文献

はじめに

田中久美子『記号と再帰: 記号論の形式・プログラムの必然』(“Semiotics of Programming,” Cambridge University Press, 2010.)は,プログラミング言語の記号論についての記念碑的な書籍である.かねてよりPeter B. Andersenらによってコンピュータ記号論(computional semiotics)は語られていたものの,プログラミング言語については議論が追い付いていなかった.
本書はまず,対応関係が不明瞭であったソシュールの記号論とパースのそれとを,関数型パラダイムとオブジェクト指向パラダイムとの対比をもって整理する.その上で,記号の本質は再帰にある(p.1)として,絵画,プログラミング言語,哲学を横断した考察が展開される.とまあ随分と衒学的な書籍なのだが,それゆえ危うさを孕んでいるようにも思う.ここではあえて,本書の批判とはいかないまでも,いくつかの不満点を提示したい.

汎記号主義

本書は「記号を媒介することなく対象を人間が認識できない」(p.27)とされ,「記号の解釈を記号系の中だけで捉える」(p.26)という汎記号主義を前提としている.この妥当性について考えても埒が明かないので,ひとまずはそういうことにしておこう.

HaskellとJavaによるプログラム例

本書で用いられるプログラミング言語は,HaskellとJavaである.
以下はHaskellによる平面上の長方形,楕円,円の面積を計算するプログラムである(p.15).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
data Shape = Rectangle Double Double
| Ellipse Double Double
| Circle Double
area (Rectangle width height) = width * height
area (Ellipse width height) = pi * width * height / 4.0
area (Circle radius) = area (Ellipse (radius * 2.0)(radius *2.0))
main = let
r = Rectangle 5.0 8.0
u = Ellipse 3.0 4.0
v = Circle 3.0
ss = [r, u, v]
in
for (\s -> putStr("area: "++show (area s)++"\n")) ss
for f [] = do return ()
for f (s:ss) = do { (f s); for f ss}

いきなり不安になってくる.Haskellについてはずぶの素人の私だが,それでもこのような場面ではforMmapMを用いるべきだと知っている.「このfor関数は,次の図2.2のJavaプログラムとの整合性をふまえて定義されている」(p.17)とあるが,首を傾げざるを得ない.なおmapはp.141に至るまで登場しない.
続いて,同様にJavaによるプログラムが示される(p.18).

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
class Shape{
double width, height;
Shape (double w, double h){ width = w; height = h; }
public double area () { return width * height; }
}
class Rectangle extends Shape{
Rectangle (double w, double h){ super(w, h); }
}
class Ellipse extends Shape{
Ellipse (double w, double h){ super(w, h); }
public double area(){ return Math.PI*width*height/4.0; }
}
class Circle extends Ellipse{
Circle(double r){ super(r*2.0, r*2.0); }
}
void run(){
Rectangle r = new Rectangle(5.0, 8.0);
Ellipse u = new Ellipse(3.0, 4.0);
Circle v = new Circle(3.0);
Shape [] ss = new Shape[]{r, u, v};
for (Shape s : ss){ putStr("area: " + s.area() + "\n"); }
}

これらのプログラムは異なるパラダイム,異なる記法によって書かれているが,しかし同じ出力を得ることができる.ここに本書は,ソシュール二元論とパース三元論を託つける.

ソシュール二元論とパース三元論

ソシュールとパースはそれぞれ記号について以下のように整理した.

  • ソシュール二元論
シニフィアン シニフィエ
“tree”
ラベル 内容
  • パース三元論
表意体 解釈項 対象
“tree” 木の解釈
ラベル イデア 対象

この対応について,本書は,パース「記号は人に働きかけ,人の心の中に等価な記号を作り出し,あるいはより発展した記号を作り出す.もとの記号が作り出すこの記号のことを私は解釈項と呼ぶ」を根拠に(p.40),「解釈項は記号の解釈を呼び,記号過程を生成するもので」あり「これに対応するものがソシュールの記号モデルの中にあるならば,それはシニフィエ以外にありえない」(p.41)と導く.
続いて,「記号の差異は他の記号と対比されてはじめて立ち現れるものである.とすると,記号の解釈にまつわる記号の使用はソシュールの記号モデルの構成要素には含まれてはいなが,全体論的価値として位置付けられていると考えることができる」(p.41)ことから,「ソシュールのシニフィエはパースの直接対象に対応し,そしてパースの解釈項はソシュールの記号モデルに外在する全体論的価値に内包される」(pp.41-42)という仮説を提示する.

全体論的価値

関数型パラダイムとオブジェクト指向パラダイムの比較を通じて仮説を検証する前に,この「全体論的価値」とは何を意味するのだろうか.おそらくは意図的なのだろうが,本書にはパロールやラング,レフェランといった語が一切登場しない.これによって混乱してしまったのは私だけだろうか.記号論についてもずぶの素人である私の苦し紛れの解釈では「全体論的価値」はラングに相当するが,詳細は述べられていない.ソシュールの「言語記号は恣意的です」という原理も後に登場する(p.57)が,社会的慣習と全体論的価値が絡められることはなかった.

ソシュール二元論とパース三元論の接続

さて,ソシュールとパースの関係は,先に挙げたプログラム例のarea関数のあり方によって整理される.

プログラミング言語 Haskell Java
記号論 二元論 三元論
area関数 外在的 内在的

Haskellのプログラム例では,areaは他のデータ構造に外在するが,Javaのプログラム例では内在する(p.42).言い換えれば,Haskellにおいては記号がその使用によって意味付けられるが,Javaにおいては記号の定義がその使用を内在する.つまり,次のような対応関係になる(p.49).

  • ソシュールのシニフィアンはパースの表意体に対応する.
  • ソシュールのシニフィエはパースの直接対象に相当する(心的な対象).
  • パースの解釈項は識別子の使用に相当する.パースの記号モデルでは,記号の使用は解釈項として記号モデルの中に埋め込まれ,記号過程は解釈項を次々と呼ぶことによって生成される.ソシュールにおいては,記号過程は記号が別の記号に呼ばれ,それがまた別の記号に呼ばれることにより生成される.ある記号の使用によって記号に付される価値は記号モデルに外在し,それは記号を併置した際の差異として現れる.

こうして,ソシュールとパースの論が接続された.なるほど綺麗にまとまったかのように思える.

プログラミングパラダイム

しかし,これはプログラミングパラダイムから見て妥当だろうか.HaskellやJavaに固有の特徴と,パラダイムの特徴を同一視していないだろうか.本書において,HaskellやJavaを選択した基準は最後まで明確に示されない(私はJavaScriptが良いのではないかと思った).
CTMCPこと『コンピュータプログラミングの概念・技法・モデル』(“Concepts, Techniques, and Models of Computer Programming, “ The MIT Press, 2004.)のPeter Van-Royによると,オブジェクト指向パラダイムとは関数型パラダイムに状態(state)を追加したものである.私はこの考えに沿った展開に期待していたのだが,しかし状態の概念はp.190に至るまでほとんどといって触れられず,HaskellとJavaの比較に絡められることはなかった.
オブジェクト指向すなわちカプセル化という前提に立っているところ,プロトタイプベースのオブジェクト指向について触れていないところも勿体無い.

モナドと状態

状態の概念は,「インタラクションを参照透明に記述しようと思うと,」「莫大な量の記号を使い捨てなければならない」(pp.198-199)からこそモナドが考案されたという流れで援用される.すなわち,参照透明性を保ちつつ状態を記述するためにモナドがある(p.196).失敗系モナドが無視されているにせよ,このあたりの説明が明快なだけに,HaskellとJavaの比較において状態の概念が持ち出されなかったことが残念に思われる.

参照の値渡し

本書はJavaを「関数に値とアドレスのどちらかを渡すのかは,再び文脈により実用論的に決まり,」「プログラマが定義して導入する複合型」は「アドレスを渡す」ものとして紹介している(p.117).これは端的に誤りである.なぜなら,Javaはあらゆる場面において値渡しであり,参照は参照の値(reference values)として扱われるためである.

おわりに

主にプログラミングの観点から,『記号と再帰』に見られる不満点を述べた.要約すると次のようになる.

  • Haskellのコードが微妙
  • 全体論的価値の定義が不明瞭
  • HaskellとJavaを題材に選んだ根拠が不明瞭
  • Javaの参照の値渡しについての説明が不適切

だからといって私は本書が駄本であると切り捨てたいわけではない.
シニフィアンを持たない状態で分節されたλ項にシニフィアンが付与されていく簡約の過程は大変面白かったし,再帰から是態(交換不可能性?)が立ち上るという考えも論証不足ながら興味深かった.
汎記号主義という極端な見地から,記号が投機的に記号系に導入されるからこそ再帰が成立すると言い切ることで,ここまで手際よく語ることができるのかという興奮があった.
だからこそ,(今後本書が重版されることがあればの話だが)今回述べたような不満点が解消されることを望む.
終盤に本書は,「何ら形式的な制約なく自然に作られた」自然言語の構造的な系と,「停止性が保証される最小の記号群からはじめ,停止性の制約下でボトムアップに構築される」プログラミング言語の構成的な系とを対比している(p.183).再帰による是態の獲得.構造的な系.次に語られるのはニューラルネットの記号論だろうか.

参考文献