HN 日本語サマリー

← 一覧へ戻る
プログラミング

Infidel Goes Wild

Infidel Goes Wild (blog.zarfhome.com)

171 pointsby tobr36 コメント

要約

Infocomのゲーム「Infidel」で発見された、ゲームプレイにほとんど影響しないがメモリ破壊を引き起こす「ワイルドポインタバグ」について解説しています。著者は、ENDLESS-DESERTという無限に広がる砂漠のロジックにおけるオブジェクト管理の不具合を、ZILコードとZ-machineの実装詳細を掘り下げて分析し、その原因がコンパイラバグにある可能性を示唆しています。

全文翻訳

Infidel goes wild

昨日はPlanetfallが公開されましたが、もちろん私はここ数週間はInfidelに集中していました。数日前、Infocomのゲームでこれまで見た中で最もひどいバグに遭遇しました。

このバグは、ゲームをプレイして検出するのが極めて困難です。おそらく私がメモリレベルのデバッガ(に相当するもの)でゲームをプレイした最初の人なので、このバグに気づいたのも最初でしょう。

では、なぜこれをひどいバグと呼ぶのでしょうか?ほとんどの人はこれを「些細な」バグと呼ぶでしょう。なぜなら、ゲームプレイに影響することはほとんどないからです。しかし、よく聞いてください。これはワイルドポインターバグであり、意図しない方法でメモリを書き換えます。Cプログラマとして、メモリ破損はあらゆる罪の中で最悪のものと見なすことが法的に義務付けられています。それに加えて、これはコンパイラバグなのです!

(警告:ここではZILコードとZ-machineの実装の詳細に入ります。分析するのはMacintosh用のアップデートであるInfidelリリース22シリアル840522です。元のリリース、シリアル830916には、メモリのアドレスが若干異なるだけで同じバグがあります。)


状況を設定しましょう。Infidelはエジプトの遠い砂漠を舞台にしています。あなたは自分のキャンプから始まります。ナイル川は西にあります。東には9つの砂漠のロケーションがあり、3x3のグリッドになっています。(そのうちの1つに、あなたが探している埋められたピラミッドがあります。)

その地域外に ventures したり、他の方向でキャンプを離れたりすると、公式に砂漠で迷ったことになります。いくらでも移動できます。ただもっと砂漠が見つかるだけです。(熱中症に見舞われるまで。)これはEnchanterで最初に見られた既知のトリックです。ENDLESS-DESERTという単一の部屋が、マッピングされていないすべての砂漠のロケーションを表します。移動すると、キャンプやマッピングされたエリアに戻っていない限り、ENDLESS-DESERTにループバックするだけです。ゲームはあなたの緯度と経度を追跡します。

これを説得力のあるものにするために、ゲームはオブジェクトを管理する必要があります。ENDLESS-DESERTに物を落としてから移動すると、それらのアイテムは舞台裏に移動されます。それらの緯度/経度座標はDESERT-TABLEという配列に記録されます。後でそれらの座標に戻ると、ゲームはそれらのオブジェクトをDESERT-TABLEからENDLESS-DESERTに戻すことができ、それらがあなたを待っているのを見つけることができます。

(おそらく。ENDLESS-DESERTにアイテムを落とすと、砂に埋もれて永遠に失われる確率は3分の1です。これはここでは関係ありませんが、後で見るように、バグをさらに発見しにくくしています。)

さて、ここまでの計画は順調に見えます。実際に見てみましょう:

Desert You are in the desert, a vast wasteland of sand and heat.

>DROP AXE, SHOVEL pick axe: Dropped. shovel: Dropped. A brief but strong gust of wind comes up off a dune, whipping sand in your face, blinding you for long enough to lose track of the shovel.

>EAST Desert You are in the desert, a vast wasteland of sand and heat.

>WEST Desert You are in the desert, a vast wasteland of sand and heat. There is a pick axe here.

どちらのロケーションも同じENDLESS-DESERTですが、つるはしは異なる部屋の幻想を維持しています。

(背中を向けた間に、シャベルが静かに砂に埋もれて消える方がリアルではないでしょうか?おそらくそれはプレイテストで悪かったのでしょう。)

いずれにせよ、それはうまく機能するように見えます。バグはどこにあるのでしょうか?


これを実現するDESERT-TO-TABLEルーチンを見てみましょう:

<ROUTINE DESERT-TO-TABLE (
                         SLOC 
                   "AUX" (TBL ,DESERT-TABLE) 
                         (CNT 0)
                         (F <FIRST? ,ENDLESS-DESERT>)
                         N)
  <REPEAT ()
      <COND (.F <SET N <NEXT? .F>>)
            (ELSE <RETURN>)>
      <COND (<EQUAL? .F ,WINNER>)
            (<FSET? .F ,TAKEBIT>
             <REPEAT ()
                 <COND (<==? <GET .TBL .CNT> 0>
                        <PUT .TBL .CNT .SLOC>
                        <PUT .TBL <+ .CNT 1> .F>
                        <SET CNT <+ .CNT 2>>
                        <REMOVE .F>
                        <RETURN>)
                       (ELSE
                        <SET CNT <+ .CNT 2>>)>>)> 
      <SET F .N>>>

これと同様のTABLE-TO-DESERTルーチンがあり、物を元に戻します。こちらに焦点を当てます。

ルーチンは1つの必須引数SLOC(緯度/経度座標)を取ります。(これは単一の数値としてエンコードされますが、それはどうでもいいです。)次に"AUX"は4つのオプション引数をマークし、これらはローカル変数としても機能します。Z-machineは区別しません。TBLは書き込み先の配列アドレスです。デフォルトはDESERT-TABLEです。FはENDLESS-DESERTのコンテンツリストの最初のオブジェクトに初期化されます。CNTとNはゼロに初期化されます。

実際に呼び出されるとき、ゲームはSLOCという1つの引数しか渡しません。TBL=DESERT-TABLEのデフォルト値に依存します。(もしゲームに2つの無限の砂漠があったなら、別々のテーブルでこのルーチンを呼び出すでしょう。しかし、ありません。)DESERT-TABLEはアドレス11129から始まる100個の値(200バイト)の配列です。

関数本体はENDLESS-DESERT内のすべてのオブジェクト(Fから開始)をループします。ポータブルなオブジェクト(風景やプレイヤーを除く)はすべて削除され、TBL配列に2つの値(座標SLOCとオブジェクトID)が追加されます。テーブルには既にエントリがある場合があります(複数の場所に物を落とすことができるため)。そのため、空のスロットを見つけて埋めるように注意しています。リストの終わりに達したら完了です。ロジックが少し複雑に見えるかもしれませんが、連結リストを扱っていることを思い出してください。

ここまではすべて順調ですか?私には順調に聞こえました。「よし」と私は自分に言いました。「StateタブにDESERT-TABLEの内容を表示すべきだ!そうすれば、オブジェクトが出入りするのを観察できるだろう。」

そこで設定しました…しかし、うまくいきませんでした。DESERT-TABLE配列は断固として空のままでした。オブジェクトが消えたり現れたりするのは見えました — 上のつるはしを見てください! — しかし、どこへ行っていたのでしょうか?

固定サイズの配列を見ているCオタクなら誰でも「配列オーバーフローはどうなる?」と尋ねるでしょう。しかし、DESERT-TABLEにはコメントがあります:

;"length should be 2*number of takeable objects"

確かに、2つの値ごとの100個の値は、50個のオブジェクトのための十分なスペースです。ゲーム内のすべてのポータブルオブジェクトを積み上げると、(思いますに)45個になります。いずれにせよ、配列のどこにも何も格納されていません。


ゲームファイルからDESERT-TO-TABLE関数を逆アセンブルして見てみましょう。(深く入ると警告しました…)

Routine 109bc, 5 locals (0000, 001e, 0000, 0000, 0000)

109c7:  GET_CHILD     ENDLESS-DESERT -> .F [TRUE] 109cb
109cb:  JZ            .F [TRUE] RTRUE
109ce:  GET_SIBLING   .F -> .N [TRUE] 109d2
109d2:  JE            .F, G70 [FALSE] 109d9
109d6:  JUMP          10a02
109d9:  TEST_ATTR     .F, #0f [FALSE] 10a02
109dd:  LOADW         .TBL, .CNT -> -(SP)
109e1:  JZ            (SP)+ [FALSE] 109fb
109e4:  STOREW        .TBL, .CNT, .SLOC
109e9:  ADD           .CNT, #01 -> -(SP)
109ed:  STOREW        .TBL, (SP)+, .F
109f2:  ADD           .CNT, #02 -> .CNT
109f6:  REMOVE_OBJ    .F
109f8:  JUMP          10a02
109fb:  ADD           .CNT, #02 -> .CNT
109ff:  JUMP          109dd
10a02:  STORE         .F, .N
10a05:  JUMP          109cb

(1983年版を見ている場合、このルーチンはアドレス1051aにありますが、それ以外は同じです。)

私はztoolsの逆アセンブラツールtxdを使用していますが、変数名が表示されるように出力を編集しました。オペコード名はZILの用語と一致しないことに注意してください。txdは1990年代初頭のものです。ZILのマニュアルがなかったため、独自のオペコード名を作成する必要がありました。

最初の行は、部屋の最初のオブジェクト(<FIRST? ,ENDLESS-DESERT>)のFの初期値を設定します。2番目の行は、Fがゼロかどうかをテストします。これは関数のREPEATループの条件です。ループはそこから続きます。

何か足りないことに気づきましたか?TBLをデフォルト値DESERT-TABLE(11129)に初期化するのはどこでしょうか?これは明らかな穴のように思えます。

Aha、ZILは言います、私たちはあなたをカバーしました。Z-machine関数には、ローカル変数(またはオプション引数)を定数に初期化するためのスロットがあります。これはヘッダー行に示されています:

Routine 109bc, 5 locals (0000, 001e, 0000, 0000, 0000)

CNTはゼロに初期化され、Nも暗黙的に初期化されます。Fは定数ではなく計算されるため、スロットから初期化されません。ZILは関数の先頭にそのFIRST?(GET_CHILD)行を生成します。DESERT-TABLEは定数なので…

…しまった。そうではありません。DESERT-TABLEはグローバル変数です。その値は決して変化しません — ゲーム全体を通して11129のままです — しかし、ZILはそれを知りません!TBLは定数値30(16進数1e)に初期化されます。これはDESERT-TABLEのインデックス番号です。

(グローバル変数は、つまらない理由で16から255まで番号が付けられています。DESERT-TABLEは15番目のグローバルなので、番号は30です。)

誰もこのケース(引数がグローバル変数の値にデフォルトする)を考えていなかったようです。もし考えていたら、ZILはコンパイラエラー(「デフォルト値が定数ではありません!」)を表示するか、関数の先頭にSTORE命令を生成するでしょう(Fが初期化されるのと同じ方法です)。30は単に間違っています。

結果として、DESERT-TO-TABLEがメモリにオブジェクト番号を書き込み始めるとき、アドレス11129には書き込みません。アドレス30以降のメモリを上書きします。なんてこった。

TABLE-TO-DESERTルーチンも同様の方法でデフォルトのグローバル引数を使用しています。そのため、オブジェクトリストをアドレス30から取得し、一見正しい結果を生成します。しかし、メモリが踏みつけられています。


では、そのアドレスには何があるのでしょうか?

メモリの最初の64バイトはヘッダーデータですが、ヘッダー全体が使用されているわけではありません。全くの偶然ですが、Z-machineバージョン3ではアドレス0〜29のみが意味を持ちます。もしDESERT-TABLEが3番目のグローバル、インデックス18だったら、このバグはゲームのシリアル番号を破損させていたでしょう!それはもっと明白だったでしょう。

したがって、アドレス30〜63は未使用ですが、アドレス64は省略データの開始地点です。これはZ-machineのテキスト圧縮スキームの一部です:頻繁に出現するため、取り出して数ビットで置き換えることができる96個の単語のリストです。

予測:砂漠に9つのオブジェクトをドロップして(そして立ち去って)しまうと、最後のオブジェクトが省略テーブルの開始部分を上書きします。

これを調整するのは少し面倒です。ドロップされたオブジェクトは、単純に消えてしまう確率が3分の1であることを思い出してください。私はたくさんのものをそこに運び出して、何度か試さなければなりませんでした。しかし、成功し、次にゲームが表示したテキストは次のようになりました:

Desert You are in the desert, a vast wasteland of sand and heat. A small lizard pokes its head up from You sands and asks You shortest route to Times Square. You scratch your head for a moment and when you remember You proper subway line to recommend to it, you notice it's disappeared.

これはもちろん、熱による幻覚ですが、「the」(最初の省略形)という単語が「You」(2番目の省略形)に置き換えられていることに注目してください。これは、初期の文字列データが、終端子がないジャンクによって上書きされていることを示しており、そのためプリントルーチンは次の有効な文字列に進み続けます。

別のテストでは、インタプリタをクラッシュさせることに成功しました。おそらく、最初の省略形を、最初の省略形を表すビットで上書きしたため、プリントルーチンが無限ループに陥ったのだと思います。ご存知の通り。


よし!バグが実証されました!何を学びましたか?

このバグは出荷され、誰もそれに気づきませんでした。私が子供の頃にInfidelをプレイして砂漠を探索したとき、私のゲームはメモリを破損していました。他のすべてのプレイヤー、Infocomのプレイテスターでさえも同様でした。

おそらく、誰も無限の砂漠に8つ以上のオブジェクトをドロップしようとしなかったのでしょう。なぜそうするでしょうか?そこには何もありません!どこへ行くにも途中にありません。このメカニズム全体は、ピラミッドを発見していないプレイヤーを一時的に引き留めるためだけに存在します。細部へのこだわりはInfocomの典型ですが、そのエリアはあまりプレイテストされなかったに違いありません。

(Infocomのテストログを調べて、バグの痕跡が現れたかどうかを確認したいです。Infocom Cabinetには関連するものはないようです。そのようなものを見つけたら知らせてください。)

1984年のゲームの改訂版では、このバグに対処しませんでした。InfocomにはVisible Zorkerのようなものは何もありませんでした。メモリを検査するためのデバッグツールを持っていたかもしれませんが、誰もこれらのルーチンとそのストレージに適用しようとは考えませんでした。

後続のゲームで同様のバグが存在するかどうか、またはコンパイラによって正しく処理されているかどうかは調査していません。注意しておきます。

バグを修正するにはどうすればよいでしょうか?簡単です:TBLの引数デフォルトを削除し、代わりにルーチンを<SET TBL ,DESERT-TABLE>で開始します。または、DESERT-TABLEをルーチンに2番目の引数として渡します。どちらでも機能します。

同様のバグを持つルーチンのペアPROP-TO-TBL、TBL-TO-PROPがあり、PROP-TBLテーブル(アドレス11329、グローバル番号22)でも同様です。これらのルーチンには正直少し困惑しています。砂に掘れる穴(これらは砂漠の部屋にCAPACITYプロパティとして格納されています)で同様のシャッフル作業を行っているように見えます。しかし、ゲームはENDLESS-DESERTで掘ることを許可していません。「地面が硬すぎます」と表示されます。そのため、これらのルーチンは無用に見えます。開発中に削除された、以前の機能の残骸かもしれません。おそらく、シリアル番号を破損させたためです!

もし私がInfidelを更新するなら(riffing itするのではなく)、砂漠で無意味な穴を掘る能力を確実に回復させるでしょう。そのような無意味な詳細は、IFの最大の喜びの一つです。