10

エミュレーターとステートメントに関する投票数の多い質問を読んでいたところです

特定のバイナリ内のすべてのコードを見つけることは、停止問題と同等であることが証明されています。

本当に私に突き出ました。

そんなことはあり得ませんよね？それは単なる大きな依存関係グラフではありませんか?

この声明へのさらなる洞察に本当に感謝します。

4

4 に答える 4

5

私はラースマンに同意しません。

停止性問題は、任意のプログラムを取り、そのプログラムが命令を実行するかどうかを決定Pできるプログラムが存在しないことを示しています。ウィキペディアを引用させてください：halt

Alan Turingは、1936年に、考えられるすべてのプログラムと入力のペアの停止問題を解決するための一般的なアルゴリズムが存在できないことを証明しました。チューリングマシンでは、停止問題は決定不可能であると言えます。

一方、私たちはそのようなプログラム/アルゴリズムを作成しようとはしていませんが、この/これらの特定のプログラム内のすべてのコードを見つけようとしています。プログラムをリバースエンジニアリングして、すぐに呼び出されることを確認すると（非常に楽観的な例の状況） 、それは不可能でしたが、呼び出されることがexit()証明されました。halt

それ以降失敗するプログラムを実行できるエミュレーターを構築しようとしている場合は、それを（簡単に）停止問題に減らすことができます。しかし、通常は、有限量のゲームカートリッジ（プログラム）をサポートするゲームボーイのようなエミュレーターを構築しているため、それは可能です。

于 2011-03-14T15:55:39.120 に答える
4

「これまでに実行されたすべてのコードを見つける」こと、つまりカバレッジを見つけること、おそらく動的に生成されたコードと組み合わせることを意味していると思います。それは確かに停止問題に還元できます。

実行される可能性のあるプログラム内のすべてのコードを検出する完全なカバレッジ ツールがあるとします (つまり、残りはデッド コードです)。program が与えられた場合、このツールは、拡張されたプログラムが命令を実行するかどうか、またはその部分がデッド コードであるかどうPかを判断することもできます。したがって、決定不能であることがわかっている停止問題を解決できます。(P ; halt)halthalt

于 2011-03-14T14:39:56.227 に答える
3

有限状態マシンの停止問題は解決可能です (宇宙の多くの寿命がかかるかもしれませんが)。エミュレートする可能性のあるマシンはすべて有限状態マシンです。プログラムを実行するだけで、ステップ数は可能な状態の数によって制限されます。停止せずにその数を超えた場合、プログラムはループ内にある必要があるため、停止することはありません。

実際には、すべてのコードを見つけることは、コードが計算された goto を使用できない限り、はるかに簡単な問題です。コードを実行するのではなく、考えられる各分岐点ですべての分岐を 1 回だけ実行します。

于 2011-03-25T18:09:01.707 に答える
0

私はラーズマンに同意し、議論を正確にすることができると信じています. まず、「特定のバイナリ内のすべてのコードを見つける」とは、このコンテキストでは、入力バイナリ内のどのバイトが実行される命令に対応するかを決定する単一の計算可能な関数を持つことを意味することに同意する必要があります。

編集: ここに問題がある理由が明確でない場合は、難読化されたマシン コードについて考えてみてください。このようなコードの逆アセンブルは、重要な問題です。マルチバイト命令の途中で逆アセンブリを開始すると、間違った逆アセンブリが発生します。これにより、問題の命令だけでなく、通常、それを超えるいくつかの命令が壊れます。などを調べます。(たとえば、Google の「難読化と分解」)。

これを正確にするための戦略のスケッチ:

まず、プログラムがマルチビット バイナリ命令でエンコードされる理論的なコンピューター/マシン モデルを定義します。このモデルでは、「実際の」コンピューターのマシン コードによく似ていますが、正確に作成されます (チューリングが完全になるように)。バイナリがプログラムとすべての入力をエンコードすると仮定します。これはすべて正確にする必要がありますが、言語には (バイナリ エンコードされた) 停止命令があり、「停止」命令を実行した場合にのみプログラムが停止すると仮定します。

まず、マシンがプログラムコードを変更することはできませんが、作業するメモリを持っていると仮定しましょう。(興味深いケースでは無限であると仮定されます)。

次に、特定のビットは、プログラムの実行中に実行される命令の先頭にあるか、そうでないかのいずれかになります。（たとえば、命令の途中、データ、または「ジャンクコード」、つまり決して実行されないコードである可能性があります。たとえば、ジャンプ命令のように、これらが相互に排他的であると主張していないことに注意してください特定の命令の途中にあるターゲットを持つことができるため、「最初のパスで」実行された命令のように見えない別の命令が作成されます。)

ins(i, j) を、バイナリ i にビット位置 j で始まる命令があり、i によってエンコードされたプログラムの実行で実行される場合に 1 を返す関数として定義します。それ以外の場合は、ins(i,j) を 0 に定義します。ins(i,j) が計算可能であるとします。

Halt_candidate(i) を次のプログラムとします。

for j = 1 to length(i)
  if(i(j..j+len('halt')-1) == 'halt')
    if(ins(i,j) == 1)
      return 1
return 0

上記の自己変更コードを禁止しているため、プログラムを停止する唯一の方法は、実行される位置 j に「停止」命令があることです。設計上、halt_candidate(i) は停止関数を計算します。

これは、証明の一方向の非常に大まかなスケッチを提供します。つまり、プログラム i の位置 j にすべての j について命令があるかどうかをテストできると仮定すると、停止関数をコーディングできます。

もう一方の方向では、フォーマル マシン内で、フォーマル マシンのエミュレーターをエンコードする必要があります。次に、プログラム i をエミュレートする入力 i と j を加えたプログラムを作成し、ビット位置 j の命令が実行されると、1 を返して停止します。他の命令が実行されると、その命令は引き続き実行され、シミュレーションが i で「停止」機能をシミュレートした場合、エミュレーターは無限ループにジャンプします。その場合、ins(i,j) は halt(emulator(i,j)) と同等であるため、停止問題はコード検索の問題を意味します。

もちろん、これが有名な解決不可能な停止問題と同等であるためには、理論的なコンピューターを想定する必要があります。それ以外の場合、「実際の」コンピューターの場合、停止の問題は解決できますが、扱いにくいです。

自己変更コードを許可するシステムの場合、引数はより複雑になりますが、それほど変わらないと思います。

編集:自己変更の場合の証拠は、上記の静的コードとデータシステムにシステムと自己変更コードのエミュレーターを実装することだと思います。次に、データ x を使用してプログラム i に許可された自己変更コードで停止することは、コードとデータとしてエミュレータ i と x を含むバイナリを使用して、上記の静的コードとデータ システムで停止することと同じです。

于 2014-05-22T13:08:45.883 に答える