Reverse engineering van een ASIC — Per aspera ad astra

Jane Street heeft onlangs een puzzel uitgebracht waarbij het doel is om een ASIC-chip te reverse-engineeren, uit te zoeken wat deze doet en een oplossing in te dienen. Ik heb mijn vriend Leander overgehaald om mee te doen. Tijdens het proces realiseerde ik me dat de weg naar de oplossing op een visueel mooie manier beschreven kon worden; dit is mijn poging tot die beschrijving.

Dit artikel is bedoeld als een oplossing, met name voor degenen die de uitdaging hebben gelezen maar deze niet in hun planning konden passen. Het is bedoeld om de centrale ideeën over te brengen die nodig zijn om tot een oplossing te komen.

---

Deel I: Wat is GDS?

De eerste stap is het openen van de bestanden. In principe is dit het eenvoudigste gedeelte.

De bestanden

Afgezien van de warmup-puzzel — die je zeker moet proberen — bestaat de puzzel uit slechts twee bestanden: puzzle.gds en example_inputs.vcd. De puzzel draait om het Graphic Data System (GDS) bestand. De voorbeeld-inputs dienen als eenvoudige testcase: één input en de output die de chip daarvoor zou moeten produceren.

Lagen

Wanneer we het GDS-bestand openen in een gespecialiseerd programma zoals KLayout, zien we direct de structuur. Het beschrijft een lay-out: polygonen van verschillende typen, aangeduid door hun laag. Het bevat ook annotaties, waardoor het bestand bij het eerste openen als een chaos oogt.

Cellen

Het GDS-bestandsformaat maakt het mogelijk om polygonen te groeperen in cellen. Dergelijke cellen kunnen eenmaal worden gedefinieerd en vervolgens meerdere keren worden geplaatst. Meestal definiëren ze logische poorten, die op hun beurt weer registers, rekenunits en dergelijke vormen. Deze hiërarchie maakt het ontwerpen van een chip beheersbaar. Hoewel deze hiërarchie doorgaans het resultaat is van een beschrijving op een hoger niveau in Verilog, die uiteindelijk wordt vertaald naar deze lay-out, geven de celgrenzen ons een structuur om mee te werken, zelfs zonder de originele Verilog-code.

Slechts een lay-out

Hoewel een GDS-bestand een lay-out definieert, zegt het op zichzelf weinig over de betekenis daarvan. Zelfs een visuele weergave is suggestief, omdat we de lagen vaak al kleuren en diktes hebben gegeven. Alleen op basis van het bestand zouden we niet weten welke lagen metaal zijn, welke silicium, of hoe een fabriek ze zou omzetten in een werkende chip.

Om hier zin aan te geven, moeten we het productieproces weten waarvoor de chip is ontworpen. Elk proces heeft eigen conventies voor wat de laagnummers betekenen. Deze staan beschreven in een process design kit (PDK), samen met de regels voor het gebruik van de verschillende materialen. Voordat we het circuit kunnen lezen, moeten we dus bepalen om welk proces het gaat.

Het proces identificeren

Gelukkig geven de namen van de logische cellen een directe aanwijzing. Ze beginnen met sky130fdsc_hd__, wat wijst op een standard-cell library voor het SkyWater 130 nm-proces. Een standard-cell library is een collectie kant-en-klare componenten, zoals logische poorten en flip-flops, die een chipontwerper kan gebruiken zonder elke component vanaf de transistoren te hoeven tekenen.

De documentatie voor dit proces en deze bibliotheek is openbaar, dus we kunnen opzoeken wat de lagen betekenen en wat de cellen precies doen. Dat is aanzienlijk handiger dan dit zelf uit de polygonen moeten afleiden.

De lagen

Met de documentatie kunnen we namen toekennen aan de lagen. Onderaan definiëren nwell, diff en poly de delen van de transistoren. Daarboven bevindt zich li1 (local interconnect), die transistoren binnen een cel met elkaar verbindt.

Daarboven liggen vijf metaallagen, met1 tot en met met5, voor de bedrading tussen cellen en het transporteren van signalen over de chip. Meerdere lagen zorgen ervoor dat draden elkaar kunnen kruisen zonder elkaar te raken. Om een draad van de ene laag naar de volgende te verbinden, is er een verbinding door het isolatiemateriaal nodig, een zogenaamde via. De cut-lagen (die eindigen op /44) specificeren waar deze verbindingen lopen.

Dit onderscheid is cruciaal bij het volgen van de draden. Twee polygonen kunnen in een bovenaanzicht overlappen zonder elektrisch verbonden te zijn; we moeten dus zowel de lagen als de vormen bijhouden.

(Afbeelding: Een dwarsdoorsnede door de lagen met verbindingen ertussen. De diktes en tussenruimtes zijn aangepast voor de zichtbaarheid en zijn niet op schaal.)

Inputs en outputs

Het bestand bevat ook tekstlabels op sommige lagen. Op het hoogste niveau benoemen deze de inputs en outputs van de chip.

Aan de linkerkant vinden we clk (de klok), samen met rst_n, enable en I. Aan de rechterkant bevinden zich de acht bits van O en een aparte success-output. De puzzel vraagt ons om een input te vinden die ervoor zorgt dat success hoog wordt. We weten nog niet wat die input moet zijn, maar we weten nu waar we deze moeten sturen en waar we het resultaat kunnen controleren.

De pinnen van een cel

Als we inzoomen op een van de logische cellen, vinden we een andere set labels. Deze geven aan waar de inputs en outputs van de cel aansluiten op de bedrading eromheen. In het geval van een XOR-poort zijn dit de inputs A en B, en de output X.

Er zijn ook VPWR en VGND (voeding en massa). Deze lopen langs de boven- en onderkant van de cel, zodat naburige cellen ze kunnen delen. De labels zelf zijn slechts annotaties; het is het geleidende materiaal eronder dat de verbinding vormt. Later kunnen we deze posities gebruiken om uit te zoeken hoe de poorten met elkaar verbonden zijn.

De transistor

Logische poorten zijn gemaakt van transistoren. Voor ons doel kunnen we een transistor beschouwen als een elektrisch gestuurde schakelaar: de spanning op één terminal, de gate, bepaalt of er stroom kan vloeien tussen de andere twee, de source en drain.

In de lay-out herkennen we een transistor waar een strip polysilicium een diffusiegebied kruist. Het polysilicium vormt de gate, gescheiden van het silicium door een dunne isolerende laag. De diffusie aan weerszijden vormt de source en drain. Hoewel deze vormen in de tekening overlappen, is de gate niet direct verbonden met het materiaal eronder.

(Afbeelding: Een transistor in dwarsdoorsnede: de gate bevindt zich boven een dunne isolerende laag, met de source en drain aan weerszijden. Spanning op de gate trekt een kanaal samen onder de oxide, waardoor stroom van source naar drain loopt.)

Er zijn twee soorten transistoren in deze cellen: nMOS en pMOS. In simpele termen geleidt een nMOS wanneer de gate hoog is, terwijl een pMOS geleidt wanneer de gate laag is. Door deze twee te combineren, kunnen we een circuit maken dat de output verbindt met ofwel de voeding of de massa, afhankelijk van de inputs.

(Afbeelding: Symbolen voor nMOS en pMOS transistoren. Het kleine cirkeltje op de pMOS-gate geeft aan dat deze geleidt bij een laag signaal.)

Voor onze analyse kunnen we echter werken met de logische poorten die deze transistoren vormen.

De XOR-poort

Een XOR-poort is een eenvoudig voorbeeld. Hij heeft twee inputs, A en B, en één output, X. Als de inputs verschillen, is de output één. Als ze hetzelfde zijn, is de output nul. We kunnen de hele cel behandelen als deze ene operatie.

In de lay-out markeren de labels A, B en X de aansluitingen op li1. Als we de waarden op de twee input-draden kennen, kunnen we de waarde op de output-draad berekenen en deze doorgeven aan de volgende poorten. Zo kunnen we de chip simuleren.

(Afbeelding: Het XOR-schema over een vage kopie van de lay-out. De draadkleuren komen overeen met de kleuren aan de rechterzijde.)

Flip-flops

De meeste cellen zijn direct: hun output is een functie van de huidige inputs. Een flip-flop is anders, omdat deze het circuit in staat stelt een waarde te onthouden.

Een flip-flop heeft een data-input D, een output Q, en een klok-input CLK. Op het moment dat de klok van laag naar hoog gaat (de stijgende flank), wordt de waarde van D de nieuwe waarde van Q. Deze waarde blijft behouden tot de volgende stijgende flank, ongeacht wat er in de tussentijd met D gebeurt.

(Afbeelding: De klok, de data en de opgeslagen bit. Q neemt de waarde van D alleen bij de stijgende flank van CLK en behoudt deze tot de volgende.)

In de praktijk zijn er nuances zoals setup en hold tijden, maar voor onze analyse volstaat het om een stijgende klokflank te beschouwen als één precies moment waarop elke flip-flop wordt bijgewerkt.

De flip-flops in dit circuit hebben ook een RESET_B (een active-low reset). Het laag trekken hiervan dwingt Q naar nul zonder te wachten op een klokflank. Er zijn 92 flip-flops op de chip. We kunnen het circuit dus zien als een systeem met 92 bits aan status, waarbij de klok bepaalt wanneer deze bits worden bijgewerkt.

Clock buffers

Buffers zijn minder interessant; ze dienen enkel om het kloksignaal over grote afstanden te transporteren. Omdat een kleine poort niet altijd een lange draad of veel andere poorten snel genoeg kan aansturen, worden buffers geplaatst om het signaal te versterken. Voor ons betekent dit dat we ze grotendeels kunnen negeren en ons alleen op de klok zelf hoeven te concentreren.

Terug naar de gehele chip

Als we de cellen inkleuren op basis van het type component, zien we dat een groot deel van de chip is opgebouwd uit een paar basisbouwstenen. De lay-out is nog steeds overweldigend, maar we hebben nu een idee van wat we bekijken. Om uit te zoeken wat de hele chip doet, moeten we weten hoe deze componenten verbonden zijn. Dat is wat we in deel twee zullen doen.

---

Deel II: Het circuit herstellen

Nu we begrijpen hoe een GDS-bestand de lay-out definieert, moeten we uitzoeken hoe we het circuit kunnen reconstrueren.

Cellen abstraheren

We hoeven geen individuele transistoren te simuleren. Net zoals we het Sky130-proces herkenden aan de celnamen, kunnen we de functies van de cellen uit hun namen afleiden. Elke celnaam beschrijft een component: xor2 is een XOR-poort, and4bb is een AND-poort met vier inputs waarvan er twee geïnverteerd zijn, enzovoort. We kunnen elke cel dus behandelen als het logische component dat het vertegenwoordigt.

Waar een cel aansluit

Om componenten te verbinden, moeten we twee dingen weten: welk deel van de cel komt logisch overeen met welke pin van de poort, en welke geleidende draden verbinden twee cellen?

Het eerste wordt beantwoord door de laag 67/5 (de li1 label laag). Hier zien we waar de inputs en outputs aansluiten. Voor de XOR-poort zijn dit A en B voor de inputs en X voor de output. De voeding- en massalabels, VPWR en VGND, staan op laag 68/5 (de met1 label laag).

Deze labels geleiden zelf niet. De signaallabels verwijzen naar het geleidende materiaal eronder op laag 67/20 (li1 drawing), de laagste bedradingslaag die we gebruiken voor het traceren. Vormen die elkaar raken op dezelfde geleidingslaag zijn verbonden. Verbindingen naar een andere laag vereisen een contact of via.

Componenten verbinden

Twee cellen zijn verbonden als er een geleidend pad tussen hen bestaat. Voor Sky130 zijn zowel de met- als de li1-lagen geleidend over afstand. Deze lagen worden verbonden door vias.

(Afbeelding: Polygonen die elkaar raken op dezelfde geleidingslaag zijn verbonden. Een contact of via verbindt aangrenzende lagen.)

De draden volgen

Door de verbonden geleiders te volgen, kunnen we elke draad traceren. Door dit te combineren met de componenten verkrijgen we de netlist.

De netlist afleiden

Het volgen van deze verbindingen resulteert in een lijst van poorten en welke pinnen een draad delen. Dit is de netlist. Voor elke poort bewaren we het celtype en voor elke pin noteren we met welke draad deze is verbonden.

Eén draad kan met meerdere poorten verbonden zijn. Een verbinding met de data-input D van een flip-flop betekent iets heel anders dan een verbinding met de klok-input CLK, zelfs als beide verbindingen dezelfde component bereiken.

Met deze informatie kunnen we het circuit tekenen als een graaf. De componenten hoeven niet meer op hun fysieke plek op de chip te staan; we kunnen ze zo rangschikken dat de verbindingen makkelijker te volgen zijn. De voedingslijnen laten we weg, aangezien we de voeding als constant beschouwen.

Buffers negeren

We kunnen ook de klokbedrading vereenvoudigen. Omdat klokbuffers hetzelfde logische signaal herhalen, kunnen we ze terugvolgen om te zien welke klok elke flip-flop aanstuurt. In deze chip worden ze allemaal bijgewerkt op dezelfde stijgende flank.

Tussen deze updates houden de flip-flops hun huidige waarden op Q. Samen met de chip-inputs geven dit de waarden die nodig zijn voor de berekeningen. Zodra we alle inputs van een poort weten, kunnen we de output berekenen en deze doorgeven. Dit herhalen we tot we de outputs van de chip en de waarden op elke D-input van de flip-flops hebben. Daarna werken we alle flip-flops tegelijk bij (waarde van D wordt Q), tenzij een reset is geactiveerd. Dit proces herhalen we per cyclus.

Het circuit testen

We kunnen nu het bestand example_inputs.vcd gebruiken om te controleren of onze simulator werkt. Een VCD-bestand registreert hoe signalen in de loop van de tijd veranderen. Het bevat zowel de inputs die naar de chip zijn gestuurd als de geproduceerde outputs.

Het voorbeeld begint met het laag houden van rst_n gedurende drie klokcycli om de chip te resetten. Daarna wordt enable hoog gezet en worden er 121 bits via I verzonden, één per cyclus. Daarna gaat enable weer laag en lezen we de output op O.

Wanneer we deze sequentie in onze simulator volgen, zien we dat alle 730 output-bitwaarden exact overeenkomen met de opname. Dit geeft ons vertrouwen dat het circuit correct is gereconstrueerd.

De output op O is acht bits breed. Wanneer we deze bytes interpreteren als ASCII, krijgen we de tekst TRY AGAIN. Dit is geruststellend voor de simulator, maar vertelt ons nog niets over wat de chip van ons verwacht. Om dat te ontdekken, moeten we kijken naar wat het circuit daadwerkelijk doet.

---

Deel III: De werking afleiden

Nu we het circuit kunnen draaien, is het tijd om de functie te achterhalen. Dit is over het algemeen moeilijk omdat dezelfde functie op veel verschillende manieren met poorten kan worden gebouwd. Het testen van elke mogelijke 121-bit input zou $2^{121}$ combinaties betekenen, wat onmogelijk is.

We hebben echter een belangrijke aanwijzing gekregen: de locatie van elke component is betekenisvol.

De lay-out bestuderen

We groeperen de componenten op basis van hun locatie. Door de output-schrijver te scheiden van de rest, vinden we in totaal elf regio's. We noemen de output-schrijver R11.

De cellen buiten deze regio's zijn klokbuffers; deze laten we weg uit het regiodiagram, maar we houden wel bij welke klok welke flip-flop aanstuurt. Door deze grenzen te trekken, kunnen we de logica van elke regio apart behandelen als een subcomponent met eigen inputs en outputs.

Hoe de regio's verbonden zijn

Met de netlist kunnen we controleren hoe regio's met elkaar communiceren. Sommige regio's liggen dicht bij de outputs, zoals R10 (die de success-bit aanstuurt) en R11 (die O schrijft). Anderen hebben veel inputs en geheugenbits, zoals R5 en R7, terwijl regio's zoals R1 er zeer weinig hebben.

De regio's ordenen

We kunnen de regio's tekenen als een graaf en rangschikken op basis van de informatiestroom. We gebruiken hiervoor het concept van het 'trofische niveau' (uit de ecologie), wat in ons geval betekent: van input naar output.

Regio 1 bevindt zich aan de basis van de keten en voedt stroomafwaarts. We analyseren de regio's daarom in de volgorde van R1 tot R11.

R1

Regio 1 is de simpelste. Naast de klok en reset heeft het slechts één input-bit, afkomstig van regio 3. Wanneer we de interne status volgen, zien we dat er niets gebeurt als de input uit staat. Wanneer deze aan staat, zien we elke tick een transitie door elf verschillende waarden voordat het patroon zich herhaalt.

Aangezien de totale input 121 bits is, is dit suggestief: 121 is $11 \times 11$. We kunnen de waarden van de teller visualiseren op een raster van $11 \times 11$. Omdat er een unieke waarde is voor elke kolom, noemen we dit de kolomteller.

R2

Regio 2 heeft dezelfde inputs als de kolomteller, plus een bit dat het einde van een ronde van elf counts signaleert. Als beide signalen aan staan, doorloopt de interne status eveneens elf verschillende waarden. Op het raster vormen deze horizontale stroken. We noemen dit de rijteller. Samen geven R1 en R2 coördinaten om een punt op het $11 \times 11$ raster te lokaliseren.

R3

Dit is een klein blok dat beide tellers voedt. Het bewaakt of de enable-poort aan staat en of er minder dan 121 bits zijn geaccepteerd. Het geeft een signaal aan R10 wanneer de input compleet is.

R4

Dit blok heeft geen geheugenbits; de output is een vaste functie van de rij- en kolomteller. Wanneer we het raster inkleuren op basis van de output-waarden, ontstaan er elf verschillende 'vlakken' (patches) van variërende grootte en vorm. Dit is een lookup-tabel van rasterpositie naar vlaknummer, oftewel de patch-map.

R5

Dit is een groter blok met 22 geheugenbits. Bij nadere inspectie blijkt dit te bestaan uit elf identieke, onafhankelijke kopieën van een kleine machine. Elke kopie telt de enen in één specifieke kolom. De output is 'ja' als er exact twee enen in die kolom zitten. We noemen dit de kolom-check.

R6

Dit blok bevat drie geheugenbits. Twee bits tellen de enen in de huidige rij en stoppen bij drie. De derde bit is een vlag die 'aan' blijft zodra een rij een foutief aantal enen bevat. We noemen dit de rij-check.

R7

Dit blok werkt hetzelfde als R5, maar in plaats van de kolomteller leest het de output van de patch-map (R4). Het controleert dus of er in elk van de elf vlakken exact twee enen zitten. Dit is de patch-check.

R8

Dit blok bevat 13 geheugenbits. Een deel vormt een AND-boom die controleert of alle kolommen aan de voorwaarde voldoen. Het grootste deel is een shift register dat de vorige twaalf input-bits onthoudt. Hiermee kunnen de huidige bit en zijn buren (links, boven-links, boven, boven-rechts) vergeleken worden. Als twee enen elkaar raken (horizontaal, verticaal of diagonaal), wordt een vlag gezet. Dit is de buur-check.

R9

Dit blok bevat acht geheugenbits. Het bevat een AND-boom voor de patch-checks en een teller die het totaal aantal enen in de input telt. De output is 'ja' wanneer het totaal exact 22 is. Dit is de totaal-check.

R10

Dit blok stuurt de success-poort aan. Het verzamelt de signalen van:

• Input-voltooid vlag
• Rij-check
• Buur-check
• Kolom-check (alle kolommen hebben er twee)
• Patch-check (alle vlakken hebben er twee)
• Totaal-check (totaal aantal is 22)

Als aan alle voorwaarden is voldaan op het moment dat de input compleet is, gaat de success-bit hoog.

De regels

Samengevat zijn de succesvoorwaarden:

• Twee enen per rij
• Twee enen per kolom
• Twee enen per vlak (patch)
• Geen enkele een mag een andere een raken
• In totaal exact 22 enen

Wie dit herkent, weet dat dit de regels zijn van het spel Two Stars. De chip is dus een Star Battle validator, waarbij de elf vlakken uit R4 het speelbord verdelen.

R11: De output-schrijver

Dit is het grootste blok, dat de uiteindelijke tekst op O schrijft. Door de output te analyseren bij verschillende inputs, kunnen we zien welke berichten de chip verstuurt.

---

Acknowledgements Per aspera ad astra. Dank aan Leander Post voor het samen oplossen van de puzzel en de visuals, aan Jane Street voor de puzzel, en aan Fabio Crameri voor de kleurkaarten. Tevens dank aan Claude en Astra voor hun hulp.