KeyVM

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).

Recursive Control Structure

The TRANSFERKEY instruction can be used to give another process the right to call a process the current domain already has access to.

Key graph: process 0 created 1 and 2, but gave only 1 the key to call back. Therefore, one can be absolutely certain that 2 can never modify anything but its own state.

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.

Genetic Programming

• 
  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.

• 
  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.

See also

• Notes
• Specification
• Documentation