Ｃの逆コンパイラはどこまで実現可能か，Javaはなぜ逆コンパイルされやすいのか？

自称・リバースエンジニアリング技術のホビー研究家です．(^^;
逆コンパイラ (デコンパイラ，decompiler) の可能性と限界，プログラムの自動解析の難易度等について日頃考えていることをまとめてみました． (こうすること自体が研究を進めることにもなるので．)

注意： このページの内容の多くは現時点での私の直観・主観・推測等に基づくものであり，正当性は全く保証の限りではありません．また，今後の研究の進展 (または行き詰まり(苦笑)) により，内容が変化する可能性は大いにあります．

■関連ページ

はじめに
動機
Ｃの逆コンパイルはどこまで可能か？
Java はなぜ逆コンパイルされやすいのか？
C++ の逆コンパイラは C よりもはるかに困難
逆コンパイラは何の役に立つか？
逆コンパイラ研究に必要な技術・知識・参考図書
1. 参考図書
サイト内関連ページ
外部へのリンク
更新履歴

逆コンパイルについて Web 上で調べてみると，洋の東西を問わず「C/C++ の逆コンパイルは可能か？」とか「C/C++ の逆コンパイラはどこで手に入るか？」という質問をする人 (明らかに，(ネイティブ) コンパイラが何をするのか１ミリも理解していない初心者) がいて，それに対しては「元通りのソースを復元することは不可能」というのがお決まりの反応のようだ．そしてその理由もだいたい判で押したように「コメントやローカル変数名は復元できないから．」まあ，コンパイラについて１ミリ以上理解している人なら誰でも知ってることだし，「完全復元」を否定するにはそれだけで十分だからだろう．

Is there any hope of a decompiler that would convert an executable program into C/C++ code?
(もっとも，このページでも最後の追記で最近の逆コンパイル技術の進歩を認めている．)

確かに回答とその理由自体は全く正しい．しかしそれ以前に「逆コンパイルは可能か？」という質問に対して「元のソースと同じにならないから不可能」と答える理由がわからない．多くの場合「逆コンパイルは可能か？」と質問する初心者が求めてるのは，理解困難な機械語を，(プログラムの意味を変えずに) それよりずっと理解しやすい高級言語の構文で見せてほしい，ということのはずだ^注１．文字コード変換ツールじゃあるまいし，元のソースと１文字も違わないものを求めているわけじゃない^注２．

そもそも，元のソースが理解しやすいという保証はないでしょ？(笑) 仕事で他人の書いた (ヘタクソな) ソースを理解・メンテしなきゃならないはめになった時， (プログラムの動作が変わらないように注意しながら)

意味不明の関数名や変数名を変更したり，
ぐちゃぐちゃの制御フローを書き直したり，
1024行もある単一の関数 (main() とか main(argc, argv) とか main(argc, argv, envp) とか…) を複数の関数に分割したり

したことありませんか？

そこでこのページでは，まずＣの場合について，コンパイルされた機械語コードをＣに (復元というより) 変換することはどこまで可能かということについて考えてみる．そしてそれに基づき，Java がなぜ逆コンパイルされやすいのかを説明する．

^注１) とはいえ，C/C++ の逆コンパイラが実現不可能なことさえわかっていないレベルの初心者が，逆コンパイラの吐き出すソースを理解するのは到底無理 (爆笑)． C/C++ の逆コンパイラを探しまわっている人は，その前に何か興味のあるオープンソースのコードをプリプロセッサに通した後で読んでみるといい (gcc の場合は -E オプションを指定してできる *.i ファイルを読む)．これを読んで理解できない人は，奇跡的に C/C++ の逆コンパイラを手に入れられたとしても， それが吐き出すソースを理解できる可能性は全くないのでさっさとあきらめて10年間修行した方がいい (何の？)． *.i ファイルでさえ，逆コンパイラ出力よりずっと理解しやすいのだから (ただし元のソースがダメすぎる場合を除く)．もっとも，(使いものになる) Ｃの逆コンパイラなんて存在しないし， C++ の逆コンパイラに至っては (使えるレベルどころか) 影も形もないのだから，実際には「それらが吐き出すソースを理解できない」という心配は全くないので安心してください (笑)．

^注２) ソースファイルをうっかり消してしまった開発者本人は別 (笑)．私にはそれに少し似た経験がある．以前勤めていた会社で，別の開発部門から「客先にリリースした実行ファイルのソースのバージョンがどれだかわからなくなったので調べてほしい」と依頼された (マヌケすぎる話だ…)．結果だけを書くと，完全に一致するソースはなくて，そのうちの一つのバッファサイズだけを変更したものがリリースされていた．

私がリバースエンジニアリング技術，特に逆コンパイラに興味を持っている理由．

まず無用な誤解を避けるために書いておくが，私は他人の書いたプログラムをクラックしたいから逆コンパイラを研究しているわけではない．一般論として，プログラミングが好きで逆コンパイラを作れるだけの技術があるならば，他人の書いたプログラムをわざわざクラックするよりも，自分で書く方を選ぶだろう (その方が面白いし)．私がクラックしてみたいと思うソフトがあるとすれば次のようなものだが，幸か不幸か滅多にお目にかかれない．
- 魔法のような機能
  どうやってその機能を実現しているのか，アルゴリズムが全く想像できない場合．
- 圧倒的に高速または省メモリ
  既知の方法では到底実現できそうにないほど高速または省メモリな場合．
えっ，じゃ具体的にどんなプログラムならクラックしてみたいと思うかって…？
そうですね … 仮に「ソースを完璧に復元できる C/C++ 逆コンパイラ」なんてものがあったら，是非それ自身を逆コンパイルしてみたいですね．(爆)
「プログラムを理解するプログラム」や「プログラムを作るプログラム」といった， AI (~~Artificial Idiot，人工痴呆~~ Artificial Intelligence，人工知能) 的なテーマに興味があるから．プログラムがプログラムを理解するための一つの通過点として，そして理解していることを示す一つの方法として，Ｃ言語の逆コンパイラを作ってみたいと思っている．
グラフアルゴリズム (グラフ理論的アルゴリズム) も大好きなんだけど，プログラム解析はその重要な応用分野であり，新しいアルゴリズムを考える機会でもある．私にとっては一粒で二度面白い．＼(^o^)／

グラフアルゴリズムのどこがそんなに面白いかというと，局所的な情報を積み重ねて全体的な構造や性質を認識できるところ． (だからこそプログラム解析にも必要．)

他方，仕事でグラフアルゴリズムを使う機会はほとんどない．
(十数年前にごくごく初歩的なグラフアルゴリズム (サイクル検出) を使っただけ．orz)
一生に一度は，他人が逆立ちしても作れないようなソフトを作ってみたいから．(笑)
ちなみに，私は逆立ちできません．(^^;)

そういうわけで，これは私のライフワークにするつもり．

逆コンパイルの難易度は，C の構文要素ごとに大きく異なる．以下，最初に逆コンパイル絶対不可能な要素を示し，続いて容易な順に列挙する．ただしこの難易度ランキングは，今後の研究の進展または行き詰まりにより，変化する可能性は大いにある．

絶対不可能！

コンパイルによって完全に情報が失われる (実行ファイルには全く含まれない^注３) ので復元が絶対不可能なもの．これらを自動的に復元することはスッパリあきらめてください．いやだといっても無駄です．ない袖は振れません．卵焼きから卵の殻を復元できると思う？卵焼きに卵の殻を入れる人なんかいないでしょ！殻入りの卵焼きを食べたいと思う？(笑)

コメント
外部リンケージを持たない変数名・関数名 (auto 変数名，static 変数名/関数名)
構造体・共用体のタグ名およびメンバ名
構造体・共用体の，全く使用されていないメンバ (名前だけでなく型・サイズ・オフセットなどすべて)
typedef した型名
マクロの定義および呼び出し (inline 関数や C++ の template なども同様)
これらはせいぜいインライン展開後のソースしか復元できない．

つまり，普通ヘッダファイルに書かれる情報は絶対復元できないものが多い．

逆コンパイラがこれら (コメントとマクロ以外) をソースに (復元ではなく) 変換するとしたら，「名前の種類」＋「番号」のようなものにならざるを得ない (例：var1，StaticFunc8，Struct15，Union2，Struct1_Member1 など)．

したがって逆コンパイラで見やすいソースを復元しようとすれば，コンパイラのように最初にオプションを指定してあとはおまかせというわけにはいかない．そこで GUI を用いた対話型ツール (最近流行の「統合開発環境」ならぬ「統合解析環境」？) を提供し，逆コンパイル結果を見ながら名前を変更できるようにする方がよいと思う．

■2010/10/03(日) 追記

ただし使用しているコンパイラやライブラリを (バージョンを含めて) 特定できて，それらのヘッダファイルが入手できる場合，ターゲットと照合することによって元の名前を復元できる部分もある．

^注３) デバッグモードでコンパイルした場合は含まれる処理系もある．

超簡単！

外部リンケージ (extern) を持つ変数名・関数名
これらが超簡単に復元できることは説明不要だろう．ただしリンク後に実行ファイルからシンボル情報が削除されていなければの話．今ちょっと VC2003 で確認してみたところ，たとえ Debug モードでビルドしたとしても，デバッグ用シンボル情報は exe ファイルではなく pdb ファイルに入るようなので， exe ファイルだけからは復元不可能ということになる．orz
OS の API (システムコール) 名や共有ライブラリ (Windows では DLL) が export している関数・変数名などはリンク後も削除するわけにはいかないので復元可能．

extern "C" 宣言されていない C++ の識別子であれば，型名も復元可能．ただし復元できるのは型名だけであって，型定義は全く別の話．また，mangling (型名を文字列に変換してリンケージ名に埋め込む) の方法がコンパイラにより異なるため，使用したコンパイラが特定できることが前提．実用上は，既知の複数のコンパイラ用の demangler を用意しておいて，片っ端から試すという方法でコンパイラを特定するという方法もある．

簡単？

スカラ型変数
変数名の復元については上に書いたとおり，超簡単な場合と絶対不可能な場合の両極端．
変数の型は整数型 (符号付 (signed) または無符号 (unsigned)) か浮動小数 (単精度 (float) または倍精度 (double)) のいずれかだが，基本的には変数にアクセスする機械語命令の種類やアドレシングモードで型とサイズを判別できる．それで判別できない場合は，データフローを解析してどのような演算に使われているか，またはどのような演算の結果が格納されたのかを調べれば判別できるだろう．

難易度を「簡単？」としたが，それは実際には構造体や共用体が使用されていないことが事前に想定できる場合に限る．メモリ上の基本データ型の変数がスカラ型であると判断するためには，その変数のスコープ全体^注４にわたってその変数が存在しているメモリ領域の使用状況を調べ，その変数が構造体や共用体のメンバでないことを確認する必要がある．したがって実際にスカラ型変数を復元する難易度は，後述の「構造体定義」の場合とあまり変わらない．
関数呼び出し，式
関数呼び出しは，CALL 命令とその前後のスタック操作命令から復元できるはず．式 (一般には関数呼び出しを含む) は，データフロー解析により比較的簡単に復元できるはず．
2011/01/14(金) 追記

ただし，CALL/RET 命令は逆コンパイル対策のため偽装される可能性もある． CALL 命令の (直接または間接の) 呼び出し先でリターンアドレスをこっそり書き換えていた場合，「CALL命令＝関数呼び出し，RET命令＝関数からのリターン」と無邪気に信じ込んでいるナイーブな逆コンパイラはコロッと騙されて間違った結果を返すだろう．

また，一部の演算子を専用のライブラリ関数の呼び出しに変換する処理系では，コンパイラの特定が必要．例えば乗除算命令を持たない CPU 用のコンパイラでは，乗除算演算子をライブラリ関数の呼び出しに変換するだろうから，それらの関数名を事前に知っておく必要がある．

^注４) 大域変数や static 変数であればアプリケーション全体，auto 変数であればそれを定義している関数全体．ただし後者で変数のアドレスが別の関数に渡されていればその関数も含むし，グローバル変数にコピーされていればそれを参照しているすべての関数も含む．なお「static 変数のスコープはアプリケーション全体じゃなくてソースファイル内だ」とツッコミたい人もいるかもしれないが，リンクされた実行ファイルではソースファイルの境界など跡形もなくなっているので，アプリケーション全体を調べるしかない．

やや困難？

構造体定義
書きかけです．
とりあえずこちら→ OKWave QNo.3043962：デコンパイル？について (回答 No.5)

困難？

制御構造
書きかけです．
とりあえずこちら→ OKWave QNo.3043962：デコンパイル？について (回答 No.5)
参考：Javaバイトコードをデコンパイルする効果的なアルゴリズム
(具体例で逆コンパイル (制御構造の復元) 手順を示したスライドショー．)

かなり困難？

共用体 (またはキャストしたポインタでアクセスされる変数) 書きかけです．
とりあえずこちら→ OKWave QNo.3043962：デコンパイル？について (回答 No.5)

参考：Impossible To Decompile
↑Boomerang の元・主要開発者の Mike Van Emmerik 氏の記事だということに今更気付いた．(2010/10/03(日))
(しかも Boomerang プロジェクトから去る少し前)

一般には不可能？ (決定不可能問題？)

書きかけです．
とりあえずこちら→ OKWave QNo.3043962：デコンパイル？について (回答 No.5)

ポインタ演算を行ったポインタを使ってのメモリアクセス
関数ポインタだけを使って呼び出される static 関数

~~説明 (および逆コンパイル対策を考えている人への注意)~~ (準備中)

番外：復元可能であっても，ソースの表現方法が一義的に定まらないもの．

処理内容は同じであっても，Ｃのソースとしての表現方法が複数存在するもの．

if 文 vs. switch 文
共用体 vs. キャストしたポインタによるメモリアクセス
共用体の使い方には２通りある．
- 同時に存在することのない異なる型の変数が，メモリ節約のため同じアドレスに配置されている場合．この場合はポインタのキャストではなく，共用体として表現する方が妥当．
- 同一のビットパターンを，複数の異なる型の変数として解釈する場合 (type punning)．例えばエンディアン変換などを行うため，複数バイト整数型をバイト配列として扱うなど．この場合は共用体でもポインタのキャストでもいいという曖昧さがある．
(構造体への) ポインタを使わずにアクセスされる構造体
メモリ上に隣接して配置されている複数のスカラ型変数がある場合，それらが構造体にまとめられているのか，それともバラ売りされているのか，構造体へのポインタを使ってアクセスされていない限り区別できない．
(ただしコンパイラの癖によっては区別できる可能性もありそう．)
また仮に元のソースが構造体へのポインタを使っていたとしても，それが定数ポインタ (* const，定数へのポインタ (const *) ではない) ならば最適化によりポインタを使わないコードが生成される可能性もある．

書きかけです．
とりあえずこちら→ OKWave QNo.3043962：デコンパイル？について (回答 No.5)

すでに多数の Java 逆コンパイラが出回っているので， Java が逆コンパイルされやすいということを知っている人は多いと思う．しかしなぜ逆コンパイルされやすいのか，正しい理由を知っている人はほとんどいないようだ (無理もないけど)．

Java が逆コンパイルされやすい原因として，CPU 独立な中間コードを採用しているからだとか，オブジェクト指向だから (失笑) だとか説明している Java 専門サイトを見かけたことがある．しかしこれらはまったく的外れな勘違い説明で，私は次のような Java の言語仕様に原因があると考えている． (と偉そうに書くほど Java を熟知しているわけではないので，違っていたら指摘してください．)

共用体が存在しない．
C/C++ 流の共用体はその内容を完全にプログラマが管理する．仮に共用体を Java に導入した場合，その中にポインタが含まれていると，ガーベージ・コレクタはそれが有効か否かを判断できないのでガーベージ・コレクションの対象にできない．共用体ではなく Pascal 流の可変レコード型ならばガーベージ・コレクション可能だが，ポリモルフィズムを使うのが Java 流．
インライン展開される要素 (マクロ，インライン関数，テンプレート) が存在しない．
ポインタ演算が禁止されている．
ポインタのキャストがかなり制限されている． (アップキャストとダウンキャストだけ(？))
class ファイルにクラス (構造体) 定義情報が含まれている．
(クラス名，インスタンス変数 (構造体メンバ) の名前や型など．)

以上を上に書いた難易度ランキングと見比べてみてほしい．難易度上位の部分が (コメント以外) すっぽり抜け落ちているのがわかるだろう．

それと goto 文を禁止していることは，制御構造の復元を容易にしている (復元が難しい制御フローが出来にくい)．しかし制御フローの解析・復元能力が低い逆コンパイラではうまく復元できず，やむなく goto 文として「復元」してしまうこともある．Java 難読化ツールの中にはこの弱点に着目し，余分な分岐命令を挿入して制御フロー解析を混乱させるものもある．

結局，Java の逆コンパイラで最も難しいのは制御構造の復元である．苦しまぎれに goto 文をはき出してしまうのはバグとかプログラミングスキルとかそういうレベルの問題じゃなくて，制御構造の復元が数学的な難問だから．ちゃんと制御構造を復元できる逆コンパイラを作れるのは，グラフアルゴリズムやコンパイラの最適化技術の研究者レベルでないとまず無理．そんじょそこらのプログラマには手も足も出ない超難問．ハッカーと呼ばれる人であっても，自分で新しい数学的アルゴリズムを考え出せる研究者タイプのハッカーでないと無理．制御構造の次に難しい式の復元は制御フロー解析とデータフロー解析の知識があれば可能． Java 逆コンパイラのそれ以外のほとんどの部分は高校生でも作れる．

とはいえ，「CPU 独立な中間コードだから逆コンパイルしやすい」という俗説は， 100％間違いというわけでもない．普通，中間コードはネイティブコードに比べて命令の種類や複雑さが少ないので，命令デコーダを作る手間が少なくなるのは確かだろう．

しかし逆コンパイルの本質的な困難さ (コンパイルによって失われた情報をどうやって復元するか？) が軽減されるわけではないので，その効果は微々たるものである．例えるならば，火星に有人宇宙船を送り込むのに，着地点を南極にするか北極にするか程度の違いだろう．

■注意 (2010/10/03(日) 追記)

ここでいう「中間コード」とは Java バイトコードだけを指すのであって， class ファイル全体を意味するものではない．
(プログラミング言語と機械語の「中間」の「命令コード」という意味だから， Java バイトコード以外の部分にはあてはまらない．)
class ファイルはクラス定義情報 (これは中間コードじゃなくてメタデータ) を含んでいるのだから，「class ファイルを使っているから逆コンパイルされやすい」というのは正しい．しかし「Java バイトコードだから (以下同文)」とはいえない． (まだバイトコードの仕様を詳しく調べたわけではないので断定はしないが，現時点では「Java バイトコードだから逆コンパイルしやすい」具体的な証拠は見つかっていない．)
ここに書いたことは Java バイトコードに限らず，一般の中間コードについても言える．そもそも，中間コードとネイティブコードの区別は絶対的なものではない． Java チップにとっては Java バイトコード自体がネイティブコードだし，最近の x86 のコアは x86 命令セットをそのまま実行しているわけではなく，事実上中間言語化している．

Java に限らず，ガーベージ・コレクション機能のある言語の実行ファイルは，そうでない言語に比べてはるかに逆コンパイルしやすいはずである．なぜならば，実行ファイル (Java の場合は class ファイル) に構造体 (インスタンス) 定義情報がなければガーベージ・コレクタが困ることになるからである．

ガーベージ・コレクタは，ポインタで結ばれた多数のオブジェクトのネットワークをトラバース (順番に渡り歩く) し，現在使用中のオブジェクトを調べる．したがって，オブジェクト (構造体) 内のどこにどういう型のポインタがあるかがわからないと，ガーベージ・コレクタがトラバースを行うことができない．

リフレクションは，プログラム自身の情報を実行時に取得・変更することのできる機能である． Java ではクラスやオブジェクトについてのリフレクション情報を取得するためのクラスおよびインタフェースが提供されている．当然，class ファイル (他言語では実行ファイル) はこれらの情報を持っていなければならない．

逆コンパイルの難度

Java <<<<<<<< 絶対越えられない壁 <<<<<<<< C <<<<<<<< 絶対越えられない壁 <<<<<<<< C++

… ということに間違いはないが，これはネイティブ C++ についての話．Managed C++ については Spices.Decompiler という逆コンパイラがあるらしい (ただし MSIL 用)．

マネージ拡張も MSIL もまだよく調べてないけど，ガーベージ・コレクションができるということなので， Java の class ファイルと同様，実行ファイルにクラス定義情報が入っているはず．したがって逆コンパイルができても全く不思議ではない．

■2007/06/28(木) 追記

やはり Java と同様，コメント以外はほとんど復元できるらしい(↓)．

投票：逆コンパイル対策について (@IT 会議室 Insder.NET 会議室)

書きかけです．
とりあえずこちら→ OKWave QNo.3043962：デコンパイル？について (回答 No.5)

「逆コンパイラ」と聞いて誰でも真先に思い浮かぶであろう「知的財産権侵害」という目的は論外として，とりあえず思い浮かぶのは，

マルウェア解析の迅速化 (ゼロデイ防御)
コンパイルされたコードの脆弱性検出 (事前防御)
ソースのないレガシープログラムの解析

というわけで，逆コンパイラの最大の (合法的な) 需要家は，マルウェア対策ソフトの開発元かもしれない．(単なる憶測)

楽天で買う

価格：3,150円（税込、送料別）

アナライジング・マルウェア ―フリーツールを使った感染事案対処 (Art Of Reversing)

posted with amazlet at 11.01.15

新井悠岩村誠川古谷裕平青木一史星澤裕二
オライリージャパン
売り上げランキング: 12471

Ｃの逆コンパイラはどこまで実現可能か， Javaはなぜ逆コンパイルされやすいのか？

Ｃの逆コンパイラはどこまで実現可能か，
Javaはなぜ逆コンパイルされやすいのか？