Essa história de Heartbleed me lembrou de algumas coisas que eu tinha pensado meses atrás e não lembrava mais.
Para quem não sabe, o Heartbleed (concisamente explicado por este quadrinho do xkcd) é uma falha de segurança na OpenSSL (uma biblioteca que implementa os protocolos de comunicação segura SSL e TLS usada por basicamente todo o mundo) que permite a um atacante obter porções da memória do servidor potencialmente contendo dados como nomes de usuários, senhas, a chave privada do certificado servidor, etc.
Como 237% das falhas de segurança de software encontradas nos últimos 30 ou 40 anos, o Heartbleed é causado por um buffer overflow (tecnicamente "overread", pois trata-se de leitura e não escrita), e teria sido evitado se a OpenSSL tivesse sido escrita em uma linguagem que fizesse verificação de limites (bounds checking) antes de acessar uma posição de um vetor.
No fórum do xkcd, alguém escreveu:
Heartbleed is yet another example of why coding in C is a bad idea. A memcpy with an incorrect size caused all this because C compilers do no bounds checking. Heartbleed wouldn't have happened if OpenSSL had been written in, for example, Ada. Instead of an information leak that leaves no trace it would have been a denial of service at the worst.
Mais adiante na thread, alguém respondeu:
It's yet another example of why poorly written code is a bad idea. No amount of programming languages and frameworks is going to protect you from incompetent programmers.
A essa altura eu fechei a tab e fui ler outras coisas, porque se eu continuasse ali eu ia acabar respondendo com o equivalente virtual do soco na cabeça pra desentupir o cérebro. Isso é mais ou menos como ter um viaduto do qual diariamente caem carros há trinta anos, e se recusar a colocar um muro de proteção nas bordas, porque se alguém cai "a culpa é do motorista que foi incompetente".
Se bounds checking é uma coisa tão mágica, por que não está todo o mundo usando linguagens que fazem bounds checking? A resposta, obviamente, é performance, a propriedade mais importante de qualquer software. Does it work? No, but it's fast! Ok, chega de comentários sarcásticos por ora. Eu já falei sobre a performance de bounds checking em um post anterior, onde fiz alguns benchmarks com código em C com e sem bounds checking (implementado manualmente com ifs no código testando se o índice está dentro dos limites do vetor e abortando a execução caso contrário). As conclusões no final foram que:
Do segundo item depreende-se que um acesso bounds-checked a um vetor é cerca de 25% mais lento do que um acesso direto. Assumindo que a maioria dos programas não consiste primariamente de acessos a vetores, esses 25% talvez não fizessem tanta diferença, e o benefício seria maior que o custo. (Disclaimer: talvez no caso geral o slowdown seja maior que 25%. Talvez eu faça mais uns benchmarks, só para não perder o costume, quando estiver mais disposto. Read on.)
O primeiro item é mais interessante: em algumas circunstâncias é possível provar que todos os acessos a um vetor estarão dentro dos limites, e nesses casos não é necessário fazer qualquer verificação em tempo de execução. Por exemplo (assumindo uma função hipotética length_of, que retorna o comprimento de um vetor), em um loop como:
for (i=0; i < length_of(vector); i++)
printf("%d", vector[i]);
não é necessário verificar em tempo de execução se vector[i] está dentro dos limites do vetor, pois é possível ao compilador provar em tempo de compilação que i só adquire valores que são índices válidos do vetor. Para casos simples como esse, o gcc e outros compiladores já são capazes de fazer esse tipo de análise estática, como visto no post linkado; não se trata de uma tecnologia mítica e utópica. Os problemas começam a surgir quando temos coisas como:
int get(int vector[], int i) {
return vector[i];
}
void foo() {
...
for (i=0; i < length_of(vector); i++)
printf("%d", get(vector, i));
}
pois a função get não sabe que será chamada com um índice válido. Se o compilador fizer inlining de get no corpo de foo, ele será capaz de eliminar o bounds checking, mas, no caso geral, não queremos sempre fazer inlining (get poderia ser uma função grande chamada em diversos pontos do código, por exemplo), e a função get (que poderia ter sido compilada separadamente) não pode assumir que quem a chamar lhe passará um índice válido.
Mas ela pode exigir. Imagine que pudéssemos escrever algo do tipo:
int get(int vector[n], int i)
i>=0 && i<n;
{
return vector[i];
}
i>=0 && i<n é parte da assinatura da função: além de ela exigir que o primeiro argumento seja um vetor de int e o segundo um int, ela também exige que a condição especificada seja satisfeita. Com isso: (1) a função pode assumir que a condição é verdadeira dentro do corpo, eliminando assim o bounds checking; e (2) o encargo de testar se a condição é verdadeira é passado para o chamador da função (foo, no nosso exemplo), onde há contexto suficiente para determinar se a condição é sempre verdadeira em tempo de compilação (por conta de ocorrer dentro do for, no nosso exemplo). Se esse for o caso, o bounds check pode ser eliminado do programa; caso contrário, o check é realizado em tempo de execução, garantindo que o acesso será seguro.
Mesmo em loops em que o range não está evidentemente nos limites do vetor é possível utilizar uma pequena dose de falcatrua para "amortizar" os checks. Por exemplo, em uma função como:
int sum(int vector[], int start, int end) {
int i, total=0;
for (i=start; i<=end; i++)
total += vector[i];
return sum;
}
não é possível eliminar completamente o checking, pois não sabemos de antemão se start e end é uma faixa válida de índices do vetor. Mas nem por isso precisamos fazer o checking dentro do loop. Ao invés disso, podemos transformar o código em:
int sum(int vector[], int start, int end) {
int i, total=0;
int length = length_of(vector);
if (start < 0) out_of_bounds_exception();
if (end >= length) out_of_bounds_exception();
for (i=start; i<=end; i++)
total += vector[i];
return sum;
}
Se a execução passar dos ifs, então start e end são índices válidos no vetor, e não precisamos executar testes para cada acesso.
Só tem um pequeno problema na transformação acima: ela encerra o programa se end estiver além dos limites do vetor mesmo antes de vetor[end] ter sido acessado; basicamente uma exceção que ainda não aconteceu encerra o programa. Neste programa em particular isso não chega a ser um problema pois o comportamento observável do programa seria o mesmo, mas isso não é válido no caso geral. Por exemplo, poderia ser que eu soubesse de antemão que o vetor é encerrado por um valor 0, e escrevesse o código como:
int sum(int vector[], int start, int end) {
int i, total=0;
for (i=start; i<=end; i++) {
if (vector[i] == 0) break;
total += vector[i];
}
return sum;
}
Nesse caso, mesmo que eu passe um end inválido, pode ser que o meu programa termine com um resultado correto, desde que o vetor seja devidamente terminado com um 0. O compilador não tem dados suficientes para provar que o vetor terá o 0, entretanto, e portanto checks precisam ser inseridos. Ainda assim, é possível transformar o código em algo como:
int sum(int vector[], int start, int end) {
int i, total=0;
int length = length_of(vector);
if (start < 0) out_of_bounds_exception();
int bounded_end = min(end, length-1);
for (i=start; i<=bounded_end; i++) {
if (vector[i] == 0) break;
total += vector[i];
}
if (end>bounded_end && i>bounded_end) out_of_bounds_exception();
return sum;
}
que é menos trivial (e provavelmente pode ser escrito de maneira mais eficiente, mas menos clara para fins de exposição), mas preserva a semântica do programa (a prova é sugerida como exercício para o leitor).
Nem sempre os índices de vetores provêm de ranges seqüenciais. Um exemplo em que isso não ocorre é em uma busca binária, em que, para eliminar os checks, o compilador precisaria conseguir provar que (min+max)/2 está entre min e max*.
Outra situação é quando criamos um vetor de lookup reverso r que mapeia os valores de um vetor v aos índices correspondentes, i.e., se v[1] = 42, então r[42] = 1. Nesse caso, para eliminar os checks, o compilador precisa ter informação suficiente para saber que os valores de v são sempre índices válidos em r. O que pode ser viável se o tipo de v indicar qual é a faixa de valores válidos que o vetor pode conter. De qualquer forma, é interessante que esse tipo de assumption usualmente escondida sobre o comportamento do programa seja explicitamente expressível na linguagem, especialmente se tais declarações (1) não forem obrigatórias, e (2) forem usadas para melhorar performance. (Side-effect: as pessoas seriam incentivadas a documentarem melhor seus programas visando ganhar performance. Todos comemora.)
Bounds checking é só um componente de memory-safety. Outro aspecto importante é garantir que os ponteiros/referências apontam de fato para objetos válidos em memória, e não para áreas que já foram desalocadas (ou pior, realocadas para outros objetos). A solução clássica para o problema é gerência automática de memória com garbage collection, mas há outras soluções possíveis.
O fato de que, com a introdução de pré-condições, os tipos das funções falam mais sobre o que a função faz, provavelmente implica que os tipos das funções mudam com mais freqüência quando uma função é alterada, efetivamente alterando sua interface, uma vez que cabe ao chamador da função garantir que as pré-condições são satisfeitas. Isso torna mais provável que uma alteração em uma biblioteca exija a recompilação de todo o mundo que depende dela. A solução que eu proponho é distribuir tudo como bytecode e (re)compilar para código nativo transparentemente as needed (o que tem inúmeras outras vantagens, tais como não fixar a ABI, permitir compilar o código com ou sem certs instruções (e.g., SSE) dependendo de sua disponibilidade no processador, permitir se aproveitar de mandingas brabas dependentes de uma versão da arquitetura (e.g., assumir que ponteiros têm efetivamente 48 bits e não 64 no amd64) sem se preocupar se daqui a 5 anos elas não vão mais funcionar, pois o ambiente pode simplesmente testar se uma assumption é válida e recompilar caso contrário, etc.). Uma solução alternativa é the C++ way: não fazer nada a respeito.
1. Bounds checking, galera. De uma vez por todas. Entre acidentes e talvez-nem-tão-acidentes, depois de 30 anos tá na hora de a gente aprender, não?
2. Bounds checking não necessariamente implica perda de performance, pois o compilador pode determinar que certos checks não são necessários em tempo de execução. Em uma linguagem sem bounds checking, o programador tem que ou inserir os checks manualmente anyway para garantir que não ocorrerá nenhum buffer overflow, ou concluir que o check não é necessário pois o índice está garantidamente dentro do vetor. No primeiro caso o check está lá anyway com ou sem bounds checking automático; com o check automático não há o risco de o programador esquecer de fazer o teste. No segundo caso o programador pode (idealmente) escrever explicitamente o raciocínio que permite concluir que o check é desnecessário, o que, além de menos error-prone (já que, se o compilador não for capaz de concluir que o raciocínio é válido, seja porque o raciocínio está errado ou porque o compilador não é suficientemente esperto, ele vai inserir o check dinâmico), é benéfico do ponto de vista de engenharia de software.
P.S.: Idéias similares às apresentadas neste post já foram inventadas e reinventadas mais de oito mil vezes sob os nomes de dependent types, design by contract, e sabe-se lá mais que outros (sinta-se à vontade para citar referências nos comentários). É por este motivo que, embora o tópico seja perfeitamente o tipo de coisa na qual eu gostaria de trabalhar, eu provavelmente não vou nem tentar empurrar o tema da minha dissertação de mestrado para esse caminho. Mais sobre isso em um post futuro, talvez.
_____
* Ou ser informado disso pelo programador, como um "axioma" sem prova. Nesse caso introduz-se uma fonte bastante perigosa de potenciais bugs, pois um axioma incorreto poderia levar a transformações de código incorretas em pontos arbitrários do programa. Uma solução semi-aceitável neste caso particular é ter uma função na biblioteca padrão da linguagem que calcula a média de dois números, acompanhada de um axioma sobre o resultado. O problema é que se a habilidade de declarar axiomas sem prova for introduzida na linguagem, é praticamente certo que alguém vá usá-la incorretamente e criar outro Heartbleed. Outra alternativa é introduzir um meio de o programador escrever a prova do axioma, que o compilador seria então capaz de verificar. Isto é nada mais, nada menos do que uma aplicação de proof-carrying code.
Caro Sr. Fantasma,
És verdadeiramente um indivíduo de verdadeira lucidez. Espero contar com vossos sóbrios e esclarecedores pareceres sobre o estado da computação moderna no futuro.
Um fraterno início de semana,
Huang Ho, CEO
Bolshevik Computing Ltd.
[P.S.: Eu ri alto lendo o comentário. :P]
https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcS9XFg_hOChk4dh_o2G2bcRIy-LumN2r0xNCHstdhoV0HWH0iZkgA
p.s.: Enter the rom name and press enter: _
Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.
Powered by Blognir.
Cayo, 2014-04-13 13:30:49 -0300 #
Eu sempre escrevi código em C com bibliotecas como OpenScripture e OpenTTB, e geralmente me defronto com bugs de overchecking. Não acho que seja razão pra mudar de linguagem. Digo, se eu pudesse escolher, se tanto fizesse C ou Python ou Haskell ou até mesmo Clojure, bom, eu tendo a preferir código assim:
int fun(var x) :: one {
let x := -14
do while {}
return buffer[x]
}
que a alternativa, mas sempre compilo com -o4 ou até mesmo -o5. No final das contas o meu makefile tem 100-200 MB e já até aconteceu kernel contrast numa máquina antiga sem IP onde eu estava programando, mas geralmente na minha opinião a recompensa é que meu código é proof-safe e certificado OpenSpec 2.0, com ou sem SSL, pouco importa. Sugiro a todos que façam o mesmo.
-- Haker Fantasma