Execução fora de Ordem e Spectre
===
###### tags: `Segurança` `Arquitetura de Computadores` `Pwning` `Engenharia reversa`
Nesse artigo vamos abordar os principais tópicos referentes a microprocessadores modernos como pipelines de instrução, execução fora de ordem especulação
# Como CPUs funcionam
As CPUs contém um grupo de comandos bem definidos que permitem realizar operações lógicas e aritimeticas, ler e escrever na memória, fazer comparações, e controlar o fluxo de execução do próprio programa. O programador tem acesso a parte dessa interface da CPU através de instruções de máquina, que permitem ao programador solicitar diretamente a CPU para que esses comandos sejam realizados. Uma exemplo de sequência de instruções é:
```
1.mov ax,8
2.mov bx,10
3.add ax,bx
```
Registradores são as unidades de armazenamento mais rápidas em termos de tempo de acesso pois estão presentes dentro da CPU e estão fisicamente próximas das unidades de execução, que serão responsáveis por realizar as operações matemáticas na Unidade Lógico aritimética.
No exemplo acima foram utilizados dois registradores, o ax e o bx para realizar uma soma. Para o programador é importante que essas instruções sejam executadas na ordem correta, pois caso as instruções 2 e 3 troquem de posição isso poderia resultar em um comportamento inesperado do programa.
Todavia o ciclo completo de execução de uma única instrução possui várias etapas demoradas. Entre elas pode-se citar:
- A leitura da própria instrução
- A decodificação da instrução pela CPU, realizando o chaveamento e a decisão de qual caminho o dado manipulado deve tomar
- A resolução dos acessos a memória, se houverem
- A execução da operação aritimética ou lógica, se houver
- A escrita do resultado na memória, se houver
# Hierarquia de memória
Para compreender por que certas operações demoram mais que as outras é preciso abordar o conceito de hierarquia de memória.
Devido a questões de tecnologia empregada, proximidade física e densidade de armazenamento, os computadores utilizam uma combinação de dispositivos de armazenamento. Em geral componentes mais rápidos como registradores e caches localizam-se próximos a CPU pois são constantemente utilizados. Esses componentes priorizam velocidade acima de densidade de bits ou custo e pelo fato de estarem próximos ao local de uso estão restritos a uma quantidade pequena. No outro extremo estão componentes lentos, mas com alta capacidade como SSDs e HDDs, que acabam priorizando armazenamento total e custo ao invés de velocidade.
| Tecnologia empregada | Tempo tipico de acesso | $ por GB em 2012 |
| -------- | -------- | -------- |
| SRAM | 0.5-2.5 ns | $500-$1000 |
| DRAM | 50-70 ns | $10-$20 |
| FLASH | 5000 50000ns | $0.75-$1.00 |
| Disco Magnético | 5000000 - 20000000 ns | $0.05-$0.10 |
*Adaptado de Computer Organization and Design RISC-V Edition: The Hardware Software Interface*
## Localidade Temporal e espacial
A hierarquia de memória se baseia no princípio de que o acesso aos dados não é puramente aleatório.Devido a estrutura das operações mais comuns em programas como loops, acessos sequenciais a listas, e até mesmo o acesso das próprias instruções que tendem a seguir um fluxo sequencial, tem-se os conceitos de localidade temporal e espacial.
A localidade temporal é quando um dado recentemente acessado tem alta probabilidade de ser acessado novamente, como em indices de *loops* e contadores.
A localidade espacial diz respeito ao acesso de posições de memória próximas, quando o elemento 2 de uma lista é acessado, provavelmente o elemento 3 também será.
Quando esses dados são trazidos para níveis superiores da hierarquia de memória, a próxima vez que esses itens precisarem ser acessados, os níveis inferiores não precisarão ser consultados, permitindo um acesso mais rápido ao dado.
## Hit rate, Miss rate
Sabendo as taxas de acerto dos componentes da hierarquia pode-se calcular o tempo de acesso médio a memória e observar o impacto que determinados componentes possuem. Tomando com exemplo (não muito realista) a seguinte estrutura:
| Componente |Tempo de acesso | Taxa de Acerto |
| --------| -------- | ----- |
| Cache | 2 ns| 90% |
| DRAM | 70ns|90%|
| FLASH |5000ns |100%|
* Em 90% dos acessos o dado estará na cache e tempo de resposta será 2ns
* Em 90% das 10% (9%) das ocorrencias em que o dado não estava na cache, ele estará na DRAM e o tempo de resposta será 2ns (busca na cache) + 70ns (busca na DRAM)
* Nos 1% de acessos que não foram satisfeitos pelos componentes superiores o tempo de acesso será 5000ns +70ns+2ns
Portanto o tempo médio de acesso será
``` 0.9 * 2ns + 0.09 * 72ns + 0.01 * 572ns = 14ns```
Ao remover a cache o tempo médio subiria para
``` 0.99 * 70ns + 0.01 * 570ns = 75ns```
# Pipeline
Conforme visto no programa abaixo, diversas etapas são necessarias para a execução completa de uma instrução. Todavia durante esse processo o dado é utilizado apenas em um componente por vez, deixando os demais elementos da CPU osciosos, por exemplo durante o cálculo de uma soma na ULA não existem leituras de instruções feitas pela memória por exemplo. Uma forma de melhorar o *Throughtput* de instruções seria permitir que os componentes ociosos trabalhem em forma de uma cadeia de produção, assim como ocorrem em uma linha de montagem, permitindo então reduzir o período de clock total pois cada etapa do processo pode ser feita em menos tempo.
|Operação| 1 | 2 | 3 | 4 |5 | 6 | 7|
|--------|---|---|---|---|---|---|--|
|Leitura de instrução| A| B | C |
|Decodificacao| | A| B | C
|Execução| | | A| B | C
|Memória| ||| A| B | C
|Escrita| |||| A| B | C
*Diagrama da execução das instruções A B e C ao longo dos ciclos 1-7 no estágio 3 por exemplo as unidades de Leitura, decodificação e execução estão ativas simultaneamente*
Todavia ao contrário de uma linha de produção em uma fábrica, instruções não são completamente independentes umas das outras. Considere a seguinte sequência:
```
A. add ax,[bx]
B. jz $+1
C. nop
```
Neste caso, a finalização da instrução A ocorrera no melhor dos casos, apenas no ciclo 5, podendo levar ainda mais tempo dependendo de qual posição na hierarquia de memória o dado apontado por *bx* está. Todavia o pipeline necessita escolher se faz a leitura da instrução C ou a próxima ($+1) logo no ciclo 3. Quando isso ocorre, a CPU pode decidir esperar o resultado da operação o que acarretaria em perda de performance ou realizar uma *predição* sobre o pulo.
# Predição
O exemplo acima trata de um desvio condicional. Ou seja, existem apenas dois caminhos possíveis que a CPU pode executar, tomar ou não tomar o pulo. Para auxiliar a decisão existem componentes internos na CPU chamados preditores de desvio, que coletam informações sobre os pulos recentes tomados para auxiliar na decisão. O exemplo mais simples é do contador de saturação ilustrado abaixo. Quando o desvio é tomado diversas vezes o preditor se adapta e passa a aceitar os próximos pulos tomados.
*Preditor condicional de 2 bits. Extraido de https://en.wikipedia.org/wiki/Branch_predictor*
```
if (*canRun){
f1();
}
else{
f2();
}
```
*Exemplo de código que pode gerar comportamento especulativo caso a variável apontada por canRun não esteja na cache por exemplo*
Quando é necessário predizer o próximo endereço, é realizado uma **execução especulativa** ou seja, o processador não tem certeza se o caminho de execução esta correto, então todos os resultados feitos a partir da predição são armazenados em **registradores de rascunho**. Quando a condicional que gerou a execução especulativa for resolvida (canRun foi lida da memória por exemplo), caso o caminho tomado esteja correto os resultados são gravados nos registradores verdadeiros, levando a um ganho de desempenho. Se o caminho tomado estiver incorreto os resultados presentes nos registradores de rascunho são descartados e é necessário executar o caminho correto dessa vez, levando a um desempenho semelhante como se o processador tivesse esperado a avaliação ter sido concluida.
# Processador superescalar e execução fora de ordem
As CPUs modernas possuem mais do que uma única unidade de execução por núcleo, permitindo em algumas situações realizar mais do que uma instrução por ciclo de clock. Para que o uso de mais de um unidade de execução simultânea seja funcional ele deve ser capaz de alocar as instruções sem que haja uma alteração no resultado da operação a ser computada visando paralelizar as operações a serem realizadas. As instruções podem ser re-ordenadas e executadas fora de ordem desde que a dependência entre elas seja obedecida.
Para que as instruções possam ser reordenadas elas devem respeitar os três riscos ao pipeline
#### Read After Write
```
mov rax,2
mov rbx,rax
Não podem ser trocadas de ordem pois o resultado da segunda instrução seria alterado
```
#### Write After Read
```
mov rbx,rax
mov rax,2
Não podem ser trocadas de ordem pois o resultado da primeira instrução seria alterado
```
#### Write After Write
```
mov rbx,rax
mov rax,rbx
Não podem ser trocadas de ordem pois o resultado de ambas instrução seriam alterados
```
Desde que respeitadas essas dependências a CPU pode reordenar instruções para executar várias operações em paralelo. Abaixo esta representada a unidade de execução de uma CPU moderna.
*Unidades de execução presentes em CPUs modernas intel. Extraido de https://mdsattacks.com/. A unidade de execução está presente em cada núcleo da CPU*
Uma forma simples de demonstrar o paralelismo a nivel de instrução é com o código abaixo.
No primeiro bloco existem 200 instruções `inc esi` . Devido a dependência Write after Write elas não poderão ser trocadas de ordem ou executadas em paralelo.
No segundo bloco existem 100 instruções `inc esi` e 100 instruções `inc edi`.Embora haja dependência entre o valor atual do registrador `esi` e o anterior o par de instruções pode ser executado em paralelo, pois não há dependência entre eles.
Dessa forma, é esperado um desempenho próximo de 200 ciclos para o primeiro bloco e próximo de 100 ciclos para o segundo bloco. Foram utilizadas as instruções `rdtsc` para realizar a medição do "tempo" de execução e `lfence` para serializar a instrução `rdtsc`, garantindo que ela não será reordenada.
O resultado do programa (executado em um i5-7500) mostra 264 ciclos para o primeiro bloco e 146 para o segundo. Considerando o overhead esperado pela execução do `rdstd; lfence` os resultados indicam um *throughput mínimo* de 0.75 instruções por ciclo para o primeiro bloco e 1.36 para o segundo bloco, evidenciando o comportamento superescalar da CPU.
```c
//gcc -masm=intel -o ilp ilp.c
#include <stdio.h>
int main(){
int time1;
int time2;
asm __volatile__(
"lfence ;"
"rdtsc ;"
"lfence ;"
"mov ecx,eax ;"
".rept 200 ;"
"inc esi ;"
".endr ;"
"lfence ;"
"rdtsc ;"
"sub eax,ecx ;"
"mov %0,eax ;"
:"=r"(time1)
);
asm __volatile__(
"lfence ;"
"rdtsc ;"
"lfence ;"
"mov ecx,eax ;"
".rept 100 ;"
"inc edi ;"
"inc esi ;"
".endr ;"
"lfence ;"
"rdtsc ;"
"sub eax,ecx ;"
"mov %0,eax ;"
:"=r"(time2)
);
printf("Ciclos gastos no bloco 1: %i\n",time1);
printf("Ciclos gastos na bloco 2: %i\n",time2);
}
$ ./ilp
Ciclos gastos no bloco 1: 264
Ciclos gastos na bloco 2: 146
```
# Operação da Cache
A Cache de um processador funciona como uma pequena e rápida memória dentro do chip da CPU que salva o conteúdo dos últimos e próximos endereços a serem acessados. Quando uma CPU solicita um byte para a memória devido ao barramento ser de 64 bits e as memórias serem otimizadas para operação em modo *burst* bem mais dados do que o que foi solicitados chegam a CPU, assim a cache guarda os dados recebidos para quando eles forem solicitados novamente não seja necessário requisitar a memória novamente e a resposta seja muito mais rápida.
A cache armazena os dados em forma de linhas, onde cada linha contém múltiplos bytes (64 bytes atualmente).
Quando o endereço solicitado chega a cache, ele é dividido da seguinte forma:
| Tag | Set| Offset|
| ----|---|----|
Offset é a posição do byte na linha da cache, Set é o endereço da linha na Cache e a Tag é o restante. A tag é guardada para poder diferenciar endereços com mesmo set e offset. Em uma CPU com 256 linhas e 64 bytes cada linha o tamanho de cada parte seria:
|||
|---|---|
|Offset | bits 0-5|
|Set | bits 6-13|
|Tag | bits 14 -63|
# Observando o estado da micro arquitetura - Cache Side Channels Attacks
Um ataque de side channel é um ataque que ao invés de buscar uma falha no algoritmo, exfiltra ou obtem informação sensível de um sistema baseado em algum efeito colateral durante a sua execução.
Alguns exemplos de side channel
* Frequencia de rádio
* Air-Fi permite um atacante exfiltrar dados de um computador comprometido mas sem acesso a internet, utilizando o barramento de memória como placa de rede sem fio.
* TempestSDR permite um atacante recuperar a imagem transmitida para um monitor através das ondas eletromagnéticas transmitidas pelo cabo HDMI.
* Consumo de energia
* Ataques de análise de consumo de energia podem ser capazes de identificar quais etapas do algoritmo de encriptação estão sendo executadas e assim extrair a chave utilizada. (rhme2 ctf)
* Tempo
* Checagens de senhas com tempo variável podem permitir descobrir quantos caracteres em uma senha estão corretos e assim realizar um ataque de força bruta com muito mais facilidade
* Cache
* Permite observar efeitos colaterais da execução de outros programas, bem como observar os efeitos de operações internas de CPU que deveriam ser invisíveis ao programador, como execução especulativa por exemplo.
Para compreender melhor os ataques a seguir vamos escolher um tipo de side channel de cache que será utilizado como método de exfiltração dos segredos obtidos pelos ataques a seguir.
## FLush + Reload
### Copy on write e paginação
Os sistemas operacionais isolam a memória de processos através de paginação. Toda vez que um programa acessa a memória o endereço presente no programa é traduzido de endereço lógico para físico através da consulta da tabela de páginação no sistema operacional (para aumentar o desempenho essa tabela é cacheada através do Translation lookaside buffer, que evita com que a memória seja consultada toda vez que um endereço seja acessado). É através desse mecanismo que é possível que programas que utilizem o mesmo endereço lógico não gerem colisões na memória e assim possam coexistir em um processador multitarefa de forma isolada.
Porém, nem sempre é desejavel que os processos isolem completamente sua memória. Seções de memória comuns a diversos processos como bibliotecas podem ser compartilhadas através do mecanismo de *Copy on Write*. Nele, quando uma página é carregada através da syscall de *mmap* com um arquivo como parâmetro se aquele arquivo já estiver mapeado em memória não é criada uma nova página. Caso o processo deseje alterá-lo, uma cópia privada da página é criada e passa a ser exclusiva para aquele processo, por isso o nome *Copy on Write*. Embora não haja nenhum problema de segurança inerente desse mecanismo pois para que haja compartilhamento as seções devem ser idênticas, o mero compartilhamento da memória física pode gerar interferencias entre processos, como será visto ao analisar o tempo de resposta da memória para essas regiões.
*Diagrama de dois processos compartilhando a região de bibliotecas. Quando o endereço lógico referente a biblioteca é traduzido, ele aponta para uma única região da memória RAM*
### Exemplo de programa vulneravel a side channel
```c
void main(){
//emojiList é compartilhada por COW pois está em uma biblioteca
char *flag="segredo";
char t;
while (1){
for (int i=0;flag[i]!='\0';i++){
t = emojiList[flag[i] * 160];
}
}
}
```
No exemplo acima, o conteúdo da variável flag, a principio não conhecida pelo atacante é utilizado como índice para acessar o array `emojiList`. Quando um acesso ocorre, o emoji passa estar presente na cache, de tal forma que o próximo acesso vai ter um tempo de resposta inferior. Sabendo disso um atacante poderia constantemente medir o tempo de resposta de cada valor possivel do `emojiList` e quando detectar um tempo de resposta rápido, inferir qual caracter foi utilizado como índice.
Para essa manipulação de cache, são utilizados duas instruções
* RDTSC - Read Time Stamp Counter, que lê um registrador que conta quantos ciclos se passaram desde o boot da máquina. É utilizada como um relógio muito preciso para a medição de tempo
* CLFLUSH - Permite invalidar uma linha da cache dado um endereço. É utilizada para impedir que a própria medição do tempo de acesso leve a um falso positivo na proxima medição
Um exemplo de medição seria
```c
unsigned long probe_timing(char *adrs) {
volatile unsigned long time;
asm volatile(
" mfence \n"
" lfence \n"
" rdtsc \n"
" lfence \n"
" movl %%eax, %%esi \n"
" movl (%1), %%eax \n"
" lfence \n"
" rdtsc \n"
" subl %%esi, %%eax \n"
" clflush 0(%1) \n"
: "=a" (time)
: "c" (adrs)
: "%esi", "%edx"
);
return time;
}
```
Para que um sistema seja vulnerável a esse tipo de ataque é necessário que haja uma clara distinção entre o tempo de resposta de um dado presente apenas na memória e um dado em cache. Para isso é possivel testar:
```c
char globalVar[4096]={1,4,7,8,5,9,1};
int main(){
unsigned long t1,t2;
unsigned long count=0;
double total_access,total_evict;
total_access=0;
total_evict=0;
for(unsigned i=0;i<100;i++){
if (i%2==0){
maccess((void *)&globalVar[44]);
}
t1=probe_timing((void *)&globalVar[44]);
count++;
if (i%2==0){
printf("time w acess: %lu\n",t1);
total_access+=(double)t1;
}
else{
printf("time no acess: %lu\n",t1);
total_evict+=(double)t1;
}
}
printf("avg cached=%lf\n",total_access/50);
printf("avg evicted=%lf\n",total_evict/50);
return 0;
...
time w acess: 68
time no acess: 304
time w acess: 66
time no acess: 308
avg cached=68.400000
avg evicted=347.200000
# head /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 158
model name : Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz
stepping : 9
cpu MHz : 3408.006
cache size : 6144 KB
```
Botando o tempo de resposta de cada acesso no gráfico, pode-se perceber a diferença do tempo de acesso entre dados presentes na cache e na memória principal e se estabelecer um limite para decidir se o dado esta na cache.
*Diferença do tempo de resposta da memória para dados em cache*
O ataque originalmente foi criado para vazar chaves criptográficas entre usuários usando a biblioteca GnuPG. Posterioremente o exploit foi adotado em outros ataques de micro arquitetura como canal para vazar segredos obtidos de forma especulativa.
# Spectre
O spectre se baseia no envenenamento de preditores para realizar a execução de código que não deveria ser executado. Dessa forma um atacante consegue enganar a CPU a burlar checagens de limite ou até obter execução de código (espculativo) no processo da vitima. Isso traz implicações sérias de segurança para o isolamento entre processos e sandboxes como navegadores. As variantes mais comuns do spectre são as duas primeiras.
### Variant 1 - Exploiting Conditional Branch Missprediction
```
if (x < array1_size)
y = array2[array1[x] * 4096];
```
O código acima mostra um exemplo de programa vulnerável ao spectre em que o atacante possui controle da variável x.Na primeira linha existe uma checagem do limite do valor x para impedir que o conteúdo do array1 seja acessado fora desse limite o que poderia gerar uma exceção ou um acesso a um dado sensível no espaço de endereço do processo da vítima. A segunda linha consistem em um alvo para um side channel attack. O conteúdo do array1 é utilizado como indice para o array2. É possível mensurar quais elementos do array2 estão em cache através de ataques como flush+reload caso array2 seja compartilhado via *COW* ou através de outros side channels mais complexos como prime+probe que não necessitam de memória compartilhada.
Utilizando apenas o side channel é possível obter o conteúdo do array1, porém o exploit do spectre amplia o escopo do ataque permitindo vazar endereços fora do limite do array.
#### Manipulação de preditor
A primeira linha realiza uma checagem que está passível a ser especulada. Caso o valor de `array1_size` demore para ser lido, o processador criará um ponto de especulação e tera de decidir se o desvio será tomado. Um atacante com o controle do x pode manipular o preditor para treinar a CPU a sempre executar o bloco dentro da condicional. Supondo um valor de `array1_size=10` por exemplo uma sequencia de entradas como: `0,0,0,0,0,0,0,0,20` faria o preditor saturar na posição de *desvio não tomado* fazendo com que ao tratar a entrada x=20 `y = array2[array1[20] * 4096];` seja executado de forma especulativa e o segredo presente na posição 20 seja vazado, o que pode ser outra variável.
Exploits dessa categoria são perigosos para navegadores pois podem ser implementados de forma semelhante em javascript. Um código em javascript que seja capaz de ler a memória do próprio processo pode extrarir cookies e dados sensíveis de outros domínios.
*Antes da checagem de limite ser realizada, o preditor de desvio continua a execução no caminho mais provável, levando a uma melhora do desempenho quando correto. Todavia se a checagem do limite for indevidamente predita como verdadeira pode levar um atacante a vazar informação em algumas sitauções. Extraido de: Spectre Attacks: Exploiting Speculative Execution*
É importante notar também que cada núcleo da CPU possui o próprio preditor de desvio, portanto para que esse ataque seja bem sucedido quando executado em processos diferentes eles sejam escalonados para executarem no mesmo núcleo, seja através do escalonador do sistema operacional ou através de mecanismos *Simultaneous MultiThreading (SMT)*.
### V2 Poisoning Indirect Branches
Conforme já foi abordado, preditores condicionais tem apenas duas opções para escolher sobre o pulo, tomar ou não tomar. Porém existem instruções que permitem pulos para endereços armazenados em variáveis por exemplo que possuem um comportamento um pouco mais complicado de predizer.
```
call rbx ;branch direto
jump rcx ;branch direto
call [rax] ;branch indireto
São todas instruções que necessitam do preditor indireto.
```
Esses tipos de instruções são geradas quando o programa precisa dinamicamente descobrir o que executar. funções que recebem ponteiros para outras funções ou até mesmo *Virtual tables* podem gerar esse comportamento. Para realizar essa predição a CPU possui um *Branch Target Buffer(BTB)* que armazena os endereços de origem e destino dos desvios indiretos mais recentes.
*Diagrama do preditor de desvio Incondicional - Extraído de Exploiting Speculative Execution*
Para efetuar o ataque o programa do atacante deve treinar o *BTB* para que quando a vitima execute o desvio indireto o atacante tenha controle do endereço de destino. A técnica utilizada é muito semelhante a *Return Oriented Programing (ROP)* pois constroi o código de ataque utilizando pedaços do código da vítima, porém não há nenhuma corrupção de memória envolvida.O único meio de obter informação é através do estado da cache.
*Layout de um ataque de Spectre V2*
Para performar o ataque o atacante deve alinhar em seu processo o endereço do pulo ou chamada e treinar o preditor para outro endereço. Como entrada para o preditor são utilizados os endereços lógicos do programa, portanto além de ser necessário identificar a existencia de um *spectre gadget* é necessário também saber o seu endereço.
# bibliografia
flush + reload https://eprint.iacr.org/2013/448.pdf
spectre https://spectreattack.com/spectre.pdf
mds attacks https://mdsattacks.com/
meltdown https://meltdownattack.com/meltdown.pdf
RSA power analys https://www.youtube.com/watch?v=bFfyROX7V0s
Linux memory management https://jasoncc.github.io/kernel/jasonc-mm-x86.html
Algumas provas de conceito https://github.com/Jos3Luiz/hackeando-cpus
Computer Organization and Design RISC-V edition
Sign in with Wallet
Connect another wallet