Spekulativ udførelse: Sådan virker Meltdown-sårbarheden

Gode intentioner om at udføre programmer hurtigere ved at gemme værdier lokalt, omordne instruktioner og gætte på udfald af forgreninger ligger bag nuværende og fremtidige sikkerhedsproblemer i CPU'er.

Afsløringen af sidste uges sårbarheder, som findes i de fleste moderne CPU’er, var en brat opvågning for en branche, der er vant til, at problemer findes i programkode, som kan ændres efter forgodtbefindende.

Forrige onsdags afsløring handlede imidlertid ikke om kode, men om instruktioner og teknikker i processorerne, der udgør hjertet i vore dages computer-arkitektur.

Teknikken benytter et 'side channel-angreb', hvor der ikke er tale om deciderede fejl i hardwaren. I stedet benyttes andre typer af information, som i forbindelse med Meltdown og Spectre handler om den tid, det tager at læse fra hukommelsen, i modsætning til chippens eget cache-lager. Meltdown relaterer sig primært til moderne Intel-CPU'er, mens Spectre vedrører ARM, AMD og Intel.

De to centrale faciliteter, som sårbarhederne udnytter, er caching og spekulativ udførelse af instrukser. Cache, også kendt som L1, L2 og L3-cache, er i denne forbindelse et lager, som sidder på selve CPU-chippen. Cachen kan tilgås omkring 100 gange hurtigere end selve hukommelsen i RAM, så det giver god mening at kopiere den hukommelse, som CPU’en er i gang med at behandle.

Den anden facilitet er spekulativ udførsel. Det går kort sagt ud på at benytte noget af den tid, hvor CPU’en ellers er i tomgang, til at udføre instruktioner, der måske skal bruges til noget - på den anden side af en ‘if’-sætning. Moderne CPU-kerner kan udføre mere end én instruktion af gangen, men det er kun muligt at fylde rørledningen op, hvis instruktionerne er uafhængige.

I det følgende kigger vi nærmere på en forsimplet og principiel gennemgang af problematikken i forhold til Meltdown, som den er beskrevet af arkitekten bag Rasberry Pi-computeren, Eben Upton, i et blogindlæg.

I eksemplet benytter vi følgende simple program, som processoren skal udføre:

t = a+b
u = c+d
v = e+f
w = v+g 
x = h+i
y = j+k

Her er det værd at bemærke, at den fjerde instruktion (w) afhænger af et tidligere resultat.

I såkaldt ‘skalare processorer’ kan der kun laves én beregning af gangen, så udførslen ser ud som ovenstående. Det gælder eksempelvis den første Rasberry Pi samt Intel 486-processorer fra 1990’erne.

Skridtet op fra skalare CPU’er er ‘multiskalare’ processorer. De kan udføre mere end en enkelt instruktion af gangen. Så vores program fra før kan se sådan ud, med tanke på, hvordan CPU’en udfører programstumpen:

t, u = a+b, c+d
v, w = e+f, v+g
x, y = h+i, j+k

Men den går ikke: I andet skridt afhænger w af v, så derfor skal udregningen af v ske først. Så ser det sådan ud, fra CPU’ens synspunkt:
t, u = a+b, c+d
v    = e+f                   
w, x = v+g, h+i
y    = j+k

Nu er der i og for sig plads til en ekstra instruktion i andet og fjerde trin.

Det er her, egenskaben ‘out-of-order’ kommer ind i billedet. De fleste moderne CPU’er er i stand til at omordne instrukser, der ikke er indbyrdes afhængige, så pipelinen bliver fyldt ud.

Hvis vi bytter rundt på w- og x-beregningen, kan vores program se sådan ud:

t = a+b
u = c+d
v = e+f
x = h+i
w = v+g
y = j+k

Nu kan instruktionerne klares på denne måde:
t, u = a+b, c+d
v, x = e+f, h+i
w, y = v+g, j+k

Forudse forgreningen

Det næste trick for at få programmet til at køre hurtigere går ud på at gætte, hvad der sker i fremtiden. Hvis programmet, som vi har ændret lidt i forhold til før, indeholder en if-sætning, kan det se sådan ud:

t = a+b
u = t+c
v = u+d
if v:
   w = e+f
   x = w+g
   y = x+h

(hvor værdierne 0 og ikke-0, ligsom i C, kan stå for falsk og sand i if-sætningen.)

Her afhænger v af u, og u af t, så det er umiddelbart ikke muligt at fylde pipelinen ud. Men hvis CPU’en har en god ide om at forgreningen bliver udført - at v er ‘sand’ - så kan det give mening at prøve at udregne de tre instruktioner i ovenstående if-gren på forhånd:

t = a+b
u = t+c
v = u+d
w_ = e+f
x_ = w_+g
y_ = x_+h
if v:
   w, x, y = w_, x_, y_

— som med pipelines kan udregnes således:

t, w_  = a+b, e+f
u, x_  = t+c, w_+g
v, y_  = u+d, x_+h
if v:
   w, x, y = w_, x_, y_

Det smarte er, at hvis if-delen gennemløbes, er de tre værdier allerede udregnet. CPU’en bruger statistik til at gætte på værdien af v. Hvis en løkke hopper tilbage til det samme punkt igen og igen, kan det give god mening at forudberegne værdierne, hvis alternativet ellers er, at CPU’ens ene pipeline står med hænderne tomme.

I det tænkte eksempel her barberes seks instruktioner ned til tre. Hvis en løkke hopper tilbage til start en million gange, har vi sparet en væsentlig del processorcyklusser med det trick.

Cache

En moderne processor bruger måske i omegnen af et halvt nanosekund for at foretage en udregning, men som tidligere nævnt tager det op til 100 nanosekunder at hente en byte i hukommelsen. Derfor kopieres værdier fra lagret ind i cachen, hvor læsetiden er omkring ét nanosekund.

Taktikken er, at hvis programmet læser fra en adresse i hukommelsen , læser den nok også byten ved siden af. Så kan det se sådan ud, hvis vi læser fra adresse 0:

a = mem[0]    # 100 nanosekunders forsinkelse. 
              # mem[0:15] kopieres til cache.
b = mem[1]    # mem[1] ligger i cachen - læses på 1 nanosekund.

Nu gælder det om at holde ørene stive, for det er denne forskel i læsetider, der i sidste ende afslører en værdi i styresystemets ‘hemmelige’ del af hukommelsen, det såkaldte kernelspace, kernens hukommelse.

Vi strikker nu en Meltdown-agtig sårbarhed på denne måde:

t = a+b
u = t+c
v = u+d
if v:
   w = kern_mem[address]   # hvis vi når hertil, opstår der en fejl
   x = w&0x100
   y = user_mem[x]

Her står kern_mem for kernens hukommelse og user_mem for programmets hukommelse. Programmet her fungerer ikke. Når vi når til udregningen af w, afbrydes programmet, da det uretmæssigt forsøger at få adgang til den privilegerede hukommelse.

Men den stopklods snyder vi os uden om på følgende vis.

Vi manipulerer processoren til at tro, at v nok er sand ved næste gennemløb, så den kan udregne de tre instruktioner i if-delen på forhånd, på samme måde som før:

t, w_ = a+b, kern_mem[address]
u, x_ = t+c, w_&0x100
v, y_ = u+d, user_mem[x_]
if v:
   # fejl
   w, x, y = w_, x_, y_      # vi kommer aldrig hertil

Når programmet når til if-delen, opstår fejlen igen, og udregningen af w, som tilgår kernens adresserum, finder aldrig sted. Men det er heller ikke nødvendigt for vores formål.

Hvis CPU’en gætter på at v er sand, bliver følgende udført:

  • w_ tildeles kern_mem[address]

  • x_ tildeles w_&0x100, som tager første bit fra kern_mem[address] og er enten binært 00000000 eller 1000000 (hexadecimalt 0x100 eller 0x000).

  • y_ tildeles user_mem[x_], en byte i programmets hukommelse på adressen x_.

Da CPU’en tror, at if-delen skal udføres, indlæser den user_mem[x_] og nabo-bytes til cachen.

Når CPU’en når forbi v, ‘erkendes’ den uretmæssige tilgang til kernehukommelsen, så w aldrig beregnes.

Men derefter kan programmet uhindret hente værdien fra user_mem[x_] eller naboer: Hvis det går hurtigt, omkring 1 nanosekund, må værdien være i cachen. Hvis det tager omkring 100 nanosekunder, er værdien ikke i cachen. Hvis det eksempelvis tager omkring et nanosekund at læse adressen user_mem[00000000], må den første bit på kernelspace-adressen være 0.

På den måde kunne vi læse en enkelt bit fra adressen i det privilegerede rum, og så er det bare at gå videre med de resterende bits.

Den rigtige Meltdown-kode er mere kompleks end den principielle gennemgang her, skriver Eben Upton på sin blog. En af forskellene er måden, som Meltdown snyder CPU’en til at tro, at if-delen skal udføres. Spectre-sårbarheden fungerer på en tilsvarende facon, men prøver at snyde afgrænsninger i arrays.

Meltdown-sårbarheden har eksisteret i Intel-CPU’er de sidste tyve år. Ifølge flere sikkerhedsforskere er det forventeligt, at flere side channel-huller vil dukke op fremover.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Følg forløbet
Kommentarer (2)
Log ind eller Opret konto for at kommentere
Pressemeddelelser

Welcome to the Cloud Integration Enablement Day (Bring your own laptop)

On this track, we will give you the chance to become a "Cloud First" data integration specialist.
15. nov 2017

Silicom i Søborg har fået stærk vind i sejlene…

Silicom Denmark arbejder med cutting-edge teknologier og er helt fremme hvad angår FPGA teknologien, som har eksisteret i over 20 år.
22. sep 2017

Conference: How AI and Machine Learning can accelerate your business growth

Can Artificial Intelligence (AI) and Machine Learning bring actual value to your business? Will it supercharge growth? How do other businesses leverage AI and Machine Learning?
13. sep 2017
Jobfinder Logo
Job fra Jobfinder