Torben Mogensen header

Speculative execution == sårbarheder?

Der er offentliggjort nye Meltdown-lignende sårbarheder i Intel CPUer, og igen skyldes det, at speculative execution lækker information.

Lad os begynde med hvad speculative execution egentlig er. Moderne CPUer har en meget lang pipeline og vil endda ofte have flere samtidige pipelines, så mere end en instruktion kan udføres samtidig. Når et betinget hop udføres koster det derfor adskillige instruktioners forsinkelse, hvis man skal vente på, at betingelsen er afgjort, før man begynder at hente og udføre instruktioner på hoppets destination (eller lige efter hopinstruktionen, hvis hoppet ikke tages). For at undgå denne forsinkelse, forsøger CPUen at gætte sig til, om instruktionen hopper eller ej, og begynder på forhånd at hente og udføre instruktioner fra det forventede sted. Men forudsigelsen kan tage fejl, og så skal man rulle tilstanden tilbage til den tilstand, der var lige ingen hopinstruktionen. Men med en forudsigelsessikkerhed på bare lidt over 50% er det en nettogevinst.

Problemet er, at der ikke altid bliver ryddet ordentlig op, når en spekulativt udført beregning rulles tilbage: Der kan f.eks. ligge data i cachen, som ikke ellers ville være der. Og det er den slags oprydningsproblemer, der er skyld i sårbarhederne.

Men vil spekulativ udførsel altid give anledning til læk af data? I teorien ikke: Hvis der ryddes ordentligt op, er der ingen læk.

Problemet er, at det er svært at rydde ordentligt op: Hvis man har lagt data i cachen, er det ikke nok blot at invaiidere den pågældende cahcelinje, man skal huske, hvad der tidligere lå samme sted, så man kan genetablere den oprindelige tilstand. Og det koster. Der er tilsvarende problemer med andre slags instruktioner: Man skal huske på en masse data, hvis man skal rydde ordenligt op, og også dette data skal fjernes under oprydningen. Det er særligt slemt, hvis der sker en afbrydelse (et interrupt) under spekulativ udførsel. Så skal alle registre gemmes på stakken, så de kan reetableres, når man vender tilbage fra afbrydelsen. Men under spekulativ udførsel eksisterer der flere kopier af samme register -- et svarende til tilstanden før den spekulative udførsel, og et fra den nuværende spekulative tilstand. Det er med til at øge risikoen for datalæk.

En potentiel løsning er at rulle tilstanden tilbage, når der kommer en afbrydelse, så man kun skal gemme et kopi af registrene. Men det tager tid, og forsinker responsen på afbrydelsen. Og hvis tilbagerulningen ikke er perfekt, så ligger der stadig spekulativ information rundt omkring.

Et grundlæggende problem er, at de fleste instruktioner er irreversible: Der findes ikke inverse operationer til dem. For at kunne komme tilbage, skal man altså gemme (checkpointe) tidligere tilstande. Så en potentiel løsning på problemet er kun spekulativt udføre reversible instruktioner. Det betyder, at en tilbagerulning altid vil være perfekt: Man kommer tilbage til præcis den tilstand, man havde før spekulationen. Det tager stadig tid at rulle tilbage, så for at få hurtig respons på afbrydelser, kan man gemme den nuværende tilstand. Da der kun er et kopi af hvert register, er det relativt simpelt. Alternativt kan man begrænse spekulationen til det, man er villig til at rulle tilbage ved en afbrydelse.

Men som sagt er det de færreste instruktioner, der er reversible. Men der er mange nyttige instruktioner, der er 100% reversible: A+=B, A-=B, og A^=B er f.eks. reversible, hvis A og B er forskellige registre. Det er lidt mere tricky med lageroperationer, for selv om A+=(B), hvor parenteserne indikerer, at man bruger B som adresse, er reversibel, så tager dette ikke højde for cachens tilstand -- hvis man skal hente noget fra lageret ind i cachen, kan det lække information. Så man skal nok undlade spekulationen, hvis man skal lave noget med data, der ikke ligger i cachen.

En anden løsning er helt at undlade spekulativ udførsel. Men skal man så gøre ingenting, mens man venter på afgørelsen af en betingelse? Det ville betyde et betragteligt fald i performance, så er det en god ide? Måske. En af de store problemer med at køre processorer hurtigt er varmeudvikling. Og hvis varmeudviklingen er lav, mens en processor venter, så er den samlede varmeudvikling mindre. Dermed kan man pakke flere kerner ned i samme pakning, uden at den overopheder. Men det kræver som sagt, at varmeudviklingen falder, når en pipeline venter (staller), og det er ikke ligetil. Men verden er på vej væk fra single-core performance over mod multiple-core performance, hvor man accepterer, at de enkelte processorer kører lidt langsommere, hvis man bare kan få flere til at køre samtidigt.

Der vil nok blive brugt en kombination af forskellige teknikker. Men overvej, om du ikke i højere grad end nu kan programmere med reversible operationer. Potentielt kan det give et performance boost på fremtidige processorer.

Kommentarer (18)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Morten Andersen

Hej Mogens tak for fin opsummering. Men i relation til dit "I teorien ikke: Hvis der ryddes ordentligt op, er der ingen læk." tænker jeg om der ikke også er situationer tilbage, selv hvis der altid ryddes perfekt op, nemlig dem der skyldes timing-effekter. Tag f.eks. Meltdown - problemet er at de spekulativt udførte instruktioner får lov at tilgå data før CPU'en har checket om datatilgangen er tilladt. Det er således også muligt at branche på basis af værdien af en "fortrolige bit" (altså i et adresserum programmet normalt ikke har adgang til) og angriberen kan tilrettelægge det således at der i tilfældet hvor bitten er én sker "noget" der medfører et umiddelbart flush af hele pipelinen, mens der i det andet tilfælde bliver udført instruktioner som CPU'en godt kan spekulere i hvorfor spekuleringen fortsætter længere tid - typisk indtil CPU'en opdager at instruktionerne slet ikke burde have haft adgang til data. Hvis programmet (angriberens program) har adgang til en nøjagtig tidskilde vil dette vise sig som en statistisk målbar forskel i udførelsestiden, som afhænger af værdien af bitten. Dette gælder også selvom CPU'en perfekt ruller tilstanden tilbage hver gang pipelinen flushes. Problemet er at informationen her "lækker" via timing.

Nu var Meltdown også i særdeleshed slem, og er iøvrigt lukket i nyere CPU'er og med lappeværk i software. Men jeg mener ikke man helt kan afvise at også de andre lignende sårbarheder også kunne fortsætte med at eksistere, selv ved perfekt oprydning.

  • 3
  • 0
Torben Mogensen Blogger

problemet er at de spekulativt udførte instruktioner får lov at tilgå data før CPU'en har checket om datatilgangen er tilladt.

Det bør de selvfølgelig ikke kunne, men det er ikke et problem med spekulativ udførsel i almindelighed, men at spekulativ udførsel ved en fejl har tilladelser, der ikke burde have. Altså en regulær bug, som ligeså vel kunne have være i kode uden spekulation. F.eks. hvis en load-instruktion spænder over to pages, og kun den første burde være tilgængelig, men CPU'en kun checker adgang til den første.

  • 0
  • 0
Torben Mogensen Blogger

...burde vel være kortere pipeline i CPU'erne og hurtigere RAM ?

Hurtigere RAM ville være rart, men det er meget dyrt. Den hurtige RAM bruges netop i cache, hvor man ikke behøver så meget af det.

Hurtigere clockfrekvens ville også være rart, men problemet her er, at strømforbrug (og varmeproduktuion) stiger kvadratisk med frekvensen, så for at undgå overophedning har man i stedet valgt lavere frekvens men flere kerner.

De p.t. hurtigste beregnere er grafikkort (GPUer). De bruger ikke spekulativ udførsel, men har mange regneenheder, der udfører den samme kode, blot på forskellige data. Så fremtiden er måske simplere CPUer, som ikke laver beregningstunge ting, som til gengæld overlades til GPUerne.

  • 2
  • 0
Morten Andersen

Meltdown var blot et eksempel og iøvrigt var CPUerne bevidst designet sådan af hensyn til performance og før meltdown blev det ikke betragtet som en fejl men som en optimering. arm havde netop ntroduceret samme optimering i A75 og POWER har (havde) samme optimering. Med "før meltdpon" briller på var der ikke noget problem for det var jo blot spekulativ udførelse og instruktionerne blev ikke committed før Access checket var foretaget. Men det er eksempler på antagelser der ikke holder længere også timing lækage. Selvom CPU tilstanden rulles perfekt tilbage så kan de spekulative instruktioner lække information via varians i kørselstiden . Problemet ligger her i at uret/tiden ikke kan køres tilbage så hvis angriberen har adgang til en form for timer/ur så kan han overføre information fra det spekulative til det faktisk udførte. Så tror ikke det er nok bare at rulle CPU tilstanden tilbage heller ikke i forhold til de øvrige sårbarheder.

  • 2
  • 0
Baldur Norddahl

Mon man kan hjælpe CPUen ved at programmøren, sprog og oversætter markere kode der er sikker at udføre spekulativt?

Eksempel: Hvis vi har et array i et sprog der tjekker grænser inden adgang, så kan man få indlæst data i cachen ved at gå ud over grænserne, selvom dette bliver stoppet af et tjek. Det skal markeres som usikkert. Men hvis vi har en løkke, hvor grænserne er tjekket udenfor løkken, så er det sikkert. Dog kan det være nødvendigt at slutte løkken et index før tid, så sidste gennemgang ikke resultere i et ekstra prediktive array tilgang et indeks for langt.

  • 0
  • 0
Troels Henriksen

Dog kan det være nødvendigt at slutte løkken et index før tid, så sidste gennemgang ikke resultere i et ekstra prediktive array tilgang et indeks for langt.

Hvorfor kun ét indeks før tid? Moderne CPUer kan spekulativt afvikle hundredevis af instruktioner i forvejen, og det nøjagtige antal varierer fra model til model.

Jeg tror ikke sprogmekanismer kan bruges til at undgå disse informationslækager, med mindre det er samdesignet med en specialiseret maskine - og dertil vil det kun være anvendeligt til ganske bestemte opgaver. Næsten alting er potentielt usikkert når det kommer til at lække spekulativ information.

  • 2
  • 0
Torben Mogensen Blogger

Selvom CPU tilstanden rulles perfekt tilbage så kan de spekulative instruktioner lække information via varians i kørselstiden.

Det er ikke specifikt for spekulativ udførsel. Enhver beregning, hvis tid afhænger af dataværdier, lækker information om disse værdier. Det er også derfor, at krypteringsalgoritmer typisk laves, så tidsforbruget er uafhængigt af værdierne af nøgle og data. Men det er metoder, der kun bruges til meget sensitiv information. Det er urimeligt at kræve, at "almindelige" programmer er tidsinvariante, og derfor er det heller ikke rimeligt at kræve, at spekulativ udførsel ikke ændrer køretiden. Faktisk er hele pointen ved spekulativ udførsel at ændre køretiden. Så det vil stort set altid være nok at rydde op på registre, lager, cache, osv., når man udfører spekulativt -- og selvfølgelig ikke give spekulativt udførte instruktioner rettigheder, som ikke-spekulativ udførsel ikke har.

Til meget sensitive opgaver kan der dog være en pointe i at bruge processorer, der er meget simple: Uden cache, uden spekulativ udførsel, osv. Ikke kun for at sikre tidsinvarians, men fordi det kan være realistisk at verificere korrektheden af processorerne.

  • 3
  • 0
Baldur Norddahl

Hvorfor kun ét indeks før tid? Moderne CPUer kan spekulativt afvikle hundredevis af instruktioner i forvejen, og det nøjagtige antal varierer fra model til model.

Den nyeste Intel Core i7 har kun 14 stages i pipelinen. Og jeg vil tro at den højest kan lave et spekulativt hob.

Jeg tænker at man kan lave nogle udvidelser til instruktionsættet. Hvad nu hvis det er CPUen der laver boundary tjek? I stedet for:

Move register, adresse

Move register, adresse, boundary

Således at cpu kan lave spekulationer alt den vil, så længe det er sikkert at adressen ligger indenfor grænserne.

  • 0
  • 0
Baldur Norddahl

Da meltdown kun er et problem når angriberen får lov selv at skrive koden, så kan angriberen jo blot sætte grænsen til uendelig.

Hvis koden er skrevet i et sikkert sprog som Java eller javascript, eventuelt kørende i en webbrowser, så har du ikke mulighed for at aflæse hukommelse udenfor din sandkasse. Meltdown åbner for at det kan lade sig gøre alligevel. Det er ikke kun et angreb på tværs af processer.

  • 0
  • 0
Jens Madsen

Jeg har aldrig hørt om problemer før. En jump/branch indstruktion fylder ikke det almindelige antal bytes, men er udvidet så den fylder flere bytes, og derfor har plads til flere indstruktioner bagefter. Når at CISC oversættes til RISC formatet, så foldes koden ud, og de indstruktioner der kommer bagefter, placeres i jump indstruktionens felt. Det er så korrekt, at hvis en branch udføres i en anden retning, at så skal cachen slettes. Dette klares, ved at ikke have nogen decideret cache, men ved at bruge forwarding, og det er forward køen som slettes. Det svarer til en cache. Faktisk gøres det, ved at man sætter en cache på foran alle registre og anvender retiming, til at placere denne korrekt i strukturen. Det er en fuldt automatisk metode. Jeg har svært ved at forstå problemerne, da jeg mener at det er muligt at føre automatiserede beviser for, at det er gjort korrekt. Normalt ved dem der laver VHDL koden intet om pipelining, og hvor mange pipelines der er, og hvordan de er forwarded. Det er en automatisk process.

  • 0
  • 0
Morten Andersen

lige antal bytes, men er udvidet så den fylder flere bytes, og derfor har plads til flere indstruktioner bagefter. Når at CISC oversættes til RISC formatet, så foldes koden ud, og de indstruktioner der kommer bagefter, placeres i jump indstruktionens felt. Det er så korrekt, at hvis en branch udføres i en anden retning, at så skal cachen slettes. Dette klares, ved at ikke have nogen decideret cache, men ved at bruge forwarding, og det er forward køen som slettes. Det svarer til en cache. Faktisk gør

Hej Jens, er ikke sikker på om jeg forstår alt hvad du skriver, men ser lidt ud som om du forholder dig til korrektheden af pipelining, rollback o.s.v. som den normalt opfattes, altså at CPU'en har lov til at foretage spekulativ afvikling sålænge det set fra bussen (memory, I/O) af ser ud som om eksekveringen sker rent serielt (evt. lidt løsere end det, afhængigt af hvor meget den pågældende CPU's memorymodel lover). Det er imidlertid ikke det der er problemet med de har sårbarheder - CPU'erne er korrekte nok i denne klassiske forstand. Problemet består i de "side channel" attacks som der åbnes for, altså at køretiden kan bruges til at afsløre værdier programmet normalt ikke ville have adgang til. F.eks. at et program i user mode kan se hvad der foretages i kernel mode etc.

  • 0
  • 0
Morten Andersen

Hej Torben, men alle de her spekulative sårbarheder er jo side-channels så AL lækgagen sker via timing angreb. Angrebene adskiller sig alene ved hvordan forskellen i timing opnås baseret på værdier der burde have været fortrolige. Men ud fra det du skriver virker det som om du slet ikke synes denne type angreb er et problem (hvad end vi snakker Meltdown, Spectre, L1TF, RIDL etc.).

Iøvrigt, hvis du synes Meltdown er speciel pga. CPU'ens manglende check, så overvej f.eks. branch-prediction baseret Spectre. Fx et user-mode program der kalder kernen for at få oplyst en følsom værdi. Kun hvis programmet har et bestemt privilegium afsløres værdien. Kernens kode ser måske således ud:

1) Flyt privilegie-værdi til register RAX
2) Hvis RAX = 0 - hop til 4
3) [RAX = 1] - privilegie tilstede, returner fortrolig værdi
4) [RAX = 0] - privilegie ikke tilstede, returner fejl

Forestil sig et program der ikke har pågældende privilegium og kalder. Hvis den initielle hopforudsigelse går galt kan bullet 3 blive spekulativt afviklet og programmet får den fortrolige værdi i hånden. Umiddelbart synes det måske ikke at være et problem, for det hele rulles jo tilbage når CPU'en opdager at hopforudsigelsen var forkert. Men de nye angrib går ud på at user-programmet kigger på værdien og gør noget der givre en timing-mæssig synlig konsekvens afhængigt af værdien. Denne timingmæssige konsekvens kan ikke rulles tilbage.

  • 1
  • 0
Jens Madsen

Det er imidlertid ikke det der er problemet med de har sårbarheder - CPU'erne er korrekte nok i denne klassiske forstand. Problemet består i de "side channel" attacks som der åbnes for, altså at køretiden kan bruges til at afsløre værdier programmet normalt ikke ville have adgang til. F.eks. at et program i user mode kan se hvad der foretages i kernel mode etc.


Ok, det forstod jeg ikke lige. I nogle tilfælde, kan man også få informationer ud af opsamlet støj mv. og det kan være meget svært at gardere sig 100% imod. Den eneste løsning jeg kender - og som mest er egnet til microcontrollere og FPGA løsninger - er at definere den tidsmæssige grænseflade til omverdenen. Det betyder, at man i softwaren definerer timingen, f.eks. tidspunktet et indgangs signal skal samples, og tidspunktet den skal sendes ud, og det er ikke muligt at hente data, eller sende data, som ikke har et tidsstempel på. Signaler der genererer interrupts, får tidsinformationer skrevet på, så man kan skifte udgange defineret i forhold til indgangens tidspunkt. Det betyder, at det er muligt at lave eksakte tidsoplysninger om funktionen. I nogle tilfælde, så garanterer man svartid, og sætter klokregistre på, på alle indgange og udgange. Det er mere enkelt i hardwaren. Og man kan lave en kombination, hvor en del af funktionen er i SW. Selvom man derved får styr på timingen, og alt kun kan skifte på et eksakt programmeret tidspunkt, så kan stadigt være problemer ved at lytte til støjen. Den kan afsløre noget om, hvordan at softwaren kører internt.

  • 0
  • 0
Torben Mogensen Blogger

Men de nye angrib går ud på at user-programmet kigger på værdien og gør noget der givre en timing-mæssig synlig konsekvens afhængigt af værdien. Denne timingmæssige konsekvens kan ikke rulles tilbage.

Jeg vil stadig mene, at det er acceptablet, sålænge programmører af sensitiv kode er klar over det. Et alternativ til den viste kode er:

1) Flyt -(privilegieværdi) til register RAX
2) Beregn RAX = RAX & (fortrolig værdi)
3) Returner register RAX

Her er ikke noget spekulativt udført kode, og køretiden er uafhængig af privilegieværdien, og dermed er der ikke nogen læk. Det er sådanne teknikker, der bruges i krypteringsalgoritmer for at undgå timing-baserede side-channelangreb.

Grundlæggende bør sensitiv kode undgå timingvariante og spekulative beregninger, og det kan gøres med teknikker som denne. Ikke desto mindre vil det være en klar fordel, hvis processoren tilbyder et ikke-spekulativt betinget hop, der venter med at udføre hoppet til betingelsen er kendt. Alternativt en barriereinstruktion, der tømmer pipelinen før den næste instruktion påbegyndes.

  • 0
  • 0
Log ind eller Opret konto for at kommentere