予備的注意
まず、バイナリプログラムの正しい逆アセンブルとは何かについて合意する必要があります。私は次の定義を提案します:
バイナリプログラムの正しい分解は、プログラムが入力したものに関係なく、プログラムによって実行できるすべての可能な命令のセットを提供します。
別の言い方をすれば、プログラムが実行できるすべての入力に対して、プログラムの実行可能なすべての命令を公開するということです。
停止問題
ここで、Turingマシンの停止問題と並行して、次のように定義できます( Wikipedia):
停止問題は、任意のコンピュータプログラムの説明と入力から、プログラムの実行を終了するか、永久に実行し続けるかを決定する問題です。
この(明らかに)非常に単純な問題は、Turingによって決定できないことが示されています。つまり、プログラムで一定量のケースを自動的に処理できたとしても、一部の病的なケースは常に回避されます。マシン/プログラムが指定された入力で停止するかどうかを判断できない私たちのプログラム。
そしてもちろん、そのような病理学的ケースは無限に多いです(したがって、それらを列挙する望みはありません)特別な場合として次々に)。
逆アセンブルの問題に戻りましょう!
プログラムのすべての可能なパスを探索することは、停止問題のために決定不可能です。 >!
実際、停止問題を定式化する2つの方法は、アクセシビリティ問題です。ここでは、特定のポイントに到達できる入力があるかどうかを知りたい場合があります。プログラム。また、プログラムがメモリ内の特定の場所に到達して命令として解釈できるかどうかを知ること(つまり、命令ポインタはある時点でこのアドレスの値を取得します) アクセシビリティの問題。
つまり、分解は決定不能です。
しかし、現実の世界では?
わかっています、わかっています、これは数学だけです...現実ではありません...ほとんどの難読化(自発的かどうか)は解決され、バイナリコードから自動的に削除されます...
これは本質的に、これらの難読化を行った人々が決定不能に慣れていなかったためです。問題...
決定不能問題の計算をプログラムに挿入することを想像してみてください。あるいは、それに適用される自動推論を壊すほど難しい複雑なものを挿入することさえ想像してみてください。
例を挙げると、Collatzシーケンス( Wikipedia)を見てみましょう。このシーケンスは、しばらくすると常に1で終了すると推測されます。しかし、その背後にある算術問題は非常に複雑であるため、この推測は約1世紀以来成り立っています...これは使用するのに完全な不透明な述語です!もちろん、そのような推測の証拠が存在する可能性もありますが、この問題は、その上に構築を開始し、プログラムの状態空間を探索するコンピューターを混乱させるほど複雑です。
実際、これは現在の問題です。今日の強い難読化における研究の方向性...私たちは以前に使用された小さなトリックでほとんど終わり、人々はより根拠のある問題に基づいて物事を構築し始めます。暗号化と比較するためのソフトウェアの難読化に関して、シャノン(情報理論の父)に相当するものをまだ見逃している場合でも。
最後の言葉
したがって、分解の問題は停止の問題と強く関連していることがわかりました。また、非常に複雑な問題を使用することが、最新のソフトウェア難読化の次のステップになる可能性もあります。
現在の分解ツールは、分解技術の最先端に固執しなければならない場合にできることよりもはるかに遅れているという事実について、最後に一言申し上げます。現在のツールがどれほど先史時代のものであるかを見ると、私はいつも苦痛で泣いています...しかし、すべての現代的な技術を実践するには、開発と保守に多大な労力が必要になるため、誰もそれを行う準備ができていないようです(しかしこれは私のものだけです)謙虚な意見)。