Xmas.c, vencedor do International Obfuscated C Code Contest de 1988

 (udel.edu)
3 pontos por GN⁺ 2023-12-24 | 1 comentários | Compartilhar no WhatsApp
  • xmas.c, vencedor do International Obfuscated C Code Contest de 1988, é um código C que parece digitação aleatória e imprime a letra de The Twelve Days of Christmas
  • Ele coloca uma string criptografada dentro de um código menor que a própria saída e decodifica palavras e frases com uma cifra de substituição e chamadas recursivas
  • Ao expandir o operador ternário if-then-else em blocos e dar nomes a words e shift, aparece uma estrutura em que o valor de t muda o fluxo recursivo
  • shift mapeia caracteres iniciais para caracteres 31 posições à frente, e words contém trechos criptografados da letra separados por barras (/)
  • Embora seja um programa simples de impressão de letra, ele permanece como um exemplo criativo de ofuscação em C por combinar cifra de substituição, recursão bidirecional, código desnecessário e argumentos não usados

O que xmas.c imprime

  • xmas.c é um programa em C que venceu o International Obfuscated C Code Contest de 1988
  • O analista viu esse programa pela primeira vez por volta de 2000 e, em novembro de 2008, desmontou o código para entender seu funcionamento
  • Ao compilar e executar sem parâmetros, ele imprime a letra do cântico natalino The Twelve Days of Christmas, do 1º ao 12º dia
  • Um comentário no código original diz que o programa é menor até mesmo que a forma “compactada” da saída e que os jurados acharam que ele parecia “o resultado de alguém batendo aleatoriamente em uma máquina de escrever antiga”

Estrutura interna reescrita para facilitar a leitura

  • O primeiro passo da análise foi transformar todas as formas a ? b : c em blocos if-then-else explícitos
  • Duas strings de significado difícil receberam nomes de acordo com sua função
    • words: conjunto de palavras e frases criptografadas usado para construir a letra do cântico natalino
    • shift: string de substituição que converte caracteres criptografados nos caracteres reais de saída
  • main() começa com xmas(1, 0, '\0'), e depois uma única função xmas() trata toda a saída recursivamente
  • A variável t é o valor-chave que controla a direção da recursão e o comportamento dos desvios

Cifra de substituição e dados da letra

  • A string shift funciona, na prática, como se duas strings estivessem concatenadas
  • Um caractere encontrado na metade inicial é decodificado como o caractere 31 posições à frente
    • Por exemplo, o primeiro caractere da string, !, corresponde ao caractere de nova linha 31 posições adiante
  • O desvio t < -50 avança pela string a caractere por caractere até que o caractere de entrada _ apareça em shift
    • Ao encontrar um caractere correspondente, imprime a[31] e retorna
  • A string words é composta por dados criptografados da letra decodificados pela cifra de substituição
    • As expressões ordinais e os trechos da letra de cada verso são separados pelo caractere barra (/)

Papel de cada desvio recursivo

  • O desvio t < -72 troca os dois primeiros argumentos e chama a função novamente passando words como terceiro argumento
    • O principal objetivo é causar confusão, além de permitir recursão aninhada que ignora o terceiro argumento
  • O desvio t < 0 encontra a |t|-ésima barra (/) dentro da string e passa adiante a string que começa no caractere seguinte
  • O desvio t == 0 decodifica e imprime a string até a próxima barra, depois retorna 1
  • O desvio t == 1 é chamado apenas uma vez no início e inicia a recursão principal com xmas(2, 2, "%s")
  • O desvio t == 2 imprime a primeira linha no formato "On the [ordinal] day of Christmas my true love gave to me\n"
  • Os dois blocos condicionais finais mantêm a recursão em duas direções
    • Descendo a partir do dia atual para imprimir a letra do respectivo verso em ordem inversa
    • Subindo os dias até o 12º dia para repetir todos os versos

Fluxo de execução visível após a simplificação

  • Depois de entender o funcionamento, é possível reescrever o código em uma forma mais simples usando laços e rotinas da biblioteca de strings de C
  • Mesmo na versão simplificada, os dados centrais words e shift permanecem intactos
  • O desvio t < 0 usa index(a, '/') para encontrar o delimitador de barra e avançar até a posição desejada do trecho da letra
  • O desvio t == 0 decodifica e imprime caracteres com index(shift, *a++)[31]
  • O desvio t == 2 imprime o início de um verso na seguinte ordem
    • "On the "
    • O ordinal correspondente ao dia
    • " my true love gave to me\n"

Por que a ofuscação é interessante

  • Ao ser simplificado até o fim, o programa pode ser reduzido a um código que imprime a letra
  • O original usa cifra de substituição junto com recursão para criar uma estrutura muito mais complexa que uma simples impressão
  • Pequenos trechos de código desnecessário e argumentos arbitrários que na prática não são usados tornam a compreensão ainda mais difícil
  • Entender o código e escrevê-lo por conta própria são problemas diferentes, e xmas.c é considerado um exemplo criativo de código C

Leituras relacionadas

1 comentários

 
GN⁺ 2023-12-24
Opiniões no Hacker News

  • Há um exemplo parecido no lado do TeX, o xii.tex
    Colocando esse conteúdo em um arquivo .tex, executando pdftex e vendo o PDF resultante, ele sai assim: https://shreevatsa.net/post/xii/

    • Parece menos uma ofuscação e mais uma forma específica de compressão lógica

  • Eu guardei isso quando foi publicado originalmente, mas, diferentemente do nome de arquivo neste artigo, o meu arquivo era carol.c
    Ao compilar e executar em sistemas modernos, gcc -o carol carol.c emitiu avisos como return type defaults to ‘int’, type of ‘t’ defaults to ‘int’, type of ‘_’ defaults to ‘int’

    • A partir do GCC 14, int implícito não será mais permitido: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • O problema está em chamar xmas() dentro de main antes de sua definição
      Ao compilar com o GCC no macOS, aparece o erro ISO C99 and later do not support implicit function declarations; se main() for movida para baixo, compila corretamente e produz a saída certa
    • É surpreendente que haja tão poucos avisos, e que todos apareçam apenas na mesma linha

  • Isso me lembrou a complexidade de Kolmogorov
    Este programa parece um monte de absurdo, mas como produz a saída desejada, fico curioso se existiria um programa que gere a mesma saída sendo ainda mais curto e parecendo ainda mais sem sentido
    Como seria possível encontrar um programa desses?

    • O recorde atual do programa em C mais curto que imprime a letra de 12 Days of Christmas é de 431 bytes: https://code.golf/12-days-of-christmas#c
    • É bem provável que existam programas mais curtos
      Mas uma busca por força bruta é muito ineficiente; a resposta prática fica mais próxima de “seja esperto”, no sentido matemático
      Em geral, a complexidade de Kolmogorov é incomputável, portanto não existe um programa que receba uma string e retorne o programa mais curto que calcula essa string
      Ainda assim, em princípio, é possível que alguém prove que a complexidade de Kolmogorov de uma string específica é X
    • Na maioria dos casos, calcular diretamente a complexidade de Kolmogorov é praticamente impossível, e acho que só dá para comparar do ponto de vista de possibilidades, como dizer que algo é mais lento que alguma versão ou valor
      Por isso ela combina bem com competições de longo prazo, e por causa de curvas de crescimento como logaritmos, às vezes surgem descobertas interessantes bem na ponta final
      No momento, estou organizando uma mini competição até março do ano que vem para LLMs disputarem quem memoriza mais dígitos de pi; o prêmio atual é de 100 dólares e pretendo distribuí-lo de acordo com a proporção de contribuição no espaço logarítmico
      Como pi é teoricamente bastante compressível, parece interessante ver se um modelo consegue aprender um conjunto de pesos próximo ao comprimento mínimo de descrição (MDL) que recupere dos dados um algoritmo de alta compressão
      Mas ainda não está claro se isso é possível com modelos prontos; por enquanto, vou deixar como uma competição de memorização de dígitos e observar

  • A explicação é boa, e o IOCCC parece continuar vivo em 2023: https://www.ioccc.org/years.html

    • Olhando essa página, o último IOCCC aparece como sendo de 2020
      Mas na página inicial há uma atualização de maio de 2023 dizendo que eles “planejam realizar o 28º IOCCC”
      Há coisas que valem a espera, como lançamentos do Nethack

  • Recentemente descobri algo interessante sobre The Twelve Days of Christmas: todos os presentes seriam algum tipo de ave
    Dizem que até as ladies dançando e os lords pulando entram nisso

  • Também há algo que eu mesmo pesquisei há mais de 20 anos: http://michaeldnahas.com/xmassong/index.html

  • Se desativar os avisos, ainda funciona até no trunk: https://compiler-explorer.com/z/hGvs1e9jo

  • Lembrei de uma boa memória de 2022, quando eu estava nos meus dois últimos semestres da universidade e o professor mostrou esse trecho de código logo no começo da aula

    • Também dá para ler como uma piada do tipo “meus dois últimos semestres da universidade, nossa, foi no ano passado!”, como se fosse tão antigo que a lembrança estivesse nebulosa
      Não consigo distinguir se é sério ou uma comédia contida

  • Na faculdade, um professor incluiu isso no material impresso de C, e me lembro de ter digitado tudo à mão uma vez

  • Há uma tarefa parecida no Rosetta Code
    É um programa que imprime Old Lady Swallowed a Fly, uma música que cresce repetitivamente: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly