読者です 読者をやめる 読者になる 読者になる

逆アセンブラについて

ゲーム

Web上で動作し、コメントを共有できる、というコンセプトのNES用逆アセンブラを見つけました:

ただしこれは試作段階のようで、商用ROMを食わせるとまともに逆アセンブルしてくれないので実戦投入は厳しそうです。しかし、

アセンブルはみんなでやった方が楽しい

ワークエリアのシンボルとかもシェアできるようになるとすごく便利

というのは全くその通りで、いずれそういう仕組みが欲しいところだとは常々思っています。実際、私の力ではFC初期の容量の少ない(PRG 16Kとか)ゲームでさえ一人で全部解析するのは厳しいですし、そもそもコード/データ領域の判別やメモリアドレスの調査だけでも相当時間がかかるので、その辺の作業を複数人で分担し、成果を共有できるようになれば色々可能性が広がるのではないかと思っています。

しかし現状は

アセンブラってあんまりいいのがないんですよね

に同意せざるを得ないわけですが、逆アセンブラの開発があまり活発でないのは「コード/データの判別」という問題を根本的には解決できないというのが大きな理由だと思います(SNESの場合、レジスタサイズが可変なので更にめんどくさい)。上記記事の逆アセンブラでも一応その点の解決は試みているようですが、今のところ商用ROMを食わせるとボロボロです。私もtd6502なんてのを作ったりしましたが、やはり一部のROMでは誤認識でボロボロになります(あと若干バグが残ってると思います)。

コード/データ判別精度を上げる方法として、Recursive Traversal法というものがあるようです(上記記事の逆アセンブラtd6502で一応実装されている、と思う)。詳細はDisassembling Obfuscated Assemblyなどが参考になります。平たく言えば「制御フローをトレースし、コードになりえない領域はデータとみなす」という手法ですが、先の記事でも触れられているように無条件分岐があると必ずしも正しく動作しないのと、NESの場合は間接ジャンプやスタック操作による変則的な制御フローがあるので、やはり完璧には程遠いです。なお、単にバイト列を先頭からなめる方式はLinear Sweep法と呼ばれているようです(md6502などが該当します)。

この他に、「隠れマルコフモデルに基づく確率的逆アセンブル」というものもあるようです。ネット上に論文があるようですが、直リンクしていいのかどうかわからないので「IATエントリ格納場所の特定方法」とか "Specifying the Addresses of IAT Entries" で検索すると見つかるとだけ言っておきます。平たく言えば「たくさん呼び出されているコードは真のコードである可能性が高いよね」という発想…だと思います。

しかし、こういった手法はあくまでヒューリスティックに過ぎないので、どうやっても100%誤認識しないものを作るのは不可能だと思います。大まかな解析には役立つと思いますが、最終的には人手で判別しなければならない場合が多いでしょう(FCEUX CDLのような動的解析*1も併用すると多少楽になるかも)。

実際、NESに限ってみても、完璧を期すとあまり多くの仮定を置けないように思います:

  • 商用ソフトでは隠し命令が使われることは稀だが、皆無ではない
  • ほとんどの場合、コード領域内のByteはオペコード/オペランドのどちらかだが、稀に両者を兼ねるものがある
  • 普通は JSR 命令の次はコードだが、呼び出し先でスタックをいじっている場合そうとは限らない(例えば、ギャラクシアンの $E44B 呼び出しや、スーパースターフォースの $D2FC 呼び出しの直後はコードでない)
  • 割り込みを考慮すると理論上はあらゆるアドレスがコード/データ境界になりうる

また、バンク切り替えまで考慮するとなると正直私の力ではどうにもならない気がします^^;

というわけで、むやみに賢くなろうとしても得るものはあまりなく、むしろメタデータ(コード/データフラグ、シンボル情報、コメントなど)に関するフォーマットを定め、そのためのツールを充実させるのが先決なのかなぁと思います。Recursive Traversal法などはあくまでメタデータ作成時の補助として使い、最終的にはメタデータのみに基づいて逆アセンブルするのが本筋なのではないかと。

あとは出力形式をいろいろ選べると便利かもしれないですね(nesasm, ca65, md6502などなど)。

今のところ構想すら全く見えてない状態ですが、とりあえず妄想ということで。やるとすれば少なくとも .nes ファイルを丸ごと処理するような形ではなく、バンクごとに別個に処理する形になるのではないかと思います(マッパーが絡むと非常に面倒なので。特にFDSとか)。

*1:FCEUX CDLはオペコードとオペランドを一緒くたにコードとして記録するのが若干不満なところですが