第3章 実験結果紹介

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ディレクトリに配置したファイルが、「正常終了するだけのバイナリ」を構成する機械語命令列の部分です。ここに配置した命令が突然変異により細胞の中で組み合わされ、「正常終了するだけのバイナリ」が生成される事を期待します。

codeディレクトリに配置した各命令について、対応するアセンブラとともに列挙すると表3.1の通りです。

表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命令のコード化合物も置いています。

実験結果

ここでは10回の実験を行い、結果は表3.2の通りでした。

10回の実験全てで終了ステータス0で正常終了する実行バイナリを生成することができました。

では、生成された実行バイナリの機械語命令の並びは期待値通りだったのでしょうか？確認してみると、全てのケースで、生成された実行バイナリの機械語命令部分がリスト3.1の通りでした。

0:   48 31 c0                xor    %rax,%rax
3:   b0 3c                   mov    $0x3c,%al
5:   0f 05                   syscall
7:   c3                      retq

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

考察

1分前後でできあがるというのは、体感としてはあっという間です。「仕掛けて、寝て、起きたらできあがっている」の理想に対しては、全く申し分ないです。

ただ、今回の場合、「60番のシステムコール(exit)を呼び出す」という1つ分のコドンが追加されれば良く、1回の突然変異で目的のバイナリへ至ることができるものでした。

より複雑な実行バイナリではどうでしょうか。それは次の実験で確認してみます。

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の通りです。

#!/bin/bash

set -uex

TMP_NAME=.test

if [ $# -ne 1 ]; then
        echo "Usage: $0 CELL_FILE" 1>&2
        exit 200
fi

cell_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; then
        exit 100
fi
exit 50

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

補足: codeディレクトリ内の各命令について

codeディレクトリに配置した各命令について、対応するアセンブラとともに列挙すると表3.3の通りです。

「['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'を出力するバイナリへ進化することはありませんでした。

考察

どれだけ時間をかけても期待した進化に至らない要因は、期待する進化の幅が高すぎる事にあると考えられます。

実験1の場合、「ret命令の前にexitシステムコールの命令列が追加される」という1度の突然変異で期待する状態に至ることができたため、「期待する結果か否か」という「1か0か」の評価でも進化を導くことはできました。

しかし、実験2の場合、2つ以上の命令(列)をある程度決まったルールで並べる必要があるため、「1か0か」という評価では、評価に至るまでに必要な進化の幅が高すぎるのです。これではランダム性に頼るばかりで、進化を導くことはできません。

イメージとしては図3.1のような感じです。例え海に食料が少なかったとしても、切り立った崖の上にジャンプするような進化は難しいです。そうではなく、できる限りなだらかな斜面で徐々に食料を得る機会が増えるような環境だと、小さなステップの進化を繰り返すことで目的地へたどり着くことができます。

図3.1: 急な崖上へジャンプするような進化は難しい

3.3 実験3: 'A'を出力する実行バイナリ生成(改良版)

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

実験条件

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

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

#!/bin/bash

set -uex

TMP_NAME=.test

if [ $# -ne 1 ]; then
        echo "Usage: $0 CELL_FILENAME" 1>&2
        exit 200
fi

cell_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 0
fi

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 200
fi

# コドン数に応じて適応度を上げる
# 適応度 = 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点加点する
        fitness=$((fitness + 9))
fi

exit ${fitness}

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

実験結果

実験結果は表3.5の通りです。

期待する状態へ進化を導くことができました。

生成された実行バイナリは、例えば1回目の実験ではリスト3.4の通りです。

   0:   48 83 c6 22             add    $0x22,%rsi
   4:   48 c7 c7 01 00 00 00    mov    $0x1,%rdi
   b:   48 c7 c6 78 00 40 00    mov    $0x400078,%rsi
  12:   48 31 ff                xor    %rdi,%rdi
  15:   48 c7 c7 01 00 00 00    mov    $0x1,%rdi
  1c:   48 83 c6 22             add    $0x22,%rsi
  20:   48 c7 c2 01 00 00 00    mov    $0x1,%rdx
  27:   48 31 c0                xor    %rax,%rax
  2a:   b0 01                   mov    $0x1,%al
  2c:   0f 05                   syscall
  2e:   48 31 ff                xor    %rdi,%rdi
  31:   48 31 c0                xor    %rax,%rax
  34:   b0 3c                   mov    $0x3c,%al
  36:   0f 05                   syscall
  38:   c3                      retq

考察

3日以上かけても到達できなかった状態へ、最短で3時間半で到達できたことは大きな進歩です。やはり進化を導くには評価を適切に行う必要があると考えられます。

ただ、生成されたバイナリは目的の振る舞いは達成しますが、無駄な命令をいくつも蓄えています。1回目の実験結果のみ掲載しましたが、無駄に蓄えている命令が違うだけで2回目と3回目の実験結果も同様でした。

今回設定した評価スクリプトの場合、命令数が多い、すなわち体が大きい個体ほど栄養を取り入れる機会を多く得る世界である事に加え、前述の通り、命令数の多さに比例して寿命を延ばすようにしているため、このような結果になるのは仕方ないと言えます。対策としては、例えば、適応度100の個体が現れた時点で環境を止めるのではなく継続するようにして、適応度100の個体のみ「コドン数(命令数)が少ないほど適応度をより上げる*1」というように評価の仕方を切り替える事が考えられます。