Bootstrappable builds: hoe en waarom

Tijdens de今年的 editie van de Free and Open Source Software Yearly conferentie (FOSSY), die plaatsvond op de campus van de University of British Columbia in Vancouver, Canada, gaf Timothy Sample een presentatie over bootstrappable builds. Hoewel dit concept minder bekend is dan reproduceerbare builds, is het essentieel voor het begrijpen van de oorsprong van software.

In essentie is een bootstrappable build een proces dat begint met een klein programma dat een iets groter programma kan bouwen, dat op zijn beurt weer een nog groter programma bouwt, enzovoort. Dit gaat door tot de volledige moderne Linux user space is opgebouwd vanuit een klein "zaadje" (seed). Het uiteindelijke doel is om code te verkrijgen met een volledig begrijpelijke oorsprong, wat in tegenstelling staat tot de meeste huidige Linux-systemen.

De complexiteit van software-afhankelijkheden

Sample begon met de vraag of de aanwezigen bekend waren met het concept. Hij vertelde dat hij ongeveer tien jaar geleden met bootstrappable builds begon toen hij GNU Guix ging gebruiken. Guix is een "functionele pakketbeheerder", vergelijkbaar met en geïnspireerd door Nix.

In zowel Guix als Nix wordt alle software in het systeem gerepresenteerd in een derivation graph. Deze graaf beschrijft hoe elk programma moet worden gebouwd, inclusief alle benodigde inputs. Deze inputs hebben op hun beurt weer eigen inputs, wat resulteert in honderden knooppunten in moderne software.

Als voorbeeld nam hij een Python-programma:

• Een Python-programma heeft de Python-interpreter nodig om te draaien.
• De Python-interpreter is geschreven in C, dus er is een C-compiler nodig.
• Die C-compiler is zelf weer in een bepaalde taal geschreven, waarvoor opnieuw een compiler nodig is.

Bij een distributie als Debian stopt deze keten bij een C-compiler-binary die door iemand naar de repositories is geüpload. Voor Guix was het startpunt oorspronkelijk een statisch gekoppelde "blob" van 250MB aan GNU user-space programma's. Voor de ontwikkelaars van Guix was dit onbevredigend, omdat de exacte oorsprong van die blob niet volledig helder was.

Wat zijn bootstrappable builds?

Het basisidee van bootstrappable builds is het creëren van een systeem dat gebouwd kan worden zonder te vertrouwen op vooraf gebouwde artefacten (pre-built artifacts). Sample vergeleek het huidige proces van het bouwen van een C-compiler met het maken van yoghurt, waarbij je een beetje bestaande yoghurt nodig hebt om het proces te starten. "We maken in feite C-compilers met de 'starter' van Dennis Ritchie uit Bell Labs," grapte hij.

Veel programmeertalen streven naar self-hosting, waarbij de compiler van de taal in de taal zelf is geschreven. Dit creëert echter een kip-en-ei-probleem. Bootstrappable builds is een poging om dit probleem te omzeilen door tools echt "vanaf nul" op te bouwen.

Het verschil met reproduceerbare builds

Reproduceerbare builds zorgen ervoor dat een gebruiker kan verifiëren of een binary exact overeenkomt met de broncode door de binary zelf te bouwen en bit-voor-bit te vergelijken.

Bootstrappable builds pakken een ander risico aan: de integriteit van de compiler zelf. Dit refereert aan de beroemde lezing van Ken Thompson, Reflections on Trusting Trust. Thompson beschreef hoe een backdoor in een compiler kan worden verborgen, waardoor de backdoor in de resulterende binaries terechtkomt, zelfs als de broncode van het programma (zoals het login-programma) schoon is. De compiler kan namelijk zo zijn geprogrammeerd dat hij een specifieke reeks instructies herkent en vervangt door kwaadaardige code tijdens het compileren, zonder dat dit in de broncode van de compiler zelf zichtbaar is.

Een recent onderzoek ("Trusting-Trust Attack against an Entire Linux Distribution through Binary Manipulation") toonde een soortgelijke aanval aan op het strip-programma in NixOS. Omdat strip op bijna elke binary wordt uitgevoerd, konden onderzoekers vrijwel elk programma op het systeem onzichtbaar infecteren. Bootstrappable builds zijn bedoeld om dit soort aanvallen te dwarsbomen.

Strategieën voor bootstrapping

De beste manier om bootstrapping aan te pakken is proactief. Voordat een compiler self-hosted wordt, is hij meestal in een andere taal geschreven. Door die oorspronkelijke code te behouden, kan worden gegarandeerd dat er niets in de binary verborgen zit.

• GNU Guile: Deze Scheme-implementatie behoudt een C-implementatie voor bootstrapping.
• GNU Make: Heeft naast een makefile ook een shell-script voor situaties waarin make nog niet beschikbaar is.

Voor tools die alleen self-hosting ondersteunen, worden andere technieken gebruikt:

1. Archeologische opgraving: Men zoekt in de geschiedenis van een project naar een oude versie die nog niet self-hosted was. Deze wordt gebouwd met tools uit die tijd, waarna men versie voor versie naar de moderne versie toe werkt.
2. Doelgerichte tools (Bespoke tools): Er wordt een speciaal hulpmiddel ontwikkeld om een taal op te starten. Een voorbeeld is mrustc (een C++-gebaseerde compiler) die gebruikt wordt om Rust op te bouwen.

Het meest succesvolle proces is vaak een combinatie: teruggaan in de tijd naar een simpelere versie die met een speciaal hulpmiddel kan worden gebouwd, om vervolgens naar de huidige versie toe te werken.

Projecten: Guix en live-bootstrap

De "seed" van Guix is tegenwoordig gereduceerd van 250MB naar slechts 256 bytes. Dit bestaat uit een programma genaamd hex0. Het proces verloopt als volgt:

hex0 → hex1 → hex2 → M0 → M2-Planet → GNU Mes → MesCC → TCC (Tiny C Compiler) → moderne tools.

• hex0, hex1, hex2: Converters die hexadecimale tekst omzetten naar binaries, met toenemende complexiteit in labels en adressering.
• M0: Maakt het gebruik van assembly-mnemonics mogelijk.
• M2-Planet: Een dialect van C.
• GNU Mes: Een Scheme-interpreter geschreven in M2-Planet, inclusief een C-library (Meslibc) en een C-compiler geschreven in Scheme (MesCC).
• TCC: Een eenvoudiger maar completere C-compiler die vervolgens wordt gebruikt voor moderne development tools.

Een gerelateerd project, live-bootstrap, gaat nog verder en heeft geëxperimenteerd met het bootstrappen van kernels via de Fiwix-kernel. Het proces van live-bootstrap omvat maar liefst 182 stappen om tot een basis Linux-systeem te komen.

Germ: Een alternatieve benadering

Omdat de huidige keten (van C naar Scheme en terug naar C) erg complex is, werkt Timothy Sample aan een nieuwe aanpak genaamd Germ (of Germ Lisp).

Het uitgangspunt van Germ is dat een primitieve Lisp-interpreter niet veel complexer is dan een primitieve assembler. Germ is een binary van ongeveer 2,25KB die "bijna-Scheme" kan draaien. Dit is net genoeg om een assembler in Scheme te kunnen draaien, die vervolgens de tweede fase van de interpreter bouwt.

Voordelen en uitdagingen van Germ

Germ is conceptueel eenvoudiger omdat het de vele tussenstappen van bespoke assemblers en compilers overslaat. Het is direct compatibel met de Scheme-gebaseerde build-scripts van Guix.

Er zijn echter ook nadelen:

• Performance: Omdat Germ in assembly is geschreven als een interpreter uit de jaren '50, is het traag. Hoewel het sneller is dan Mes in micro-benchmarks, is het in de praktijk trager omdat bijna alles in Scheme draait (zoals loops).
• Portabiliteit: Op dit moment werkt Germ alleen op x86_64, terwijl Mes ook op Arm en RISC-V draait.

Toekomstperspectief

Sample wil Germ integreren met Guix om de huidige afhankelijkheid van de statisch gekoppelde Guile-binary (%bootstrap-guile) te vervangen. Daarnaast wil hij de performance verbeteren, mogelijk door bepaalde loop-constructies direct in assembly te schrijven of door een compiler-backend voor C te ontwikkelen. Ook is er een port naar RISC-V in planning.

Tijdens de Q&A-sessie werd besproken dat Germ een effectieve "wig" kan zijn om lange build-ketens (zoals die van Perl en Autoconf) te verkorten en zo de totale hoeveelheid stappen te verminderen, wat de verifieerbaarheid van het gehele systeem vergroot.