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, Idel, Ethereum Virtual Machine, E, Stackless Python, Context |
| Influenced | KeyVM |
| 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")
- fully deterministic execution (optional)
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).
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/credit vs transfer/money
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/credit* 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. It never goes below 0. 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/money* 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: (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.
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
-
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
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.