Impossible Code Golf Record via Covert Channel

In this post, I’ll set an impossible record on a code golf challenge using a procfs side channel.

Feel free to skip to the TL;DR section!

Context

Recently, my friends and I have been having fun competing with each other on code.golf. The idea of code golf is to solve a programming problem in as few characters as possible. Lots of these problems are highly optimized and leave little room for improvement. Naturally, I started looking to somewhat dubious methods to get the edge on my friends.

Runner Architecture

The code runner for code.golf is open source. The go backend for the site and the runner program is all within a single docker image. Separate docker images for each language are built and then their rootfs is copied into this central docker image in a subfolder. When a submission is to be ran, the go backend invokes the runner in new PID and network namespaces. The runner remounts the root to the specified language folder. It then applies a restrictive seccomp allow list, among other things.

What We Can’t Do

This architecture is pretty robust. We can’t establish network connections. We can’t write to the filesystem. We can’t escape the chroot without a kernel exploit. Due to the namespaces and read only filesystem, I couldn’t find a way to persist state across runs.

What We Can Do

The two interesting things we can do from our python script are

1. Write to /tmp, which is mounted as a tmpfs. This folder isn’t shared outside our namespace.
2. Read from /proc, which is mounted as the procfs

Covert Channel

The key observation is that all programs are being executed on the same host. Is there some way we can submit two separate solutions at the same time and have them communicate? Then we could submit a tiny receiver to the problem of interest and an arbitrarily long transmitter to a different problem at the same time. The receiver could read a python script from the transmitter and exec it to solve the problem in an impossibly small number of characters. In general, communication between two processes which aren’t supposed to be able to communicate is known as a covert channel.

Side channels, specifically cache based side channels, can be used to this effect. However, cache based attacks are somewhat complicated and can have a poor signal to noise ratio. Executing one would require us to exploit the python process to get native code execution.

Click here for more notes on exploiting cpython

Exploiting cpython for native code execution is useful when you find yourself in pyjail-like situations. You can use ctypes to overwrite cpython function pointers. ASLR is useless, since id(x) will return the address of x. You can also import mmap to mmap rwx pages for your shellcode. In our case, we can't import ctypes, since the environment is missing shared objects.

In the absence of ctypes, you can write to /proc/self/mem to overwrite cpython function pointers

Additionally, cpython does not validate bytecode. You can exploit cpython using malformed bytecode

These methods are a bit too verbose for our use case, especially if we have to add a cache prime and probe implementation on top of that.

Special files in /proc give us simpler, more powerful primitives to establish a covert channel.

/proc/meminfo

/proc/meminfo returns information about the system’s memory:

nathan@laptop:~$ cat /proc/meminfo 
MemTotal:       24309368 kB
MemFree:        13771348 kB
MemAvailable:   17315352 kB
...
Committed_AS:   21705528 kB

If we allocate memory in one process, we can read from /proc/meminfo and observe the change in the free memory of the system. While googling around for procfs side channels, I found this behavior was reported to Docker 4 years ago. It was dismissed as a non-issue. Clearly, they didn’t think about code golf use case :)

The POC from the report uses the MemFree field and allocates big python strings. This is too slow for us, since we have a strict 5 second timeout. It is also susceptible to the noise of other processes allocating memory.

Communication Protocol

We’ll use the Committed_AS field of /proc/meminfo. This number increases when we mmap memory, even if we don’t fill that memory. We have more precise control over this field since python’s mmap module gives us more precise control over allocations/deallocations. We can also mitigate noise by mapping huge chunks of memory, even more than the system has available.

The transmitter will be mapping and unmapping memory, and the receiver will be watching /proc/meminfo. The transmitter will allocate a chunk size which transmits 3 bits of information: a clock signal, the value bit, and a bit to indicate if the transmission is finished. This technique enables reliable transmission at 2KB/s.

Receiver (golfed)

g=lambda:int([*open('/proc/meminfo')][31].split()[1])//(2<<21)
s=g()
p=1
v=b=0
while 1:
    v=g()-s
    if v&1:
        c=v&2
        if c-p:
            if v&4:break
            b=b<<1|(v>>3)
            p=c
exec(b.to_bytes((b.bit_length()+7)//8,'big').decode())

Transmitter

import time
import mmap

chunk_size = 4 * 1024 * 1024 * 1024

def write(clk, val, done=False):
    print(f'clk={clk}, val={val}')
    val = val << 3 | done << 2 | clk << 1
    a = mmap.mmap(-1, val * chunk_size + chunk_size)
    time.sleep(0.0005)


msg = b'''print("hello world!")'''

clk = 0
for c in msg:
    for i in range(8):
        write(clk, (c >> (7 - i)) & 1)
        clk ^= 1

write(clk, 0, done=True)

Go ahead and try it on your system! Run python3 receiver.py first, then run python3 transmitter.py in a separate terminal. The receiver should print “hello world!”.

Results

I submitted the receiver to the 12 Days of Christmas challenge. I quickly submitted the transmitter to a different problem immediately after. Sure enough, I set an impossible record. I made sure to take a couple screenshots before I could get banned.

Report

I was spotted right away in the Discord.

I reported the find to an admin who was very kind despite promptly deleting my record :( They marked /proc/meminfo as non readable. They are currently looking into locking down procfs more.

TL;DR

1. I want to set an impossible code golf record on code.golf
2. Their code runner is open source and is locked down well using namespaces and seccomp allow lists
3. /proc is mounted as procfs and is readable
4. Submissions run on the same host
5. Committed_AS field of /proc/meminfo can be used as a way to transmit data reliably between processes
6. A transmitter can mmap and munmap memory to transmit data, and a receiver can read /proc/meminfo to receive data. These two programs are submitted to different challenges at the same time.
7. The golfed receiver executes the script it receives from the transmitter, resulting in impossibly small golf solution