KeyVM

From Esolang
Jump to: navigation, search
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 consists of a

  • read-only header (contains status, available resources, and instruction pointer)
  • read-only key list (a list of all processes it can call)
  • code (a list of instructions)
  • data (a list of linear memories)
  • a stack (used for computation)

Distinguishing features

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/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]

Cooperative resource sharing between devices

Since resources are metered and can be limited, a process can securely execute (untrusted) code for someone else.

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.

Computational class

blobVM 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