Archivos para 31 agosto 2008

El LHC y el peligro asumible frente al peligro real

Como todos sabréis, el LHC es es un aparato muy caro, tanto, que vale nada mas y nada menos que 6.000 millones de dolares.

Dicho así, de entrada, uno podría pensar que es un poco caro, pero teniendo en cuenta que es posiblemente el mayor experimento científico de la humanidad, incluso parece barato (¿Quien no tiene 6.000M euros en calderilla? :), sin embargo, no ha sido su precio lo que ha levantado la liebre sobre este trasto, sino su supuesto peligro.

El caso, es que se ha hablado largo y tendido en foros, blogs y en meneame sobre el peligro del LHC, resulto que hay quien piensa, que generará uno o mas agujeros negros, que crecerán hasta absorber la tierra, el sistema solar, o todo el universo.

Esto plantea serias dudas, para algunos, sobre si se debería continuar con el experimento. Sin embargo otros se muestran en otra postura, y preguntan si de verdad existe un riesgo real, y se asustan al escuchar a gente entendida, decir que si.

Llegados a este punto de alarmismo social entorno al LHC, hoy, leyendo a supuestos entendidos el tema, por blogs y por meneame, creo que he entendido por que se niegan a decir que no hay riesgo.

Pero en lugar de entrar en divagaciones, sobre los riesgos, que seguramente, ni yo entendería, por que no soy físico, me he dado cuenta de que existe una analogía entre el tema del LHC y la seguridad informática (eso, o yo veo analogías con la seguridad en todas partes).

En seguridad informática, se habla mucho sobre el riesgo teórico (donde juega un papel clave), el cual muchas veces, está muy alejado del riesgo real.

El riesgo teórico es ese que podría pasar, pero nuestra lógica y conocimientos en la materia nos indica lo contrario, sin embargo, queda una posibilidad, la cual nosotros sabemos que no se cumplirá, pero que podríamos decir que existe, y por ello, no la descartamos.

Voy a poner un ejemplo técnico: el caso del overflow en los mbuf de OpenBSD en ipv6:

http://www.securiteam.com/unixfocus/5HP0C1FKUO.html

Es un bug en OpenBSD, que permite provocar un overflow en la pila ipv6, lo cual, por el tamaño y disposición de las estructuras en memoria, no permite ejecutar código arbitrario de mas de una instrucción.

Es decir, el exploit que porporcionan, solo ejecuta int 3h y punto, por que? por que no caben mas instrucciones, dada la naturaleza del bug.

Sin embargo, a día de hoy, nadie se ha atrevido a decir que ese exploit, no se pueda usar para conseguir acceso remoto a un OpenBSD, y es por que aunque en teoría, no caben mas instrucciones en memoria, y nuestra lógica dice que nunca nadie podrá aprovechar eso para ejecutar nada de mas de una instrucción, la historia nos ha enseñado a no hacer afirmaciones del tipo “nunca nadie…“, por lo que pese a que todos sabemos que ese bug no tiene mas riesgo que que te cuelguen el sistema, ¿Que pasaría si el sistema fuese el planeta, y funcionase sobre OpenBSD?

Seguramente, todos los que no entendiesen de esto, vendrían corriendo a preguntar, si realmente hay riesgo de que alguien consiga acceso a nuestro mundo, utilizando este bug. Y cualquiera que sepa un mínimo del tema, les tendría – tristemente – que contestar: existe una cierta posibilidad.

El problema de estas situaciones, es que la frase “existe cierta posibilidad” no significa lo mismo para un experto en el tema, que para alguien que no tiene ni idea, el segundo, seguramente se asustará, mientras que el experto, discernirá que se trata de una posibilidad teórica, y que si pudiésemos hablar de forma menos científica y menos ortodoxa, podríamos decir que no existe esa posibilidad.

Nota: no se como me atrevo a escribir posts mezclando el LHC, el universo, y OpenBSD.

Librería en C para usar la API de meneame, y meneame-utils

Hoy es sábado, y como informático que soy, los sábados no salgo por ahí, no voy a bares ni discotecas, ni me paseo por ningún sitio…Me quedo en casa programando, igual que el resto de la semana, pero programando lo que yo quiero, es decir, como hobby.

Este sábado he decidido programar algo un poco rebuscado…empezaré por el principio.

Como todos sabéis, meneame es una página web, donde los usuarios envían noticias, las cuales los usuarios votan, y las que mas votos reciben, llegan a portada, y son vistas por miles de personas. Es una especie digg en español, pero que además, es software libre.

El caso es que meneame tiene una API pública, que cualquiera puede utilizar, para interactuar con meneame, desde cualquier programa, mediante el protocolo http, por ejemplo, si queremos comprobar si una url existe en meneame, ha sido enviada antes:

http://meneame.net/api/url.php?url=http://www.google.com

Y nos devuelve OK seguido de los enlaces a las veces que ha sido enviada y los votos que recibió, si no ha sido envíada:

http://meneame.net/api/url.php?url=http://www.example.com

Nos devuelve “KO” y la url desde la que podemos enviarla.

Utilizando esta API, podemos hacer un programa, que tenga la opción de comprobar si una url, existe en meneame, y con eso, todo tipo de viguerías.

Otra API muy interesante de el meneame, es la de enviar notas al notame. El notame es una especie de twitter, pero integrado en la página de meneame.

Para enviar notas al notame, existe otra API que podemos utilizar:

http://meneame.net/api/newpost.php?user=NOMBREUSUARIO&key=CLAVEAPI&text=TEXTOAQUI

Donde la clave API, es nuestra clave API, que podemos consultar en nuestro perfil de meneame, habiendo iniciado sesión.

Bien, además de todo esto, las notas del notame se pueden leer vía rss, entre otras cosas.

No voy a continuar, por que no pretendo documentar aquí toda la API de meneame, era solo para hacer una idea de lo que es, y como funciona, para introduciros en lo que he programado hoy.

El caso, es que imaginaros que queréis hacer un programa que utilice una de esas API, necesitaréis hacer peticiones HTTP desde vuestro programa, en algunos casos parsear la respuesta…si queréis leer las notas del notame, necesitaréis leer del feed…todo esto, es demasiado trabajo para un simple programa que interactúa con meneame, por ello, he creado un conjunto de librerías en C, que disponen de una serie de funciones para interactuar con el meneame desde tu programa, sin preocuparte de nada.

Para ejemplificar como funcionan, he creado también 3 programas que utilizan las librerías, para que podáis ver en directo, como funciona todo esto.

Antes de entrar en materia de código, voy a enseñar un poco los 3 programas (en C, para consola) de los que hablo.

jcarlosn@thanatos:~$ mnmuserinfo -h
mnmuserinfo [-xkrwndz] [-i id] [-u usuario]
Consulta información sobre un usuario de meneame

-x    Muestra solo el username
-k    Muestra solo el karma
-r    Muestra solo la posicion en el ranking
-w    Muestra solo la web
-n    Muestra solo el nombre
-d    Muestra solo la fecha de registro
-z    Muestra solo el id

-i id    Consulta la informacion para el usuario con ese id
-u usuario    Consulta la informacion mediante el nombre de usuario

Ejemplos:

Consultar informacion de jcarlosn usando su id: mnmuserinfo -i 23321
Consultar informacion de jcarlosn usando su nombre: mnuserinfo -u jcarlosn

Para notificar bugs: jose@eyeos.org
jcarlosn@thanatos:~$

El primero, permite obtener información de un usuario de meneame, vamos a verlo:

jcarlosn@thanatos:~$ mnmuserinfo -u Carme
Id: 2682
Nombre de usuario: Carme
Web:
Nomre: Carmen
Karma: 15.220000
Ranking: 70
Fecha de registro: 2006-03-04
jcarlosn@thanatos:~$

Podemos pedirle información del usuario pasando su id, o su nombre de usuario, si queremos ver solo un campo, podemos hacerlo, por ejemplo, la web:

jcarlosn@thanatos:~$ mnmuserinfo -u jonarano -w

http://www.jonarano.es

jcarlosn@thanatos:~$

Vale, el siguiente comando de ejemplo, creado con las librerías es mnmchecklink, permite consultar una url, para saber si ya existe en meneame, y si existe, muestra su enlace a meneame, y sus votos:

jcarlosn@thanatos:~$ mnmchecklink http://www.google.com
http://meneame.net/story.php?id=41836  votes: 4
http://meneame.net/story.php?id=20861  votes: 3
jcarlosn@thanatos:~$

Y si no existe:

jcarlosn@thanatos:~$ mnmchecklink http://www.meloinvento.com
El link proporcionado no existe en meneame
jcarlosn@thanatos:~$

Y el tercer y último comando, el mas elaborado, permite enviar y leer notas del notame, vamos a verlo:

jcarlosn@thanatos:~$ cnotame -h
cnotame [-l] [-n usuario] [-v] [-k apikey] [-m mensaje]
Publica notas en el notame, usando la API de meneame

-v    modo verbose (salida con detalle)
-h    muestra la ayuda
-k CLAVE    la clave API que se utilizara para agregar las notas
-m MENSAJE    el texto de la nota a enviar
-u USUARIO    el usuario asociado a la clave API porporcionada

-n USUARIO    lista las ultimas notas de USUARIO
-l    lista las ultimas notas de el notame

Ejemplos:

Listar las ultimas notas: cnotame -l
Listar las ultimas notas del usuario jcarlosn: cnotame -n jcarlosn
Enviar una nota al notame: cnotame -k XXXXXXXXXX -m “hola meneantes” -u youuser

Para notificar bugs: jose@eyeos.org
jcarlosn@thanatos:~$

Por ejemplo, para ver las últimas 20 lineas del notame:

jcarlosn@thanatos:~$ cnotame -l | tail -n 20
#15   Abel.Florez

No creo que seas de Segovia. Si es así, te mando a “los Miami”.
autor: jmt
———————
Entro a tuenti.

Me encuentro con una foto de la Euskal Encounter, que salgo dormido como un angelito!!! Con una toalla al cuello (porque tenía frio). No conocía la existencia de tal foto

Eso si, la que la ha subido, ya tiene la respuesta en “modo foto”
autor: jonarano
———————
Odio cuando algunos videojuegos llegan a un punto de dificultad en el cual pasarte una pantalla significa “pulsar exactamente los mismos botones en los mismos instantes (durante un buen rato) porque no hay otra manera, llegar a un punto ligeramente más avanzado que la vez anterior, morir, repetir”.
autor: trollinator
———————
@trollinator Por curiosidad. Qué juego te atormenta?
autor: Cesc
———————
jcarlosn@thanatos:~$

Si no lo limitamos con tail ,la salida será un poco extensa.

Ahora para ver todas las notas de un usuario concreto:

jcarlosn@thanatos:~$ cnotame -n jcarlosn
No es lo mismo @PEP0M0LT0, no
autor: jcarlosn
———————
me aburro
autor: jcarlosn
———————
no es lo mismo ganar karma para votar, que votar para ganar karma (karmwhore)
autor: jcarlosn
———————
@Ancalagon: no, no lo merece
autor: jcarlosn
———————
las 3 y media y aun sin sueño, que dura la vida del informatico
autor: jcarlosn
———————
jcarlosn@thanatos:~$

Para enviar una nota al notame:

cnotame -m “introduce aqui tu nota” -k tuclaveapiaqui -u tuusuarioaqui

Estos programas, son ejemplos del uso de esta librería, podéis crear vuestros propios programas con ella, vamos a verla un poco por encima:

En la parte de notame, tenemos libnotame.h/libnotame.c que disponen de:

int sendNote(char *msg, char *key, char *user);
struct note *listNotes(char *author);

La primera envía una nota dado su texto, la clave API y el usuario, la segunda devuelve una lista enlazada con el contenido de las notas, si no queremos especificar autor, y queremos leer todas las notas del notame, basta con pasarle NULL, para iterar sobre la lista de notas, tenéis un ejemplo en cnotame.c:

result=listNotes(vuser);
if(result == NULL) {
fprintf(stderr, “Error obteniendo las notas de notame\n”);
}
while(result != NULL) {
ptr=result;
printf(“%s\n———————\n”,ptr->text);
result=ptr->next;
free(ptr->text);
free(ptr);
}

En el apartado de la API de consultar la información de un usuario, tenemos libuserinfo.c/libuserinfo.h, que disponen de:

int getUserInfo(int id, struct userInfo *uinfo);
int getIdByUser(char *user);

La primera, rellena el struct de tipo userInfo que le pases en el segundo argumento, con la información obtenida del usuario con id, recibido por el primer argumento, el struct userInfo es:

struct userInfo {
char username[60];
char name[512];
char web[1024];
int id;
float karma;
int ranking;
char regdate[11];
};

La segunda, devuelve el id de un usuario, dado su nombre de usuario.

Y en el apartado de links, tenemos liblink.h/liblink.c que dispone de:

struct link *linkExists(char *link);

La cual comprueba si el link dado existe ya en meneame, y si existe, devuelve una lista enlazada de structs del tipo:

struct link {
char url[42];
int votes;
struct link *next;
};

Con todos los enlaces de las veces que fue enviado a meneame, y los votos que obtuvo, para iterar sobre ella, hay un ejemplo en mnmchecklink.c:

stack = linkExists(argv[1]);

if(stack == NULL) {
printf(“El link proporcionado no existe en meneame\n”);
} else {
while(stack != NULL) {
printf(“%s votes: %d\n”,stack->url,stack->votes);
myLink=stack;
stack=stack->next;
free(myLink);
}
}

Bueno, tiene muchísimos detalles ocultos esta librería, y no voy a entrar demasiado en detalles por que me estoy extendiendo demasiado, si tenéis alguna duda sobre la librería, podéis escribirme, mi correo está en los headers de todos los archivos.

Para poder compilar los ejemplo, se requiere libmrss y libcurl, para instalarlos en sistemas basados en debian, como ubuntu:

sudo apt-get install libcurl4-openssl-dev libmrss0-dev libmrss0

Luego estando en el directorio donde lo habéis extraído, ejecutáis make y si queréis que se copien a /usr/local/bin, sudo make install.

El makefile es muy cutre, por que solo son ejemplos de lo que se puede hacer con la librería, nada mas.

Todo el código es software libre y está liberado bajo GPL3, como dice en los headers.

Podéis descargar la librería de aquí.

Aviso: no es una librería propiamente dicha, en el sentido de librería de linux :) recordad que es un trabajo de fin de semana por hobby, es simplemente archivos .h con su .c, que proporcionan funciones para interactuar con meneame, y programas de ejemplo que los utilizan.

Por cierto, me olvidaba, segun comentaban aquí:

[*] Crea un API para bobos y los frikis harán virguerías, además dejarán de darte la lata pidiendo cosas complicadas. Pero no serán capaces de hacer que esos programas lean las notas vía RSS

así que los frikis no eramos capaces de leer las notas vía RSS :p

chage, un comando simpático

Seguramente muchos conoceréis el comando chage, incluido en la mayoría de distribuciones linux y que forma parte del paquete shadow-utils.

Para los que no lo conozcáis, chage es un comando que permite al root especificar la fecha de expiración de la contraseña de los usuarios, entre otras cosas. A los usuarios les permite consultar la fecha de expiración de su contraseña, la última vez que la cambiaron etc.

Por ejemplo, si ejecuto chage con la opción -l en mi sistema, obtengo:

Último cambio de contraseña                    : nunca
La contraseña caduca                    : nunca
Contraseña inactiva                    : nunca
La cuenta caduca                        : nunca
Número de días mínimo entre cambio de contraseña        : 0
Número de días máximo entre cambio de contraseñas        : 99999
Número de días de aviso antes de que expire la contraseña    : 7

Bien, el comando parece de los mas normal, pero vamos a investigar un poco… hagamos un ls -la sobre el, para ver que aspecto tiene:

-rwxr-sr-x 1 root shadow 45384 2008-04-03 03:07 /usr/bin/chage

Según se ve por la ‘s’ que hay en la mascara de permisos, tiene el bit sgid activado, eso significa, que lo ejecute quien lo ejecute, el grupo del proceso, será el del archivo, es decir, el grupo shadow.

Eso significa, que este binario puede leer y escribir del /etc/shadow, sin importar quien lo ejecute.

En principio esto no tiene ningún peligro, hay varios binarios que usan el bit suid/sgid en los sistemas linux modernos, y no sucede nada, por que el programa comprobará que usuario es quien lo ejecuta, y no nos dejará hacer según que cosas si no somos root, pero imaginad que pudiésemos tomar el control del proceso…sería fatal, podríamos alterar el /etc/shadow y modificar nuestro uid a 0, y ser root.

Sin embargo, ya os adelanto que el articulo de hoy no va sobre eso, así que espero que esta vez, nadie me acuse de “fanfarrón” o de hacer alarde de cosas que no son, voy a dejarlo bien claro: no estoy hablando de ningún agujero de seguridad en este post.

Vale, ahora que ya tenemos la aclaración de rigor, podemos continuar…como decía, sería muy peligroso que alguien pudiese tomar el control de ese proceso…así que veamos que medidas se toman para asegurar que el código de ese programa es de alta calidad, pues la seguridad de las cuentas locales de la mayoría de distribuciones, dependen de el.

Si nos descargamos el código fuente de su svn, en:

svn://svn.debian.org/pkg-shadow/

Y abrimos el archivo upstream/trunk/libmisc/strtoday.c, veremos una función, que usa el programa desde el propio main(), para convertir cadenas de texto que provienen del usuario, en fechas en segundos desde el 1 de enero de 1970, las típicas.

* strtoday() now uses get_date() (borrowed from GNU shellutils)

Según dice la linea 50 de ese archivo, esa función ya no es mas que un wrapper, un envoltorio que finalmente llama a otra función, una tal get_date robada de ¿GNU shellutils? Increíble.

El proyecto GNU shellutils se unió a GNU coreutils hace ya años, aquí debe haber algún error…no puede ser que una aplicación, que de fallar comprometería la seguridad de las cuentas locales (es decir, la cuenta root) de las principales distribuciones, tenga código de hace años y años, y además de un proyecto que ya no se mantiene, y que incluso se ha juntado con otro proyecto…

Sigamos indagando, vamos a ver el código de este tal get_date en upstream/trunk/libmisc/getdate.y

Nada mas abrirlo, la cabecera ya asusta:

**  Originally written by Steven M. Bellovin <smb@research.att.com> while
**  at the University of North Carolina at Chapel Hill.  Later tweaked by
**  a couple of people on Usenet.  Completely overhauled by Rich $alz
**  <rsalz@bbn.com> and Jim Berets <jberets@bbn.com> in August, 1990;

Según como se nos va presentando el panorama, un programa que podría comprometer la seguridad de nuestro sistema (de forma local, lo cual a muchos seguro que no les importa, ya que si fuese remoto, sería mucho peor) tiene código de hace 18 años.

Bueno, no juzguemos a dicho código por su edad, vamos a ver que tal está el código en si:

sign = c == ‘-’ ? -1 : 1;
if (!ISDIGIT (*++yyInput))
/* skip the ‘-’ sign */
continue;
}
else
sign = 0;
for (yylval.Number = 0; ISDIGIT (c = *yyInput++);)
yylval.Number = 10 * yylval.Number + c – ’0′;
yyInput–;
if (sign < 0)
yylval.Number = -yylval.Number;
return (0 != sign) ? tSNUMBER : tUNUMBER;

Con párrafos como ese, lo digo todo…no es un código muy organizado, documentado, ni ortodoxo.

Citaré otro párrafo, con un return muy legible, para los interesados:

long days = (
/* difference in day of year */
a->tm_yday – b->tm_yday
/* + intervening leap days */
+ ((ay >> 2) – (by >> 2))
- (ay / 100 – by / 100)
+ ((ay / 100 >> 2) – (by / 100 >> 2))
/* + difference in years * 365 */
+ (long) (ay – by) * 365
);
return (60 * (60 * (24 * days + (a->tm_hour – b->tm_hour))
+ (a->tm_min – b->tm_min))
+ (a->tm_sec – b->tm_sec));

Ahora ya si es suficiente.

Como vemos, no es un código que inspire mucha confianza…

Sin embargo, estoy de acuerdo que llegados a este punto, se me podría recriminar que el código funciona, y funciona bien, y que pese a sus años y su falta de coding style, no tiene por que tener fallos, bueno, vamos a verlo:

root@thanatos:/# chage -l root
Último cambio de contraseña                    : ago 27, 2008
La contraseña caduca                    : nunca
Contraseña inactiva                    : nunca
La cuenta caduca                        : nunca
Número de días mínimo entre cambio de contraseña        : 0
Número de días máximo entre cambio de contraseñas        : 99999
Número de días de aviso antes de que expire la contraseña    : 7
root@thanatos:/# chage -d 9999999999999999 root
root@thanatos:/# chage -l root
Fallo de segmentación
root@thanatos:/#

No ha sido muy difícil hacer que acceda a memoria fuera de su proceso, y viole un segmento, a que no?

Me reitero, yo no tengo ningún bug en este programa, ni estoy diciendo que sea inseguro, dejo el juicio de pensar si es seguro o no lo es, en manos del lector :)

Lo peor, es que no es raro ver trozos de código que quedan olvidados en programas que finalmente se incluyen en distribuciones importantes, y además, con el bit suid/sgid activado.

Algunos quizas conoceréis el término “seguridad proactiva” que viene a sugerir que hay que controlar estas cosas antes de que a alguien se le ocurra como aprovecharse de ello. GNU/Linux y las distros que lo rodean, son todo grandes proyectos llevados a cabo por personas admirables que ponen mucho empeño en el software libre, sin embargo, uno de sus puntos flacos es precisamente ese, la falta de seguridad proactiva.

Nota: chage produce la violación de segmento demostrada (que no es un agujero de seguridad, ni sirve nada mas que para mostrar que el programa no está muy pulido frente a errores) en ubuntu hardy de 64bits, no puedo garantizar que lo haga en otro sistema, no lo he probado.

Actualización: me confirman que en mandriva 64 no produce la violación de segmento, por lo que el pequeño experimento no se puede llevar a cabo en mandriva.

Agujero de seguridad grave en La Sexta

Últimamente está de moda en las cadenas de televisión, modificar cosas de la wikipedia, poniendo datos erróneos para reírse de que dicha enciclopedia se puede alterar por cualquiera…

Es irónico que las cadenas de televisión, donde mas se manipula, hagan este tipo de cosas, y es muy hipócrita que se rían de lo fácil que es alterar la wikipedia, cuando ellos de cada 4 noticias que dan, 7 son alteradas y manipuladas… Pero claro, ellos lo que quieren es ser los únicos con el poder de redactar lo que la gente lee…en fin.

Dejándome de rodeos, me ha sentado tan mal el incidente del follonero con la sexta, que he decidido mirar un poco por su web, a ver que tan bien hacen las cosas ellos, evidentemente, no pienso dar ningún detalle de como utilizar lo que voy a explicar aquí para hacer ningún daño, no pienso ayudar a ningún “cracker” aburrido a hacer de las suyas, pero si voy a explicar un poco, lo seguros que están tus datos con la sexta.

Investigando un poco he visto que cuando te vas a registrar en:

http://comunidad.lasexta.com/

Te da la opción de comprobar si tu nombre de usuario está libre o no, esto hace una petición ajax, que responde con el resultado.

Dicha petición es algo así:

http://comunidad.lasexta.com/comunidad/comprobar_login/0.40978486285709026/usuario

donde “usuario” es el nombre de usuario a comprobar, bien, si en ese campo metemos código xhtml:

http://comunidad.lasexta.com/comunidad/comprobar_login/0.40978486285709026/lol%22%3E%3Cbody%20onload=%22alert(document.cookie);%22%3E

Conseguimos acceso a las cookies del usuario, que podríamos reenviar hacia una web nuestra, utilizando document.location y pasando document.cookie como parámetro GET.

No se como hacen un programa metiéndose con la wikipedia, teniendo ellos sistemas así de vulnerables…

Estructuras de datos y todo eso

Acabo de empezar a escribir este blog, en el que me he propuesto escribir solo lo que me apetezca…  y el caso es que varios conocidos mios, están cursando la carrera de ingeniería informática, y estos últimos días me han pedido ayuda con la asignatura que ellos llaman FP2, y me ha parecido interesante escribir un poco, precisamente sobre eso, sobre algunos fundamentos de programación (en C/C++).

Voy a hablar de las estructuras de datos básicas que podríamos decir que son la Pila, lista y cola.

Una estructura de datos, es en programación, una forma de organizar y acceder a conjuntos de datos, de forma que podríamos decir, que las estructuras de datos, son distintos modelos de organizar conjuntos de información.

Como eso no suena muy claro, voy a enfocarlo de otra manera menos ortodoxa (espero que esto no lo lea nunca ningún experto :D)

Imagina que estás en tu casa, y de pronto el lavavajillas termina su trabajo, y los platos están listos para que los saques y los metas en el armario, bien, como la distancia entre el armario de los platos, y el lavavajillas, es un poco grande, os cansáis de tanto ir arriba y abajo, y le pedís a vuestra esposa/madre, que  se ponga al lado del armario, y vosotros le iréis pasando los platos.

Entonces empiezas a sacar platos del lavavajillas, y los vas dejando encima de la mesa, y de ahí, los va cogiendo ella, y los va metiendo en el armario.

En este ejemplo, los platos son los datos unitarios, y la mesa, es la memoria, en donde se almacenan los datos, el cómo nosotros pongamos los platos en la mesa, y en como ella los saque de la mesa, constituirán una estructura de datos.

Vamos a poner el ejemplo mas típico de todos, si vas dejando los platos encima de la mesa, cada uno encima del otro, estarás utilizando una estructura de datos llamada pila, y su particularidad es que el último plato que metas, será el primero en salir, esto se conoce como LIFO (Last Input, First Output).

Vale, con nuestro ejemplo de los platos, hemos descubierto ya la primera estructura de datos, la pila, la cual ya sabemos que es de tipo LIFO. En la pila, existe un concepto de siguiente, el siguiente plato es el que hay debajo de el que quitas, como siempre podemos ir agregando platos a la pila (en una habitación que no tuviese techo) la pila permite apilar tantos datos como quieras, sin afectar a los platos que yo había, ni cambiarlos de lugar o reestructurarlos.

Como vemos, el esfuerzo necesario para agregar un plato a la pila es mínimo y solo implica a ese plato.

Sin embargo, imagina que le dices a tu querida ayudante: saca primero el plato séptimo empezando por abajo, ella tendrá que primero contar los platos, recorriendo todos los platos hasta llegar al 7, levantar los de encima, coger el 7, y dejar otra vez los otros encima.

Como veis, el esfuerzo de acceder a un plato concreto, y no siempre el de encima, es muy grande.

Para solventar eso, podríamos cambiar el modo en el que apilamos los platos, podríamos colocar unas cajas numeradas encima de la mesa, en las que cada una cupiese un plato, al hacer esto, en la mesa cabrían como máximo unas 20 cajas, tu irías metiendo empezando por la caja 1, y acabando en la 20.

Al hacer esto, estaríamos usando un vector (array).

Tu ayudante, podría ir sacando platos de las cajas (posiciones del array), y metiéndolos en el armario. Si ahora le pidieses el plato número siete, solo tendría que ir y coger el plato de la caja (posición) 7, sin necesidad de mover nada, ni contar nada. El esfuerzo ha sido mucho menor, sin embargo, este método tiene también sus contras…

- Solo caben 20 platos, y si queremos meter mas, hay que hacer cosas muy costosas, como poner otra mesa y llenarla de cajas.
- Aunque tengas solo 3 platos, las cajas te ocupan gran parte de la mesa (que hemos dicho que es la memoria)

Como es lógico, todo el mundo, sin saber programar usa una pila para este problema, en el mundo real. La gente simplemente va apilando platos en lugar de utilizar cajas, por que? Por que en el problema planteado, no existe normalmente la necesidad de coger un plato arbitrario, sino que solo hay que ir apilando y desapilando.

Esta demostración sirve para ilustrar un par de cosas, la primera, es que distintas formas de organizar datos, proporcionan distintas ventajas y desventajas, y que en cada problema, hay que utilizar la adecuada.

Para extenderme un poco mas, seguramente alguien habrá pensado que el caso de la pila tiene otra desventaja, que es que los platos salen de la pila de platos, en un orden invertido al que entraron, por lo cual, el primer plato que apilaste, permanece en la pila mucho tiempo, y el último plato apilado, permanece en la pila un instante.

En el caso de los platos, esto no importa, pero, y si importase? Habría que utilizar una cola.

Una cola funciona exactamente igual que una pila, con la diferencia, que los platos se meten por arriba, y se sacan por abajo (imaginaros una mesa con una trampilla que tiene platos encima, y que se abre dejando caer un solo plato cada vez, y por ahí recoge los platos tu ayudante).

Usando una cola, tienes las mismas ventajas y desventajas que usando una pila, pues son sustancialmente lo mismo, pero en la cola se preserva el orden, el primer plato que metes, es el primer plato que sale (FIFO, First Input, First Output)

Es lógico que la gente use pilas y no colas para el problema de los platos, pues el orden en ese caso, no importa.

En toda esta explicación hay un concepto implicito, no tan fácil de ver, que es el concepto de lista, una lista es una forma de ordenar datos en la cual, cada datos apunta al siguiente, y el siguiente al siguiente, y nosotros solo tenemos el primero de todos, pero accediendo a su siguiente, y al siguiente del siguiente etc, podemos acceder a cualquier dato de la lista.

Una pila, es una lista, pues utilizamos el concepto siguiente, y una cola igual, cada vez que alguien desapila un plato de la pila, queda visible el siguiente, y cada vez que tu apilas un plato en la pila, lo haces encima del siguiente.

Como se puede ver, la pila y la cola, son formas de trabajar con listas, formas de ir metiendo y sacando cosas de listas, listas en las cuales, nosotros solo vemos el elemento que hay a la cabeza (como en el caso de los platos) y luego su siguiente, y su siguiente…

Existen otras estructuras de datos, pero de momento solo he querido entrar en estas 4 básicas: Vector, Pila, Cola y Lista.

En resumen:

- Si nuestro conjunto de datos, requiere que se pueda acceder a un dato concreto, de forma rápida, hay que utilizar un vector, donde podemos pedir la casilla X, sin pasar por las demas (acceso aleatorio)
- Si nuestro conjunto de datos tiene un volumen indeterminado y variable, debemos usar una lista
- En dependencia del orden y la forma en la que queramos ir sacando y metiendo cosas de la lista, debemos trabajar con ella en forma de cola, o en forma de pila

Como curiosidad, he desarrollado un ejemplo muy muy simplificado de Pila en C++, para que se vea una aplicación práctica, es un programa que apila 3 números, luego los desapila, y los muestra por pantalla:

Ejemplo de Pila en C++

Espero que esto ayude un poco a cualquiera que esté estudiando todos estos temas y se sienta un poco perdido :)

Por cierto, cuando le explicaba a un conocido mio, un fanático de kde, que estaba ayudando a algunos conocidos a entender FP2, me dijo: “es que todo eso ya te lo da Qt, no hace falta saberlo cuando programas en Qt)” Qt es una librería de clases, utilizada como base de KDE… mi duda es: ¿y entonces, como disciernes que estructura de datos usar en cada caso y por que?



Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.