Mejora de los algoritmos de prueba: enfoques matemáticos en las pruebas de software

Nuevas metodologías de diseño de pruebas no siempre surgen simultáneamente. Una parte importante de las prácticas de evaluación modernas ha evolucionado a través de un meticuloso trabajo teórico y experimental en la adaptación de modelos matemáticos. Aunque no es necesario ser matemático para ser un buen evaluador, puede resultar beneficioso comprender los fundamentos teóricos detrás de los métodos de prueba.

Maximizar la cobertura y minimizar el número de casos de prueba

Se puede aplicar la lógica matemática para optimizar la cobertura del código de un sistema. Consideremos un ejemplo simple con una declaración "si" que contiene dos ramas y una fórmula lógica larga en la condición:

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

Para cubrir ambas ramas, es necesario comprender la estructura de la fórmula. Cabría preguntarse ¿qué se puede hacer? Siempre puedes probar este fragmento de código (fórmula lógica) de forma exhaustiva, lo que da como resultado 16 pruebas. Sin embargo, esto es bastante y se deben hacer esfuerzos para reducir el número de pruebas. El número de pruebas se puede reducir utilizando el método de condición modificada/cobertura de decisión (MC/DC) (que produce entre 11 y 12 pruebas). Si la cobertura de sucursales es suficiente para probar los riesgos, sólo se necesitan dos pruebas, pero no está claro cuáles.

Para resolver este problema, se puede aplicar el álgebra booleana a la fórmula lógica:

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

Después de transformar la fórmula original, resulta evidente que sólo una variable a3 influye realmente en el valor de verdad. Como resultado, obtener casos de prueba se vuelve más simple (uno con y el otro con a3 == false ). Además, resulta evidente que el código no está optimizado, ya que es extraño tener una expresión lógica compleja que dependa de una sola variable. Desafortunadamente, estas situaciones son bastante comunes en la realidad y el ejemplo proporcionado es relativamente sencillo.

En conclusión:

• 2 pruebas si se utilizan pruebas exhaustivas

• 2 pruebas con el método MC/DC

• 2 pruebas si se aplica cobertura de sucursal

  
  

En general, las expresiones lógicas se pueden simplificar (minimizar) utilizando álgebra, métodos matemáticos y algoritmos. Existen al menos tres métodos similares. Las transformaciones directas que utilizan álgebra booleana, como se explicó anteriormente, siempre funcionan. Se pueden encontrar y aplicar métodos de minimización de expresiones que consideren las características del dominio específico basándose no sólo en las matemáticas y la lógica sino también en las peculiaridades del dominio.

Optimización de las pruebas por pares

El método de prueba por pares implica generar conjuntos de pruebas de tal manera que, en lugar de probar todas las combinaciones posibles de parámetros de entrada mediante pruebas exhaustivas (que pueden consumir mucho tiempo y recursos), los conjuntos de pruebas se diseñan de manera que cada valor de parámetro se combine con cada valor de parámetro. valor de los otros parámetros probados al menos una vez. Esto reduce significativamente la cantidad de casos de prueba.

Es un método bien establecido y de uso frecuente. Sin embargo, lamentablemente este método no siempre funciona a medida que los sistemas se vuelven más complejos. Surge la pregunta: ¿son suficientes las pruebas por pares para probar exhaustivamente un sistema complejo con numerosos parámetros de entrada? Esta pregunta ha intrigado a muchos investigadores y profesionales de las pruebas, incluido el Instituto Nacional de Estándares y Tecnología (NIST) de 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

Según los estudios, las pruebas por pares encuentran errores en el 65-97% de los casos. Si empezamos a combinar no pares de parámetros sino triples o cuádruples, es decir, usando pruebas de k-way, obtenemos un mayor número de pruebas pero también detectamos más errores.

Por ejemplo, supongamos que un sistema tiene dos parámetros con tres valores cada uno y tres parámetros con dos valores cada uno:

• 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

Puede elegir un nivel satisfactorio de cobertura de prueba y un número aceptable de casos de prueba.

La base del método por pares son las matrices ortogonales que contienen n-tuplas (pares, triples, cuádruples, ...) de valores el mismo número de veces.

La base habitual para las pruebas por pares y de k vías es OA(N, V^k, t) , donde:

• N es el número de filas

• k es el número de columnas

• V es el número de valores diferentes en una columna.

• t es la fuerza (t=2 por pares)

  
  

En OA, cada conjunto de t columnas incluye todas las t tuplas un número igual de veces.

En lugar de matrices ortogonales, es mejor utilizar matrices de cobertura. Estas matrices se diferencian de las ortogonales en que cada conjunto de valores aparece al menos una vez, no "un número igual de veces". En este caso, hay un poco menos de pruebas. Pueden surgir casos de prueba incorrectos con las matrices de cobertura, pero en general, el proceso de prueba es mucho más rápido. De este modo, el proceso de prueba se simplifica significativamente.

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

• N es el número de filas
• k es el número de columnas
• V es el número de valores diferentes en una columna.
• t es la fuerza (t=2 por pares)

En CA, cada conjunto de t columnas incluye todas las t tuplas al menos una vez. El uso de matrices de cobertura permite pasar de pruebas por pares a pruebas de k vías sin aumentar significativamente el número de pruebas.

Estados del sistema y pruebas de estados cambiantes del sistema

Por lo general (casi siempre), un sistema tiene más de dos estados: "funcionando" y "no funcionando". Consideremos una parte de los estados que tienen un pedido de acciones. Una orden de compra o venta de acciones debe pasar por una serie de estados para que se complete la transacción. Primero se crea la orden, luego la bolsa la confirma, luego numerosas transacciones de compra pequeñas y, finalmente, se compra o vende la cantidad necesaria de acciones. Todos los estados de una orden bursátil se reflejan en los sistemas de negociación y, por supuesto, todas las transiciones y estados deben comprobarse.

Casi siempre se prueban todos los estados o todas las transiciones, pero la mayoría de las veces se verifican ambos. Es posible lograr una cobertura total, pero requerirá mucho tiempo, dinero y recursos.

Gráficos y autómatas finitos

Consideremos el problema del viajante (commi voyager) y el algoritmo de De Bruijn. Basta entender que el algoritmo permite obtener un conjunto óptimo o suficientemente óptimo de caminos cortos que pueden ser recorridos en un grafo para cubrirlo por completo (estrictamente hablando, se puede usar cualquier otro algoritmo que logre algo similar, o se puede inventar un algoritmo personalizado).

• Primero, tome los estados iniciales del sistema y construya un nuevo gráfico donde los vértices correspondan a las transiciones en el gráfico original.
• A continuación, cubra los vértices del nuevo gráfico, es decir, las transiciones en el antiguo.
• Algunos caminos son obvios y resultan bastante cortos (lo cual es muy conveniente para probar estados y transiciones del sistema).
• Continuar construyendo otros caminos. Como resultado, pueden volverse demasiado largos (y eso no es bueno).

Consideremos el siguiente ejemplo para analizar la situación:

Hay tres probadores. El primero realizará la primera prueba, el segundo la segunda prueba, el tercero la tercera prueba. Los dos primeros completarán las dos primeras pruebas bastante rápido porque los caminos son cortos (en comparación con el tercero, ya que los dos primeros caminos son cortos), pero el último llevará mucho tiempo (ya que el tercer camino es muy largo).

Si se aplica el algoritmo de Bruijn, la tercera secuencia se puede "cortar" en varias secuencias más cortas y la ejecución de todas las pruebas se puede paralelizar de manera eficiente.

Podemos terminar con más pruebas, pero en el caso de la ejecución paralela, las pruebas finalizarán mucho más rápido porque las pruebas son más cortas.

Además, cuanto más pruebas, hay más flexibilidad en su ejecución. Todas las pruebas se pueden ejecutar simultáneamente o se pueden eliminar las pruebas menos interesantes y menos importantes. Se pueden asignar prioridades más altas a las pruebas que pasan por los estados más importantes del sistema. Hay muchas formas de aprovechar los resultados del algoritmo.

Como ventaja, el algoritmo no utiliza elementos específicos del dominio; Trabaja con estados y transiciones absolutamente abstractos del sistema.

En esta técnica, mucho depende de cómo se utilice el algoritmo. En el caso más extremo, es posible que los evaluadores no sepan nada sobre la lógica detrás de las transiciones entre estados. En tal situación, el algoritmo "cortará" la larga cadena de transiciones de estado en varias cortas. Algunas de estas cadenas pueden resultar carentes de sentido. Por lo tanto, es necesario evaluar la razonabilidad de las cadenas obtenidas y aquellas que son importantes y significativas para las pruebas. Los caminos posibles, sin sentido y sin importancia, para cambiar los estados del sistema pueden proporcionar una comprensión de qué parte del sistema necesita modificación, y será evidente qué parte exactamente.

Las conclusiones clave se pueden considerar de la siguiente manera:

• Los algoritmos para minimizar expresiones lógicas brindan la máxima cobertura de prueba con el mínimo esfuerzo. No siempre es necesario utilizar algoritmos de minimización; a veces es una pérdida de tiempo; existen enfoques universales.
• Se podría lograr una cobertura de prueba completa con un pequeño conjunto de casos de prueba breves que sean fáciles de paralelizar, automatizar, flexibles e independientes.
• El análisis de estadísticas sobre el uso de aplicaciones en condiciones reales permite optimizar y adaptar las técnicas de diseño de pruebas existentes y lograr la cobertura de prueba necesaria, garantizando la calidad de la aplicación.
• La modificación de las pruebas por pares permite realizar pruebas más profundas con una mayor cobertura de prueba que los algoritmos estándar y con casi los mismos recursos.
• Algunos algoritmos pueden resultar eficaces en los casos en que las técnicas de diseño de pruebas estándar sean menos eficientes.
• Existen algunos desafíos en los fallos de las técnicas de diseño de pruebas combinatorias .
• Los algoritmos obtenidos se pueden adaptar fácilmente a diferentes sistemas y no requieren conocimientos especiales del dominio.

En cuanto a los inconvenientes menores, cabe destacar:

• Algunos algoritmos no son eficaces y relevantes para todos los casos; En muchas situaciones, las técnicas de diseño de pruebas estándar son igual o, a veces, incluso más efectivas.
• La aplicación de algoritmos requiere ciertos conocimientos matemáticos y en ocasiones más tiempo para su aplicación por lo que también puede convertirse en un factor vital en muchas situaciones.