Programmes auto-reproducteurs (quines)

Vous êtes-vous déjà demandé comment écrire un programme qui génère son propre code source ? Si vous n’avez jamais essayé, je vous conseille de prendre un peu de temps pour y réfléchir avant de lire la suite. Ce n’est pas évident, car chaque caractère ajouté dans le code source doit également apparaître sur la sortie…

Un tel programme s’appelle un quine. Et il est prouvé qu’avec tout langage de programmation il existe un quine (une infinité ?). Cette page détaille un peu plus la théorie.

Des exemples sont déjà écrits pour plein de langages.

Quine simple

Voici un programme auto-reproducteur simple en C :

#include<stdio.h>
main(){char*s="#include<stdio.h>%cmain(){char*s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}

Nous pouvons tester, ce programme se génère bien lui-même :

$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){char*s="#include<stdio.h>%cmain(){char*s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}
$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){char*s="#include<stdio.h>%cmain(){char*s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}
$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){char*s="#include<stdio.h>%cmain(){char*s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}

(essayez de l’écrire ou de le réécrire tout seul pour bien comprendre comment ça fonctionne)

L’essentiel de l’astuce ici est de passer la chaîne s à la fois en tant que format et d’argument de printf.

Ce n’est pas sans poser de problèmes : dans la déclaration de la chaîne s, nous ne pouvons pas écrire " (évidemment), ni \", car alors il faudrait que le programme génère le \", donc le ", ce que précisément nous cherchons à faire. L’astuce est donc d’utiliser son code ASCII (34), inséré grâce aux %c. Le code 10, quant à lui, correspond au saut de ligne.

Quine alternatif

Nous pouvons imaginer deux programmes qui se génèrent l’un-l’autre : un programme A génère un code source B, tel que le programme B génère le code source A.

À partir de l’exemple précédent, c’est trivial, il suffit de rajouter une variable (que j’ai appelée « f » comme « flag ») dont on alterne la valeur :

#include<stdio.h>
main(){int f=0;char*s="#include<stdio.h>%cmain(){int f=%i;char*s=%c%s%c;printf(s,10,!f,34,s,34,10);}%c";printf(s,10,!f,34,s,34,10);}

La valeur de f alterne entre 0 et 1 :

$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){int f=1;char*s="#include<stdio.h>%cmain(){int f=%i;char*s=%c%s%c;printf(s,10,!f,34,s,34,10);}%c";printf(s,10,!f,34,s,34,10);}
$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){int f=0;char*s="#include<stdio.h>%cmain(){int f=%i;char*s=%c%s%c;printf(s,10,!f,34,s,34,10);}%c";printf(s,10,!f,34,s,34,10);}
$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){int f=1;char*s="#include<stdio.h>%cmain(){int f=%i;char*s=%c%s%c;printf(s,10,!f,34,s,34,10);}%c";printf(s,10,!f,34,s,34,10);}

Quasi-quine

Il est également possible d’écrire un programme qui en génère un autre, qui lui-même en génère un autre… sans jamais “boucler”. Je me suis amusé à en écrire deux exemples.

Fibonacci

Le premier calcule la suite de Fibonacci. Ou plutôt, il contient les deux premiers éléments de la suite (F(0)=0 et F(1)=1), génère un programme qui contiendra F(1) et F(2), qui lui-même générera un programme qui contiendra F(2) et F(3), etc. :

#include<stdio.h>
main(){int a=0,b=1;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}

Pour obtenir F(10) et F(11) (suivre les valeurs des variables a et b) :

$ for i in {1..10}; do gcc quine.c && ./a.out | tee quine.c; done
#include<stdio.h>
main(){int a=1,b=1;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=1,b=2;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=2,b=3;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=3,b=5;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=5,b=8;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=8,b=13;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=13,b=21;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=21,b=34;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=34,b=55;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=55,b=89;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}

Ce que je trouve fabuleux, c’est que chaque programme, qui connaît deux valeurs de la suite, sait non seulement générer un nouveau programme qui calculera la valeur suivante (ça, c’est facile), mais en plus, ce nouveau programme saura lui-même générer un autre programme qui calculera la prochaine, etc. Chaque programme transmet en quelque sorte son code génétique à sa descendance.

PGCD

Suivant le même principe, il est possible de calculer le PGCD de deux nombres. Nous pouvons générer une lignée de programmes qui calculeront chacun une étape de l’algorithme d’Euclide.

Cet exemple permet de calculer PGCD(64,36) :

#include<stdio.h>
main(){int a=64,b=36;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}

Le caractère % ayant une signification dans le formatage de printf, nous devons le doubler.

Nous aurions pu utiliser à la place a-a/b*b (ce qui revient à peu près au même, si a et b sont positifs avec a>b).

Voici le résultat (suivre les valeurs des variables a et b) :

$ for i in {1..5}; do gcc quine.c && ./a.out | tee quine.c; done
#include<stdio.h>
main(){int a=36,b=28;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}
#include<stdio.h>
main(){int a=28,b=8;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}
#include<stdio.h>
main(){int a=8,b=4;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}
#include<stdio.h>
main(){int a=4,b=0;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}
#include<stdio.h>
main(){int a=4,b=0;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}

Une fois la solution trouvée (lorsque b vaut 0), le programme se comporte comme un vrai quine (il se regénère à l’identique).

Compilateur magique

Passons maintenant à l’étape suivante. Jusqu’à maintenant, nous avons généré un programme qui génère un autre programme… Très bien. Mais ces programmes générés (en fait, leur code source), nous les compilons avec un compilateur (gcc).

Mais un compilateur, c’est un programme, qui en plus est écrit dans le langage qu’il doit compiler. En particulier, le compilateur C est écrit en C.

À partir là, il est possible de faire des choses très intéressantes, comme l’a expliqué en 1984 Ken Thompson dans son célèbre article Reflections on Trusting Trust (que je vais paraphraser).

Le code suivant est une idéalisation du code du compilateur C qui interprète le caractère d’échappement :

= next();
if (c != '\\')
    return c;
c = next();
if (c == '\\')
    return '\\';
if (c == 'n')
    return '\n';

C’est “magique” : le programme sait, de manière totalement portable, quel caractère est compilé pour un saut de ligne pour n’importe quel jeu de caractères. Le fait qu’il le sache lui permet de se recompiler lui-même, en perpétuant ainsi cette connaissance.

Supposons que nous voulions rajouter le caractère spécial « \v » pour écrire une “tabulation verticale” :

c = next();
if (c != '\\')
    return c;
c = next();
if (c == '\\')
    return '\\';
if (c == 'n')
    return '\n';
if (c == 'v')
    return '\v';

Évidemment, si le compilateur ne connaît pas \v, ce code ne compile pas. Mais il suffit de lui apprendre : le code ASCII de la tabulation verticale est 11. Nous pouvons donc modifier temporairement le compilateur, pour en générer une nouvelle version :

c = next();
if (c != '\\')
    return c;
c = next();
if (c == '\\')
    return '\\';
if (c == 'n')
    return '\n';
if (c == 'v')
    return 11;

La nouvelle version du compilateur accepte maintenant « \v », et peut donc compiler son propre code source contenant ce caractère. Le code source contenant le 11 peut donc être totalement supprimé et oublié.

C’est un concept profond. Il suffit de lui dire une fois, l’auto-référencement fait le reste.

Cheval de Troie (quasi-)indétectable

Considérons alors la fonction compile(s) permettant de compiler une ligne de code source. Une simple modification va délibérément mal compiler la source lorsqu’un motif est détecté :

void compile(char *s) {
    if (match(s, "pattern")) {
        compile("bug");
        return;
    }
    // …
}

Supposons que le motif permette d’identifier la commande login, et que le bug (cheval de Troie) compilé permette d’accepter, en plus du mot de passe correct, un mot de passe prédéfini quelconque : nous pourrions, en connaissant ce “faux” mot de passe, nous connecter sur n’importe quelle machine possédant le programme login compilé avec ce compilateur.

Mais évidemment, un tel bout de code dans le compilateur C ne passerait pas inaperçu et serait détecté très rapidement… Sauf avec l’ultime étape :

void compile(char * s) {
    if (match(s, "pattern1")) {
        compile("bug1");
        return;
    }
    if (match(s, "pattern2")) {
        compile("bug2");
        return;
    }
    // …
}

Ici, nous ajoutons un second cheval de Troie. Le premier motif correspond toujours à la commande login, tandis que le second motif correspond au compilateur C. Le second bug est un programme auto-reproducteur (tel que ceux que nous avons vus dans ce billet) qui insère les deux chevaux de Troie. Il nécessite une phase d’apprentissage comme dans l’exemple avec \v. Nous compilons d’abord la source ainsi modifiée avec le compilateur C normal pour générer un binaire corrompu, que nous utilisons désormais comme compilateur C. Maintenant, nous pouvons supprimer les bugs de la source, le nouveau compilateur va les réinsérer à chaque fois qu’il sera compilé.

Ainsi, en compilant un code source “propre” avec un compilateur dont le code source est “propre” et que nous avons compilé nous-mêmes, nous générons un binaire contenant un cheval de Troie !

Il est cependant possible de contrer cette attaque.