Como testar o software de uma calculadora - o fuzzing

“Beware of bugs in the above code; I have only proved it correct, not tried it.” — Donald Knuth

Um passo importante do desenvolvimento do software passa por certificar que o mesmo se comporta como esperado. É este o passo sobre o qual vamos falar hoje: como testar um programa? Como tornar o software robusto?

A primeira solução é a mais natural: teste você mesmo todas as características do programa. No entanto, dois problemas vão surgir muito rapidamente.

Antes de mais nada, os testes manuais são muitas vezes tendenciosos: estamos presos aos nossos hábitos quando usamos um software e acabamos por não testar algumas funcionalidades.

O segundo problema é a quantidade de testes a realizar, que muitas vezes é infinita. Ora vejamos: no caso do Epsilon, o software da nossa calculadora, um utilizador pode pressionar qualquer uma das 46 teclas. Para testar todos os cenários possíveis onde o utilizador pressiona quaisquer 10 teclas de seguida, seriam necessários 42420747482776576 testes manuais. A uma taxa de uma tecla por segundo, este processo levaria… mais de mil milhões de anos! E um cenário com 10 toques de teclas está longe de ser longo.

Automatizar os testes

Porque não gerar então automaticamente rotinas de teste aleatórias e executá-las no software desejado? No caso do Epsilon, poderíamos gerar uma sequência de eventos que podem ser escolhidas pelo utilizador (por exemplo: OK, seta à esquerda, seno, 9, …) e fazer com que seja executada automaticamente pelo computador. É de facto muito mais rápido do que sermos nós a fazê-lo: em média, um computador é capaz de simular 150 000 toques no teclado por segundo.

cat /dev/urandom|pv|./app.bin
1.54MiB 0:00:10 [ 152KiB/s]

E o computador nunca se cansa de gerar casos de testes falsos, ou de os aplicar efetivamente. Também chamado de teste monkey-testing, este método simples não discrimina nenhum teste. A metáfora é bastante reveladora: um exército de macacos, cada um pressionando os botões da sua calculadora, à espera de encontrar um bug.

Automático, mas inteligente!

Sendo o conjunto de testes possíveis enorme, podem correr-se biliões de cenários por hora sem que surja um problema interessante. É por isso que é importante orientar o gerador de cenários para situações interessantes. Isto é precisamente o que um fuzzer faz: fornecido com sequências de eventos que o utilizador provavelmente vai realizar e o fuzzer usa essas “rotinas” para gerar aleatoriamente outras rotinas que poderão ser igualmente interessantes.

Mais especificamente, o fuzzer american fuzzy lop (AFL) utiliza aquilo a que chamamos um algoritmo genético: este fuzzer recebe de input um conjunto de rotinas, que de seguida modifica, fazendo-as sofrer pequenas alterações - como se fossem “mutações”: a ideia é descobrir quando estas mutações trazem essas novas rotinas.
Contudo, será necessário compilar o programa com uma instrumentação especial que permita ao AFL saber quais são as partes do programa usadas em determinado cenário.

Na prática, o fuzzer é fornecido com cerca de dez cenários de exemplo e algumas horas (ou dias…) mais tarde envia de voltas as rotinas de eventos que fazem o programa falhar ou nunca terminar. O fuzzer também é perspicaz o suficiente para tentar minimizar as rotinas e devolver apenas as sub-rotinas interessantes, facilitando a correção do programa.

O fuzzing não é uma solução milagrosa

O fuzzing é obviamente muito bom (obrigada Michal Zalewski pelo AFL!), porém o critério de falha é limitado: o programa não ter terminado ou ser encerrado devido a um erro.

No entanto o Epsilon, por exemplo, poderia exibir “1+2=11” sem fazer parar o programa: o fuzzer não compreenderia o erro. Todos os métodos de testes têm as suas falhas: embora rápido e automatizado, o fuzzing não pode ter nenhuma noção do funcionamento interno de um software e dos seus requisitos. É por isso que uma combinação de vários métodos de teste é muitas vezes necessária para eliminar o maior número de bugs possível. No nosso caso, usamos, entre outros, os seguintes:

  • Testes unitários: geramos diversos testes específicos para o nosso software que são uma fonte de verdade. Por exemplo, “1+1 de ver igual a 2” ou “raiz(8) deve simplificar para 2*raiz(2)”. Estes testes permitem fazer evoluir o código enquanto verifica regularmente se outras funcionalidades foram perturbadas.
  • Programas de deteção de falhas na gestão de memória (memcheck de Valgrind).
  • Análise estática (clang-checker e coverity scan).
  • E por útlimo, mas não menos importante, os bons velhos testes manuais!