Meta-programación (II): Cómo construir nuestros propios quines

En el anterior artículo ya habíamos avanzado brevemente qué es un quine. Tomando la definición de la Wikipedia, en informática, un quine es un programa (un tipo de metaprograma) que produce su código fuente como única salida. Por diversión, algunos hackers intentan desarrollar el quine más corto posible en cualquier lenguaje de programación. Los quines se llaman así por Willard Van Orman Quine (1908-2000), que hizo un estudio extensivo de autoreferencia indirecta y sugirió un caso famoso de paradoja sin autoreferencia directa: “Da como resultado un enunciado falso si es precedido por su cita”. ¿Estoy confundiéndote con tanta palabrería? Pongámonos manos a la obra…

 

Primera aproximación a la programación de un quine

Si me propusieran programar un programa cuya salida es su propio código fuente en un lenguaje de programación interpretado como pueda ser bash scripting, intentaría algo parecido a esto:

#!/bin/sh
cat $0

Es decir, sacar por pantalla el contenido del fichero $0, o sea, yo mismo. Sin embargo, esto viola la ley fundamental de la programación de quines: no está permitido leer el propio fichero de código para sacar el código por pantalla. Esta regla se aplica tanto a lenguajes de programación interpretados como a lenguajes compilados, puesto que un programa en C que buscara su fichero fuente en el disco duro y lo sacase por pantalla tampoco se consideraría un quine válido.

Veamos entonces cómo podríamos hacer un quine válido: dado que lo que necesitamos es sacar código fuente por pantalla, usaremos las funciones para escribir en la pantalla en cada lenguaje de programación. Intentémoslo en bash scripting…

#!/bin/sh
echo "#!/bin/sh"
echo "echo \"#!/bin/sh\""
echo "echo \"echo \\\"#!/bin/sh\\\"\""
...

Hummm, parece que así no acabaremos nunca. Probemos en C…

#include <stdio.h>
int main(int argc, char **argv)
{
  printf("#include <stdio.h>\nint main(int argc, char **argv)\n{\nprintf(\"#include <stdio.h>\\nint main(int argc, char **argv)\\n{\\nprintf(\"...

Estamos en las mismas: la cosa va bien hasta que llegamos a la línea en la que estábamos escribiendo por pantalla y se convierte en un bucle recursivo sin salida 🙁

Elemental, querido Thompson

Tenemos que idear algo para romper esa recursividad. El quid está en las referencias, definir una cadena y su valor y poder referirnos a ella tanto por su nombre como por su valor. ¿Cómo? No hay nada mejor que verlo con un ejemplo:

char s[] = {
	'\t',
	'0',
	'\n',
	'}',
	';',
	'\n',
	'\n',
	'm',
	'a',
	'i',
	'n',
	'(',
	')',
	'\n',
	'{',
	'\n',
	'\t',
	'i',
	'n',
	't',
	' ',
	'i',
	';',
	'\n',
	'\n',
	'\t',
	'p',
	'r',
	'i',
	'n',
	't',
	'f',
	'(',
	'\"',
	'c',
	'h',
	'a',
	'r',
	' ',
	'\\',
	't',
	's',
	'[',
	']',
	' ',
	'=',
	' ',
	'{',
	'\\',
	'n',
	'\"',
	')',
	';',
	'\n',
	'\t',
	'f',
	'o',
	'r',
	'(',
	'i',
	'=',
	'0',
	';',
	's',
	'[',
	'i',
	']',
	';',
	'i',
	'+',
	'+',
	')',
	'\n',
	'\t',
	'\t',
	'p',
	'r',
	'i',
	'n',
	't',
	'f',
	'(',
	'\"',
	'\\',
	'r',
	'%',
	'd',
	',',
	'\\',
	'n',
	'\"',
	',',
	's',
	'[',
	'i',
	']',
	')',
	';',
	'\n',
	'\t',
	'p',
	'r',
	'i',
	'n',
	't',
	'f',
	'(',
	'\"',
	'%',
	's',
	'\"',
	',',
	's',
	')',
	';',
	'\n',
	'}',
	0
};

main() {
int i;

        printf("char \ts[] = {\n");
        for(i=0;s[i];i++)
                printf("\r%d,\n",s[i]);
        printf("%s",s);
}

¿Os suena el código? Los lectores atentos ya se habrán dado cuenta de que se trata precisamente del código de Ken Thompson del que hablamos en el artículo anterior. Su funcionamiento es simple:

  1. Declara un array con gran parte del código fuente del programa.
  2. Comienza la función principal sacando por pantalla la declaración de ese array de caracteres.
  3. Realiza un bucle para ir escribiendo cada uno de sus valores, separados por comas, para completar la declaración del array.
  4. Escribe por pantalla el contenido del propio array, ahora ya todo seguido, es decir, el propio código fuente.

Al utilizar una variable de tipo array de caracteres, puede acceder a ella para regenerar el propio array (en el bucle, paso 2), o bien para escribir el propio código fuente (al final, paso 4).

Este programa realmente no se auto-imprime por pantalla, sino que genera un programa que sí se auto-imprime por pantalla:

$ make thompson
cc     thompson.c   -o thompson
thompson.c: In function 'main':
thompson.c:126: warning: incompatible implicit declaration of built-in function 'printf'
$ ./thompson
char    s[] = {
9,
48,
10,
125,
59,
10,
10,
109,
97,
105,
110,
40,
41,
10,
123,
10,
9,
105,
110,
116,
32,
105,
59,
10,
10,
9,
112,
114,
105,
110,
116,
102,
40,
34,
99,
104,
97,
114,
32,
92,
116,
115,
91,
93,
32,
61,
32,
123,
92,
110,
34,
41,
59,
10,
9,
102,
111,
114,
40,
105,
61,
48,
59,
115,
91,
105,
93,
59,
105,
43,
43,
41,
10,
9,
9,
112,
114,
105,
110,
116,
102,
40,
34,
92,
114,
37,
100,
44,
92,
110,
34,
44,
115,
91,
105,
93,
41,
59,
10,
9,
112,
114,
105,
110,
116,
102,
40,
34,
37,
115,
34,
44,
115,
41,
59,
10,
125,
        0
};

main()
{
        int i;

        printf("char \ts[] = {\n");
        for(i=0;s[i];i++)
                printf("\r%d,\n",s[i]);
        printf("%s",s);
}

Podemos entonces hacer lo siguiente:

$ ./thompson > thompson2.c
$ make thompson2
cc     thompson2.c   -o thompson2
thompson2.c: In function 'main':
thompson2.c:243: warning: incompatible implicit declaration of built-in function 'printf'
thompson2.c:247:2: warning: no newline at end of file
$ ./thompson2 > thompson3.c
$ make thompson3
cc     thompson3.c   -o thompson3
thompson3.c: In function 'main':
thompson3.c:243: warning: incompatible implicit declaration of built-in function 'printf'
thompson3.c:247:2: warning: no newline at end of file
$ ls -l thompson[23]*
-rwxr-xr-x 1 txipi txipi 7389 2007-01-02 01:11 thompson2
-rw-rr 1 txipi txipi  757 2007-01-02 01:11 thompson2.c
-rwxr-xr-x 1 txipi txipi 7389 2007-01-02 01:11 thompson3
-rw-rr 1 txipi txipi  757 2007-01-02 01:11 thompson3.c

Implicaciones en cuanto a seguridad informática

Como se ve, a partir de la segunda generación, ya tenemos un quine que genera a su vez quines que pueden ser compilados y ejecutados. Supongo que a alguno se le habrá ocurrido otro tipo de programas en los que suele pasar esto: al programar un virus informático es muy común esto mismo. La primera generación es un poco diferente a las subsiguientes debido a que inicialmente el virus carece de huesped en el que alojarse, pero posteriormente el virus va metaprogramando los programas que encuentra para convertirlos en generadores de su propio código.

¿Podría hacerse un virus apoyándose en el concepto de quine? Si el objetivo es infectar código fuente, parece que el enfoque mediante un quine tiene bastantes probabilidades de éxito. Desde hace un tiempo ya no es necesario especular sobre este hecho: los virus de código fuente existen y en los próximos artículos transcribiré un artículo del e-zine 29a donde se muestran unos cuantos ejemplos funcionales de virus de código C escritos en C.

Dado que C es un lenguaje no interpretado, el virus tendrá dos estados:

  1. Código fuente: el virus existe dentro de un fichero de código fuente C, pero no puede infectar a nadie hasta no ser compilado.
  2. Código ejecutable: el virus buscará huéspedes para ser infectados, es decir, ficheros de código fuente C, en los que dejará una copia de su propio código fuente.

Este enfoque se me antoja similar al que realizan algunos parásitos orgánicos como el que provoca la toxoplasmosis, que infecta a roedores, pero se reproduce dentro del aparato digestivo de los gatos, por lo que no se reproducirá hasta que el ratón no haya sido comido por el gato (el canalla de toxoplasma gondii, protozoo causante de la toxoplasmosis, hace que los roedores sean más atrevidos, provocando que sean más fácilmente cazados por los gatos).

4 pensamientos en “Meta-programación (II): Cómo construir nuestros propios quines

  1. jonbaine

    EUP!!
    Los infectores de codigo java también existen (hay un par de pruebas de concepto por ahi). El concepto es parecido, pero, lo mas interesante es utilizar descompiladores, infectar el codigo fuente y volverlo a compilar, hasta ese punto creo que no existe ningun virus que haga eso, pq el versionado de java perturba la vida (el codigo decompilado de la jdk 1.5 no es recompilable, en cambio el de la jdk 1.4 si :P).
    Si te interesa el tema un dia lo discutimos.
    Un saludete!!

    Responder
  2. txipi

    Sí, he visto pruebas de concepto de infectores en Java e incluso en MSIL (Microsoft Intermediate Language) que tienen enfoques que se parecen vagamente a la infección mediante quines. Donde ya se te va toda la olla con este tema es con la infección mediante metamorfismo y cosas como el Metaphor de Mental Driller y demás. Para mí ya es informática-ficción ;-D

    Responder
  3. jose

    hola…
    pues io no entiendo mui bn esto de un quines jejeje pero me gustaria saber para crear un virus…
    si alguien me puede ayudar les dejo mi correo valmon512@hotmail.com
    ai se podran comunicar conmigo e informarme todo sobre lo k saben =)
    atte jose

    Responder

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *