virtual - きめの細かいサンドボックス

Question

シナリオ：JavaやPythonなどのバイトコード仮想マシンで実行されているプログラムが、コードが自動的に生成または外部から提供された関数を（バイトコードにオンザフライでコンパイルして実行することにより）評価したいと考えています。

トリッキーな点は、関数のコードが信頼されていないことです。遺伝的プログラミングのような確率論的方法によって生成された可能性があり、敵から提供された可能性もあります。したがって、純粋関数として動作することを強制することが望まれます。値を返すことはできますが、副作用がない可能性があります。つまり、プログラムの既存のデータを変更することはできません。

もう1つの注意点は、関数がプログラムの既存の関数の一部を呼び出す正当な必要性を持っている可能性があることです。これらの関数の一部には副作用がある可能性がありますが、疑わしい関数によって呼び出されている限り、これらの関数が実際に持続的な効果を発揮しないようにする必要があります。

また、疑わしい関数のコーディングスタイルに制約を課さないことが望ましいです。たとえば、それ自体が作成するデータ構造に対して破壊的な更新を自由に実行できます。純粋に機能するために必要なのは、全体的な効果だけです。

さらに、これは何十億回も実行する必要がある可能性があるため、ソリューションのオーバーヘッドが適度に低いことが望ましいです。たとえば、そのような機能ごとにまったく新しい仮想マシンをフォークする必要がないようにする方がよいでしょう。

これは、JavaやPythonなどの既存の仮想マシンで実行可能である必要はありません。このユースケースを中心に仮想マシンを設計する必要がある場合は、そうしてください。

この問題に対する既知の解決策（または非解決策、つまり機能しないことがわかっているもの）はありますか？

Answer 1

サンドボックスが唯一の選択肢だと思います。プログラムを分析して安全かどうかを判断しようとすることは、停止性問題と同等です。CLRには、このような制限を可能にするセキュリティが組み込まれています。Javaにも同様の制限があると思います。Pythonはそうは思わない。

Answer 2

さて、一般的な問題は解決できないようです。本質的にステートフルな計算を、おそらくステートフリーからソートするための終了戦略はありません。これを克服するために必要な種類の強い型制約を提供するようにバイトコードが特別に構築されていない限り、あなたは失われます。 キュリアンは、ブラックボックスの観測からどのようなことが推測できるか、推測できないかについて多くのことを書いています。

しかし、関数プロバイダーにもっと多くのことを要求したいのであれば、質問は答えとして証明付きコード（PCC）を求めています。範囲外の状態を改ざんしないなど、アセンブリコードがメモリ使用量の制約を尊重するようにすることに特に関心を持っていたNeculaの作業をご存知だと思います。かなり一般的なケースでは、証明の自動推論で行われる作業に気付いていない可能性があります。PCCが思ったよりも簡単なオプションである場合があります。

Answer 3

私や他の多くの人々は、以前に遺伝的プログラミングの目的で言語を構築しました。新しい言語を構築することがオプションである場合、そのようなソリューションはすでに存在します。自動関数生成の手法があるため、関数ライブラリを提供するのは簡単なはずです。このシステムは、事実上、サンドボックス環境を構成します。これらの機能の副作用は、プログラムがアクセスできるスペースに限定されます。