Memory-corrupting Pong

If you’ve kept up with my blog, you might know that my recent “street-cred” has been messing around with “corruption art.” I can’t help it. Stuff like this is always so fascinating to me.

Some context would be in order. Two years ago, I made NAND, a 16-bit computer made entirely from NAND gates emulated on the web. NAND features its own custom CPU architecture, virtual machine, programming language, compiler, and IDE, and it is based on the Jack-VM-Hack platform specified in the Nand to Tetris course. Here’s (single-player) pong!

Now, I have many wonderful things to talk about with NAND, but we’re not going to be focusing on that. A few weeks ago during the height of my midterms I had a crazy idea: what if we allocated memory on the screen instead of on the heap?

To understand what that means, let’s consider this program written in NAND’s custom programming language.

class Main {
    function void main() {
        var int length;
        var Array a;
        let length = Keyboard.readInt("How much memory? ");
        let a = Array.new(length);
    }
}

The compiler stores the local variables of a function in a memory region called the stack. Everything on the stack must have a size that is known at compile time so the compiler knows how much memory to reserve for it. However, the compiler has no way of knowing how much memory is required to store the array a—it’s a dynamic amount only known at run time. The contemporary solution is to use a memory allocator, something that you can ask for an arbitrary amount of memory and will return a pointer to a chunk of that much memory. The memory allocator looks for memory in a memory region called the heap.

If you run the above program and enter 5, the NAND memory allocator does this to allocate the array:

The NAND memory allocator traverses a linked list of memory blocks and returns the first one with enough memory to satisfy the allocation request. It can undoubtedly be made more efficient. The screen is stored as a bitmap of 512 (length) * 256 (width) = 131072 pixels in its own dedicated memory region. There are no colors; a 0 means black and a 1 means green. To allocate memory on the screen instead of the heap means to tell the memory allocator to treat the screen memory region as the heap memory region.

What makes this so interesting is the fact that NAND has no trap instructions, no hardware interrupts, and no concept of a kernel mode. Universally among modern computers, if you try to read or write memory that belongs to another process or memory region, the operating system will trigger a segmentation fault and terminate your program. But NAND gives every program full reign to modify any part of the computer memory; hence, logically invalid memory operations are shamelessly allowed.

Now to actually do it.

Memory.jack

class Memory {
    static Array ptr;
    static int offset;

    /** Initializes the class. */
    function void init() {
    function void init(int offset_) {
        let ptr = 0;
        let ptr[2048] = 14334;
        let ptr[2049] = 16384;
        let offset = offset_;
        let ptr[offset] = 24574 - offset;
        let ptr[offset + 1] = 24576;
    }

    /** Finds an available RAM block of the given size and returns
     *  a reference to its base address. */
    function int alloc(int size) {
        var Array segment;
        var int length;
        if (size < 0)
            do Sys.error(5);
        let segment = 2048;
        let segment = offset;
        ...

(Reminder that this is NAND’s custom programming language; you can read it like Java)

In terms of modifying the memory allocator, this is all that is needed! The memory allocator normally starts at memory address 2048 and initializes its linked list data structure over there, the start of the heap memory region. This modification tells the memory allocator to start at the integer offset_ provided as an argument during initialization.

Sys.jack

class Sys {

    /** Performs all the initializations required by the OS. */
    function void init() {
        do Memory.init();
        do Memory.init(16384);
        do Math.init();
        do Screen.init();
        do Screen.clearScreen();
        do Output.init();
        do Main.main();
        do Sys.halt();
    }
    ...

The entrypoint of every NAND program is hardcoded to be Sys.init. When this function is called, it initializes the operating system libraries, runs Main.main to execute the program, and runs Sys.halt to terminate the program. It’s analogous to the _start entrypoint on Linux. We change Memory.init to take as input the start of the screen memory region, 16384, so the memory allocator allocates memory on the screen. Additionally, we have to disable the routine that automatically clears the screen at the start of every program because it zeros out the metadata that was just configured by Memory.init and renders the memory allocator unusable.

With that out of the way, let’s run it on a hello world program and see what happens!

Main.jack

class Main {
    function void main() {
        do Output.printString("Hello world!");
    }
}

Great, there’s our heap! If you look at the top left corner of the screen, you’ll see “Hello World!”. Printing the text to the screen overwrote some of the heap memory data! It looks wonderful, but this program is relatively uninteresting: it immediately terminates afterwards. Can we run the pong program initially shown with our modified, silly memory allocator? We need to do two more things.

Sys.jack

    ...
    /** Halts the program execution. */
    function void halt() {
        // Set a hardware-specific flag to tell the computer runtime to stop
        do Memory.poke(24576, 32767);
        while (~false) {}
    }
    ...

First, whenever a NAND program is finished or the operating system detects something logically invalid like dividing by zero, the operating system prints “ERR” followed by an error code number to the screen and calls Sys.halt to terminate the program¹. We don’t want our program to terminate for any reason, so we simply delete this code.

Second, we add a prompt before running the program that asks the user to enter an integer offset to add to the screen region memory address (i.e Memory.init(16384 + offset)). We do this because allocating heap data at the same place on the screen would produce the same results every time. It’s nice (as you will soon see) to introduce variety in the results. The code at this point doesn’t feel necessary to explain in full detail, so I’ve omitted it.

We’re off to the races. I spent a few days playing around with memory offsets and want to showcase the most interesting results. First up is memory offset 914:

There’s a lot to unpack here! You might have noticed that the ball appears to teleport—this is because it is literally overwriting the bits that control its position on the screen while in motion. The ball then overwrites the paddle’s position bits to the top of the screen and height bits to approximately three times as tall. Despite the extensive memory corruption, why did the pong program still have some semblance of being able to run? NAND uses the Harvard architecture, which means that the program memory is stored separately from the instruction memory. The instruction memory can only be written to once when loading a program; it is read-only during its execution. So, the logic to move the paddle around and bounce the ball will always still exist.

Next, here is memory offset -10:

The ball is doing some spooky things here—it’s supposed to move in a straight line as a reminder 👻. The main takeaway with this program is that it somehow restarts itself at the end. Why this happens is simple: the program executed an instruction that sets the program counter’s value to 0, effectively telling the program to jump to the first instruction and start over.

Bam, what happened here? I would be lying if I said I knew exactly what happened, but what probably did is the program executed an instruction to jump to some random part in the instruction memory. At that point, all bets on what is supposed to happen are off: the abstractions of function calls and the program logic flow are destroyed. The processor might as well just be executing random instructions and interpreting random noise as memory. You invoked undefined behavior. NAND invoked Cthulhu.

I don’t have much to say about the next few videos, but you should give each one a moment to marvel at what is actually happening.

Here is memory offset 6:

Here is a run with extra modifications that I don’t remember:

Here is memory offset 577:

Here is memory offset 777:

This last one is my personal favorite because of how it long it lasts before restarting the program. Try to play pong all the way to the end; it’s a fun challenge!

I invite you to try out this program with your own memory offsets at NAND’s website. To run it, click “Load example program”, select “CorruptedPong”, and click “Start”. Note that your results will not always be deterministic because the program memory persists when a program is manually reset. If you want the same behavior every time, or if you want to reproduce the results of the memory offsets in my videos, make sure to first clear the program memory by clicking “Dec” on the memory view and selecting “Clr”.

So, yeah. Your takeaway should be that this could technically happen the next time you read one byte of memory out of bounds in C. Until next time!

Footnotes

1. If Memory.poke(24576, 32767) terminates the program, why does Sys.halt need an infinite loop? It boils down to an implementation detail in the computer runtime: the program will execute up to 30000 instructions at a time before polling memory address 24576 and testing if it is equal to 32767. So, it’s possible for other instructions to modify the program memory after setting the termination flag but before it is polled. It wouldn’t make sense for random memory to be modified after calling Sys.halt because it can be used to debug the program memory using the built-in memory view. As such, Sys.halt enters an infinite loop until the termination flag is actively polled again. ↩

↑ Scroll to top ↑