La técnica de C-Reduce que se puede usar con cualquier lenguaje

 (bernsteinbear.com)
1 puntos por GN⁺ 2024-11-28 | 1 comentarios | Compartir por WhatsApp
  • C-Reduce es una herramienta para reducir código que reproduce bugs de compiladores de C, pero también puede aplicarse a otros lenguajes si hay una condición determinista, una reproducción rápida y uno o más archivos fuente editables
  • El ejemplo muestra el proceso de reducción de un bug ocurrido al ejecutar scrapscript en RustPython, donde interesting.sh determina si el problema se reproduce buscando un mensaje de error específico
  • Con solo ejecutar creduce --not-c interesting.sh scrapscript.py, el tamaño del archivo se redujo rápidamente, y al principio se observó un progreso de casi 50% de reducción
  • --not-c es una opción para evitar los passes de reducción específicos de C, por lo que ayuda a reducir tiempo de ejecución innecesario con entradas como Python
  • Si puedes expresar en un script corto la condición bajo la cual se reproduce un bug, también puedes usar C-Reduce para hacer más pequeños y manejables los reportes de bugs en lenguajes que no son C

Condiciones para usar C-Reduce con entradas que no son C

  • C-Reduce es una herramienta creada por Regehr y sus colaboradores para minimizar código que reproduce bugs de compiladores de C
  • Si un archivo de C de 10,000 líneas provoca un bug en Clang, puede usarse para reducirlo automáticamente en lugar de enviar el archivo gigante tal cual
  • Aunque parece una herramienta exclusiva para C, también puede usarse con entradas de otros lenguajes si se cumplen las siguientes condiciones

    • Condición determinista

      • Un método de reproducción relativamente rápido que ayude a la velocidad de reducción
      • Uno o más archivos fuente editables que C-Reduce pueda reducir
      • La condición determinista también puede imitarse de forma probabilística usando un wrapper en bucle

Ejemplo de reducción de una reproducción de bug en RustPython

  • Al ejecutar scrapscript en RustPython apareció un bug, y para reportarlo se escribió el script interesting.sh
  • El script ejecuta scrapscript.py usando la ruta absoluta al binario de RustPython y luego busca la siguiente cadena en la salida, incluyendo el error estándar
    • tried to push value onto stack but overflowed max_stackdepth
  • El comando de ejecución es el siguiente
    • creduce --not-c interesting.sh scrapscript.py
  • C-Reduce ejecuta en paralelo la prueba de interestingness y va reduciendo rápidamente el tamaño del archivo
    • El progreso de ejemplo se muestra como 0.5%, 9.2%, 18.1%, 47.5%, etc.
    • En pocos segundos reduce el archivo en casi 50%
    • Al momento de cerrar el artículo, ya había llegado a una reducción de 96.9%
  • Si no se usa --not-c, C-Reduce aplica muchos passes específicos de C
    • Con entradas de Python, esos passes pueden ralentizar el tiempo de ejecución
    • Es poco probable que cambien de forma sustancial el resultado en sí
  • El contenido relacionado se movió después a la página de Delta debugging

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-11-28
Opiniones de Hacker News

  • Como no compartieron el archivo reducido, lo corrí yo mismo. Compilé RustPython, tomé scrapscript.py, cambié la ruta en interesting.sh y lo ejecuté con nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py; al final se quedó cerca de 96.4%, 7347 bytes, y el resultado está en https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

    • Se me ocurrió de pronto que alguien más estaba preocupado de que, durante el proceso de reducción, el programa se rompiera y pudiera realizar acciones destructivas en la máquina local. Me pregunto si ejecutar el reductor como una derivación de Nix de source-to-source podría impedir comportamientos peligrosos y facilitar su despliegue en builders remotos
    • Como referencia, shrinkray lo reduce hasta 162 bytes si se deja correr unos 10 minutos: https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
      Si lo dejara más tiempo quizá mejoraría un poco más, pero parecía casi estancado, me aburrí y lo detuve

  • John Regehr, autor de C-Reduce, también recomienda probar Shrinkray para este uso. Dice que Shrinkray fue hecho para funcionar de forma independiente del formato, y que es una herramienta adecuada incluso en casos donde C-Reduce no se desempeña bien: https://mastodon.social/@regehr/113489759789563570

  • Hay un paper escrito en 2012 por John Regehr y otros autores que explica cómo funciona: https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

    • Leí este paper y aun así sigo sin entender cómo es posible. Parece entender tokenización, fusión de líneas, eliminación de tokens, etc., para lenguajes de programación arbitrarios; me pregunto si hay otro paper que explique solo este algoritmo
    • Este paper no trata sobre C-Reduce completo, sino sobre 3 reductores de casos de prueba específicos de dominio agregados al proyecto
      Por lo que recuerdo, la mayor parte de la reducción no específica de dominio de C-Reduce se acerca a una simple fuerza bruta

  • Acabo de enterarme de C-Reduce y ya me enganché. Se siente parecido a cuando descubrí git bisect por primera vez
    Tendré que guardarlo en algún rincón de la cabeza para usarlo algún día cuando se dé la situación adecuada

    • En mi primer trabajo después de la universidad, cuando estaba en el equipo de compiladores C/C++, hacía este tipo de trabajo manualmente. Me sorprende bastante que se pueda automatizar lo mismo
    • Tuve un problema que parecía ser un bug del compilador en cc65, un compilador C para procesadores 6502. Para targets como C64, NES y Apple 1
      Estoy pensando en configurarlo. Como VICE soporta una función para “emitir” a archivos del sistema operativo anfitrión, parece que se podrían correr las pruebas en el emulador
    • Es excelente cuando se usa junto con un generador aleatorio de entradas de prueba

  • El delta debugging no es un concepto nuevo: https://en.wikipedia.org/wiki/Delta_debugging
    delta, mi implementación de delta debugging, tiene más de 19 años: https://github.com/dsw/delta
    En la época en que Microsoft llamaba “cáncer” al open source, Microsoft Research envió a alguien hasta mi oficina para pedirme que lo publicara, así que lo lancé como open source. En la introducción a LLVM de Lattner también se menciona como la “herramienta estándar de delta debugging”, así que es una herramienta bastante conocida: https://aosabook.org/en/v1/llvm.html

    • C-Reduce es un poco más sofisticado que el delta debugging simple. Según el resumen del paper de 2012 “Test-Case Reduction for C Compiler Bugs”, los resultados de C-Reduce son en promedio más de 25 veces más pequeños que los de otros reductores o que los reductores que antes usaban más los desarrolladores de compiladores
      Es decir, la conclusión es que para una reducción efectiva de programas se necesita algo más que simple delta debugging. Claro que C-Reduce ya es una herramienta de 12 años
      Al mismo tiempo, la herramienta de LLVM enlazada, BugPoint, es exclusiva para LLVM IR, mientras que C-Reduce parece más general. Las herramientas y técnicas de minimización automática de casos de prueba todavía son desconocidas para la mayoría de los desarrolladores, así que este artículo puede ser útil aunque la idea sea conocida desde hace tiempo en ese campo

  • Encontré un artículo con ejemplos de antes y después: https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
    Aun así, todavía no entiendo bien cómo sabe qué eliminar en cada iteración. Supongo que hay cierto nivel de tokenización, pero no sé cómo funciona eso a través de varios lenguajes de programación

  • creduce es excelente
    Cuando desarrollaba un backend de target exótico para LLVM, usé un script de pruebas que generaba programas de prueba aleatorios durante horas con CSmith. Si había un crash, automáticamente corría C-Reduce y dejaba un archivo para inspeccionar, y fue de muchísima ayuda

  • También funciona bien con SQL. Lo uso en el trabajo y lo conocí a través de https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu...

  • Es una afirmación difícil de creer si no explican por qué funciona también en lenguajes distintos de C. No creo que sea mentira, pero me desconcierta que lo haga sin LLM

    • En pocas palabras, algunos pases de reducción se generalizan bastante bien a lenguajes de la familia C, y esos pases están entre los más efectivos.
      Por ejemplo, tokenizar la entrada al estilo de C y luego descartar al azar fragmentos de longitud de alrededor de 1 a 13 funciona bien para eliminar calificadores o atributos innecesarios, porque la mayoría de los lenguajes parecidos a C tienen reglas de tokenización similares. El pase que elimina unidades de paréntesis balanceados (), {}, [] también es útil en casi todos los lenguajes. Quitar comentarios y espacios en blanco también es efectivo, ya que muchos lenguajes usan estilos como los de C, /* */ y //.
      En realidad no hay tantos pases que sean muy específicos de C/C++. Por experiencia, una de las grandes debilidades de creduce es que es realmente malo en el paso de reducción que elimina templates, una tarea que parecería relativamente fácil de automatizar.
    • Recomiendo hojear el paper de PLDI que enlazó asmeurer. Está bien resumido.
      Algunas transformaciones son bastante específicas de C y usan el frontend de Clang, mientras que otras son bastante generales y probablemente funcionen en general para lenguajes de la familia Algol. Como es una herramienta modular, si quieres puedes agregar transformaciones que entiendan otros lenguajes.
    • Esto se parece más a la ciencia de la computación de antes. Espero que HN no haya olvidado ya esa tradición clásica de la ciencia de la computación.
      Aquí hablamos de cosas como algoritmos, no de machine learning espeluznante. También incluye cosas como usar Prolog para IA, aunque tiene el pequeño inconveniente de que no funciona muy bien para el propósito de crear IA.
    • Si no entiendo cómo funciona, no sé si es seguro usarlo de esta manera. ¿creduce podría ejecutar el script de entrada modificado y borrar mis archivos o comerse mi almuerzo?
    • Sin haber leído el paper, supongo que se parece a un fuzzer que aplica mutaciones orientadas a reducir el tamaño de la entrada.

  • ¿Cómo se compara con dustmite? [https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...](https://dlang.org/blog/2020/04/13/dustmite-the-general-purpose-data-reduction-tool/