自作OSでできる!NVDIMMのつかいかた

これは、自作OS Advent Calendar 2018 の7番目の素数日の記事です。

はじめに

みなさん、NVDIMMって知っていますか?知っている人はぜひ仲良くなりましょうー。

NVDIMMとは、Non-Volatile DIMMの略で、要するにDIMMスロットに刺さる不揮発性の記憶モジュールのことです。 通常のDRAM DIMMは、電源を切るとデータが消えてしまう揮発性の記憶素子なのですが、なんとNVDIMMは電源を切ってもデータが消えません。すごいね!

(NVDIMMの実現方法にはいくつか種類があって…という、NVDIMM自体の細かい話はここではしません。)

さて、自作OSを書いている皆様はよくわかると思うのですが、自作OSで何らかのデータを保存するのはとても大変です。メモリにあるデータは電源を切ると消えてしまいますから、HDDやSSDやSDカードに書き出さないといけません。そうすると、まずはそれらのデバイスのドライバを書かなくてはいけませんし、しかもこれらのデバイスはブロック単位でしか書き込みができませんから、何らかのファイルシステムのような仕組みも用意しなくてはいけません。…大変ですね。

そういうわけで、多くのみなさんはデータを保存する機構を実装せず、電源を切ったらデータは全部消えてしまってもいいという割り切りをすることになります。これはかなしい。

ところが!NVDIMMはCPUからみたとき、メモリとして認識されるので、ドライバなしにCPUから直接読み書きすることができます。つまり、DIMMにマッピングされたアドレスに書いたデータは、起動後もそのまま読み出せるのです!

ということで、この記事では、自作OSでNVDIMMを使うにはどうすればいいかを解説していきます。

検証環境

残念ながら、NVDIMMの実機を個人で買うのはすこしたいへんです。なので、代わりにQEMUのNVDIMMエミュレーションを利用することにします。

利用したバージョンはコミット7c69b7c849をソースビルドしたものです。

QEMU emulator version 3.0.50 (v3.0.0-1143-g7c69b7c849)

コマンドラインオプション

公式ドキュメントは以下にあります。

qemu/docs/nvdimm.txt

これを参考に、QEMUの起動コマンドラインオプションは以下のようにしました。

-bios $(OVMF) \
-machine q35,nvdimm -cpu qemu64 -smp 4 \
-monitor stdio \
-m 8G,slots=2,maxmem=10G \
-drive format=raw,file=fat:rw:mnt -net none \
-object memory-backend-file,id=mem1,share=on,mem-path=pmem.img,size=2G \
-device nvdimm,id=nvdimm1,memdev=mem1

これらのオプションのうち、NVDIMMをエミュレーションする上で重要なポイントは以下の通りです。

  • -machinenvdimm を追加する。
  • -m のサイズはDRAMのサイズを設定する。
    • slots は、(メインのDRAMスロット数+NVDIMMスロット数)に設定する。
      • (今回の場合 1 + 1 = 2)
    • maxmem は、(メインのDRAM容量 + NVDIMMの容量)に設定する。
      • (今回の場合 8G + 2G = 10G)
  • -object-device の組で、ひとつのファイルバックエンドNVDIMMデバイスを作成できる。
    • -objectid と、-devicememdevの値を一致させる。
    • -mem-path にはqemu-imgで作成したデータイメージのパスを指定する。
      • ここでは、qemu-img create pmem.img 2G と実行して作成されたイメージを利用した。
    • -sizeには、上記データイメージ作成時に渡したパラメータと同じサイズを指定する。

また、今回はUEFIを利用するため、-biosにはOVMFのコミットb9cee524e6からビルドしたbiosイメージを指定しています。

Linux以外でのエミュレーションができなかった問題

ちなみに、Linux以外でNVDIMMエミュレーション(正確にはhostmem-file)が正しく動作しない問題があったので、私がパッチを送っておきました。すでにmasterにはマージされているので、最新のQEMUコンパイルしてご利用ください。

https://github.com/qemu/qemu/commit/d5dbde4645fe56a1bcd678f85fa26c5548bcf552

実装の指針

さて、これでエミュレーションの準備は整いました。つぎは実装の計画を立てましょう。

いかにしてNVDIMMのマップされている物理アドレスを取得するか

NVDIMMはメモリバスの配下に接続されているので、物理アドレス空間のどこかにNon-volatileなメモリ空間が生い茂っているはずです。 しかし、私たちはそれがどこにあるのかまだ知りません。知るためにはどうすればよいか…ACPIのNFITを読みます。

ACPI NFIT

ACPI Revision 6.0 より、NFITというPlatform Capabilities Structureが追加されました。 NFITとは、NVDIMM Firmware Interface Table の略です。このテーブルを参照することで、実行中のプラットフォーム上にあるNVDIMMの情報を取得できます。

packed_struct ACPI_NFIT {
  char signature[4];
  uint32_t length;
  uint8_t revision;
  uint8_t checksum;
  uint8_t oem_id[6];
  uint64_t oem_table_id;
  uint32_t oem_revision;
  uint32_t creator_id;
  uint32_t creator_revision;
  uint32_t reserved;
  uint16_t entry[1];
};

今回はそのNFITに含まれる情報の中でも、SPA(System Physical Address) Range Structures に知りたい情報があります。

packed_struct ACPI_NFIT_SYSTEM_PHYSICAL_ADDRESS_RANGE_STRUCTURE {
  uint16_t type;
  uint16_t length;
  uint16_t spa_range_structure_index;
  uint16_t flags;
  uint32_t reserved;
  uint32_t proximity_domain;
  uint64_t address_range_type_guid[2];
  uint64_t system_physical_address_range_base;
  uint64_t system_physical_address_range_length;
  uint64_t address_range_memory_mapping_attribute;
};

話はわかった。ところで、そのNFITっていうのはどうやったら読めるの?

NFITへのポインタは、ACPIのXSDT(eXtended System Descriptor Table)に格納されています。

packed_struct ACPI_XSDT {
  char signature[4];
  uint32_t length;
  uint8_t revision;
  uint8_t checksum;
  uint8_t oem_id[6];
  uint64_t oem_table_id;
  uint32_t oem_revision;
  uint32_t creator_id;
  uint32_t creator_revision;
  void* entry[1];
};

XSDTへのポインタはRSDT(Root System Description Table)に格納されています。

packed_struct ACPI_RSDT {
  char signature[8];
  uint8_t checksum;
  uint8_t oem_id[6];
  uint8_t revision;
  uint32_t rsdt_address;
  uint32_t length;
  ACPI_XSDT* xsdt;           // <<< HERE!
  uint8_t extended_checksum;
  uint8_t reserved;
};

で、このRSDTへのポインタは…EFI Configuration Table にあります。(EFI_ACPI_TABLE_GUIDから引ける。)

というわけで、実際の順番としては

EFIConfigurationTable 
-> ACPI_RSDT 
-> ACPI_XSDT 
-> ACPI_NFIT 
-> SPARangeStructure

と辿っていけば、NVDIMMのマップされているアドレス system_physical_address_range_base がわかるわけです。

実装

さあ、これでもうあとは実装するだけですね!

ということで、実装してみた例がこちらです。

github.com

軽く実装について説明します。

src/liumos.cc のMainForBootProcessor()が、起動後に最初に実行される関数です。

この関数内の、

  ACPI_RSDT* rsdt = static_cast<ACPI_RSDT*>(
      EFIGetConfigurationTableByUUID(&EFI_ACPITableGUID));
  ACPI_XSDT* xsdt = rsdt->xsdt;

という部分で、EFIConfigurationTableからRSDTを取得し、そこからXSDTを取得しています。

そして、以下のようにしてXSDTからNFITを見つけ出し、

  ACPI_NFIT* nfit = nullptr;
  ...
  for (int i = 0; i < num_of_xsdt_entries; i++) {
    const char* signature = static_cast<const char*>(xsdt->entry[i]);
    if (IsEqualStringWithSize(signature, "NFIT", 4))
      nfit = static_cast<ACPI_NFIT*>(xsdt->entry[i]);
   ...
  }

NFITが存在していれば、適当にSPARange structureを見つけ出して、適宜書き込んだり読み込んだりしてみてその結果を表示しています。

 if (nfit) {
    PutString("NFIT found\n");
    PutStringAndHex("NFIT Size", nfit->length);
    PutStringAndHex("First NFIT Structure Type", nfit->entry[0]);
    PutStringAndHex("First NFIT Structure Size", nfit->entry[1]);
    if (static_cast<ACPI_NFITStructureType>(nfit->entry[0]) ==
        ACPI_NFITStructureType::kSystemPhysicalAddressRangeStructure) {
      ACPI_NFIT_SPARange* spa_range = (ACPI_NFIT_SPARange*)&nfit->entry[0];
      PutStringAndHex("SPARange Base",
                      spa_range->system_physical_address_range_base);
      PutStringAndHex("SPARange Length",
                      spa_range->system_physical_address_range_length);
      PutStringAndHex("SPARange Attribute",
                      spa_range->address_range_memory_mapping_attribute);
      PutStringAndHex("SPARange TypeGUID[0]",
                      spa_range->address_range_type_guid[0]);
      PutStringAndHex("SPARange TypeGUID[1]",
                      spa_range->address_range_type_guid[1]);

      uint64_t* p = (uint64_t*)spa_range->system_physical_address_range_base;
      PutStringAndHex("\nPointer in PMEM Region: ", p);
      PutStringAndHex("PMEM Previous value: ", *p);
      (*p)++;
      PutStringAndHex("PMEM value after write: ", *p);

      uint64_t* q = reinterpret_cast<uint64_t*>(page_allocator.AllocPages(1));
      PutStringAndHex("\nPointer in DRAM Region: ", q);
      PutStringAndHex("DRAM Previous value: ", *q);
      (*q)++;
      PutStringAndHex("DRAM value after write: ", *q);
    }
  }

(本当はきちんと見つけ出さなければいけないのですが、QEMUの場合NFIT中の0番目のエントリに運良くSPARangeStructureがあったので手抜きしています。ごめんなさい!)

ね!テーブルをたどるだけの簡単なお仕事でしょ!

実行結果

リポジトリのこのハッシュをクローンしてきてmake runすると、最初にpmem.imgが作成されてからQEMUが起動します。

$ make run
make -C src
make[1]: Nothing to be done for `default'.
qemu-img create pmem.img 2G
Formatting 'pmem.img', fmt=raw size=2147483648
mkdir -p mnt/EFI/BOOT
cp src/BOOTX64.EFI mnt/EFI/BOOT/
qemu-system-x86_64 -bios ovmf/bios64.bin -machine q35,nvdimm -cpu qemu64 -smp 4 -monitor stdio -m 8G,slots=2,maxmem=10G -drive format=raw,file=fat:rw:mnt -net none -object memory-backend-file,id=mem1,share=on,mem-path=pmem.img,size=2G -device nvdimm,id=nvdimm1,memdev=mem1
QEMU 3.0.50 monitor - type 'help' for more information
(qemu)

画面としてはこのような感じになります。

f:id:hikalium:20181217181025p:plain
最初の起動

今回は比較のため、PMEM領域に含まれるアドレスと、DRAM領域に含まれるアドレスにある8バイト整数を起動毎にそれぞれインクリメントしていくように実装しました。

ひとまず最初は、どちらも運良く0で初期化されていたので、それぞれインクリメントしたら1になっていますね。

では、qemuのコンソールにqと打ち込んで終了させ、もう一度make runしてみましょう。

すると…!

f:id:hikalium:20181217231241p:plain
2回目の起動

DRAMとPMEM、どちらも最初の起動時と同じポインタを読み書きしているのですが、DRAMでは最初の起動時にインクリメントした1は忘れ去られてまた0からやりなおしになっている一方、PMEMでは前回のインクリメント結果である1が再起動後も残っていて、今度は2が書き込まれました!

念の為もう一回再起動してみると…

f:id:hikalium:20181217231640p:plain
3回目の起動

やっぱりDRAMはデータが消えてしまっていますが、PMEMは残っていますね!すごい!

まとめ

というわけで、NVDIMMを使えば、自作OSでも簡単にデータを保存して再起動後にも残しておけるということがわかりました! とはいえ今回は簡単な説明しかしておらず、実装は手抜きですし、キャッシュをフラッシュしなければデータが消える可能性があるなど、細かい点で注意しなければならないことが山積みです。

これらを考慮しつつ、liumOSはNVDIMMを有効活用した新しいOSを目指して開発をしてゆきますので、今後にご期待ください!

では皆様、よいOS自作ライフを!

参考文献

編集履歴

  • ACPI SpecおよびUEFI Specについて、最新バージョンを参照するよう参考文献を変更しました。
  • ACPI SpecにNFITが追加されたのは6.2Aではなく6.0からとの指摘を受けましたので、該当箇所を修正しました。

compilium v2 (in progress)の工夫点

この記事は、言語実装アドベントカレンダーの7日目にあたります。

ちなみに、これを書いている現在は2018年12月7日の12:00です。果たして今日中に記事を公開することはできるのでしょうか…。

compilium v2とは

github.com

compiliumは、hikaliumが開発しているC11準拠(予定)のCコンパイラです。C言語で書かれています。

compilium v2では、v1での反省点およびセキュリティ・キャンプ全国大会2018のCコンパイラ自作ゼミでの知見をもとに、よりわかりやすく単純でインクリメンタルに開発できることを目標に開発しています。

この記事では、これらの得られた知見とともに、それらが実際にどのようにcompilium v2に活かされているかを紹介します。

最初からレジスタマシンとしてアセンブリを出力する

当初、Cコンパイラゼミでは、スタックマシンとしてアセンブリを出力するよう受講者のみなさんにお願いしていました。

これは、レジスタ割り当てを最初から考慮するのは大変であり、スタックマシンならばシンプルに実装できるという予想に基づいたものでした。

実際、スタックマシンを採用したことで、式のコード生成については、かなりスムーズに習得してもらうことができました。

一方で、スタックマシンの弱点としては、アセンブリレベルでのデバッグが非常に困難になることが挙げられます。 これは、出力の多くが本質的な計算ではなくpush/popに占められることと、各計算の間で値がどのように伝播するかわかりづらいことが原因でした。

そこで、レジスタマシンの可能性を再考してみたところ、式に閉じたレジスタマシンであれば、複雑な式を与えない限り、単純なコードでもうまく生成でき、出力も自然に近いアセンブリになることがわかりました。

簡単なレジスタマシンの実装

式(Expression)に閉じたレジスタマシン、つまり、異なる式の間で値を引き継いだりしないようなものは容易に実装することができます。 具体的には、値であれば新しくレジスタを確保し、演算子であればその各オペランドに対してレジスタ割り当てを実行したのち、戻り値を戻すためのレジスタ一つをのぞいてすべて解放する、という手順を行えばよいです。

戻り値を戻すためのレジスタとして、演算子の左側のオペランドレジスタを利用することにした場合、2 + 3 * 5は、下の図のように割り当てることができます(R, G, Bはそれぞれレジスタ名です)。

f:id:hikalium:20181207192720g:plain
レジスタ割り当てのようす

実際には、この式は2つのレジスタで計算可能な式(3*5を先に計算すればよい)なのですが、そんなことは気にしたら負けです。 とにかく単純に実装することがcompiliumの目的ですからね!

利用可能なレジスタ

SystemV ABI において、保存せずに破壊しても問題ない汎用レジスタは、以下のものになります。

rax, rcx, rdx, rsi, rdi, r8, r9, r10, r11

このうち、

  • raxは戻り値の格納に使われる
  • rdxはmul, div系で変更される可能性がある(MUL r/m64: RDX:RAX ← RAX ∗ r/m64))
  • rcxはシフト系演算でオペランドとして利用される(シフト系演算のシフト量は、レジスタで指定する場合CLしか使えない)

ことから、単純のため利用しないことにすると、気軽に自由に使えるレジスタ

rsi, rdi, r8, r9, r10, r11

の6つになります。

なぜこれで大体うまくいくのか

f:id:hikalium:20181207200845p:plain
レジスタ割り当ての例

上の図を参照してもらえればわかるように、ASTが右に伸びるほど、必要なレジスタの個数が増えていることがわかります。

ASTが右に伸びるということは、右側のほうを先に計算する必要がある、つまり、右側の演算子の優先順位が高いか、同じ優先順位でも右結合の場合か、もしくはかっこで包まれている場合に限られます。

C言語二項演算子で右結合性のものはassignment-operatorのみであり、これを連続して使うような場合はあまり多くありません。

したがって、優先順位の異なる演算子や括弧をひとつの式の中で多用しないかぎり、このアルゴリズムでも大体うまくいくわけです。

うまくいかなかったらどうするかって?ソースを書き換えちゃいましょう!変数を使えばどんな式もコンパイルできる形に確実に書き直せますよ!

エラーメッセージの改善

compilium v1では、エラー時にその行番号を報告することしかできませんでした。 しかし、式のテストは1行にソースが押し込められてしまうことから、行番号は大して役にたちませんでした。 そこで、compilium v2では、エラー発生時に該当トークンの前後を表示できるように実装されました。

{int *a; return sizeof(a);}
                ^^^^^^
Error: Generate: Not implemented unary prefix op

assignment-expression のパーストリック

assignment-expression:
    conditional-expression
    unary-expression assignment-operator assignment-expression

assignment-expressionが右再帰であることは先ほど触れましたが、右再帰とはいっても単純な右再帰ではありません。 再帰の終端点では conditional-expression が許されるのに対し、再帰途中の左辺には unary-expressionしか許されません。 パーサを書いていて、ここをどう処理するか悩んでいるみなさんも多いのではないでしょうか。(もしかしてみんな悩まない!?)

compilium v2の実装にあたり、この問題の解決策をいくつか考えてみました。

方法1: unary-expressionを先読みする

conditional-expressionは、cast-expressionの場合を除いて、先頭にunary-expressionがくる。

そして、cast-expressionの場合に左側に来る要素はunary-expressionとして認識される可能性がない( type-name ) ので、unary-expressionを先読みして直後にassignment-operatorがくるか調べ、来なければそのunary-expressionを渡しつつconditional-expressionをパースすれば良い。

  • 利点:
    • 文法に沿ったパース結果を得られる
  • 欠点:
    • パーサの一部のみ引数が増える

方法2: 試してみてだめだったら巻き戻す

compilium v1で採用していた方法

  • 利点
    • 文法に沿ったパース結果を得られる
  • 欠点
    • 巻き戻すのはださい(このためだけにTokenStreamの位置を保存しなければいけない)
    • 効率が悪い(2回同じことをすることになる可能性がある)

方法3: conditional-expressionとして読んでから、読んだトークンのクラスを判定する

  • 利点:
    • 文法に沿ったパース結果を得られる
    • パーサの引数の数を統一できる
  • 欠点:
    • ASTのタイプを注意深く設計しなければならない
    • unary-expression以下のASTタイプを新たに実装した際に判定条件に追加しなければならない
      • unary-expression, postfix-expression, primary-expression がunary-expressionに含まれる。

方法4: 単純な右再起になるよう構文を変更してしまう

assignment-expression:
    conditional-expression
    conditional-expression assignment-operator assignment-expression
    ^^^^^^^^^^^^^^^^^^^^^^

9ccで採用されている方法 compilium v2でもこれを採用することにした。

  • 利点:
    • パーサの記述が楽
  • 欠点:
    • 構文にあてはまらない入力をパースできてしまう
      • a+1 = 2 のような構文は本来パースできない
    • ただし意味解析で除去できる(左辺がlvalueかどうかチェックすればよい)
    • 副作用として、条件演算子を左辺値として用いることができるようになる。
      • これはgcc拡張である
      • しかもこの構文はC++ではvalid(つまりこっちのほうが自然)

というわけで、皆さんも方法4を採用するといいと思います!(楽なので)

主要な構造体をTokenとASTNodeのみに集約

compilium v1 では、型がついていないと不安だし、メモリを効率よく使いたいという思いから、ASTの各タイプごとに構造体を用意していました。

しかし、これは機能追加ごとのコード量が増大する要因となり、またほぼ同一内容のコードがソース中に増える原因となりました。

compilium v2 では、思い切ってASTおよび型情報を単一の構造体ASTNodeに押し込めることにしました。

これは、メモリ効率の低下を招きますが、まあ昨今みんなRAMは32GB以上積んでいると思われますので問題ないでしょう…。

(やっぱり無理して書くよりも気楽に書いた方がいいですよ。)

おわりに

本来はもっと真面目にもっと詳細に語りたかったのですが、ちょっと疲れてしまってゆるふわになってしまいました。ごめんなさい…。

特に型の話についてはもう少し語りたいので、12/23のC言語アドベントカレンダーでまた書きたいと思います。

私もコンパイラ初心者なので、何か指摘や質問等あればぜひTwitterのほうまでお願いします!

年内にはv2がセルフホストできるようにがんばりますので、どうか生暖かい目で見守っていてください…。

今年度セキュリティキャンプ2018のCコンパイラゼミに参加してくださったみなさん、そして一緒に講師を担当していただいたRuiさんには、実装方法など様々な面でよい刺激をいただきました。ありがとうございます。

ということで、

みなさんもCコンパイラ書きましょうね?

楽しいぞ!

参考文献

SECCON 2018 Online CTF Writeup

https://score-quals.seccon.jp/team/115

チーム Bluemermaid として参加しました。総合17位、国内6位だったようです。 私がsubmitしたフラグは1つでした。(2つ解けたのだけど、1つは少し前に他の方が解いていた…。はやい。)

解けた問題

Special Device File

毎度おなじみ謎アーキでした。

$ file runme_8a10b7425cea81a043db0fd352c82a370a2d3373 
runme_8a10b7425cea81a043db0fd352c82a370a2d3373: ELF 64-bit LSB executable, ARM aarch64, version 1 (SYSV), statically linked, not stripped

と言ってもaarch64ですが。

まずは毎度おなじみ環境構築をします。私はUbuntu 18.04でやりました。(事前にやっておけ。) 全部のアーキをビルドしていると試合が終わってしまうので、必要なアーキだけtargets.shに書いておくとよいでしょう。

そんなわけで、とりあえずシミュレータで実行してみると

/usr/local/cross2-gcc494/bin/aarch64-elf-run runme_8a10b7425cea81a043db0fd352c82a370a2d3373 

トラップで落ちます。まあきっと未実装なのでしょう。

みんな大好きobjdumpをみてみると、

000000000000140c <__exit>:                           
    140c:       d4200000        .word   0xd4200000   
    1410:       d65f03c0        ret               
                                                      
0000000000001414 <__read>:                           
    1414:       d28000c8        mov     x8, #0x6                        // #6
    1418:       d45e0000        .word   0xd45e0000             
    141c:       d65f03c0        ret                            
                                                    
0000000000001420 <__write>:                           
    1420:       d28000a8        mov     x8, #0x5                        // #5
    1424:       d45e0000        .word   0xd45e0000         
    1428:       d65f03c0        ret                   
                                                     
000000000000142c <__open>:                           
    142c:       d2800028        mov     x8, #0x1                        // #1
    1430:       d45e0000        .word   0xd45e0000    
    1434:       d65f03c0        ret                  
                                                      
0000000000001438 <__close>:                                                  
    1438:       d2800048        mov     x8, #0x2                        // #2    
    143c:       d45e0000        .word   0xd45e0000          
    1440:       d65f03c0        ret                         
    1444:       d503201f        nop                        
    1448:       d503201f        nop                         

こんな感じでたいへん怪しいです。きっと0xd45e0000という命令を実装しないといけないのでしょう。

ここで、シミュレータをトレース付きで実行してみると、

/usr/local/cross-gcc494/aarch64-elf/bin/run --trace-syscall=on  runme_8a10b7425cea81a043db0fd352c82a370a2d3373

どこでこけているのかわかるようになります。

具体的には、cross-gcc494/toolchain/gdb-7.12.1/sim/aarch64/simulator.cの中のhandle_halt関数内です。(このソースは1万5000行くらいあって、ファイル分けてほしかったなあという気持ちになった。)

static void
handle_halt (sim_cpu *cpu, uint32_t val)
{
  ....
  switch (aarch64_get_reg_u32 (cpu, 0, NO_SP))
    {
    case AngelSVC_Reason_HeapInfo:
    ...
    case AngelSVC_Reason_Rename:
    case AngelSVC_Reason_Elapsed:
    default:
      TRACE_SYSCALL (cpu, " HLT [Unknown angel %x]",
         aarch64_get_reg_u32 (cpu, 0, NO_SP));
      sim_engine_halt (CPU_STATE (cpu), cpu, NULL, aarch64_get_PC (cpu),
           sim_stopped, SIM_SIGTRAP);
    }
  aarch64_set_reg_u64 (cpu, 0, NO_SP, result);
}

この関数の下方、AngelSVC_XXXでswitch-caseのdefaultで落ちていました。ということで、適当にここにハンドラを作ってあげればよさそうです。

syscall番号は、先のobjdump disasより、x8レジスタに代入されていることがわかっているので、引数はレジスタ0から入ると仮定していろいろみてみたところ、なんと/dev/xorshift64といういかにもなデバイスをopenしていることがわかりました。 最初のwriteはシードを設定するのでしょう。そして、後続のreadで乱数を取得すると予想できます。 というわけで、こんな感じで書いてみるとよさそうです。

    default:
      {     
        static uint64_t seed = 0;
        uint64_t syscall_id = aarch64_get_reg_u64 (cpu, 8, SP_OK);
        if(syscall_id == 1) {
          uint64_t pathname = aarch64_get_reg_u64 (cpu, 0, SP_OK);
          uint64_t flags = aarch64_get_reg_u64 (cpu, 1, SP_OK);
          uint64_t mode = aarch64_get_reg_u64 (cpu, 1, SP_OK);
          printf("open \n");
          printf("pathname:%s \n", aarch64_get_mem_ptr (cpu, pathname));
          break;
        } else if(syscall_id == 2) {
          printf("close\n");
          break;
        } else if(syscall_id == 5) {
          printf("write\n");
          uint64_t buf = aarch64_get_reg_u64 (cpu, 1, SP_OK);
          uint64_t size = aarch64_get_reg_u64 (cpu, 2, SP_OK);
          printf("buf:%lX \n", buf); 
          printf("size:%lX \n", size);
          seed = aarch64_get_mem_u64 (cpu, buf); 
          printf("seed:%lX \n", seed);
          break;
        } else if(syscall_id == 6) {
          uint64_t buf = aarch64_get_reg_u64 (cpu, 1, SP_OK);
          uint64_t size = aarch64_get_reg_u64 (cpu, 2, SP_OK);
          printf("read\n");
          printf("seed:%lX \n", seed);
          printf("buf:%lX \n", buf); 
          printf("size:%lX \n", size);
          aarch64_set_mem_u64(cpu, buf, xorshift64_2(&seed));
          printf("seed:%lX \n", seed);
          break;
        }     
        printf("not implemented syscall %lX\n", syscall_id);
      }     
      

      TRACE_SYSCALL (cpu, " HLT [Unknown angel %x]",
         aarch64_get_reg_u32 (cpu, 0, NO_SP));
      sim_engine_halt (CPU_STATE (cpu), cpu, NULL, aarch64_get_PC (cpu),
           sim_stopped, SIM_SIGTRAP);

注意しておきたいのは、readは戻り値ではなく、メモリに読み込んだ値を書き込んで返すということです。当たり前なのですが、私はうっかり戻り値に収まる大きさだったので戻り値として乱数を返してしまっており、時間を少し無駄にしました。(そのぶんaarch64のアセンブリを読めるようになったのでよしとしよう)。

ちなみにxorshift64_2は、試行錯誤の結果以下のコードでうまくいきました。(試行錯誤の過程が関数名に現れている。)

uint64_t xorshift64_2(uint64_t *state) {
  uint64_t x = *state;
      x = x ^ (x << 13);
      x = x ^ (x >> 7);
      x = x ^ (x << 17);
      *state = x; 
      return x;
}

xorshiftは、よい周期性をもつシフトパラメータがいくつも存在するので、どれが選ばれるかは実装依存なのですが、このパラメータはxorshiftの論文内で例として用いられていたものでした。

Xorshift RNGs George Marsaglia ∗The Florida State University

余談ですが、論文内のxorshift32の実装例のところに

It uses one of my favorite choices, [a, b, c] = [13, 17, 5]

と書いてあって、めっちゃわかるー、ってなっていました。64bit版もきれいでよい。

まあ、こんな感じでデバイスの実装自体は終わりですが、文字出力のほうも既存のsyscallの実装にかぶっていたのでよしなにしてあげます。(同関数の上方です。)

    case AngelSVC_Reason_Open:
      {
        /* Get the pointer  */
        /* uint64_t ptr = aarch64_get_reg_u64 (cpu, 1, SP_OK);.  */
        /* FIXME: For now we just assume that we will only be asked
           to open the standard file descriptors.  */
        static int fd = 0;
        result = fd ++;

        //TRACE_SYSCALL (cpu, " AngelSVC: Open file %d", fd - 1);
        uint64_t p0 = aarch64_get_reg_u64 (cpu, 0, SP_OK);
        uint64_t p1 = aarch64_get_reg_u64 (cpu, 1, SP_OK);
        uint64_t p2 = aarch64_get_reg_u64 (cpu, 2, SP_OK);
        uint64_t p19 = aarch64_get_reg_u64 (cpu, 19, SP_OK);
        //printf("p0:%lx p1:%lx p2:%lx sp:%lx p19:%lx\n", p0, p1, p2, aarch64_get_reg_u64 (cpu, 31, SP_OK), p19);
        printf ("%c", aarch64_get_mem_u8(cpu, p1));
      }
      break;

(いろいろdeadcodeがありますが気にしないでください。)

これでシミュレータをコンパイルして再度実行してあげるとフラグを得られました。

SECCON{UseTheSpecialDeviceFile}

Special Instructions

これも謎アーキです。cross-gccのサンプルをfileしたときの出力と、与えられたファイルのfileを比較した結果、アーキはmoxieとわかりました。

$ file runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be 
runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be: ELF 32-bit MSB executable, *unknown arch 0xdf* version 1 (SYSV), statically linked, not stripped

*unknown arch 0xdf* いい響きだ。

さて、というわけで適当に実行してみると、

This program uses special instructions.
SETRSEED: (Opcode:0x16)
RegA -> SEED
GETRAND: (Opcode:0x17)
xorshift32(SEED) -> SEED
SEED -> RegA

と出てから、SIGILLで落ちてしまいます。

cross-gcc494/toolchain/gdb-7.12.1/sim/moxie/interp.c にソースがあるので適当に読むと、該当する命令番号にご丁寧にも/*bad*/と書かれているのがわかりました。というわけで、適当に実装しちゃいましょう。

      case 0x16: /* bad */
        {    
          int a = (inst >> 4) & 0xf; 
          xorstate = cpu.asregs.regs[a];
          //printf("SETRSEED(%X)\n", xorstate);
        }    
        break;
      case 0x17: /* bad */
        {    
          int a = (inst >> 4) & 0xf; 
          //printf("GETRAND SEED=%X\n", xorstate);
          cpu.asregs.regs[a] = XorShift(&xorstate);
        }    
        break;

変数 xorstate は適当に関数sim_engine_runの先頭でstatic宣言しておきます。

void
sim_engine_run (SIM_DESC sd,
    int next_cpu_nr, /* ignore  */
    int nr_cpus, /* ignore  */
    int siggnal) /* ignore  */
{
  word pc, opc;
  unsigned short inst;
  sim_cpu *scpu = STATE_CPU (sd, 0); /* FIXME */
  address_word cia = CPU_PC_GET (scpu);
  static int xorstate = 0;

で、問題はxorshiftです。論文で示されているパラメータは64セットあるのですが、十数個試しても引っかかりません。こまった。

というわけで、適当にパラメタ化してソルバを書いてやりました。

int shift_table[9 * 9 * 3] = {
 1, 3,10, 1, 5,16, 1, 5,19, 1, 9,29, 1,11, 6, 1,11,16, 1,19, 3, 1,21,20, 1,27,27,
 2, 5,15, 2, 5,21, 2, 7, 7, 2, 7, 9, 2, 7,25, 2, 9,15, 2,15,17, 2,15,25, 2,21, 9,
 3, 1,14, 3, 3,26, 3, 3,28, 3, 3,29, 3, 5,20, 3, 5,22, 3, 5,25, 3, 7,29, 3,13, 7,
 3,23,25, 3,25,24, 3,27,11, 4, 3,17, 4, 3,27, 4, 5,15, 5, 3,21, 5, 7,22, 5, 9,7 ,
 5, 9,28, 5, 9,31, 5,13, 6, 5,15,17, 5,17,13, 5,21,12, 5,27, 8, 5,27,21, 5,27,25,
 5,27,28, 6, 1,11, 6, 3,17, 6,17, 9, 6,21, 7, 6,21,13, 7, 1, 9, 7, 1,18, 7, 1,25,
 7,13,25, 7,17,21, 7,25,12, 7,25,20, 8, 7,23, 8,9,23 , 9, 5,1 , 9, 5,25, 9,11,19,
 9,21,16,10, 9,21,10, 9,25,11, 7,12,11, 7,16,11,17,13,11,21,13,12, 9,23,13, 3,17,
13, 3,27,13, 5,19,13,17,15,14, 1,15,14,13,15,15, 1,29,17,15,20,17,15,23,17,15,26,
};

uint32_t XorShift(uint32_t *state)
{
  *state ^= *state << shift_table[SHIFT_INDEX * 3 + 0];
  *state ^= *state >> shift_table[SHIFT_INDEX * 3 + 1];
  *state ^= *state << shift_table[SHIFT_INDEX * 3 + 2];
  return *state;
}

SHIFT_INDEXを定義してビルド&実行をぶん回すスクリプトを用意して

for i in {0..80}
do
echo index=$i
touch ~/repo/cross-gcc494/toolchain/gdb-7.12.1/sim/moxie/interp.c && \
        make -s -C ~/repo/cross-gcc494/build/gdb/moxie-elf/sim CFLAGS+="-DSHIFT_INDEX=$i " &> /dev/null && \
        cp ~/repo/cross-gcc494/build/gdb/moxie-elf/sim/moxie/run /usr/local/cross-gcc494/moxie-elf/bin/ && \
        /usr/local/cross-gcc494/moxie-elf/bin/run runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be | grep SECCON && exit
done

実行すると

$ ./solve.sh 
index=0
...
index=74
SECCON{MakeSpecialInstructions}

74番目は...13,17,15でしたね。うつくしい…。

ということで、フラグを得ました。(ところが十数分前にsrupさんがsubmitしていたのでした。きっとソルバを書き始めようとしていた頃でしょう。ちょっとくやしい。)

解けなかった問題

q-escape

megumishさんから教えていただいた

あたりを参考にしつつ、情報収拾をしている段階で時間切れでした。

$ ./qemu-system-x86_64 -device help 2>&1 | grep cydf
name "cydf-vga", bus PCI, desc "Cydf CLGD 54xx VGA"
name "isa-cydf-vga", bus ISA
$ nm qemu-system-x86_64 | grep cydf | grep ' d '
0000000000f5a580 d isa_cydf_vga_properties
0000000000f5a460 d pci_vga_cydf_properties
$ nm qemu-system-x86_64 | grep mmio | grep cydf
000000000068da40 t cydf_mmio_blt_read
000000000068ec70 t cydf_mmio_blt_write
0000000000a99bc0 r cydf_mmio_io_ops
000000000068dd90 t cydf_mmio_read
000000000068f9f0 t cydf_mmio_write
00:02.0 Class 0300: 1234:1111
/ # cat /proc/iomem | grep 00:02.0
  fc000000-fcffffff : 0000:00:02.0
  febc0000-febc0fff : 0000:00:02.0

これはがんばれば解けそうな気がするのでぜひやりたい。

Needle in a haystack

場所の特定はした。大阪の梅田ですね。(「新梅田研修センター」という看板が目立っていた。) 画面中央のビルは実在しなさそうなので怪しかったのですが、動画処理は得意ではないので撤退しました。

まとめ

今回は謎アーキ問題がそんなに多くなかったし、そこまで頭をひねるというわけでもなかったのは少し残念かもしれない。 とはいえ、単純なところで引っかかって時間を無駄にしてしまったり、そもそも準備不足で環境構築に時間を浪費する場面が多かったので、本戦に行く際には改善してゆきたい。 あと風邪を引いてしまったようなので、きちんと休んで回復したい。

運営の皆さん、面白い問題をありがとうございました!

ISUCON8 本戦に出てまあまあだった話

(この記事は本戦後の眠い頭を無理に回して書いています。どうか温かい目で読んであげてください…。)

これまでのあらすじ

前回は、ISUCON8予選に出てガチャを引いたら運良く本戦に行けることになった!という話を書きました。

hikalium.hatenablog.jp

というわけで今回は、本戦でどのようなことをしたのか、そしてその結果などをまとめてゆきたいと思います。

試合開始前

椅子CONではなく机CONだった

開場より少し早く会場に着いてしまったので、エレベーターホールで受付開始まで待っていたのですが、すでにかなりの人数が集まっていたのでびっくり。

入場開始するも、チームメイトのうさぎさん・megumishさんがまだ着いていなかったので、長蛇の列を横目に傍観していた。

列も捌けてきたし、まだ二人が来ないので入場して会場のあるフロアへ。

「机は各チームひとつくらいで」とのことだったので周囲を見回して見たところ、すでにけっこう埋まっていた。

埋まっていないもっとも多くある机は、3人だとちょうどよいか少し肩身がせまいかも、という感じだった。

広めの机はすでに確保されていたし、空いている広い机は椅子に座って作業するには適していない低い机だったので、まあしょうがない。

(もちろんたくさんのチームを招くために場所を確保するのはたいへんだったと思うのでありがたい限りだが、もう少し各チームの机が広かったらうれしいなあと思った。)

ストーリー説明

仮想椅子取引所ISUCOINというこれまた面白そうなテーマの背景ストーリーが説明された。あの人気SNS、ISUBATAと連携!とか、過去問をやっていてわかるネタがあって、良く練られていると感じた。

試合の中身

私はインフラ要員として雇われた感じなので、アプリのアルゴリズムそのものではなく、環境やDB, Webサーバの設定最適化を主に担当した。

環境としては、2cpu, 1G mem のサーバーが4台与えられて、初期状態では各サーバでDB, Webサービス共に動作していた。

目新しかった点は、サービスがDocker内で動いていたということである。Dockerよくわからん!となったので、とりあえず当初は、Dockerからアプリを引き剥がす作業に取り組むことになった。

megumish氏はアプリ本体、私はDBとWebサーバをひっぺがす作業をした。

今回はアプリがHTTPSで動作していたため、当初何も考えずにcertbotで新しくグローバルのドメイン用にLetsEncryptで証明書を取ってきたりしたのだが、なんとベンチマーカはグローバルIPではなくベンチマーカIPを対象にアクセスしており、そのIPにはグローバルのドメインとは別のドメインが割り当てられていたため、証明書エラーでベンチマークが落ちてしまった。これは、よくよくアプリのディレクトリを確認すると、Docker内のnginxが参照していた証明書が置いてあったため、それを証明書として指定してやればうまくいった。(ちょっと時間を無駄にしてしまった。)

同時に、アプリの実装を、デフォルトのgolangからPythonに変更する作業もした。ここまでの作業をしてdstatをつかってなんとなく状況を測定してみたところ、やはりCPUを食いつぶしていたので、次はDBを別サーバに分離することにした。

このあたりだったか、うさぎさんがさくっとLIMIT 1の修正などを追加してくれて、これにより得点が700前後->2000超になった。

https://github.com/kmyk/isucon8-final/pull/6

アプリサーバとDBサーバを分けてからベンチマークを再度かけてみたところ、DBサーバのCPU使用率が高く、律速しているような雰囲気だった。

ここでうさぎさんが、ローソク足の計算を毎回履歴を走査して計算することなく、アプリ起動時にキャッシュするようにすればよいのではないかと気づき実装してくれた。

https://github.com/kmyk/isucon8-final/pull/9

この修正により、ベンチマーク中のDBサーバのCPU利用率は、ベンチ開始時にどかんと上がり、すぐに低くなって低いまま走る、という感じになった。

この、ベンチ開始時に急にCPU利用率が上がるという現象は、今後ロードバランシングする上で問題になりそうだったので、そもそも初期データに対するローソク足の計算は事前にやっておいてテーブルの初期データに挿入しておけばいいという話になり、その変更が入った。

https://github.com/kmyk/isucon8-final/pull/12

これにより、DBの利用率はかなり落ちて、またシェアボタンも確率的に出すようにしたところ( https://github.com/kmyk/isucon8-final/pull/10 )、アプリが律速してきたような印象だったため、ロードバランシングをするようにしてみた。

https://github.com/kmyk/isucon8-final/pull/13

当初は2台でロードバランシングしていたが、それでも1台のサーバに対してベンチマークをかけて2台のサーバのCPU利用率が上がるのは、見ていて非常に楽しかった。

と、ここに来て、連続でベンチを2回走らせると必ず事前チェックでfailするという問題が明らかになり、どうも初期に投入した、settingsのシングルトン化がバグっていたということがわかり、revertするなどした。

megumish氏はこの裏で、ログ送信を即時ではなくキューイングして非同期に行う方法を模索していたのだが、それがなかなかうまくいかずこの辺りでチームの人々に疲れが相当見え始めた。

結局最後は、全4台でアプリサーバをロードバランスしつつ、DBサーバはひとつという構成に落とし込んで、ガチャを回しつつ再起動テストに備える(ただし実際に再起動はしないで最後は祈る)ということをした。

結果

f:id:hikalium:20181020235815p:plain

f:id:hikalium:20181020235848p:plain

明らかに得点が伸び悩んだので、これはかなり厳しい結果だったのではないかと誰もが覚悟していたが、予想に反して全30チーム中12位の最終7475点(途中最高は7752点)、学生チームだけで見れば第4位と、そこまでひどくない成績を残せたようで、チームメンバー一同少し心がやわらぎました。

そして、なんと優勝は学生チームの「最大の敵は時差」で、35312点でした。すごい!おめでとうございます。

社会人チームの「takedashi」は、最大で5万点超えを出していたようですが、再起動後に動作が不調で減点の結果、2位となったようです。残念(でもすごい)。

講評や反省

試合結果発表後、問題作成者による講評があったのですが、DBのパーティションを解除しましたか?したほうが高速だったよ、という話を聞いて、それは気づかなかったなあ、まだまだ勉強が足りないな、と思いました。

また、私がPythonにそんなに慣れていないこともあって直接ロジックの改良に加われなかったこと、非同期処理や排他制御に関する知識の不足、そもそも練習不足なども多くあったなあと、反省する点が多く見つかりました。

もちろん、これまで何度か練習をしたことで得た知見を活かせていた部分もあったので、もっとこれからもいろいろ知識を身につけてゆけばよいのですが。がんばってゆきたい!

感想

  • 高レイヤ、まだまだ知らないことが多すぎる
  • 非同期・マルチスレッドの知識が薄かったので深めたい
  • ISUCON楽しい!

学生生活延長することになったし、来年も本戦に出られるよう精進します。次こそは優勝するぞ!

f:id:hikalium:20181020231226j:plain

ISUCON8の予選に出てみた

概要

  • CTFつながりでうさぎさんに声をかけていただき、megumishさんと3人で参加した。
  • チーム名は「受験生の仇」
  • 13980点で学生枠8位で通過できた。

とにかくうさぎさんのギャンブル運の賜物である。

isucon.net

なにをしたの

基本的にインフラまわりをしていた。

突然のh2oが登場してびっくりするなどした。h2o速いですね。

nginxに慣れていてログ取りとかもこれで用意していたので、最初はnginxに移行することを試みたが、微妙に遅い上にcsvファイルを上手く転送できずよくわからなくてあきらめた。

代わりにh2oのログフォーマットを書き換えて、alpで使えるようになおした。これでやっと定量的にパフォーマンスをみることができるようになった。

あとpythonのプロファイラも事前の練習で出来上がっていたものを使えるようにセットアップしたりしていた。あまり使わなかったけれど。

最初は一台のサーバでWebサーバもDBサーバも動かしていたけれど、htopとかdstatでみていた感じ、メモリが飽和していて苦しそうだったので分けてあげることにした。

分けたことで、DBサーバにメモリをたくさん食べさせてあげることができてDBもうれしそうな悲鳴をあげていた。

初めてMySQLTunerをつかってみた。だいたいはおすすめ通りでいい感じだったが、一部おすすめ通りだとメモリが少なすぎるのかDBが死んだので適宜調整した。

github.com

あとは、アプリ側の小さな修正をしたり、二人のプルリクをレビュー&マージしたり、ロードバランシングできないかなーと試すなどしていた(firewalldさんの存在を忘れかけていて頭をひねっていた)。

最後はみんながベンチを投げた時のDBサーバの負荷を見て「あ、落ちたね」「終わった」とか呟くボットになっていました。

結果

最後にうさぎさんがスロットを回し続けたおかげでなんとか13980点に到達した。最後の賭けが外れていたら本戦には行けていなかった。

一応再起動のことを考えてsystemctlまわりの設定は見直していたものの、追試で落ちないことを祈り続けていた。祈るだけじゃなくて検証したいものですね。

感想

運良く本戦に行けることになったので、次は実力で勝負したいところ。

バイナリ問が出るといいなー。(これはCTFではない。)

あと、学生チームが強い。(昨年同じチームで出て予選敗退した人が今回別のチームで出ていたのだが、我々よりずっと高得点を叩き出していて、学生なのに普通の枠で通過しており、さすがだと思った。)

みなさまどうかお手柔らかにお願いいたします…。

チームメンバーの参加記

kimiyuki.net

思い立っておうちネットワークにdnsmasqを建てた話

概要

  • ホストとipの結びつきや、固定ipの利用状況の管理が ~/.ssh/config 頼りだったので改善したかった
  • とりあえず善は急げでdnsmasqを建てた
  • Ubuntu 18.04ではsystemd-resolvedが53をLISTENしていて手間取った

環境

$ cat /etc/lsb-release 
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=18.04
DISTRIB_CODENAME=bionic
DISTRIB_DESCRIPTION="Ubuntu 18.04 LTS"

動機

ふとRaspberry pi で遊びたくなったんです。そんな日もありますよね。

IPアドレスどれにしていたかなーと思いつつ、WiresharkDHCPのパケットを見張って特定して無理やりSSHするなどして、とりあえずアクセスはできました。

あとのことも考えて、そうだIPアドレスを固定しようと思った時に、気づいたわけです。

「どのアドレスが空いてるんだっけ?」

まあ、手元の端末の ~/.ssh/configを参照すればだいたい書いてあったので、そこから適当に選んでIPを振ったのはよかったのですが、本当はかっこよくDNSでシュッと引けたら気分がいいですよね?そうしましょう!

やったこと

dnsmasq を使うことにしました。bindっていう規模でもなかったので。aptですぐ入るのが便利。

sudo apt install dnsmasq

ところがインストール直後に不穏なメッセージが。

dnsmasq: failed to create listening socket for port 53: アドレスは既に使用中です

え?いつの間にDNSサーバーが!?誰だ建てたのは!外部からの侵入か?と冷や汗をかいたが犯人は systemd-resolved でした。 (127.0.0.1:53 だけだったので、外からはアクセスできませんでしたが。)

以下の記事も同じような状況に遭遇して同じような反応をしていました。

qiita.com

結局 systemd-resolvedをdisableすることにしました。以下の投稿の通りにすればOKだった。

askubuntu.com

設定は基本的に以下で述べられている例を参考にすれば良いと思います。

int128.hatenablog.com

また、 /etc/hostsをdnsmasq用に使うと、dnsmasq自体を走らせているサーバーのホストについて127.0.0.1を返すことになります。これでは悲しいので、/etc/dnsmasq.conf

no-hosts
addn-hosts=/etc/hosts-dnsmasq

と記述し、/etc/hostsは読み込まず、代わりに/etc/hosts-dnsmasqを利用するように設定しました。

おまけ:DHCPサーバにDNSサーバとドメイン名を設定する(Ciscoルーターの場合)

ここまで設定したら、端末側のDNSサーバ設定もDHCP経由で自動的に設定してあげたいですよね。私のネットワークでは、CiscoルーターDHCPサーバーになっているので、その設定も変更しておくことにします。

ルータのバージョンは以下の通りです。

Cisco IOS Software, C800M Software (C800M-UNIVERSALK9-M), Version 15.7(3)M2, RELEASE SOFTWARE (fc2)

手順

  1. show ip dhcp pooldhcp poolの名前を確認しておきます。
  2. configure terminal に入って、ip dhcp pool <dhcp pool名>を実行して該当poolの設定に入ります。
  3. dns-server <DNSサーバのアドレス> domain-name <ネットワークのドメイン名> としたのち、exitしてwrite memします。

これで、各端末のDHCPリースを更新すれば、ホスト名だけでsshしたりできるようになっているはずです。やったね!

まとめ

  • dnsmasqをインストールして、かんたんな内部向けDNSサーバを建てた。
  • 新しいUbuntuでは、systemd-resolvedがすでにPort 53をLISTENしているので、これをdisableにした。
  • /etc/dnsmasq.confはこんな感じ。
domain-needed
bogus-priv
local=/local.hikalium.com/
no-hosts
addn-hosts=/etc/hosts-dnsmasq
expand-hosts
domain=local.hikalium.com
  • DHCPサーバの設定もいじっておきましょう!

SECCON 2017 Online CTF writeup (Remote debugging of a micro computer)

概要

SECCON 2017 Online CTF にチーム Bluemermaid (a.k.a. Harekaze)として参加し、Remote debugging of a micro computer (300) を解きました。 この問題を解いたチームは13チームと結構少なめだったようです。 また、チーム全体では5800ポイントで第3位でした。最終的に出題されていたほとんどの問題が解かれていてびっくりしました。チームのプロの皆様に感謝 :pray: 。

ちなみにこれに時間を費やした結果、TOEICに行き損ねました。

バイナリの方が話者多いし問題ないでしょ!

解くまでの過程

問題

Remote debugging of a micro computer

Connect to the server and read "word.txt" on current directory.

$ echo '$g#67+' | nc micro.pwn.seccon.jp 10000

The server is running on GDB simulator with special patches.

Long time connection will be disconnected automatically. (in several minutes)

Short interval requests will be also ignored. (in several seconds)

URLとポートが与えられ、そこにncで接続すると、GDBのリモートデバッグプロトコルで問題サーバーとお話しできます。 そして、word.txtというファイルがカレントディレクトリにあるので、それを読んでね!という内容でした。

与えられている情報は:

  • デバッグポートのURLと番号
  • 去年も同じような問題を出したよ
  • SOP(Step-Oriented Programming)というのがあるよ(スライドへのリンク)
  • 去年の問題サーバのソースとか、マルチアーキテクチャ対応のgccはここにあるよ(リンク)

という感じでした。つまりですね、この問題は

「対象アーキテクチャが一切不明な状態」 で始まるのです。

SOP(Step-Oriented Programming)ってなんだ

これはたしか坂井さん(KOZOSやバイナリかるたとか熱血アセンブラ入門で有名なあの方です。セキュリティキャンプなどで大変お世話になっております)の造語で、「デバッガでステップ実行することで任意コード実行できるよね?じゃあやってみようか」というものです。 今年のCODEBLUEでも坂井さんがこの話で登壇されていらっしゃいました。というか、問題で提示されていたスライドはどう見てもCODEBLUEのときのものです。

www.slideshare.net

ただし、フル機能のデバッガが使える状態であれば、あまりにも簡単過ぎてお話しになりません。 というわけで、問題文をよく読んでみるとThe server is running on GDB simulator with special patches. と書いてあります。つまり、このリモートデバッガはなんでもできる訳ではなく、機能が非常に制限されているのです。

どの程度制限されているかということはスライドに記載があります。

簡単に説明すると、デバッガは通常、レジスタへの読み書きと、メモリへの読み書きができるのですが、今回は「メモリへの書き込みができない」ような状態になっています。

いやー、それはそうですよ。だって、メモリに書き込めちゃったら、(アーキテクチャさえわかれば)簡単に任意コード実行できますからね。

という訳で、この問題で重要なパートは以下の2つに大別されます。

  • 対象バイナリのアーキテクチャを特定する
  • 任意コード実行をできるようにしてフラグファイルを読む

ではまず、アーキテクチャの特定からとりかかりましょう。

アーキテクチャの特定

さて、アーキテクチャを特定したかったのですが、まずこの問題はバイナリが配布されていません。バイナリがないことには(一般人は)アーキテクチャを特定しようがないので、どうにかバイナリを手に入れることを考えます。

バイナリをもらってくる

GDBデバッグプロトコルには、メモリを読み込む命令があります。形式は以下の通りです。

$m<addr>,<count>#<checksum>+

addrとcountは16進数です。桁数は適当で大丈夫でした。 checksumは、コマンド部分に相当するバイトの総和をhexで記述します。 といっても、いちいち手動で計算するのはつらいので、問題文に書いてあった昨年の解答例に含まれているperlスクリプトを利用するとよいでしょう。スクリプトを利用する際は、先頭の$と末尾の#<checksum>+はつけなくて大丈夫です(自動で付加されます)。

echo "m0000,100" | ./sendgdbproto.pl | nc micro.pwn.seccon.jp 10000

すると、こんな感じの応答が得られます。

+$00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#00

うん。たしかに100バイトですね。でも全部0...。

いつかバイナリに当たることを祈って、順次アドレスを変化させてゆきます。 ちなみに、一度に取得するサイズを大きくしすぎると

+$E03#a8

のように、Eが先頭につく返答が帰ってきます。かなしいです。 だいたい300くらいまでは大丈夫そうでした。

で、やがて見つける訳です。バイナリを。

echo "m2000,200" | ./sendgdbproto.pl | nc micro.pwn.seccon.jp 10000
+$11400e08b0137620b01381011001b01384011001b01385011001b01382011001b01383011001b0130820b1000200c14d0100cd01ad0001001e43b0131420a100020010010a140a4db0132a200c4a0a1610012a14094cca0d6d4d0d930924880044200c494813aa0001006d4a0d93f9230c43281610011c438d006821b01352200c43b01326205a143a401f00064305461e430b46084e085e094b096b074807fc0f490ffd0fd70f93022406de05db3a530e480b490a93ee230c460d45551610010a1408142a428800862048133a530a93fc2308160a1610016a14b1001400814c00000c4d0d4e0a4fc14313000e4c0edd0e9303200f9301201a43ce01ae0012000e1440183841401839418700762180003621044c34f00f000e43054e051204120e16ee07e64e0000b013c0200a9501243a53385339630912081206160e4c0edd0e93e7230a930524f64030000000800030212c41cd06ad000100b01352200c43a10014006416100148656c6c6f20576f726c64210a00303132333435363738396162636465660000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#2a

おおー!待望のバイナリですね。これでもう勝てた...と思ったら大間違いです。ここからがつらかった...。

じっとながめる

上記の出力から無駄な部分をのぞいて、純粋なバイト列にしたものが以下です。

00000000  11 40 0e 08 b0 13 76 20  b0 13 81 01 10 01 b0 13  |.@....v ........|
00000010  84 01 10 01 b0 13 85 01  10 01 b0 13 82 01 10 01  |................|
00000020  b0 13 83 01 10 01 b0 13  08 20 b1 00 02 00 c1 4d  |......... .....M|
00000030  01 00 cd 01 ad 00 01 00  1e 43 b0 13 14 20 a1 00  |.........C... ..|
00000040  02 00 10 01 0a 14 0a 4d  b0 13 2a 20 0c 4a 0a 16  |.......M..* .J..|
00000050  10 01 2a 14 09 4c ca 0d  6d 4d 0d 93 09 24 88 00  |..*..L..mM...$..|
00000060  44 20 0c 49 48 13 aa 00  01 00 6d 4a 0d 93 f9 23  |D .IH.....mJ...#|
00000070  0c 43 28 16 10 01 1c 43  8d 00 68 21 b0 13 52 20  |.C(....C..h!..R |
00000080  0c 43 b0 13 26 20 5a 14  3a 40 1f 00 06 43 05 46  |.C..& Z.:@...C.F|
00000090  1e 43 0b 46 08 4e 08 5e  09 4b 09 6b 07 48 07 fc  |.C.F.N.^.K.k.H..|
000000a0  0f 49 0f fd 0f d7 0f 93  02 24 06 de 05 db 3a 53  |.I.......$....:S|
000000b0  0e 48 0b 49 0a 93 ee 23  0c 46 0d 45 55 16 10 01  |.H.I...#.F.EU...|
000000c0  0a 14 08 14 2a 42 88 00  86 20 48 13 3a 53 0a 93  |....*B... H.:S..|
000000d0  fc 23 08 16 0a 16 10 01  6a 14 b1 00 14 00 81 4c  |.#......j......L|
000000e0  00 00 0c 4d 0d 4e 0a 4f  c1 43 13 00 0e 4c 0e dd  |...M.N.O.C...L..|
000000f0  0e 93 03 20 0f 93 01 20  1a 43 ce 01 ae 00 12 00  |... ... .C......|
00000100  0e 14 40 18 38 41 40 18  39 41 87 00 76 21 80 00  |..@.8A@.9A..v!..|
00000110  36 21 04 4c 34 f0 0f 00  0e 43 05 4e 05 12 04 12  |6!.L4....C.N....|
00000120  0e 16 ee 07 e6 4e 00 00  b0 13 c0 20 0a 95 01 24  |.....N..... ...$|
00000130  3a 53 38 53 39 63 09 12  08 12 06 16 0e 4c 0e dd  |:S8S9c.......L..|
00000140  0e 93 e7 23 0a 93 05 24  f6 40 30 00 00 00 80 00  |...#...$.@0.....|
00000150  30 21 2c 41 cd 06 ad 00  01 00 b0 13 52 20 0c 43  |0!,A........R .C|
00000160  a1 00 14 00 64 16 10 01  48 65 6c 6c 6f 20 57 6f  |....d...Hello Wo|
00000170  72 6c 64 21 0a 00 30 31  32 33 34 35 36 37 38 39  |rld!..0123456789|
00000180  61 62 63 64 65 66 00 00  00 00 00 00 00 00 00 00  |abcdef..........|
00000190  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

みなさんはこれを見て、何を思いますか? ごく少数のプロを除けば、「は?」という感じだと思います。

これ以降は、私が適当に時間をかけて無理やりアーキテクチャを特定した話なので、参考になるかはご自身で判断してください。 もし、もっといい方法があったなら(きっとある)ぜひ教えてください...。

まず、気づくこととしては

  • eが多い訳でもない -> ARMっぽくない
  • b0 13が頻出する(なんかありそう)
  • 10 01もたまに出てくる (なんかありそう)
  • 最後の部分はASCIIコードでHello World!のあとに'0-9a-z'って書いてある

があげられると思います。 というわけで、バイナリ部分をとりあえず予想にしたがって切ってみましょう。

11400e08
b0137620
b01381011001
b01384011001
b01385011001
b01382011001
b01383011001
b0130820b1000200c14d0100cd01ad0001001e43
b0131420a100020010010a140a4d
b0132a200c4a0a1610012a14094cca0d6d4d0d930924880044200c494813aa0001006d4a0d93f9230c43281610011c438d006821
b01352200c43
b01326205a143a401f00064305461e430b46084e085e094b096b074807fc0f490ffd0fd70f93022406de05db3a530e480b490a93ee230c460d45551610010a1408142a428800862048133a530a93fc2308160a1610016a14b1001400814c00000c4d0d4e0a4fc14313000e4c0edd0e9303200f9301201a43ce01ae0012000e1440183841401839418700762180003621044c34f00f000e43054e051204120e16ee07e64e0000
b013c0200a9501243a53385339630912081206160e4c0edd0e93e7230a930524f64030000000800030212c41cd06ad000100
b01352200c43a1001400641610014
8656c6c6f20576f726c64210a0030313233343536373839616263646566

おー、たしかにb0 13がたくさんありますね。しかも先頭の方、末尾が全部01 10 01 になっていて、怪しいです。 でも、01 10 01で1命令だとすると、先頭部分と合いませんね。そもそも3バイト固定ってアーキテクチャってのも変だし...。

というわけで、これ以上予想を重ねるのはやめて、きちんと動作を確認して予想を立てることにします。

ステップ実行してレジスタの様子をみる

こういう時はステップ実行すれば、命令境界がわかって嬉しいですね。 というわけで、レジスタをトレースしつつ、ステップ実行してみましょう。 現在のレジスタ状態を取得するコマンドはg, ステップ実行はsです。

g
s
g
s
g

これを適当にcmd.txtとでも保存して、cat cmd.txt | ./sendgdbproto.pl | nc micro.pwn.seccon.jp 10000とすれば、順次実行時のレジスタ状態が降ってきます。かんたんですね。

+$00200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#02+$T05#b9+$04200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#06+$T05#b9+$76200000fcff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#1a+$T05#b9+$78200000fcff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000#1d+$T05#b9+$7c200000fcff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000682100000000000000000000#59+$T05#b9+$52200000f8ff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000682100000000000000000000#fb+$T05#b9+$54200000ecff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000682100000000000000000000#27+$T05#b9+$56200000ecff0f000000000000000000000000000000000000000000000000000000000001000000000000000000000001000000682100000000000000000000#2a+$T05#b9+$58200000ecff0f000000000000000000000000000000000000000000000000000000000001000000682100000000000001000000682100000000000000000000#3d+$T05#b9

これを見ていると、いくつかわかることがあります。まず、最初の少なくとも2バイトがプログラムカウンタだということ、そして途中で突然4バイトめが負の数っぽくなっていることから、そのあたりがスタックポインタっぽい、しかもその幅をみるに、16bitに収まらないから32bitだろう...などです。

でも、出力を読むのがつらいです。どこでレジスタが切れているのかわからない...。 というわけで、これを自動でフォーマットしてくれる&前状態との差分をとってくれるプログラムを書きました。

seccon 2017 online CTF writeup (Remote debugging o ...

このプログラムでは、レジスタ幅を32bitとしていますが、当初私は16bitと仮定していて、上に書いた通りスタックポインタの動きを見て、32bitだと考えて修正しました。

で、もうちょっとステップ実行の回数を増やして、出力をこのプログラムに食べさせると、こんな感じになります。

PC: 0x2000
----
PC: 0x2004
----
PC: 0x2076
        SP: 0x0 -> 0xffffc
----
PC: 0x2078
        R12: 0x0 -> 0x1
----
PC: 0x207c
        R13: 0x0 -> 0x2168
----
PC: 0x2052
        SP: 0xffffc -> 0xffff8
----
PC: 0x2054
        SP: 0xffff8 -> 0xfffec
----
PC: 0x2056
        R9: 0x0 -> 0x1
----
PC: 0x2058
        R10: 0x0 -> 0x2168
----
PC: 0x205a
        R13: 0x2168 -> 0x48
----
PC: 0x205c
        R2: 0x0 -> 0x1
----
PC: 0x205e
----
PC: 0x2062
        R8: 0x0 -> 0x2044
----
PC: 0x2064
----
PC: 0x2044
        SP: 0xfffec -> 0xfffe8
----
PC: 0x2046
        SP: 0xfffe8 -> 0xfffe4
----
PC: 0x2048
        R10: 0x2168 -> 0x48
----
PC: 0x202a
        SP: 0xfffe4 -> 0xfffe0
----
...

この出力をどんどん見てゆくと、

  • 命令サイズは2 or 4バイト
  • レジスタ数は16本(PC, SP含む)
  • b0 13 aa bb = call 0xbbaa っぽい
  • 8r aa bb cc = Rr = 0xccbbaa っぽい

ということがわかります。分岐命令や代入命令はそこそこ登場頻度が多いので、それがわかればアーキテクチャを見分けられる可能性が高まります。

では、これらのヒントをもとに、アーキテクチャを絞り込んでゆきます。

絞り込む(目grep

最初はgrepb0 13とか調べればいいかなと思ったのですが、どうもぱっとしませんでした。というわけで、ありそうなアーキテクチャアセンブリコードを総当りすることにしました。

ヒントとなるのは、問題に書かれていたクロスコンパイラの中にあるサンプルです。 cross-gcc494/sample/*.dには、各アーキテクチャ向けのバイナリ&アセンブリ例が載っています。

ここを読んで、形式が似ているかどうか、そして、同じ命令がないかをじっくり探しました。

- このCPU -> 2, 4バイト混在, 16個のレジスタ(4byte), アドレス幅は16bit?
- aarch64 -> 4バイト固定
- alpha -> 4バイト固定
- arm -> 4バイト固定
- arm16 -> 2, 4バイト混在
- mn10030 -> 可変長命令、ちょっとちがう
- avr -> 2バイト固定
- avr8 -> 2バイト固定
- bfin -> 2, 4混在
- cr16 -> 2, 4混在
- cris -> 2, 4, 8バイト, ちょっとちがう
- epiphany -> 2, 4混在
- frv -> 4バイト固定
- fr30 -> 2, 4混在
- h8300 -> 2, 4バイト混在,
- h8300h -> 2, 4バイト混在,
- hppa -> 4固定
- i386 -> 可変長
- lm32 -> 4バイト固定
- m32r -> 4バイト固定
- m32c -> 1-4可変
- m6811 -> 1-4バイト可変
- m68k -> 2, 4, 6可変
- mcore -> 2バイト固定
- microblaze -> 4固定
- mips -> 4バイト固定
- mips16 -> 2, 4バイト混在。
- mips64 -> 4固定
- mn10300 -> 1-3バイト混在
- moxie -> 2, 4混在
- msp430 -> 2, 4混在
- powerpci -> 4バイト固定
- sh -> 2バイト固定
- sh64 -> 4バイト固定
- sparc -> 4バイト固定
- v850 -> 2, 4バイト混在

そして、やっとmsp430にたどり着いた訳です。

ちなみに、決め手はこのサイトでした。

16進数を流し込んだら、「読める、読めるぞ!!!」という感じで最高に嬉しかったです。

あとはシステムコールを叩くだけ...どうやって?

さて、これでアーキテクチャは完全にわかったので、どのコード片がどういう動作をするのかだいたい把握できた訳です。 あとは、システムコールを叩いてword.txtを読むだけなのですが、しかし、どうやらこのアーキテクチャでは、システムコールは「syscall命令」や「割り込み」ではなく、関数呼び出しとして実装されているようです。syscallみたいな文字が見えないですし。

(2017-12-11追記:作問者の坂井さんより、このアーキテクチャではシステムコール呼び出しに使えるCPUの機構がおそらくなく、そのためシミュレータは「モニタ」とよばれる、各マイコンメーカから提供されるデバッガのようなハードウエアの動作を模倣しているのではないか、もしくはこの「システムコール」はGDBの独自拡張ではないか、という話でした。ちなみに、こういった「特定番地を呼び出すとシステムコール的な動作をする」仕組みのことを、H8マイコンでは magic trap というらしいですが、一般的な用語ではないそうなので、「システムコールっぽいサービスを関数呼び出しでエミュレーションしているよくあるやりかた」と言うと通じるらしいです。)

ここは少し悩んだ結果、disasmした結果から、"Hello World!"している場所を探して、どうやって処理しているか確認しました(私もこれを書きながら一瞬どうやったのか忘れてしまいました)。

まず、"Hello World"という文字列が格納されているアドレスですが、それは物理メモリ上の0x216eでした。 で、disasmした結果からこの番地を使っている場所を探すと、

2076: 1c 43                            mov   #1, r12 ;r3 As==01
2078: 8d 00 68 21                      mova #8552,  r13 ;0x02168
207c: b0 13 52 20                      calla    #8274       ;0x02052
2080: 0c 43                            clr  r12     ;
2082: b0 13 26 20                      calla    #8230       ;0x02026

という場所が見つかり、ここが文字列を出力している部分と思われます。ここでは2回callaがありますが、ひとつめはstrlenした結果をr14に格納するようなコードに飛ぶもので、問題は2つめのほうです。この飛び先は...。というあたりで、どうやって解いたのか忘れてしまいました。 ここは思い出したら追記します。ごめんなさい。メモリがそろそろ耐用年数を過ぎていて...。

ひとまず、特定のアドレスに飛ぶことが、syscallを呼び出すことになると理解してください。

結果、以下のことがわかりました。

  • open(path, flags, mode)は以下の命令を以下のレジスタ状態で呼べば良い。

    • 201a: b0 13 82 01 calla #386 ;0x00182
    • R12 = path
    • R13 = flags
    • R14 = mode
  • read(fd, buf, size) は以下の命令を以下のレジスタ状態で呼べば良い。

    • 200e: b0 13 84 01 calla #388 ;0x00184
    • R12 = fd
    • R13 = size
    • R14 = buf

任意メモリ書き換えの手段

これも、アセンブリの中から使えそうな命令を拾ってきます。私が選んだのはこの子です。

20de: 81 4c 00 00         mov    r12,    0(r1)    ;

この命令を実行すれば、r12のデータがr1番地に書き込まれます。試したところ、16bit分でした。わーい。

道具は揃った

さて、これで道具は揃いました。すべきことは3段階です。

  • "word.txt"をメモリ上のどこかにつくる
  • openする
  • readする

これらは、

Gコマンドでレジスタを特定の状態に設定し、 sコマンドで動かす

ということを繰り返せば実現できます。

最初の目標は、言い換えれば77 6f 72 64 2e 74 78 74 00をメモリに書き込むことでした。 ちょうど、"Hello World!"の後半は"World"だったので、この辺りに書き込むことにします。(効率化は面倒なのでしなかった。あとでやってみたい。) アドレス0x216eからの場所に書き込むとすれば、

Gde2000006e2100000*l776f00000*4
s
Gde200000702100000*l726400000*4
s
Gde200000722100000*l2e7400000*4
s
Gde200000742100000*l787400000*4
s
Gde200000762100000*l000000000*4
s

こうすれば書き込めます!あ、ちなみに0*lとかは省略表記で、*の前の文字を、(後ろの文字のASCIIコード-28)回書くことと同義です。(2017-12-11 回数が間違っていたので修正しました。)

スライドには「さらに(後ろの文字のASCIIコード-29)回書いたのと同じ」と書いてあって私は誤解した(全体でこうだと思っていた)ので、気をつけるといいと思います。

つまり、0*40が32個と等価になるわけです。

そして、最後のsyscallですが、openは

G1a20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006e210000000000000000000000000000
s

readは

G0e2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000006e2100002000000000000000
s

とすればよいです。もちろん、読み出した結果を知る必要もありますから、末尾にメモリ呼び出し命令をつければ、全体では

m0216e,10
g
Gde2000006e2100000*l776f00000*4
s
Gde200000702100000*l726400000*4
s
Gde200000722100000*l2e7400000*4
s
Gde200000742100000*l787400000*4
s
Gde200000762100000*l000000000*4
s
G1a20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006e210000000000000000000000000000
g
s
g
G0e2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000006e2100002000000000000000
s
g
s
g
m0216e,20

という感じになります(実際にこれで通しました)。最後に出力されたメモリ内容が、フラグの文字列データになっていました。

あ、実はopenしたファイルディスクリプタが2になると信じ込んでいて、(stdin: 0, stdout: 1, stderr: 2 だから3になるのはあたりまえ)、それで10分くらい無駄にしたのは秘密です。

本当は省略表記を活用すればもっと綺麗になったかと思いますが、それはまたの機会に。

おわりに

TOEICをさようならしたおかげで、なんとか問題を解くことができて非常に嬉しかったです。

競技時間内は、なんのアーキテクチャかわからず6時間くらい苦しい時間を過ごしていたので、もっと色々なアーキテクチャのことを知らなければ、と思いました。

久々にバイナリをたくさん食べてお腹がいっぱいになったので、また明日からも頑張れそうです。

ではみなさまも、存分にバイナリをお楽しみください。