|Computational class||Turing complete|
|Influenced by||rarVM KeyKOS, Ethereum Virtual Machine, E, Stackless Python, Context|
KeyVM is a a resource aware, capability-secure, recursively sandboxable virtual machine built to simultaneously have these properties:
- fine grained control of process-internal resources (cpu time/cycles, memory usage)
- control of access to process-external resources (filesystem, networking)
- doing the above recursively, to securely sandbox libraries from each other
- the platform-independent transfer of process state (mobile agents, "jumping processes")
It is a variant of rarVM, here, processes are not nested within each other, but they need a key (capability) to call each other.
- 1 Language overview
- 2 Implementations
- 3 Examples
- 4 Use cases
- 5 Computational class
- 6 See also
- 7 External resources
KeyVM is a stack-based architecture, single-threaded (control only resides at one place at a time) and deterministic (a copy of the program state with the same input will always create the same results, down to the bit). The runtime state is a list of processes. The VM is stateless, all data necessary to restore a process resides in the process image.
A process is a key list, containing keys to:
- process metadata (runtime status, keys to resources, the instruction pointer)
- code (a list of instructions)
- data (a linear memory page)
- a stack (used for computation)
- more keys to data pages or key pages, some of which could be other processes
The language [reifies] a concept first introduced in the KeyKOS operating system: rights are represented as keys, objects which grant access to a specific resource and can be passed around between processes.
The CREATE instruction is used to create a new process from one of the processes' memories. The creating process receives a key to the newly created process.
The RECURSE instruction can be invoked to transfer control to another process image in the list. Each process is assigned resource limits: instruction steps/time ('gas') and a memory allocation limit and/or memory-time cost (cost per word per timestep).
The TRANSFERKEY instruction can be used to give another process the right to call a process the current domain already has access to.
The VM was implemented in Python.
The following code replicates itself and gives a third of its resources to the child, then transfers control to it (twice, resulting in a binary tree). Each subprocess runs the same code again, which continues until they run out of resources.
memcreate alloc(0,2) memwrite(0,0,fork()) memwrite(0,1,fork()) transferkey(1, random(0, numkeys())) transferkey(2, random(0, numkeys())) recurse(mempush(2,0), div(mempush(0,2), 3), div(mempush(0,3), 3)) recurse(mempush(2,1), div(mempush(0,2), 2), div(mempush(0,3), 2))
Resource aware, recursive Sandboxing
What you can see here is the main process sandboxing the function f, limiting it to 50 virtual machine steps and a maximum of 50 additionally allocatable bytes, passing the command line input into it, running it and returning the result. This also works recursively, where f sandboxes another function, possibly even itself.
# This function will be sandboxed def f(x): return x + 1 # Infinite loop while: # Returns the result of applying f to the input # f is sandboxed and limited to run 50 instructions # and use a maximum of 50 additional words of memory yield f<50,50>($arg(0))
Since the effects of process execution can be arbitrarily limited, it is safe to generate random programs and execute them. Thanks to the accounting mechanisms, resource efficient programs can be given an evolutionary advantage.
Cooperative resource sharing between devices
Since resources are metered and can be limited, a process can securely execute (untrusted) code for someone else.
When a (sub)process has run out of time or memory, its snapshot can be written to a file or sent to another computer. The process can 'jump' between systems. This is known as Code/Agent mobility. A process snapshot can be "refueled" and then resumed.
Because a subprocess can be called with resource limits, processes can secure themselves against resource-exhaustion attacks from imported libraries.