逆コンパイル30年史：いまだ解決せぬ「構造化問題」とは何か

はじめに

IDA ProやGhidraを使ったことがあるだろうか。これらのツールは、コンパイルされたバイナリを人間が読めるコードに変換する「逆コンパイラ」だ。マルウェア解析、脆弱性発見、レガシーコードの解析に欠かせない。

しかし、使ったことがある人なら経験したことがあるはずだ。デコンパイル結果が奇妙なgotoだらけで、元のコードが想像できないという状況を。

実はこれ、単なるツールの不具合ではない。30年間解決されていない根本的な研究問題なのだ。

2026年2月、Redditのr/programmingで「30 Years of Decompilation and the Unsolved Structuring Problem」という記事が注目を集めている。この記事では、バイナリ逆コンパイルの歴史と、いまだ解決されていない「制御フロー構造化問題」について詳しく解説されている。

本記事では、この30年間の軌跡と、なぜこの問題が難しいのかを紐解く。

—

逆コンパイルの3つの柱

まず基本を整理しよう。バイナリを高級言語のコードに戻すには、大きく3つのステップが必要だ：

1. CFG復元とリフティング

バイナリを逆アセンブルし、制御フローグラフ（CFG）として表現する。CFGは命令間のジャンプ関係をグラフ構造で表したものだ。

2. 変数復元と型推論

レジスタやメモリ位置から元の変数を復元し、その型を推論する。intなのかchar*なのか、構造体なのかを見分ける作業だ。

3. 制御フロー構造化（Control Flow Structuring）

ここが問題の核心だ。 CFGには「if文」「whileループ」といった高級言語の構造情報がない。これらを復元するのが「構造化アルゴリズム」の役割だ。

—

1994年：すべての始まり

逆コンパイル研究の祖とされるのは、Dr. Cristina Cifuentesの1994年の博士論文「Reverse Compilation Techniques」だ。

Cifuentesは、CFGから高級言語構造を復元するために「グラフスキーマ」を使うアプローチを提案した。これは、CFGの中からif-then-elseやwhileループの「パターン」を探し出し、それらを構造としてマークする方法だ。

パターンマッチングの限界

しかし、このアプローチには根本的な問題がある。

例えば、以下のような5ノードのCFGを考えてみよう：

A → B → C → E
     ↓   ↑
     D ──┘

B-D-Eのひし形パターンは典型的なif-then-else構造に見える。だが、AからCへの直接エッジがある場合、このパターンは崩れる。

どのエッジをgotoにすればいいのか？

Cifuentesの手法には、この問いに対する明確な答えがなかった。小さな選択（どのエッジをgotoにするか、ifの条件を反転するかどうか）が、出力コードの品質に劇的な影響を与える。

ここに30年間続く「構造化問題」の種があった。

—

2007年：ハッカーたちの台頭

学術界が長らく沈黙していた間、実務家たちは独自の逆コンパイラを作り始めた。

2007年は重要な年だ。

IDA Pro / HexRays – 逆アセンブラとして既に有名だったIDA Proが、デコンパイラHexRaysを統合。現在でもデファクトスタンダードとして君臨している。
Reko – オープンソースの逆コンパイラとして公開開始。

両者ともCifuentesのアイデアをベースにしつつ、実用性を高めていった。IDA Proは条件チェックを導入して構造を削減するなど、独自の改良を加えたとされる。

その後も：

2015年: Snowman、fcd、Binary Ninjaが登場
2019年: NSAがGhidraを公開 – 初めて資金豊富な組織からリリースされたオープンソース逆コンパイラ

—

2013年：学術界の再始動

学術界が本格的に逆コンパイル研究に戻ったのは、2011年のCarnegie Mellon大学のTIE論文からだ。これはCFG内の型と変数を復元する新しい手法を提案したものだ。

この成果をベースに、2013年にPhoenix論文が発表された。

「Native x86 Decompilation Using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring」

Phoenixは、初めてTop 4セキュリティ会議（USENIX Security、CCS、S&P、NDSS）に掲載された制御フロー構造化アルゴリズムだった。これは他の研究者に「逆コンパイルは学術的に価値がある分野だ」というシグナルを送った。

しかし、研究は進まなかった

Phoenixの後、著者は「Top 4が逆コンパイル論文で埋め尽くされるだろう」と予想した。しかし現実は違った。

30年間で、逆コンパイルに関するTop 4論文はわずか約45本。
比較として、「カーネル」関連の論文は121本もある。

なぜ这么少ないのか？

答えはシンプルだ：研究用の逆コンパイタを作るのが難しすぎるからだ。

2019年にGhidraが公開されるまで、まともに使えるオープンソース逆コンパイラは存在しなかった。研究者は毎回ゼロから逆コンパイラを作らなければならなかったのだ。

—

制御フロー構造化論文の系譜

30年間で、制御フロー構造化に焦点を当てた論文はわずか4本しかない：

| 年 | 論文 | 会議 | 特徴 |
|—-|——|——|——|
| 2013 | Phoenix | USENIX Security | 初のTop 4掲載。意味保存構造解析 |
| 2015 | DREAM | NDSS | パターン非依存構造化。goto削減 |
| 2020 | A Comb for Decompiled C Code | Asia CCS | 構造の「くし」による整理 |
| 2024 | SAILR | USENIX Security | コンパイラ認識型構造化 |

興味深いことに、これら4本のうちオープンソース実装があるのは2本だけ。しかもDREAMは2020年までコードが非公開で、IDA Pro 6.6でしか動かなかった。

—

なぜ構造化は難しいのか

根本的な問題：情報の損失

コンパイル時、多くの情報が失われる：

変数名
コメント
制御構造の意図
マクロ展開

構造化アルゴリズムは、この失われた情報を推測しなければならない。

多対多問題

あるCFGから生成可能なCコードは無数にある。その中でどれが「元のコード」に近いのか、実行時には判断できない。

コンパイラ依存性

同じCコードでも、GCC、Clang、MSVCでコンパイルすれば異なるCFGが生成される。最適化レベルによっても変わる。

2024年のSAILRは、この問題に「コンパイラ認識」でアプローチした。コンパイラが生成するパターンを学習し、それに基づいて構造化を行うのだ。

—

実際の出力例

1994年のdcc（Cifuentesのデコンパイラ）が出力したコードを見てみよう：

void proc_1 (int arg0, int arg1, int arg2)
{
 int loc1;
 int loc2;
 int loc3;
 loc2 = 0;
 while ((loc2 < 5)) {
   loc3 = 0;
   while ((loc3 < 4)) {
     loc1 = 0;
     while ((loc1 < 4)) {
       *((((loc2 * 10) + arg2) + (loc3 << 1))) =
       ((*((((loc2 << 3) + arg0) + (loc1 << 1))) *
       *((((loc1 * 10) + arg1) + (loc3 << 1)))) +
       *(((loc2 * 10) + arg2) + (loc3 << 1 ))));
       loc1 = (loc1 + 1) ;
     }
     loc3 = (loc3 + 1);
   }
   loc2 = (loc2 + 1);
 }
}

変数名はloc1、loc2と意味不明。ポインタ演算だらけ。whileループが過剰。

30年経っても、現代の逆コンパイラも似たような問題に直面している。 スコープが複雑になると、gotoだらけのコードを出力してしまうのだ。

---