¿Cuáles son las mejores prácticas para probar programas con comportamiento estocástico?

14

Haciendo trabajo de I + D, a menudo me encuentro escribiendo programas que tienen un alto grado de aleatoriedad en su comportamiento. Por ejemplo, cuando trabajo en programación genética, a menudo escribo programas que generan y ejecutan código fuente aleatorio arbitrario.

Un problema al probar dicho código es que los errores a menudo son intermitentes y pueden ser muy difíciles de reproducir. Esto va más allá de simplemente establecer una semilla aleatoria en el mismo valor y comenzar de nuevo la ejecución.

Por ejemplo, el código puede leer un mensaje del búfer de anillo kernal y luego realizar saltos condicionales en el contenido del mensaje. Naturalmente, el estado del búfer en anillo habrá cambiado cuando uno más tarde intente reproducir el problema.

Aunque este comportamiento es una característica , puede desencadenar otro código de maneras inesperadas y, por lo tanto, a menudo revela errores que las pruebas unitarias (o probadores humanos) no encuentran.

¿Existen mejores prácticas establecidas para probar sistemas de este tipo? Si es así, algunas referencias serían muy útiles. Si no, cualquier otra sugerencia es bienvenida.

John Doucette
fuente
55
¿No puedes burlarte del búfer del anillo del núcleo también? ¿Y otros aspectos aleatorios de tu código?
Jonathan Merlet
1
@JonathanMerlet Potencialmente, pero el problema es que, cuando se implementa, el código tendrá acceso al búfer de anillo real (de hecho, a un sistema operativo real). Entonces, si solo pruebo una versión simulada, entonces solo aplazaré el descubrimiento de estos errores hasta más tarde.
John Doucette
Me parece que el problema no está relacionado con el comportamiento aleatorio del programa (ya que esto puede ser controlado por la semilla aleatoria) sino con estados particulares de este 'buffer de anillo de núcleo'. Entonces su pregunta es en realidad '¿cómo pruebo un programa que depende del estado externo', ¿verdad?
AakashM
@AakashM, sí, esa es una mejor manera de expresarlo. Para ser más específico, un programa con un estado externo, que accede estocásticamente o altera el estado externo.
John Doucette el

Respuestas:

7

Es útil agregar ganchos, como se sugiere, para recrear estados exactos. También instrumente el sistema para que pueda volcar sus "semillas" (en su caso, incluida la semilla PRNG, así como el búfer del anillo del núcleo y cualquier otra fuente de entrada no determinista).

Luego ejecute sus pruebas con entrada aleatoria verdadera y estilo de regresión con cualquier caso interesante previamente descubierto.

En el caso particular de su acceso al kernel, recomendaría hacer un simulacro en cualquier caso. Use el simulacro para forzar las clases de equivalencia que tienen menos probabilidades de aparecer en la práctica, en el espíritu de "vacío" y "lleno" para contenedores, o "0, 1, 2 ^ n, 2 ^ n + 1, muchos" para cosas contables Luego puedes probar con el simulacro y con la realidad, sabiendo que has manejado y probado los casos que has pensado hasta ahora.

Básicamente, lo que estoy sugiriendo equivale a una mezcla de entradas deterministas y no deterministas, siendo las deterministas una mezcla de las que puede pensar y las que le sorprendieron.

Stephan A. Terre
fuente
6

Una cosa razonable para hacer es sembrar el generador de números aleatorios con un valor constante para las pruebas, de modo que obtenga un comportamiento determinista.

Dima
fuente
1
esta; o burlarse del prng completamente
jk.
1
¡Gracias por la sugerencia! Ya hago esto para las pruebas unitarias, pero no puedo probar todos los programas posibles a mano.
John Doucette
2
pero esto significa que no puede probar si la aleatoriedad funciona correctamente ..
Louis Rhys
2

Creo que las pruebas estadísticas son la única forma. Al igual que los números aleatorios son "probados" para determinar su aleatoriedad mediante pruebas estadísticas, también deben ser algoritmos que utilicen el comportamiento aleatorio.

Simplemente ejecute el algoritmo varias veces con entrada igual o diferente y compárelo entre sí. El problema con este enfoque es el aumento masivo en el tiempo computacional requerido para finalizar la prueba.

Eufórico
fuente
No necesariamente, porque puede elegir un pequeño conjunto de entradas "abarcadoras" y ejecutarlas varias veces, el número de entradas necesarias para determinar la confiabilidad puede ser menor. Este conjunto de "expansión" debe ingresar a cada rama del código, inicializar todos los objetos, etc.
Daniel Moskovich
2

No soy un especialista en este dominio, pero hay una literatura científica relativa a las pruebas de programas estocásticos.

Si no puede crear fácilmente clases de prueba, se puede usar una prueba estadística, como dijo #Euphoric. Borning y col. compare un enfoque tradicional y uno estadístico. Una generalización de las pruebas estadísticas sugeridas por @Euphoric podría ser la discutida por Whittaker. Sugirió crear un modelo estocástico del comportamiento deseado (estocástico, en su caso) y luego generar casos de prueba específicos a partir de este modelo (consulte su documento dedicado ).

mgoeminne
fuente
¡Gracias! Se ve muy útil. Para aquellos que se encuentran fuera de las instituciones académicas, se puede obtener una versión preimpresa del documento del repositorio de código de Google del autor aquí: team4model.googlecode.com/svn/trunk/resources/paper/…
John Doucette