Fork bombs: Concurrencia y recursividad

¡Hola!

Os traigo un nuevo script esta vez el más corto que se puede encontrar por ahí, incluso hay competiciones de cómo hacerlos lo más cortos posibles y en diferentes lenguajes.

Hoy de nuevo no se trata de arreglar ni facilitar cosas, sino de aprender. ¿Y cuál es la mejor manera de aprender? Romper. Sí pero no sólo eso: vamos a romper y explicar por qué rompe y cómo.

Como pone en el título, vamos a tratar las fork bombs o bombas fork. Lo importante para nosotros es la parte fork y la parte divertida es el bomb.

Fork significa bifurcación (¡y tenedor!) en inglés. En la informática, designa el acto de pasar de tener un proceso a tener dos.

¡Cuidado! No mezclar con los forks de los proyectos de software.

Hay una llamada al sistema en POSIX que se llama fork, (hay ejemplos de uso en la wikipedia). Esta función copia el proceso en ejecución, creando dos programas iguales corriendo exactamente en el mismo punto. No me quiero meter más en eso ahora, si alguien quiere saber más que ejecute “man 2 fork” o mire este enlace.

Y ahora la parte bomb 🙂
Los sistemas operativos tienen una tabla en la que guardan todos los procesos que se están ejecutando y, como todo en esta vida, tiene un límite. Esta tabla no sólo sirve para guardar un listado de los procesos, además sirve para ir rotando entre ellos y asignándoles tiempo de máquina.

Cuando la tabla está llena, no se pueden generar nuevos procesos y el procesador va rotando por todos esos procesos desaprovechando completamente el tiempo.

Una bomba fork es un script o programa que genera procesos de forma infinita llenando la tabla totalmente y generando un bloqueo del sistema 😀 .

Una vez dada la explicación, es momento de mostrar el script. Este es en bash, aunque se puede hacer en mil lenguajes. Os muestro un ejemplo que aparece en la wikipedia, aunque podéis encontrar más:

:(){:|:&};:

Es tan cortito porque el objetivo es que sea lo más corto posible (hay “competiciones” en el tema) y que se pueda ejecutar en una terminal. Sustituyendo los dos puntos (“:”) por un nombre más representativo y dándole un poco de forma de script:

#!/bin/bash
bomb(){
    bomb | bomb &
}
bomb

Como veis, no he cambiado realmente el contenido, lo que pasa es que la función ahora no se llama “:” sino “bomb”.

Vamos a analizar lo que ocurre aquí:

En primer lugar declaramos una función, llamada “bomb”. Esta función es una función recursiva, que eso ya es interesante, pero lo bonito viene ahora. Lo que ocurre es que hacemos un pipe entre dos funciones “bomb” y lo ejecutamos en background.

Se ejecuta en background porque si no, cerrando la terminal cortaríamos la ejecución del programa y no reventaría todo y no sería tan divertido.

El pipe se utiliza para generar los dos procesos, es decir, para hacer el fork… Me he tirado un poco a la piscina, vamos poco a poco:

En bash los pipes (tubería en inglés) se definen con el caracter “|” también conocido como “pleca” aunque en el mundillo se le suele llamar “pipe” directamente (para escribirlo: AltGr+1 en el teclado qwerty). Su funcionamiento, resumiendo un poco, es el de una tubería normal: lo que entra por un lado sale por el otro. En este caso, el output del comando de la izquierda será el input del comando de la derecha. Como algunos os preguntaréis cómo se hacen los forks con un pipe, respondo directamente: Los pipes no esperan a que el comando de la izquierda termine su ejecución para ejecutar el de la derecha introduciéndole el output del anterior, ejecutan ambos al mismo tiempo y transmiten los datos directamente esperándose el uno al otro si fuera necesario. De esta forma, en nuestro script (aunque no nos pasemos datos) ejecutamos ambas funciones al mismo tiempo y cada una es un proceso independiente, que a su vez ejecutan ambas funciones en procesos independientes, que ejecutan ambas funciones en procesos independientes, que…

Y así hacemos miles de procesos. En el momento en el que se llena la tabla (se llenará, y no tardará mucho) los procesos que han pedido un fork se quedarán esperando a que esta se vacíe y en cuanto lo haga se bifurcarán de nuevo volviéndola a llenar. A continuación un gráfico de lo que ocurre. Cada rectángulo representa una llamada a la función y los triángulos de colores representan su ejecución creando dos nuevas llamadas. Si os fijáis, no he definido ningún órden en el recorrido del árbol porque las llamadas ocurren al mismo tiempo.

forkbomb

Os animo a que lo probéis (poniéndole un sleep 1 o algo para que os dé tiempo) con alguna herramienta para ver los procesos al lado y veáis como crecen. El crecimiento será exponencial y molará mucho, pero seguramente tengáis que reiniciar el ordenador de botonazo. También podéis quitarle el “&” para cerrar la consola y que se corte todo, pero no sé qué tal se comportará.

Y eso es todo por parte de las bombas fork.

Por otro lado, me parece interesante hilar con mi entrada anterior en la que hablo de la recursividad y su relación con las estructuras tipo árbol. Si os fijáis en el gráfico que muestro más arriba, tiene similitudes con el que mostré en la otra entrada. Una diferencia es que el otro script sólo tenía un hilo y recorría el árbol entrando por las ramas hasta el último nodo y volviendo hasta la bifurcación anterior. El fork bomb construye el árbol de forma concurrente, creando las ramas al mismo tiempo. Esto nos enseña que podríamos recorrer un árbol de forma rápida utilizando la concurrencia y la recursividad. Podríamos repetir el script de la entrada anterior utilizando la concurrencia para que fuera como un tiro, pero eso os lo dejo a vosotros. Añadir también que podemos crear demasiados procesos y hacer una especie de fork bomb sin querer si no controlamos la profundidad del árbol. Como dije la última vez: un gran poder conlleva una gran responsabilidad.

Resumiendo las ideas interesantes:

  • Los sistemas operativos tienen una tabla de procesos. Cuando se llena esta tabla no se pueden crear más.
  • Los pipes arrancan ambos procesos al mismo tiempo.
  • La recursividad combinada con la concurrencia puede mejorar la velocidad al recorrer árboles. Pero es peligroso porque podemos crear demasiados.

Unos enlaces interesantes:

Y eso es todo por esta vez. Espero que os sirva de algo.

Un saludo.

Anuncios

Un pensamiento en “Fork bombs: Concurrencia y recursividad

  1. Aleatoriedad y timing desde python: multithreading. – Free Hacks!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s