Xmas.c, der Gewinner des International Obfuscated C Code Contest 1988

 (udel.edu)
3 Punkte von GN⁺ 2023-12-24 | 1 Kommentare | Auf WhatsApp teilen
  • Das Gewinnerprogramm xmas.c des International Obfuscated C Code Contest von 1988 gibt mit C-Code, der wie zufälliges Tippen aussieht, den Text von The Twelve Days of Christmas aus
  • Es legt verschlüsselte Strings in Code ab, der kleiner ist als die Ausgabe, und entschlüsselt Wörter und Phrasen per Substitutionschiffre und rekursiven Aufrufen
  • Wenn man ternäre Operatoren in if-then-else-Blöcke auflöst und words sowie shift benennt, wird sichtbar, dass der Wert t den rekursiven Ablauf verändert
  • shift ordnet vordere Zeichen den Zeichen 31 Positionen weiter hinten zu, während words durch Schrägstriche (/) getrennte verschlüsselte Textfragmente enthält
  • Obwohl es nur ein einfaches Programm zur Ausgabe eines Liedtexts ist, bleibt es durch die Kombination aus Substitutionschiffre, bidirektionaler Rekursion, überflüssigem Code und ungenutzten Argumenten ein kreatives Beispiel für C-Obfuskation

Was xmas.c ausgibt

  • xmas.c ist ein C-Programm, das 1988 den International Obfuscated C Code Contest gewann
  • Der Analyst sah dieses Programm erstmals um das Jahr 2000 und zerlegte den Code im November 2008, um seine Funktionsweise zu verstehen
  • Wenn man es ohne Parameter kompiliert und ausführt, gibt es den Text des Weihnachtslieds The Twelve Days of Christmas vom ersten bis zum zwölften Tag aus
  • Im Kommentar des Originalcodes steht, dass das Programm sogar kleiner sei als die „komprimierte“ Form seiner Ausgabe und dass die Jury meinte, es sehe aus wie „das Ergebnis zufälligen Tippens auf einer alten Schreibmaschine“

Die intern lesbarer gemachte Struktur

  • Der erste Schritt der Analyse bestand darin, alle Ausdrücke der Form a ? b : c in explizite if-then-else-Blöcke umzuwandeln
  • Zwei schwer verständliche Strings erhielten Namen entsprechend ihrer Rolle
    • words: eine Sammlung verschlüsselter Wörter und Phrasen, aus denen der Text des Weihnachtslieds erzeugt wird
    • shift: ein String für die Substitution, der verschlüsselte Zeichen in tatsächlich ausgegebene Zeichen umwandelt
  • main() beginnt mit xmas(1, 0, '\0'); danach übernimmt eine einzige Funktion xmas() rekursiv die gesamte Ausgabe
  • Die Variable t ist der zentrale Wert, der Richtung und Verzweigungen der Rekursion steuert

Substitutionschiffre und Liedtextdaten

  • Der String shift verhält sich praktisch wie zwei aneinandergehängte Strings
  • Ein Zeichen, das in der vorderen Hälfte gefunden wird, wird durch das Zeichen 31 Positionen dahinter entschlüsselt
    • Zum Beispiel entspricht das erste Zeichen des Strings, !, dem Zeilenumbruchzeichen 31 Positionen weiter hinten
  • Der Zweig t < -50 bewegt den String a zeichenweise weiter, bis das Eingabezeichen _ in shift auftaucht
    • Findet er ein passendes Zeichen, gibt er a[31] aus und kehrt zurück
  • Der String words enthält die per Substitutionschiffre entschlüsselten verschlüsselten Liedtextdaten
    • Ordnungszahlen und die Textfragmente der einzelnen Strophen sind durch Schrägstriche (/) getrennt

Welche Rolle die Rekursionszweige übernehmen

  • Der Zweig t < -72 vertauscht die ersten beiden Argumente und ruft die Funktion erneut auf, wobei words als drittes Argument übergeben wird
    • Sein Hauptzweck ist Verwirrung; er ermöglicht verschachtelte Rekursion, bei der das dritte Argument ignoriert wird
  • Der Zweig t < 0 sucht im String den |t|-ten Schrägstrich (/) und übergibt den String ab dem darauffolgenden Zeichen
  • Der Zweig t == 0 entschlüsselt und gibt Zeichen aus, bis der nächste Schrägstrich erscheint, und gibt anschließend 1 zurück
  • Der Zweig t == 1 wird nur einmal zu Beginn aufgerufen und startet mit xmas(2, 2, "%s") die eigentliche Rekursion
  • Der Zweig t == 2 gibt die erste Zeile im Format "On the [ordinal] day of Christmas my true love gave to me\n" aus
  • Die letzten beiden Bedingungsblöcke halten die Rekursion in zwei Richtungen aufrecht
    • Vom aktuellen Tag aus nach unten gehend werden die jeweiligen Textzeilen in umgekehrter Reihenfolge ausgegeben
    • Die Tage werden bis zum zwölften Tag hochgezählt, und alle Strophen werden wiederholt

Der vereinfachte Ablauf

  • Nachdem man die Funktionsweise verstanden hat, lässt sich der Code mit Schleifen und Routinen der C-Stringbibliothek in eine einfachere Form umschreiben
  • Auch in der vereinfachten Version bleiben die Kerndaten words und shift unverändert
  • Der Zweig t < 0 nutzt index(a, '/'), um den Schrägstrich-Trenner zu finden und zur gewünschten Position des Liedtextfragments zu springen
  • Der Zweig t == 0 entschlüsselt mit index(shift, *a++)[31] Zeichen und gibt sie aus
  • Der Zweig t == 2 gibt den Anfang einer Strophe in folgender Reihenfolge aus
    • "On the "
    • die Ordnungszahl des jeweiligen Tages
    • " my true love gave to me\n"

Warum die Obfuskation interessant ist

  • Wenn man dieses Programm vollständig vereinfacht, bleibt Code übrig, der einen Liedtext ausgibt
  • Das Original kombiniert Substitutionschiffre und Rekursion und erzeugt so eine Struktur, die deutlich komplexer ist als eine einfache Ausgabe
  • Kleine überflüssige Codeteile und tatsächlich ungenutzte beliebige Argumente erschweren das Verständnis zusätzlich
  • Etwas zu verstehen und es selbst zu schreiben sind verschiedene Dinge; xmas.c gilt als kreatives Beispiel für C-Code

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-12-24
Meinungen auf Hacker News

  • Auf der TeX-Seite gibt es ein ähnliches Beispiel namens xii.tex.
    Wenn man diesen Inhalt in eine .tex-Datei schreibt, pdftex ausführt und sich dann das resultierende PDF ansieht, sieht es so aus: https://shreevatsa.net/post/xii/

    • Es wirkt weniger wie Obfuscation, sondern eher wie eine Form von insbesondere logischer Kompression.

  • Als es ursprünglich veröffentlicht wurde, habe ich es mir gespeichert; anders als der Dateiname in diesem Artikel hieß meine Datei aber carol.c.
    Beim Kompilieren und Ausführen auf einem modernen System bekam ich bei gcc -o carol carol.c Warnungen wie return type defaults to ‘int’, type of ‘t’ defaults to ‘int’ und type of ‘_’ defaults to ‘int’.

    • Ab GCC 14 wird implizites int nicht mehr erlaubt sein: https://fedoraproject.org/wiki/Changes/PortingToModernC#Remo...
    • Das Problem liegt darin, dass in main xmas() aufgerufen wird, bevor es definiert ist.
      Wenn man es mit GCC unter macOS kompiliert, erscheint der Fehler ISO C99 and later do not support implicit function declarations; verschiebt man main() nach unten, kompiliert es korrekt und erzeugt die richtige Ausgabe.
    • Erstaunlich ist, wie wenige Warnungen es gibt und dass sie alle nur in derselben Zeile auftreten.

  • Das erinnert mich an Kolmogorow-Komplexität.
    Dieses Programm wirkt zwar wie Kauderwelsch, erzeugt aber die gewünschte Ausgabe; deshalb frage ich mich, ob es für dieselbe Ausgabe auch ein noch kürzeres und noch unsinniger wirkendes Programm geben könnte.
    Wie könnte man so ein Programm finden?

    • Der aktuelle Rekord für das kürzeste C-Programm, das den Text von 12 Days of Christmas ausgibt, liegt bei 431 Byte: https://code.golf/12-days-of-christmas#c
    • Kürzere Programme gibt es höchstwahrscheinlich.
      Eine Brute-Force-Suche ist jedoch extrem ineffizient; die realistische Antwort läuft mathematisch gesehen eher auf „stell dich clever an“ hinaus.
      Im Allgemeinen ist Kolmogorow-Komplexität nicht berechenbar, daher gibt es kein Programm, das einen String entgegennimmt und das kürzeste Programm zurückgibt, das diesen String berechnet.
      Grundsätzlich ist es aber möglich, dass jemand beweist, dass die Kolmogorow-Komplexität eines bestimmten Strings X ist.
    • In den meisten Fällen ist es praktisch unmöglich, Kolmogorow-Komplexität direkt zu berechnen; man kann sie meiner Ansicht nach nur aus der Perspektive von Möglichkeiten vergleichen, etwa dass etwas langsamer wächst als eine bestimmte Version oder ein bestimmter Wert.
      Deshalb eignet sich das gut für langfristige Wettbewerbe, und wegen logarithmischer Wachstumskurven kommen manchmal gerade ganz am Ende interessante Entdeckungen heraus.
      Derzeit veranstalte ich bis März nächsten Jahres einen Mini-Wettbewerb, bei dem LLMs darum konkurrieren, die meisten Ziffern von Pi auswendig zu können; das aktuelle Preisgeld beträgt 100 Dollar und soll im Log-Space proportional zu den Beiträgen verteilt werden.
      Da Pi theoretisch recht gut komprimierbar ist, wäre es interessant zu sehen, ob ein Modell eine Gewichtsmenge lernen kann, die der Minimum Description Length (MDL) zur Rekonstruktion eines hochkomprimierenden Algorithmus aus den Daten nahekommt.
      Ob das mit fertigen Modellen möglich ist, ist allerdings noch unklar; deshalb lasse ich es vorerst einfach als Ziffern-Memorierwettbewerb laufen und beobachte es.

  • Die Erklärung ist gut, und IOCCC scheint auch 2023 weiter am Leben zu sein: https://www.ioccc.org/years.html

    • Auf dieser Seite wird als letzter IOCCC 2020 angezeigt.
      Auf der Homepage steht jedoch in einem Update vom Mai 2023, dass man plant, den „28. IOCCC“ auszurichten.
      Es gibt Dinge, auf die es sich zu warten lohnt, wie bei Nethack-Releases.

  • Kürzlich habe ich etwas Interessantes über The Twelve Days of Christmas erfahren: Alle Geschenke sollen eine Art Vogel sein.
    Sogar die hüpfenden Damen und die Lords sollen dazugehören.

  • Dazu habe ich vor über 20 Jahren selbst einmal recherchiert: http://michaeldnahas.com/xmassong/index.html

  • Wenn man die Warnungen abschaltet, funktioniert es sogar noch auf trunk: https://compiler-explorer.com/z/hGvs1e9jo

  • Das weckt eine schöne Erinnerung an 2022, meine letzten beiden Semester an der Uni: Der Professor zeigte direkt zu Beginn der Vorlesung dieses Codefragment.

    • „Meine letzten beiden Semester an der Uni, also vor sage und schreibe einem Jahr!“ liest sich auch wie ein Witz darüber, dass die Erinnerung wegen des hohen Alters schon verblasst sei.
      Ich kann nicht unterscheiden, ob das ernst gemeint oder trockene Comedy ist.

  • Ich erinnere mich, dass ein Professor an der Uni das in ein gedrucktes C-Skript aufgenommen hatte und ich es einmal komplett von Hand abgetippt habe.

  • Auf Rosetta Code gibt es eine ähnliche Aufgabe.
    Es geht um ein Programm, das das sich wiederholend erweiternde Lied Old Lady Swallowed a Fly ausgibt: https://rosettacode.org/wiki/Old_lady_swallowed_a_fly

    • Die Tcl-Version gefällt mir, weil sie im Grunde einfach den Liedtext komprimiert enthält.
      puts [zlib inflate [binary decode base64 "7VRNa8MwDL3nV2(...)"]]
      https://rosettacode.org/wiki/Old_lady_swallowed_a_fly#Tcl
      Für Python, Nim, Julia usw. gibt es wahrscheinlich ähnliche Versionen.