Over the last two weeks, I’ve written a compiler for a tiny lisp language I call Rotten.
The way Rotten works is:
- Rotten compiles to code for a simple VM
- The VM has an interpreter written in another language, called Racket
The first interesting thing about Rotten is that the compiler from Rotten to VM-code is written in Rotten!
The second interesting thing about Rotten is how small it is: the compiler is only 80 lines of code! And it can compile itself! So that’s pretty cool.
But that’s not what I’m here to talk about. I’m here to talk about a bug in my compiler!
<driver.rkt> (boot “compile.rotc”) ;; the virtual machine has just booted up ;; and loaded a precompiled image of the compiler
<driver.rkt> (repl) ;; Now we’re running Rotten code!
ROTTEN> (+ 2 2) ROTTEN> ‘(hello from rotten)
;; so, remember I talked about a bug ROTTEN> (def (id x) x) ROTTEN> (id 10)
ROTTEN> (def (id rotten) rotten) ROTTEN> (id 10) ROTTEN> rotten
;; at this point it’s clear our compiler has a bug ;; our compiler’s only 80 lines long, let’s take a look
open compile.rot the name ‘rotten appears nowhere in this file neither does “YOUR COMPILER HAS A VIRUS” I’m going to spoil it for you: the bug isn’t here.
if it’s not here, where is it? remember how I had to boot up the VM using a precompiled compiler image. what if that compiler image had the bug in it?!
$ grep rotten compile.rotc $ grep ‘YOUR COMPILER’ compile.rotc
Okay, now what are we going to do?
No problem, we’ll just recompile the compiler! Since compile.rot doesn’t have a bug, the new compiler will be bug-free.
ROTTEN> (write-file “new-compile.rotc” (compile-program (read-file “compile.rot”))) ROTTEN> ,quit <driver.rkt> (boot “new-compile.rotc”) <driver.rkt> (repl) ROTTEN> rotten ;; what the hell?
What’s going on here is our buggy compiler image is buggy in more ways than one. Not only does it wait for the name ‘rotten and compile it into an obnoxious message; it waits for you to compile the compiler itself, and replaces it with a malicious version - one with the same bugs!
It’s a self-propagating virus in our compiler image. And unless you look at the compiled code, it’s totally undetectable. Apart from that obnoxious message.
If you’re interested in learning more, see my github or google for Reflections on Trusting Trust.