Het Lab: Boot strappable builds

Henk van de Kamer

In de vorige aflevering stelde ik Dusk OS voor. Dit simpele besturingssysteem begint met een kernel van slechts 3 kilobyte en dat is 1.700 keer kleiner dan mijn huidige Linux-kernel. Een ander belangrijk verschil is dat de Dusk OS-kernel bij elke start de Forth-broncode van het besturingssysteem compileert. En dat leidt ons naar een andere insteek van mijn ‘dode’ computeridee.

Vertrouwen

Ik heb weinig vertrouwen in Windows of macOS. Hun broncode is niet openbaar en in handen van Amerikaanse bedrijven. Nu Trump zijn plannen voor een dictatuur kan gaan uitvoeren, zou het mooi zijn als Europa eindelijk eens serieus gaat werken aan een plan om qua hard- en software onafhankelijk te worden van landen als Amerika en China.

In 2001 begon ik het proces om Windows te vervangen door Linux. In die tijd was de eerste crypto-oorlog over, maar was mij duidelijk dat de vijandelijkheden weer zouden opwaaien. Er waren geruchten dat Microsoft onder dwang van de NSA in Windows achterdeurtjes had ingebouwd. Alhoewel dit bij mijn weten nooit is bewezen, zou het mij ook niet verbazen. Overheden kunnen allerlei manieren bedenken om de eigen nationale bedrijven te dwingen hun wil uit te voeren. De enige manier om als burger onder dat juk uit te komen, is software gebruiken die niet onder controle van een bedrijf of overheid valt.

Broncode

Dankzij Linux heb ik de broncode en kan daardoor theoretisch controleren of er geen verborgen achterdeurtjes aanwezig zijn. In de praktijk is dat echter een onbegonnen zaak. De Linux-kernel alleen is al 22,5 miljoen regels aan voornamelijk C- en C++-code. Ik noem dat een kriebeltjes-taal en alhoewel ik het in grote lijnen kan volgen, ontgaan mij vaak de nuances. Ofwel ik hoop dat genoeg andere mensen het controleren voor mij doen. Idem voor de rest van het besturingssysteem welke waarschijnlijk richting een miljard regels aan code omvat.

Self hosting

Zelfs als de broncode geen achterdeurtjes bevat, is er een ander probleem. Een lakmoes-test voor een programmeertaal is het zichzelf kunnen compileren. Leuk, maar ook vrij nutteloos. Waarom? Op zich is het een goede test als een programmeertaal zichzelf succesvol kan compileren. De code van een programmeertaal vraagt vaak het uiterste van een compiler, ofwel als er in deze stresstest geen problemen worden ontdekt, is dat een goede indicatie van de kwaliteit.

Om mijn bovenstaande uitspraak te demonstreren, moet je voor de aardigheid eens een (virtuele) kale Linux-distributie installeren. Mag grafisch, maar voor deze demonstratie niet nodig. Controleer of niet per ongeluk een verouderde versie van GCC (spoiler) is geïnstalleerd:

hvdkamer@bookworm:~$ gcc

-bash: gcc: command not found

Als je een melding krijgt dat er geen broncodebestand is opgegeven, moet je het GCC-pakket voor dit experiment verwijderen. De volgende stap is de broncode van GCC downloaden [https://ftp.nluug.nl/languages/gcc/releases/gcc-14.2.0/gcc-14.2.0.tar.gz] – liefst 153 megabyte groot (!) – en uitpakken:

hvdkamer@bookworm:~$ tar -xzf gcc-14.2.0.tar.gz

Met deze versie hebben we na afloop een directory gcc-14.2.0. De documentatie raadt aan om het compileren in een aparte directory te doen. Ofwel:

hvdkamer@bookworm:~$ mkdir build

hvdkamer@bookworm:~$ cd build/

hvdkamer@bookworm:~/build$ ../gcc-14.2.0/configure

...

checking for gcc... no

checking for cc... no

checking for cl.exe... no

configure: error: in `/home/hvdkamer/build':

configure: error: no acceptable C compiler found in $PATH

See `config.log' for more details

De derde opdracht is volgens de documentatie de juiste. Desondanks breekt het proces af, omdat er geen bruikbare C-compiler wordt gevonden. Euh? Was het geheel niet self hosting?

Gedachtefout?

Als ik self hosting lees in de documentatie van een compiler, is mijn verwachting dat het geheel zichzelf kan bootstrappen in een kaal besturingssysteem. Ofwel er is een programma – klein en uiteraard met code – dat als zaadje de rest van de boom – lees compiler – laat groeien naar uiteindelijk de compiler zelf. Om te controleren of het hele proces foutloos is verlopen, kunnen we dan deze nogmaals zijn eigen broncode laten compileren. Het resultaat zou dan byte voor byte identiek moeten zijn.

In plaats van bootstrap verwacht GCC, maar ook bijna alle andere zogenaamde self hosting- programmeertalen, een oudere versie van zichzelf. Of zoals we hierboven zien de Microsoft Visual C++-compiler. Bij mijn weten is daar geen Linux-versie van beschikbaar. Daarmee zitten we nu in een spagaat. Of we vertrouwen een oudere gecompileerde versie van GCC of we vertrouwen Windows. Beide zijn onacceptabel!

Vertrouw in vertrouwen

Ken Thomson, één van de originele Unix-programmeurs, schreef in 1984 een artikel met als titel Reflections on Trusting Trust. In dit artikel laat hij zien hoe een compiler zijn eigen broncode kan aanpassen om een achterdeur in te bouwen. Uiteraard via het aanpassen van de broncode, maar zodra die is gecompileerd, wordt de detectie van deze achterdeur vrijwel onmogelijk. Omdat een oudere versie van de compiler nodig is om de nieuwere broncode te compileren, hebben we nu een enorm probleem!

In 2019 was de code van GCC al gegroeid tot 15 miljoen regels. Op zich al een enorme taak om te controleren op achterdeurtjes, die zoals we nu weten niet eens in de code aanwezig hoeft te zijn! Als we onze kwaadaardige compiler kunnen verspreiden, wordt tijdens het compileren automatisch de achterdeur in elke nieuwere versie ingebouwd. Een aantal afleveringen geleden heb ik Ghidra gebruikt om een gecompileerd programma te ontleden. Dat programma was zeer klein, GCC is ruim 1 miljoen bytes groot ofwel dit wordt zoeken naar een speld in een hooiberg.

Bootstrappable builds

Het vertrouwen in broncode is mogelijk niet gerechtvaardigd, maar zolang deze openbaar is en door genoeg mensen wordt bestudeerd, is het in ieder geval te verdedigen. De volgende stap is uitvogelen hoe we het proces waarmee de broncode wordt gecompileerd, kunnen vertrouwen. Het GNU Project – leverancier van de basis in elke Linux-distributie – begon voor hun Guix-distributie in juni 2016 [https://lists.gnu.org/archive/html/guile-user/2016-06/msg00061.html] over dit probleem na te denken.

Naast een gecompileerde vorige versie van een compiler is nog veel meer nodig. Deze collectie programma’s noemen we de bootstrap binaries. Met deze kan een nieuwere versie gemaakt worden. Bedenk dat dit alles niet de kernel bevat. De oude versie compileert de nieuwe versie en die wordt vaak via chroot – change root – gestart, ofwel is daarmee onafhankelijk – op de kernel na – van wat er op het systeem draait. In deze chroot compileren we vervolgens nogmaals de  bootstrap binaries en wat we verder nodig hebben voor onze Linux-distributie. Klinkt moeilijk, maar wie handmatig zelf de Linux From Scratch [https://www.linuxfromscratch.org/] distributie handmatig heeft gebouwd, snapt de truc.

Helaas hebben we nu het probleem of we de voorgaande compiler kunnen vertrouwen enorm opgeblazen. In plaats van de ruim één megabyte had Guix in 2016 ruim 250 megabyte in hun bootstrap binaries. Voor Debian is dat  ruim een factor twee meer. Bedenk dat naast een achterdeur in een compiler er veel meer mogelijkheden zijn om deze te verstoppen.

Uitdunnen!

Op dit punt zijn we aanbeland op de andere insteek van mijn ‘dode’ computeridee. We moeten gewoon terug naar het begin toen er nog geen software was. We starten met een eerste, zeer simpele programmeertaal welke we in machinetaal schrijven. In het verleden was dat vaak een assembler, maar er zijn aanwijzingen dat we die stap kunnen overslaan. De Dusk OS bevat in zijn kleine kernel een basale Forth-compiler. Daarmee kunnen we het geheel bootstrappen naar een omgeving met bijvoorbeeld een simpele C-compiler. En met die kunnen we stapsgewijs steeds complexere C-compilers met uiteindelijk GCC verkrijgen. Hetzelfde geldt voor de bootstrap binaries.

Dit versimpelen wordt in Guix van twee kanten benaderd. De eerste is het reduceren van de bootstrap binaries uit 2016. In oktober 2019 werd de 250 megabyte bijna gehalveerd naar 130 megabyte [https://guix.gnu.org/blog/2019/guix-reduces-bootstrap-seed-by-50/]. Vervolgens lukte het in juni 2020 om het geheel nogmaals te halveren naar zo’n 60 megabyte [https://guix.gnu.org/blog/2020/guix-further-reduces-bootstrap-seed-to-25/]. En in april 2023 was dit alles teruggebracht naar 357 (!) bytes [https://guix.gnu.org/en/blog/2023/the-full-source-bootstrap-building-from-source-all-the-way-down/]. Oké, niet helemaal want deze wordt uitgevoerd door de Linux-kernel.

Tot slot

Helaas moet ik hier stoppen. In de volgende aflevering laat ik via een virtuele machine – ja, die draait weer in een volledige Linux-omgeving, maar niet iedereen heeft fysieke hardware staan voor dit experiment – zien hoe dit werkt. Plus dat ik uitleg waarom we er dan nog steeds niet zijn.