RarVM

From Esolang
Jump to: navigation, search
rarVM
Paradigm(s) imperative
Designed by void4
Appeared in 2019
Memory system stack-based
Dimensions tree-based
Computational class Turing complete
Major implementations (R)Python Rust
Influenced by [KeyKOS], [Ethereum Virtual Machine], [E], [Stackless Python], [Context]
File extension(s) .et


rarVM is a a resource aware, 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")

No system to date has all of these combined.

Philosophy

Machine cooperation, the very big picture

In distributed systems, shared beliefs, laws, systems of accountability and behavioral constraints enable large scale cooperation. Humans have this, digital systems do not have this yet. In most cases, humans are still required to mediate between programs. Cooperation can only be achieved if systems can rely on each other, or if trust is not required in the first place. Sufficient security is a fundamental requirement for any type of cooperation.

There are many strategies to limiting trust, including making the behavior of a system more predictable (deterministic), limiting access to internal and external resources (sandboxing) and having common, formally verifiable standards (well defined interfaces and protocols).

Machine cooperation is desirable. Think of all the devices you own. Right now, you can use only one at a time. While one is computing for you, the others are mostly idle. It's time to change that. Not just for economic reasons, but because the concept of programs cooperating in your best interest, and jumping processes between machines are pretty cool.

The principle of least authority

Very few languages actually adhere to the security principle of least authority ('POLA' - grant processes and their constituents as many permissions as necessary, but as few as possible). This leads to security disasters such as the recent NPM [malware incident].

In a few decades, tiny processors will be everywhere. We'll better have appropriate mechanisms that make them secure. Even better, with the right substrate, they might even be able to manage themselves some day! [Capability Security] shows how to make such systems scale securely. And the [Agoric Papers] detail market based cooperation mechanisms that could be build on them. This system aims to follow the POLA principle as close as possible. Here, you can import a library and attenuate its authority by giving it only the necessary resources. It is of course only one attempt, but I hope there will be many more.

Language overview

General properties

rarVM is 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 VM is stateless, all data necessary to restore a process resides in the process image.

The runtime state is a tree of processes. A process can invoke the RECURSE instruction to transfer control to a process image in its memory. Each process is assigned resource limits: cpu ('gas') - where each instruction step cost is proportionate to it's actual cpu time used - and a memory allocation limit and/or memory-time cost (gas per word per timestep).

Recursive Control Structure

While a few other systems also support sandboxing (say, WebAssembly), they require a new instance of the interpreter for each additional sandbox. This results in a linear overhead growth, while rarVMs model is constant. This also makes it easier to serialize entire trees of processes, since they are nested.

Hierarchical resource models: intent vs transfer

A parent process can have less resources than its child, or said in another way, it can allocate more to its children than it has itself. It's an *intentional* model: The parent indicates how many resources it would ideally want the child to have. If a child process is running, and its parent runs out of resources, control jumps back to the grandparent. If the grandparent refuels the parent, control is immediately transferred back to the child (the parent doesn't notice it happening). Implementing the state tree with the *intentional* resource model is a challenge, because the entire parent chain has to be checked at every step (depending on the granularity of accounting) and a given execution step has to either revert or complete successfully.

There are systems which use an alternate, *resource transfer* model: parents in the tree must transfer resources to their child nodes, thus they cannot transfer more than they have themselves. This is easier to implement at the VM-level because only at the moment of transfer has to be checked if the parent has enough resources. However, inside the program running on the VM, it requires the parent program to include an explicit while loop around the subprocess invocation, if it has at this moment less resources than it wants to allocate to it (and has to refuel its child manually after it has been refueled itself). Therefore, the intentional model is more intuitive for the VM users.

Persistence and Portability

When it regains control, a parent process can serialize the child (and it's children recursively) into linear memory. All of the runtime state is inside that image, so the child can be sent to another machine and resumed there (compare with [Stackless Python] which also has that ability, but has no sandboxing mechanisms).

Implementations

The VM was implemented in Python/RPython and Rust, the general principle also in a modified [lis.py] interpreter.

The Python implementation can run on the web, too, via Pyodide: https://void4.github.io/webjump/index.html (Try with Chrome) or via [Transcrypt].

The Rust implementation can be transpiled to WebAssembly using [wasm-pack].


A high-level language called Entish compiles down to it.

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

Different combinations of cooperation may be possible, in terms of space:

  • between processes on the same device
  • only on the local network
  • on the internet

in terms of ownership of these devices:

  • between your devices
  • between your and your friends devices
  • between your and strangers devices

and in terms of mutual accounting:

  • no accounting
  • [tit-for-tat]
  • instant or contractually agreed upon payment

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

rarVM is Turing-complete, meaning that it is in the same computational class as universal Turing machines.

Next steps

The next step is implementing capability security mechanisms.

It is heavily inspired by the KeyKOS and Genode operating systems, the E language, Stackless Python and a few more.

There seem to be more and more systems that are going into this direction, so maybe I'll build on top of a better engineered one when it emerges. A prime candidate seems to be the [Life] WebAssembly VM, which already provides resource tracking and external environment isolation and can be easily extended to allow for full runtime state serialization. Calling untrusted code by creating a new VM instance would have to be managed externally however, as the Wasm ISA is not designed to allow isolation *within* a single VM.

See also

[Notes]

[Specification]

External resources