Les secrets de fabrication d'une entrée gagnante de l'IOCCC

Plus de 30 ans après sa création (voir encadré), le concours de l'IOCCC existe toujours. En ce qui me concerne, j’en ai entendu parler la première fois en 2003, en regardant le site de Fabrice Bellard (auteur de qemu, entre autres). Il a gagné le concours en 2000 (avec une méthode de calcul rapide de nombres premiers) et en 2001 (en écrivant un compilateur C de seulement 3301 octets...). Plus tard, j’ai beaucoup aimé les articles de GNU/Linux Magazine où David Odin tentait de déchiffrer les entrées gagnantes. Et finalement, l’année dernière j’ai décidé de me lancer… La figure 1 présente le code que j’ai proposé. Dans la suite vous découvrirez le cheminement que j’ai suivi et nous détaillerons certaines parties de ce code.

1. Les règles et conseils des juges

Les candidats sont invités à suivre un certain nombre de règles et de conseils.

Les conseils [3] sont bien sûr indicatifs, mais au final très utiles. Par exemple, on y apprend que certains thèmes (calcul de pi, etc.) ont été traités souvent, et les juges sont donc très exigeants sur ces sujets.

Les règles [4] doivent en revanche être respectées à la lettre. La règle la plus contraignante est la limite de taille du code source : il ne doit pas dépasser 4096 octets. De plus, en testant avec l’outil iocccsize.c, la taille indiquée doit être inférieure ou égale à 2053. Cet outil renvoie une taille plus faible parce que les mots -clés du langage ne comptent que pour 1 octet, les espaces sont ignorés, etc.

2. À la recherche d'une idée gagnante...

Ensuite, il vous faut une idée sympa. À quoi va servir votre programme ? Cela peut paraître secondaire, le but étant l’obfuscation, mais si votre proposition ne surprend pas les juges, vos chances sont minces. Bien sûr, si vous avez une idée vraiment géniale et inédite en matière d’obfuscation, alors vous pourrez gagner même si le programme en lui-même est très basique. On en a eu quelques beaux exemples en 2015 [5]. Dans le même ordre d’idée, certains gagnent avec des 1-liners... Donc tout est possible.

Mais revenons au cas le plus fréquent. Quelle est donc la dernière fois qu’un collègue vous a montré une technique ou un outil épatant ? Ou bien, en lisant GNU/Linux Magazine (par exemple), n’avez vous pas eu envie de creuser un thème en particulier ? Si ça ne vous dit rien, vous trouverez peut-être l’inspiration en regardant les entrées gagnantes des années précédentes. On discerne assez bien quelques sujets dont les juges paraissent friands : les maths, l’informatique théorique, les jeux vidéo, etc. Si vous hésitez entre plusieurs idées, sachez que vous pouvez soumettre jusqu'à 8 propositions différentes ! Un auteur peut donc gagner plusieurs fois la même année (cela a été le cas en 2015 par exemple).

Concernant l'objet de cet article, c’est le numéro de mai 2015 de GNU/Linux Magazine qui m'a inspiré. F. Le Roy nous y présentait blessed-contrib, un outil pour afficher des dashboards avec de vraies courbes dans le terminal [6]. L'outil repose sur la plage des 256 caractères « Braille ». Grâce à eux, on peut considérer chaque caractère du terminal comme une mini-bitmap de taille 2x4, la plage de 256 caractères donnant ainsi toutes les combinaisons possibles pour allumer ou éteindre chacun des 8 points.

En fait, on peut aller plus loin dans le côté visuel : si on remplace un caractère par un autre qui contient un point supplémentaire, on fait « apparaître » ce point supplémentaire. Avec une boucle et une temporisation, on peut donc visualiser un tracé de courbe progressif, pour simuler, par exemple, quelqu'un qui écrit à la main. C'est ce que j'ai choisi de faire pour cette entrée de l'IOCCC 2015.

La figure 2 présente l'utilisation du programme en mode interactif. On le voit en train de tracer le mot « hello ».

3. La manière simple d'obtenir un résultat compliqué

Maintenant qu’on a une idée, on peut commencer à travailler et implémenter une première version. En ce qui me concerne, j’ai commencé par un prototype fonctionnel en Python. Avec ce langage, on peut faire un prototypage rapide d’abord, puis se rapprocher petit à petit du programme C, les fonctionnalités bas-niveau de la librairie standard étant proches de celles du C.

Attention quand même à ne pas trop repousser le portage en C. Ce sera de toute façon vite nécessaire pour savoir si vous êtes proche ou non des limites de taille imposées.

Notez aussi que seule la partie visible de votre travail devra être en langage C : rien ne vous empêche d’automatiser les tâches annexes dans un autre langage. Par exemple, grâce à un script en Python, j’ai généré une longue chaîne de caractères utilisée dans le code source (la macro O_o, nous en reparlerons). J’ai aussi scripté le formatage final en Python, comme nous le verrons plus loin.

4. De l’obfuscation… beaucoup d’obfuscation !

Ensuite, on va commencer à s’amuser. Que peut-on imaginer pour rendre un programme absolument indéchiffrable ? Ma proposition, par exemple, est dotée des sept couches d’obfuscation qui suivent.

4.1 Complexité fonctionnelle

Dans l’idée que j’ai voulu développer, il y a quelques subtilités qui compliquent l’analyse du programme. Ce n'est donc pas à proprement parler une couche d’obfuscation que j’aurais rajoutée, mais ça tombe plutôt bien : quitte à obfusquer, il vaut mieux partir d’une base déjà complexe.

Pour remplacer un caractère par un autre, il faut pouvoir positionner le curseur à sa guise sur le terminal. Cela implique l'utilisation de caractères d'échappement fort peu lisibles [7]. Les juges ont déjà rencontré ces caractères plusieurs fois dans le contexte de l'IOCCC, mais je doute qu'ils les aient mémorisés...

Une autre subtilité se situe au niveau de l'encodage des caractères Braille. En réalité, pour écrire les « vrais » caractères Braille il suffit d'une bitmap 2x3 (et non 2x4). Cependant, dans l'Unicode, on a 2 points supplémentaires en bas. Cela rend la numérotation des points très étrange : les points 1 à 6 sont numérotés de haut en bas en 2 colonnes, et les points 7 et 8 sont comptés en ligne. Le calcul du caractère Braille à afficher est donc forcément bizarre...

4.2 Obfuscation des identifiants et noms de variables

Il s’agit d’une forme d'obfuscation très classique. On choisit des caractères qui se ressemblent, comme le O, le Q et le zéro par exemple, on réutilise les noms de variables dans des contextes différents, on s’amuse à enfreindre les règles de nommage habituelles (les fonctions en majuscules, les macros en minuscules), etc. Le but est toujours le même : faire passer un identifiant donné pour ce qu’il n’est pas.

Au début de mon code (figure 1 ou en ligne [8]), on lit par exemple la définition de macro suivante :

Cela ressemble à une macro récursive. À un détail près : les macros récursives cela n’existe pas ! ;) En fait, cette macro est utilisée à la fin du code, dans ce qui ressemble beaucoup à la fonction main() :

En réalité, après préprocessing, on obtient :

La fonction main() n’est donc pas exactement là où on l’attendait. Et la fonction f() n’est jamais appelée dans le code… Elle est juste là pour brouiller les pistes.

4.3 Obfuscation par le préprocesseur

Cette obfuscation n'est généralement pas la plus robuste face à l'expertise des juges. Mais cela peut être un plus, surtout si vous implémentez quelques contre-mesures pour perturber l'exploration des juges. Analysons quelques éléments de mon programme à ce sujet :

La définition de la macro Q en ligne 18 ouvre une parenthèse sans la refermer. De ce fait, à chaque fois que cette macro est utilisée, il faut fermer la parenthèse, comme en ligne 27, et au final le code se trouve avec plus de parenthèses fermantes que de parenthèses ouvrantes. Les « enjoliveurs de code », que les juges utilisent sûrement, n'aiment pas ce genre de choses :

Mais attention, les juges peuvent utiliser l’option -E de gcc pour voir l'allure du code après remplacement des macros. Effectivement, dans la sortie de gcc -E, le parenthésage est rétabli, rendant cette obfuscation plutôt vaine. Il faudrait donc décourager les juges d’utiliser gcc -E... Voilà comment je m’y suis pris.

La macro Q_ permet de répéter 5^³ = 125 fois son argument. Je l'utilise pour répéter les accolades ouvrantes et fermantes, ainsi que la macro O_o. La répétition des accolades permet de générer un grand nombre de blocs de codes imbriqués (inutiles). Imaginez l'indentation générée par un enjoliveur de code après ça… Quant à la macro O_o, il s’agit d’une longue chaîne de caractères (252 octets, elle est définie entre les lignes 7 et 14), la répéter 125 fois permet donc de rendre le résultat de gcc -E assez lourd...

Mais bon. Les juges auront tôt fait de redéfinir cette macro Q_ pour passer de 125 répétitions à une seule :

En tout cas, ils peuvent essayer. Car dans ce cas, le programme ne fonctionne plus :). En effet, pour parcourir O_o, le pointeur est incrémenté de 97 en 97, et non pas de 1 en 1, on a donc tôt fait de dépasser sa taille.

Prenons l'exemple d'un tableau de sept cases. Le plus simple est de numéroter les cases successivement : 0, 1, 2, 3, 4, 5, 6. Mais on peut aussi compliquer un peu la chose en numérotant de 5 en 5. On applique aussi un modulo 7 pour ne pas dépasser la taille. Cela donne : 0, 5, 3, 1, 6, 4, 2. On a bien parcouru toutes les cases (car 5 et 7 sont premiers entre eux). Si on numérote de 5 en 5 sans appliquer le modulo (0, 5, 10, 15, etc.), alors on doit concaténer cinq instances du tableau initial pour arriver au même résultat sans dépassement.

La macro O_o est indexée suivant ce principe. La méthode cachée, pour pouvoir se passer des 125 répétitions, est donc de rajouter des modulos 252 (la taille de O_o) à divers endroits du code. Voilà qui devrait quand même occuper les juges un moment, s’ils veulent passer par là...

4.4 Obfuscation liée au compactage

La macro O_o encode le tracé de chaque caractère géré par le programme. Il a fallu trouver un encodage compact, sinon on aurait gaspillé une bonne partie des 4096 ou 2053 octets autorisés.

En fait, chaque caractère à tracer correspond à un « circuit » à parcourir. J’ai donc encodé les opérations successives à effectuer (avancer, tourner à gauche, à droite, etc.) sous la forme de 4 bits par opération. En concaténant les opérations, on obtient donc un entier de 4*n bits qui correspond au circuit à parcourir. Il fallait ensuite un moyen pour encoder ces entiers de manière compacte dans le code source.

Pour compacter des informations en langage C, le plus efficace est d’utiliser une chaîne de caractères. On peut y encoder des valeurs entre 0 et 127 en utilisant le caractère ASCII correspondant. Par exemple ‘b’ pour la valeur 98. Mais certaines valeurs doivent être échappées. Par exemple, la valeur 10 s’écrira \n, ce qui fait 2 caractères dans le code source (backslash et n). Et il y a pire. La valeur 1 par exemple ne correspond pas à un caractère imprimable, on devra donc l’écrire en hexadécimal, avec quatre caractères : \x01 !!

En observant la table des caractères ASCII [9], on voit que les 95 caractères entre l’espace (32) et ~ (126) sont imprimables. Dans cette plage, seuls " et \ devront être échappés dans une chaîne C.

Vous souvenez-vous de vos premiers cours d’informatique, quand vous avez appris à compter dans des bases différentes de la base décimale ? Disons que l’entier que nous devons coder a la valeur 125674529. En base 10, il se décompose ainsi :

Sur le même principe, décomposons-le en base 95 (en prenant le reste de divisions successives par 95) :

Ainsi, coder cet entier revient à coder les coefficients successifs 1, 51, 55, 14 et 74. S’agissant de la base 95, ces coefficients sont des nombres compris entre 0 et 94. Ça tombe bien, on a justement repéré une plage de 95 symboles successifs dans la table ASCII. Pour coder 1, on prend donc le deuxième symbole de cette plage (car on démarre à 0), et on obtient ‘!’. On procède de même pour les autres. Et au final, on a codé notre nombre en cinq symboles seulement. Notez qu’en base décimale, il fallait neuf symboles !

À l’intérieur de la macro O_o, j’ai donc utilisé ce principe pour encoder le circuit correspondant à chaque caractère à tracer. Cela permet à la fois un encodage compact et une couche d’obfuscation supplémentaire.

4.5 Obfuscation dans la structure du programme

À ce stade, notre programme est déjà relativement complexe. Mais on peut faire mieux, en prenant à rebrousse-poil les principes de programmation structurée les plus élémentaires :).

Premièrement, on regroupe tout dans une seule fonction. De ce fait, un appel de f() vers g() devient un appel récursif à f(), ce qui est tout de suite moins clair. Ensuite, on enlève les autres éléments structurants du programme. On remplace les boucles via un nouvel appel récursif. On essaie aussi de dissimuler le branchement conditionnel (le if), mais ça, ça reste difficile.

Prenons un exemple de code simple :

On peut utiliser les opérateurs booléens pour cacher ce if, mais cela reste facilement lisible :

Essayons avec l’opérateur ternaire :

On a écrit que b ne prend la valeur 3 que lorsque la condition est remplie, sinon il garde sa valeur. La variation suivante nous permet d’avoir une clause <else> à 0 :

En C, si la condition est vraie, sa valeur est 1, et 0 sinon. Donc on peut écrire :

À ce stade, le problème reste l’opérateur ==. En le voyant, on pense tout de suite à une condition, donc le juge cherchera un if dissimulé. Mais on peut le remplacer, lui aussi. En effet, l’expression (a==2) est équivalente à !(a‑2). On obtient donc (après avoir consulté la table de précédence des opérateurs [10]) :

Ou mieux, au cas où un œil expert y verrait encore un if, on met la condition à la fin :

Et voilà, au final il est plutôt bien caché ce if non ? On est pourtant parti d’un cas trivial. Imaginez la chose dans un cas complexe et saupoudré de diverses couches d’obfuscation...

Un autre exemple de dissimulation de if concerne le code d’initialisation. Un programme plus simple aurait une structure du type :

En effet, le programme étant regroupé dans une seule fonction récursive, on va souvent passer par là et il faut s’assurer que <init> ne sera exécuté qu’une fois au début.

Pour une partie de ce code, j’ai adopté une approche différente : j’ai conçu ce <init> pour qu’il puisse être appelé N fois sans avoir aucun effet, sauf la première fois. Donc je n’avais plus besoin du if.

Notez enfin que comme les expressions sont combinables à volonté, elles sont très pratiques pour l’obfuscation. Dans mon unique fonction, en dehors de la déclaration des variables au début, il n’y a pas de point-virgule : j’ai combiné tout le traitement en une seule et unique expression. Ce n’est pas très compliqué, on peut par exemple combiner 2 expressions en une seule avec la virgule. Mais cela rend la structure du programme encore plus obscure, à mon avis.

Au départ je voulais aller plus loin dans ce registre. Mais, au bout d’un moment, on ne comprend plus son propre programme, et là on est obligé de s’arrêter...

4.6 Obfuscation dans le comportement du programme

Pour comprendre cette partie, revenons un instant sur deux use cases du programme :

Use case 1 : mode interactif

Le programme semble suivre le pseudo-code suivant :

Use case 2 : mode non-interactif (entrée standard redirigée)

ou

Dans ce cas, il n’y a pas d’interaction avec l’utilisateur. Le pseudo-code semble plutôt être :

En réalité, que ce soit l’utilisateur ou pas qui lui « parle », le programme lit toujours les données sur son entrée standard. Il n’y a donc pas de différence dans l’implémentation à ce niveau. De plus, dans sa configuration standard, le terminal bufferise déjà l’entrée clavier ligne par ligne : il n’y a rien de spécial à faire à ce titre pour gérer le cas « interactif ». Au final, la seule différence à implémenter dans le code pour différencier ces deux use cases est l’affichage ou non de "> " !!

Un programme classique utiliserait la fonction isatty() pour savoir si stdin est un terminal, et donc afficher ou non ces deux caractères. Mais bien sûr, pour un code de l’IOCCC, ce serait trop simple ;). Faisons un petit test avec un programme plus didactique :

Ce programme tente d’écrire "> \n" sur son entrée standard (stdin). Voilà une idée bizarre, non ? Normalement, quand on écrit, c’est sur la sortie standard (stdout)...

Les trois essais qui suivent doivent vous rappeler fortement les use cases décrits plus haut. On s’aperçoit que dans le premier cas, l’écriture réussit, et elle échoue dans les deux autres. En réalité, dans le premier cas, stdin = stdout = <le_terminal>. Il est donc logique que ça fonctionne. En revanche dans le deuxième cas, stdin est le fichier file.txt ouvert en lecture, on ne peut donc pas y écrire. Et dans le troisième cas, stdin est un pipe ouvert en lecture, donc là aussi l’écriture échoue.

Vous l’aurez deviné, mon programme utilise la même astuce : en écrivant le prompt sur stdin, celui-ci n’apparaîtra que dans le cas interactif.

Au final, dans mon code il n’y a donc aucune distinction entre le mode interactif et le mode non-interactif. Le programme exécute exactement les mêmes instructions dans ces deux cas. Et l'une de ces instructions, suivant qu'elle échoue ou non, permet de parfaire l'illusion.

4.7 Inversion des descripteurs de fichiers

Lors de son initialisation, mon programme s’amuse à inverser les descripteurs de fichier 0 (d’habitude stdin) et 1 (d’habitude stdout) via plusieurs appels à dup(), dup2() et close() (voir encadré).

Après inversion, 0 correspond donc à stdout et 1 à stdin. Ainsi, le programme lit sur le descripteur 1 (lignes 40-41) et écrit sur 0 (ligne 49). Logique. Cependant, on trouve quand même une écriture sur le descripteur 1 via l’instruction write(1,"> ",2) en ligne 45 : ce sont les 2 caractères du prompt interactif, qui sont donc écrits sur stdin, conformément à ce qui est dit dans la section précédente.

5. Le formatage

J’ai choisi de formater le code sous la forme d’un cadenas fermé, comme si je défiais les juges de l’« ouvrir ». En réalité, ce formatage est une opération délicate : vous manipulez la version finale de votre code, que vous ne comprenez plus depuis un bon moment, et qui explose à la moindre modification mineure !

J’ai voulu automatiser cette étape, mais il ne me restait que très peu de temps avant la date limite de soumission. J’ai donc été contraint de faire simple. Mon script layout.py prend 2 fichiers en paramètre : compacted.c qui contient le code à formater, sous la forme d’un bloc de code sans espaces, et layout.txt qui définit le masque à appliquer. Voici un exemple de fichier layout.txt pour appliquer la forme de la lettre D :

L’étoile indique à layout.py d’écrire le prochain caractère du code à cet endroit, l’espace et le \n doivent juste être reportés en sortie.

Bien sûr, vous aurez des noms de variable ou de fonction coupés au milieu. On essaie alors de permuter des choses comme <e1>+<e2> en <e2>+<e1> dans compacted.c pour voir si ça passe. Au pire, on ajoute un espace par-ci par-là. Pour procéder de manière progressive, layout.py prend un numéro de ligne en troisième paramètre. De ce fait, il applique le masque uniquement sur les n premières lignes, et il concatène le reste du code compact. On fait alors un test complet (test limite de taille, test compile, test fonctionnel) du genre :

Si tout fonctionne avec n=1, on essaie avec n=2, et ainsi de suite.

6. Les fichiers associés

Quand on soumet un programme à l’IOCCC, on peut fournir un certain nombre de fichiers associés. Pour ma part, j’ai hésité à fournir un fichier contenant l’encodage du tracé des caractères, plutôt que de l’intégrer au code source (macro O_o). Mais les juges pourraient interpréter ceci comme un moyen d'extraire du code pour satisfaire les limites de taille. À vous donc de voir quels fichiers annexes vous fournissez.

On doit aussi fournir un Makefile, ainsi qu’un fichier de remarques en markdown. Si vous gagnez, les juges commentent également le code et concatènent vos remarques pour générer le fichier hint.html publié sur le site [11]. Normalement, dans ce fichier, vous expliquez comment utiliser votre programme, en quoi il est obfusqué, et toute autre subtilité que les juges risquent de ne pas détecter. Laissez quand même du mystère... Par exemple, j’ai fait remarquer que le programme fournit deux modes, « interactif » et « non-interactif », et que pourtant la fonction isatty() n’est pas utilisée. Juste de quoi piquer la curiosité des juges en somme. Je les invite aussi à définir la variable d’environnement DRAFT=1, ou encore à donner prog.c en entrée du programme, pour voir. Je m’aperçois d’ailleurs que je n’ai pas abordé ces petites choses dans l’article… Est-ce que cela va aussi piquer la curiosité de mes lecteurs ? :)

Les juges font également remarquer que la revue des propositions peut devenir un peu fastidieuse quand le soir approche, et qu’ils apprécient donc un fichier de remarques avec un peu d’humour.

Conclusion

Vous voilà parés pour écrire votre première entrée pour l’IOCCC : j’espère bien voir fleurir les mentions FR parmi les gagnants des prochaines éditions !

Références

[1] Les fichiers de mon entrée gagnante : http://www.ioccc.org/years.html#2015_duble

[2] L’appel à proposition de 1984 : https://groups.google.com/d/msg/net.lang.c/lx-TAuEyeRI/HdOOnNx6LC0J

[3] Les conseils des juges : http://www.ioccc.org/2015/guidelines.txt

[4] Les règles du concours : http://www.ioccc.org/2015/rules.txt

[5] Une entrée de 2015 vraiment originale : http://www.ioccc.org/2015/endoh2/hint.html

[6] LE ROY F., « Créez des dashboards sexy dans vos terminaux », GNU/Linux Magazine n°182, mai 2015, p.78.

[7] Déplacement du curseur dans un shell : http://www.tldp.org/HOWTO/Bash-Prompt-HOWTO/x361.html

[8] Le code de mon entrée gagnante : http://www.ioccc.org/2015/duble/prog.c

[9] La table des caractères ASCII : http://www.asciitable.com/

[10] La priorité des opérateurs : http://en.cppreference.com/w/c/language/operator_precedence

[11] Le fichier hint.html de mon entrée : http://www.ioccc.org/2015/duble/hint.html