バイナリ⽣成環境「daisy-tools」実験報告— 培養‧進化で簡単な ELF バイナリを⽣成！ —［著］⼤神祐真

技術書典 8（2020 年春）新刊

2023 年 5 ⽉ 20 ⽇1

ver 1.1

■免責
本書は情報の提供のみを⽬的としています。
本書の内容を実⾏・適⽤・運⽤したことで何が起きようとも、それは実⾏・適⽤・運⽤した⼈
⾃⾝の責任であり、著者や関係者はいかなる責任も負いません。
■商標
本書に登場するシステム名や製品名は、関係各社の商標または登録商標です。
また本書では、™、®、© などのマークは省略しています。

2

はじめに
本書をお⼿にとっていただきありがとうございます！*1
本書では、前著「バイナリ⽣物学⼊⾨」で紹介した「実⾏バイナリを⽣物に⾒⽴てる設計」へ「進化」の仕組みを追加することで、実⾏バイナリを進化により⽣み出せ
るようにした「daisy-tools」というツールを紹介する本です。
プログラマの三⼤美徳の⼀つに「怠惰」がありますが、その究極は「寝て、起きた
らできあがっている」だと思います。本書で紹介する daisy-tools は、「コードを書くことでバイナリを⽣成」する従来の「プログラミング」による⽅法とは違い、「バイナリを進化させる」事で任意のバイナリを⽣成します。それによりエンジニアは、進化を評価するスクリプトを書くだけで、実⾏バイナリ本体に関するコードは書かずに⽬的のバイナリを⽣成できます。(と⾔っても、現実的に⽣成できるのは簡単なもの
のみですが。)

本書の構成
本書では daisy-tools について以下の 3 章構成で紹介します。

• 第 1 章 daisy-tools のコンセプトとアーキテクチャ◦ daisy-tools の基本コンセプトと、バイナリを進化させる仕組みを紹介します。

• 第 2 章 daisy-tools の使い⽅
◦ 使い⽅を実⾏例と共に紹介します。
• 第 3 章 実験結果紹介◦「終了ステータス 0 で正常終了する」
・「’A’ を出⼒して正常終了する」という 2 つの ELF バイナリの⽣成について実験結果を紹介します。

PDF/HTML 版や本書の更新情報について
本書の PDF/HTML 版は筆者のウェブページで公開しています。

• http://yuma.ohgami.jp
本書の内容について訂正や更新があった場合もこちらのページに記載しますので、何かおかしな点などあった場合はまずはこちらのページをご覧ください。
*1 こんな何だかよく分からない本を、本当にありがとうございます。
。

–i–
3

4

⽬次
はじめに
本書の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

PDF/HTML 版や本書の更新情報について . . . . . . . . . . . . . . . . . . .
第1章

1.1
1.2

第2章

2.1

2.2

第3章

3.1

3.2

daisy-tools のコンセプトとアーキテクチャ
コンセプト . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
本書でやること . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
♣ ELF バイナリについて . . . . . . . . . . . . . . . . . . . . . .
♣ 実⾏バイナリを細胞に⾒⽴てる . . . . . . . . . . . . . . . . . .
♣ 突然変異の仕組み . . . . . . . . . . . . . . . . . . . . . . . . .
♣ 意図した⽅向へ進化を導く仕組み . . . . . . . . . . . . . . . . .

1
1
1
2
3
5
7

daisy-tools の使い⽅

11
主に使⽤するツール類 . . . . . . . . . . . . . . . . . . . . . . . . . 11
♣ dsy-name について . . . . . . . . . . . . . . . . . . . . . . . . 12
♣ dsy-eval について . . . . . . . . . . . . . . . . . . . . . . . . 13
使⽤例: 簡単な評価スクリプトで試す . . . . . . . . . . . . . . . . . 14
♣ ツールをダウンロード . . . . . . . . . . . . . . . . . . . . . . . 15
♣ 細胞ファイルを配置 . . . . . . . . . . . . . . . . . . . . . . . . 15
♣ コード化合物ファイルを配置 . . . . . . . . . . . . . . . . . . . 16
♣ ユーザー定義スクリプトを配置 . . . . . . . . . . . . . . . . . . 17
♣ dsy-sysenv を実⾏ . . . . . . . . . . . . . . . . . . . . . . . . 18
実験結果紹介19

実験 1: 正常終了するだけのバイナリ⽣成 . . . . . . . . . . . . . . .
♣ 実験条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
♣ 補⾜: code ディレクトリ内の各命令について . . . . . . . . . . . .
♣ 実験結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
♣ 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

実験 2: ’A’ を出⼒する実⾏バイナリ⽣成 . . . . . . . . . . . . . . . .
♣ 実験条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
♣ 補⾜: code ディレクトリ内の各命令について . . . . . . . . . . . .
♣ 実験結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
♣ 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22– iii –
5

i
i
i

19
19
21
21
22
22
23
24

⽬次

3.3

実験 3: ’A’ を出⼒する実⾏バイナリ⽣成 (改良版) . . . . . . . . . . .
♣ 実験条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
♣ 実験結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
♣ 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

おわりに

25
25
27
27

29

– iv –
6

第1 章 daisy-tools のコンセプ
トとアーキテクチャ

この章では「daisy-tools」の基本コンセプトとアーキテクチャを紹介します。

1.1

コンセプト

普段、実⾏バイナリを作る際はには、ソースコードを書いてそれをコンパイルする、という流れが⼀般的です。スクリプト⾔語等の場合も、結局は「ソースコードを書く」事は変わらないと思います。
「daisy-tools」(というより前著で紹介した「バイナリ⽣物学」) のコンセプトは、バイナリを⽣物のように⽣成することです。⽣物学で理解されている⽣物が増殖・進化する仕組みを、バイナリの⽣成に応⽤します。

1.2

本書でやること

前著では、独⾃ OS のメモリ上で、⽣物と⾒⽴てた関数が、運動・代謝・成⻑・増殖・死の 5 つの振る舞いをするデータ構造と実装例を説明しました。
本書では、細胞分裂時に DNA が突然変異する仕組みを導⼊します。そして、代謝・運動の結果に応じて各個体へ「適応度」を設定することで、⽬的の⽅向へ進化できるようにします。
なお、前著では独⾃ OS 上のアプリの関数を対象としていましたが、本書では、Linux 上で実⾏可能な ELF バイナリを⽣成します。

–1–
7

第 1 章 daisy-tools のコンセプトとアーキテクチャ♣ ELF バイナリについて
本書では、実⾏バイナリを培養するシステムである daisy-tools を使って ELF バ
イナリを⽣成します。
まずは、⽣成する ELF バイナリがどのようなものであるかをざっくりと紹介します。
本書で扱う ELF フォーマットの要素は「EFL ヘッダ」と「機械語命令列」のみで、簡単に説明すると図 1.1 の通りです。

▲ 図 1.1: 本書で使う ELF の要素
重要なのは、ELF バイナリには実⾏される機械語命令列⾃体と、それが ELF バイ
ナリ中のどこにあるかを⽰す情報が⼊っているということです。実⾏させたい機械語
命令を並べ、そこへのアドレスを適切に⽰すようにヘッダを⽤意すれば ELF バイナ
リは作れるわけです。
図 1.1 の機械語命令箇所をアセンブラで⽰すと図 1.2 の通りです。図⽰の際の分かりやすさのため、以降はアセンブラで図⽰するようにします。ただ、実際に扱うのはそれに対応する機械語です。

–2–8

1.2 本書でやること▲ 図 1.2: 機械語部分をアセンブラで図⽰♣ 実⾏バイナリを細胞に⾒⽴てる
前著でも紹介した通り、実⾏バイナリを細胞に⾒⽴てることで、⽣物としての振る舞いをさせます。構造は図 1.3 の通りです。

▲ 図 1.3: 細胞の構造–3–9

第 1 章 daisy-tools のコンセプトとアーキテクチャ

構成要素については前著でも紹介した通りですが、突然変異と進化の仕組みを⼊れるために以下の要素を追加しています。

• 属性情報: 適応度• DNA: 突然変異不可フラグ
なお、前著では 1 命令をさらに分解したバイト列を単位としていましたが、本書では 1 命令を最⼩単位とします。そのため、本書でのコード化合物は 1 命令そのものとなります。また、DNA を構成するコドンも 1 命令単位となります。
今回対象とする実⾏バイナリは⼊⼒データを取らないため、細胞の他に存在する物
質はコード化合物のみです (図 1.4)。

▲ 図 1.4: コード化合物

daisy-tools における実⾏バイナリ培養は、これらの細胞とコード化合物をシャーレに⼊れて培養させるイメージです (図 1.5)。

–4–

1
0

1.2 本書でやること▲ 図 1.5: 実⾏バイナリを培養するイメージ♣ 突然変異の仕組み
突然変異は、細胞分裂時にあらかじめ設定された確率で発⽣します。
突然変異の単位はコドンですので「1 命令」の単位です。
「対象とするコドン」
・「突
然変異の仕⽅ (追加/変更/削除)」
・「変異後の命令」をそれぞれランダムに選び、例えば「DNA 内の 2 番⽬のコドン」を対象に「mov 命令」へ「変更」する、といったよ
うに突然変異を⾏います。
「突然変異不可フラグ」を設定しておくと、そのコドンは突然変異の対象にしないようにすることができます (図 1.6)。これにより、「最後の ret 命令だけは突然変異で変更/削除されないようする」等といった設定が可能です。

1
1

–5–

第 1 章 daisy-tools のコンセプトとアーキテクチャ▲ 図 1.6: 突然変異不可フラグ【コラム】体が⼤きくなると寿命も延びる
daisy-tools では、DNA へコドンが追加される突然変異が起きた場合、ある⼀定の⽐率で寿命を延ばすようにしています。
それは、DNA を⻑くする⽅向の突然変異が細胞の⽣存戦略においてデメリッ
トにならないようにするためです。
前著でも紹介した通り、細胞が分裂により増殖する流れは以下の通りです。

1. DNA の各コドンが⽰すコード化合物を取り込む (各サイクルで最⼤ 1 個ずつ)
2. DNA の全コドンのコード化合物が揃ったら細胞分裂
この時、各サイクルで寿命も 1 ずつ減るため、DNA が⻑くなった際に寿命が短い頃のままだと、⻑い DNA は各サイクルで 1 つずつ化合物を取り込んでも、短い DNA より残せる⼦の数は減ってしまいます。
このような不平等が起こらないように、DNA が⻑くなった場合 (体が⼤きくなった場合) は、寿命も延ばすようにしています。

–6–

1
2

1.2 本書でやること♣ 意図した⽅向へ進化を導く仕組み
ただ突然変異をさせ続けるだけでは、⽬的の実⾏バイナリへ近づけていくのは難しいです。
そのためには、正に「海に餌が少なくなったから陸へ上がった」というような進化の⽅向性を付ける仕組みが必要です。そのために細胞の構造に追加した「適応度」というパラメータを使います (図 1.7)。

▲ 図 1.7: 細胞の適応度パラメータ
適応度は各周期で細胞を評価する際に設定されるパラメータです。そしてこの適応度を、各周期で細胞が化合物を取り込める確率に使います (図 1.8)。⾃⾝の DNA に合致するコード化合物を揃えれば分裂が⾏えるため、適応度が⾼いほど化合物を多く取り込め、増殖も⾏いやすくなる訳です。

1
3

–7–

第 1 章 daisy-tools のコンセプトとアーキテクチャ▲ 図 1.8: 細胞周期での適応度の使われ⽅
イメージとしては図 1.9、図 1.10、図 1.11 の通りです。

▲ 図 1.9: 適応度による進化 (1)

–8–

1
4

1.2 本書でやること▲ 図 1.10: 適応度による進化 (2)▲ 図 1.11: 適応度による進化 (3)
本書で紹介する「daisy-tools」では、このようにして実⾏バイナリの培養・進化を
⾏います。

1
5

–9–

1
6

第

2 章 daisy-tools の使い⽅

この章では daisy-tools の基本的な使い⽅を説明します。

2.1

主に使⽤するツール類

daisy-tools は様々なツールで構成されています。主に使⽤するツールは表 2.1 の通りです。なお、これらのファイルは daisy-tools の GitHub リポジトリの Releases
ページからダウンロードできます (後述)。
▼ 表 2.1: daisy-tools の基本的なツール
ツール名

dsy-sysenv
dsy-cell2elf
dsy-dump-cell
dsy-name
dsy-eval

機能/役割
周期的な細胞の実⾏を⾏う。
daisy-tools のシステムを担うメインの実⾏バイナリ。

daisy-tools の細胞形式のバイナリを ELF バイナリへ変換する。
細胞形式バイナリの内容を独⾃のリスト形式
あるいは JSON 形式でダンプする。
⽣成される細胞バイナリ・化合物バイナリのファイルの名前付けを⾏うスクリプト。(ユーザー定義)
各周期で dsy-sysenv から呼び出され、指定された細胞を評価し適応度を返すスクリプト。(ユーザー定義)

dsy-sysenv はカレントディレクトリにリスト 2.1 の構成で配置された細胞ファ

イル・化合物ファイルを認識します。
▼ リスト 2.1: dsy-sysenv が認識するカレントディレクトリ構成.
|-- bin||-- "dsy-"で始まる各ツールを配置

17– 11 –

第 2 章 daisy-tools の使い⽅||-- dsy-sysenv||-- dsy-cell2elf||-- dsy-dump-cell||-- dsy-name <- ユーザー定義スクリプト||-- dsy-eval <- ユーザー定義スクリプト|`-- ...etc|-- cell|`-- 細胞ファイルを配置|-- code|`-- コード化合物ファイルを配置|-- data|`-- データ化合物ファイルを配置(現バージョンでは未使⽤)`-- samples`-- 細胞ファイル ‧コード化合物ファイルを⽣成するサンプルツール群

リスト 2.1 のディレクトリ構成のカレントディレクトリ上で dsy-sysenv を実⾏
すると、存在する全ての細胞ファイルに対して「代謝/運動」
・
「成⻑」
・
「増殖」
・
「死」
といった⽣物の振る舞いを繰り返し実⾏します。
dsy-name と dsy-eval は、 dsy-sysenv から必要に応じて呼び出されるユー

ザー定義のスクリプトで、 dsy-sysenv 実⾏前に予め⽤意しておく必要があります。
以降ではそれぞれのファイルについて説明します。

♣ dsy-name について
dsy-sysenv が新たに細胞ファイルやコード化合物ファイルを⽣成する際に呼び出すスクリプトで、それらのファイル名を決めるために使⽤します。

• 第 1 引数に"cell"あるいは"code"を指定して呼び出される◦ 名付ける対象が細胞ファイル/コード化合物ファイルのどちらなのかを指定• dsy-sysenv は標準出⼒に出されたものをファイル名として扱う• 指定されたファイル名が既に存在する場合、 dsy-sysenv は dsy-name を
繰り返し呼び出す◦ 現時点 (2020 年 2 ⽉現在) では、存在しないファイル名が返されるまでリトライし続ける実装
⽣成される細胞や化合物には固有の名前が付けられると⾯⽩いかなと思い、ファイ
ル名の名付けの部分は別スクリプトへ切り出しました。
ただ、動作上、ファイル名は何でも良いので、例えばリスト 2.2 の様にランダムな⽂字列を返すようにしてしまっても構いません。

– 12 –

18

2.1 主に使⽤するツール類▼ リスト 2.2: dsy-name の実装例#!/bin/bash
echo $RANDOM | md5sum | cut -c-10

なお、リスト 2.2 は samples/dsy-name に⽤意してあります。これをそのまま使う場合は、 bin ディレクトリに dsy-name という名前でこのファイルのシンボ
リックリンクを作成すれば良いです。(もちろん Windows 等の環境で実⾏する場合
はファイルコピーでも構いません。)♣ dsy-eval について
dsy-eval は、各周期で各細胞の適応度を決めるために細胞毎に呼び出されるスクリプトです。ユーザーはこのファイルで細胞をどのように評価するかを定義します。

• 第 1 引数に対象の細胞ファイル名を指定して呼び出される◦ "cell"から始まるパス指定ではなく、細胞ファイル名のみの指定• dsy-sysenv は dsy-eval の終了ステータスの値を適応度として扱う◦ 適応度の範囲は 0 から 100◦ 100 の適応度が返された場合、 dsy-sysenv は⽬的のバイナリが⽣成できたとして実⾏終了する◦ 0 から 100 以外の終了ステータスを返された場合、 dsy-sysenv はエ
ラー終了する
評価の流れを図⽰すると図 2.1 の通りです。

▲ 図 2.1: dsy-eval を使⽤した評価の流れ

1
9– 13 –

第 2 章 daisy-tools の使い⽅

例えば「細胞がエラーなく終了できるか (終了ステータスが 0 であるか)」のみを評価するようなものはシェルスクリプトでリスト 2.3 のように記述します。
▼ リスト 2.3: 終了ステータスの成否のみで評価#!/bin/sh
set -uex
if [ $# -ne 1 ]; thenecho "Usage: $0 CELL_FILE" 1>&2
exit 200ficell_file=$1
bin/dsy-cell2elf $cell_file ${cell_file}.elf
chmod +x ${cell_file}.elf./${cell_file}.elf && fitness=100 || fitness=50
rm ${cell_file}.elf
exit $fitness

dsy-cell2elf は第 1 引数で指定された細胞ファイルを ELF バイナリへ変換し、第 2 引数で指定されたパスへ保存します。
リスト 2.3 では、 dsy-cell2elf で変換した ELF バイナリを試しに実⾏し、正常終了したら適応度として終了ステータス 100 を、異常終了したら適応度として終了
ステータス 50 を返すようにしています。
適応度は、細胞が化合物を取り込める確率として使⽤されるものなので、0 を返してしまうと、その細胞は今後⼀切化合物を取り込めなくなり、細胞分裂も⾏えなくなってしまう点にご注意ください。また、0 で無くとも、あまりにも低い適応度ばかりを与えると適応度 100 の細胞が⽣まれる前に環境の細胞が全滅してしまう点も注意が必要です。経験的には最低適応度は 50 くらいにしておくと良い感じです。
リスト 2.3 のスクリプトは、 samples/dsy-eval-exit_0 にあります。これをそのまま使う場合は、このファイルのシンボリックリンクかコピーを bin ディレク
トリに dsy-eval という名前で作成してください。
本書で dsy-eval として使⽤する評価スクリプトは全て samples ディレクトリ
に置いてあります。

2.2

使⽤例: 簡単な評価スクリプトで試す

ここでは、使い⽅の紹介として、前節の評価スクリプトを使⽤して、次章でも実験– 14 –

20

2.2 使⽤例: 簡単な評価スクリプトで試す

結果として紹介する「正常終了するだけの ELF バイナリ⽣成」へ向けた環境を作ってみます。

♣ ツールをダウンロード
daisy-tools リポジトリの Releases ページでビルド済みバイナリを ZIP アーカイブで配布しています。

• daisy-tools リポジトリの Releases ページ◦ https://github.com/cupnes/daisy-tools/releases
ダウンロードしたらお好きな場所へ展開してください。 dsy-work というディレクトリができあがります。このディレクトリ名は変更しても構いません。
なお、現⾏のビルド済みバイナリの動作環境は表 2.2 の通りです。
▼ 表 2.2: 動作環境
ライブラリ/ソフトウェア

バージョン

Linux
GNU C ライブラリ (libc6)
bash

特になし。ELF が実⾏できれば OK。

2.24
特になし。bash のシェルスクリプトが実⾏できれば OK。

標準的な Linux 環境であればディストリビューション問わず動作すると思いま
す*1 。
ただ、必須要件ではないのですが、ログのほとんどは syslog に出⼒しますので、
syslog が使えない環境 (WSL 等) では syslog 出⼒のログは⾒ることができません。

♣ 細胞ファイルを配置
進化のベースとなる最初の状態の細胞ファイルを cell ディレクトリへ配置します。
本書で進化のベースとして使⽤する細胞ファイルは以下のいずれかです。

• cell/initial◦ ret 命令のみの細胞◦ ⾃⾝を構成する命令には突然変異不可フラグ設定済み◦ samples/create-init-cell で⽣成可能• cell/exit◦ 終了ステータス 0 で終了するための機械語命令群と ret 命令の細胞*1 筆者が使⽤しているのは Debian GNU/Linux 9 (stretch) です。

2
1– 15 –

第 2 章 daisy-tools の使い⽅

◦ ⾃⾝を構成する命令には突然変異不可フラグ設定済み◦ samples/create-exit-cell で⽣成可能
それぞれのツールを実⾏すると、 cell ディレクトリにそれぞれのファイル名で細胞ファイルを⽣成します。なお、daisy-tools では今の所、ファイル名で何らかの判断は⾏っていないので、ファイル名は変更しても構いません。
例えば、 initial の細胞ファイルを cell ディレクトリへ配置する場合は、以下のように samples/create-init-cell を実⾏します。
$ samples/create-init-cell$ ls cell/
initial♣ コード化合物ファイルを配置
コード化合物ファイルは、細胞が成⻑や増殖する際に使⽤するコード化合物に当たるファイルです。表 2.3 の構成の 16 バイトのファイルです。
▼ 表 2.3: コード化合物ファイルの構成
オフセット

内容

⻑さ [バイト]

0
8

命令の⻑さ [バイト]

8
8

機械語命令

なお、 dsy-sysenv ではコード化合物ファイル 1 つを 1 命令として扱います。そのため、分割してほしくない複数の命令がある場合、1 つのコード化合物ファイルに並べておけば、1 命令として扱われます。
本書で⽣成する「正常終了するだけの実⾏バイナリ」と「⽂字’A’ を出⼒する実⾏
バイナリ」については、⽣成するために必要なコード化合物ファイルは、それぞれ以下のサンプルツールで⽣成できます。

• 正常終了するだけの実⾏バイナリ◦ 必要なコード化合物ファイルは samples/create-exit-codes で⽣成できる• ⽂字’A’ を出⼒する実⾏バイナリ◦ 必要なコード化合物ファイルは samples/create-puta-codes で⽣成できる
それぞれのツールは共に、実⾏時に「各命令で何個ずつコード化合物ファイルを⽣成するか」をコマンドライン引数で指定します。そして実⾏すると、指定した個数ず– 16 –

22

2.2 使⽤例: 簡単な評価スクリプトで試す

つ、各命令のコード化合物ファイルが code ディレクトリへ⽣成されます。
例えば、「正常終了するだけの実⾏バイナリ」に必要なコード化合物ファイルを⽣成するには以下の通りです。(各命令 100 個ずつ⽣成)$ samples/create-exit-codes 100+ '[' 1 -ne 1 ']'+ num_codes=100+ mkdir -p code++ seq -w 100+ for i in $(seq -w ${num_codes})...
$ ls -1 code
ret_001..
ret_100
syscall_60_001...
syscall_60_100
xor_rdi_rdi_001...
xor_rdi_rdi_100

このサンプルでは各コード化合物ファイルのファイル名を各命令になぞらえて付けていますが、細胞ファイル同様にファイル名は何でも構いません。
なお、実⾏ログからも分かる通り、 samples/create-exit-codes のサンプル
ツールはシェルスクリプトです。簡単なコマンドでコード化合物ファイルを⽣成する
際に参考にしてみてください。

♣ ユーザー定義スクリプトを配置
bin ディレクトリに dsy-name と dsy-eval のユーザー定義スクリプトを配置

してください。
前述の通り、 dsy-name は samples/dsy-name のシンボリックリンクかコピーで構いません。
$ ln -s ../samples/dsy-name bin/dsy-name$ ls -l bin/dsy-name
lrwxrwxrwx 1 yohgami yohgami 19 2⽉ 12 14:59 bin/dsy-name -> ../samples/dsy››-namedsy-eval は⽣成したいバイナリによって変える必要があります。前節で説明した評価スクリプトで試す場合は以下のようにシンボリックリンクを作成します。

2
3– 17 –

第 2 章 daisy-tools の使い⽅

$ ln -s ../samples/dsy-eval-exit_0 bin/dsy-eval$ ls -l bin/dsy-evallrwxrwxrwx 1 yohgami yohgami 26 2⽉ 12 15:02 bin/dsy-eval -> ../samples/dsy››-eval-exit_0♣ dsy-sysenv を実⾏
以上で準備は完了です、 dsy-sysenv を実⾏すると環境の動作が始まり、細胞の⽣命活動が始まります。
$ bin/dsy-sysenv
dsy-sysenv を実⾏すると running というファイルがカレントディレクトリに作成されます。中断したい場合はこのファイルを削除してください。すると、その周期の全ての動作を終えたところで dsy-sysenv は終了します。
$ ls runningrunning$ rm runningdsy-sysenv は現在の環境の状態を cell と code ディレクトリに保存しています。再開したい場合は単に dsy-sysenv をもう⼀度実⾏すれば良いです。
そして、適応度が 100 の細胞が⽣まれると、 dsy-sysenv はその細胞ファイルをカレントディレクトリに out.cell という名前で保存し、その周期を実⾏し終えた
後、プログラム⾃体を終了します。

– 18 –

2
4

第

3章

実験結果紹介

この章では daisy-tools を使⽤して「終了ステータス 0 で正常終了するだけの実
⾏バイナリ」と「⽂字’A’ を出⼒して正常終了する実⾏バイナリ」のそれぞれを⽣成する実験結果を紹介します。

3.1

実験 1: 正常終了するだけのバイナリ⽣成

前章で紹介した簡単な評価スクリプトで、「何もせず正常終了 (ステータス 0 でexit) するだけの ELF バイナリ」を⽣成させてみます。

♣ 実験条件実 験 条 件 と し て 、 cell ・ code の 各 デ ィ レ ク ト リ と 評 価 ス ク リ プ
ト dsy-eval の状態を説明します。
ま ず 、 cell と code の 各 デ ィ レ ク ト リ 内 の フ ァ イ ル は 、そ れ ぞれ samples/create-init-cell と samples/create-exit-codes で⽣成しました。各命令に対するコード化合物の数は 100 個ずつです。
そして、 dsy-eval は前章で紹介したもので、 samples ディレクトリのファイルとしては dsy-eval-exit_0 です。

♣ 補⾜: code ディレクトリ内の各命令について
今回の実験で code ディレクトリに配置したコード化合物ファイルについて補⾜します。
code ディレクトリに配置したファイルが、「正常終了するだけのバイナリ」を構成する機械語命令列の部分です。ここに配置した命令が突然変異により細胞の中で組み合わされ、「正常終了するだけのバイナリ」が⽣成される事を期待します。

2
5– 19 –

第3章

実験結果紹介code ディレクトリに配置した各命令について、対応するアセンブラとともに列挙

すると表 3.1 の通りです。
▼ 表 3.1: 実験 1:code ディレクトリに配置する命令⼀覧
機械語

(1)
(2)
(3)

[終了ステータス 0 で exit]
48 31 ﬀ
48 31 c0 b0 3c 0f 05[return]c3

アセンブラ

xor %rdi,%rdi
xor %rax,%rax; mov $60,%al; syscallret

表 3.1 の (1) から (3) の各⾏が各コード化合物ファイルに相当し、それぞれ 100 個ずつ code ディレクトリに配置しています。
内容について簡単に説明すると、(1) と (2) が終了ステータス 0 で exit システ
ムコールを呼び出すための命令です。プログラムが終了する際には exit システム
コールを呼ぶ必要があり、このシステムコールは第 1 引数 (RDI) に終了ステータスをとります。そのため (1) で RDI を xor 命令でゼロクリアし終了ステータスに 0を設定しています。
そして、(2) で exit システムコールを呼び出しています。ここで、前章で紹介した「1 つのコード化合物ファイルに複数命令を列挙すれば 1 命令として扱われる」機
能を使っています。システムコールを呼び出す syscall 命令を実⾏すると、RAXに格納された番号のシステムコールがカーネル内で呼び出されるのですが、ここでは「RAX のゼロクリア」
・「RAX へ 60 を加算 (60 を設定)」
・「システムコール呼び出し」
までを 1 命令としています。
「システムコール番号の設定」と「システムコール呼び出し」を 1 命令として扱われるようにしているのは、 dsy-sysenv を実⾏するホスト側で意図しないシステム
コールが呼び出されないようにするためです。細胞の突然変異では、機械語命令列のどこにどの命令が挿⼊/削除/変更されるかが分かりません。どの細胞も評価の過程で⼀度実⾏することになるので、RAX が未設定の状態でシステムコール呼び出しが⾏
われることで、例えば意図しないファイルアクセスなどが⾏われると困るため、明⽰的に指定したシステムコールのみが使われるように、「システムコール番後設定」と「システムコール呼び出し」を 1 命令としています。
最後に (3) の ret 命令は単に関数の return です。初期状態の細胞は ret 命令のみの細胞であるため、⾃分⾃⾝の細胞分裂のために ret 命令のコード化合物も置いています。

– 20 –

2
6

3.1 実験 1: 正常終了するだけのバイナリ⽣成♣ 実験結果ここでは 10 回の実験を⾏い、結果は表 3.2 の通りでした。
▼ 表 3.2: 実験 1:実験結果

1
2
3
4
5
6
7
8
9
10

総時間

総サイクル

結果

42 秒
59 秒
57 秒
59 秒
12 秒
1分6秒
33 秒
1 分 17 秒
51 秒
1分3秒

23
23
21
33
10
42
23
32
43
29

⽣成成功
⽣成成功
⽣成成功
⽣成成功
⽣成成功
⽣成成功
⽣成成功
⽣成成功
⽣成成功
⽣成成功

10 回の実験全てで終了ステータス 0 で正常終了する実⾏バイナリを⽣成することができました。
では、⽣成された実⾏バイナリの機械語命令の並びは期待値通りだったのでしょうか？ 確認してみると、全てのケースで、⽣成された実⾏バイナリの機械語命令部分
がリスト 3.1 の通りでした。
▼ リスト 3.1: 実験 1:⽣成されたバイナリ
0:
3:
5:
7:

48 31 c0
b0 3c
0f 05
c3

xor
%rax,%rax
mov$0x3c,%alsyscallretq

第 1 引数である RDI をゼロクリアする xor 命令が無いです。実は RDI は明⽰的にゼロクリアしなくとも、動作上はゼロになっているのですね。

♣ 考察
1 分前後でできあがるというのは、体感としてはあっという間です。「仕掛けて、寝て、起きたらできあがっている」の理想に対しては、全く申し分ないです。
ただ、今回の場合、「60 番のシステムコール (exit) を呼び出す」という 1 つ分のコドンが追加されれば良く、1 回の突然変異で⽬的のバイナリへ⾄ることができるものでした。
より複雑な実⾏バイナリではどうでしょうか。それは次の実験で確認してみます。

2
7– 21 –

第3章

実験結果紹介3.2

実験 2: ’A’ を出⼒する実⾏バイナリ⽣成

続いて、前節よりは少し複雑な「⽂字’A’ を画⾯に出⼒して正常終了する実⾏バイナリ」の⽣成を⾏ってみます。

♣ 実験条件cell と code の

各

デ

ィ

レ

ク

ト

リ

は

、そ

れ samples/create-exit-cell と samples/create-puta-codes で

れ

ぞ

⽣

成

したものを配置しました。各命令に対するコード化合物の数も実験 1 同様に 100 個ずつです。
評価スクリプト dsy-eval は、 samples/dsy-eval-puta_0 を使⽤していて、内容はリスト 3.2 の通りです。
▼ リスト 3.2: 実験 2:評価スクリプト#!/bin/bash
set -uex
TMP_NAME=.test
if [ $# -ne 1 ]; thenecho "Usage: $0 CELL_FILE" 1>&2
exit 200ficell_file=$1
bin/dsy-cell2elf ${cell_file} ${TMP_NAME}.elf
chmod +x ${TMP_NAME}.elf./${TMP_NAME}.elf >${TMP_NAME}.out || true
if grep -q 'A' ${TMP_NAME}.out; thenexit 100fiexit 50

評価の仕⽅としては実験 1 と同様に「成功 (適応度 100) か失敗 (適応度 50) か」のみです。今回の場合は「実⾏してみて⽂字’A’ を出⼒できたら適応度 100」そして「それ以外は 50」としました。

♣ 補⾜: code ディレクトリ内の各命令について
code ディレクトリに配置した各命令について、対応するアセンブラとともに列挙– 22 –

28

3.2 実験 2: ’A’ を出⼒する実⾏バイナリ⽣成

すると表 3.3 の通りです。
▼ 表 3.3: 実験 2:code ディレクトリに配置する命令⼀覧
機械語

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)

[’A’ を標準出⼒へ出⼒]
48 c7 c7 01 00 00 00
48 c7 c6 78 00 40 00
48 83 c6 22
48 c7 c2 01 00 00 00
48 31 c0 b0 01 0f 05[終了ステータス 0 で exit]
48 31 ﬀ
48 31 c0 b0 3c 0f 05[return]c3

アセンブラ

mov $1,%rdi
mov $0x400078,%rsi
add $34,%rsi
mov $1,%rdx
xor %rax,%rax; mov $1,%al; syscall
xor %rdi,%rdi
xor %rax,%rax; mov $60,%al; syscall
ret「[’A’ を標準出⼒へ出⼒]」の部分では、 write システムコール (システムコール
番号:1) を使⽤して標準出⼒へ’A’ を出⼒しています。
write システムコールは、第 1 引数 (RDI) にファイルディスクリプタ、第 2 引

数 (RSI) に書き込むデータのアドレス、第 3 引数 (RDX) にデータのバイト数をとります。
そこで、(1) で標準出⼒のファイルディスクリプタである 1 を RDI へ設定し、(2)と (3) で⽂字’A’ の先頭アドレスを RSI へ設定 (後述)、(4) でバイト数 1 を RDX へ設定した上で、(5) でシステムコール番号 1 のシステムコールを呼び出します。

(3) で RSI へ格納しているアドレスは、全 ASCII ⽂字が並んでいる領域のアドレスです。write システムコールが出⼒するデータをアドレスで渡す必要があるため、ASCII のキャラクターマップを ELF バイナリに埋め込むことで対応しています。
(4) で RSI に⾜し合わせている値はこのキャラクターマップの中の⽂字’A’ へのオフ
セットです。

ELF バイナリに埋め込んでいる ASCII マップについては daisy-tools リポジトリ
内の dsy-cell2elf.c を⾒てみてください。

(6)・(7)・(8) は実験 1 と同じものです。

♣ 実験結果実験結果は表 3.4 の通りです。
延べ 3 ⽇以上の時間をかけ、9 万回以上のサイクルを実施しましたが、’A’ を出⼒するバイナリへ進化することはありませんでした。

2
9– 23 –

第3章

実験結果紹介▼ 表 3.4: 実験 2:実験結果

1

総時間

総サイクル

結果

3 ⽇ 16 時間

96,685

適応度 100 に⾄らず中⽌♣ 考察
どれだけ時間をかけても期待した進化に⾄らない要因は、期待する進化の幅が⾼すぎる事にあると考えられます。
実験 1 の場合、「ret 命令の前に exit システムコールの命令列が追加される」という 1 度の突然変異で期待する状態に⾄ることができたため、「期待する結果か否か」という「1 か 0 か」の評価でも進化を導くことはできました。
しかし、実験 2 の場合、2 つ以上の命令 (列) をある程度決まったルールで並べる必要があるため、「1 か 0 か」という評価では、評価に⾄るまでに必要な進化の幅が⾼す
ぎるのです。これではランダム性に頼るばかりで、進化を導くことはできません。
イメージとしては図 3.1 のような感じです。例え海に⾷料が少なかったとしても、切り⽴った崖の上にジャンプするような進化は難しいです。そうではなく、できる限
りなだらかな斜⾯で徐々に⾷料を得る機会が増えるような環境だと、⼩さなステップの進化を繰り返すことで⽬的地へたどり着くことができます。

– 24 –

30

3.3 実験 3: ’A’ を出⼒する実⾏バイナリ⽣成 (改良版)▲ 図 3.1: 急な崖上へジャンプするような進化は難しい

3.3

実験 3: ’A’ を出⼒する実⾏バイナリ⽣成 (改良版)

徐々に適応度が上がるような評価スクリプトを⽤意して実験を⾏ってみます。

♣ 実験条件cell と code の各ディレクトリの初期状態は実験 2 と同じです。

評価スクリプト dsy-eval は、徐々に適応度が上がるように⼯夫してリスト 3.3のようにしてみました。(同じものが samples/dsy-eval-puta にあります)3
1– 25 –

第3章

実験結果紹介▼ リスト 3.3: 実験 3:評価スクリプト#!/bin/bash
set -uex
TMP_NAME=.test
if [ $# -ne 1 ]; thenecho "Usage: $0 CELL_FILENAME" 1>&2
exit 200ficell_filename=$1
bin/dsy-cell2elf ${cell_filename} ${TMP_NAME}.elf
chmod +x ${TMP_NAME}.elf
exit_status=0./${TMP_NAME}.elf >${TMP_NAME}.out || exit_status=$?
if [ ${exit_status} -ne 0 ]; then
# 突然変異でret命令が変なところに⼊る等 、# 終了ステータスが0ではない状態で終了するようになってしまった場合# 適応度は0とする
exit 0fi
bin/dsy-dump-cell -j ${cell_filename} >${TMP_NAME}.json
num_codns=$(jq .attr.num_codns ${TMP_NAME}.json)
if [ ${num_codns} -eq 0 ]; then
# コドン数=0 は何かがおかしい
exit 200fi# コドン数に応じて適応度を上げる# 適応度 = 6 * コドン数 + 32
fitness=$(((6 * num_codns) + 32))
if [ ${fitness} -gt 90 ]; then
# コドン数に応じた適応度では90以上にはならない
fitness=90
fi
if grep -q 'A' ${TMP_NAME}.out; then
# 'A'を出⼒できた場合 、適応度100
fitness=100
elif [ $(wc -c ${TMP_NAME}.out | cut -d' ' -f1) -gt 0 ]; then
# 'A'でなくとも何かを出⼒したなら適応度に9点加点する– 26 –

32

3.3 実験 3: ’A’ を出⼒する実⾏バイナリ⽣成 (改良版)

fitness=$((fitness + 9))fiexit ${fitness}

主にコドン数 (命令数) に応じて、最⼤ 90 まで適応度を上げるようにしてみました。また、’A’ でなくとも何かを出⼒できた場合はそれも評価するようにしています。

♣ 実験結果実験結果は表 3.5 の通りです。
▼ 表 3.5: 実験 3:実験結果

1
2
3

総時間

総サイクル

結果

3 時間 38 分
5 時間 56 分
6 時間 15 分

1,805
2,743
2,988

⽣成成功
⽣成成功
⽣成成功

期待する状態へ進化を導くことができました。
⽣成された実⾏バイナリは、例えば 1 回⽬の実験ではリスト 3.4 の通りです。
▼ リスト 3.4: 実験 3:1 回⽬の実験結果
0:
4:
b:
12:
15:
1c:
20:
27:
2a:
2c:
2e:
31:
34:
36:
38:

48 83 c6 22
48 c7 c7 01 00 00 00
48 c7 c6 78 00 40 00
48 31 ff
48 c7 c7 01 00 00 00
48 83 c6 22
48 c7 c2 01 00 00 00
48 31 c0
b0 01
0f 05
48 31 ff
48 31 c0
b0 3c
0f 05
c3

add
$0x22,%rsimov$0x1,%rdi
mov$0x400078,%rsi
xor%rdi,%rdi
mov$0x1,%rdi
add$0x22,%rsimov$0x1,%rdx
xor%rax,%rax
mov$0x1,%al
syscallxor%rdi,%rdi
xor%rax,%rax
mov$0x3c,%alsyscallretq♣ 考察
3 ⽇以上かけても到達できなかった状態へ、最短で 3 時間半で到達できたことは⼤きな進歩です。やはり進化を導くには評価を適切に⾏う必要があると考えられます。

3
3– 27 –

第3章

実験結果紹介ただ、⽣成されたバイナリは⽬的の振る舞いは達成しますが、無駄な命令をいくつも蓄えています。1 回⽬の実験結果のみ掲載しましたが、無駄に蓄えている命令が違うだけで 2 回⽬と 3 回⽬の実験結果も同様でした。
今回設定した評価スクリプトの場合、命令数が多い、すなわち体が⼤きい個体ほど栄養を取り⼊れる機会を多く得る世界である事に加え、前述の通り、命令数の多さに⽐例して寿命を延ばすようにしているため、このような結果になるのは仕⽅ないと⾔えます。対策としては、例えば、適応度 100 の個体が現れた時点で環境を⽌めるのではなく継続するようにして、適応度 100 の個体のみ「コドン数 (命令数) が少ないほど適応度をより上げる*1 」というように評価の仕⽅を切り替える事が考えられます。

*1 100 を超える適応度を化合物を取得する確率としてどう扱うかが問題ですが、例えば「1 つは確実に取得できるとした上で、100 を超えている分の値を、さらにもう⼀つ取得できる確率として扱う」
事が考えられます。

– 28 –

3
4

おわりにここまで本書をお読みいただきありがとうございました！ 本書で前著の設計に「進化」の仕組みを導⼊し、ついに実⾏バイナリを⽣成できるようになりました。その⽅法は⽣物学にアイディアを得たオリジナルのものですが、ジャンルとしては「遺伝的アルゴリズム」の⼀種になるのかなと思います。本来の遺伝的アルゴリズムは⽣物の遺伝の仕組みのみをモデル化しており、わざわざ⽣物が⽣きる振る舞いを模倣したりはしませんが、「バイナリ⽣物学」では「⽣きていると⾔い張れる」だけの振る舞い
をバイナリにさせた上で進化の仕組みを導⼊します。そのため、より⽣々しく⽣物の振る舞いを模倣している⼿法であるかと思います。

3 つの実験を通して、評価スクリプトを適切に⽤意すれば実⾏バイナリを⽣成できる事を⽰しました。⽣成された実⾏バイナリは、評価スクリプトの評価は満たしつつも、機械語のコード列としては「想定よりも短いコードで実現可能」だったり、「余計なコードがいくつも付いていた」り、といったものが⽣成されていた点は興味深いポイントです。些細なことでもありますが、前者は、設計者が想定していた以上の最適化が⾏われていたとも⾔えます。後者は、実⾏上は問題ないですが、余計なゴミがくっついているという意味ではバグ (?) かもしれません。バグに対しては評価⽅法を改善すれば良いので、「⼈間の想定以上の解が産まれ得る」という点が「進化」によるバイナリ⽣成の重要ポイントじゃないかなと思います。
また、このバイナリ⽣成⽅法では、エンジニアは評価スクリプトしか書かないため、それをテストコードと捉えるなら、「エンジニアがテストコード書かない問題」を解決しているとも (⼀応) ⾔えます。加えて評価の仕⽅はアーキテクチャ⾮依存にできるので、「⼀つの評価スクリプトで複数のアーキテクチャ向けの実⾏バイナリを⽣成する」といったことも可能です。
課題は「実⽤的な実⾏バイナリは⽣成できるのか」あるいは「そういうものではない」としても「何に使えるのか？」という所ですね。実⽤的な実⾏バイナリは今回実験したようなバイナリよりももっと規模が⼤きく多機能であるため、例えば「別々の環境で単機能毎に進化した細胞を組み合わせて多細胞⽣物にする」といったような新しい進化の仕組みが必要そうです。なお、daisy-tools は「バイナリ」であれば⽣成対
象は「実⾏バイナリ」以外も可能な⽅法であるため、現状の実装でも何か解決できる問題はあるかもしれません。
なお、「daisy-tools」という名前の元ネタはガイア理論の「デイジーワールド」です。「バイナリを⽣きている様に産み出す」という発想元には⼩さい頃に遊んだ「シムアース」があったりします。

3
5– 29 –

バイナリ⽣成環境「daisy-tools」実験報告
培養‧進化で簡単な ELF バイナリを⽣成！

2020 年 2 ⽉ 29 ⽇
2023 年 5 ⽉ 20 ⽇
著

者

⼤神祐真

発⾏者

⼤神祐真

連絡先

ver 1.0 （技術書典 8 新刊）
ver 1.1 （技書博指定の奥付を追加）

yuma@ohgami.jp
http://yuma.ohgami.jp@yohgami (https://twitter.com/yohgami)
印刷所

⽇光企画

© 2020 へにゃぺんて(powered by Re:VIEW Starter)

3
6