Quais são as melhores práticas para testar programas com comportamento estocástico?

14

Fazendo trabalho de pesquisa e desenvolvimento, muitas vezes me pego escrevendo programas que têm um grande grau de aleatoriedade em seu comportamento. Por exemplo, quando trabalho em Programação Genética, geralmente escrevo programas que geram e executam código fonte aleatório arbitrário.

Um problema ao testar esse código é que os bugs geralmente são intermitentes e podem ser muito difíceis de reproduzir. Isso vai além de apenas definir uma semente aleatória com o mesmo valor e iniciar a execução novamente.

Por exemplo, o código pode ler uma mensagem do buffer de anel kernal e, em seguida, fazer saltos condicionais no conteúdo da mensagem. Naturalmente, o estado do buffer do anel será alterado quando mais tarde tentar reproduzir o problema.

Embora esse comportamento seja um recurso, ele pode disparar outro código de maneiras inesperadas e, portanto, frequentemente revela bugs que os testes de unidade (ou testadores humanos) não encontram.

Existem práticas recomendadas estabelecidas para testar sistemas desse tipo? Nesse caso, algumas referências seriam muito úteis. Caso contrário, outras sugestões são bem-vindas!

John Doucette
fonte
5
Você também não pode zombar do buffer de anel do kernel? E outros aspectos aleatórios do seu código?
Jonathan Merlet
1
@JonathanMerlet Potencialmente, mas o problema é que, quando implantado, o código terá acesso ao buffer de anel real (de fato, a um sistema operacional real). Portanto, se eu testar apenas em uma versão simulada, adiaremos a descoberta desses erros até mais tarde.
John John Doucette
Parece-me que o problema não está relacionado ao comportamento aleatório do programa (já que isso pode ser controlado pela semente aleatória), mas a estados particulares desse 'buffer de anel do kernel'. Portanto, sua pergunta é realmente 'como faço para testar um programa que depende do estado externo', certo?
AakashM
@AakashM, sim, é a melhor maneira de expressá-lo. Para ser mais específico, um programa com um estado externo, que acessa estocástico ou altera o estado externo.
John Doucette

Respostas:

7

É útil adicionar ganchos, como sugerido, para recriar estados exatos. Também instrumentar o sistema para que ele possa despejar suas "sementes" (no seu caso, incluindo a semente PRNG, bem como o buffer de anel do kernel e quaisquer outras fontes de entrada não determinística).

Em seguida, execute seus testes com entrada aleatória verdadeira e estilo de regressão com todos os casos interessantes descobertos anteriormente.

No caso particular de seu acesso ao kernel, eu recomendaria fazer uma zombaria em qualquer caso. Use o mock para forçar classes de equivalência com menor probabilidade de aparecer na prática, no espírito de "vazio" e "cheio" para contêineres, ou "0, 1, 2 ^ n, 2 ^ n + 1, muitos" para coisas contáveis. Em seguida, você pode testar com o mock e com o real, sabendo que você lidou e testou os casos em que você pensou até agora.

Basicamente, o que estou sugerindo equivale a uma mistura de entradas determinísticas e não determinísticas, com as determinísticas sendo uma mistura daquelas em que você pode pensar e das que foram surpreendidas.

Stephan A. Terre
fonte
6

Uma coisa razoável a se fazer é propagar o gerador de números aleatórios com um valor constante para os testes, para que você obtenha um comportamento determinístico.

Dima
fonte
1
esta; ou zombar completamente do prng
jk.
1
Obrigado pela sugestão! Eu já faço isso para testes de unidade, mas não consigo testar todos os programas possíveis manualmente.
John John Doucette
2
Mas isso significa que você não pode testar se a aleatoriedade funciona corretamente ..
Louis Rhys
2

Eu acho que o teste estatístico é o único caminho. Assim como os números aleatórios são "testados" quanto à aleatoriedade por testes estatísticos, também precisam ser algoritmos que usam comportamento aleatório.

Simplesmente execute o algoritmo várias vezes com entrada igual ou diferente e compare-o. O problema com essa abordagem é um aumento maciço no tempo computacional necessário para concluir o teste.

Eufórico
fonte
Não necessariamente, porque você pode escolher um pequeno conjunto de entradas "abrangentes" e executar várias vezes nelas - o número de entradas necessárias para verificar a confiabilidade pode ser menor. Este conjunto "abrangendo" deve entrar em cada ramo do código, inicializar todos os objetos, etc.
Daniel Moskovich
2

Não sou especialista neste domínio, mas há uma literatura científica relativa ao teste estocástico do programa.

Se você não pode criar facilmente classes de teste, um teste estatístico pode ser usado, como #Euphoric disse. Borning et al. compare uma abordagem tradicional e uma estatística. Uma generalização dos testes estatísticos sugeridos pelo @Euphoric pode ser o discutido por Whittaker. Ele sugeriu criar um modelo estocástico do comportamento desejado (estocástico, no seu caso) e, em seguida, gerar casos de teste específicos a partir desse modelo (consulte seu artigo dedicado ).

mgoeminne
fonte
Obrigado! Parece muito útil. Para as instituições acadêmicas fora, uma versão pré-impressão do papel pode ser retirado do repositório de código do Google do autor aqui: team4model.googlecode.com/svn/trunk/resources/paper/...
John Doucette