Redutores de casos de teste são ferramentas de depuração subestimadas

• Ao procurar a parte que causa um problema em uma entrada grande, um redutor de casos de teste reduz automaticamente a entrada e facilita a depuração
• O redutor recebe um programa, uma entrada e um teste de interesse, e verifica repetidamente se entradas candidatas menores reproduzem o mesmo problema
• Até um redutor simples que apaga linhas consegue, em /usr/share/dict/words, deixar apenas uma palavra longa e, em um exemplo em C, reduzir 78 linhas para 54 em menos de 10 segundos
• O teste de interesse precisa ser escrito de forma correta e rápida por causa de redução excessiva, execuções lentas, execuções infinitas e ambientes de execução paralela
• Além do tamanho da entrada, colocar no teste de interesse métricas como frequência de ocorrência do erro ou comprimento do rastreamento de execução ajuda a depurar bugs não determinísticos e logs de rastreamento grandes

---

Redução de casos de teste

• Quando um programa falha com uma entrada grande e não se sabe qual parte da entrada é a causa, reduzir a entrada facilita identificar a origem do problema
• A redução manual consiste em apagar partes da entrada em um editor de texto e depois verificar se a mesma falha continua acontecendo
• Na redução manual, é fácil a pessoa deixar passar muitas oportunidades de remoção, e após apagar algo o programa pode terminar normalmente ou emitir outro erro normal
• Se o efeito só aparece quando partes A e B, separadas entre si, precisam ser removidas juntas, o espaço de busca cresce muito

Estrutura básica de um redutor de casos de teste

• Um redutor de casos de teste é uma ferramenta que recebe um programa, uma entrada e um teste de interesse para tornar a entrada menor
• O teste de interesse retorna 0 quando a entrada reduzida reproduz o erro de interesse e retorna um valor diferente de 0 caso contrário
• Em redutores de casos de teste, reduções de 95~99% são comuns e podem tornar a depuração muito mais fácil
• O redutor funciona mesmo sem entender semanticamente quais partes da entrada devem ser removidas

• Exemplo de redutor simples

  • O programa de exemplo lê linhas de um arquivo e imprime Word too long se houver uma linha com comprimento maior que 25
  • O teste de interesse retorna 0 se a saída do programa contiver Word too long, e 1 se não contiver
  • Um redutor simples em Python lê a entrada linha por linha, grava em um arquivo temporário uma entrada candidata com uma linha removida e então executa o teste de interesse
  • Se a candidata for interessante, a entrada atual é substituída por ela, e quando não for mais possível reduzir, o resultado é impresso em stdout
  • Ao executar em /usr/share/dict/words, sobra apenas antidisestablishmentarianism

Redutores mais fortes e o Shrink Ray

• O exemplo de programa em C com 78 linhas trata de um problema em que as configurações FAST=0 e FAST=1 produzem saídas diferentes
• O teste de interesse só passa quando, após compilar com as duas configurações, a saída de FAST=0 é 0d754a56 e a saída de FAST=1 é diferente desse valor
• Um redutor simples consegue reduzir a entrada em C de 78 linhas para 54 linhas em menos de 10 segundos, uma redução de cerca de 30% pelo critério de linhas
• Se for adicionado i=0 para voltar a apagar desde a primeira linha sempre que uma candidata interessante for encontrada, o tempo de execução aumenta quase 10 vezes e mais 3 linhas são removidas
• Shrink Ray oferece várias regras de redução e execução paralela, e com --no-clang-delta não usa conhecimento específico sobre C
• Depois de cerca de 15 minutos, o Shrink Ray reduziu a entrada em mais de 60% em bytes e, em outro caso, encontrou cerca de 90% de redução após uns 20 minutos e depois foi além até 99%
• O Shrink Ray conhece a sintaxe padrão de comentários e tenta removê-los no início, além de também tentar reduzir inteiros para valores menores

Dificuldades ao escrever testes de interesse

• Como o redutor de casos de teste segue o teste de interesse ao pé da letra, se o teste passar por engano pode ocorrer redução excessiva, em que a entrada é reduzida além do ponto desejado
• O Shrink Ray verifica explicitamente se o teste de interesse aceita uma entrada vazia, e esse tipo de situação pode acontecer com frequência
• No exemplo em C, se for verificado apenas se as duas saídas são diferentes, diferenças pouco importantes ou enganosas podem fazer uma entrada ser classificada como interessante
• A verificação test "$slow_out" = "0d754a56" confirma que a versão lenta realmente está fazendo o comportamento esperado e reduz a chance de redução excessiva

• Velocidade e timeout

  • Se o teste de interesse for rápido, o redutor pode executá-lo centenas de vezes por segundo
  • Mesmo exemplos de tamanho médio podem levar a centenas de milhares de tentativas de redução, então otimizar o teste de interesse afeta bastante o tempo total
  • Há um caso em que desativar a geração automática de core dump deixou o teste de interesse cerca de 3 vezes mais rápido
  • O redutor pode remover uma linha como i-=1 e transformar um programa que terminava em um programa que roda infinitamente
  • Se o programa executa em 0,1 segundo mas o timeout é definido como 60 segundos, a redução inteira fica muito mais lenta
  • Para programas rápidos, usa-se timeout arredondado para 1~2 segundos; nos demais casos, usa-se algo como 1,5~2 vezes o tempo da execução inicial

• Execução paralela

  • Redutores como o Shrink Ray executam o teste de interesse em paralelo
  • O Shrink Ray executa cada teste de interesse em um diretório temporário e limpa esse diretório automaticamente
  • Há casos em que apenas um diretório temporário não basta, e as medidas necessárias variam conforme o caso

Induzindo determinismo com testes de interesse

• O trecho de exemplo cria um erro de divisão por zero por causa de len([])==0, mas devido à condição random.random() < 0.33 o problema só aparece em cerca de um terço das execuções
• Bugs não determinísticos fazem o erro aparecer e desaparecer aleatoriamente, o que torna a validação de hipóteses mais difícil e demorada
• Se o redutor remover a chamada de random.random() ou alterar a expressão condicional, um erro não determinístico pode virar um erro determinístico
• Na prática, a não determinismo costuma envolver interações desfavoráveis entre várias partes da entrada, então removê-la pode ser difícil
• O redutor de casos de teste funciona como um algoritmo de subida de encosta que usa o tamanho da entrada como métrica substituta para “melhor”
• Essa abordagem de subida de encosta tende a ficar presa em ótimos locais, e uma entrada mais curta nem sempre é melhor para investigar o erro

• Método de execuções repetidas

  • Ao lidar com bugs não determinísticos, usa-se um teste de interesse que executa a entrada várias vezes e a aceita se o erro de interesse ocorrer pelo menos uma vez
  • Esse método pode ajudar a aumentar a frequência de ocorrência do erro
  • Como um teste que passa se o erro ocorrer ao menos uma vez também aceita entradas não determinísticas, a redução pode avançar enquanto a não determinismo até aumenta
  • Uma abordagem mais rígida é aceitar a entrada apenas quando o erro ocorre em todas as n repetições
  • Um teste rígido tem baixa probabilidade de aprovar a entrada inicial, o que dificulta iniciar o Shrink Ray; no exemplo com condição de 3 repetições, a chance inicial de aprovação é de 3,6%
  • Um contorno prático é começar com o teste “erro em pelo menos 1 de n execuções” e, quando surgir uma entrada reduzida em que o erro ocorre com mais frequência, trocar para o teste “erro em n execuções consecutivas”

Contadores globais e outras métricas-alvo

• A intervenção manual é poderosa, mas exige acompanhar o Shrink Ray e é fácil perder o momento certo para intervir
• Para guiar o redutor por uma propriedade diferente do tamanho da entrada, é possível impor essa propriedade dentro de um único teste de interesse
• Na depuração do yk, mais importante que o tamanho da entrada é o comprimento do rastreamento de execução, isto é, um valor próximo do número de instruções executadas pelo programa
• A saída YKD_LOG="$t:jit-asm" grava em arquivo o IR de rastreamento em texto e as instruções de máquina, e uma saída jit-asm curta facilita a depuração
• wc -l conta o número de linhas do arquivo de log e serve como métrica substituta aproximada do comprimento do rastreamento
• O teste de interesse trata a entrada como não interessante se o número atual de linhas do rastreamento for maior que o menor valor anterior, e esse menor valor fica salvo em /tmp/global_best
• Esse método não é seguro para redução paralela e inclui suposições sobre como o redutor é chamado, mas para um script curto e descartável isso é tratado como uma imperfeição aceitável
• Em um caso de segfault no yk, a redução normal deixou um rastreamento de 40 mil linhas, mas essa técnica produziu, em vez de uma entrada reduzida maior, um rastreamento de 10,1 mil linhas e permitiu identificar o bug raiz em 30 minutos

Resumo principal

• Redutores de casos de teste não são ferramentas úteis apenas para quem escreve compiladores; também podem ser usados em problemas fora desse contexto
• Além do objetivo básico de reduzir o tamanho da entrada, o teste de interesse pode ser usado para guiar propriedades como frequência do erro, tempo de relógio, nível de não determinismo e comprimento do rastreamento
• A precisão do teste de interesse, sua velocidade de execução, o timeout e a segurança em execução paralela determinam a eficácia real do redutor
• Mesmo sem entender quase nada da semântica da entrada e do programa, o redutor consegue manter o problema em uma forma menor e aumentar a produtividade na depuração

[GN⁺]

Comentários do Lobste.rs

• Fico realmente curioso: existe alguém que não reconheça o valor da redução automática de casos de teste? A palavra “subestimada” soa como se houvesse gente que nem sempre quisesse reduzir casos de teste
  Mesmo que você consiga identificar o bug imediatamente, não precisa de um caso reduzido para teste de regressão?

  • Acho que, em geral, desenvolvedores nem chegaram a pensar nisso como uma técnica
  • A primeira linha do texto é “Test-case reducers are less well known than they should be, [...]”, e foi exatamente essa a minha impressão, mesmo sendo alguém que passou anos recomendando que as pessoas usassem fuzzing e testes baseados em propriedades
    Ambos frequentemente incluem algum tipo de redução de casos que falham, ou “shrinking”, e isso os torna muito mais práticos de usar
  • Em fuzzer eu conheço mais ou menos. Depois que o fuzzer encontra um caso de falha, ele reduz automaticamente, e essa parte funciona muito bem
    Só que, pela minha experiência com fuzzing em geral, especialmente usando AmericanFuzzyLop e AFL++, a configuração é tão sofrida que eu normalmente evito
    A maior parte dos bugs com que eu lido também se parece menos com “se você passar este arquivo de entrada, dá erro” e mais com “dá erro para algum usuário, em algum lugar”. Às vezes dá para reduzir isso a “sob certas condições, ao seguir uma sequência de etapas, dá erro”, mas 1) eu não sei bem como aplicar um redutor automático de casos de teste a “um usuário fazendo coisas em sequência”, e 2) quando você já encontrou um jeito de reproduzir localmente, 99% da depuração já está feita
    Imagino que o autor consideraria essa minha atitude como “subestimar”
  • Acho que já é minoria quem sequer sabe o que é redução de casos de teste

• Este texto e seus exemplos dizem que redutores deveriam ser mais usados também fora do contexto de compiladores, mas a perspectiva continua bastante puxada para a de quem escreve compiladores
  Como o ~silentbicycle escreveu, a maioria das reduções de caso de teste acontece no contexto de fuzzers ou testes baseados em propriedades, com a funcionalidade de redução embutida em um framework maior. Compiladores são uma das áreas incomuns em que um redutor independente é útil. Não sei dizer se há muitos outros casos em que um redutor independente também ajude
  A parte sobre determinismo também é interessante. O exemplo começa com um arquivo de entrada que dispara o bug, ou seja, um script, e é isso que traz o determinismo; não é algo inerente ao próprio programa com bug, o interpretador. Não está claro se o texto quer dizer que a técnica de “interestingness” também funciona em cenários fora de compiladores, nos quais o próprio programa com bug é não determinístico
  Como forma de adaptar um problema de teste para fuzzing e redução de casos de teste, eu recomendaria criar um conjunto numerado de comandos imperativos. Em cada comando, inclua verificações leves de consistência para detectar falhas de teste, pegando também casos que não travam imediatamente. Verificações pesadas de consistência podem ficar em comandos separados, para não deixar o teste lento demais. Em testes puramente aleatórios, o harness escolhe comandos ao acaso até algo quebrar; depois, ao trocar para um harness de fuzzer, basta fazer o fluxo de bytes de entrada do fuzzing escolher os comandos. Assim você ganha automaticamente coisas boas como testes de regressão determinísticos e redução de casos de teste
  Nunca tive muito resultado pedindo explicitamente ao libfuzzer para reduzir casos de teste, provavelmente porque ele já os reduziu durante a geração de entradas. Por isso, nunca me senti motivado a experimentar mais verificações de interestingness para ajudar um fuzzer genérico a reduzir casos de teste. Fico curioso se outras pessoas já tiveram sucesso

  • Concordo totalmente. Eu uso muito esse método. Você cria uma representação simbólica de uma interface com estado, geralmente faz um interpretador simples baseado em switch-case ou match, depois gera aleatoriamente uma lista de operações, executa e reduz a entrada que dispara asserts de violação de pré/pós-condições ou corrupção interna
    Chame de teste baseado em propriedades, fuzzing ou model checking leve, isso pode ser surpreendentemente eficaz para encontrar bugs profundos. Já vi muitas interfaces com estado em que cada operação, isoladamente, estava correta, mas as suposições entre elas ficavam levemente desalinhadas, e essas operações, quando combinadas de formas inesperadas, escalavam para corrupção interna
    Também é útil executar a lista de operações em paralelo com uma implementação simples em memória, baseada em tabela hash ou lista, e verificar se os resultados coincidem. Se houver divergência, quase sempre é bug ou um caso de borda que precisa ser melhor documentado
  • Às vezes trabalho com otimização de transporte e frequentemente encontro cenários bem complexos em que invariantes são violados. Seria ótimo ter um redutor de casos de teste, mas antes eu precisava me contentar em reduzir manualmente[0]
    Infelizmente, os arquivos de dados são complexos demais para algo como o shrinkray conseguir lidar. Ele lê dados tabulares de vários “arquivos” diferentes, com dependências de longo alcance, então eu provavelmente teria que codificar diretamente o conhecimento de domínio sobre como reduzir isso
    Pelo ritmo do avanço da IA, acho que da próxima vez que surgir um cenário desses vou escrever um redutor sob medida
    [0] Se quisermos apelar para uma ontologia ambígua, um problema de otimização é um problema de busca que minimiza custo e, nesse sentido, é praticamente a mesma coisa que um compilador, então não é um exemplo perfeito

• Li isso três vezes tentando entender como aplicar a testes escritos com pytest
  Quero reduzir a complexidade da minha suíte de testes, então estou pensando em reler uma quarta vez quando não estiver trabalhando

  • Se você usa Python, o primeiro passo é adotar o Hypothesis, que já vem com redução de casos de teste embutida

• No ano passado, ao investigar problemas de ordem de execução de testes no CI, eu fiz uma ferramenta para ajudar a reduzir a lista de testes
  Basicamente, ela executava cortando as linhas pela metade
  O script em si tem bastante bug, mas foi muito legal ver uma lista de 5000 testes se reduzir a algo como 4 testes que disparavam meu bug de concorrência
  Fico realmente curioso se o Shrink Ray teria simplesmente funcionado no meu caso. Eu sinceramente acho que “reduzir um conjunto de linhas com base em um teste” deveria fazer parte do kit padrão de ferramentas de linha de comando

• Relacionado a este tema, testes baseados em propriedades também usam uma abordagem bem parecida de “reduzir” o espaço de estados das entradas geradas para produzir contraexemplos do teste
  A vantagem dos testes baseados em propriedades é que você pode guiar e estruturar o espaço de busca. Você pode transformar a entrada em um conjunto de transições que aciona uma máquina de estados que modela o programa
  Sempre me surpreende ver como essa técnica ainda é pouco usada, mesmo em áreas em que ela encaixa muito bem, como bancos de dados e sistemas distribuídos. Na semana passada mesmo, no $WORK, montei um teste desses em poucas horas e descobri rapidamente que nosso sistema não convergia. O teste imprimia um rastreamento limpo que meus colegas conseguiam entender de imediato quando eu mostrava
  Pessoalmente, considero essa a técnica de teste com melhor retorno sobre investimento para depurar sistemas complexos