Show HN: RISC-Vアセンブリ卓上ボードゲームで相手をハックする
(punkx.org)- PROJEKT: OVERFLOWは、RISC-Vアセンブリとバッファオーバーフローをボードゲームのルールに落とし込み、メモリ・スタック・リターンアドレスの操作を実際に追体験できる学習用ゲーム
- プレイヤーは同じメモリとプログラムを共有し、仮想メモリなしでターンごとに10命令だけを実行するプリエンプティブスケジューリング方式で競い合う
- 勝敗は、既存の命令をコピーしてシェルコードを作り、相手の return address を上書きして
game_over()に飛ばす流れで決まる - 不正なメモリアクセス、非アライン読み書き、違法命令はクラッシュと例外ハンドラの実行につながり、trap アドレスの変更と
nopモンキーパッチが戦略の重要な変数となる - Webプレイ、印刷用ボード、ESP32・モバイル向けゲームヘルパーが提供されるが、ルールの一部はまだ調整中で、実験的なハッキングパズルに近い
ゲームの目標と実行モデル
- PROJEKT: OVERFLOWは、RISC-Vアセンブリとバッファオーバーフローを卓上ボードゲームとして扱うプロジェクト
- 中核となる目標は、既存の命令をコピーしてメモリ内に小さなシェルコードを作り、バッファオーバーフローでそのコードへジャンプしたあと、相手の return address を上書きして
game_over()関数を呼ばせること - 戦略には単純なコード実行だけでなく、例外ハンドラの設定やモンキーパッチも含まれる
- すべてのプレイヤーは同じメモリと同じプログラムを共有し、同じプロセッサをタイムスライス方式で使う
- 1ターンでは10命令を実行する
- 各プレイヤーの stack pointer は異なる位置から始まる
- 仮想メモリはない
ビルドとボード生成の流れ
- コードは
riscv64-unknown-elf-gccでRV32向けにコンパイルされる- 主なオプションには
-march=rv32g,-mabi=ilp32,-ffreestanding,-nostdlib,-nostartfiles,-O0などが含まれる -O0により、マシンコードは冗長だが追いやすい形になる
- 主なオプションには
- ボード用の資料は
riscv64-unknown-elf-objdump -S -l -fd gameの出力をパースして作成する▲と✎命令を修正する- ジャンプオフセットを16進数から10進数に変換する
- アセンブリを整理してソースコードと対応付ける
- SVGを作成したあと、InkscapeでPDFに変換する
印刷と準備物
- ボードは左右に分かれたPDFを印刷して使う
- 印刷はA3推奨で、A4でも可能だが小さい
- 準備物は
nop命令用のコマ1個、trap アドレス用のコマ1個、プレイヤーごとに program counter と stack pointer 用のコマ2個、鉛筆と消しゴム - Web版は1人プレイと友人とのプレイに対応し、ESP32・モバイル向けゲームヘルパーも提供される
基本ルールとターン進行
- 開始状態は以下のとおり
- すべてのレジスタは0から始まるが、return address レジスタ
raは1000から始まる - Player 1 の
spは2244、Player 2 のspは3844に初期化される - 両プレイヤーの
pcはmain関数の開始アドレスである1000から始まる - trap のコマはアドレス1000に置く
- あらかじめロードされたプログラムを除くすべてのメモリアドレスは0
nop命令のコマは最初はボード上に置かない
- すべてのレジスタは0から始まるが、return address レジスタ
- 1ターンでは10命令を実行しなければならず、
jalやbeqのようなジャンプもそのまま追う - プレイヤーは少なくとも1命令を実行したあとでターンを中断し、残り命令数を次のターンに持ち越せる
- 累積できる命令数の上限は20命令
モンキーパッチと勝利条件
- 各ターン開始時、ちょうど1命令を実行したあと、現在どのプレイヤーも実行中でない関数内の任意のアドレスへ
nop命令のコマを移動できる - そのアドレスに
pcが到達すると、その命令はno-operationとして動作する nopのコマを移動すると現在のターンと次のターンを失い、相手は次のターンに最大20命令を実行できる- モンキーパッチのルールはまだバランス調整中で、数日ごとに少しずつ変わっている
- ハードモードでは、相手をハックして
game_over()関数を呼ばせるとゲーム終了 - どちらも相手を
game_over()に送れない状態になった場合は引き分け - イージーモードでは、
mainでretを実行してメインループを抜けた最初のプレイヤーが勝利する
特殊記号と例外処理
✎はli命令の immediate 値として0から4095までの任意の12ビット数を選べることを示す▲は load 命令で、自分の stack pointer を基準に ±128バイトの範囲から値を選べることを示す- たとえば
spが2180なら、2052から2308まで選択可能
- たとえば
- 禁止行為はプログラムのクラッシュにつながる
- 1192より低いメモリアドレスの上書き
- 4の倍数でないアドレスへの非アライン読み書き
- 違法命令の実行
- クラッシュすると例外ハンドラが実行され、trap アドレスへジャンプする
- trap アドレスは最初は1000だが、
set_trap()関数で上書きできる - 例外が発生すると program counter が特定の値に設定され、実行が継続される
- trap アドレスは最初は1000だが、
- 不正行為やミスが発覚した場合、そのプレイヤーのプログラム状態、メモリ、レジスタはリセットされる
3〜4人拡張ルール
- Player 3 の
spは2116に設定される - Player 4 の
spは3716に設定される - 3人以上の場合、
▲記号は stack pointer から -128バイトの範囲にしか使えない - 2人より多いプレイヤーで進行すると、ゲームはかなり不安定になり、すぐに壊れやすくなる
- 勝利条件に到達するのはより難しくなるが、プレイはより楽しく、より混沌としたものになる
ハッキング戦略の例
- クラッシュは相手の進行を止める攻撃戦略として使える
- trap handler を
game_over関数に変えると、最初にクラッシュしたプレイヤーが敗北する- この状態では
nopのコマが非常に強力になる - 相手が現在実行中の関数の
retの上にnopを置くと、相手が敗北する可能性がある
- この状態では
bug()関数で index を400または-400にオーバーフローさせると、相手のスタックにアクセスして return address を上書きできる- 例として、アドレス3784から2184へ移動するには
(3784 - 2184) / 4 = 400なので index-400が必要
- 例として、アドレス3784から2184へ移動するには
copy()関数で特定の命令をコピーし、メモリ上に短いシェルコードを作れる- 例のシェルコードは
li a4, ✎,li a5, ✎,sw a4, 0(a5),retの組み合わせで任意書き込みを実行する ret命令をコピーすると return address がシェルコード開始地点に設定され、無限ループになる
- 例のシェルコードは
bug()関数で index を6に設定すると、value変数をスタック上の保存された return address である28(sp)に書き込めるbug()から戻る際、28(sp)の値が return address レジスタにコピーされる- ここに作成したシェルコードのアドレスを入れれば、メモリへジャンプできる
命令解釈と変更点
- すべてのジャンプは、逆アセンブラでは絶対アドレスのように見えても、現在の program counter を基準にした相対ジャンプ
- たとえば
jal a4, 0のマシンコード1903は、実行すると無限ループになる
- たとえば
- 有効なゲーム命令の一覧は、マシンコード0から4095までのRV32 JRI命令のうち
a0,a4,a5,sp,raなどを使う形で整理されている - 変更ログ0.0.6には、
while(run)の代わりにwhile(*prun)を使う変更が含まれる- 相手が非アライン参照を誘発して強制的にクラッシュさせられるようになった
- NOPルールは、現在実行中でない関数にのみ配置可能なように変更された
デザインと学習資料
- ボード左右の四角形はASCIIでエンコードされたバイナリメッセージ
- 白い四角は1、黒い四角は0
- 色は安価な印刷と白黒プリンタでの可読性のため、赤、青、黒、白だけを使う
- シンタックスハイライトは使わない
- テーマによってコードの一部がより重要に見える効果を避け、自分で判断しながら集中するための選択
- RISC-Vアセンブリの学習資料として riscv-programming.org, cs3410 risc-v interpreter, luplabの rvcodecjs などがある
- Cの学習資料としては Beej's Guide to C Programming の前半が使われる
- 変数、関数呼び出し、ポインタ、文字列、構造体、配列、再帰などを扱う印刷用アセンブリ練習PDFと、穴埋め式の “assembly hangman” バージョンが提供される
1件のコメント
Hacker News の意見
本当に印象的。特に12歳の娘にこれを一緒に遊ばせたという点が一番すごいと思う
CHERI 版はいつごろ期待できる？ :-D
Core War は、単純な模擬アセンブリ言語をサポートする仮想マシンのメモリアリーナで行うゲーム。1984年に Scientific American で初めて見たが、その時点ですでに15年ほどプログラミングをしていたので、Bell Labs のもっと古いゲーム Darwin に触発されたものだと分かった
Darwin は1961年に作られ、IBM 7090 上で動作していた。プログラム同士が資源をめぐって競争し、割り当てられた空間全体を複製して支配したプログラムが勝つ仕組みだった。Robert Morris Sr. が勝てないプログラムを作った後、長くは続かなかった。[2] 参照
1970年代半ばには Software Practice and Experience が最も好きなコンピュータサイエンス誌の一つで、Aleph-Null という筆名で書かれた Computer Recreations 欄がよく掲載されていた。大学院時代、その欄に載っていたゲームをいくつも実装して楽しんだ。雑誌は高いが、大学生なら昔の私のように大学図書館で見つけられる可能性が高い。1970年代の号には Pascal コンパイラ、Algol 68、並行プログラミングといったテーマが載っていて読みやすく面白く、N. Wirth の記事を通じて Module[3,4] と、その後 Oberon[5] を知った
[1] https://en.wikipedia.org/wiki/Core_War
[2] https://en.wikipedia.org/wiki/Darwin_(programming_game)
[3] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
[4] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
[5] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801909...
ゲームは好きだけれどコーディング脳はないと言っていた友人がいたが、Human Resource Machine を通じて実質的にコーディングするようになり、いくつかの解法は数年経験のある私のものより良かった
うちの12歳の子は数学が嫌いだが、Human Resource Machine と SpaceChem は驚くほど得意。高校数学とプログラミングにおける数学は根本的に違うのかと気になる
とても興味深い。今日のコンピュータのメモリ容量を考えると、短いニーモニックは工学的に良い選択ではないとずっと感じてきた
ここでも最初にやるべきことは、命令が何をするのかを学び、覚えること。名前をもっと説明的な形に変えれば、習得も記憶もコードの読解もはるかに簡単になる。人々があまりそうしない点が疑問だ
こうした種類の脆弱性が可能であるという事実も、システム全体の設計失敗を示していると思う。面白いゲームではないとか、学ぶのに良い方法ではないという意味ではないが、工学では構造的な問題があまりにも簡単に受け入れられている。大半の人はその構造的欠陥を見ることすらできないほどだ
子どもは見くびらないと本当によく応えてくれると思う。少なくともうちの子はそうだった
任意読み取りと任意書き込みを構造的欠陥だと思わない人がいると思う？ 何千人もの人がその問題に取り組み、かなりの進展も生み出している。同時に、それでも peek と poke は楽しいと思う
これ本当にかっこいい。会社で試してみたい
かなり面白そう。どの年齢層に向いていると思う？
bug()で素早いバッファオーバーフローによってメインループから抜け出すのは、10〜15歳でもできると思ううちの娘は12歳で、一緒に楽しく遊んでいる。難しい勝利条件、つまり相手を
game_over()関数へジャンプさせるのはもっと難しいが、5〜6か月以内には到達できると思う大人についてはよく分からない。アセンブリを悪魔が作ったもののように怖がる人もいるので、子どもよりプレイしてもらうのが難しいかもしれない
興味深いのは、私たちが世界を自分自身の鏡のように見る傾向があることだ
自分がバッファオーバーフローとプログラミングに興味があるからといって、自分の娘も当然大きな関心を持つだろうと見るのは、どれほどあり得ることだろうか？ 第一子で、第二に女の子だという点まで考えると確率はさらに低そうだが、それでも多くの父親が押し進めるのを見ている
こういうプロジェクトをやるとき、少なくともある程度は虚栄心のプロジェクトだという自覚があったのか気になる。いずれにせよ、私はこういうものに興味があるので、公開してくれてうれしい
プロジェクトの作者が自分の虚栄心のために娘にこれを強いていると示唆しているが、その根拠はどこにあるのか？ サイトを数ページ見たが、そんなことを示す内容はまったく見当たらず、むしろ娘が楽しんでいて、とても関心を持っているという穏やかな表現が何度もあった
娘のほうが先に、父親がコンピュータで何をしているのかをずっと気にしていて始まった可能性を、なぜ排除するのか？ 小さく始まり、関心を共有する人と幼い共同探検者の間の双方向のプロセスとして育ったのかもしれない
実際どうなのかは私にも分からないが、あなたにも分からないはずだ。教育に数年関わってきた立場からすると、子どもは一般に信じられているよりはるかに優れた学習者だ。学校の構造も一因だろうが、根底にはこうした制限的な思い込みがあるのかもしれない。娘と世界に自分の関心と情熱を分かち合おうとしたこの父親に拍手を送りたい
そのうち価値のあるものもあれば、ないものもあるだろう。確率はいつだって不利だ。人生とはそういうものだ
64ビットの RISC-V コードパスが安定し、十分にうまく動作し、「バッファオーバーフロー」までなくなったら、C/C++ がいつも文法を変えてくれるわけではない状況で、計画的陳腐化はどうするつもりなのだろう？ 哀れな魂たち……
ちょっと待って。
アセンブリコーディングが入る卓上ボードゲームだって？ どうしてこれを以前に思いつかなかったんだ？ :D
PL/I は文字列/配列の境界チェック、下ではなく上に伸びるスタックといった部分を正しくやっていた
https://www.acsac.org/2002/papers/classic-multics.pdf