On solving the Jane Street Reverse Engineering Challenge

Or: Why do I always do things the hard way? Jane Street periodically puts out challenges, and this one thoroughly nerd-sniped me and sent me down a month-long rabbit hole that I’m only now emerging from. This post is an overview of how I solved it with a combination of hard-headedness and sleep deprivation. It’s going to be decently technical, but in future posts I’ll go over the specifics of each step if people are interested. For some background I’d recommend looking at the original post on the Jane Street blog here - Can you reverse Engineer an ASIC? And if you ever want to read the (terrible) code I used for this challenge, you can find it at my github page here Challenge Accepted I have an engineering degree rotting away somewhere in my brain, so a lot of the words of the challenge are familiar. The challenge is to take an ASIC and work out what it does. For those unfamiliar, an ‘ASIC’ is an Application-Specific Integrated-Circuit, which is a fancy word for what we’d usually call a ‘Computer Chip’. Firms like Jane Street presumably design these to get extra performance relative to the equipment you can buy from a normal manufacturer. In any case, the challenge is to take a ‘GDS’ file describing a chip, and work backwards to understand what it does, and then I guess maybe there’s a password in there or something. I didn’t, and still don’t, know what ‘GDS’ stand for. There’s two parts to the challenge - one is a warmup where you’re given a lot more information (like the actual design of the chip), and the real puzzle where you’re given a firm handshake and a ‘good luck’ as you face the increasing prospect of not sleeping for the next three weeks. What’s in the files? For some reason, I like to do things the hard way so rather than doing any research I just started poking around in the files. I can see there’s some familiar words in them like like ‘clk’ (clock), ‘rst’ (reset) and ‘VGND’ (Ground Voltage) and ‘VPWR’ (Power Voltage). And there’s a bunch of …. something with a prefix of sky130_fd_sc_hd__ followed by things that sound like logic element, like ‘or’ and ‘not’ and things like that. I guess that’s what I’ll need to pull out of the file? I found there’s a really nice library ‘gdstk’ in python that seems to be able to read them. It tell me that there’s 27 elements on the warmup puzzle. A good start! % python3 -c 'print(len(__import__("gdstk").read_gds("warmup/04_final.gds").cells))' 27 There’s also a ‘vcd’ file for the main puzzle, which is a text file, and I guess is a simulation input or output or something. I didn’t, and still don’t, know what ‘vcd’ stands for. I can see some suspicious entries in it that look like ASCII characters. I play around with it, writing a small C program, and get the output ‘TRY AGAIN’. Ah, so the circuit has messages in it somehow! $ gcc what-is-this-thing.c && ./a.out T R Y A G A I N T R Y A G A I N Ok we’re on to something Getting Distracted and wasting my time. And my life. Here we need to do a huge digression and of course build our own circuit simulator. For reasons. You can skip this section. I sure wish I did. Several days later Ok so I built a circuit sim using sqlite3 as a driver. Quite neat really. But it’s quite hard to design circuits in Python! If only there was a language for describing hardware. Several days later Ok so I built a parser for my new language and now I can design circuits. But I need to test them! If only there was some way of scriptings inputs and validating outputs. Several days later Ok so I built a harness for my circuit simulator. But it’s really hard to visualise what it’s doing! If only there was… well you see where this is going Several days later Ok so I gave up on writing a wave form viewer and decided to just use ‘surfer’. But these gds files are hard to work with, how can I make that easier? Several days later Ok so I wrote a basic GDS viewer in raylib but I can’t get the blocks to sit quite the way I want to. So anyway, I realised I’m down too many tangents and it’s time to drop all of the custom software. Ok we’re done with that section. Aren’t you glad you skipped it? Focus, Chris, Focus. The Jane Street blog actually points to quite a handy GDS Viewer, so I spent some time just looking at it real hard and hoping something would come to me. I was able to roughly annotate what I though were which inputs, and I could later confirm that by looking through the approximate locations of wires in the files. Because this was the warmup I could compare what I knew about the circuit against what I could see. What do these files represent? These files seem to have some sense of ‘layers’ of different types of material or something, I imagine it’s a bit like a big 3d-printer that has to be told where to move the print head, and at what depth it needs to put a new material. Maybe these files are close to the instructions to the machine? But rather than having arbitrary positions in vertical space they seem to have standard layers of standard widths so that simplifies things. I wanted to prove that I could at least operate on these files, so I tried to extract the Jane Street logo on the upper right corner. Somehow this was way harder than I thought and I ended up extracting everything except the Jane Street logo? But whatever good enough, lets move on. I also at some point work out that the library I’m using can extract the elements to SVG file formats, and it includes a bunch of text describing the parts of the elements. This will be key to actually understanding the challenge because I can maybe use that information to work out which parts are inputs and outputs. Time to actually read about these elements I’ve gotten as far as I can with guessing. Time to actually read some proper documentation. Looks like this is their official home, despite the ‘unofficial’ in the name - sky130-unofficial The docs had the answers to many of my questions. Why do I always do things the hard way? It turns out that this ‘sky130’ thing is like a … standard? Or something for making chips. I guess making chips is hard, and so it makes sense for there to be common design elements. Crucially it also contains the descriptions of what the elements do, which is easy for elements like ‘and’ that are probably an ‘and gate’ but less clear for a ‘o21bai’ which is a …. well don’t worry too much about that. Using the information from the docs and the labels from the SVG I can now theoretically map specific geometry to the I/O of the circuit elements, which I guess will be the first step to turning it into a ‘real circuit’. I get really lucky here, in that my library has the ability to check if two elements overlap in 2d space (remember these gds files are actually a description of a 3d geometry). I wasn’t sure how reasonable the assumption of the labels overlapping the correct locations, but it worked way better than I expected! I guess labels are already referenced on their centerpoint! It even picked up some geometry that isn’t visually connected so a visual inspection would never have revealed their connections. And looking at the total design’s IO ports, it’s so much less visually noisey. I think I can make a graph now? I think I have what I need now to extract a circuit from this gds file. This isn’t going to be easy. This thing has 1k paths and almost 17k polygons even after ignoring everything I don’t care about. I need to find a way of finding things that are ‘touching’, which means that they are on adjacent layers and also overlapping. My algorithm is pretty terrible, but it does the job for now. I also introduce a simplification step where I take all of the ‘wire segments’ and …. compress? or coalesce? them into a single wire. The logic is, that if two wires are touching then they’re actually the same wire from my perspective. Luckily I spent several weeks grinding leetcode last year while unemployed so a few graph algorithms weren’t going to slow me down. Many days later The next few days of work were not easy. In my working log I have recorded that “By beating my bloodied face against the keyboard for several hours and cursing how long I’ve already spent on this, I’ve managed to nail down a tricky bug”. I’m not exactly sure what that bug was now, but I’m sure it deserved it. I’ve started to be able to turn my network in to real descriptions of hardware in a language called ‘Verilog’, which also allows me to run basic simulations like checking that ‘turning this pin high makes that one go low’. I’m eventually able to extract all the components into a handful of spaghetti, and I spend time manually drawing out the connections. I don’t use any tooling (other than excalidraw, my drawing program). I mostly just look at it real hard until things make sense. Again, I do things the hard way Not pictured: Sanity But in any case I now had an understanding of the major components of the warmup puzzle - two shift registers (that shift things), an adder (that adds things) and a comparitor (that compares things) and I work on trying to simulate the outputs. I know that the input needs to sum to be 496 as the comparitor is named comparitor496 so I just need to put in the correct sequence of bits to achieve that. That’s just simple maths, the hard part was trying to get all the various parts all working together in a single simulation. If only there were some way of doing this that didn’t involve trading off my sanity for progress. A few hour later and it’s done! I finally got this thing to work! It’s at this point I knew I had a chance of solving this thing, but it was a race against the clock, and my immune system was starting to give out. On to the real puzzle The real puzzle has many more component types (81 vs 20 or so) and many more of them (almost 10k vs 1k) so this won’t be easy. I was able to quickly get most aspects of my scripts working from the warmup steps, so long as I