Los reductores de casos de prueba son una herramienta de depuración subestimada

• Al buscar qué parte causa un problema en una entrada grande, un reductor de casos de prueba reduce automáticamente la entrada y facilita la depuración
• El reductor toma un programa, una entrada y una prueba de interés, y verifica repetidamente si entradas candidatas más cortas reproducen el mismo problema
• Incluso un reductor simple que elimina líneas puede dejar una sola palabra larga de /usr/share/dict/words, y en un ejemplo en C reduce 78 líneas a 54 en menos de 10 segundos
• La prueba de interés debe escribirse con precisión y rapidez por problemas de reducción excesiva, ejecución lenta, ejecuciones infinitas y entornos de ejecución en paralelo
• Si además de la longitud de la entrada se incluyen en la prueba de interés métricas como la frecuencia del error o la longitud del rastro de ejecución, puede ayudar a depurar bugs no deterministas y registros de trazas grandes

---

Reducción de casos de prueba

• Cuando un programa falla con una entrada grande y no se sabe qué parte de la entrada lo provoca, reducir la entrada facilita identificar la causa
• La reducción manual consiste en borrar parte de la entrada en un editor de texto y comprobar si el mismo fallo se mantiene
• En la reducción manual, es fácil que una persona pase por alto muchas oportunidades de borrar contenido, y tras borrar algo el programa puede terminar normalmente o producir otro error normal distinto
• Si solo funciona borrar juntas dos partes separadas, A y B, el espacio de búsqueda crece mucho

Estructura básica de un reductor de casos de prueba

• Un reductor de casos de prueba es una herramienta que toma un programa, una entrada y una prueba de interés para acortar la entrada
• La prueba de interés devuelve 0 si la entrada reducida reproduce el error de interés, y un valor distinto de 0 si no lo hace
• En reductores de casos de prueba, una reducción del 95 al 99% es común y puede hacer la depuración mucho más sencilla
• El reductor funciona aunque no entienda semánticamente qué partes de la entrada debe eliminar

• Ejemplo de un reductor simple

  • El programa de ejemplo lee líneas de un archivo y, si alguna tiene longitud mayor que 25, imprime Word too long
  • La prueba de interés devuelve 0 si la salida del programa contiene Word too long, y 1 si no
  • Un reductor simple en Python lee la entrada línea por línea, escribe en un archivo temporal una entrada candidata con una línea eliminada y luego ejecuta la prueba de interés
  • Si la entrada candidata es interesante, reemplaza la entrada actual por esa candidata y, cuando ya no puede reducir más, imprime el resultado en stdout
  • Al ejecutarlo con /usr/share/dict/words, deja solo antidisestablishmentarianism

Reductores más potentes y Shrink Ray

• El ejemplo del programa en C de 78 líneas trata un problema donde las configuraciones FAST=0 y FAST=1 producen salidas distintas
• La prueba de interés solo pasa si, tras compilar con ambas configuraciones, la salida de FAST=0 es 0d754a56 y la salida de FAST=1 es distinta de ese valor
• El reductor simple puede reducir la entrada en C de 78 líneas a 54 en menos de 10 segundos, lo que equivale a una reducción de alrededor del 30% por número de líneas
• Si se añade i=0 para volver a borrar desde la primera línea cada vez que se encuentra una candidata interesante, el tiempo de ejecución aumenta casi 10 veces y se eliminan 3 líneas más
• Shrink Ray ofrece varias reglas de reducción y ejecución en paralelo, y con --no-clang-delta no usa conocimiento especial sobre C
• Después de unos 15 minutos, Shrink Ray redujo la entrada en más del 60% por bytes, y en otro caso encontró una reducción del 90% tras unos 20 minutos y luego la llevó hasta el 99%
• Shrink Ray conoce la sintaxis estándar de comentarios e intenta eliminarlos al principio, y también prueba reducir enteros a valores más pequeños

La dificultad de escribir una prueba de interés

• Los reductores de casos de prueba siguen literalmente la prueba de interés, así que si la prueba pasa por error puede producirse una reducción excesiva, donde la entrada se reduce más de lo deseado
• Shrink Ray comprueba explícitamente si la prueba de interés acepta una entrada vacía, y esta situación puede ocurrir con frecuencia
• En el ejemplo en C, si solo se comprueba que las dos salidas sean distintas, diferencias irrelevantes o engañosas podrían clasificarse como entradas interesantes
• La comprobación test "$slow_out" = "0d754a56" verifica que la versión lenta realmente haga lo esperado y reduce la posibilidad de reducción excesiva

• Velocidad y timeouts

  • Si la prueba de interés es rápida, el reductor puede ejecutarla cientos de veces por segundo
  • Incluso ejemplos de tamaño medio pueden llevar a cientos de miles de intentos de reducción, así que optimizar la prueba de interés influye mucho en el tiempo total
  • Hubo un caso en que desactivar la generación automática de core dumps hizo la prueba de interés unas 3 veces más rápida
  • El reductor puede eliminar una línea como i-=1 y convertir un programa que termina en uno que se ejecuta indefinidamente
  • Si el programa tarda 0.1 segundos y se fija un timeout de 60 segundos, toda la reducción se vuelve mucho más lenta
  • En programas rápidos se suele redondear timeout a 1 o 2 segundos, y en otros casos se usa alrededor de 1.5 a 2 veces el tiempo de ejecución inicial

• Ejecución en paralelo

  • Reductores como Shrink Ray ejecutan la prueba de interés en paralelo
  • Shrink Ray ejecuta cada prueba de interés en un directorio temporal y limpia ese directorio automáticamente
  • A veces un directorio temporal no basta, y las medidas necesarias cambian según el caso

Forzar determinismo con la prueba de interés

• El fragmento de ejemplo provoca un error de división por cero por len([])==0, pero por la condición random.random() < 0.33 el problema solo aparece en aproximadamente un tercio de las ejecuciones
• Los bugs no deterministas aparecen y desaparecen al azar, lo que vuelve más difícil y más lenta la validación de hipótesis
• Si el reductor elimina la llamada a random.random() o cambia la condición, un error no determinista puede volverse determinista
• En la práctica, la no determinación suele venir de la interacción desfavorable entre varias partes de la entrada, por lo que puede ser difícil eliminarla
• Un reductor de casos de prueba funciona como un algoritmo de ascenso de colina que usa la longitud de la entrada como métrica sustituta de “mejor”
• Este enfoque de ascenso de colina se atasca fácilmente en óptimos locales, y una entrada más corta no siempre es mejor para investigar un error

• Método de ejecución repetida

  • Para manejar bugs no deterministas, se usa una prueba de interés que ejecuta la entrada varias veces y la acepta si el error de interés ocurre al menos una vez
  • Este método puede ayudar a aumentar la frecuencia con que aparece el error
  • Una prueba que pasa si ocurre al menos una vez también acepta entradas no deterministas, así que durante la reducción la no determinación incluso puede aumentar
  • Un método más estricto es una prueba que solo acepta la entrada si el error ocurre en las n repeticiones
  • Con una prueba estricta, la probabilidad de que la entrada inicial pase puede ser baja y dificultar iniciar Shrink Ray; en el ejemplo de 3 repeticiones, la probabilidad inicial de pasar es 3.6%
  • Una solución práctica es empezar con una prueba de “al menos un error en n ejecuciones” y, una vez obtenida una entrada reducida donde el error ocurre con más frecuencia, cambiar a una prueba de “error en n ejecuciones consecutivas”

Contadores globales y otras métricas objetivo

• La intervención manual es poderosa, pero obliga a vigilar Shrink Ray y es fácil perder el momento adecuado para intervenir
• Si se quiere guiar al reductor por una propiedad distinta de la longitud de la entrada, esa propiedad puede imponerse dentro de una sola prueba de interés
• En la depuración de yk, más que la longitud de la entrada importa la longitud del rastro de ejecución, es decir, un valor cercano al número de instrucciones ejecutadas por el programa
• La salida YKD_LOG="$t:jit-asm" escribe en un archivo el rastro IR en texto y las instrucciones en lenguaje máquina, y una salida jit-asm corta facilita la depuración
• wc -l cuenta las líneas del archivo de log y se usa como métrica sustituta aproximada de la longitud del rastro
• La prueba de interés trata la entrada como no interesante si el número actual de líneas del rastro es mayor que el mejor mínimo anterior, y ese mínimo se guarda en /tmp/global_best
• Este enfoque no es seguro en reducción paralela e incluye supuestos sobre cómo se invoca al reductor, pero para un script desechable se considera una imperfección aceptable
• En un caso de segfault de yk, la reducción normal dejó un rastro de 40K líneas, pero esta técnica produjo un rastro de 10.1K líneas en vez de una entrada reducida más grande, y permitió identificar el bug raíz en 30 minutos

Resumen clave

• Los reductores de casos de prueba no son útiles solo para autores de compiladores; también pueden usarse en problemas que no son de compiladores
• Además del objetivo básico de reducir la longitud de la entrada, la prueba de interés puede guiar propiedades como la frecuencia del error, el tiempo real transcurrido, el nivel de no determinación y la longitud del rastro
• La precisión de la prueba de interés, su velocidad de ejecución, los timeouts y la seguridad en ejecución paralela determinan el efecto real del reductor
• Aunque el reductor apenas entienda la semántica de la entrada y del programa, puede conservar el problema en una forma más pequeña y aumentar la productividad al depurar

[GN⁺]

Comentarios en Lobste.rs

• La verdad me pregunto si hay alguien que no reconozca el valor de la reducción automática de casos de prueba. La palabra “subestimada” suena como si hubiera gente que no quisiera reducción de casos de prueba siempre.
  Incluso si puedes identificar el bug de inmediato, ¿no necesitas un caso reducido para una prueba de regresión?

  • Supongo que la mayoría de los desarrolladores ni siquiera lo habrá pensado como una técnica
  • La primera línea del artículo dice “Test-case reducers are less well known than they should be, [...]”, y justo esa fue mi impresión, incluso después de años recomendando a la gente usar fuzzing y pruebas basadas en propiedades.
    Ambos suelen incluir alguna forma de reducción de casos fallidos o “shrinking”, y eso los hace mucho más prácticos
  • Más o menos lo conozco por los fuzzers. Después de que el fuzzer encuentra un caso fallido, lo reduce automáticamente, y esa parte funciona muy bien.
    Pero, por mi experiencia usando AmericanFuzzyLop y AFL++ en general, la configuración es tan dolorosa que normalmente prefiero evitarlo.
    Además, la mayoría de los bugs con los que me topo no son del tipo “si metes este archivo de entrada falla”, sino más bien “le falla a algún usuario, en alguna parte”. A veces sí se puede reducir a “si sigues una serie de pasos bajo ciertas condiciones falla”, pero 1) no tengo claro cómo aplicar un reductor automático de casos de prueba a “un usuario haciendo cosas en secuencia”, y 2) una vez que encuentras cómo reproducirlo localmente, el 99% de la depuración ya está hecho.
    Supongo que el autor llamaría “subestimada” a esta actitud mía
  • Me parece que ya de por sí son pocos los que saben qué es la reducción de casos de prueba

• Aunque este artículo y sus ejemplos dicen que los reductores deberían usarse más también fuera de situaciones de compiladores, la perspectiva sigue bastante cargada hacia la de alguien que escribe compiladores.
  Como escribió ~silentbicycle, la mayoría de la reducción de casos de prueba ocurre en el contexto de fuzzers o pruebas basadas en propiedades, donde la reducción ya viene integrada en un framework más grande. Los compiladores son una de las áreas inusuales donde un reductor independiente sí resulta útil. No estoy seguro de en qué otros casos ayudaría un reductor independiente.
  La parte de la determinación también es interesante. El ejemplo empieza con el caso de un archivo de entrada que dispara un bug, es decir, la determinación viene del script, no de una propiedad del propio intérprete con el bug. No queda claro si el artículo quiere decir que la técnica de “interestingness” también funciona en contextos no relacionados con compiladores donde el programa con el bug en sí es no determinista.
  Como forma de adaptar un problema de prueba al fuzzing y a la reducción de casos de prueba, recomiendo crear un conjunto numerado de comandos imperativos. Cada comando puede incluir una verificación ligera de consistencia que detecte fallas en la prueba, incluso cuando no haya un crash inmediato. Las verificaciones pesadas de consistencia conviene separarlas en comandos aparte para no ralentizar tanto las pruebas. En pruebas aleatorias simples, el harness puede elegir comandos al azar hasta que algo se rompa; luego, al cambiar a un harness de fuzzer, basta con usar el flujo de bytes de entrada fuzzed para elegir los comandos. Así obtienes automáticamente cosas buenas como pruebas de regresión deterministas y reducción de casos de prueba.
  Nunca obtuve grandes resultados al pedirle explícitamente a libfuzzer que redujera casos de prueba, probablemente porque ya los había reducido mientras generaba la entrada. Por eso no me motivé a probar más verificaciones de interestingness que ayudaran a un fuzzer general a reducir casos de prueba. Me da curiosidad saber si a otros sí les ha funcionado

  • Totalmente de acuerdo. Uso este enfoque muy seguido. Haces una representación simbólica de una interfaz con estado, normalmente con un intérprete sencillo basado en switch-case o match, luego generas y ejecutas listas aleatorias de operaciones, y reduces la entrada que dispara asserts por violaciones de pre/postcondiciones o corrupción interna.
    Ya sea que lo llames pruebas basadas en propiedades, fuzzing o model checking ligero, puede ser sorprendentemente eficaz para encontrar bugs profundos. He visto muchas interfaces con estado donde cada operación por separado es correcta, pero sus supuestos mutuos no encajan del todo, y cuando se combinan de formas inesperadas eso escala a corrupción interna.
    También sirve ejecutar la lista de operaciones en paralelo con una implementación simple en memoria basada en hash table o lista, y verificar que los resultados coincidan. Si hay diferencias, casi siempre es un bug o un caso límite que debería documentarse mejor
  • A veces trabajo con optimización del transporte, y seguido me encuentro con escenarios bastante complejos donde se rompen invariantes. Sería buenísimo tener un reductor de casos de prueba, pero antes solo quedaba conformarse con reducirlos a mano[0].
    Lamentablemente, los archivos de datos son demasiado complejos como para que shrinkray pueda manejarlos. Lee datos tabulares de varios “archivos” distintos y además hay dependencias de largo alcance, así que probablemente habría que codificar directamente conocimiento del dominio sobre cómo reducirlos.
    Viendo la velocidad del avance de la IA, la próxima vez que me toque un escenario así probablemente escribiré un reductor a medida.
    [0] Si nos ponemos con ontología dudosa, un problema de optimización es un problema de búsqueda que minimiza un costo y, en ese sentido, en realidad es lo mismo que un compilador, así que no es un ejemplo perfecto

• Lo leí tres veces tratando de entender cómo aplicar esto a pruebas escritas con pytest.
  Quiero reducir la complejidad de mi suite de pruebas, así que pienso releerlo una cuarta vez cuando no esté trabajando

  • Si usas Python, el primer paso sería adoptar Hypothesis, que ya trae reducción de casos de prueba integrada

• El año pasado, mientras revisaba un problema con el orden de ejecución de pruebas en CI, hice una herramienta que ayudaba a reducir una lista de pruebas.
  Básicamente iba cortando las líneas por mitades y ejecutándolas.
  El script en sí tenía bastantes bugs, pero fue genial ver cómo una lista de 5000 pruebas se reducía a unas 4 que provocaban mi bug de concurrencia.
  De verdad me pregunto si Shrink Ray habría funcionado tal cual en mi caso. Sinceramente creo que “reducir un conjunto de líneas con base en una prueba” debería ser una función incluida en el conjunto estándar de herramientas de línea de comandos

• Relacionado con este tema, las pruebas basadas en propiedades usan un enfoque bastante parecido al “reducir” el espacio de estados de entradas generadas para producir contraejemplos de una prueba.
  La ventaja de las pruebas basadas en propiedades es que te permiten guiar y estructurar el espacio de búsqueda. Puedes hacer que la entrada sea un conjunto de transiciones que haga avanzar una máquina de estados que modela el programa.
  Siempre me sorprende lo poco que se usa esta técnica, incluso en áreas donde encaja especialmente bien, como bases de datos y sistemas distribuidos. Justo la semana pasada armé una de estas pruebas en $WORK en cuestión de horas, y rápidamente descubrimos que nuestro sistema no convergía. La prueba imprimió una traza limpia que mis colegas pudieron entender en cuanto se las mostré.
  Personalmente, me parece la técnica de pruebas con mejor retorno sobre la inversión cuando se trata de depurar sistemas complejos