Core Wars Shows the Battle WebAssembly Needs to Win

This will probably be the year of WebAssembly (Wasm), but right now it remains a “byte code target” for compilers. In other words, it’s just another way to create and manage executable programs. Despite the name, it isn’t limited to browsers — and its main potential is with the Internet of Things (IoT). So you may be asking, why all the fuss?

Looking a bit more closely at the documentation, I can’t help noticing that quite a bit of thought has been dedicated to security. One way of achieving high security is to write a very careful spec, so that freedom of choice is limited yet transparent. Tom Stuart has even misspent considerable time making a WebAssembly interpreter in Ruby, just based on the specs and their tests. This generally helps create safe code, but there is also a slant toward not trusting code to work properly in the first place.

This goes together with the fairly ambitious component model. This has always been the great curse of collaborative models — working out how far to trust code you know nothing about, while reaping the benefits of a wider ecosystem. Whether through malice or incompetence, society can be heavily inconvenienced when running code goes awry.

In order to gain an appreciation for naughty code, I’d like to reintroduce Core War.

Core War is a programming game where assembly programs try to destroy each other in the memory of a simulated computer.

It might be an ancient developer-minded virtual sport, but as a side product it provides a useful demonstration of the problems with errant software. We aren’t going to delve into the details, but we will look at just enough to understand the Way of the Warrior. Forgive the somewhat testosterone-induced naming; remember this was a product of the 1980s.

A game of Core War running under the pMARS simulator (via Wikipedia)

Core War Basics

So the basics are that you have two or more competing programs, running in a virtual space and trying to corrupt each other with code. In summary:

• The assembler-like language is called Redcode.
• Redcode is run by a program called MARS (Memory Array Redcode Simulator).
• The competitor programs are called “warriors” and are written in Redcode, managed by MARS.
• The basic unit is not a byte, but an instruction line.
• MARS executes one instruction at a time, alternatively for each “warrior” program.

The core (the memory of the simulated computer), or perhaps “battlefield”, is a continuous wrapping loop of instruction lines, initially empty except for the competing programs, which are set apart. Code is run and data stored directly on these lines.

Each Redcode instruction contains three parts: the operation itself (OpCode), the source address and the destination address. When I say “address,” I mean a relative reference from the line the instruction is on. So +1 would refer to the next line.

While in modern chips, code moves through parallel threads in mysterious ways, the Core War setup is still pretty much the basics of how a computer works. However code is written it, we know it ends up as a set of machine code instructions.

So what does Redcode look like? Here is the simplest known warrior, the Imp, sitting in the middle of the battlefield. It just copies the contents of one line, itself, to the next line:

Now the instruction “MOV” is actually a copy instruction. (There are various reasons why this misnomer lingers, but none of them are good.) It reads “Copy the line at relative address 0 (this line) to the line at relative address +1 (the next line).”

So after the first instruction line is executed, there will be two lines of Imp:

This technically means the Imp has extended itself, as it has created a new instruction at the end of its own listing. This also implies that MARS just executes instructions without recognizing a formal end to a warrior program.

So the upshot is that after executing this a number of times, the whole battlefield will be filled with Imps. At some point the other program would execute an Imp, and … turn into an Imp.

The actual win condition for a Core War warrior is to force the opponent to execute a rogue “DAT” instruction. So let us end our quick sojourn into Core War by looking at a slightly more sophisticated program that drops “DAT” bombs.

This is the warrior program known as the Dwarf:

This is not the place to deal with the various “addressing modes,” so I am not going to dwell on the differences between “4”, “#4”, and “@2”. Suffice to say, they are just directions for how to use values, addresses and results. There is a reason why nobody uses assembler anymore! However, the design is revealed as soon as you notice the jump statement.

That “JMP” instruction creates a simple loop — the program jumps from the third line back two steps to the first line again. The first line ADDs the number 4 to the DAT statement three lines down. Then the MOV statement copies the DAT statement two lines below a number of lines, depending on the value in the second field of the DAT statement. And that number starts off at 0, but remember the ADD statement…

Here is the battlefield after one iteration of the Dwarf:

In short, the Dwarf is really an artillery unit, altering the launch angle then firing DAT shells further and further down the battlefield. So whereas the Imp replicates itself, the Dwarf remains in position and shoots. Quite different mechanisms, even in small bits of code that wreak havoc.

How Does This Relate to Wasm?

Ok, so the purpose of all this was to show how even a very simple program given free rein can be “destructive”, and to have a better idea of what systems like Wasm have to contend with.

Probably the first thing to recognize is the idea of the “sandbox” — usually considered a safe play area for kids sufficiently old enough not to swallow the sand. Notice that our Core War “battlefield” was a continuous ring of memory that doesn’t go anywhere either. Wasm also executes modules in careful isolation.

The other thing to notice is that while the original warrior code was known, it could effectively write over itself — or worse, other running programs. This would mean that a section of code might present itself as one thing, but on running becomes something else. This leads to the idea of not allowing the presented code to change itself — i.e. it is immutable. Also, the mobility of code means that where it technically starts and finishes needs strict control.

Like many systems, Wasm allows for traps — these condition statements look for unexpected occurrences and immediately stop execution if they are found. For example, a trap occurs if an attempt is made to access memory not within the bounds of the container — an attempt to escape a sandbox, for example.

Most systems deal with security breaches through constant updates, but this is always a bit harder if the system is fragmented into many components that might be constructed in a unique configuration. Wasm will initially be judged on how efficiently it runs code, but it is the security of the component model that will decide how well it competes in the future market.

David has been a London-based professional software developer with Oracle Corp. and British Telecom, and a consultant helping teams work in a more agile fashion. He wrote a book on UI design and has been writing technical articles ever since....

Read more from David Eastman