第1章 daisy-toolsのコンセプトとアーキテクチャ
1.1 コンセプト
普段、実行バイナリを作る際はには、ソースコードを書いてそれをコンパイルする、という流れが一般的です。スクリプト言語等の場合も、結局は「ソースコードを書く」事は変わらないと思います。
「daisy-tools」(というより前著で紹介した「バイナリ生物学」)のコンセプトは、バイナリを生物のように生成することです。生物学で理解されている生物が増殖・進化する仕組みを、バイナリの生成に応用します。
1.2 本書でやること
前著では、独自OSのメモリ上で、生物と見立てた関数が、運動・代謝・成長・増殖・死の5つの振る舞いをするデータ構造と実装例を説明しました。
本書では、細胞分裂時にDNAが突然変異する仕組みを導入します。そして、代謝・運動の結果に応じて各個体へ「適応度」を設定することで、目的の方向へ進化できるようにします。
なお、前著では独自OS上のアプリの関数を対象としていましたが、本書では、Linux上で実行可能なELFバイナリを生成します。
ELFバイナリについて
本書では、実行バイナリを培養するシステムであるdaisy-toolsを使ってELFバイナリを生成します。
まずは、生成するELFバイナリがどのようなものであるかをざっくりと紹介します。
本書で扱うELFフォーマットの要素は「EFLヘッダ」と「機械語命令列」のみで、簡単に説明すると図1.1の通りです。
図1.1: 本書で使うELFの要素
重要なのは、ELFバイナリには実行される機械語命令列自体と、それがELFバイナリ中のどこにあるかを示す情報が入っているということです。実行させたい機械語命令を並べ、そこへのアドレスを適切に示すようにヘッダを用意すればELFバイナリは作れるわけです。
図1.1の機械語命令箇所をアセンブラで示すと図1.2の通りです。図示の際の分かりやすさのため、以降はアセンブラで図示するようにします。ただ、実際に扱うのはそれに対応する機械語です。
図1.2: 機械語部分をアセンブラで図示
実行バイナリを細胞に見立てる
前著でも紹介した通り、実行バイナリを細胞に見立てることで、生物としての振る舞いをさせます。構造は図1.3の通りです。
図1.3: 細胞の構造
構成要素については前著でも紹介した通りですが、突然変異と進化の仕組みを入れるために以下の要素を追加しています。
- 属性情報: 適応度
- DNA: 突然変異不可フラグ
なお、前著では1命令をさらに分解したバイト列を単位としていましたが、本書では1命令を最小単位とします。そのため、本書でのコード化合物は1命令そのものとなります。また、DNAを構成するコドンも1命令単位となります。
今回対象とする実行バイナリは入力データを取らないため、細胞の他に存在する物質はコード化合物のみです(図1.4)。
図1.4: コード化合物
daisy-toolsにおける実行バイナリ培養は、これらの細胞とコード化合物をシャーレに入れて培養させるイメージです(図1.5)。
図1.5: 実行バイナリを培養するイメージ
突然変異の仕組み
突然変異は、細胞分裂時にあらかじめ設定された確率で発生します。
突然変異の単位はコドンですので「1命令」の単位です。「対象とするコドン」・「突然変異の仕方(追加/変更/削除)」・「変異後の命令」をそれぞれランダムに選び、例えば「DNA内の2番目のコドン」を対象に「mov命令」へ「変更」する、といったように突然変異を行います。
「突然変異不可フラグ」を設定しておくと、そのコドンは突然変異の対象にしないようにすることができます(図1.6)。これにより、「最後のret命令だけは突然変異で変更/削除されないようする」等といった設定が可能です。
図1.6: 突然変異不可フラグ
体が大きくなると寿命も延びる
daisy-toolsでは、DNAへコドンが追加される突然変異が起きた場合、ある一定の比率で寿命を延ばすようにしています。
それは、DNAを長くする方向の突然変異が細胞の生存戦略においてデメリットにならないようにするためです。
前著でも紹介した通り、細胞が分裂により増殖する流れは以下の通りです。
- DNAの各コドンが示すコード化合物を取り込む(各サイクルで最大1個ずつ)
- DNAの全コドンのコード化合物が揃ったら細胞分裂
この時、各サイクルで寿命も1ずつ減るため、DNAが長くなった際に寿命が短い頃のままだと、長いDNAは各サイクルで1つずつ化合物を取り込んでも、短いDNAより残せる子の数は減ってしまいます。
このような不平等が起こらないように、DNAが長くなった場合(体が大きくなった場合)は、寿命も延ばすようにしています。
意図した方向へ進化を導く仕組み
ただ突然変異をさせ続けるだけでは、目的の実行バイナリへ近づけていくのは難しいです。
そのためには、正に「海に餌が少なくなったから陸へ上がった」というような進化の方向性を付ける仕組みが必要です。そのために細胞の構造に追加した「適応度」というパラメータを使います(図1.7)。
図1.7: 細胞の適応度パラメータ
適応度は各周期で細胞を評価する際に設定されるパラメータです。そしてこの適応度を、各周期で細胞が化合物を取り込める確率に使います(図1.8)。自身のDNAに合致するコード化合物を揃えれば分裂が行えるため、適応度が高いほど化合物を多く取り込め、増殖も行いやすくなる訳です。
図1.8: 細胞周期での適応度の使われ方
イメージとしては図1.9、図1.10、図1.11の通りです。
図1.9: 適応度による進化(1)
図1.10: 適応度による進化(2)
図1.11: 適応度による進化(3)
本書で紹介する「daisy-tools」では、このようにして実行バイナリの培養・進化を行います。