Xmas.c, ganador de 1988 del Concurso Internacional de Código C Ofuscado

 (udel.edu)
3 puntos por GN⁺ 2023-12-24 | 1 comentarios | Compartir por WhatsApp
  • xmas.c, ganador de 1988 del International Obfuscated C Code Contest, imprime la letra de The Twelve Days of Christmas con código C que parece tecleado al azar
  • Incluye una cadena cifrada dentro de un código más pequeño que la salida, y descifra palabras y frases mediante un cifrado por sustitución y llamadas recursivas
  • Al expandir los operadores ternarios if-then-else y darles nombre a words y shift, se revela una estructura en la que el valor de t cambia el flujo recursivo
  • shift mapea caracteres iniciales con caracteres ubicados 31 posiciones más adelante, y words contiene fragmentos cifrados de la letra separados por barras (/)
  • Aunque es un programa simple que imprime una letra, sigue siendo un ejemplo creativo de ofuscación en C por la combinación de cifrado por sustitución, recursión bidireccional, código innecesario y argumentos sin uso

Lo que imprime xmas.c

  • xmas.c es un programa en C que ganó el International Obfuscated C Code Contest de 1988
  • El analista vio este programa por primera vez alrededor del año 2000 y, en noviembre de 2008, desarmó el código para entender cómo funcionaba
  • Si se compila y ejecuta sin parámetros, imprime la letra del villancico The Twelve Days of Christmas, desde el primer día hasta el duodécimo
  • El comentario del código original incluye una frase que dice que el programa es incluso más pequeño que la forma “comprimida” de su salida, y que los jueces pensaron que parecía “el resultado de golpear al azar una máquina de escribir antigua”

Estructura interna explicada de forma legible

  • El primer paso del análisis fue convertir todas las formas a ? b : c en bloques if-then-else explícitos
  • A dos cadenas cuyo significado era difícil de entender se les dieron nombres acordes a su función
    • words: conjunto de palabras y frases cifradas para construir la letra del villancico
    • shift: cadena de sustitución que convierte caracteres cifrados en caracteres reales de salida
  • main() empieza con xmas(1, 0, '\0'), y luego una única función xmas() procesa recursivamente toda la salida
  • La variable t es el valor clave que controla la dirección de la recursión y el comportamiento de las ramas

Cifrado por sustitución y datos de la letra

  • La cadena shift funciona, en la práctica, como si fueran dos cadenas concatenadas
  • Un carácter encontrado en la primera mitad se descifra con el carácter ubicado 31 posiciones más adelante
    • Por ejemplo, el primer carácter de la cadena, !, corresponde al carácter de salto de línea 31 posiciones después
  • La rama t < -50 avanza por la cadena a carácter por carácter hasta que el carácter de entrada _ aparezca dentro de shift
    • Cuando encuentra un carácter coincidente, imprime a[31] y retorna
  • La cadena words es datos cifrados de la letra que se resuelven mediante el cifrado por sustitución
    • Las expresiones ordinales y los fragmentos de la letra de cada verso están separados por el carácter barra (/)

Rol de las ramas recursivas

  • La rama t < -72 cambia los dos primeros argumentos y vuelve a llamar a la función pasando words como tercer argumento
    • Su propósito principal es confundir, y permite una recursión anidada que ignora el tercer argumento
  • La rama t < 0 busca la barra (/) número |t| dentro de la cadena y pasa la cadena que empieza en el carácter siguiente
  • La rama t == 0 descifra e imprime la cadena hasta que aparece la siguiente barra, y luego retorna 1
  • La rama t == 1 se llama una sola vez al inicio e inicia la recursión principal con xmas(2, 2, "%s")
  • La rama t == 2 imprime la primera línea con el formato "On the [ordinal] day of Christmas my true love gave to me\n"
  • Los dos últimos bloques condicionales mantienen la recursión en dos direcciones
    • Desciende desde el día actual e imprime la letra de ese verso en orden inverso
    • Incrementa los días hasta el día 12 y repite todos los versos

Flujo de ejecución visto al simplificarlo

  • Una vez entendido su funcionamiento, puede reescribirse como un código más simple usando bucles y rutinas de la biblioteca de cadenas de C
  • Incluso en la versión simplificada, los datos centrales words y shift se mantienen sin cambios
  • La rama t < 0 usa index(a, '/') para encontrar el separador de barras y desplazarse hasta el fragmento deseado de la letra
  • La rama t == 0 descifra e imprime caracteres con index(shift, *a++)[31]
  • La rama t == 2 imprime el inicio de un verso en el siguiente orden
    • "On the "
    • El ordinal correspondiente a ese día
    • " my true love gave to me\n"

Por qué la ofuscación resulta interesante

  • Si se simplifica por completo, este programa puede reducirse a un código que imprime la letra
  • El original combina cifrado por sustitución y recursión para crear una estructura mucho más compleja que una simple impresión
  • Pequeños fragmentos de código innecesario y argumentos arbitrarios que en realidad no se usan dificultan aún más la comprensión
  • Entenderlo y escribir algo así son problemas distintos, y xmas.c es considerado un ejemplo creativo de código C

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-12-24
Comentarios en Hacker News

  • En el mundo de TeX también hay un ejemplo parecido, xii.tex
    Si pones esto en un archivo .tex y ejecutas pdftex, al ver el PDF resultante aparece esto: https://shreevatsa.net/post/xii/

    • Más que ofuscación, parece una forma de compresión lógica en particular

  • Lo había descargado cuando se publicó originalmente, pero a diferencia del nombre de archivo en este post, mi archivo era carol.c
    Al compilarlo y ejecutarlo en un sistema moderno, con gcc -o carol carol.c salieron advertencias como return type defaults to ‘int’, type of ‘t’ defaults to ‘int’ y type of ‘_’ defaults to ‘int’

    • A partir de GCC 14, ya no se permitirá int implícito: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • El problema está en que dentro de main se llama a xmas() antes de su definición
      Si se compila con GCC en macOS, aparece el error ISO C99 and later do not support implicit function declarations; si se mueve main() hacia abajo, compila bien y produce la salida correcta
    • Sorprende que haya tan pocas advertencias, y que además todas salgan solo en la misma línea

  • Esto me hace pensar en la complejidad de Kolmogórov
    Este programa parece un montón de incoherencias, pero produce la salida deseada, así que me pregunto si habrá programas aún más cortos y que parezcan todavía menos tener sentido produciendo la misma salida
    ¿Cómo se podrían encontrar?

    • El récord actual del programa en C más corto que imprime la letra de 12 Days of Christmas es de 431 bytes: https://code.golf/12-days-of-christmas#c
    • Es muy probable que existan programas más cortos
      Pero la búsqueda por fuerza bruta es muy ineficiente, así que la respuesta realista se parece más a “hazlo de forma ingeniosa” en el sentido matemático
      En general, la complejidad de Kolmogórov no es computable, así que no puede existir un programa que reciba una cadena y devuelva el programa más corto que la calcule
      Aun así, en principio sí es posible que alguien demuestre que la complejidad de Kolmogórov de una cadena concreta es X
    • En la mayoría de los casos, calcular directamente la complejidad de Kolmogórov es prácticamente imposible, y solo se puede comparar desde una perspectiva de posibilidad, como decir que algo es menor que alguna versión o valor
      Por eso encaja bien con competencias y concursos de largo plazo, y por la curva de crecimiento logarítmica a veces aparecen descubrimientos interesantes muy al final
      Ahora mismo estoy organizando una mini competencia para ver qué LLM puede memorizar más dígitos de pi hasta marzo del próximo año, con un premio actual de 100 dólares que se repartirá según la proporción de contribución en espacio logarítmico
      Como pi es teóricamente bastante compresible, sería interesante ver si un modelo puede aprender un conjunto de pesos cercano a la mínima longitud de descripción técnica (MDL) que restaure un algoritmo de alta compresión a partir de los datos
      Pero todavía no está claro si eso es posible con modelos ya existentes, así que por ahora lo dejaré como una competencia de memorización de números y veré qué pasa

  • La explicación es buena, y IOCCC parece seguir vivo incluso en 2023: https://www.ioccc.org/years.html

    • En esa página se muestra que el último IOCCC fue en 2020
      Pero en la página principal dice, en una actualización de mayo de 2023, que “planean realizar el 28.º IOCCC”
      Hay cosas que vale la pena esperar, como con los lanzamientos de Nethack

  • Hace poco descubrí algo curioso sobre The Twelve Days of Christmas: que todos los regalos serían algún tipo de ave
    Incluso las damas brincando y los lores saltando, al parecer

  • También hay algo que investigué personalmente hace más de 20 años: http://michaeldnahas.com/xmassong/index.html

  • Si desactivas las advertencias, todavía funciona incluso en trunk: https://compiler-explorer.com/z/hGvs1e9jo

  • Esto me trae un buen recuerdo de 2022, cuando estaba en mis dos últimos semestres de universidad y el profesor mostró este fragmento de código en cuanto empezó la clase

    • También se puede leer como un chiste de que ha pasado tanto tiempo que ya tiene borrosa la memoria, algo como “¿mis dos últimos semestres de universidad? ¡Pero si fue literalmente el año pasado!”
      No queda claro si lo decía en serio o como comedia seca

  • Recuerdo que en la universidad un profesor incluyó esto en un material impreso de C, y una vez lo tecleé a mano yo mismo

  • También hay una tarea parecida en Rosetta Code
    Es un programa que imprime la canción repetitiva Old Lady Swallowed a Fly: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly