Teste de unidade de algoritmos inerentemente aleatórios / não determinísticos

Meu projeto atual, sucintamente, envolve a criação de "eventos restritos e aleatórios". Estou basicamente gerando um cronograma de inspeções. Alguns deles são baseados em restrições estritas de agendamento; você realiza uma inspeção uma vez por semana na sexta-feira às 10:00. Outras inspeções são "aleatórias"; existem requisitos configuráveis ​​básicos, como "uma inspeção deve ocorrer 3 vezes por semana", "a inspeção deve ocorrer entre as 9h e 21h" e "não deve haver duas inspeções no mesmo período de 8 horas", mas dentro de quaisquer restrições configuradas para um conjunto específico de inspeções, as datas e horários resultantes não devem ser previsíveis.

Os testes de unidade e o TDD, IMO, têm um grande valor nesse sistema, pois podem ser usados ​​para construí-lo de forma incremental enquanto seu conjunto completo de requisitos ainda está incompleto e garantir que eu não o exagere na execução de coisas que não uso. atualmente não sei que eu preciso. Os horários rígidos eram um pedaço de bolo para o TDD. No entanto, acho difícil definir realmente o que estou testando quando escrevo testes para a parte aleatória do sistema. Posso afirmar que todos os horários produzidos pelo agendador devem estar dentro das restrições, mas eu poderia implementar um algoritmo que passe em todos esses testes sem que os horários reais sejam muito "aleatórios". De fato, foi exatamente isso que aconteceu; Encontrei um problema em que os horários, embora não exatamente previsíveis, se enquadravam em um pequeno subconjunto dos intervalos de data / hora permitidos. O algoritmo ainda passou em todas as afirmações que eu achava que poderia razoavelmente fazer, e não pude projetar um teste automatizado que falharia nessa situação, mas que passou quando obtinha resultados "mais aleatórios". Eu tive que demonstrar que o problema foi resolvido reestruturando alguns testes existentes para repetir-se várias vezes e verificar visualmente se os tempos gerados estavam dentro do intervalo permitido total.

Alguém tem alguma dica para projetar testes que devem esperar um comportamento não determinístico?

Obrigado a todos pelas sugestões. A opinião principal parece ser que eu preciso de um teste determinístico para obter resultados determinísticos, repetíveis e afirmativos . Faz sentido.

Criei um conjunto de testes "sandbox" que contêm algoritmos candidatos para o processo de restrição (o processo pelo qual uma matriz de bytes que pode ter um longo comprimento se torna um longo entre um mínimo e um máximo). Em seguida, executo esse código através de um loop FOR que fornece ao algoritmo várias matrizes de bytes conhecidas (valores de 1 a 10.000.000 apenas para iniciar) e faz com que o algoritmo restrinja cada um a um valor entre 1009 e 7919 (estou usando números primos para garantir uma algoritmo não passaria por algum GCF aleatório entre os intervalos de entrada e saída). Os valores restritos resultantes são contados e um histograma produzido. Para "passar", todas as entradas devem ser refletidas no histograma (sanidade para garantir que não "perdemos" nenhuma), e a diferença entre dois baldes no histograma não pode ser maior que 2 (na verdade deve ser <= 1 , mas fique atento). O algoritmo vencedor, se houver, pode ser cortado e colado diretamente no código de produção e um teste permanente é implementado para a regressão.

Aqui está o código:

    private void TestConstraintAlgorithm(int min, int max, Func<byte[], long, long, long> constraintAlgorithm)
    {
        var histogram = new int[max-min+1];
        for (int i = 1; i <= 10000000; i++)
        {
            //This is the stand-in for the PRNG; produces a known byte array
            var buffer = BitConverter.GetBytes((long)i);

            long result = constraintAlgorithm(buffer, min, max);

            histogram[result - min]++;
        }

        var minCount = -1;
        var maxCount = -1;
        var total = 0;
        for (int i = 0; i < histogram.Length; i++)
        {
            Console.WriteLine("{0}: {1}".FormatWith(i + min, histogram[i]));
            if (minCount == -1 || minCount > histogram[i])
                minCount = histogram[i];
            if (maxCount == -1 || maxCount < histogram[i])
                maxCount = histogram[i];
            total += histogram[i];
        }

        Assert.AreEqual(10000000, total);
        Assert.LessOrEqual(maxCount - minCount, 2);
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionMSBRejection()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByMSBRejection);
    }

    private long ConstrainByMSBRejection(byte[] buffer, long min, long max)
    {
        //Strip the sign bit (if any) off the most significant byte, before converting to long
        buffer[buffer.Length-1] &= 0x7f;
        var orig = BitConverter.ToInt64(buffer, 0);
        var result = orig;
        //Apply a bitmask to the value, removing the MSB on each loop until it falls in the range.
        var mask = long.MaxValue;
        while (result > max - min)
        {
            mask >>= 1;
            result &= mask;
        }
        result += min;

        return result;
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionLSBRejection()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByLSBRejection);
    }

    private long ConstrainByLSBRejection(byte[] buffer, long min, long max)
    {
        //Strip the sign bit (if any) off the most significant byte, before converting to long
        buffer[buffer.Length - 1] &= 0x7f;
        var orig = BitConverter.ToInt64(buffer, 0);
        var result = orig;

        //Bit-shift the number 1 place to the right until it falls within the range
        while (result > max - min)
            result >>= 1;

        result += min;
        return result;
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionModulus()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByModulo);
    }

    private long ConstrainByModulo(byte[] buffer, long min, long max)
    {
        buffer[buffer.Length - 1] &= 0x7f;
        var result = BitConverter.ToInt64(buffer, 0);

        //Modulo divide the value by the range to produce a value that falls within it.
        result %= max - min + 1;

        result += min;
        return result;
    }

... e aqui estão os resultados:

A rejeição de LSB (mudar o número até que ele caia dentro do intervalo) foi TERRÍVEL, por um motivo muito fácil de explicar; quando você divide qualquer número por 2 até que seja menor que o máximo, você sai assim que for, e para qualquer intervalo não trivial, isso influencia os resultados para o terço superior (como foi visto nos resultados detalhados do histograma ) Esse foi exatamente o comportamento que vi nas datas finais; todos os horários eram à tarde, em dias muito específicos.

A rejeição de MSB (remover o bit mais significativo do número um de cada vez até que esteja dentro do intervalo) é melhor, mas novamente, porque você está cortando números muito grandes a cada bit, não é distribuído uniformemente; é improvável que você obtenha números nas extremidades superior e inferior, de modo a obter um viés em direção ao terço médio. Isso pode beneficiar alguém que procura "normalizar" dados aleatórios em uma curva bell-ish, mas uma soma de dois ou mais números aleatórios menores (semelhante a jogar dados) daria a você uma curva mais natural. Para os meus propósitos, falha.

O único que passou neste teste foi restringido pela divisão de módulos, que também se mostrou a mais rápida das três. O módulo, por sua definição, produzirá uma distribuição o mais uniforme possível, considerando os insumos disponíveis.

O que você realmente deseja testar aqui, presumo, é que, dado um conjunto específico de resultados do randomizador, o restante do seu método funcione corretamente.

Se é isso que você está procurando, zombe do randomizador, para torná-lo determinístico dentro dos domínios do teste.

Geralmente, tenho objetos simulados para todos os tipos de dados não determinísticos ou imprevisíveis (no momento da gravação do teste), incluindo geradores GUID e DateTime.Now.

Edit, from comments: Você tem que zombar do PRNG (esse termo me escapou na noite passada) no nível mais baixo possível - ie. quando gera a matriz de bytes, não depois de transformá-los em Int64s. Ou mesmo nos dois níveis, para que você possa testar sua conversão para uma matriz de Int64 conforme o planejado e, em seguida, testar separadamente se a conversão para uma matriz de DateTimes funciona como pretendido. Como Jonathon disse, você pode fazer isso dando uma semente definida ou pode fornecer a matriz de bytes a ser retornada.

Eu prefiro o último porque ele não será quebrado se a implementação da estrutura de um PRNG for alterada. No entanto, uma vantagem de fornecer a semente é que, se você encontrar um caso em produção que não funcionou conforme o esperado, precisará ter registrado um número para poder replicá-lo, em oposição a toda a matriz.

Tudo isso dito, você deve se lembrar de que é chamado de gerador de números pseudo- aleatórios por um motivo. Pode haver algum viés mesmo nesse nível.

Isso vai soar como uma resposta estúpida, mas vou divulgá-la porque é assim que eu já vi isso antes:

Desacoplar seu código do PRNG - passe a semente da randomização para todo o código que usa a randomização. Em seguida, você pode determinar os valores 'funcionais' de uma única semente (ou várias sementes disso o faria se sentir melhor). Isso permitirá que você teste seu código adequadamente, sem ter que confiar na lei de grandes números.

Parece insano, mas é assim que os militares fazem isso (ou usam uma 'mesa aleatória' que não é realmente aleatória)

"É aleatório (o suficiente)" acaba sendo uma pergunta incrivelmente sutil. A resposta curta é que um teste de unidade tradicional simplesmente não funciona - você precisará gerar vários valores aleatórios e enviá-los a vários testes estatísticos que lhe dão uma alta confiança de que são aleatórios o suficiente para suas necessidades.

Haverá um padrão - afinal, estamos usando geradores de números aleatórios psuedo. Mas, em algum momento, as coisas serão "boas o suficiente" para o seu aplicativo (onde suficientemente bom varia MUITO entre os jogos digamos em uma extremidade, onde geradores relativamente simples são suficientes, até a criptografia, na qual você realmente precisa de sequências para ser inviável para determinar por um atacante determinado e bem equipado).

O artigo da Wikipedia http://en.wikipedia.org/wiki/Randomness_tests e seus links de acompanhamento têm mais informações.

Eu tenho duas respostas para você.

=== PRIMEIRA RESPOSTA ===

Assim que vi o título da sua pergunta, vim direto ao assunto e propus a solução. Minha solução foi a mesma que vários outros propuseram: zombar de seu gerador de números aleatórios. Afinal, criei vários programas diferentes que exigiam esse truque para escrever bons testes de unidade e comecei a tornar o acesso simulável a números aleatórios uma prática padrão em toda a minha codificação.

Mas então eu li sua pergunta. E para a questão específica que você descreve, essa não é a resposta. Seu problema não era que você precisava tornar previsível um processo que usasse números aleatórios (portanto, seria testável). Em vez disso, seu problema era verificar se o seu algoritmo mapeou a saída aleatória uniformemente do seu RNG para a saída uniforme dentro das restrições do seu algoritmo - que, se o RNG subjacente fosse uniforme, resultaria em tempos de inspeção distribuídos uniformemente (sujeito à restrições de problemas).

Esse é um problema muito difícil (mas bastante bem definido). O que significa que é um problema INTERESSANTE. Imediatamente comecei a pensar em ótimas idéias de como resolver isso. Quando eu era um programador de sucesso, eu poderia ter começado a fazer algo com essas idéias. Mas não sou mais um programador de ponta ... Gosto disso, sou mais experiente e mais qualificado agora.

Então, em vez de mergulhar no problema difícil, pensei: qual é o valor disso? E a resposta foi decepcionante. Seu bug já foi resolvido e você será diligente sobre esse problema no futuro. As circunstâncias externas não podem desencadear o problema, apenas alterações no seu algoritmo. A ÚNICA razão para enfrentar esse problema interessante foi para satisfazer as práticas do TDD (Test Driven Design). Se há uma coisa que aprendi é que aderir cegamente a qualquer prática quando não é valiosa causa problemas. Minha sugestão é a seguinte: não escreva um teste para isso e siga em frente.

=== SEGUNDA RESPOSTA ===

Uau ... que problema legal!

O que você precisa fazer aqui é escrever um teste que verifique se o seu algoritmo para selecionar datas e horas de inspeção produzirá uma saída uniformemente distribuída (dentro das restrições do problema) se o RNG usado produzir números uniformemente distribuídos. Aqui estão várias abordagens, classificadas por nível de dificuldade.

1. Você pode aplicar força bruta. Basta executar o algoritmo várias vezes, com um RNG real como entrada. Inspecione os resultados da saída para ver se eles estão distribuídos uniformemente. Seu teste precisará falhar se a distribuição variar de perfeitamente uniforme em mais de um determinado ponto de limiar e, para garantir que você encontre problemas, o ponto de limiar não pode ser definido como MUITO baixo. Isso significa que você precisará de um número enorme de execuções para garantir que a probabilidade de um falso positivo (uma falha no teste por acaso) seja muito pequena (bem <1% para uma base de código de tamanho médio; ainda menos para uma grande base de código).

2. Considere o seu algoritmo como uma função que recebe a concatenação de toda a saída RNG como uma entrada e produz tempos de inspeção como uma saída. Se você souber que essa função é contínua por partes, existe uma maneira de testar sua propriedade. Substitua o RNG por um RNG zombável e execute o algoritmo várias vezes, produzindo uma saída RNG uniformemente distribuída. Portanto, se seu código exigisse 2 chamadas RNG, cada uma no intervalo [0..1], o teste poderia ser executado 100 vezes, retornando os valores [(0,0,0.0), (0,0,0,1), (0,0, 0,2), ... (0,0,0,9), (0,1,0,0), (0,1,0,1), ... (0,9,0,9)]. Em seguida, você pode verificar se a saída das 100 execuções foi (aproximadamente) distribuída uniformemente dentro do intervalo permitido.

3. Se você REALMENTE precisar verificar o algoritmo de maneira confiável e não puder fazer suposições sobre o algoritmo OU executar um grande número de vezes, ainda poderá atacar o problema, mas poderá precisar de algumas restrições sobre como programar o algoritmo . Confira o PyPy e sua abordagem do Object Space como um exemplo. Você pode criar um Espaço de Objeto que, em vez de realmente executar o algoritmo, apenas calcule a forma da distribuição de saída (assumindo que a entrada RNG seja uniforme). Obviamente, isso exige que você construa uma ferramenta desse tipo e que seu algoritmo seja construído no PyPy ou em alguma outra ferramenta em que seja fácil fazer modificações drásticas no compilador e usá-lo para analisar o código.

Para os testes de unidade, substitua o gerador aleatório por uma classe que gere resultados previsíveis, cobrindo todos os casos de canto . Ou seja, verifique se o seu pseudo-randomizador gera o menor valor possível e o maior valor possível, e o mesmo resultado várias vezes seguidas.

Você não deseja que seus testes de unidade ignorem, por exemplo, erros que ocorrem um a um quando o Random.nextInt (1000) retornar 0 ou 999.

Você pode dar uma olhada em Sevcikova et al: "Teste automatizado de sistemas estocásticos: uma abordagem estatisticamente fundamentada" ( PDF ).

A metodologia é implementada em vários casos de teste para a plataforma de simulação UrbanSim .

Uma abordagem simples de histograma é um bom primeiro passo, mas não é suficiente para provar a aleatoriedade. Para um PRNG uniforme, você também (pelo menos) geraria um gráfico de dispersão bidimensional (onde x é o valor anterior e y é o novo valor). Esse gráfico também deve ser uniforme. Isso é complicado na sua situação, porque existem não linearidades intencionais no sistema.

Minha abordagem seria:

1. validar (ou considerar que o PRNG de origem é suficientemente aleatório (usando medidas estatísticas padrão)
2. verifique se uma conversão irrestrita de PRNG em data e hora é suficientemente aleatória no espaço de saída (isso verifica uma falta de viés na conversão). Seu teste simples de uniformidade de primeira ordem deve ser suficiente aqui.
3. verifique se os casos restritos são suficientemente uniformes (um teste simples de uniformidade de primeira ordem sobre os compartimentos válidos).

Cada um desses testes é estatístico e requer um grande número de pontos de amostra para evitar falsos positivos e negativos com alto grau de confiança.

Quanto à natureza do algoritmo de conversão / restrição:

Dado: método para gerar valor pseudo-aleatório p onde 0 <= p <= M

Necessidade: saída y na faixa (possivelmente descontínua) 0 <= y <= N <= M

Algoritmo:

1. calcular r = floor(M / N), ou seja, o número de faixas de saída completas que se encaixam na faixa de entrada.
2. calcule o valor máximo aceitável para p :p_max = r * N
3. gerar valores para p até um valor menor do que ou igual a p_maxé encontrado
4. calcular y = p / r
5. se y for aceitável, devolva-o; caso contrário, repita com o passo 3

A chave é descartar valores inaceitáveis ​​em vez de dobrar de maneira não uniforme.

no pseudo-código:

# assume prng generates non-negative values
def randomInRange(min, max, prng):
    range = max - min
    factor = prng.max / range

    do:
        value = prng()
    while value > range * factor
    return (value / factor) + min

def constrainedRandom(constraint, prng):
    do:
        value = randomInRange(constraint.min, constraint.max, prng)
    while not constraint.is_acceptable(value)

Além de validar que seu código não falha, ou lança exceções corretas nos lugares certos, você pode criar pares válidos de entrada / resposta (mesmo calculando isso manualmente), alimentar a entrada no teste e garantir que ela retorne a resposta esperada. Não é ótimo, mas isso é tudo o que você pode fazer, imho. No entanto, no seu caso, não é realmente aleatório. Depois de criar sua programação, você pode testar a conformidade das regras - deve fazer 3 inspeções por semana, entre 9 e 9; não há necessidade ou capacidade real de testar os horários exatos em que a inspeção ocorreu.

Realmente não há maneira melhor do que executá-lo várias vezes e ver se você obtém a distribuição que deseja. Se você tiver 50 programações de inspeção em potencial permitidas, execute o teste 500 vezes e verifique se cada programação é usada perto de 10 vezes. Você pode controlar suas sementes do gerador aleatório para torná-lo mais determinístico, mas isso também tornará seus testes mais fortemente acoplados aos detalhes da implementação.

Não é possível testar uma condição nebulosa que não tem definição concreta. Se as datas geradas passarem em todos os testes, teoricamente, seu aplicativo está funcionando corretamente. O computador não pode dizer se as datas são "aleatórias o suficiente" porque não pode reconhecer os critérios para esse teste. Se todos os testes forem aprovados, mas o comportamento do aplicativo ainda não for adequado, sua cobertura de teste será empiricamente inadequada (da perspectiva do TDD).

Na minha opinião, o melhor é implementar algumas restrições de geração de datas arbitrárias para que a distribuição passe no teste de odor humano.

Basta gravar a saída do seu randomizador (seja pseudo ou quântico / caótico ou do mundo real). Em seguida, salve e reproduza as seqüências "aleatórias" que atendem aos seus requisitos de teste ou que expõem possíveis problemas e bugs, à medida que você cria seus casos de teste de unidade.

Este caso parece ideal para Based Testing propriedade .

Em poucas palavras, é um modo de teste em que a estrutura de teste gera entradas para o código em teste e as asserções de teste validam as propriedades das saídas. A estrutura pode ser inteligente o suficiente para "atacar" o código em teste e tentar encurralá-lo em um erro. A estrutura geralmente também é inteligente o suficiente para seqüestrar sua semente do gerador de números aleatórios. Normalmente, você pode configurar a estrutura para gerar no máximo N casos de teste ou executar no máximo N segundos, e lembre-se dos casos de teste com falha da última execução e execute-os novamente na versão de código mais recente. Isso permite um ciclo rápido de iteração durante o desenvolvimento e um teste lento e abrangente fora da banda / no IC.

Aqui está um exemplo (burro, com falha) testando a sumfunção:

@given(lists(floats()))
def test_sum(alist):
    result = sum(alist)
    assert isinstance(result, float)
    assert result > 0

• estrutura de teste gerará uma lista por vez
• o conteúdo da lista será números de ponto flutuante
• sum é chamado e as propriedades do resultado são validadas
• o resultado é sempre flutuante
• resultado é positivo

Este teste encontrará vários "bugs" em sum(comente se você conseguiu adivinhar tudo isso sozinho):

• sum([]) is 0 (int, não um flutuador)
• sum([-0.9]) é negativo
• sum([0.0]) não é estritamente positivo
• sum([..., nan]) is nan o que não é positivo

Com as configurações padrão, hpythesisinterrompe o teste depois que 1 entrada "ruim" é encontrada, o que é bom para TDD. Eu pensei que era possível configurá-lo para relatar muitas / todas as entradas "ruins", mas não consigo encontrar essas opções agora.

No caso do OP, as propriedades validadas serão mais complexas: tipo de inspeção A presente, tipo de inspeção A três vezes por semana, tempo de inspeção B sempre às 12h, tipo de inspeção C de 9 a 9, [o cronograma determinado é para uma semana] inspeções de tipos A, B, C todos presentes, etc.

A biblioteca mais conhecida é o QuickCheck for Haskell, consulte a página da Wikipedia abaixo para obter uma lista dessas bibliotecas em outros idiomas:

https://en.wikipedia.org/wiki/QuickCheck

A hipótese (para Python) tem uma boa descrição sobre esse tipo de teste:

https://hypothesis.works/articles/what-is-property-based-testing/

o que você pode testar por unidade é a lógica determinar se as datas aleatórias são válidas ou se outra data aleatória precisa ser selecionada.

Não há como testar um gerador de datas aleatórias antes de obter várias datas e decidir se elas são adequadamente aleatórias.

Seu objetivo não é escrever testes de unidade e passá-los, mas garantir que seu programa atenda aos requisitos. A única maneira de fazer isso é definir com precisão seus requisitos em primeiro lugar. Por exemplo, você mencionou "três inspeções semanais em momentos aleatórios". Eu diria que os requisitos são: (a) 3 inspeções (não 2 ou 4), (b) às vezes que não são previsíveis por pessoas que não desejam ser inspecionadas inesperadamente e (c) não estão muito próximas - duas inspeções com cinco minutos de intervalo provavelmente são inúteis, talvez também não muito distantes.

Então você anota os requisitos com mais precisão do que eu. (a) e (c) são fáceis. Para (b), você pode escrever um código o mais inteligente possível, que tente prever a próxima inspeção e, para passar no teste de unidade, esse código não deve ser capaz de prever melhor do que pura adivinhação.

E, é claro, você precisa estar ciente de que, se suas inspeções forem realmente aleatórias, qualquer algoritmo de previsão poderá ser corrigido por puro acaso, portanto, você deve ter certeza de que você e seus testes de unidade não entrarão em pânico se isso acontecer. Talvez faça mais alguns testes. Eu não me incomodaria em testar o gerador de números aleatórios, porque no final é o cronograma de inspeção que conta, e não importa como ele foi criado.