KeyVM
| Paradigm(s) | imperative |
|---|---|
| Designed by | [void4] |
| Appeared in | 2019 |
| Memory system | stack-based |
| Computational class | Turing complete |
| Major implementations | Python |
| Influenced by | rarVM KeyKOS, Ethereum Virtual Machine, E, Stackless Python, Context |
| File extension(s) | .blob |
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.
Language overview
General properties
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
Distinguishing features
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.
[Why KeyKOS is fascinating] and [What makes KeyKOS special] explain this in detail.
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.
Implementations
The VM was implemented in Python.
Examples
Self-replicating processes
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))
KeyVM Process Capability Graph generated by running the code above with step and memory limits of 5000
Use cases
Resource aware, recursive Sandboxing
Showcase: (Youtube)
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))
Evolving programs
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.
Tracking physical resource usage (Approximated by listening to cat /sys/class/power_supply/BAT0/power_now)
Jumping processes
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.
Full memory snapshot of a process. Each pixel is a byte.
Visualized as a 3d cube. Imagine manipulating this in AR or VR
As a QR code. You could run a scanned program with your smartphone.
Computational class
KeyVM is Turing-complete, meaning that it is in the same computational class as universal Turing machines.
Because a subprocess can be called with resource limits, processes can secure themselves against resource-exhaustion attacks from imported libraries.