Het artikel bespreekt de transitie in de x86-architectuur van fijnmazige geheugenbescherming (segmentatie) naar platte adresruimtes, een trend die mede is ingezet door de dominantie van Unix. De auteur betoogt dat er een fundamentele mismatch bestaat tussen de recursieve manier waarop software geheugen onderverdeelt (bijvoorbeeld via memory pools of geneste structuren) en de niet-recursieve aard van hardware.
Er worden verschillende benaderingen besproken om dit gat te overbruggen:
- CHERI: Een model dat veiligheid probeert te garanderen via capabilities en monotone grenzen, waardoor hardwarematige ondersteuning voor software-onderverdelingen ontstaat.
- liballocs: Een softwarematige abstractie die probeert de recursieve boomstructuur van allocaties reflectief vast te leggen.
- Language-VM's: Deze benadering fragmenteert geheugen maximaal in kleine objecten, wat echter ten koste gaat van de ruimtelijke lokaliteit en prestaties.
De kernvraag is in hoeverre hardware kennis moet hebben van de softwarematige onderverdelingen om zowel veiligheid als efficiëntie te waarborgen.
Flat versus gesegmenteerd geheugen — het is recursief
Mijn recente verkenningen in x86-segmentatie hebben me doen opmerken dat er een trend zichtbaar is in de evolutie van x86: de afname van fijnmazige geheugenbescherming. Dit is zowel merkbaar bij de overgang naar 64-bit als in de snelle system-calling functies van daarvoor. Beide ontwikkelingen hebben het geavanceerde segmentatiesysteem, dat sinds de 286 een kenmerk van de architectuur was, gedeeltelijk lamgelegd.
De verklaring hiervoor is mogelijk Unix. De dominantie van Unix en de voorkeur voor platte adresruimtes boven gesegmenteerde ruimtes — waarschijnlijk overgenomen van de PDP-11 of zelfs de PDP-7 — betekende dat er simpelweg geen vraag was naar een 64-bit versie van de segmentatiefuncties.
De terugkeer van niet-platte geheugenmodellen
Tegenwoordig graap ik vaak tegen WebAssembly-enthousiastelingen dat "gesegmenteerd geheugen terugkeert". WebAssembly lijkt in zekere zin een terugkeer naar het programmeermodel van OS/2 of andere niet-Unix-besturingssystemen, waar "platheid" niet zo dominant was.
Deze vorm van niet-platheid is uiteraard nog steeds zeer relevant voor veiligheid en security. Onlangs las ik opnieuw enkele teksten van Poul-Henning Kamp, die CHERI beschrijft als een reactie op platte geheugenmodellen, die hij omschrijft als "onveilig bij elke snelheid". Kamp merkt op dat het eerste wat software doet op elk plat geheugen, het opleggen van een onderverdelingsstructuur is.
De vraag is in hoeverre de hardware kennis moet hebben van deze onderverdeling. CHERI zegt "ja", terwijl eerdere hardware "nee" zei — behalve natuurlijk in bepaalde gevallen voor een reeks segmentatiefuncties.
Natuurlijk beschikt segmentatie zoals gerealiseerd in x86 niet over de semantiek die nodig is voor fijnmazige inkapseling (confinement), oftewel inkapseling binnen specifieke hoeken van de niet-platte adresruimte. Onbevoorrechte code kan segmentregisters opnieuw laden en daarmee elk gedefinieerd segment bereiken, op basis van een zeer grofmazig model met vier privilege-ringen. De niet-platheid van traditionele segmenten was dus eerder bedoeld voor foutisolatie dan voor security: het was veilig tot aan grofmazige onderscheidingen zoals gebruiker versus systeem, en bood verder alleen bescherming tegen incompetentie, niet tegen kwaadwillendheid.
De recursieve aard van geheugen
Ik denk echter dat de vraag "ja of nee" de verkeerde benadering is. Het is recursief. Wanneer we een onderverdelingsstructuur hebben opgelegd aan een plat geheugen, willen we dat vaak opnieuw doen. Denk aan arenas of memory pools, maar ook aan velden binnen structuren (die weer binnen structuren zitten).
De kwestie is dus niet of het geheugen plat is of niet — de mentale abstractie van de programmeur is namelijk nooit plat — maar hoe we een fundamenteel recursief fenomeen dat door programmeurs wordt toegepast (namelijk onderverdeling) kunnen verenigen met hardware, die juist niet-recursief is.
Hardware is conceptueel een finite-state machine, en de engineering-praktijk geeft de voorkeur aan vaste structuren en begrensde dieptes. Misschien biedt een ultra-CISC CPU enige iteratie in de microcode, maar dat is ongeveer de limiet.
Als hardware niet-recursief is maar software wel, hoe lossen we dat verschil dan op?
Benaderingen van hardware-ondersteuning
Een naïeve aanpak is om de diepte te begrenzen: de hardware herkent bijvoorbeeld tot N niveaus van decompositie (waarschijnlijk met N=1), en de rest wordt aan de software overgelaten. Dit is echter onbevredigend; het is alsof de hardware haar handen wast van wat de programmeur doet. Het garandeert inconsistentie en het verlies van enige toegevoegde waarde van de hardware bij hogere N.
CHERI doet dit niet. Het behoudt de flexibiliteit om met recursieve decompositie om te gaan omdat de software de recursieve stappen nog steeds afhandelt:
- Grenzen kunnen willekeurig smal zijn.
- Deze grenzen worden door software vernauwd en expliciet doorgegeven.
Wat je op een bepaald punt kunt adresseren, wordt daarom niet zozeer bepaald door de staat van de hardware, maar door een emergentie van de software: wat binnen bereik is gekomen van de momenteel uitvoerende code. Dit is de transitieve afsluiting van bereikbare capabilities. (Deze emergentie zorgt overigens voor een evidente moeilijkheid bij auditing, hoewel de juiste tools dit zouden kunnen oplossen.)
CHERI koopt deze flexibiliteit ironisch genoeg door een restrictie: adressering is beperkt tot een ononderbroken keten van capability derivation-operaties met monotoon afnemende grenzen.
Ik heb altijd een zekere ongemakkelijkheid gevoeld bij deze afweging. Software is immers software, en sommige programma's zullen hun eigen weg kiezen, bijvoorbeeld door vreemde, niet-monotone adresberekeningen uit te voeren. Onze decennialange erfenis van programma's die hun navigatie door een onderverdeelde adresruimte in software uitdrukken — precies zoals ze dat willen — botst met elke nieuwe, meer dwingende hardware. Het overwinnen hiervan is een kwestie van ontwikkelingsinspanning, maar die inspanning wordt pas genormaliseerd (en de kosten "succesvol" geëxternaliseerd over de industrie) als CHERI (of iets soortgelijks) definitief doorgebroken is.
liballocs en recursieve abstractie
Bij de ontwikkeling van liballocs heb ik me veel minder beziggehouden met security en ben ik daarom grotendeels vrijgebleven van het voorschrijven van regels over hoe adressen mogen worden afgeleid. In plaats daarvan heb ik me meer gericht op het beschrijvend vastleggen van welke structuur echte software ook maar heeft bedacht terwijl deze de platte adresruimte recursief onderverdeelt.
In de kern van liballocs zit een recursieve abstractie: allocaties nesten binnen andere allocaties, waardoor een boomstructuur ontstaat. Er is geen "niveau-N afkap" of harde scheiding tussen hardware en software; het is fundamenteel software die de structuur tot in de kleinste details wil vastleggen via reflectieve abstracties. Deze zijn zo uniform mogelijk, ondanks hun vele en heterogene implementaties binnen het systeem.
Dit idee van een "homogene interface, heterogene implementatie" wordt vaak geassocieerd met objectgeoriënteerd programmeren, en zelden met hardware. Hoewel liballocs zelf geen mening heeft over hoe programma's de recursief onderverdeelde structuur gebruiken, zou het zeker kunnen worden ingezet voor extra beveiligingsmechanismen. Deze zijn echter alleen beveiligd tegen kwaadwillendheid als de onderliggende hardware nuttige primitieven biedt om die mechanismen zelf te beveiligen binnen dezelfde adresruimte.
Vervelend genoeg zou x86-stijl segmentatie een bijna voldoende basis hiervoor zijn geweest, als het besturingssysteem dit daadwerkelijk beschikbaar had gesteld aan de userland. Voor wat ik ongeveer zoek, word ik constant herinnerd aan het amusement-getitelde paper "Lord of the x86 Rings".
De tegengestelde benadering van Language-VM's
Om af te sluiten met een andere objectgeoriënteerde noot: de klassieke benadering van language-VM's bij onderverdeling doet precies het tegenovergestelde van hardware. Alles wordt maximaal onderverdeeld in minuscule objecten, met een enorme, expliciete interreferentie-relatie (pointers) tussen hen.
De programmeur heeft ongetwijfeld grovermazige structuren in zijn hoofd, maar die blijven daar; het systeem biedt niet aan om de opslag rondom deze structuren te organiseren. Als gevolg hiervan offeren deze systemen de ruimtelijke lokaliteit (spatial locality) op — de heuristiek van hardware om bytes of woorden samen te groeperen in grotere eenheden. Dit verklaart de langdurige prestatie-nadelen van dergelijke benaderingen.
Flat versus gesegmenteerd geheugen — het is recursief
Mijn recente verkenningen in x86-segmentatie hebben me doen opmerken dat er een trend zichtbaar is in de evolutie van x86: de afname van fijnmazige geheugenbescherming. Dit is zowel merkbaar bij de overgang naar 64-bit als in de snelle system-calling functies van daarvoor. Beide ontwikkelingen hebben het geavanceerde segmentatiesysteem, dat sinds de 286 een kenmerk van de architectuur was, gedeeltelijk lamgelegd.
De verklaring hiervoor is mogelijk Unix. De dominantie van Unix en de voorkeur voor platte adresruimtes boven gesegmenteerde ruimtes — waarschijnlijk overgenomen van de PDP-11 of zelfs de PDP-7 — betekende dat er simpelweg geen vraag was naar een 64-bit versie van de segmentatiefuncties.
De terugkeer van niet-platte geheugenmodellen
Tegenwoordig graap ik vaak tegen WebAssembly-enthousiastelingen dat "gesegmenteerd geheugen terugkeert". WebAssembly lijkt in zekere zin een terugkeer naar het programmeermodel van OS/2 of andere niet-Unix-besturingssystemen, waar "platheid" niet zo dominant was.
Deze vorm van niet-platheid is uiteraard nog steeds zeer relevant voor veiligheid en security. Onlangs las ik opnieuw enkele teksten van Poul-Henning Kamp, die CHERI beschrijft als een reactie op platte geheugenmodellen, die hij omschrijft als "onveilig bij elke snelheid". Kamp merkt op dat het eerste wat software doet op elk plat geheugen, het opleggen van een onderverdelingsstructuur is.
De vraag is in hoeverre de hardware kennis moet hebben van deze onderverdeling. CHERI zegt "ja", terwijl eerdere hardware "nee" zei — behalve natuurlijk in bepaalde gevallen voor een reeks segmentatiefuncties.
Natuurlijk beschikt segmentatie zoals gerealiseerd in x86 niet over de semantiek die nodig is voor fijnmazige inkapseling (confinement), oftewel inkapseling binnen specifieke hoeken van de niet-platte adresruimte. Onbevoorrechte code kan segmentregisters opnieuw laden en daarmee elk gedefinieerd segment bereiken, op basis van een zeer grofmazig model met vier privilege-ringen. De niet-platheid van traditionele segmenten was dus eerder bedoeld voor foutisolatie dan voor security: het was veilig tot aan grofmazige onderscheidingen zoals gebruiker versus systeem, en bood verder alleen bescherming tegen incompetentie, niet tegen kwaadwillendheid.
De recursieve aard van geheugen
Ik denk echter dat de vraag "ja of nee" de verkeerde benadering is. Het is recursief. Wanneer we een onderverdelingsstructuur hebben opgelegd aan een plat geheugen, willen we dat vaak opnieuw doen. Denk aan arenas of memory pools, maar ook aan velden binnen structuren (die weer binnen structuren zitten).
De kwestie is dus niet of het geheugen plat is of niet — de mentale abstractie van de programmeur is namelijk nooit plat — maar hoe we een fundamenteel recursief fenomeen dat door programmeurs wordt toegepast (namelijk onderverdeling) kunnen verenigen met hardware, die juist niet-recursief is.
Hardware is conceptueel een finite-state machine, en de engineering-praktijk geeft de voorkeur aan vaste structuren en begrensde dieptes. Misschien biedt een ultra-CISC CPU enige iteratie in de microcode, maar dat is ongeveer de limiet.
Als hardware niet-recursief is maar software wel, hoe lossen we dat verschil dan op?
Benaderingen van hardware-ondersteuning
Een naïeve aanpak is om de diepte te begrenzen: de hardware herkent bijvoorbeeld tot N niveaus van decompositie (waarschijnlijk met N=1), en de rest wordt aan de software overgelaten. Dit is echter onbevredigend; het is alsof de hardware haar handen wast van wat de programmeur doet. Het garandeert inconsistentie en het verlies van enige toegevoegde waarde van de hardware bij hogere N.
CHERI doet dit niet. Het behoudt de flexibiliteit om met recursieve decompositie om te gaan omdat de software de recursieve stappen nog steeds afhandelt:
- Grenzen kunnen willekeurig smal zijn.
- Deze grenzen worden door software vernauwd en expliciet doorgegeven.
Wat je op een bepaald punt kunt adresseren, wordt daarom niet zozeer bepaald door de staat van de hardware, maar door een emergentie van de software: wat binnen bereik is gekomen van de momenteel uitvoerende code. Dit is de transitieve afsluiting van bereikbare capabilities. (Deze emergentie zorgt overigens voor een evidente moeilijkheid bij auditing, hoewel de juiste tools dit zouden kunnen oplossen.)
CHERI koopt deze flexibiliteit ironisch genoeg door een restrictie: adressering is beperkt tot een ononderbroken keten van capability derivation-operaties met monotoon afnemende grenzen.
Ik heb altijd een zekere ongemakkelijkheid gevoeld bij deze afweging. Software is immers software, en sommige programma's zullen hun eigen weg kiezen, bijvoorbeeld door vreemde, niet-monotone adresberekeningen uit te voeren. Onze decennialange erfenis van programma's die hun navigatie door een onderverdeelde adresruimte in software uitdrukken — precies zoals ze dat willen — botst met elke nieuwe, meer dwingende hardware. Het overwinnen hiervan is een kwestie van ontwikkelingsinspanning, maar die inspanning wordt pas genormaliseerd (en de kosten "succesvol" geëxternaliseerd over de industrie) als CHERI (of iets soortgelijks) definitief doorgebroken is.
liballocs en recursieve abstractie
Bij de ontwikkeling van liballocs heb ik me veel minder beziggehouden met security en ben ik daarom grotendeels vrijgebleven van het voorschrijven van regels over hoe adressen mogen worden afgeleid. In plaats daarvan heb ik me meer gericht op het beschrijvend vastleggen van welke structuur echte software ook maar heeft bedacht terwijl deze de platte adresruimte recursief onderverdeelt.
In de kern van liballocs zit een recursieve abstractie: allocaties nesten binnen andere allocaties, waardoor een boomstructuur ontstaat. Er is geen "niveau-N afkap" of harde scheiding tussen hardware en software; het is fundamenteel software die de structuur tot in de kleinste details wil vastleggen via reflectieve abstracties. Deze zijn zo uniform mogelijk, ondanks hun vele en heterogene implementaties binnen het systeem.
Dit idee van een "homogene interface, heterogene implementatie" wordt vaak geassocieerd met objectgeoriënteerd programmeren, en zelden met hardware. Hoewel liballocs zelf geen mening heeft over hoe programma's de recursief onderverdeelde structuur gebruiken, zou het zeker kunnen worden ingezet voor extra beveiligingsmechanismen. Deze zijn echter alleen beveiligd tegen kwaadwillendheid als de onderliggende hardware nuttige primitieven biedt om die mechanismen zelf te beveiligen binnen dezelfde adresruimte.
Vervelend genoeg zou x86-stijl segmentatie een bijna voldoende basis hiervoor zijn geweest, als het besturingssysteem dit daadwerkelijk beschikbaar had gesteld aan de userland. Voor wat ik ongeveer zoek, word ik constant herinnerd aan het amusement-getitelde paper "Lord of the x86 Rings".
De tegengestelde benadering van Language-VM's
Om af te sluiten met een andere objectgeoriënteerde noot: de klassieke benadering van language-VM's bij onderverdeling doet precies het tegenovergestelde van hardware. Alles wordt maximaal onderverdeeld in minuscule objecten, met een enorme, expliciete interreferentie-relatie (pointers) tussen hen.
De programmeur heeft ongetwijfeld grovermazige structuren in zijn hoofd, maar die blijven daar; het systeem biedt niet aan om de opslag rondom deze structuren te organiseren. Als gevolg hiervan offeren deze systemen de ruimtelijke lokaliteit (spatial locality) op — de heuristiek van hardware om bytes of woorden samen te groeperen in grotere eenheden. Dit verklaart de langdurige prestatie-nadelen van dergelijke benaderingen.
Groetjes,