x86のMMUはチューリング完全である

jbangert/trapcc · GitHub

The Page-Fault Weird Machine: Lessons in Instruction-less Computation | USENIX

x86のMMU、つまりは割り込みとメモリ変換テーブルは、チューリング完全であることの証明。割り込みとメモリ変換テーブルを活用して、プログラムカウンターを一切進めず、ひたすら割り込みを続けるだけで、任意の演算が可能になる。もちろん条件分岐だってオーケーだ。

このテクニックを使えば、カーネルモジュールのバイナリにとても解析が面倒な難読化処理を施すことができる。なぜなら、通常のインストラクションは実行しないから、何をしているのか、通常のインストラクションを追うだけでは一見して明らかではないからだ。そもそも、既存のKGDBなどは、あまりに頻繁な割り込みがかかるため、まともに機能しなくなるようだ。また、エミュレーターでこのコードを正しく実行できるのは、今のところ、Bochsだけだという。

このテクニックを使い、通常のインストラクションを実行せずに、ライフゲームを実行するデモ。