C言語から0番地へアクセスする方法についての個人的まとめ

発端はuchan_nos氏によるこのツイートでした。

それに対する私のリプライ:

私はこれで話が終わると思っていたのだが、どうやらそうではなかったらしく、色々な視点からの意見が加わりながら、話は混沌を極めたのでした…。

ということで、ここに私のこのツイートに対しての見解とか、わかったことをまとめておこうと思います。

私のリプライの背景について

uchanさんが求める「0番地にデータを書きたい」という課題設定を、私はこのように解釈しました。

  • C言語において、整数0をポインタに変換すると、それはNULLポインタになる
  • C言語において、NULLポインタへのアクセスは未定義動作である
  • したがって、0番地にデータを書くことはできないのではないだろうか?
  • これをすり抜ける方法はあるか?

これを受けて、私はこのように考えました。

  • NULLポインタへのアクセスが未定義となるのはコンパイル時の話である
  • ではコンパイル時にNULLポインタであるとコンパイラにバレなければ未定義動作にならないのではないだろうか?
  • じゃあアドレス1を代入してポインタをつくり、それを引き算して0番地へのポインタをつくれば、コンパイラは見逃してくれるのではないだろうか?

そして、以下のコード片が生まれたわけです。

uint8_t *p = 1;  p--; *p = v;

ここで、vは何らかのuint8_t型の書き込みたいデータである(と文脈からわかると期待)。

仕様上の問題

しかしその後、有識者の人々がにわかにざわつき始めた。そして、私の提示したコードはやはり動かないということをherumiさんがありがたくも指摘してくださったわけです。

では仕様上、単なる0番地への代入コードや、私の書いたコードがなぜうまく動かないのかをみていきましょう。

0をポインタにキャストするとそれはnull pointerになる (6.3.2.3 - 3)

この仕様によれば、整数定数0となるような定数式をポインタにキャストすると、それはnull pointerになる。 そして、null pointerは、いかなるオブジェクトや関数へのポインタとも等しくならないことが保証されている。

null pointerを用いた間接参照は未定義動作になる (6.5.3.2 - 4)

この仕様によれば、*演算子を用いた間接参照をするときに、その参照が「無効なもの」であるとき、*演算子の挙動は未定義となる。 ここでいう「無効なもの」には、null pointerも含まれると注釈102に書かれている。


したがって、0番地に1を書き込もうとして *(uint8_t *)0 = 1; と書いてもこれは未定義動作になる これは、整数定数0をポインタにキャストしたもの(uint8_t *)0がnull pointerであり(ここまでは定義された動作)、これへの間接参照が「null pointerを用いた間接参照」になるためである。

この、null pointerへの間接参照を回避するための方法として私が編み出したのがuint8_t *p = 1; p--; *p = v;であるが、これも以下の仕様によって「処理系定義」の動作になる。

整数からポインタへの変換は処理系定義である (6.3.2.3 - 5)

この仕様によれば、整数からポインタへの変換を行ってもよいが、その結果は処理系定義になるという。 つまり、たとえアドレス1を表現しようとして(uint8_t *)1と書いても、その内部表現が整数1と等しくなるとは保証されないということである。


したがって、uint8_t *p = 1; p--; *p = v;と書いても、最初のuint8_t *p = 1;の段階でpがどこを指しているかは処理系の動作に完全に依存し、1番地を指しているとは限らないため、私の提案した方法は残念ながら処理系定義の結果になる。

しかも、最適化によって、コンパイラ*p=v;のタイミングでpがnull pointerになることを推測してしまう場合があるらしく、そうするとこれは未定義動作になってしまう。(これがherumiさんにご指摘いただいた部分。)

まじか、最適化の結果未定義動作を踏むこともあるのか、つらいな…。

じゃあどうすればいいのか

これは多くの人がすでに指摘している通りで、かつ私も同意する結果なのですが、

「処理系定義の動作に依存することなくメモリの0番地にC言語から読み書きをすることは不可能である」

が答えです。

これは、そもそもC言語には「メモリの何番地」に該当する概念がなく、ポインタへの整数値の代入も処理系定義であることが原因であるため、どうしようもありません。

なんとかできないの?

いくつかの点に目をつぶれば、まあ結果的に実現することは可能です。

*(uint8_t *)(0) = 1; とその派生

これは、今まで説明してきた理由によれば未定義動作となるため、鼻から悪魔が出てきてもおかしくありません。早速Compiler Explorerでやってみましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(uint8_t *)(0) = 1; with -O0 OK OK
*(uint8_t *)(0) = 1; with -O3 NG(ud2) NG(ud2)

残念ながら悪魔は出てきませんでしたが、最適化を有効にするとやはりud2ですね。しかし、最適化を無効にすれば一応期待通りのコードが得られます。

と、ここで気になるWarningがclangから出力されていることに気付きました。

<source>:3:5: warning: indirection of non-volatile null pointer will be deleted, not trap [-Wnull-dereference]

    *(uint8_t *)(0) = 1;

    ^~~~~~~~~~~~~~~

<source>:3:5: note: consider using __builtin_trap() or qualifying pointer with 'volatile'

1 warning generated.

Compiler returned: 0

ほう?volatileをつけると何か変わるんですかね。やってみましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(uint8_t * volatile)(0) = 1; with -O0 OK OK
*(uint8_t * volatile)(0) = 1; with -O3 NG(ud2) NG(ud2)

あれ、volatiileをつける場所、こっちじゃないの?

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(volatile uint8_t *)(0) = 1; with -O0 OK OK
*(volatile uint8_t *)(0) = 1; with -O3 NG(ud2) OK

なるほど、こうすれば、clangでは最適化を有効にしていても、volatile 修飾をすることで有効なコードを吐いてくれるようです。gccは規格通りだめみたいですが…。

uint8_t *p = 1; p--; *p = 1; とその派生

この手法は、null pointer dereference が未定義動作になる挙動を回避した(つもりだった)ものです。(もちろん、この挙動は整数からポインタへの変換という処理系定義の動作に依存しています。)

x86-64 gcc 9.2 x86-64 clang 9.0.0
uint8_t *p = 1; p--; *p = 1; with -O0 OK OK
uint8_t *p = 1; p--; *p = 1; with -O3 NG(ud2) NG(ud2)

しかし、最適化によって前半の結果pがnull pointerになることが推測されてしまっており、その結果ud2が生成されていますね。ということで、最適化を無効にするためにvolatile をつけてあげましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
uint8_t * volatile p = 1; p--; *p = 1; with -O0 OK OK
uint8_t * volatile p = 1; p--; *p = 1; with -O3 OK OK
volatile uint8_t * p = 1; p--; *p = 1; with -O3 NG(ud2) OK

おー、確かに動きはしますね。でもポインタ演算が入ってしまいますが…。

volatile修飾をポインタ変数ではなく、その指す値につけてみると、ポインタ演算に関する最適化は両者とも走るようになり、gccでは想定通りud2になったんですが、なんとclangでは最適化された結果である0番地への代入mov byte ptr [0], 1 が生成されました。 clangはvolatileがついてたらnull pointerのdereferenceも許容してくれるってことみたいですね。

追記: -fno-delete-null-pointer-checks というフラグをコンパイル時につける

clangとgccの両方で期待通り動くようです。gccのドキュメントにおける記載はここにあります。なるほどud2になる挙動は、「絶対に引っかかることがコンパイル時にわかっている(実行時に行われる可能性がある)null pointer checkを、コンパイル時にud2に置き換える」という最適化によるものなんですね。

ところで調べていたら、このコンパイルオプションが追加されたClangへのパッチを見つけました。曰く:

Support for this option is needed for building Linux kernel. This is a very frequently requested feature by kernel developers.

More details : https://lkml.org/lkml/2018/4/4/601

なるほど、やはりLinux Kernel開発者からの熱い要望があったんですね。(lkmlのリンクに飛ぶと、Linusの熱い言葉が見れるのでおすすめです。)入ったのが比較的最近(2018年中頃)というのも面白いですね。

(Thanks @herumi, @kazuho !)

追記: __attribute__((address_space(1))) をポインタ変数につける(LLVM/clang限定)

id:uenoku さんのコメント曰く:

id:uenoku

既出でしたら申し訳ないですが、clangならllvm::NullPointerIsDefinedをtrueにすることを考えれば良いので以下のようなコードがかけます https://godbolt.org/z/x5cXf4

Compiler Explorerでの結果 のうち、f1, f2は前述した-fno-delete-null-pointer-checksによるもの、f3がこの手法です。

address_space(n) というattributeは、そのポインタがどのアドレス空間のものかを指定するもので、デフォルトはaddress_space(0)になっています。そしてこのAddress Spaceの値が、null pointerへの参照が定義された動作かを判定するLLVMの関数bool llvm::NullPointerIsDefined(const Function *F, unsigned AS) @ lib/IR/Function.cpp に渡されます。この関数の実装を見てみると:

bool Function::nullPointerIsDefined() const {
  return getFnAttribute("null-pointer-is-valid")
          .getValueAsString()
          .equals("true");
}

bool llvm::NullPointerIsDefined(const Function *F, unsigned AS) {
  if (F && F->nullPointerIsDefined())
    return true;

  if (AS != 0)
    return true;

  return false;
}

AS(address space)が0以外のとき、常にtrueを返すことがわかります。これで、null pointerへの参照が未定義動作ではないよとコンパイラに教えることができるわけです。なるほどー。

(Thanks id:uenoku !)

まとめ

  • C言語はやはり難しい
  • こんな記事を書いて時間をつぶしている場合ではなかった
  • でも仕様書を読むのも楽しいのでおすすめ

参考文献

  • (n1570.pdf)

2019年概観

2019年を時系列に振り返る。Twitter埋め込みが大量にあるので注意。

  • 1月
    • さくらインターネットで委託研究員としてNVDIMMたちと戯れていた(4月まで)
    • liumOS本格始動
    • VR環境が整備された
    • 試される大地に行った




  • 5月
    • プラサミ+自作OSもくもく会

  • 6月
    • 某社の面接を受けた
    • ハッカーズチャンプルー登壇 @ 琉球大学 docs.google.com

  • 7月

  • 8月
    • ドワンゴでバイトを開始した(継続中)
    • 某社からオファーをもらったので承諾
    • セキュキャンでRuiさんとともにCコンパイラゼミの講師を担当
    • ラボユースキャンプに卒業生として参加




まとめ

今年もなんだかんだ活発に活動していた。本当にえらい!

タスクを積みすぎるところは反省点なので、来年はある程度自制することも覚えましょう。(すでに積み上がったタスクを眺めながら。)

来年もよい年になりますように。

SECCON CTF 2019 Final competition Q4 "box" write-up

2019-12-22に開催されたSECCONの国際決勝に、hiww, h_noson, st98ともにHarekazeとして参加しました。(昨年は国内決勝に参加してました。)

順位はあまり振るわず、14チーム中11位でしたが、個人的には問題4の"box"のattackフラグを全部回収できたので大満足です。ということで、問題4の私なりの解き方についてまとめておきます。

"box"問題概要

今回は6つ大問がありましたが、そのうちの4問目でした。問題としては、stripされたx86バイナリと、それに特定の入力を与えた際の分岐トレース結果が配布されるので、同一の分岐トレースが得られるような入力をみつける、というものです。

……あれ?この話前にも聞いたことがありますね。そうです、今年の予選では、完全に同様の形式の問題(follow-me)が出されていたのでした。

hikalium.hatenablog.jp

ということで、あとはやるだけです。

Attackフラグとしては、box1から4と名付けられた4つの問題がダウンロードできるので、それを解いて入力をAPIに投げるとフラグが得られます。

Defenceフラグとしては、box1に類似した問題が1時間ごとに出され、それをその時間内に解いてAPIに投げるとチームのtokenを設置できるのですが、ちょっと厳しかったので諦めました(後述)。

では、box1から4まで順に見ていきましょう。

box1

入力形式の特定

とりあえず普通のLinuxバイナリなので実行してみます。

$ ./box 
usage: ./box formula

なるほど…式を引数で渡すんですね。

$ ./box '1+3'
error: unhandled char '+'

うーん、だめですね。じゃああれかな、予選の時と同じ入力形式なのかな?

./box '1,3,+'
error: unhandled char ','

違うみたい…。(ここから試行錯誤することしばらく。)

$ ./box ''
error: stack is empty
$ ./box '0'
error: stack is empty
$ ./box '00'
error: stack is empty
$ ./box '000'
error: stack is empty
$ ./box '0000'
0

あー…なるほど?(さらにしばらく試行錯誤して。)

$ ./box '00010002a'
3
$ ./box '00010002b'
-1
$ ./box '00010002c'
2
$ ./box '00010002d'
1
$ ./box '00010002e'
2
$ ./box '00010002f'
5
$ ./box '00010002g'
error: unhandled char 'g'

なるほど、演算子はa-fなんですね。(なぜアセンブリを読まないのか(つかれてたので))。

トレースをみてみる

$ cat box.trace        
[                                                                         
{"event": "image_load", "image_name": "***/box1", "image_id": 1, "base_addr": "0x557a93890000", "image_size": "0x135f"},
{"event": "image_load", "image_name": "/lib64/ld-linux-x86-64.so.2", "image_id": 2, "base_addr": "0x7fb95ac8c000", "image_size": "0x26c23"},
{"event": "image_load", "image_name": "[vdso]", "image_id": 3, "base_addr": "0x7ffc905a6000", "image_size": "0x100a"},
{"event": "image_load", "image_name": "/lib/x86_64-linux-gnu/libc.so.6", "image_id": 4, "base_addr": "0x7fb9464a4000", "image_size": "0x3f0adf"},
{"event": "branch", "inst_addr": "0x557a9389064e", "branch_taken": true}, 
{"event": "branch", "inst_addr": "0x557a93890ed4", "branch_taken": false},
{"event": "branch", "inst_addr": "0x557a938907f5", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890786", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890ef4", "branch_taken": false},
{"event": "branch", "inst_addr": "0x557a938906b0", "branch_taken": true}, 
{"event": "branch", "inst_addr": "0x557a93890690", "branch_taken": true}, 
{"event": "branch", "inst_addr": "0x557a93890e3f", "branch_taken": true}, 
{"event": "branch", "inst_addr": "0x557a938906c0", "branch_taken": true}, 
...
]

こんな感じでJSONが書かれています。 base_addrは最初の要素に書いてあるので、ちゃんとやるなら引き算をすれば、適当にするなら下4桁をとればファイル内のアドレスになりそうです。 というわけで、objdumpと照らし合わせればすべてわかりそう…でもせっかくトレーサーのソースも与えられているし、あとのことも考えるとトレーサーの環境を用意した方がよくない?という気持ちになったので用意することに。

トレーサーの環境構築

問題で配布されているファイルの中には、トレース出力を得るために使ったトレーサーのソースも含まれていました。なので、これを実行したいのですが、これはIntel Pinというライブラリに依存しているので、適当にPinのソースコードを落としてきてビルドします。そして、Pinを用いたサンプルコードのディレクトリに行って、サンプルのうちひとつをコピーし、それのソースとMakefileを書き換えて、トレーサーのライブラリファイルをビルドしました。

/path/to/pin/source/tools/branchtrace $ ls
branchtrace.cpp  branchtrace.out  debugtrace.cpp  makefile  makefile.rules  obj-intel64
/path/to/pin/source/tools/branchtrace $ ls obj-intel64/
branchtrace.o  branchtrace.so

このbranchtrace.soというのがトレーサーになります。

トレーサーの実行

branchtrace.soを直接実行することはできないので、pinを介して呼び出します。以下のような感じで。

q4/box1$ /path/to/pin/pin -t /path/to/pin/source/tools/branchtrace/obj-intel64/branchtrace.so -- ./box '00010002a'
3
q4/box1$ cat branchtrace.out | head -n 7
[
{"event": "image_load", "image_name": "/vagrant/seccon2019df/q4/box1/box", "image_id": 1, "base_addr": "0x55aa08e61000", "image_size": "0x135f"},
{"event": "image_load", "image_name": "/lib64/ld-linux-x86-64.so.2", "image_id": 2, "base_addr": "0x7f4f2c012000", "image_size": "0x26c23"},
{"event": "image_load", "image_name": "[vdso]", "image_id": 3, "base_addr": "0x7fff31bb3000", "image_size": "0x100a"},
{"event": "image_load", "image_name": "/lib/x86_64-linux-gnu/libc.so.6", "image_id": 4, "base_addr": "0x7f4f1782a000", "image_size": "0x3f0adf"},
{"event": "branch", "inst_addr": "0x55aa08e6164e", "branch_taken": true},
{"event": "branch", "inst_addr": "0x55aa08e61ed4", "branch_taken": false},

できましたね!

結果を整形する

pinの出力してくれるtrace結果はまあまあ綺麗なのですが、各分岐のアドレスがイメージ内の相対ではないので、配布されたものと手元では値が異なり比較が面倒です。 ということで、ささっとスクリプトを書いて整形してくれるようにしましょう。私はNodejsが好きな変人なのでnodejsで書いたprint.jsがこちら。

const fs = require('fs');

const filename = process.argv[2];
const parseTrace =
    (fileName) => {
      const trace = JSON.parse(fs.readFileSync(fileName, 'utf-8'));
      const base_addr = parseInt(trace[0].base_addr, 16);
      const branches = trace.filter(e => (e.inst_addr != undefined)).map(e => {
        if (e.event === 'call') {
          return {
            'addr': (parseInt(e.inst_addr, 16) - base_addr).toString(16),
            'target': (parseInt(e.target_addr, 16) - base_addr).toString(16)
          };
        }
        return {
          'addr': (parseInt(e.inst_addr, 16) - base_addr).toString(16),
          'taken': e.branch_taken
        };
      });
      return branches;
    }

const print =
    (branches) => {
      for (var i = 0; i < branches.length;) {
        const b = branches[i];
        var count = 0;
        while (i < branches.length && branches[i].addr == b.addr &&
               branches[i].taken == b.taken) {
          count++;
          i++;
        }
        console.log(`${JSON.stringify(b)} * ${count}`);
      }
      console.log(branches.length);
    }

const branches = parseTrace(filename);
print(branches);

最初のほうでは気づかなかったのですが、同じ分岐をぐるぐる回る際もけっこうあって、それを *Nと表示した方がわかりやすかったので、そうしていたりします。(色々適当に工夫しながらできあがった完成形。) また、あとのほうでjmp ccだけでなくcallも出てきたので、それにも一応対応してます。

実行するとこんな感じです。

q4/box1$ node print.js box.trace | head -n 5
{"addr":"64e","taken":true} * 1
{"addr":"ed4","taken":false} * 1
{"addr":"7f5","taken":true} * 1
{"addr":"786","taken":true} * 1
{"addr":"ef4","taken":false} * 1

よいよい、みやすくなった。

入力と分岐の対応関係を調べる

本当ならファジングなり、静的解析でツールを使うなり、ちゃんとやったほうが早いと思うのですが、私はobjdumpしかわからないので、バイナリのobjdumpを横においておきながら、入力と分岐を変化させて、トレーサーをぶん回しながら、どういう挙動をしているのか調べます。

メモの断片:

XXXXYYYYa
{"addr":"ddc","taken":true},
{"addr":"bac","taken":false},
{"addr":"bb6","taken":false},
{"addr":"964","taken":true},
{"addr":"964","taken":true},
{"addr":"a21","taken":true},
{"addr":"a31","taken":true},* Y+1 times
{"addr":"9c4","taken":true},
{"addr":"bf5","taken":true},

00020001b
{"addr":"ddc","taken":true},
{"addr":"bac","taken":false},
{"addr":"bb6","taken":true},
{"addr":"bfe","taken":false},
{"addr":"964","taken":true},
{"addr":"964","taken":true},
{"addr":"9c4","taken":true},
{"addr":"c3d","taken":true},

00200010c

{"addr":"ddc","taken":true},                                                                                                                                                                                                                                  
{"addr":"bac","taken":false},                                                                                                                                                                                                                                 
{"addr":"bb6","taken":true},                                                                                                                                                                                                                                  
{"addr":"bfe","taken":true},                                                                                                                                                                                                                                  
{"addr":"c46","taken":false},                                                                                                                                                                                                                                 
{"addr":"964","taken":true},                                                                                                                                                                                                                                  
{"addr":"964","taken":true},                                                                                                                                                                                                                                  
{"addr":"a5c","taken":true},                                                                                                                                                                                                                                  
{"addr":"a82","taken":true},                                                                                                                                                                                                                                  
{"addr":"a94","taken":true}, // opR + 1                                                                                                                                                                                                                                                                                                                                                                                                                                                              
{"addr":"9c4","taken":true},                                                                                                                                                                                                                                  
{"addr":"c85","taken":true}, 

なるほど、結局のところ

XXXXYYYYa -> XXXX+YYYY
XXXXYYYYb -> XXXX-YYYY
XXXXYYYYc -> XXXX*YYYY
XXXXYYYYd -> min(XXXX, YYYY)
XXXXYYYYe-> max(XXXX, YYYY)

という感じの逆ポーランド記法電卓なんですねー(X, Yは数字) あと、addとmulでは、右辺の値に対応して、途中の分岐の呼ばれる数が変わるんですねーということがわかりました。

ということで、適当に合いそうな入力を考えて、トレース……よし、合っていそう。では、投げましょう。私はこんな入力をえらびました。

001000000012ce0010a0000b

わーい!次にいきましょうー

box2

なんだ楽勝じゃん、次もどうせ入力が違うだけなのでは?と思ったのですが

$ ./box
usage: ./box input

どうも入力はformura、つまり式ではないようです。色々入れてみましょう。

$ ./box hoge
_t
$ ./box hogehoge
#^L8
$ ./box hogehogehoge
ɿAV
$ ./box hogehogehogefuga
@%Zyr
$ ./box hogehogehogefugassssssssssssssssssssssssss
-2"qC
$ ./box hogehogehogefugasssssssssssssssssssssssssssssssssssssss
N?sG>*AA^8>PwvƴP
$ ./box hogehogehogefugassssssssssssssssssssssssssssssssssssssssssss
z:R
   Rc-OgGOx

おお?なんか印字不能な文字を出してくるときもありますね。それに、入力と出力の対応も不明です。困った。 とりあえずobjdump...と。

     8c9:       c6 45 e0 27             movb   $0x27,-0x20(%rbp)
     8cd:       c6 45 e1 51             movb   $0x51,-0x1f(%rbp)
     8d1:       c6 45 e2 90             movb   $0x90,-0x1e(%rbp)
     8d5:       c6 45 e3 79             movb   $0x79,-0x1d(%rbp)
     8d9:       c6 45 e4 66             movb   $0x66,-0x1c(%rbp)
     8dd:       c6 45 e5 b7             movb   $0xb7,-0x1b(%rbp)
     8e1:       c6 45 e6 25             movb   $0x25,-0x1a(%rbp)
     8e5:       c6 45 e7 61             movb   $0x61,-0x19(%rbp)
     8e9:       c6 45 e8 45             movb   $0x45,-0x18(%rbp)
     8ed:       c6 45 e9 63             movb   $0x63,-0x17(%rbp)
     8f1:       c6 45 ea c3             movb   $0xc3,-0x16(%rbp)
     8f5:       c6 45 eb f8             movb   $0xf8,-0x15(%rbp)
     8f9:       c6 45 ec f4             movb   $0xf4,-0x14(%rbp)
     8fd:       c6 45 ed 96             movb   $0x96,-0x13(%rbp)
     901:       c6 45 ee a5             movb   $0xa5,-0x12(%rbp)
     905:       c6 45 ef 2e             movb   $0x2e,-0x11(%rbp)
     909:       48 8b 85 00 ff ff ff    mov    -0x100(%rbp),%rax
     910:       48 8b 40 08             mov    0x8(%rax),%rax
     914:       48 89 85 18 ff ff ff    mov    %rax,-0xe8(%rbp)
     91b:       48 8b 85 18 ff ff ff    mov    -0xe8(%rbp),%rax
     922:       48 89 c7                mov    %rax,%rdi
     925:       e8 86 fd ff ff          callq  6b0 <strlen@plt>

なんか16回movしてそのあとstrlenしている…16という数字があやしいな?

と思いながらトレースをしていたところ、以下の事実を発見した。

$ node trace.js ./box '0' | tail -n 1
821
$ node trace.js ./box '0123' | tail -n 1
821
$ node trace.js ./box '0123456789abcdef' | tail -n 1
821
$ node trace.js ./box '0123456789abcdefg' | tail -n 1
1535
$ node trace.js ./box '0123456789abcdefghi' | tail -n 1
1535
$ node trace.js ./box '0123456789abcdef0123456789abcdef' | tail -n 1
1535
$ node trace.js ./box '0123456789abcdef0123456789abcdef0' | tail -n 1
2249

ここでtrace.jsは、私が適当に書いたトレーサーをラップするスクリプトで、最後にトレースの総分岐数が出てくるのですが、なぜか入力が16文字増えるごとに段階的に分岐数が増える。しかも、トレース結果をみると、同じ分岐回数なら、分岐の内容は一切変わっていない。

16文字の境界を超えるごとに、分岐数は1535-821 == 2249 - 1535 == 714増えるから、つまるところ16*N+1以上16*N+16文字(N >=0)の入力を与えた時、その総分岐数は821+N*714になるというわけです。

さて、与えられたtraceの総分岐数は8675であったから、この式で逆算すると(8675-821)/714 => 11となるわけです。おお、まじか、ぴったり整数じゃん!(ここで嬉しい気分になる。)

というわけで、気軽に16*11+16 => 192文字のファイルを生成して送りつけました。わーい!

box3

box2がさくっと終わったので、どんどんやっていこうーとなった流れで到達したbox3は、めっちゃ楽しかった。だって

$ ./box 
usage: ./box filename

と出たので、適当にtouchしたファイルを食べさせたら

./box empty.txt 


[!] Not implemented: code=0


EAX = 00000000
ECX = 00000000
EDX = 00000000
EBX = 00000000
ESP = 00007c00
EBP = 00007c00
ESI = 00000000
EDI = 00000000
EIP = 00007c00

見慣れたレジスタ名が出てきたんですもの。しかも、0x7c00!!!!!(この嬉しさを理解したい方は30日でできるOS自作入門かIntel SDMでも読んでおいてください。)

これは十中八九エミュレーターだろう、と思ったので、早速NOPを食べさせると

$ echo '90' | xxd -r -p > nop.bin
$ ./box nop.bin 


[!] Not implemented: code=0


EAX = 00000000
ECX = 00000000
EDX = 00000000
EBX = 00000000
ESP = 00007c00
EBP = 00007c00
ESI = 00000000
EDI = 00000000
EIP = 00007c01

たしかにさっきより1バイト進んでから死んでますね。やったね!

どんな命令が実装されているのか特定する

そうきたら、あとはこの子の実装状況と動作のようすを解明してあげるだけです。 最初は、Intel SDM Vol.2のopcode表をみて適当にあたりをつけていたのですが、あまりにもきつかったので方針転換しました。

幸運にもNOPが実装されていることはわかったので、NOPの数を変えてトレースしてみましょう。

トレース結果は長いのですが、着目すべき点はただ一つ: call命令のトレース結果だけです。私のprint.jsでは、call命令の場合はtargetというメンバを記録するようにしているので、それでgrepをかけます。

$ echo '90' | xxd -r -p > nop1.bin
$ echo '90 90' | xxd -r -p > nop2.bin
$ node trace.js ./box nop1.bin | grep target
{"addr":"3b2d","target":"2e44"} * 1
$ node trace.js ./box nop2.bin | grep target
{"addr":"3b2d","target":"2e44"} * 1
{"addr":"3b2d","target":"2e44"} * 1

なるほど…つまるところ、+0x2e44のところがNOPの命令を処理しているようですね。

どうしてcall命令にのみ着目すればいいのかというと、たいていのCPUエミュレータは、動作を高速にするために、入力された命令のバイトを配列の添字として、関数ポインタの配列にアクセスして各処理を呼び出すからです。(作ってみるとわかるこの気持ち。)

というわけで、call命令のtargetを見れば、どの命令が実行されているのかわかりそうですね。

では、求めるべきトレース結果から、どの命令が使われているか抽出してみましょう。とりあえずcall命令だけを抜き出してみると、

$ node print.js box.trace | grep target
{"addr":"3b2d","target":"2ebd"} * 1
{"addr":"3b2d","target":"2ebd"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"3269"} * 1

おー、やはりindirectなcall命令は1箇所しかないんですね。で、このtargetの一意なリストは以下です。

$ node print.js box.trace | grep target | cut -d \" -f 8 | sort | uniq
1ead
2159
2389
28fd
2ebd
317d
3269

さて、ここからどうやって命令オペコードを知ればよいでしょうか。

さきほど言ったように、このエミュレータは命令オペコードをテーブルの添字にすることで関数ポインタを得て、それをcallしているはずです。 では、そのテーブルはどこにあるのか…objdumpをみるとあやしいところを見つけました。

    340b:   55                      push   %rbp
    340c:   48 89 e5                mov    %rsp,%rbp
    340f:   48 83 ec 10             sub    $0x10,%rsp
    3413:   ba 00 08 00 00          mov    $0x800,%edx
    3418:   be 00 00 00 00          mov    $0x0,%esi
    341d:   48 8d 3d 7c 2c 20 00    lea    0x202c7c(%rip),%rdi        # 2060a0 <__cxa_finalize@plt+0x2055f0>
    3424:   e8 f7 d5 ff ff          callq  a20 <memset@plt>
    3429:   48 8d 05 7d ea ff ff    lea    -0x1583(%rip),%rax        # 1ead <__cxa_finalize@plt+0x13fd>
    3430:   48 89 05 71 2c 20 00    mov    %rax,0x202c71(%rip)        # 2060a8 <__cxa_finalize@plt+0x2055f8>
    3437:   48 8d 05 0c eb ff ff    lea    -0x14f4(%rip),%rax        # 1f4a <__cxa_finalize@plt+0x149a>
    343e:   48 89 05 7b 2c 20 00    mov    %rax,0x202c7b(%rip)        # 2060c0 <__cxa_finalize@plt+0x205610>
    3445:   48 8d 05 02 ec ff ff    lea    -0x13fe(%rip),%rax        # 204e <__cxa_finalize@plt+0x159e>
    344c:   48 89 05 c5 2c 20 00    mov    %rax,0x202cc5(%rip)        # 206118 <__cxa_finalize@plt+0x205668>
    3453:   48 8d 05 62 ec ff ff    lea    -0x139e(%rip),%rax        # 20bc <__cxa_finalize@plt+0x160c>
    345a:   48 89 05 87 2d 20 00    mov    %rax,0x202d87(%rip)        # 2061e8 <__cxa_finalize@plt+0x205738>
    3461:   48 8d 05 f1 ec ff ff    lea    -0x130f(%rip),%rax        # 2159 <__cxa_finalize@plt+0x16a9>
    3468:   48 89 05 f9 2d 20 00    mov    %rax,0x202df9(%rip)        # 206268 <__cxa_finalize@plt+0x2057b8>
    346f:   48 8d 05 8b ed ff ff    lea    -0x1275(%rip),%rax        # 2201 <__cxa_finalize@plt+0x1751>
    3476:   48 89 05 fb 2d 20 00    mov    %rax,0x202dfb(%rip)        # 206278 <__cxa_finalize@plt+0x2057c8>
    347d:   48 8d 05 25 ee ff ff    lea    -0x11db(%rip),%rax        # 22a9 <__cxa_finalize@plt+0x17f9>
    3484:   48 89 05 f5 2d 20 00    mov    %rax,0x202df5(%rip)        # 206280 <__cxa_finalize@plt+0x2057d0>
    348b:   48 8d 05 89 ee ff ff    lea    -0x1177(%rip),%rax        # 231b <__cxa_finalize@plt+0x186b>
    3492:   48 89 05 ef 2d 20 00    mov    %rax,0x202def(%rip)        # 206288 <__cxa_finalize@plt+0x2057d8>
    3499:   c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)

何やらばんばんleaして代入してますね。しかも、関数のアドレスっぽいです。もう少し下の方をみると

    3677:   48 8d 05 c6 f7 ff ff    lea    -0x83a(%rip),%rax        # 2e44 <__cxa_finalize@plt+0x2394>
    367e:   48 89 05 9b 2e 20 00    mov    %rax,0x202e9b(%rip)        # 206520 <__cxa_finalize@plt+0x205a70>

NOP命令だとわかっている、0x2e44の関数ポインタを代入しているところをみつけました! どうもこのテーブルの先頭は、ソースの流れ的に

    341d:   48 8d 3d 7c 2c 20 00    lea    0x202c7c(%rip),%rdi        # 2060a0 <__cxa_finalize@plt+0x2055f0>

曰く0x2060a0のようです。では、この予想が正しいか調べてみましょう。

  • NOPのオペコードは0x90
  • NOPの関数ポインタはオフセット0x206520に格納されている
  • ポインタの大きさは8bytes
  • 関数ポインタのテーブルは0x2060a0から始まっている?

関数ポインタのテーブルをop_tableとしたとき、

op_table[0x90] == <+0x2e44のアドレス>

になっていてほしいわけです。これはつまり

*(op_table + 8 * 0x90) == <+0x2e44のアドレス>

というのと等価ですから、格納されるべきアドレスは、テーブルの先頭op_tableから8 * 0x90 == 1152離れているはずです。op_tableを0x2060a0とすれば、その結果は…

0x2060a0 + 8 * 0x90 => 0x206520

ビンゴ!NOPの関数ポインタが代入されているアドレスと一致しますね!!

というわけで、これでテーブルを生成するコードで各関数がテーブルのどのオフセットに格納されているか調べれば、対応するオペコードがわかりそうです。

…とりあえず、テーブル内の各オフセットと対応するオペコードはスクリプトでさくっと生成しました。

[
  [ '2060a8', '1' ],  [ '2060c0', '4' ],
  [ '206118', 'f' ],  [ '2061e8', '29' ],
  [ '206268', '39' ], [ '206278', '3b' ],
  [ '206280', '3c' ], [ '206288', '3d' ],
  [ '2063e0', '68' ], [ '2063f0', '6a' ],
  [ '206420', '70' ], [ '206428', '71' ],
  [ '206430', '72' ], [ '206438', '73' ],
  [ '206440', '74' ], [ '206448', '75' ],
  [ '206460', '78' ], [ '206468', '79' ],
  [ '206480', '7c' ], [ '206490', '7e' ],
  [ '206498', '7f' ], [ '2064b8', '83' ],
  [ '2064e0', '88' ], [ '2064e8', '89' ],
  [ '2064f0', '8a' ], [ '2064f8', '8b' ],
  [ '206508', '8d' ], [ '206520', '90' ],
  [ '2066b8', 'c3' ], [ '2066d8', 'c7' ],
  [ '2066e8', 'c9' ], [ '206708', 'cd' ],
  [ '2067c0', 'e4' ], [ '2067e0', 'e8' ],
  [ '2067e8', 'e9' ], [ '2067f8', 'eb' ],
  [ '206800', 'ec' ], [ '206810', 'ee' ],
  [ '206840', 'f4' ], [ '206898', 'ff' ]
]

そして、あとはobjdumpの結果とIntel SDM Vol.2をじーっと見つめると…

1ead -> 2060a8 -> 0x01  -> ADD Ev,Gv
2159 -> 206268 -> 0x39  -> CMP Ev,Gv
2389                    -> INC r32
28fd -> 206498 -> 0x7f  -> JNLE / JG
2ebd ->                 -> mov r32, imm32
317d -> 2067f8 -> 0xeb  -> short Jb
3269 -> 206840 -> 0xf4  -> HLT

はい!

incとmovに関しては、オペコード内にレジスタエンコーディングされている(つまり、複数のオペコードが同じ操作を表現する)ので、バイナリ中でもループを回して代入されていました。なのでちょっと歯抜けです。(INCとかがオフセットいくつで実装されているかを調べたりして突き止めた。)

さて、あとはprint.jsを拡張して、トレース結果からオペコードを表示してみるか…となったんですが

PROLOGUE                           
mov r32, imm32                     
mov r32, imm32                     
CMP Ev,Gv                          
{"addr":"bdf","taken":false} * 1   
{"addr":"be6","taken":true} * 1    
{"addr":"a20","taken":true} * 1    
{"addr":"c7d","taken":true} * 1    
{"addr":"cbf","taken":true} * 1    
{"addr":"cd6","taken":true} * 1    
{"addr":"d0e","taken":true} * 1                                                                
{"addr":"13a1","taken":false} * 1                                                                                           
{"addr":"13bc","taken":true} * 1
{"addr":"1cb5","taken":false} * 1
{"addr":"1cca","taken":true} * 1
{"addr":"1cf1","taken":true} * 1
{"addr":"1d2d","taken":false} * 1
{"addr":"1d41","taken":true} * 1
{"addr":"1e86","taken":true} * 1 
{"addr":"1d67","taken":true} * 1
{"addr":"21f8","taken":true} * 1                       
JNLE / JG                                                                                                                                                      
ADD Ev,Gv                                                                                                                                                      
INC r32                                                         
...
INC r32
short Jb
CMP Ev,Gv
{"addr":"bdf","taken":false} * 1
{"addr":"be6","taken":true} * 1
{"addr":"a20","taken":true} * 1
{"addr":"c7d","taken":true} * 1
{"addr":"cbf","taken":true} * 1
{"addr":"cd6","taken":true} * 1
{"addr":"d0e","taken":true} * 1
{"addr":"13a1","taken":false} * 1
{"addr":"13bc","taken":true} * 1
{"addr":"1cb5","taken":true} * 1
{"addr":"1cf1","taken":true} * 1
{"addr":"1d2d","taken":true} * 1
{"addr":"1e86","taken":true} * 1
{"addr":"1d67","taken":true} * 1
{"addr":"21f8","taken":true} * 1
JNLE / JG
JNLE / JG taken
HLT->END
444

これはCMP Ev, Gvの分岐列だけベタで、あとは命令の名前で表示してみたんですが、なぜか微妙に長さが違います。考えられるのは…演算結果によって分岐が変わるということです。 CMP命令は、引き算の結果に合わせてフラグレジスタを設定しますから、いかにもありそうなかんじです。また、分岐命令についても分岐列の長さが1命令程度変動する時があり、これは分岐が行われたか否かを示しているようでした。 というわけで、うまくつじつまを合わせるとこんな感じのアセンブリ列をバイナリにして食べさせてあげたトレース結果を投げると(長い)フラグが降ってきました。うれしいね!

.intel_syntax noprefix

mov eax, 1
mov ebx, 5
cmp eax, ebx
jg out
add ecx, edx
inc eax
jmp a
a:
cmp edx, ebx
jg out  # false
add ecx, edx
inc eax
jmp b
b:
cmp edx, ebx
jg out  # false
add ecx, edx
inc eax
jmp d
d:
cmp edx, ebx
jg out  # false
add ecx, edx
inc eax
jmp e
e:
cmp eax, ebx
jg cccc  
cccc:
add ecx, edx
inc eax
jmp g
g:
cmp ebx, edx
jg out  # true
add ecx, edx
inc eax
jmp f
f:
out:
hlt

コンパイルとバイナリの抽出は以下のような感じで。(out.binがおいしいバイナリです。)

gcc -m16 -c -o test.o test.S && objcopy -O binary test.o out.bin

さあ、次もいきましょう!!

box4

さて、次は何かな、と思ったら

$ md5sum box3/box box4/box
d8614ad07b9efbb87a6049bd7b5da1c7  box3/box
d8614ad07b9efbb87a6049bd7b5da1c7  box4/box

同じバイナリじゃないですか!やったね、スクリプトが流用できるよ!

追加の命令列を特定

2c33 -> 2064e8 -> 0x89  -> MOV Ev,Gv
23e7 ->            -> DEC r32
24c3 ->                 -> POP r32
251a ->  2063e0 -> 0x68  -> PUSH lz
2645 -> 206440 -> 0x74  -> JZ/JE
2695 -> 206448 -> 0x75  -> JNZ/JNE
3144 -> 2067e8 -> 0xe9  -> JMP near Jz

かんたんだね!

print.jsを拡張

  • 分岐のtaken/not taken
  • OF(オーバーフローフラグ)の表示を追加

Parser for SECCON 2019 final q4 box4

このスクリプトを、与えられたトレース結果に適用すると、こんなかんじの出力が得られます。

$ node print.js box.trace
PROLOGUE
PUSH imm32
PUSH imm32
PUSH imm32
PUSH imm32
POP r32
POP r32
DEC r32 ZF=false OF=false
MOV r/m32,r32
ADD Ev,Gv
DEC r32 ZF=false OF=false
JNZ/JNE
JNZ/JNE taken?
ADD Ev,Gv
DEC r32 ZF=true OF=false
JNZ/JNE
CMP Ev,Gv ZF=false
JZ/JE
JMP near Jz
POP r32
DEC r32 ZF=false OF=false
MOV r/m32,r32
ADD Ev,Gv
DEC r32 ZF=true OF=false
JNZ/JNE
CMP Ev,Gv ZF=false
JZ/JE
JMP near Jz
POP r32
DEC r32 ZF=false OF=false
MOV r/m32,r32
ADD Ev,Gv
DEC r32 ZF=false OF=false
JNZ/JNE
JNZ/JNE taken?
ADD Ev,Gv
DEC r32 ZF=false OF=false
JNZ/JNE
JNZ/JNE taken?
ADD Ev,Gv
DEC r32 ZF=true OF=false
JNZ/JNE
CMP Ev,Gv ZF=true
JZ/JE
JZ/JE taken
HLT->END
613

もうほとんどアセンブリだね!

入力バイナリを錬成

メモ書き込みですがこんな感じでとけた。

.intel_syntax noprefix

//PUSH lz
//PUSH lz
//PUSH lz
//PUSH lz

.byte 0x68, 0x02, 0x00, 0x00, 0x00
.byte 0x68, 0x02, 0x00, 0x00, 0x00
.byte 0x68, 0x02, 0x00, 0x00, 0x00
.byte 0x68, 0x02, 0x00, 0x00, 0x00

//POP r32
//POP r32
//DEC r32 ZF=false : r32 != 1
//MOV Ev,Gv
//ADD Ev,Gv
//DEC r32 ZF=false : r32 != 1
//JNZ/JNE
//JNZ/JNE taken?

pop edx // edx = 1
pop esi // esi = 1
dec edx // op != 0
mov ecx,edx
add edx,eax
dec esi
jne fake
fake:

//ADD Ev,Gv
//DEC r32 ZF=true : r32 == 1
//JNZ/JNE
//CMP Ev,Gv ZF=false
//JZ/JE
//JMP near Jz

add ecx,ecx
dec esi // op should be 1
jnz c
c:
cmp eax,ecx
jz d
.byte 0xe9, 0x00, 0x00, 0x00, 0x00
d:

//POP r32
//DEC r32 ZF=false
//MOV Ev,Gv
//ADD Ev,Gv
//DEC r32 ZF=true
//JNZ/JNE

pop ebx
dec ebx
mov ecx,ebx
add edi,ecx
dec ebx
jne e
e:

//CMP Ev,Gv ZF=false
//JZ/JE
//JMP near Jz

cmp eax,ecx
jz p
.byte 0xe9, 0x00, 0x00, 0x00, 0x00
p:

//POP r32
//DEC r32 ZF=false
//MOV Ev,Gv
//ADD Ev,Gv
//DEC r32 ZF=false
//JNZ/JNE
//JNZ/JNE taken

pop ebx
dec ebx
mov ecx,ecx
add edi,ecx
dec edi
jne q
q:

//ADD Ev,Gv
//DEC r32 ZF=false
//JNZ/JNE
//JNZ/JNE taken
add edi,ecx
dec edi
jnz m
m:

//ADD Ev,Gv
//DEC r32 ZF=true
//JNZ/JNE
add ecx,ecx
dec ebx
jne n
n:

//CMP Ev,Gv ZF=true
//JZ/JE
//JZ/JE taken
cmp eax,eax
jz s
s:

//HLT->END
hlt

あれ、Defenceポイントはどうしたの?

box1のvariantってことだったので、演算子とかは一緒かなと思っていたのですが、完全に変わっていたのでつらかった。自動化するにはちゃんとファジングとかデコンパイラを活用する必要がありそうだなあという気持ちになりました。強くなりたいです。

他に何をやりましたか?

MimuraのフラッシュをダンプしてFATを読む試みをしたりした。でもうまくいかなかった。st98さんが実機を持って帰ったので朗報を期待している。

Bad mouseをst98さんが解いてくれたのだが、実機を持っていなかったようなので、去年かどこかで配られたのを家に置いてあった私が代わりに実行しました。 マウスが動いてフラグが塗られるのは楽しかった。しかし、待ち時間が長かった…(st98さん曰く、もっとwaitを短くできたらしいのでそうするといいと思います。)

以下、塗られたフラグの実際の画像です。

f:id:hikalium:20191222231359p:plain
FLAG for Bad Mouse

まとめ

問題4はめっちゃ楽しかった。作問者の友利奈緒さん、いい問題をありがとうございます!

坂井さんの問題は、ちょっとやる気が出なかったです。私のバイナリ鍛錬が足りないのも要因ですが、単純にあまり問題がおもしろくなかったのと、ディフェンスポイントの入りかたにゲーム性がないなどの問題もあったと私は思います。来年はアーキの数で殴るタイプではない、面白く解けるマルチアーキテクチャ問題を期待しています…。

とはいえ、全体的には楽しめたのでよかったです。SECCONはSECCONなので!と私は思っています。

運営のみなさま、ありがとうございました。

自作OS開発におけるTips集 〜liumOSの場合〜

これは、自作OS Advent Calendar 2019 の7番目の素数日の記事です。(遅れてごめんなさい!)

はじめに

github.com

liumOSは、2018年の中頃から私が一人で開発している自作OSです。これまでにいくつかの自作OSを作っては壊し続けてきましたが、今回が3作目になります。(蛇足ですが、前作はchnosという名前で、2010-2012年に主に開発していたようです。)

今回は、このliumOS自体の紹介ではなく、開発をしてゆく中で色々と工夫したポイントを紹介したいと思います。

ビルドの依存関係を自動生成する

プロジェクトの規模が大きくなってくると、全ファイルを毎回ビルドしていては時間がかかるようになってきます。 liumOSプロジェクトでは、C++のソース(.cc)とヘッダ(.h)ファイルが合計80個程度あり、これらを毎回ビルドするのはCPU時間の無駄です。 そこで、分割コンパイルにより、変更のないファイルを再度ビルドしないようにする方法がよくとられますが、ソースファイルには変更がなくても、それがincludeしているヘッダファイルに変更があった場合は、やはり再度ビルドする必要があります。そのため、各ソースファイルがどのヘッダをincludeしているのかをMakefileに記述する必要があるのですが、これは人間のやるべきことではありません!ファイル一つ一つの依存関係を列挙するのは面倒ですし、依存関係が変わった際に整合性をとれる保証もありません。

ということで、面倒なことはコンパイラにやらせましょう。

詳細はclangのドキュメントなどをみてもらうことにして、以下ではliumOSの場合を説明します。(ソースはこちら。)

まずは、Makefileにこのようなルールを書いておきます。

%.o.d : %.c Makefile
    @$(LLVM_CC) $(CXXFLAGS_LOADER) -MD -MF $@ -c -o $*.o $*.c >/dev/null 2>&1
    @echo 'DEP $@'

%.o.d : %.cc Makefile
    @$(LLVM_CXX) $(CXXFLAGS_LOADER) -MD -MF $@ -c -o $*.o $*.cc >/dev/null 2>&1
    @echo 'DEP $@'

%.o.d : %.S Makefile
    @touch $@ # generate dummy
    @echo 'DEP $@'

...

ここで、LLVM_CC/CXXはCコンパイラへのパス、CXX_FLAGS_LOADRERは、ローダ用のCFLAGSが入っています。オブジェクトファイルを生成する各ルールのパラメータを少し変えてオブジェクトファイルの名前.dというファイルを生成するルールを書いています。アセンブリソース.Sなど、依存するヘッダがないものはダミーを生成しておきます。

そして、さらに以下のような記述をMakefile最後に書いておきます。

-include $(LOADER_DEPS)
-include $(KERNEL_DEPS)

このLOADER_DEPSには、上で説明した生成規則で生成される*.dのファイルが列挙されています。(acpi.o.d apic.o.d asm.o.d inthandler.o.d ... のような感じです。)

実際には、このような感じでソースコードのリストから生成しています。

COMMON_SRCS= \
             acpi.cc apic.cc asm.S inthandler.S \
             ...

LOADER_SRCS= $(COMMON_SRCS) \
             efimain.cc \
             ...

KERNEL_SRCS= $(COMMON_SRCS) \
             command.cc \
             ...

LOADER_OBJS= $(addsuffix .o, $(basename $(LOADER_SRCS)))
LOADER_DEPS= $(addsuffix .o.d, $(basename $(LOADER_SRCS)))
KERNEL_OBJS= $(addsuffix .elf.o, $(basename $(KERNEL_SRCS)))
KERNEL_DEPS= $(addsuffix .elf.d, $(basename $(KERNEL_SRCS)))

Makeは、このincludeディレクティブをみつけると、C言語のincludeと同じようにそのファイルの内容を書かれた場所に展開しようとするのですが、もしそのファイルが存在しなかった場合、これまで読み込んだ生成規則を適用して、読み込むべきファイルを生成しようとしてくれます。これにより、対象のソースファイルが更新された場合や、依存関係を記したファイルが存在しない場合は、自動的それをmakeしてくれるわけです。

生成される.dファイルの中身は、このような感じになっています。

$ cat acpi.o.d
acpi.o: acpi.cc liumos.h acpi.h apic.h generic.h \
  /usr/local/Cellar/llvm/9.0.0_1/lib/clang/9.0.0/include/stddef.h \
  /usr/local/Cellar/llvm/9.0.0_1/lib/clang/9.0.0/include/__stddef_max_align_t.h \
  third_party_root/include/stdint.h \
  third_party_root/include/machine/_default_types.h \
  third_party_root/include/sys/features.h \
  third_party_root/include/_newlib_version.h \
  third_party_root/include/limits.h third_party_root/include/newlib.h \
  third_party_root/include/sys/cdefs.h \
  third_party_root/include/sys/syslimits.h \
  third_party_root/include/sys/config.h \
  third_party_root/include/machine/ieeefp.h \
  third_party_root/include/sys/_intsup.h \
  third_party_root/include/sys/_stdint.h immintrin.h loader_support.h \
  guid.h asm.h console.h efi.h efi_file.h elf.h \
  third_party_root/include/elf.h gdt.h githash.h hpet.h interrupt.h \
  ring_buffer.h scheduler.h process.h execution_context.h \
  kernel_virtual_heap_allocator.h paging.h stl.h phys_page_allocator.h \
  sys_constant.h pmem.h keyboard.h keyid.h serial.h sheet.h \
  sheet_painter.h text_box.h

ここに書かれた生成規則の依存関係をみて、Makeは実際にacpi.oを生成するかどうか決定してくれます。わーい、これでCPU時間を節約できましたね!

macOSLinuxのどちらでもビルドしたい!

liumOSは、macOSLinuxのどちらでもビルドできるようになっています。これは主に、LLVMツールチェーンが異なるプラットフォーム向けのクロスビルドにデフォルトで対応してくれているおかげなのですが、ツールチェーン自体は対応していても、周辺のライブラリとの兼ね合いで困難な点がいくつかあったので、少し説明したいと思います。

まず、macOS標準のclangは、Appleが少し手を加えているようで、なんとx86_64-pc-win32-coffx86_64-unknown-none-elfなどのターゲット指定に対応していないという悲しい事実があります。また、liumOSではEDK2やgnu-efiなどのUEFI開発環境を用いずに、clang+lldのみでOSのローダを生成しているのですが、macOSにはなんとlldが入っていません!(その代わり、ld64というリンカが入っているようです。)ですから、Homebrew経由でふつうのLLVMツールチェーンを入れる必要があります。

これでツールチェーン自体は揃ったのですが、環境ごとにコンパイラを切り替えなければなりません。そこで、liumOSでは以下のMakefileで、該当するアーキテクチャ向けのツールチェーン情報を取得しています。

$ cat common.mk 
THIS_DIR:=$(dir $(abspath $(lastword $(MAKEFILE_LIST))))

OSNAME=${shell uname -s}

ifeq ($(OSNAME),Darwin)
$(THIS_DIR)cc_cache.gen.mk : $(THIS_DIR)scripts/gen_tool_defs_linux.sh
    @ $(THIS_DIR)scripts/gen_tool_defs_macos.sh > $@
else
$(THIS_DIR)cc_cache.gen.mk : $(THIS_DIR)scripts/gen_tool_defs_linux.sh
    @ $(THIS_DIR)scripts/gen_tool_defs_linux.sh > $@
endif

include $(THIS_DIR)cc_cache.gen.mk
CLANG_SYSTEM_INC_PATH=$(shell $(THIS_DIR)./scripts/get_clang_builtin_include_dir.sh $(LLVM_CXX))

ここで、なぜ直接シェルを叩いてツールチェーンの情報を変数に入れずに、cc_cache.gen.mkなるファイルを生成して読み込んでいるかというと、

$ cat scripts/gen_tool_defs_macos.sh 
LLVM_PREFIX=`brew --prefix llvm`
echo "LLVM_CC:=${LLVM_PREFIX}/bin/clang"
echo "LLVM_CXX:=${LLVM_PREFIX}/bin/clang++"
echo "LLVM_LLD_LINK:=${LLVM_PREFIX}/bin/lld-link"
echo "LLVM_LD_LLD:=${LLVM_PREFIX}/bin/ld.lld"
echo "LLVM_AR:=${LLVM_PREFIX}/bin/llvm-ar"
echo "LLVM_RANLIB:=${LLVM_PREFIX}/bin/llvm-ranlib"

このスクリプト中のbrew --prefix llvmがちょっと重くて、

$ time brew --prefix llvm
/usr/local/opt/llvm

real    0m0.723s
user    0m0.406s
sys 0m0.303s

毎回実行するコストが大きいためです。ビルドするたびに待たされるのは困りますよね?

というわけで、無事各ツールのパスは手に入ったわけですが、もう一つ引っ掛かりどころがあります。それは、stdint.hなどの、コンパイラが提供するヘッダファイルのパスについてです。

C標準ライブラリのうち、stdint.hなどの一部のヘッダは、コンパイラの実装に依存するため、標準ライブラリではなくコンパイラによって提供されます。このヘッダは通常であれば、デフォルトのインクルードパスに含まれているため、気にする必要はないのですが、私たちはOSを書きたいので、-nostdlibinc -nostdlibを設定してしまっています。そうすると、コンパイラが提供するヘッダファイル、つまりはコンパイラさえあれば使えるはずのヘッダファイルが見えなくなってしまい、困ってしまいます。(newlibなども、コンパイラが提供するstdint.hに依存しているため、なんとかしないといけません。)

では、この「コンパイラが提供するヘッダファイル」はどこにあるのかというと…

the default location to look for builtin headers is in a path $(dirname /path/to/tool)/../lib/clang/3.3/include relative to the tool binary. https://clang.llvm.org/docs/LibTooling.html#libtooling-builtin-includes

ということで、わかりづらいのですが、ツールチェインのバイナリが置かれているパスから相対パス../lib/clang/<clangのバージョン>/include にあるようです。

…clangのバージョンがいるの、つらい…。

ということで、シェルスクリプトでよしなにやります。

$ cat scripts/get_clang_builtin_include_dir.sh
#!/bin/bash
if [ "$(uname)" == 'Darwin' ] || [ "$(expr substr $(uname -s) 1 5)" == 'Linux' ]; then
    # macOS, Linux
    version=`$1 --version | head -1 | sed 's/^.*[^0-9] \([0-9]*\.[0-9]*\.[0-9]*\).*$/\1/'`
    basepath="$(dirname $(dirname $(which $1)))"
    echo ${basepath}/lib/clang/${version}/include
else
    echo "Your platform ($(uname -a)) is not supported."
    exit 1
fi

ここで、第一引数にはclangへのパスが入ってきていることを想定しています(上記のcommon.mkを参照)。このようなスクリプトを、以下のように実行すれば、めでたく組み込みヘッダファイルのインクルードパスを得ることができます。

$ ./scripts/get_clang_builtin_include_dir.sh /usr/local/opt/llvm/bin/clang
/usr/local/opt/llvm/lib/clang/9.0.0/include

これを適宜コンパイラに指定してあげれば、無事にstdint.hなどが使えるようになるはずです!

というわけで、「ツールチェーンのパス」と「組み込みヘッダファイルのパス」に気をつければ、macOSLinuxでクロスビルドをすることはそんなに難しくありません。皆さんもぜひお試しください!

まとめ

自作OSは、一人もしくは少人数で作っている場合がほとんどだとは思いますが、その割にソースコードの規模が大きくなりがちです。そのような状況下で、効率よく、ストレスをためずに開発をするためには、今回紹介したような開発環境としての工夫も大事になってきます。 この記事をきっかけに、みなさんの自作OS開発が少しでも効率化・汎用化されれば幸いです。 年末、そして来年も、自作OSを楽しんでいきましょう!

SECCON 2019 Online CTF Writeup

f:id:hikalium:20191020154255p:plain
follow-me

Harekazeの一員として参加しました。4724点を得て14位だったようです。

私は2問に取り組み、うち1問を解けたのでメモ。

follow-me (reversing)

ちょっとした計算機アプリのバイナリが渡される。そのプログラムをIntel Pin を利用したトレーサでトレースした結果と、そのトレーサのソースが与えられる。このトレース結果が同一になるような、アプリケーションへの入力を求めてねという問題。

与えられているトレース結果はこんな感じ。

{"event": "image_load", "image_name": "/home/tomori/follow-me/build/sample/calc", "image_id": 1, "base_addr": "0x55f6b4d44000", "image_size": "0x1377"},
{"event": "image_load", "image_name": "/lib64/ld-linux-x86-64.so.2", "image_id": 2, "base_addr": "0x7f13ae220000", "image_size": "0x26c23"},
{"event": "image_load", "image_name": "[vdso]", "image_id": 3, "base_addr": "0x7ffc2b775000", "image_size": "0x100a"},
{"event": "image_load", "image_name": "/lib/x86_64-linux-gnu/libc.so.6", "image_id": 4, "base_addr": "0x7f1399a39000", "image_size": "0x3f0adf"},
{"event": "branch", "inst_addr": "0x55f6b4d445de", "next_inst_addr": "0", "branch_taken": true},
{"event": "branch", "inst_addr": "0x55f6b4d44f44", "next_inst_addr": "0", "branch_taken": false},
{"event": "branch", "inst_addr": "0x55f6b4d44765", "next_inst_addr": "0", "branch_taken": true},

最初の行のbase_addrと、各分岐結果のinst_addrを差し引きすることで、実行バイナリ内のオフセットがわかる。

h_noson師匠が数秒で入力の文法と分岐の解析結果を与えてくれたので、あとは入力結果を推測するだけという簡単なお仕事。

0-9 (c): val = c - 0x30 + val * 10
,: push val to stack
+: pop twice and push(x + y)
-: pop twice and push(x - y)
*: pop twice and push(x * y)
m: pop twice and push(min(x, y))
M: pop twice and push(max(x, y))
C: pop twice and push(x C y)

たとえば./calc '5,3,+'の結果は8になる。そんなかんじ。 数値は複数桁になることもできて、先頭が0埋めでも問題ないことを確認した。

0xc1c (false): 0-9
0xbe9 (false): ,
0xc58 (false): +
0xcaf (false): -
0xd06 (false): *
0xd5d (false): m
0xdb4 (false): M
0xe08 (false): C

また、演算子による分岐だけでなく、計算時の値によっても分岐結果が変わることがわかった。

乗算は、左辺の値-1回、0xa1fを通る。

r '13,3,*' -> 0xa1fは12回呼ばれる

加算は、(右辺の値%10) + 1回、0xa1fを通る。

r '13,18,+' -> 0xa1fは9回

そして、0xe87の分岐がtrueのときに項を読み続けるので、これを境界としてトレース結果を分割し、上記の結果を総合して推測すればよい。

たとえば、以下のようなトレース列は

e87", "next_inst_addr": "0", "branch_taken": true},
be9", "next_inst_addr": "0", "branch_taken": true},
c1c", "next_inst_addr": "0", "branch_taken": true},
c58", "next_inst_addr": "0", "branch_taken": true},
caf", "next_inst_addr": "0", "branch_taken": true},
d06", "next_inst_addr": "0", "branch_taken": false},
8dc", "next_inst_addr": "0", "branch_taken": true},
8dc", "next_inst_addr": "0", "branch_taken": true},
a5b", "next_inst_addr": "0", "branch_taken": true},
a81", "next_inst_addr": "0", "branch_taken": true},
a0b", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": false},
a81", "next_inst_addr": "0", "branch_taken": false},
93e", "next_inst_addr": "0", "branch_taken": true},
d54", "next_inst_addr": "0", "branch_taken": true},
  • 0xd06の分岐がfalseなので乗算
  • 0xa1fの分岐を7回通っているので、この演算が実行される際の左辺の値は8

ということがわかる。

トレース結果より、入力列は

ccc,ccc,ccc,ccc,ccc,cccc,ccc,mm-mM-ccc,ccc,ccc,mm-ccc,ccc,ccc,ccc,ccc,-+-M+ccc,ccc,ccc,mm*

と予想できる(cは数字が入る)。これは実際に値が1つに収束するのでよさそうである。

加算と乗算に気をつけつつ、後ろ側からいい感じに値を割り当てていく。たとえばこんなかんじに。

001,002,003,004,005,0006,007,mm-mM-001,002,003,mm-008,005,001,004,001,-+-M+001,002,003,mm*

あとは問題の指示通りにサーバーに答えを投げてあげれば、フラグを得ることができた。

{"error":false,"flag":"SECCON{Is it easy for you to recovery input from execution trace? Keep hacking:)}","message":"Thanks! I'll give you a flag as a thank you."}

repair (forensics)

解けなかった…。

問題としては、壊れたAVIファイルが与えられ、その先頭1セクタ(512Bytes)が欠損しているので、なんとかしてその部分(つまりはヘッダ)を復元してねーという話だった。

解析プログラムをささっと書いて、だいたいどんなデータ構造か、フレーム数はいくつかなどを調べて、それっぽいパラメータでffmpegで動画を生成し、先頭512Bytesをつぎはぎするなどしたが、codecが特定できず断念した。

AVI file reader for SECCON 2019 Online CTF

moviリスト内の00dcというチャンクがフレームのデータで、こんな感じで並んでいる。

@+0x00146E: LIST                                                                                     
  size = 2789052                                                                                  
  movi                                                                                               
  @+0x00147A: 00dc                                                                                
    size = 32440                                                                                     
   00 00 7E B8 03 C0 02 1C                                                                        
   00 01 10 00 7E AE 00 00 00 00 02 1C 03 C0 20 00 00 04 22 00 00 0A 00 00 00 00 00 00 32 00 7E 94...
  @+0x00933A: 00dc                                                                                
    size = 4086                                                                                      
   01 00 0F F6 03 C0 02 1C                                                                        
   00 01 11 00 0F EC 00 00 00 00 02 1C 03 C0 20 00 00 04 22 00 00 04 31 00 0F D8 00 00 00 00 00 00...
  @+0x00A338: 00dc                                                                                
    size = 4086                                                                                      
   01 00 0F F6 03 C0 02 1C                                                                        
   00 01 11 00 0F EC 00 00 00 00 02 1C 03 C0 20 00 00 04 22 00 00 04 31 00 0F D8 00 00 00 00 00 00...

各フレームデータの先頭8bytesは以下のようなフォーマットになっているっぽい

     00 00 7E B8 03 C0 02 1C 
     ^^ 0ならキーフレーム, 1なら中間フレーム
           ^^ ^^ ビッグエンディアンでこのフレーム全体のサイズ(00dcのサイズと一緒)
                 ^^ ^^ 960(Width)
                       ^^ ^^ 540(Height)

ということがわかったので、ビッグエンディアンでこういうフォーマットになっているcodecないかなと探したり、ffmpegのcodecを片端から試してこのような出力が得られないか試したが間に合わなかった。かなしい。

参考文献: OpenDML AVI File Format Extensions

まとめ

CTFは生活リズムを破壊する(たのしいので)

あとAVIファイルのフレームデータの区切りがHex上で見えるようになったのでよかった。

技術書典6に初出展したところ300部の新刊が完売した話

2019-04-14, 技術書典6が池袋で開催されました。私は、前回の技術書典5の際に、買いに行く側としての初参加を果たしたのですが、その際「来年は書く側で出しなよ〜」と多数の皆様に煽られ応援されたのでした。

その流れを踏まえ、今回は絶対に書いてやるぞ!という強い意志で、アンケートをとった結果

OS Girlsというタイトルが人々にもっとも望まれているということでしたので、ひとまずサークル参加の応募をしたところ、高倍率の中ではありましたが、運良く参加できることが決まったのでした。

もうこうなったら、何か出さないわけにはいかない(出せなかった場合、もう一生技術書典からbanされてもおかしくない)ので、とにかくやっていくぞという気持ちになれました。

結果、初めての執筆・入稿・販売ということで、ヒヤヒヤしながらではありましたが、なんとなんと用意していた印刷部数のすべて、300部を頒布し尽くすことができました!

というわけで、ここまでの大雑把な流れと、ついさっきまでの当日の様子、反省点などをまとめておきたいと思います。

前日まで

正直言って、進捗は芳しくありませんでした。以下の画像は、執筆リポジトリのCode frequencyのグラフです。

f:id:hikalium:20190414210526p:plain
Code frequency of os-girls

どう見ても、締め切り直前にどかっと書いている様子がわかりますね。

ちなみに、入稿は4/9に行いました。(印刷は日光企画さんにお願いしました。)

元々は、日光企画の技術書典のしめきり表にある「40%OFF」つまり3/27に入稿できたらいいな、とか考えていたのですが、無理でした。ええ、無理は禁物です。

結局、自分はもう真のしめきりがいつだか知っているのだから、それを騙すことはできないのです。ロジックは正直です。

というわけで、滑り込みで入稿して、しかもその日の締め切り時間の数時間前に確認の電話があり

「原稿の本文の一部が完全に崩れていて読めない」

という衝撃的な事実がわかり、SATySFiで出力したものを入稿するなどという冒険をした自分を呪うなどしました。(日光企画さんにはお手数をおかけしました…丁寧な対応でほんと助かりました…)。

とりあえず、Macで「印刷」からpdfをエクスポートし直したものと、最悪のケースに備えて全ページを600dpiのjpgで出力したものを同封して再入稿するなど、バタバタとしたのち、連絡がなくて心配になりついに電話して確認したところ

「いただいたデータで大丈夫でしたので当日お届けいたします!」

と言っていただけて、やっと人心地ついたのでした。

前日準備

さて、これであとは人事を尽くして天命を、というところでしたが、ブースの設営もなにせ初めてでしたので、先人の知恵をインターネットで検索して、必要そうなものをリストアップして急遽買うなどしました。

急遽買ったものとしては、ブックスタンド、おかねを入れる袋、コインケース、透明ブックカバーなどがありました。

あと、現地には電源がないということだったので、大容量のモバイルバッテリーを買うなどしました。(元々欲しかったのでちょうどよかった。)

さらには、前日になってはじめて「500円で頒布するならおつりの500円玉がたくさん必要では?」ということに気づき、焦って1000円を握りしめ、コンビニに走ってアイスを買うなどしました。

ブース環境ともちもの

ブースの環境としては、運営からの注意事項にもあった通り

  • 机半卓(横90センチ×奥行45センチ)椅子2脚
  • Wi-Fiはなし
  • 電源もない
  • 飲食は可能、ごみすて場なし

という状況でした。

持っていったものとしては、

  • hikaliumステッカー全部(400より少し少ないくらいか?)
  • 目玉・ダブルクリップ(テーブルクロス固定等に使う)
  • モバイルバッテリー(スマホ充電用)
  • スケッチブック的ななにか(おしながきや完売表示に)
  • ふせん(価格表示やとりおき表示に)
  • テーブルクロス(みんなやってる)
  • マスキングテープ(テーブルクロスとかブックスタンドを固定できる)
  • 油性マーカ(おしながき書いたり)
  • ノート(おかねの管理等)
  • ブックスタンド(サンプル展示用)
  • ブックカバー(サンプル用)
  • 名刺(あるといいかも)
  • のみもの(水がないと死ぬ)
  • おかね・コインケース・お金を入れる袋(お金はだいじ)

という感じでした。

あと、本体としてのPCとか、通常の装備を持って行きました。

当日

なんとか起床に成功し現着。

本も無事に机の下に配送されていて、ほんと印刷所の方と運営スタッフありがとうという気持ちになった。

ほぼ初めての印刷入稿だったが、想像以上に「数学ガール」感を出せていたのでとてもよかった。マットPP貼り大好き!

そして、ブース設営完了。

(このあと、windholeの風穴さんから、吊るタイプのpopハンガーをお借りして、ブースがさらにパワーアップしました!)

ちなみに、売り子はセキュキャン同期で、かつCERNLLVMを書いていたことで知られているYuka Takahashi氏にお願いしました。ほんとに優秀で超助かりました。ありがとう。popなどはyuka氏が書いてくれました。

技術書典の会場はラッシュ時の中央線並みに混雑し、かつとても広く、出口は1箇所しかないため、会場外に昼食やトイレに行く場合はものすごく時間がかかります。それを考えると、売り子なしの1人でブースを切り盛りするのは不可能です。かならず売り子はだれかにお願いしましょう。

そして、あとは売るだけ。とにかく売る。お金を受け取って商品を渡す。簡単後払いのバーコードを読んでもらって確認画面を見て商品をわたす。それの繰り返しです。

弊ブースでは、現金・かんたん後払い・Pixiv Payの3種の支払い方法に対応していました。

内訳としては、簡単後払いが予想以上に多く、ざっと確認した限りで100名以上の方が利用してくださっていました。

Pixiv payは2名ほどでしたが利用者がおり、それ以外はすべて現金だったようです。

(かんたん後払いアプリ、販売数や金額の統計が見られないのでつらいです。とても便利なアプリなので、その部分を改善していただけるとより使いやすくなると思います!)

現金の支払いについては、Pixiv payのレジ機能で一応カウントしていたのですが、応対が忙しくなるにつれ、入力漏れが増えてきてしまいつらかったです。

当日ネタと終焉

あとは、ステッカーを50枚強奪していく悪いオタクが出現したり(きちんと対価はいただいているのでよいのです)

差し入れをさまざまな方からいただいたり(差し入れてくださった皆さま、ありがとうございました!!)

そうしていたらいつのまにか机の上の在庫だけになり、

そして完売。(ちなみに最後の一冊は、BitNOSのuchanさんが買おうとしていたら、隣のブースの暗黒通信団の方が颯爽とお買い上げしていきました。)

私もまさか完売するとは思っておらず、完全にBOOTH倉庫に直接発送できるサービスを使おうと思っていたのですが、使わずに済んでしまいました。びっくり。

とはいえ、早く売り切れになりすぎることもなく、大幅に売れ残ることもなく、ちょうどよいか少し少ない、といった程度の冊数だったのではないかな、と思います。

ちなみに、この記事を書いている、技術書典終了後の夜のチェック数はこんな感じでした。

f:id:hikalium:20190414215653p:plain

まとめ・反省点

結論としては、本当に最高の1日でした。まさか、こんなにも自分の書いた文章を買ってくださる方がたくさん、しかもリアルワールドに存在するなんて、すごくすごくありがたいことです。

正直、もっと本のクオリティをあげたかったな、というところが最大の反省点に今はなっています。

OSGirlsを読んでくださったみなさまはお気づきかと思いますが、実は結構内容が不足していたり、唐突な終わり方になってしまったりしています。特に、途中で唐突に出てくる elf.hbuild.sh なんて、本のどこを読んでも書いてありません。ええ、これは私の能力不足です。

サポートページへのリンクもつくったのですが、内容がゼロです。本当にすみません。一週間中に充実させます。(少なくとも、本の中でアキとミカが体験したことをできるだけの情報は提示します。)

…とまあ、たいへん穴だらけの作品だったわけですが、それでもみなさんが私に期待して、購入してくださったということがとても嬉しいですし、原動力にもなりました。

秋の技術書典では、もちろん続きを出したいと思います。今度は、さらに盛りだくさんで、充実した内容になるようがんばります。

というわけで、今後も OSGirls は続けて行きたいと思いますので、みなさまどうかよろしくお願いいたします。

デジタルデータ販売

BOOTHにてPDFデータの販売を開始しました。

booth.pm

こちらのデータは、現在は技術書典6で頒布した冊子と完全に同一の内容ですが、今後内容を更新した際には最新の版に更新してゆく予定です。

次の技術書典に向けて応援してくださるみなさまや、物理本を買うことができなかったので内容が気になる方はぜひ購入していただけるとありがたいです。

謝辞

OSGirlsの表紙絵は、私の古くからの友人である @From_boku_To_ 氏に描いていただきました。忙しい中、無理を言って描いてくださってありがとうございました。今後ともよろしくお願いします(笑)。

技術書典6の販売ブースでは, Yuka Takahashi氏にお手伝いいただきました。完璧なオペレーションで私が離席中も一切心配する必要がありませんでした。本当に感謝です。

また、何度か執筆の場を設けてくださったサイボウズの風穴さん( @windhole )にも大いに感謝しています。また執筆会を設けていただけると助かります!

そして、今回の作品の形態のベースとなった「数学ガール」作者の結城浩氏と、私をOSの世界に引き込んでくれた「30日でできる!OS自作入門」作者の川合秀実氏にも深くお礼を申し上げます。ありがとうございました。

次回に向けて

技術書典7でもOSGirlsを出すぞー!!!

f:id:hikalium:20190414223445j:plain

compilium v2 におけるdeclarationの実装

この記事は、C言語 Advent Calendar 2018のうち、3連続素数和が素数になる最小の数番目の記事です。

…といったものの、かなり公開が遅れてしまいました。ごめんなさい…(SECCON国内決勝とかぶったりした&計画性がないのが原因です。)

また、言語実装アドベントカレンダーのほうでもcompiliumに関連する内容の記事を書きましたので興味があればご参照ください。

hikalium.hatenablog.jp

はじめに

Cコンパイラを実装したことのあるみなさんも、変数の宣言や型の宣言を行うdeclarationの実装で詰まってしまった方は多いのではないでしょうか。 この記事では、Cのdeclarationをインクリメンタルにうまく実装する方法について検討した記録と、その実装を一部途中まで進めた話を紹介します。

仕様についてはもう知ってるので説明不要だよ!というプロの皆様は、下の方にある「インクリメンタルに実装しよう!」を読んでいただくと時間の節約になります。

まずはdeclarationについて知る

何はともあれまずは仕様書を読んで、おおまかに仕様を理解します。いくらインクリメンタルに開発するとはいえ、最終的な到達目標をきちんと理解していないことには、途中で立ち行かなくなってしまいますからね。 というわけで、declarationとは一体どのようなものか、仕様書に沿って見ていくことにしましょう。

そもそもdeclarationってなんだ?

仕様書によれば、declarationとは、いくつかのidentifierについてその解釈や属性を与えるもので、具体的には

  • ローカル変数やグローバル変数などの記憶領域を持つオブジェクト
  • 関数
  • 列挙定数
  • typedef名

となるような識別子を宣言するものであると書かれています。というわけで、declarationには必ず名前となる識別子が一つ以上、それに対応する属性もいっしょに書かれていることになります。 (ちなみに、_Static_assertも構文上はdeclarationに入っていてこれは識別子を持たないのですが、実質的にはdeclarationではないのでここでは説明しません。)

declarationの最もトップレベルな構文としては、以下のようになっています。(末尾のoptは省略可能という意味です。)

declaration:
       declaration-specifiers init-declarator-listopt ;
       static_assert-declaration
declaration-specifiers:
       storage-class-specifier declaration-specifiersopt
       type-specifier declaration-specifiersopt
       type-qualifier declaration-specifiersopt
       function-specifier declaration-specifiersopt
       alignment-specifier declaration-specifiersopt
init-declarator-list:
       init-declarator
       init-declarator-list , init-declarator
init-declarator:
       declarator
       declarator = initializer

…といって理解できればみんな困らないので、上の構文をint a = 3, *b;について図示してみたものが以下です。

f:id:hikalium:20181224205850p:plain
declaration int a = 3, *b;

みなさんご存知の通り、int a = 3, *b;を解釈すると、初期値3をもつint型の変数aと、int型へのポインタ変数b、が宣言されますね。

構文的な重要ポイントとしては、

  • declarationdeclaration-specifiersがひとつと、init-declaratorが複数合わさったものであり
  • init-declaratordeclaratorと、任意でinitializerをつけることができる

ということです。とりあえず、最初はinitializerのことは無視することにして、いまここで最も重要なことは

  • declaration-specifiers + declarator でひとつの宣言が出来上がる

ということです。ではdeclaration-specifiersdeclaratorについて見ていくことにしましょう。

declaration-specifiersってなんだ?

上の構文

declaration-specifiers:
       storage-class-specifier declaration-specifiersopt
       type-specifier declaration-specifiersopt
       type-qualifier declaration-specifiersopt
       function-specifier declaration-specifiersopt
       alignment-specifier declaration-specifiersopt

からわかることとしては、なんとかspecifierとか、なんとかqualifierというのが1つ以上並んだものがdeclaration-specifiersです。

type-specifier

たとえば、type-specifierは、よくみるintcharとかunsignedとかのことです。

type-specifier:
        void        
        char        
        short       
        int
        long        
        float       
        double      
        signed      
        unsigned    
        _Bool       
        _Complex    
        atomic-type-specifier
        struct-or-union-specifier
        enum-specifier
        typedef-name

また、これにはstructやunion, enumの型情報も含まれます。つまり、struct KV{const char *key; void *v;}とかはtype-specifier, 中でもstruct-or-union-specifierに含まれるわけです。

さらに、typedefによってつけられた型の別名もここに入ります(typedef-name)。typedefのせいで、C言語のパーサはパースしながらdeclarationを解釈しなくてはいけないのです。まあ、最初は実装しなくてもいいのですが。

enum-specifier

enum E{kKey1 = 3, kKey2} とかのことです。

type-qualifier

constとかvolatileとかです。

function-specifier

inline_Noreturnのことです。

storage-class-specifier

typedefとかexternとかstaticとかのことです。

declaration-specifiersの衝撃の事実

もっと詳しく知りたい方は、仕様書を適当に読んでほしいのですが、面白いネタとしてはこんな話があります。

なんと、上記のspecifierたちは、一部の例外を除いて順序を自由に入れ替えてよいことになっています。したがって、 unsigned long const int long externとか書いても全く問題ないわけです。(人間には厳しいですが。)

declaratorってなんだ?

正直、declaration-specifiersはやるだけです。簡単です。でもこっちのdeclaratorは、少し冷静になってしっかり理解をする必要があります。

まずdeclaratorそのものは単純明快です。

declarator:
      pointeropt direct-declarator

pointer:
      * type-qualifier-listopt
      * type-qualifier-listopt pointer

これは要するに、ポインタの*(とその修飾子列の組)が0個以上並んだあとに、direct-declaratorが続くよ、という意味です。たとえば、int *b;とかなら

f:id:hikalium:20181224215246p:plain
int *b;

という感じになります。この例は、direct-declaratorには識別子が一つだけくるケースになっています。

ところが、direct-declaratorはそう単純ではありません。

declarator:
    pointeropt direct-declarator

direct-declarator:
    identifier
    ( declarator )
    direct-declarator [ type-qualifier-listopt assignment-expressionopt ]
    direct-declarator [ static type-qualifier-listopt assignment-expression ]
    direct-declarator [ type-qualifier-list static assignment-expression ]
    direct-declarator [ type-qualifier-listopt * ]
    direct-declarator ( parameter-type-list )
    direct-declarator ( identifier-listopt )

なんとdirect-declaratorは自身とdeclarator再帰的に含むことができます。 (これはつまり、declaratordeclarator再帰的に含むことができるということです。) したがって、単にdeclaratorと呼んでしまっては、declaratorの全体をさすのか、部分を指すのか分かりづらくなってしまいます。

というわけで、あるdeclarationにおいて、他のどのdeclaratorにも含まれないようなdeclaratorのことを、仕様書の言葉を借りてfull-declaratorと呼ぶことにしましょう。

例としては、

  • int *f(int a, int b);*f(int a, int b)
  • char m[3][4];m[3][4]
  • void (*fp)(int a);(*fp)(int a);

がfull-declaratorにあたります。

declaratorの構文をじっくり見ていただくとわかるのですが、いくらdeclarator入れ子になっても、ひとつのfull-declaratorについて、identifierが現れるのはちょうどひとつになることが分かります。

つまり、declaratorは、宣言の情報のうち

  • ポインタ
  • 配列
  • 関数
  • そしてひとつの識別子(declaratonが定義しようとしている名前)

を表現することがわかります。

declarationの構文を書き下してみる

さて、ここまでの情報をもとに、declarationをもう少しわかりやすい形で書き直してみることにしましょう。

結局のところ、declarationは、なんらかの識別子と、その型や属性をペアにしたものを複数同時に表現する構文なわけです。 なぜ複数になるのかというと、init-declarator-listによって、ひとつのdeclarationの中に複数のfull-declarationが入ることがあるためなのですが、とりあえずひとつの識別子について型や属性を知りたいので、ここでは単純にdeclaration = declaration-specifiers + full-declaratorで構成されると考えて説明します。

まず、declarationの各部分を、以下のような文字でおくことにします。

T: declaration-specifier
D: declarator
P: pointer
E: direct-declaratorの各断片
I: Identifier 

そしてこれらを用いて、各構文を正規表現風に記述するとこんな感じになります。

declaration = TD
D = P*[I|(D)]E*

最もシンプルなケース

たとえば、int a;というdeclarationは、書き下すとTIになります。 int a;を回りくどく書けば、a is_a(int)ですからI(t): Iが識別子Xだとして、X is_a(t) を返すと考えればよさそうです。

ポインタの適用順

次のケースは、ポインタの場合です。たとえば、int * const * p;などを考えてみましょう。 ちなみに、これも回りくどく書けばp is_a(pointer_of(const_pointer_of(int)))となるのはすぐわかるでしょう。 念の為言っておきますと、ポインタ変数そのものは書き換えられますが、1回デリファレンスしたものはconstなポインタ変数になるので書き換えできず、2回デリファレンスしたものはただのint型なので書き換えられます。

さて、説明を容易にするため、PやEについて、左から右に番号を振ることにします。つまり、

declaration = T P_1 P_2 ... [I | (D)] E_1 E_2 ...

という感じです。

このノリでいくと、

int * const * p;
= T P_1 P_2 I

T: int
P_1: * const
P_2: *
I: p

ということになります。

さて、Pは入れ子にできますから、

P(t): pointer_of(t)を返す。(constがついているならconst_pointer_of(t)を返す)

とおくと都合がよさそうです。

この型がp is_a(pointer_of(const_pointer_of(int)))であることを考えると、連続したPは

I(P_2(P_1(T)))
= I(P_2(P_1(int)))
= I(P_2(const_pointer_of(int)))
= I(pointer_of(const_pointer_of(int)))
= p is_a(pointer_of(const_pointer_of(int)))

というように、P_1 P_2 P_3 => ...P_3(P_2(P_1(t)))と評価すればうまくいきそうです。

配列の適用順

じゃあ次は配列いってみましょうか。

たとえば、よくあるint arr[3][5];は、arr is_a(Array(size: 3, type: Array(size: 5, type: int)))という意味です。

ということでE(t): Eがarray declarator [n] ならば、Array(size: n, type: t)を返す。と考えればよさそうです。

適用順としては、 E_1 E_2 E_3 => E_1(E_2(E_3(t)))とすれば、

I(E_1(E_2(T)))
= I(E_1(E_2(int)))
= I(E_1(Array(size: 5, type: int)))
= I(Array(size: 3, type: Array(size: 5, type: int)))
= arr is_a(Array(size: 3, type: Array(size: 5, type: int)))

となってうまくいきそうです。

関数の場合

関数も配列と同じdirect-declaratorに含まれるので、配列の適用順を参考にすれば E(t): Eがfunction declarator (arg1, arg2, ...) ならば、Func(returns: t, args: (arg1, arg2, ...)) を返す。 とすれば、たとえばvoid f(int a);などは

I(E_1(T))
= I(E_1(void))
= I(Func(returns: void, args: (int a))
= f is_a(Func(returns: void, args: (int a))

となってうまくいきそうです。(引数に関しては、declarationを再帰的に適用すれば目的の結果が得られるので今回はそのままにしています。)

ところで、関数を要素とするような配列や、配列・関数を戻り値とするような関数をつくることはできてはならないと仕様書に明記されています。

したがって、Eが関数の場合にE同士がネストするケースをここで紹介することは不可能です。

E, P, (D)|Iの適用順

たとえば、みんな大好き

void (*signal(int sig, void (*func)(int)))(int);

は、書き下すと

T1(P2_1 I2 E2_1)E1_1

となります。そして、ここから導ける型としては

signal is_a(
  Func(
    returns: pointer_of(Func(returns: void, args: (int))),
    args: (int sig, void (*func)(int))
  )
)

となることから、逆に辿って考えてみると、

signal is_a(
  Func(
    returns: pointer_of(Func(returns: void, args: (int))),
    args: (int sig, void (*func)(int))
  )
)
= I2(
  Func(
    returns: pointer_of(Func(returns: void, args: (int))),
    args: (int sig, void (*func)(int))
  )
)
= I2(E2_1(
    pointer_of(Func(returns: void, args: (int)))
))
= I2(E2_1(P2_1(
    Func(returns: void, args: (int))
)))
= I2(E2_1(P2_1(E1_1(
  void
))))
= I2(E2_1(P2_1(E1_1(T))))

となります。つまり、適用順は

T
-> Pの小さい方から大きい方
-> Eの大きい方から小さい方
-> DがあればD
-> I

という順番になるんですね。

インクリメンタルに実装しよう!

お疲れ様でした。長い説明に付き合ってくださりありがとうございました。(理解しづらいところがあればぜひコメントをください。)

では、簡単なケースからインクリメンタルに実装してみましょう!

int a;char c;のようなTI型を処理できるようにする

Tにあたるものとして、BaseTypeという構造体をつくります。 とりあえず、type_specifierひとつだけがBaseTypeだと考えましょう。(int, char, voidとかが表現できるね!)

struct BaseType {
  struct Token *type_specifier;
};

次に、D: declaratorにあたるものとして、Declarator構造体をつくりましょう。 最初は簡単な例としてint a;が表現できればよいので、identifierだけ入れることにしましょう。

struct Declarator {
  struct Token *identifier;
};

これらの組をDeclarationPairとしましょう。

struct DeclarationPair {
  struct BaseType *base_type;
  struct Declarator *decltor;
};

これで、BaseTypeとDeclaratorの組TIの形式で表現できる宣言をDeclarationPairで表現できるようになりました。 パーサは再帰下降法で書くだけなので省略します。

DeclarationPairから作成される、型情報の構造体について考えます。

型情報は統一的にTypeという構造体で表すことにして、

struct Type {
  enum {
      kBaseType,
      kIdentifierAttr,
  } subtype;
  struct BaseType *base_type;
  struct Token *identifier;
  struct Type *next;
}

というふうにしておきます。nextは、pointer_of(t)ident is_a(t)のtにあたるものです。

そしてDeclarationPairからTypeを作るような関数をつくります。

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
  return type;
}

これだけで、ひとまずint a;とかchar c;とかはいけるようになります。やったね!

int **pp;のようなTP*I型を処理できるようにする

つぎは、ポインタに対応しましょう。最初は*constなどのポインタ属性に対応しないと割り切ってしまえば*の個数を数えればいいので、Declaratorに*の個数を格納するメンバを追加します。

struct Declarator {
  int pointer_count;    // new!
  struct Token *identifier;
};

そして、Typeにも型だけ追加しておきます。

struct Type {
  enum {
      kBaseType,
      kIdentifierAttr,
      kPointerType,    // new!
  } subtype;
  struct BaseType *base_type;
  struct Token *identifier;
  struct Type *next;
}

そして、CreateTypeFromDeclarationPair()にコードを追加します。

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  for(int i = 0; i < decl_pair->decltor->pointer_count){  // this loop
    type = AllocAndInitPointerType(type);
  }
  type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
  return type;
}

これで、int **pp;とかが処理できますね!

int *arr[2][3];のようなTP*IE*(Eは配列)を処理できるようにする

ポインタができたら、次は配列ですね。配列は、要素数に整数のみをとると仮定しましょう。

とりあえず、direct-declaratorに対応する構造体をつくります。

struct DirectDeclarator {
  enum {
    kArrayDeclarator,
  } type;
  int size;
}

そして、DirectDeclaratorの列E*を格納するメンバをDeclaratorに追加します。

struct Declarator {
  int pointer_count;
  struct Token *identifier;
  struct List *direct_declarators;  // List of DirectDeclarator
};

ここでは、Listの実装の詳細については述べません。

そして、CreateTypeFromDeclarationPair()にコードを追加します。

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  for(int i = 0; i < decl_pair->decltor->pointer_count){
    type = AllocAndInitPointerType(type);
  }
  for(int i = GetSizeOfList(decl_pair->decltor->direct_declarators); i >= 0; i--) {  // this loop
    struct DirectDeclarator **dd = 
      GetNodeAt(decl_pair->decltor->direct_declarators, i);
    if(dd->type == kArrayDeclarator)
      type = AllocAndInitArrayType(dd->size, type);
  }
  type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
  return type;
}

これで、int *arr[2][3];とかが処理できますね!

int f(int c);のようなTP*IE*(Eは関数)を処理できるようにする

同様にして、関数も処理できるようにしましょう。 とりあえず、direct-declaratorにメンバを追加します。

struct DirectDeclarator {
  enum {
    kArrayDeclarator,
    kFuncDeclarator,  // new!
  } type;
  int size;
  struct List *args;  // new!
}

一応argsもつけましたが、最初はargsは真面目にチェックしなくてよいと思います。また、argsのパースや型情報への変換もここでは扱いません。そんなに難しくないのですぐにできると思います。

そして、CreateTypeFromDeclarationPair()にコードを追加します。かんたんですね!

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  for(int i = 0; i < decl_pair->decltor->pointer_count){
    type = AllocAndInitPointerType(type);
  }
  for(int i = GetSizeOfList(decl_pair->decltor->direct_declarators); i >= 0; i--) {  // this loop
    struct DirectDeclarator **dd = 
      GetNodeAt(decl_pair->decltor->direct_declarators, i);
    if(dd->type == kArrayDeclarator)
      type = AllocAndInitArrayType(dd->size, type);
    if(dd->type == kFuncDeclarator)
      type = AllocAndInitFuncType(type, dd->args);  // here!
  }
  type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
  return type;
}

これでint f(int c);int **f();とかも処理できるんですよ。すごくないですか!

ちなみに、この変換コードでは、先ほど説明したような、関数の戻り値に関数/配列を指定できない、配列の要素型に関数を指定できないというチェックを行なっていません。 チェックを追加するのはとてもかんたんなので、読者への課題とします。(最初はやらなくていいと思いますよ!)

ネストしたdeclaratorに対応する

さて、みんな大好きsignalの定義をパースできるまであともう少しです!ネストしたdeclaratorに対応できれば、表現力はぐっと向上します。

まず、ネストしたdeclaratorを表現できるようにdeclaratorを修正します。

struct Declarator {
  int pointer_count;
  struct Token *identifier;
  struct Declarator *next;  // here!
  struct List *direct_declarators;
};

例によりパーサは書けると思うので省略します。

そして、CreateTypeFromDeclarationPair()から関数を切り出して、ネストにうまく対応できるように準備します。(以下のコードは、一つ前のコードと等価な動作をします)

struct Type *CreateTypeFromDeclarator(struct Declarator *decltor, struct Type *type) {
  for(int i = 0; i < decltor->pointer_count){
    type = AllocAndInitPointerType(type);
  }
  for(int i = GetSizeOfList(decltor->direct_declarators); i >= 0; i--) {
    struct DirectDeclarator **dd = 
      GetNodeAt(decltor->direct_declarators, i);
    if(dd->type == kArrayDeclarator)
      type = AllocAndInitArrayType(dd->size, type);
    if(dd->type == kFuncDeclarator)
      type = AllocAndInitFuncType(type, dd->args);
  }
  return AllocAndInitIdentifierAttr(decltor->identifier, type);
}

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  return CreateTypeFromDeclarator(decl_pair->decltor, type);
}

そして、もしもネストしていたら、再帰的にCreateTypeFromDeclarator()を呼び出すようにします。

struct Type *CreateTypeFromDeclarator(struct Declarator *decltor, struct Type *type) {
  for(int i = 0; i < decltor->pointer_count){
    type = AllocAndInitPointerType(type);
  }
  for(int i = GetSizeOfList(decltor->direct_declarators); i >= 0; i--) {
    struct DirectDeclarator **dd = 
      GetNodeAt(decltor->direct_declarators, i);
    if(dd->type == kArrayDeclarator)
      type = AllocAndInitArrayType(dd->size, type);
    if(dd->type == kFuncDeclarator)
      type = AllocAndInitFuncType(type, dd->args);
  }
  if(decltor->next)
    return CreateTypeFromDeclarator(decltor->next, type);  // here!
  return AllocAndInitIdentifierAttr(decltor->identifier, type);
}

なんとこれだけです!これだけで、あの奇怪なvoid (*signal(int sig, void (*func)(int)))(int);があなたのコンパイラでも綺麗に解釈できるようになったのです!

まとめ

本当はここでcompiliumの実際のコードを貼ることになるはずだったのですが、そちらのほうはちょっと間に合いませんでした。申し訳ないです。(27日までには出したいですね。)

実を言うと、上記のコードはブログの編集画面に直接打ち込んだため、バグやtypo、ロジックのミスなどがあるかもしれません。発見しましたら、どうかそっと教えていただけると助かります。(報告、意見等は大歓迎です!@hikaliumまでお寄せください。)

駆け足になりましたが、これでC言語のdeclarationの半分以上を理解していただけたならば私としても嬉しいですし、コンパイラを書いていてdeclarationの処理で詰まっていた皆様の一助になればいいなと思っております。

ということで、大変遅く&長くなりましたが、これにてひとまずおしまいです。

上の続きとしては、

  • const pointer
  • struct/union
  • enum
  • typedef

などが待ち受けていますが、ここまでできれば比較的簡単にできると思います。(もちろん、落とし穴はたくさんありますが…。)

長々と読んでいただき、ありがとうございました。

来年もよいCコンパイラ自作ライフを楽しみましょう!

参考文献