6502逆アセンブラに関する考察 その3
前回、アドレス単位のコード解析について考察しました。今回はその結果を元に制御フローを考慮したコード判定を行うことを考えます。
このパスは誤判定を避けるため、極力保守的な方針で解析を行います。まずは6502の制御フローについて再確認します。
制御フロー命令
6502の大半の命令は直線的に実行されます(実行後にプログラムカウンタが直後のアドレスを指す)。こうならない可能性があるのは以下の命令です:
- BRK
- KIL (12種類)
- 分岐命令 (8種類)
- JSR
- RTI
- RTS
- JMP abs
- JMP ind
これらを「制御フロー命令」と呼ぶことにします。
ただし、割り込みを考慮すると任意の命令実行後にプログラムカウンタが書き換わる可能性があります(例えば、読み書きすると即座に割り込みを発生するようなI/Oレジスタを考えることができる。また、BRK が割り込みハイジャックによりNMIルーチンへ飛ぶケースなどもありうる)。とはいえこれは特殊ケースなので当面は無視します。
全ての制御フロー命令について、実行後の飛び先(割り込みは無視する)を考えると:
| 命令 | 飛び先の数 | 特定可? |
|---|---|---|
| KIL | 0 | |
| JSR | 1 | 可 |
| JMP abs | 1 | 可 |
| BRK | 1 | 割り込みベクタがわかれば可 |
| JMP ind | 1 | 基本的に不可 |
| RTS | 1 | 基本的に不可 |
| RTI | 1 | 基本的に不可 |
| 分岐 | 2 (or 1) | 可 |
「特定可」とは、飛び先の具体的なアドレスがわかるかどうかということです。今回はポインタ値やスタック状態の追跡までは行わない(一般的には不可能なケースもある)ので、JMP ind, RTS, RTI の飛び先は特定不可としています。
なお、JSR/RTS は必ずしも対になっているとは限らず、RTS があっても JSR の直後のアドレスに戻ってくるとは限りません(NESプログラムでは変則的なスタック操作がしばしば行われており、既に一つのテクニックと化しています)。また、分岐命令は実際には無条件分岐(飛び先がどちらか1通りのみ)だったり、2つの分岐先が一致するケース(かなり稀でしょうけど)もありえます。
制御フローを考慮したコード判定
制御フローを追うことでなるべく多くのアドレスを非 UNKNOWN 状態にすることを考えます。
CODE 状態のアドレスは順方向に影響を及ぼします。つまり、CODE 状態のアドレスからの制御フローは基本的に全て CODE となります。
NOTCODE 状態のアドレスは逆方向に影響を及ぼします。つまり、NOTCODE 状態のアドレスに到達する制御フローは基本的に全て NOTCODE となります。
分岐のない直線的な制御フローの場合について図示すると:
CODE-UNKNOWN-UNKNOWN-UNKNOWN-... -> CODE-CODE-CODE-CODE-... ...-UNKNOWN-UNKNOWN-UNKNOWN-NOTCODE -> ...-NOTCODE-NOTCODE-NOTCODE-NOTCODE
このように変換できるということです。
割り込みなど特殊な事情があると以下のように衝突が生じるケースも考えられます:
CODE-UNKNOWN-UNKNOWN-NOTCODE
この場合、途中の UNKNOWN が CODE, NOTCODE どちらになるかという問題が生じますが、この優先順位については後述します。
制御フローの探索自体は全て順方向に行い、UNKNOWN または CODE 状態のアドレスから開始します。UNKNOWN 状態のアドレスから開始するものを UNKNOWN 探索、CODE 状態のアドレスから開始するものを CODE 探索と呼ぶことにします。
UNKNOWN 探索では UNKNOWN -> NOTCODE の変化のみが起こります。CODE 探索では UNKNOWN -> CODE の変化のみが起こります。
簡単のため、まず UNKNOWN 探索を収束するまで行い、次に CODE 探索を収束するまで行います(これにより先に述べた優先順位が決まります)。なお、この順番が逆だと全体として収束しないことがありえます(後述)。
探索中、例えば JMP ind 命令などが現れて次アドレスが特定できなくなったり、次アドレスが入力ファイルの範囲外となることがあります。このような特定不可アドレスや範囲外アドレスが現れたらそれ以上制御フローを追跡できないので、そこで探索を打ち切ります。ただし範囲外アドレスについてはコード判定は通常通り付加します。
UNKNOWN 探索
各アドレスについて探索済みか否かのフラグを管理し、未探索アドレスがなくなるまで全ての UNKNOWN アドレスから探索を行います(探索中のループは前述のフラグで検出され、自動で探索が打ち切られます)。
現在見ているアドレスを orig とし、ここからの飛び先の数(0,1,2)によって処理を分けます。
飛び先が0通り (KIL 命令) の場合、単に探索を打ち切ります。
飛び先が1通りの場合、次アドレスを next とし、以下のように処理します:
| orig | next | 結果 |
|---|---|---|
| UNKNOWN | UNKNOWN | 探索続行 |
| UNKNOWN | CODE | 探索打ち切り |
| UNKNOWN | NOTCODE | orig を NOTCODE に。探索打ち切り |
飛び先が2通り(分岐命令)の場合、2通りの次アドレスを next1, next2 とし、以下のように処理します:
| orig | next1 | next2 | 結果 |
|---|---|---|---|
| UNKNOWN | UNKNOWN | UNKNOWN | next1, next2 から探索し、両方 NOTCODE なら orig を NOTCODE に。探索打ち切り |
| UNKNOWN | UNKNOWN | CODE | 探索打ち切り |
| UNKNOWN | UNKNOWN | NOTCODE | 次アドレスを next1 として探索続行 |
| UNKNOWN | CODE | * | 探索打ち切り |
| UNKNOWN | NOTCODE | NOTCODE | orig を NOTCODE に。探索打ち切り |
探索は順方向ですが、NOTCODE への変化は逆方向に起こるので、実際には探索時に制御フローを記録しておき、NOTCODE への変更は一括で行う必要があります。
CODE 探索
各アドレスについて探索済みか否かのフラグを管理し、未探索アドレスがなくなるまで全ての CODE アドレスから探索を行います(探索中のループは前述のフラグで検出され、自動で探索が打ち切られます)。
現在見ているアドレスを orig とし、ここからの飛び先の数(0,1,2)によって処理を分けます。
飛び先が0通り (KIL 命令) の場合、単に探索を打ち切ります。
飛び先が1通りの場合、次アドレスを next とし、以下のように処理します:
| orig | next | 結果 |
|---|---|---|
| CODE | UNKNOWN | next を CODE に。探索続行 |
| CODE | CODE | 探索続行 |
| CODE | NOTCODE | 探索打ち切り(割り込みなど特殊な事情があるとみなす) |
飛び先が2通り(分岐命令)の場合、2通りの次アドレスを next1, next2 とし、以下のように処理します:
| orig | next1 | next2 | 結果 |
|---|---|---|---|
| CODE | UNKNOWN | UNKNOWN | 探索打ち切り |
| CODE | UNKNOWN | CODE | 探索打ち切り |
| CODE | UNKNOWN | NOTCODE | 次アドレスを next1 として探索続行 |
| CODE | CODE | * | 探索打ち切り |
| CODE | NOTCODE | NOTCODE | 探索打ち切り(割り込みなど特殊な事情があるとみなす) |
CODE 探索より UNKNOWN 探索を先に行うのはここの分岐命令の処理のためです(CODE 探索が先だとここで UNKNOWN 探索が必要になってしまう)。
出力フェーズ
これは解析結果を参照しつつ入力ファイルを先頭から逆アセンブルしていくだけです。非公式命令については、CODE ならコード、UNKNOWN ならデータとして出力するのが妥当なところでしょう。
以上の処理を Python で実装したもの を置いておきます(ドキュメント未整備)。一応以前うまく行かなかったケースは改善されたっぽいですが、あんまりテストしてないのでまだ見落としなどがあるかもしれません^^;
アドレスラベルやコメントなどについても検討中ですが、これらについてはそもそもインタラクティブに操作できるUIがないと辛いものがあるんですよね(IDA はその点が有利なのは認めざるを得ない)。radare2 という解析ツールにちょっと期待してたりするんですが、これはレトロCPUはあまり眼中にないようで、6502モードだと命令の区切りがおかしくなったりするので今のところ微妙です。
NES以外については今のところあまり考察してませんが、BizHawk の Code/Data Logger がSNESなどに対応しているようなので、これを使えばある程度精度を上げられるかもしれません。
