Fine-grained sandbox
Script: A program running in a bytecode virtual machine such as Java or Python wants to evaluate (by compiling on the fly to bytecode and then running) a function whose code is automatically generated or provided externally.
The tricky bit is that the function code is not trusted - it can be generated by a stochastic method like genetic programming or even provided by an adversary. Therefore, it is desirable to ensure that it behaves like a pure function - it can return a value, but it may not have any side effects, that is, it cannot modify any of the existing program data in any way.
The other tricky bit is that the function may have a legitimate need to call some of the existing software functions; some of these functions may have side effects, but they must be prevented from actually having any lasting effect if called by a suspicious function.
Also, it is preferable that there are no restrictions on the coding style of the suspect function, for example. it can perform destructive updates on any data structures it creates itself, only its overall effect should be purely functional.
In addition, it is preferable that the solution has a reasonably low overhead, as this can be required billions of times; it would be better, for example, to avoid having to deploy a new virtual machine for each such function.
This does not have to be done in an existing virtual machine such as Java or Python; if it is necessary to create a virtual machine around this use case, then so be it.
Are there already known solutions (or no solutions, i.e. things that are not known to work) for this problem?
source to share
I, and many others have previously built languages ββfor genetic programming purposes. If creating a new language is an option, then such solutions already exist. Since there are methods for generating automatic functions, it should be trivial for function libraries. This system will essentially be a sandboxed environment. Any side effects of these functions will be limited by the available program space.
source to share
Well, the general problem seems to be unsolvable: there is no definitive strategy for sorting natively stateful computations, possibly stateless. If the bytecode is not specifically designed to provide the kind of strong type constraints needed to overcome this, then you will be lost. Curien has written extensively about what things can and cannot be inferred from black box observations.
But if you want to demand more from your feature provider, the question is to ask for a confirmation code (PCC) as an answer. I assume that you are aware of the work of Necula, which took particular care to ensure that the assembly code enforces memory restrictions, such as not going into an inactive state; You may not be aware of working on automatic proof-withdrawal in fairly common cases: it is possible that PCC is an easier option than you think.
source to share