Execução especulativa e Spectre

Olá. Você vai notar que este é o meu primeiro post. Como não havia nada planejado durante a criação deste blog, decidi trazer um tema que havia escrito em um caderno um tempo atrás. Espero que aproveitem a leitura!

Branch prediction

Toda forma de código que cria desvios no fluxo de execução principal está intimamente ligada a um aspecto de hardware presente nas CPUs modernas—o branch predictor. Dito componente é responsável—como o nome sugere—pela predição desses desvios. A forma como isso é alcançado geralmente é baseada na análise dos padrões de resultados anteriores, através de estruturas internas como a branch predictor table (BPT), que guarda os desfechos passados (tomado/não tomado). Essencialmente, há dois tipos de branching: branch condicional e branch indireto.

Branch condicional

O branch condicional se refere principalmente a estruturas como if/elseif/else, que, no baixo nível, geram instruções conjuntas de cmp e jp. Geralmente, são mais fáceis de serem preditas pela CPU, pois possuem ambos destinos fixos no código (ou a execução continua sequencialmente, ou pula para o endereço especificado).

cmp eax, 5
je case_5

No código acima, a CPU sabe os possíveis caminhos. Com base no BPT, só precisa decidir se deve seguir com a execução ou se deve carregar as instruções presentes na seção de código case_5.

Vale observar que as branches condicionais acabam gerando uma quantidade de instruções relativa à quantidade de comparações existentes. Por exemplo: se seu código possui cinco estruturas if seguidas, o resultado final em assembly será sempre esse conjunto de duas instruções (compare e jump), gerando um código que roda em tempo O(n) e cria muitos pontos possíveis de desvio, pressionando mais o branch predictor. Em casos assim, geralmente é aplicado outro tipo de abordagem.

Branch indireto

O branch indireto, por sua vez, não possui os possíveis destinos claros no código. Ou seja, o destino não está codificado na instrução, como no caso do branch condicional. Nesse cenário, a CPU precisa prever qual endereço específico será o destino, uma tarefa, assim como aparenta, bem mais complicada.

jmp [table + rax*8]

Veja que no código acima, apesar de não haver branching condicional, é preciso que o endereço final que o código seguirá seja resolvido em runtime. Geralmente, em casos assim, há múltiplos endereços possíveis, dificultando o trabalho do predictor. Porém, em contraste com os condicionais, há apenas um único ponto de desvio, que roda em tempo constante O(1); em vez de muitas instruções de compare e jump seguidas, com todas sendo executadas no pior dos casos, aqui há apenas um único calculo e pulo direto para o handler da escolha.

Execução especulativa

A execução especulativa, como você já pode ter imaginado, nada mais é que o simples ato do branch predictor de, após tomar uma predição, carregar na pipeline da CPU as instruções sequenciais referentes àquela branch. Ou seja, executar instruções especulativas.

Caso essa execução especulativa se mostrar incorreta no futuro, é preciso que haja um pipeline flush, isto é, uma limpeza da pipeline da CPU. Todas as instruções especulativas—já executadas ou não—são removidas de todos os estágios da pipeline para dar espaço às instruções da rota que se provou ser a correta. Não é preciso reforçar que isto é prejudicial à performance geral.

É necessário entender este mecanismo para a compreensão do próximo tópico: como indivíduos conseguem explorar esse aspecto do branch predictor para acessar memória protegida de um processo.

Spectre

Spectre foi o nome dado à classe de vulnerabilidades que exploram a natureza do branch predictor. Catalogado inicialmente em 2018, o Spectre faz uso da execução especulativa da CPU para acessar endereços de memória que extrapolam um buffer específico. A especiosidade—e âmago—por de trás desse ataque reside no fato que, apesar da CPU reverter a execução de instruções especulativas erradas (por exemplo, efetua as alterações de registradores em estruturas internas para poder desfazer tudo caso a predição esteja errada), o estado do cache ainda é mantido. Isso possibilita discernir qual valor foi lido em uma posição de memória inválida durante a execução especulativa.

Esse exploit não pode ser usado em programas completos, mas somente como um canal lateral dentro de ambientes onde o atacante já consegue executar código limitado e protegido—navegadores, por exemplo.

if (x < size)
	y = probe[array[x] * 4096];

Considere o código acima. Sabemos que o branch predictor guarda um histórico de outcomes anteriores para basear sua predição; imagine, então, que um usuário rode esse trecho de código diversas vezes com valores que sempre satisfaça a condição x < size. O resultado é que o branch predictor ficará inclinado a acreditar que, na maior parte das vezes, essa condição é verdadeira.

Agora, após ter ‘treinado’ o branch predictor, este mesmo usuário decide passar um valor em x que extrapole o tamanho do array, valor este que pode ser um endereço a ser lido dentro da faixa de endereços da memória virtual do processo. Você, como programador, alheio às minúcias microarquiteturais do seu processador, naturalmente acredita que não haverá problema; ora, o acesso ao array é precedido por uma validação, afinal de contas. Contudo, a CPU, buscando maior throughput, usará da execução especulativa de instruções para escolher um caminho antes mesmo que essa condição seja avaliada, e, com base em execuções anteriores, ela vai acreditar que a condição x < size, mesmo para um valor maior que size, neste cenário, é verdadeiro, executando o acesso em array[x].

Além do acesso em array[x], como você pode analisar pelo código acima, também é feito um acesso no array probe, multiplicando o byte lido na posição x por 4096. Isso garante que para cada valor possível lido em array[x] (de 0 a 255), seja usada uma página de memória distinta (pois, geralmente, cada página de memória tem 4KB ou 4096 bytes). O porquê disto ser feito é para assegurar que o endereço final (array[x] * 4096) acessado em probe caia em cachelines diferentes. Veja, o importante aqui não é que cada acesso seja de uma página virtual diferente, mas sim que caiam em cachelines distantes. O uso do valor 4096 é meramente para garantir isto, mas poderia, tranquilamente, ser um valor menor.

Agora, o endereço array[x] * 4096 está cacheado na CPU. Mesmo que a execução tenha sido invalidada e as instruções desfeitas, o cache ainda permanece com o seu estado. Usando um código para medir o tempo de acesso, podemos dizer qual byte foi lido do endereço de memória virtual do processo:

// PSEUDOCÓDIGO!
for (uint8_t i = 0; i < 256; i++)
{
	temp_access(probe[i * 4096]);
}

O índice entre 0 e 255 que for o mais rápido corresponde ao byte lido out-of-bounds. Agora, repita esses mesmos passos várias vezes e você poderá ter acesso a informações completas do processo, como, por exemplo, cookies de sessão.

Para consolidar o funcionamento e entendimento dessa vulnerabilidade, eis a seguinte pipeline:

• A CPU especula que a condição x < size é verdadeira pelo histórico;
• Lê um valor secreto;
• Usa esse valor para acessar probe em páginas virtuais distintas;
• Isso altera o cache;
• O atacante mede qual posição do cache ficou rápida e, consequentemente, recupera o byte secreto.

Obrigado por ler!