🕶️
線形逆アセンブラの問題と、再帰逆アセンブラでの解決について

2025/01/29に公開
（本記事は正確性に配慮して記述しておりますが、私の知識不足で誤りが含まれている可能性もある旨、ご了承いただけましたら幸いです。）

 線形逆アセンブラ、再帰逆アセンブラについて逆アセンブラの種類には、主に線形逆アセンブラと呼ばれる方法と、再帰逆アセンブラと呼ばれる方法の2パターンがある。

（書籍やサイトにより呼称はばらついている気がする。）

 そもそも逆アセンブラとはCPUを動かすための入力はバイナリである。例えば加算を行なう場合、x86系ならば0x83 0xc0 0x01と言うバイナリ列を送ることで加算命令を実行してくれる。

昨今のCPU処理は、このような操作を繰り返し行うことで実現している。
一方、上記の0x83 0xc0 0x01を人間が見たところで何のことかはさっぱり分からない。こうなると、各命令列の意味を人間でもぱっと見わかるような形式に直したくなるものである。

そこで行うのが 逆アセンブラ である。

これはバイナリを人間が読める低レイヤーな言語（つまりアセンブラ言語）に変換するものであり、例えば、先ほどの0x83 0xc0 0x01なら add 0x01, %eax と言う形式に変換される。

 逆アセンブラの方法逆アセンブラの仕組みは（命令列の解読に限っては）そこまで複雑ではない。　　

各CPUの仕様書には、前記のバイナリ列がなんの命令に紐づくか記載されているので、それに従って各バイナリ列を変換すればいい。
例えば先ほどの命令列なら、公式リファレンスに「0x83 から始まるのはadd命令で、その後ろにくっついてる値はこんな意味だよ〜」みたいな事が書かれてるので
0x83,0xc0,0x01,0x83,0xc0,0x02
みたいなバイナリファイルを逆アセンブルしたければ、それぞれの命令列を置き換えて
add 0x01, %eax
add 0x02, %eax
と出力してやればいい。

 線形逆アセンブラこう聞くと「つまりプログラムの先頭からバイナリを読み取りつつ、対応する形式に置き換えていけばいいだけか。簡単やん。」と思うかもしれない（俺は思った）

そのような手法は 線形逆アセンブラ と呼ばれ、最も一般的に用いられている手法である。

しかし、これで全部が収まるほど話は単純ではない。

 線形逆アセンブラの課題一般的なCPUは、今どこの命令を読んでいるのかを覚えておきながら処理を実行する。

例えば、メモリ上の0x0番目から4バイト分の命令を読み出したなら、読んでいる位置を+0x4しておき、次の読み出しタイミングでは0x4番目から命令を読み出す。

また、もしif文や関数呼び出しがあった場合には、読んでいる位置を、対応する命令があるところに変更した上で、次の命令を読み出していく。（このような読み出し位置のことを PC(プログラムカウンタ) と言う）
厄介なのは、このPCは（CPUの特別な違反などがない限り）どこにでも位置することができるということである。これはつまり 意味のないバイナリ列を注入つつ、実行時にだけPCが違うところに行くよう細工する事で線形逆アセンブラを騙す ことができてしまう事になる。
例えばx86を例に、線形逆アセンブラを誤魔化してみる。

まずは適当なコードを用意する。（プログラムの中身に大した意味はない）
int hoge(int argc, char **argv) {
  argc += 1;
  if (argc == 1) {
    return 1;
  } else if (argc == 2) {
    return 2;
  } else {
    return 3;
  }
}
これをコンパイルし、objdumpで逆アセンブルすると以下のようになる。
0000000000000000 <hoge>:
       0: 55                           	pushq	%rbp
       1: 48 89 e5                     	movq	%rsp, %rbp
       4: c7 45 fc 00 00 00 00         	movl	$0x0, -0x4(%rbp)
       b: 89 7d f8                     	movl	%edi, -0x8(%rbp)
       e: 48 89 75 f0                  	movq	%rsi, -0x10(%rbp)
      12: 8b 45 f8                     	movl	-0x8(%rbp), %eax
      15: 83 c0 01                     	addl	$0x1, %eax
      18: 89 45 f8                     	movl	%eax, -0x8(%rbp)
      1b: 83 7d f8 01                  	cmpl	$0x1, -0x8(%rbp)
      1f: 0f 85 0c 00 00 00            	jne	0x31 <main+0x31>
      25: c7 45 fc 01 00 00 00         	movl	$0x1, -0x4(%rbp)
      2c: e9 1d 00 00 00               	jmp	0x4e <main+0x4e>
      31: 83 7d f8 02                  	cmpl	$0x2, -0x8(%rbp)
      35: 0f 85 0c 00 00 00            	jne	0x47 <main+0x47>
      3b: c7 45 fc 02 00 00 00         	movl	$0x2, -0x4(%rbp)
      42: e9 07 00 00 00               	jmp	0x4e <main+0x4e>
      47: c7 45 fc 03 00 00 00         	movl	$0x3, -0x4(%rbp)
      4e: 8b 45 fc                     	movl	-0x4(%rbp), %eax
      51: 5d                           	popq	%rbp
      52: c3                           	retq
今今はなんの変哲もないアセンブラである。しかし、例えばこのバイナリの先頭に0x83を注入してから再度逆アセンブルすると、途中まで全く違う命令列に化けてしまう。
0000000000000000 <_binary___a_bin_start>:
       0: 83 55 b8 89                  	adcl	$-0x77, -0x48(%rbp)
       4: e5 c7                        	inl	$0xc7, %eax
       6: 45 fc                        	cld
       8: 00 00                        	addb	%al, (%rax)
       a: 00 00                        	addb	%al, (%rax)
       c: 89 7d f8                     	movl	%edi, -0x8(%rbp)
       # ↑までの命令列が、全く違う命令として出力されていることがわかる
       f: 48 89 75 f0                  	movq	%rsi, -0x10(%rbp)
      13: 8b 45 f8                     	movl	-0x8(%rbp), %eax
      16: 83 c0 01                     	addl	$0x1, %eax
      19: 89 45 f8                     	movl	%eax, -0x8(%rbp)
      1c: 83 7d f8 01                  	cmpl	$0x1, -0x8(%rbp)
      20: 0f 85 0c 00 00 00            	jne	0x32 <_binary___a_bin_start+0x32>
      26: c7 45 fc 01 00 00 00         	movl	$0x1, -0x4(%rbp)
      2d: e9 1d 00 00 00               	jmp	0x4f <_binary___a_bin_start+0x4f>
      32: 83 7d f8 02                  	cmpl	$0x2, -0x8(%rbp)
      36: 0f 85 0c 00 00 00            	jne	0x48 <_binary___a_bin_start+0x48>
      3c: c7 45 fc 02 00 00 00         	movl	$0x2, -0x4(%rbp)
      43: e9 07 00 00 00               	jmp	0x4f <_binary___a_bin_start+0x4f>
      48: c7 45 fc 03 00 00 00         	movl	$0x3, -0x4(%rbp)
      4f: 8b 45 fc                     	movl	-0x4(%rbp), %eax
      52: 5d                           	popq	%rbp
      53: c3                           	retq
あとは、実行時だけhoge関数+0x1バイト目から処理を開始するよう、PC位置をずらしてしまえば良い。

このように、線形逆アセンブラでは偽造されたバイトコードを見破れず、重要な命令を見落としてしまう可能性がある。

 再帰逆アセンブラ前記課題の解決策の一つであり、順次逆アセンブラするのではなく、 ジャンプ命令やret命令を手がかりに 逆アセンブルを実行する。

例えば先ほどの命令列であれば、0x1番目に飛ばすjmp命令(PC位置を書き換える命令)を検出したあと、retq(元の位置に戻る命令)を検出したら元の解析位置に戻るようにする。これを繰り返していくことで、（原理上は）実行時と同じフローで解析できる。

一方で、この手法にもデメリットはある。例えば、jmp系命令にジャンプテーブルやレジスタ値が使われている場合、実質再帰逆アセンブラは使えない可能性が高い。

（理論上は解析可能かもしれないが、関連する他のコードや外部ライブラリも解析しなければならないケースが多く、結果的に計算量が爆発してしまう。）

 各種逆アセンブラの種類線形逆アセンブラは、gnu binutilsのobjdump、llvmツールチェインのllvm-objdumpなどで実行可能である。

再帰逆アセンブラは、IDA Proやradare2のような解析ツールを用いるか、capstone等を利用して自作することで実行可能である。

 終わりに筆者は普段aarch32/64メインでいじっているのであまり知らないのですが、x86は可変長ISAゆえにこの手の誤魔化しが普通のバイナリでも起こると聞いたような気がします(要出典)

日常的にマルウェアや高難読化バイナリを扱うセキュリティ系の方々にとっては初歩中の初歩かと思いますが、何かの参考になれば幸いです。
最後に、本当に念の為ですが

上記した各手法は悪用せず、あくまで自作バイナリや法的に問題のないバイナリへの利用に止めるようお願いいたします。

（リバースエンジニアリングは法律を守って正しくご安全に！）
線形逆アセンブラ、再帰逆アセンブラについて

そもそも逆アセンブラとは

逆アセンブラの方法

線形逆アセンブラ

線形逆アセンブラの課題

再帰逆アセンブラ

各種逆アセンブラの種類

終わりに

Discussion
