6502逆アセンブラに関する考察 その2

前回述べた前提に基づいて解析フェーズを考えます。

簡単のため、解析はマルチパスで行うことにします。具体的には以下の通り:

  • アドレス単位のコード判定
  • 制御フローを考慮したコード判定(これ自体も複数パス。後述)

以前作ったC++版では解析を1パスで行っていましたが、これだとコードが複雑になる上、たまに致命的な誤判定が生じることがありました。簡単な例を見てみます:

80FF : db $02
8100 : db $60 ; 単独の RTS はデータとみなす(ヒューリスティック)
8101 : db $02

; ...

; ここは本来コードなのだが…
8200 : lda $00
8202 : ldx $01
8204 : ldy $02
8206 : jmp $8100 ; データ領域への JMP なので、ルーチン全体がデータとみなされてしまう!

このようなケースでは $8200- が全てデータとして出力されてしまいます。ここでは単独の RTS をデータとみなすというヒューリスティックが誤っていたためにこうなったわけですが、そうしたヒューリスティックと制御フロー解析が分離されていなかったために、一箇所の誤りが全体に波及し、しかもその修正が難しいという結果になりました。そこで今回は、ヒューリスティックを用いるのはアドレス単位のコード判定のみに限定し、制御フロー解析は誤判定を避けるため極力保守的に行うことにします。

アドレス単位のコード判定

最初のパスとして、制御フローを考慮せずに個々のアドレスに対するコード判定を行います。

といっても、実際にプログラムを動かすことなく100%の精度でコード判定を行うのは不可能です。例えばNESの場合は非公式命令は滅多に使われないだとか、ある範囲のアドレスは普通は読み書きしないなどといった事実からある程度の推測は可能ですが、例外は常にありえます。よって、このパスはハードコードされた基準ではなくユーザ設定に基づいて行います。出力がおかしくなったらここの設定を変えて再試行することになります。

なお、実際にプログラムを動かしたとしても、わかるのはあるアドレスが「コードである」ことだけです。このときあるアドレスが実行されなかったとしても、条件を変えれば実行される可能性があるわけで、あるアドレスが「コードでない」ことを100%保証することはできません。

とはいえ、設定としてある程度妥当なプリセットは考えられるので、それを以下で詳しく見ていきます。

NES用プリセット

最も保守的なものはこんな感じでしょうか:

  • KIL 命令 (12種類) は非コード
  • XAA 命令 (0x8C) は非コード
  • I/Oレジスタ ($2000-$4017) を実行するものは非コード
  • 書き込み専用レジスタ ($2000 など) を読み取るものは非コード
  • 読み込み専用レジスタ ($2002 など) に書き込むものは非コード*1

これは割と信頼できそうです。KIL, XAA はともに非公式命令で、前者はCPUを停止させ、後者はそもそも動作が不安定とされているので、少なくとも商用ゲームではまず使われないでしょう。I/Oレジスタに関しても妥当なところかと思います。

よりアグレッシブに行くなら、以下の条件を加えることが考えられます:

  • 全ての非公式命令は非コード
  • BRK 命令 (0x00) は非コード
  • RAMミラー ($0800-$1FFF) を読み書き/実行するものは非コード
  • PPUレジスタのミラー ($2008-$3FFF) を読み書きするものは非コード

これでも大抵はうまく行くと思いますが、非公式命令を使っている商用ゲームも存在します。BRK を禁止するとデータ領域がかなりきれいに出力されます*2が、これは公式命令で別に禁止されているわけでもないので、使っているゲームがあってもおかしくないと思います(私は見たことがありませんが)。ミラー領域に関してはそもそも仕様の範囲内なのかどうかよくわかりませんが、使っているのを見たことがないのでとりあえず入れてみました。

後はマッパーによっては $4018-$FFFF についても読み/書き/実行を制限できるので、メジャーなマッパーについてだけでもプリセットを作っておくと役立ちそうです。ただしこれにはちょっとした罠があります。例えばマッパー0のゲームは普通 $4018-$7FFF を読み取りませんが、任天堂『ゴルフ』ではオペコード兼オペランドのByteが存在するために $40A9 の読み取りが発生しています。

例外が全くない設定というのはなかなか難しいので、出力がおかしくなった場合は手動でコード判定を行い、残りの部分について自動解析を適用するという形になるかと思います。

実行記録の利用

実際にプログラムを実行することで、少なくとも実行された部分はコードだと判定できます。例えば FCEUX には Code/Data Logger (CDL) が付属しています。*3

ただし、FCEUX CDL はオペコードとオペランドを区別しないため、確実にコードと判定できるのはコード領域の先頭のみです。

次のパスでは、これらの手段で得られた結果を元に制御フローを考慮したコード判定を行います。具体的には次回。

*1:2017/03/02 追記: NES版アルカノイドはなぜか $2002 への書き込みを行っているので、これも確実とまではいえないようです。

*2:BRK は実質的に2Byte命令です。

*3:BizHawk の Code/Data Logger はNESには未対応のようです。

6502逆アセンブラに関する考察 その1

tl;dr: taotao54321/td6502

懲りずに6502逆アセンブラについて考えてみます。まあ素直に IDA を買えという話なのかもしれませんが、結構お高いですし、プロプライエタリでない選択肢があってもいいと思うので…。なお、私はNES以外のプラットフォームには詳しくないのでNESの話が多くなると思います。

何が問題か

要はなるべくコードとデータを自動で判別したいということですね。例えば以下のような出力はしてほしくないわけです:

; NES用プログラム(マッパー0とする)

lda $00         ; 不満: 直後がデータなんだから、ここもデータのはず
db $02          ; 非公式命令 (KIL) なのでデータとして出力
jmp ($5555)     ; 不満: $5555 には何も割り当てられてないんだから、普通はデータのはず

それで以前適当な自動判別機能が付いた逆アセンブラを作ってみたのですが、これは対象によってうまく行ったり行かなかったりで微妙だったので、この際きちんと考え直して文書として残しておこうと思ったわけです(大して高度なことではないですが)。

逆アセンブラの機能としては他にもアドレスラベルの処理やコメント付加、出力整形など色々な話題がありますが、ここではコード判定のみに絞って書くことにします。

前提

逆アセンブラを解析と出力の2フェーズに分けて考えます。

解析フェーズではアドレス空間 ($0000-$FFFF) 内の各アドレスについてコード判定を行い、判定結果として以下の3通りの値のうちいずれかを与えます:

  • CODE (コード。厳密にはオペコード)
  • NOTCODE (非コード。厳密には非オペコード)
  • UNKNOWN (不明)

初期状態では全アドレスが UNKNOWN です。ここから解析フェーズでなるべく多くのアドレスを非 UNKNOWN 状態にして(ただし誤判定は極力避ける)、出力フェーズではその結果を利用して出力を行います。

なお、難しくなりすぎるのでバンク切り替えの追跡までは行わないことにします。

次回から解析フェーズを考えていきます。

Python Packaging User Guide を訳してみた

Python

Python Packaging User Guide (PyPUG) を日本語訳してみました。Python のパッケージング周りは変化が激しいのでいつまで役に立つのかはわかりませんが…。

PyCon JP で毎年パッケージング関連の発表があるようなので、とりあえず現状を把握するにはこれを見るのがいいのかな?2016年の発表は YouTube で見られるようです:

Sphinx で日本語改行が空白になる件について

Sphinx日本ユーザ会の「不自然な空白が表示される」にある通り、japanesesupport.py を使うと解消されるようです。ただしこれをそのまま使うと改行だけでなくリンクの前後の空白なども潰されてしまい、英単語が頻繁に混じる文章だとかなりギチギチした見た目になります。Issues に置いてあるパッチ版を使うといい感じになるようです(なぜか issues が放置されてるので、もしかしたら何か問題があってマージされてないのかもしれませんが…)。

この問題って Sphinx だけでなく markdown とか色々なところで(このブログでも)現れてますが、どこも大抵放置してるんですよね。多分皆ブラウザが対応しないのが悪いと思ってるということなんでしょうけど。

FC 『AD&D プールオブレイディアンス』を少し解析してみた

相当手強いのでとりあえず不完全ですが途中結果だけ置いておきます。

今までで一番読みにくいコードだと感じています。バンク切り替えが8K単位になっている上に、同じバンクが異なるアドレスにロードされたりしてややこしいんですよね…。ルーチンの先頭でいちいちレジスタをスタックに退避していることが多かったり、他のゲームではあまり見られない特徴があるので、もしかしたらアセンブラでなく何らかの高級言語で書かれているのかもしれません。

pyvenvをactivateすると"parameter not set"とか言われる場合の対処

Python zsh

zshからpyvenvをactivateしようとすると

$ source bin/activate
deactivate:2: _OLD_VIRTUAL_PATH: parameter not set

というエラーになることがあります。これはzshでno_unsetオプションを設定していると起こります。no_unsetオプションを設定したままこれを回避するには、無名関数を使って

$ (){ setopt local_options unset; source bin/activate }

とすればいいようです。deactivate時も同様に

$ (){ setopt local_options unset; deactivate }

でOK。

OpenAI GymのPong-ram用資料

OpenAI GymのPong-ram環境用のメモ。

とりあえずメモリアドレスを軽く調べました(趣旨的には解析とか一切なしで解くことが求められているのでしょうけど)。なお、Atari2600は $80-$FF の128 バイトがRAMとなっています(参考: Atari 2600 Specifications)。

address type description
$88 U8 フレームカウンタ
$8D U8 COMスコア
$8E U8 PLAYERスコア
$95 U8 COM座標y
$B1 U8 ボール座標x
$B6 U8 ボール座標y
$B8 S8 ボール速度y?
$BA S8 -1 * ボール速度x
$BC U8 PLAYER座標y

ボールのy方向の動きについては完全には理解していません($B8 に疑問符がついてるのはそのため)。もしかしたらサブピクセルまで計算されていたり、場合により $B8 が2回加えられるかもしれません。ボールの動き計算コード自体は $F554 にあります。

自機の動きには多少の慣性がかかりますが、これをメモリ内容だけで把握する方法はよくわかっていません。多分 $84 を目的座標として前回述べたような処理が行われるのだと思いますが、$84 は1Fおきに全く関係ない値に変わるため、その他のアドレスも参照しないと自機の慣性は正しく把握できないと思います。

とりあえず自機座標とボール座標/速度がわかれば最低限足りるとは思いますが、慣性も考慮しないと得点率が悪くなるかもしれません。手でプレイするとわかりますが適切な角度で打ち返さないとCOMは失点してくれないので、結構繊細な操作が要求されるんですよね…。

ただ、Pong-ram環境では1ステップごとに2-4フレーム進むようなので、そこまで繊細なことを考えても仕方ないのかもしれません。この辺はやってみないとわからない感じですね。

環境に関する情報をまとめておきます:

attribute value
env.action_space Discrete(6)
env.observation_space Box(128,)
env.reward_range (-inf,inf)
env.spec.timestep_limit 10000

actionの意味は以下の通りと思われます(2と4, 3と5の移動量は多分同じだと思いますが確証はありません):

値 意味
0,1 何もしない
2,4 上へ移動
3,5 下へ移動

observationは128バイトのRAMをそのまま格納した配列です。なお、配列の要素は numpy.uint8 で、Pythonの int と振る舞いが異なるので注意が必要です。

1点取ったとき 1.0, 1点取られたとき -1.0 の報酬が得られるようです。

ターン制限(10000)があるので、単に失点しないだけでなく得点率が求められると思われます。1ステップあたり2-4フレーム進むので、最悪の場合20000フレームで打ち切られます。なお、全く操作せずパーフェクト負けした場合は大体1000ステップ程度かかるようです。

メモリを見つつ1ステップずつ動かせるスクリプトを書いたので一応貼っておきます。