Melhorando Algoritmos de Teste: Abordagens Matemáticas em Teste de Software

Novas metodologias de design de testes nem sempre surgem simultaneamente. Uma parcela significativa das práticas modernas de teste evoluiu através de um trabalho teórico e experimental meticuloso na adaptação de modelos matemáticos. Embora não seja necessário ser um matemático para ser um bom testador, pode ser benéfico compreender a base teórica por trás dos métodos de teste.

Maximizando a cobertura e minimizando o número de casos de teste

A lógica matemática pode ser aplicada para otimizar a cobertura de código de um sistema. Vamos considerar um exemplo simples com uma instrução “if” contendo duas ramificações e uma longa fórmula lógica na condição:

 if ( (& a2) & (!(a2 || a4) ) || a3 ) { # action 1 } else { # action 2 }

Para abranger ambos os ramos, é necessário compreender a estrutura da fórmula. Alguém pode se perguntar: o que pode ser feito? Você sempre pode testar esse trecho de código (fórmula lógica) exaustivamente, resultando em 16 testes. No entanto, isto é bastante e devem ser feitos esforços para reduzir o número de testes. O número de testes pode ser reduzido usando o método Modified Condition/Decision Coverage (MC/DC) (produzindo 11-12 testes). Se a cobertura das filiais for suficiente para testar os riscos, serão necessários apenas dois testes, mas não está claro quais.

Para resolver este problema, a álgebra booleana pode ser aplicada à fórmula lógica:

 if( (& a2) & (! (a2 || a4) ) || a3 ) = = ( (& a2) & ( (!a2 || !a4) ) || a3 ) = = ( a1 & a2 & !a2 & !a4 || a3 ) = = 0 || a3 = a3

Depois de transformar a fórmula original, torna-se aparente que apenas uma variável a3 realmente influencia o valor verdade. Como resultado, a obtenção de casos de teste torna-se mais simples (um com e outro com a3 == false ). Além disso, fica evidente que o código não está otimizado, pois é estranho ter uma expressão lógica complexa dependendo de apenas uma variável. Infelizmente, tais situações são bastante comuns na realidade e o exemplo fornecido é relativamente simples.

Para concluir:

• 2 testes se testes exaustivos forem usados

• 2 testes com o método MC/DC

• 2 testes se a cobertura da agência for aplicada

  
  

Em geral, as expressões lógicas podem ser simplificadas (minimizadas) usando álgebra, métodos matemáticos e algoritmos. Existem pelo menos três métodos semelhantes. As transformações diretas usando álgebra booleana, conforme explicado acima, sempre funcionam. Métodos de minimização de expressões que consideram as características específicas do domínio, contando não apenas com matemática e lógica, mas também com as peculiaridades do domínio, podem ser encontrados e aplicados.

Otimizando Testes Pareados

O método de teste pareado envolve a geração de conjuntos de testes de tal forma que, em vez de testar todas as combinações possíveis de parâmetros de entrada por meio de testes exaustivos (que podem consumir muito tempo e recursos), os conjuntos de testes são projetados para que cada valor de parâmetro se combine com cada valor de parâmetro. valor dos outros parâmetros testados pelo menos uma vez. Isso reduz significativamente o número de casos de teste.

É um método bem estabelecido e frequentemente utilizado. Contudo, infelizmente, este método nem sempre funciona à medida que os sistemas se tornam mais complexos. Surge a questão: o teste em pares é suficiente para testar completamente um sistema complexo com numerosos parâmetros de entrada? Esta questão intrigou muitos profissionais e pesquisadores de testes, incluindo o Instituto Nacional de Padrões e Tecnologia (NIST) dos Estados Unidos.

• Pairwise finds 65-97% of errors
• 3-way finds 89-99% of errors
• 4-way finds 96-100% of errors
• 5-way finds 96-100% of errors
• 6-way finds 100% of errors

De acordo com estudos, o teste pareado encontra erros em 65-97% dos casos. Se começarmos a combinar não pares de parâmetros, mas triplos ou quádruplos, ou seja, usando testes k-way, obteremos um maior número de testes, mas também detectaremos mais erros.

Por exemplo, suponha que um sistema tenha dois parâmetros com três valores cada e três parâmetros com dois valores cada:

• Pairwise: 10 tests with 14% coverage
• 3-way: 18 tests with 25% coverage
• 4-way: 36 tests with 50% coverage
• 5-way: 72 tests with 100% coverage

Você pode escolher um nível satisfatório de cobertura de teste e um número aceitável de casos de teste.

A base para pares são matrizes ortogonais contendo n-tuplas (pares, triplos, quádruplos, ...) de valores um número igual de vezes.

A base usual para testes pareados e k-way é OA(N, V^k, t) , onde:

• N é o número de linhas

• k é o número de colunas

• V é o número de valores diferentes em uma coluna

• t é a força (t = 2 para pares)

  
  

No OA, cada conjunto de t colunas inclui todas as t tuplas um número igual de vezes.

Em vez de matrizes ortogonais, é melhor usar matrizes de cobertura. Essas matrizes diferem das ortogonais porque cada conjunto de valores ocorre pelo menos uma vez, e não “um número igual de vezes”. Neste caso, há um pouco menos testes. Podem surgir casos de teste incorretos com matrizes de cobertura, mas no geral, o processo de teste é muito mais rápido. Assim, o processo de teste é significativamente simplificado.

CA(N, V^k, t), onde:

• N é o número de linhas
• k é o número de colunas
• V é o número de valores diferentes em uma coluna
• t é a força (t = 2 para pares)

No CA, cada conjunto de t colunas inclui todas as t tuplas pelo menos uma vez. O uso de matrizes de cobertura permite passar de testes pareados para testes k-way sem aumentar significativamente o número de testes.

Estados do sistema e testes de alteração dos estados do sistema

Normalmente (quase sempre), um sistema tem mais de dois estados: “funcionando” e “não funcionando”. Vamos considerar uma parte dos estados que possuem pedido de estoque. Uma ordem de compra ou venda de ações deve passar por uma série de estados para que a transação seja concluída. Primeiro, o pedido é criado, depois confirmado pela bolsa, seguido por inúmeras pequenas transações de compra e, finalmente, a quantidade necessária de ações é comprada ou vendida. Todos os estados de uma ordem de ações são refletidos nos sistemas de negociação e todas as transições e estados devem ser testados, é claro.

Quase sempre, todos os estados ou todas as transições são testados, mas na maioria das vezes ambos são verificados. A cobertura total é alcançável, mas será demorada, cara e consumirá muitos recursos.

Gráficos e autômatos finitos

Vamos considerar o problema do caixeiro viajante (commi voyager) e o algoritmo de Bruijn. Basta entender que o algoritmo permite obter um conjunto ótimo ou suficientemente ótimo de caminhos curtos que podem ser percorridos em um grafo para cobri-lo completamente (a rigor, qualquer outro algoritmo que realize algo semelhante pode ser usado, ou pode-se inventar um algoritmo personalizado).

• Primeiro, pegue os estados iniciais do sistema e construa um novo grafo onde os vértices correspondem às transições no grafo original.
• A seguir, cubra os vértices do novo gráfico, ou seja, as transições do antigo.
• Alguns caminhos são óbvios e acabam sendo bastante curtos (o que é muito conveniente para testar estados e transições do sistema).
• Continue construindo outros caminhos. Como resultado, eles podem ficar muito longos (e isso não é bom).

Vamos considerar o seguinte exemplo para analisar a situação:

Existem três testadores. O primeiro realizará o primeiro teste, o segundo – o segundo teste, o terceiro – o terceiro teste. Os dois primeiros completarão os dois primeiros testes bastante rapidamente porque os caminhos são curtos (em comparação com o terceiro, pois os dois primeiros caminhos são curtos), mas o último demorará muito tempo (já que o terceiro caminho é muito longo).

Se o algoritmo de Bruijn for aplicado, a terceira sequência pode ser "cortada" em várias sequências mais curtas, e a execução de todos os testes pode ser paralelizada de forma eficiente.

Podemos acabar com mais testes, mas no caso de execução paralela, os testes terminarão muito mais rápido porque os testes são mais curtos.

Além disso, com mais testes, há mais flexibilidade na sua execução. Todos os testes podem ser executados simultaneamente ou testes desinteressantes e menos importantes podem ser removidos. Prioridades mais altas podem ser atribuídas a testes que passam pelos estados mais importantes do sistema. Existem muitas maneiras de aproveitar os resultados do algoritmo.

Além disso, o algoritmo não usa recursos específicos do domínio; funciona com estados e transições absolutamente abstratos do sistema.

Nesta técnica, muito depende de como o algoritmo é usado. No caso mais extremo, os testadores podem não saber nada sobre a lógica por trás das transições entre estados. Em tal situação, a longa cadeia de transições de estado será “cortada” pelo algoritmo em várias transições curtas. Algumas dessas cadeias podem revelar-se sem sentido. Portanto, as cadeias obtidas precisam ser avaliadas quanto à razoabilidade e aquelas que são importantes e significativas para teste. Sem sentido e sem importância, mas caminhos possíveis para alterar os estados do sistema podem fornecer uma compreensão de qual parte do sistema precisa de modificação, e será evidente qual parte exatamente.

As principais conclusões podem ser consideradas da seguinte forma:

• Algoritmos para minimizar expressões lógicas fornecem cobertura máxima de teste com esforço mínimo. Nem sempre é necessário utilizar algoritmos de minimização – às vezes é uma perda de tempo; existem abordagens universais.
• A cobertura completa dos testes pode ser alcançada com um pequeno conjunto de casos de teste curtos que são fáceis de paralelizar, automatizar, flexíveis e independentes.
• A análise das estatísticas de utilização da aplicação em condições reais permite otimizar e adaptar as técnicas de desenho de testes existentes e alcançar a cobertura de teste necessária, garantindo a qualidade da aplicação.
• A modificação dos testes pareados permite testes mais profundos com maior cobertura de teste do que algoritmos padrão e com quase os mesmos recursos.
• Alguns algoritmos podem ser eficazes nos casos em que as técnicas padrão de design de testes são menos eficientes.
• Existem alguns desafios nas falhas das técnicas de design de testes combinatórios .
• Os algoritmos obtidos podem ser facilmente adaptados a diferentes sistemas e não requerem conhecimentos especiais do domínio.

Quanto às pequenas desvantagens, vale a pena notar:

• Alguns algoritmos não são eficazes e relevantes para todos os casos; em muitas situações, as técnicas padrão de design de testes são igualmente ou às vezes até mais eficazes.
• A aplicação de algoritmos requer algum conhecimento matemático e por vezes mais tempo para a sua aplicação, pelo que também pode tornar-se um factor vital em muitas situações.