KeyVM

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.jpg|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.
Genetic Programming
Zmq6w93bbho21.png|Resource limited programs evolved to output as many different colors as possible
===Cooperative resource sharing between devices===
Since resources are metered and can be limited, a process can securely execute (untrusted) code for someone else.
Screenshot from 2019-04-09 04-20-58.png|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.
Snapshot.png|Full memory snapshot of a process. Each pixel is a byte.
Cube4.png|Visualized as a 3d cube. Imagine manipulating this in AR or VR
Qr process image.png|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.
==See also==
*Notes
*Specification
*Documentation
==External resources==
Category:Low-level 
Category:Implemented 
Category:Languages
Category:2019
Category:Stack-based 
Category:Turing complete