liumOS 2020年の進化を振り返る

この記事は自作OS Advent Calendar 2020の「最初の4つの素数の和」日目の記事として作成されました。

liumOSについて

liumOSは、NVDIMM(Non-volatile DIMM, 不揮発性メインメモリ)をネイティブにサポートしている、珍しいタイプの自作OSです。2018年7月26日に開発を開始して以来、記事執筆時点で682 commitsを数えるほどに成長しました。主要開発者はhikaliumですが、後述する通り、ここ数ヶ月間はd0iasmさんにも手伝っていただいていました。

2018年には、自作OSからNVDIMMを触る方法について自作OS Advent Calendar 2018の記事で紹介しましたので、NVDIMMについて知らないよという方や、興味のある方はそちらもぜひお読みください。

hikalium.hatenablog.jp

今年は、かなり色々なものをliumOS上に実装して遊んでいたので、この記事ではそのうちのいくつかについて紹介してみたいと思います。

Adlibを利用したMIDI再生機能

これはOSの中核的な機能ではありませんが、デバイスドライバの実装の一環として、Adlibという非常に古いサウンドバイスのドライバを書いて、さらにMIDIファイルのパーサを書いて再生できるようにしました。実は中学生の頃に開発していた自作OSでもMIDIファイルの再生を試みていたことはあるのですが、当時はビープ音で無理やりなんとか和音を出そうとして結局失敗した記憶があり、その当時のMIDIパーサを再利用してN年越しの目標を達成したのでした。

デモ動画はこちらです。(音が鳴るので注意。)


liumOS Adlib MIDI再生デモ

virtio-netドライバの追加とICMP, DHCPへの対応

前菜を楽しんでいただけたところで、メインディッシュですが、なんとliumOSにネットワーク通信機能を追加しました。

たとえば、pingに応答するデモはこちらです。


liumOS pingデモ

冒頭でさらっと流されていますが、なんとDHCPIPアドレスその他が自動的に割り当てられている点にも注目です!

f:id:hikalium:20201217022248p:plain
ipコマンドで割り当てられたIPアドレスを確認している図

NICドライバとしては、仮想入出力デバイスvirtioのうちのひとつである、virtio-netを実装しています。また、GPD Micro PCで採用されているRTL8168というRealtek社製のNICについても現在ドライバの実装を進めているところです。

UDP通信への対応、ソケットシステムコールの部分的実装、簡単なブラウザアプリの実装

さて、pingができるなら、もうなんでもできますね!だって、パケットを送受信するだけですから。(本当に?)

ということで、UDPプロトコルと、ソケット関連システムコールをいくつか実装し、d0iasmさんによって書かれた簡易ブラウザアプリケーションが動くように環境を整備しました。

たとえば、このようにliumOS内のクライアントから、Linux上で動くサーバーにリクエストを投げればHTMLが返ってきますし、

f:id:hikalium:20201217025756p:plain
liumOS内からHTTPのやりとりをしている図

これをパースしてMarkdownに整形するという簡易ブラウザまで動いてしまいます!

f:id:hikalium:20201217025918p:plain
同じHTTPのやりとりだが、出力をパースしてMarkdownに整形して出力している簡易ブラウザの図

どうですか?自作OSでも、これくらいなら少し頑張ればできるんです!

Web+DB Press Vol.120の特集「自作OS×自作ブラウザで学ぶ Webページが表示されるまで」をd0iasmさんと執筆した

さて、このようなことをしていましたら、ありがたいことに技術評論社Web+DB Press編集部よりお声がけをいただき、自作OSと自作ブラウザを通して、Webページが表示されるまでの流れを、文字通り上から下まで一通り追ってゆく記事を執筆させていただく機会を得ました。

gihyo.jp

Webページが表示されるまでに、HTTPのリクエストがどのようにしてパケットにまで落とし込まれて、レスポンスとしてのHTMLがどのようなパスを通って運ばれてゆき、最終的に目に見える形になるのか、ということを解説した、合計36ページの特集となっておりますので、面白そう!と思っていただけたなら、ぜひ書店で内容を確認したり、購入して読んでいただけたりしたら大変嬉しく思います。12/24発売です!

この特集の概要の紹介や、デモを交えた動画を近日中にアップロードする予定ですので、そちらもお楽しみに!

www.youtube.com

今後の展望など

やりたいことは無限にあって永遠に楽しめるのが自作OSのよいところですが、ある程度目標を立てておいたほうが物事を進めやすいのは確かです。ということで、いくつかここで私がやりたいと思っていることを書き連ねておくことにします。

GUIサポートを向上させる

現在のところ、liumOSにはほとんどGUIと呼べるものがありません。画面描画を行うAPIはアプリケーションに対して提供されていませんし、入力インターフェイスについても、ほんの少し前にPS/2マウスのサポートがやっと入ったほどです。そのため、先ほど紹介した特集でも、CUIブラウザを実装するのがやっとの状態でした。

せっかくブラウザの下回りができたなら、CSSで文字を大きく表示したり色を変えたり、なんなら文字列を<blink>させたいですよね?(とはいえblinkタグはすでに廃止されていますが…。)

ということで、ある程度の描画がアプリケーション側からできるような仕組みを近いうちに用意し、ついでにブラウザの実装も拡張したいなあと思っています。

RustでOS本体を書き直す

現在のliumOSはC++で書かれています。C++が使えるだけでもC言語に比べれば大きな進歩だったのですが、やはりメモリ安全性という面ではC言語と五十歩百歩と言わざるを得ません。最近応用が広がってきたRustであれば、より安全にプログラムを書くことができます。ということで、Rustでカーネルを書き直すことを現在検討しています。すでに、Rustで書かれたカーネルを従来のliumOSローダーが起動できるところまでは確認しているため、あとは実装するだけという状況なのですが、うまいことインクリメンタルにできないものか、考えつつ現在進めているところです。(まあ、いつか気分が乗った時にえいやっと書き換えることになりそうな気がしますが…。)

ネットワーク機能の拡張

現在のliumOSのネットワークまわりはかなりアドホックに実装されており、複数のNICをうまく扱えない、ソケットの実装がはりぼてすぎる、たまにドライバがこけるなどの問題が発生しています。特に、ドライバを書くというのは自作OSにとって頭の痛い問題ですが、私としてはネットワークドライバほど実装しておいしいものは他にないのではないかと考えています。というのも、基本的な機能としては「パケットを送信する」「パケットを受信する」の2つしかありませんし、ネットワークの先になにがあるかを私たちは意識する必要がないからです。たとえば、自作OSでファイルを保存できるところまで到達しているケースはかなり少ない(liumOSはNVDIMMに対応しているのでなんでも保存できる!…と言い張ることができるかもしれない)ですが、ネットワーク通信さえ対応してしまえば、保存すべきファイルをネットワーク越しに送信するようにすることで、自作OS側でドライバを書かなくて済む可能性が出てきます。(もちろん、各種プロトコルを実装する必要がありますが…。)あと、自作OS同士が独自のプロトコルで通信するのをみてみたい、という気持ちもかなりあります。ということで、おそらくネットワーク周りの機能はそれなりに重点的に進めていくことになるような気がしています。

おわりに

そういうわけで、今年もいろいろな機能がliumOSには生えましたし、今後も生やしていくつもりではいるのですが、ここで大事なことをひとつ。

自分が楽しいと思えることをやっていきましょう!最初から完璧なものを作る必要はありません。なにせ、一番のユーザーは自分自身なのですから。

自分以外のユーザーが出てきたら、そのときはそのときでまた考えましょう!(なおliumOSにはついにアプリ開発者(@d0iasm)が登場したので、大急ぎでテストを書いたりドキュメントの修正をしたりしていました。もちろんこれも楽しいからやってるんですけどね!)

ということで、このご時世で家にいる時間も多くなってきていると思いますので、皆様ぜひ暖かい部屋でゆっくりしながら、のんびりとした自作OSライフをお楽しみください!ではでは!

SECCON 2020 OnlineCTF writeup -- SCSBX:Reversing

概要

f:id:hikalium:20201011204310p:plain

今年も例年のように、チームHarekazeの一員として出ました。チームの結果は2123点で11位/579チーム(何らかのFLAGを提出したチーム数)でした。 そのうち、私はSCSBX:Reversingを解いて129ポイントを稼ぎました。(st98さんが一人で1552ポイントも稼いでおり目を回しています。)

あと、同じSCSBXをテーマにしたSCSBX:Escapeや、脆弱なkernel moduleの秘孔を突くkstackという問題にも挑戦しましたが、時間内に解くまでにはいたりませんでした。

ということで、挑戦した各問題の解法 or 挑戦のようすを書いておきます。

SCSBX:Reversing

f:id:hikalium:20201011194731p:plain

ソースコードの公開された独自のバイトコード処理系と、それ向けに書かれたアプリケーションのバイナリが与えられています。 そのアプリケーションは、入力がフラグであるか否かを教えてくれるものでした。

$ ./scsbx seccon.bin 
FLAG: hogehoge
Wrong!!

ということで、その処理をみてみれば、どのような入力が期待されているのか、つまりフラグがわかりそうです。ということで、読んでいきましょう。

VMソースコードを読んでみる

ファイルとしてはこんな感じ。

$ ls
Makefile          instr_logic.cpp  main.cpp
instr_arith.cpp   instr_mem.cpp    scsbx.cpp
instr_branch.cpp  instr_sys.cpp    scsbx.hpp

C++で書かれているんですねー。たとえば、scsbx.cppの中をみてみると、

void SCSBX::__cpu_exec(u8 instr)
{
  u32 val;

  switch(instr) {
    /* Memory Operation */
  case INS_PUSH:
    val = *(u32*)(&code[pc+1]);
    __stack_push(val);
    pc += 4;
    break;
  case INS_POP:
    __stack_pop();
    break;
  case INS_DUP:
    __stack_dup();
    break;
  case INS_XCHG:
    __stack_xchg();
    break;
  case INS_LOAD32:
    __mem_load32();
    break;
  case INS_LOAD64:
    __mem_load64();
    break;
  case INS_STORE8:
    __mem_store8();

という感じで、非常に素直に書かれています。

また、DOCS.md というファイルも含まれていたのでみてみると、命令形式についての説明やメモリレイアウトについても書かれていました。めっちゃ親切。

### Instruction
Every instruction except for `push` is 1-byte long.
`push` accepts a 4-byte value to push into the stack.
**SCSBX is proudly open-sourced!**
Check the source code for more details.
0x00000000 +-------------------+
           |                   |
           |     Free Space    |
0x55540000 +-------------------+
           | Machine Code (R-) |
           +-------------------+
           |                   |
           |     Free Space    |
           |                   |
0xfffe0000 +-------------------+
           |     Stack (RW)    |
0xffff0000 +-------------------+  ^^^ user-space ^^^
           |  Guard Page (--)  |
0xffffffff +-------------------+  vvv  VM-space  vvv
           |    VM instance    |
           |        ...        |

とりあえず、PUSH命令以外はすべて1バイトのスタックマシンということがわかったので、さくっとディスアセンブラを書きます。というか、VMソースコードを改造して、オプションを渡したらdisasしてくれるようにしました。その出力がこちら。

$ ./scsbx ../seccon.bin -d
00000000: 20 00001000: push
00000005: 20 DEAD0000: push
0000000A: 62: map
0000000B: 20 00000256: push
00000010: 34: call
00000011: 20 0000020A: push
00000016: 34: call
00000017: 20 47414C46: push
0000001C: 20 DEAD0004: push
00000021: 28: store32
00000022: 20 0000203A: push
00000027: 20 DEAD0008: push
0000002C: 27: store16
0000002D: 20 00000006: push
00000032: 20 DEAD0004: push
00000037: 61: write
00000038: 20 00000040: push
0000003D: 20 DEAD000A: push
00000042: 60: read
00000043: 20 00000008: push
00000048: 20 0000010E: push
...

やっぱりスタックマシンだし長いですね。というわけで、じっとこれを見つめてデコンパイラごっこをします。

私なりのやり方としては、大体以下のような手順を踏みました。

  1. 分岐命令を境に、命令列をブロックに分ける。
  2. 上から辿っていって何をやっているかお気持ちを理解する
  3. 複雑な部分では、スタックを書いて追いながらロジックを推定する

たとえばこんな感じに、スタックの使われ方を書いていったり、

<check_loop()>
/*
[0] k
[1] v
*/
00000135: 20 00000000: push
0000013A: 22: dup
0000013B: 20 00000001: push
00000140: 20 00000001: push
00000145: 23: xchg
00000146: 41: sub
/*
[0] k - 1
[0] k
[1] v
*/
00000147: 20 00000008: push
0000014C: 42: mul
/*
[0] (k - 1) * 8
[0] k
[1] v
*/
0000014D: 20 DEAD000A: push
00000152: 40: add
/*
[0] (k - 1) * 8 + 0xDEAD000A
[0] k
[1] v
*/

...(省略)

00000183: 20 00000001: push
00000188: 23: xchg
/*
[2] k
[0] v | (*p - *q) | (*(p + 4) - *(q + 4))
*/
00000189: 20 00000001: push
0000018E: 20 00000001: push
00000193: 23: xchg
00000194: 41: sub
/*
[2] k - 1
[0] v | (*p - *q) | (*(p + 4) - *(q + 4))
*/

これを元にC言語ベースの擬似コードに落とし込んだりしてみました。

int main(int argc, char *argv) {
  // 00000000
  // map [DEAD0000 - DEAD1000)
  InitEncFlag();
  // 0000020A
  *(uint32_t *)&mem[0] = 0x06D35BCD;
  // 00000017
  // read 0x40 bytes into *0xDEAD000A
  strncpy(&mem[0xA], "SECCON{[\x20-\x7e]+}", 0x40);
  uint32_t i = 8; // pushed at +00000043
  // 0000010E
  // [] i
  while(i) {
    // 0000004E
    // 000000DD
    // Stack after 00000097
    // []: *((8-i) * 8 + 0xDEAD000E) = v1
    // []: *(8-i) * 8 + 0xDEAD000A) = v2
    // []: (8-i) * 8 + 0xDEAD000A
    // []: (8-i) * 8 + 0xDEAD000E
    // []: i
    uint32_t v1 = *((8-i) * 8 + 0xE + mem);
    uint32_t v2 = *((8-i) * 8 + 0xA + mem);
    uint32_t p = 3; // pushed at +00000098
    // 000000DD
    while(p) {
      // 000000A3
      // []: p
      // []: v1
      // []: v2
      p--;
      uint32_t c = v2;
      v2 = v1;
      v1 = random_num(v1) ^ c;
    }
    // 000000F3
    // []: p
    // []: v1
    // []: v2
    // []: (8-i) * 8 + 0xDEAD000A
    // []: (8-i) * 8 + 0xDEAD000E
    // []: i
    *((8-i) * 8 + 0xE + mem) = v1;
    *((8-i) * 8 + 0xA + mem) = v2;
    i--;  // 00000102 - 0000010D
    // 0000010E
  };
  // check if flag_buf is same as flag_encrypted
  ...
}

さて、デコンパイラの気持ちを理解したところで、このプログラムは大体以下のような処理を行っていることがわかりました。

  1. 作業用のメモリ領域[0xDEAD0000 - 0xDEAD1000)をmapする
  2. そのメモリ領域に符号化されたフラグを展開する(0xDEAD004A から0x40バイト)
  3. 0xDEAD0000番地に値0x06D35BCDを格納する(おそらく何らかのシード値、後のロジックで使われる)
  4. ユーザーからの入力を受け取る(0x40バイト、これは0xDEAD000A番地から0x40バイトの空間に格納される)
  5. 上の擬似コードに書いたような処理を行って、ユーザーからの入力を符号化する
  6. 符号化した入力(0xDEAD000Aからの0x40バイト)と、展開しておいた符号化済みのフラグ値(0xDEAD004Aからの0x40バイト)を比較する
  7. それらが一致したらCorrect, 一致しなければWrong!!と出力して終了する

さて、肝心のstep5の処理ですが、擬似コードとしてはこんな感じです。(enc()がその処理)

uint32_t random_num(uint32_t v) {
  // 00000216
  uint32_t *dead0000 = (uint32_t *)&mem[0];
  *dead0000 = (*dead0000 * 0x77F - 0x32A) % 0x0x305EB3EA;
  return ~(v ^ *dead0000);
}
void enc() {
  uint32_t i = 8; // pushed at +00000043
  // 0000010E
  while(i) {
    // 0000004E
    // 000000DD
    uint32_t v1 = *((8-i) * 8 + 0xE + mem);
    uint32_t v2 = *((8-i) * 8 + 0xA + mem);
    uint32_t p = 3; // pushed at +00000098
    // 000000DD
    while(p) {
      // 000000A3
      p--;
      uint32_t c = v2;
      v2 = v1;
      v1 = random_num(v1) ^ c;
    }
    // 000000F3
    *((8-i) * 8 + 0xE + mem) = v1;
    *((8-i) * 8 + 0xA + mem) = v2;
    i--;  // 00000102 - 0000010D
    // 0000010E
  }
}

要するに、8バイトを1セットとして符号化するのを8回くりかえすことで、8*8 = 64 = 0x40バイトの領域を符号化しているわけです。 また、random_num()と仮においた処理は、0xDEAD0000番地のメモリ内容という状態を持っているため、呼び出しには副作用があります。 とはいえ、基本的にやっていることは、その8バイトの中で前後4バイトずつの部分をxorしているだけで、入力と出力は各桁ごとに独立に変化します。 結局、random_num()の状態に注意しつつ、8バイトずつのセットの各文字を順に確定させてゆけば、フラグがわかりそうです。(これなら最大でも256 * 8 * 8通り調べればいけますね。)

というわけで、このアイディアをかんたんなC言語のプログラムに落とし込みました。

#include <stdint.h>
#include <stdio.h>

uint32_t dead0000 = 0x06D35BCD;

uint32_t random_num(uint32_t v) {
  // 00000216
  dead0000 = (dead0000 * 0x77F - 0x32A) % 0x305EB3EA;
  return ~(v ^ dead0000);
}

uint64_t enc(uint64_t v) {
  uint32_t v1 = v >> 32;
  uint32_t v2 = v;
  uint32_t p = 3;  // pushed at +00000098
  while (p) {
    p--;
    uint32_t c = v2;
    v2 = v1;
    v1 = random_num(v1) ^ c;
  }
  return ((uint64_t)v1 << 32) | v2;
}

uint8_t mem[64];

void InitEncFlag() {
  // 00000256
  *(uint32_t *)&mem[4 * 0x0] = 0x46761223;
  *(uint32_t *)&mem[4 * 0x1] = 0x54BEA5C5;
  *(uint32_t *)&mem[4 * 0x2] = 0x7A22E8F6;
  *(uint32_t *)&mem[4 * 0x3] = 0x5DB493C9;
  *(uint32_t *)&mem[4 * 0x4] = 0x055D175E;
  *(uint32_t *)&mem[4 * 0x5] = 0x022FCD33;
  *(uint32_t *)&mem[4 * 0x6] = 0x42C46BE6;
  *(uint32_t *)&mem[4 * 0x7] = 0x6D10A0E8;
  *(uint32_t *)&mem[4 * 0x8] = 0x53F4C278;
  *(uint32_t *)&mem[4 * 0x9] = 0x7279EC2A;
  *(uint32_t *)&mem[4 * 0xA] = 0x5491FB39;
  *(uint32_t *)&mem[4 * 0xB] = 0x49AC421F;
  *(uint32_t *)&mem[4 * 0xC] = 0x49AB3A37;
  *(uint32_t *)&mem[4 * 0xD] = 0x47855812;
  *(uint32_t *)&mem[4 * 0xE] = 0x5718BB05;
  *(uint32_t *)&mem[4 * 0xF] = 0x0540FB5B;
}

int main(int argc, char *argv[]) {
  InitEncFlag();
  char buf[64 + 1] = "SECCON{........";

  for (int i = 0; i < 8; i++) {
    for (int k = 0; k < 8; k++) {
      for (char c = 0x20; c <= 0x7E; c++) {
        buf[k] = c;
        uint32_t prev_dead0000 = dead0000;
        uint64_t e = enc(*(uint64_t *)buf);
        uint8_t *p = (uint8_t *)&e;
        dead0000 = prev_dead0000;
        if (p[k] == mem[k + i * 8]) {
          break;
        }
      }
    }
    uint64_t e = enc(*(uint64_t *)buf);
    printf("%.8s", buf);
  }

  return 0;
}

気をつけるべき点は、forの中でencを実行する際に、毎回dead0000の内容を戻しているところですね。(少し冗長ですが色々ためしていたせいである。)

というわけで、以下のような出力を得ました。

$ ./solve2 
SECCON{TfuRYYVaz8Us696t3JWNxZZPsXEmdL7cCmgzpgxXKarUOnIwhSj9tQ}~~

SECCON{の後にはTがきそう(きっと英語のメッセージ的にTheとかがきそうだから)と思っていて、最初の8桁だけ試してTがでてきてわーいと思っていたのですが、全部出してみたら乱数フラグでちょっと意外でした。(ちゃんと通ってほっとした。)

追記

このアルゴリズムはFeistel構造と呼ばれるものらしい。

ja.wikipedia.org

SCSBX:Escape

ところでこのSCSBX(SecCon SandBoX), reversingだけでなくsandboxの問題としても登場していました。

f:id:hikalium:20201011202618p:plain

こちらは、リモートで動いているSCSBXにいい感じのバイナリを送りつけて、思い通りの動きをさせてshellをゲットしような!という問題だったのだと思います。

SCSBXの説明文にこんな一文がありますが、

### Direct Memory Access
SCSBX allows the program to directly access to the host memory.
This may sound dangerous but the program can only use the 32-bit
address space. Since SCSBX runs on a 64-bit machine with PIE enabled,
there's no way the user can read/write the VM memory directly.

明らかにこれはアヤシイ!と思いますよね。というわけで、じっとソースコードを見つめると、

void SCSBX::__sys_unmap()
{
  u64 address = ((u64)__stack_pop()) & ~0xfff;
  __assert_address_valid(address);

  for(auto itr = memmap.begin(); itr != memmap.end(); ++itr) {
    if (address == itr->first) {
      memmap.erase(itr);
      munmap((void*)address, itr->second);
      return;
    }
  }

  throw MEMORY_ERROR;
}

ほう、munmapの戻り値を確認しないとは勇気がありますね?というところを見つけられます。これは何に役立つかと言うと、メモリマップで言う

0x00000000 +-------------------+
           |                   |
           |     Free Space    |
0x55540000 +-------------------+
           | Machine Code (R-) |
           +-------------------+
           |                   |
           |     Free Space    |
           |                   |
0xfffe0000 +-------------------+
           |     Stack (RW)    |
0xffff0000 +-------------------+  ^^^ user-space ^^^
           |  Guard Page (--)  |
0xffffffff +-------------------+  vvv  VM-space  vvv
           |    VM instance    |
           |        ...        |

Guard Pageを除去するのに使えます。というのも、このGuard Pageは、実際にmapされているわけではなく、

SCSBX::SCSBX(u8 *_code, u32 _size)
{
  /* Guard page */
  memmap.push_back(std::make_pair((u64)STACK_BASE + (u64)STACK_SIZE_INIT,
                                  0x100000000 - (u64)STACK_BASE - (u64)STACK_SIZE_INIT));
}

という感じでVMの初期化時に「確保済みのメモリ領域」として予約されているだけなのです。この結果として、VMはこの領域にアクセスするとマップされていないのでSEGVがおきるし、マップしようにもマップ済みなのでmapを実行できない…はずなのですが、先ほどのようにmunmap命令が実行されると、munmapの結果にかかわらずこのmemmapというリストから除去が行われるため、なんとこの領域をmunmapしてから再度mmapすれば、普通にアクセスできるようになってしまうというバグがあったわけです。

で、ここにアクセスできると何がやばいかというと、Stackが伸びていくとやがてこのGuardPageにあたり、さらにそこを超えるとVM instance、つまりクラスSCSBXのインスタンスが確保されている領域を上書きできてしまうのです。

というわけで、たとえばこうすれば

  // unmap guard page
  instr_push(0xffff0000);
  instr_unmap();
  // map again
  instr_push(0x00010000);
  instr_push(0xffff0000);
  instr_map();

あとはstackをばんばん伸ばすだけでやがてこの構造体を上書きできるようになります。

class SCSBX {
private:
  /* fields */
  std::vector<std::pair<u64, u32>> memmap;

  u32 pc;
  int status;

  u8* code;
  u32* stack;
  u32 code_size;
  u32 capacity;
  u32 top;
...
  virtual void __assert_address_valid(u64 address);
  virtual void __assert_range_valid(u64 address, u64 size);
  virtual void __assert_resource_available(u64 address, u32 size);
...
};

しかもこの構造体、virtual関数としてアドレス範囲チェック系の重要な関数のポインタが記録されている場所でもあるので、ここをいい感じにRETを指すポインタように上書きすれば、チェックを全部回避することも、さらに任意のアドレスに実行を飛ばすこともできます。

…というところまでわかって、時間切れでした。ざんねん。

pythonが得意ではないので、hashのチャレンジレスポンスを解きつつ、ペイロードを突っ込むスクリプトを将来また書かなくてもいいようにここに貼っておきます。

from pwn import *
import itertools
import hashlib
import string
import sys

print(sys.argv[1])
f = open(sys.argv[1], "rb")
attack_bytes = f.read()

table = string.ascii_letters + string.digits + "._"

p = remote('pwn-neko.chal.seccon.jp', 19001)
ret = p.recvline().decode("utf-8") 
# ret = 'sha256("????LFx0jSq8mYA4oZC_.Kuw") = ca67aa308662f39b8e294a99120588102a94

hashval = ret.split("=")[-1].strip()
print(hashval)
suffix = ret.split("\"")[1].replace("?", "")
print(suffix)

for v in itertools.product(table, repeat=4):
    if hashlib.sha256((''.join(v) + suffix).encode()).hexdigest() == hashval:
        prefix = ''.join(v)
        break
else:
    print("[-] Solution not found :thinking_face:")

print("[+] Prefix = " + prefix)
p.sendline(prefix)
p.recvuntil('size')
p.sendline(str(len(attack_bytes)))
p.recvuntil('code')
p.sendline(attack_bytes)
p.interactive()

kstack

f:id:hikalium:20201011204833p:plain

なんか/proc/stackというファイルに対するioctlを生やすkernel moduleが入ったマシンにつながるので、そいつのバグを突いて権限昇格しようね、という問題だったようです。 QEMUで実行できるようイメージと引数の書かれたシェルスクリプトが一緒に配られていて、めちゃくちゃ親切でうれしかったです。

ioctlの仕様としては、ioctl(fd, CMD_PUSH, &value)を発行すると、その値がユーザーランドからカーネル空間のスタック(実体は各要素がkmalloc(GFP_KERNEL)で確保されたLinked List)に格納され、ioctl(fd, CMD_POP, &value)を発行すると、そのカーネル空間のスタックからユーザーランドに値がコピーされていく、というものでした。 ちなみに、そのLinked Listの各要素には、格納したタスクのtgidが一緒に記録されていて、あるtgidが記録したデータに対する操作はそのtgidからしかできないようになっていました。

これについては全然進捗がなくて、複数タスクから同時にPOP処理をかけたら、解放された領域を指し続けるLinked Listが構成できそうとか、pidがぐるっと一周したらどうなる?とか色々あったのですが、結局時間も割けなくてとけませんでした。もっとカーネルに詳しくなりたいですね。

作問者による簡易解説ツイート

感想

バイナリおいしい!あとカーネルむずかしい…。

全体的に、問題のクオリティがかなり上がっているという印象を受けました。とてもよいことだと思います。それに、何より問題を解くのが楽しかったです。(可視化とかも面白かった。)

運営のみなさん本当にお疲れ様でした!ありがとうございましたー!

ISUCON10予選 meguryohikaの記録

ISUCON10の予選にmeguryohikaとして @megumish_unsafe, @systemctl_ryoto と共に出たのでその記録です。

結果としては、初期スコア500点台から、900点台の、1000点に届きそうかな?というところまでは行けたものの、最後のベンチマーク前に複数台構成にしようとして失敗した結果スコアがつかずおしまいでした。来年もまたやりたいですね!

ISUCONは参加者だけじゃなくて運営にも降りかかる…

午前10:00から試合開始ということで、前日は人々とイカをやるのも午前1時までにとどめておき、無事健康的な午前起床を達成しました。

ところが、その少しまえに、こんなツイートが運営から…

ということで、私の目覚める前からISUCONは始まっていたようです。私たちの開始は昼ごろまで遅れたけれど。(運営のみなさんお疲れ様でした!)

正午までの暇を持て余して環境が整う

2時間の余裕を得た我々は、「二度寝するなよ!」というネタをやったり、眠気覚ましにご飯を買いにいく人々が出たりと自由な雰囲気が漂っていました。

私も、あまりにも暇だったので、ちょうど横にあるLinuxマシンを、負荷をかけている際のCPU統計などを表示するのに適したようにセットアップしたいなあという気持ちになって、apt updateしたり、NVIDIAGPUドライバを入れたりしていました。(なんとドライバを入れていなかったので、1024*768の解像度になっていた…これでは流石にきついと思ったので急いでセットアップした。)

そんなわけで、少し環境がリッチになったあたりで、試合開始が12:20からになるとの連絡が。やっていきましょう!

試合開始…からのポータルが503 Service Unavailable

我々はGoで実装を進めるつもりだった&初期実装がGoと書いてあったので、早速ベンチマーカーを回そうとしたところ…なんとポータルが503に。ISUCONむずかしいね…。

というわけで、しばらくベンチマーカーの結果は拝めそうになかったので、megumish氏はソースコードやリソースの退避とデプロイスクリプトの作成を、ryotoさんはbotを弾くnginx configをさっと書いてくれたり、ソースを読んでSQL的にヤバそうなところがないかをしらべてくれたりしていました。私はアプリを実際に触ってみて、遅い部分とか面白い部分がないかをしらべてみていました。「なぞって検索」なる、地図上に領域を描いて物件を検索できるページがあったのにはびっくりしました。また、今回は前回までと異なり、サイトへのログインという概念がなかったため、その点でも度肝を抜かれました。(ついつい/adminが存在しないか調べてしまったが、なかった…。)

14:00の定時報

前回までの反省と、チームでこれまで練習してきたことを生かして、今回は1時間ごとにさくっと進捗共有会をすることにしました。そして、進捗共有がおわったら、強制的に5分間休憩タイムをとることにしていました。これは体力を消耗しないという点では非常によい戦略だったと思います。(今までは終盤になると、精神的にもかなり疲れがきていたのですが、今回は最後までゆったりできたので割とおすすめです。)

このあたりで、megumish氏がデプロイスクリプトを完成させていて、次はredisを入れてキャッシュできるものはやっていこうか、という流れになっていました。 ryotoさんはAPIの各エンドポイントをみ終わって、いくつか修正できそうな点がみつかったので直していく、という話になっていました。

私は、やっと初のベンチを走らせてみて、nginxのログをkataribeでフォーマットしてどのエンドポイントを直すのがよさそうか議論する材料を用意しました。

Top 20 Sort By Total
Count   Total    Mean  Stddev    Min  P50.0  P90.0  P95.0  P99.0    Max  2xx  3xx  4xx  5xx  TotalBytes   MinBytes  MeanBytes   MaxBytes  Request
  105  40.860  0.3891  0.4355  0.046  0.178  1.085  1.397  1.698  2.000  103    0    2    0     1700275          0      16193      33967  POST /api/estate/nazotte HTTP/1.1
  411  33.686  0.0820  0.0246  0.031  0.078  0.115  0.123  0.151  0.206  411    0    0    0     4989248      12139      12139      12153  GET /api/chair/low_priced HTTP/1.1
  411  31.674  0.0771  0.0266  0.032  0.072  0.115  0.127  0.155  0.182  411    0    0    0     5500577      13383      13383      13398  GET /api/estate/low_priced HTTP/1.1
   86  14.241  0.1656  0.0457  0.087  0.157  0.234  0.247  0.271  0.271   86    0    0    0     1429937      16627      16627      16642  GET /api/estate/search?page=0&perPage=25&rentRangeId=1 HTTP/1.1
   67  10.303  0.1538  0.0388  0.093  0.138  0.213  0.223  0.259  0.259   67    0    0    0     1124707      16786      16786      16801  GET /api/estate/search?page=0&perPage=25&rentRangeId=2 HTTP/1.1
   72  10.238  0.1422  0.0348  0.094  0.132  0.194  0.205  0.230  0.230   72    0    0    0     1199601      16660      16661      16682  GET /api/estate/search?page=0&perPage=25&rentRangeId=0 HTTP/1.1

トータルでかかった時間としては、やはり「なぞって検索」が重く、次いで物件と椅子の安い順に上位20件をリストアップするlow_pricedが、一回一回は重くないものの、回数が多いためけっこう負荷になっていることがわかりました。あとは、検索部分が重く、今回のサービスの検索では、かなり多種多様な条件を指定できることがわかっていたので、何らかの高速化が必要だろうね、という話になりました。

例えば、searchで指定する条件には、各物件や椅子の属性(features)というのがあって、これはDBにはカンマ区切りの文字列として格納されているのですが、検索時にはそれらのAND条件を指定できる、というもので、当初の実装では全件リードが走っている状態になっており、まあ重いのは致し方ないかな、という感じでした。

改善のアイディアとしては、featuresの各要素は固定で50件であることから、各属性に対応するboolのカラム50列をDBに追加して、ついでにindexも貼ってあげればいい感じになるんじゃないか?と考えて、以後私はそれに取り組むことにしました。

ちなみに、初期状態でのベンチ終了時点では、データが3万件それぞれのテーブル(chair, estate)に入っており、初期データには2万9500件入っている、ということがわかっていました。なので、実行時に動的に増加する分は、最初は500件ということです。(おそらく、負荷レベルが向上すると、ここが増えたのでしょうが、残念ながらそこまで行きつきませんでした…。)

また、単一サーバー(1 core, 2GB RAM)でDB, Webアプリを同時に動かしている状態でベンチマークをかけても、CPU時間は100%に張り付く一方、メモリ消費量は500MBもいかない程度で、swapも全く発生していないという点に気付きました。かなりCPUに集中した負荷がかかっていたようです。当初、私はこれがMySQLのメモリ設定が厳しすぎるせいだと考えて、緩和する設定を入れてみたのですが、残念ながら全く使用量が増えなかったので、ボトルネックは別の部分にあったようです。

15:00の定期報告

このあたりで、megumish氏はGET chair/low_pricedの結果をキャッシュできないか奮闘していました。

ryotoさんは、全く貼られていなかったindexをDBに貼ったところ、100点程度のスコア向上がみられたと報告していました。

また、なぞって検索に関して、矩形で大まかに物件をフィルタしたあと、その各物件に対して、GIS関連の関数を用いて、描かれたポリゴンの内部にその物件が存在するか否かをチェックしているということがわかり、これをDBに毎回投げるのではなく、Goの側でうまく処理できないかということを検討していました。

私は、先ほど言ったMySQL周りのチューニングが効果ゼロだったことを報告して、もしかするとDBやアプリを複数サーバーに分散させる必要があるのかもしれないと言いつつ、とりあえずfeaturesをbooleanでDBの複数カラムに格納するものに着手するという話になっていました。

16:00の定期報告

megumish氏は、キャッシュの大まかな実装はできたけれど、うまくベンチが通らず四苦八苦していました。

ryotoさんは、椅子を購入すると、物件がrecommendされる(椅子が通るような玄関の間口をもつ家がリコメンドされるシステムだった!)機能のぶぶんを、事前にテーブルを作成することで高速化できないか挑戦していました。

私は、chairのfeaturesをカラム化することを引き続き挑戦していました。

17:00

ほぼ同上。だんだんつらくなってくるね。

f:id:hikalium:20200913000124p:plain
縦に長すぎるchairのschemaの図(実際にはf50まで続いたあと、さらに同じ個数のindexが張られている)

18:00

megumish氏は、キャッシュをするのはいいけれど、レースコンディションがおきたらどうなるんだろう?という問題に頭を悩ませていました。

ryotoさんは、椅子に合った不動産をおすすめする部分の改善目処がつきそうという報告をしており、それが終わり次第、なぞって検索に取り掛かるという目標を掲げていました。

私は、featuresをカラムにし終わったものの、なぜかベンチマークが通らない問題で時間をつぶしていました。(サーバーにデプロイしてみるとうまく動いているように見えた。)

糖分が足りなくなってきたので、ここらへんでクレープをたべました。おいしかったです。

f:id:hikalium:20200912233946j:plain

19:00

megumish氏の実装のバグが取れたとの報告。JSONが正しく吐けていなかったみたい。とりあえずうまくいったら、次は複数台構成の検討に入るとのこと。

ryotoさんは、物件おすすめ機能をあきらめました。というのも、冷静に考えると、事前計算をする処理はかなり重く、また椅子や物件を追加するAPIの時間制限はわりと厳しかったため、時間内に事前計算を終わらせられそうにないというのが理由でした。

今思えば、全部を事前計算せずとも、一度計算したものをキャッシュしておく、などの方策がとれたかもしれないなあ、という感想が浮かんできました。(後から振り返るとそういうアイディアが思いつく。)

私は、クレープの糖分をもってしてもバグを解決できず、なんでだーと頭を抱えていました。

さいご

最後ぎりぎりになって、ryotoさんがなぞって検索のジオメトリ計算の部分をgolangに持ってくることに成功し、これで+300程度になりました。

さらに、私もベンチマークが失敗する理由に気付き(デプロイ時に走るDB初期化と、ベンチマーク時に走るinitialize/内でのDB初期化で異なるデータを流し込んでいた)、なんとかマージに成功。

最終的に、これでスコアが900点ちょい出たのですが、複数台構成を試そうとしてぎりぎりまでryotoさんが頑張ったものの、間に合わず終了時刻を迎えました。いやはや、よくがんばりました…。

反省点

  • 複数台構成を練習時にもあまりできておらず、本番でも手間取って間に合わずじまいになってしまった。練習でできないことは本番でもできないよ!
  • 当初リストアップしていた修正できそうな点のうち、ひとつを見過ごしてしまっていた。(終わった後に気づいた。)
    • 報告会を定期的にしていたのは非常によかったが、ToDoの管理が不十分だった。見ないToDoに意味はないよ!
  • 複数台構成の件にもつながるが、本番サーバー以外に実行環境を用意できていれば、もう少し開発を効率的に行えたかもしれない。

まとめ

来年はさらに準備して望みたい…またがんばりましょう!おつかれさまでした!

f:id:hikalium:20200912235608p:plain
14:30頃のつかの間の15位の図

追記: チームメンバーのryotoさんとツイート被りしていたことが判明(終わるまで全く気づかなかった)(みんな考えることは同じである)

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を楽しんでいきましょう!