SET 39 Call For Papers

¿Eres un hacker? Si deseas pasar a formar parte de la historia del hacking hispano, colabora con la próxima edición de SET 39 enviándonos un artículo. No esperes más, esta es tu oportunidad de demostrar lo que sabes. Ayúdanos a construir una revista de hackers para hackers. SET Staff

Inteligencia artificial II

      4948

Autor: Falken
-[ 0x09 ]--------------------------------------------------------------------
-[ INTELIGENCIA ARTIFICIAL II ]----------------------------------------------
-[ by Falken ]--------------------------------------------------------SET-18-

En el numero anterior dimos un breve repaso a la historia de la inteligencia
artificial. Entre otras cosas, vimos algunos de los diferentes campos de
investigacion de esta ciencia. Se mencionaron cosas como la busqueda de
soluciones, el procesamiento del lenguaje natural, el reconocimiento de
modelos, la logica difusa, la vida artificial o los sistemas expertos. En
aquella ocasion, nos centramos en los sistemas expertos por tratarse de una
de las variantes de la inteligencia artificial que mas facil es encontrarse
en la vida cotidiana. Ademas, resulta ser bastante sencillo programar un
sistema experto basico acogiendose a la simple definicion que dimos en el
anterior numero. 


EL CONOCIMIENTO Y SU REPRESENTACION
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

En cualquier modelo de inteligencia artificial que se precie, debemos tener
en cuenta el paradigma de la representacion del conocimiento.

Al igual que con la inteligencia artificial en la que es habitual debatir
sobre que es realmente inteligencia, que me conocimiento sucede lo mismo.

El conocimiento en si no es la estructura de datos en la que almacenamos la
informacion. Para que se pueda decir que es estructura datos almacenan
conocimiento, este deber de poder ser un un mundo accedido y puesto relacion
con otras estructuras de datos similares.

El ejemplo clasico es aquel en el que un libro almacena informacion o
conocimiento en funcion de que este puede ser ha accedido a interpretado por
los lectores. De hecho un libro en chino para un espa~ol que no conoce este
idioma no contiene informacion alguna.

Estamos de acuerdo en esto. Asi que un sistema inteligente como estara tanto
de las representaciones del conocimiento de que dispone el sistema como de
las con puntuaciones que se pueden realizar sobre estas representaciones.
Esto es lo que se conoce como paradigma CONOCIMIENTO-REPRESENTACION, o
abreviadamente C-R.

Pero esta paradigma cuenta con diferentes versiones a lo largo de la historia
de la inteligencia artificial. Y en cada una de estas versiones, disponemos
de un sistema de representacion del conocimiento diferente, y como es logico,
tambien estan asociados diferentes sistemas de procesamiento sobre estos
modos de representacion.

Realizando a esta division conseguiremos independizar el proceso de
resolucion del problema o inferencia de la naturaleza del mismo. Con
encontrar una representacion del problema en el modelo escogido tendremos
bastante camino avanzado puesto que del mecanismo de inferencia debera ser
capaz de resolver el problema solo con estos datos.


TIPOS DE CONOCIMIENTO 
=-=-=-=-=-=-=-=-=-=-=

Existen distintos tipos de conocimientos definidos por aquellos aspectos en
los que se centra. Asi, tenemos las siguientes divisiones: 

     * Objetos: son entidades de las que se predican cosas. Se precisara de
       un mecanismo que sirva para representar los objetos, sus propiedades
       y sus relaciones. Por ejemplo: "Los ordenadores usan sistemas
       operativos. Linux es el mejor sistema operativo."
     * Eventos: son aquellos que especifican sucesos en el tiempo; desea ser
       posible orden a estos sucesos de forma temporal para asi establecer
       relaciones causarles entre ellos. Por ejemplo: "ma~ana sale el kernel
       2.2 de linux."
     * Reglas de inferencia: son aquellas que permiten desarrollar nuevos
       conocimientos en base a los ya existentes.
     * Conocimiento procedural o procedimental: es el conocimiento operativo
       sobre como se realizan determinados problemas. Equivale al
       procesamiento de las representaciones y se especifica a traves de los
       algoritmos. En el otro extremo tenemos el conocimiento declarativo que
       representa el conocimiento del problema de forma especifica.
     * Metaconocimientos: Es el conocimiento de nivel mas abstracto sobre lo
       que conocemos. Nos da una idea generalmente intuitiva sobre lo mas
       adecuado para resolver un problema. Desde el punto de vista de la
       informatica, es el que ayuda a resolver un problema con el menor
       tiempo de proceso. Dentro de este sistema se incluyen los algoritmos
       de encaminamiento que permiten determinar cual es el mejor camino
       entre dos puntos.

Vamos a ver todo esto con un simple ejemplo cotidiano. Analizaremos el
conocimiento para determinar la ruta mas corta entre dos puntos usando
el autobus:

	Objetos -> Las paradas del autobus.
	Eventos -> Los horarios del autobus.
	Reglas de inferencia -> Son las que determinan en que paradas
				se puede cambiar de linea.
	Conocimiento procedural -> Como ir entre paradas.
	Metaconocimiento -> Que para llegar a una parada el camino mas
			    corto es aquel que generalmente se dirige en
			    en esa direccion.

Como vemos, reducir un problema a estos tipos de conocimiento simplifica
la tarea bastante. El proceso para realizar este articulo quedaria:

	Objetos -> El articulo.
	Eventos -> Las pulsaciones por minuto o tiempo de escritura.
	Reglas de inferencia -> La documentacion que me sirve de base y como
				complementarla.
	Conocimiento procedural -> Como redactar el texto.
	Metaconocimiento -> Que entender lo que escribo ayuda a explicarlo
			    mejor.

Este como veis, es un buen ejercicio para ademas mejorar la forma en la que
nos enfrentamos a determinados problemas.


USO DEL CONOCIMIENTO
=-=-=-=-=-=-=-=-=-=-

Hay unos cuantos problemas que surgen acerca de los usos del conocimiento.
Estos son:

     * Adquisicion: Interesa que la forma de representar el conocimiento se
		    aproxime a la forma en la que los seres humanos perciben
		    el mundo; asi lograremos simplificar la obtencion del
		    conocimiento, la modelizacion del problema, la
		    comprension y la explicacion del proceso de resolucion.
     * Recuperacion: Hay que simplificar el metodo de recuperacion de parte
                    del conocimiento. La forma de conseguirlo es adaptando
		    al programa la memoria asociativa, es decir, asociando
		    un contexto al conocimiento.
     * Razonamiento: O como conseguir nuevos conocimientos en base a los que
		    ya tenemos. Quizas se trate de la parte mas compleja a
		    la que nos enfrentamos en inteligencia artificial.


TIPOS DE RAZONAMIENTO
=-=-=-=-=-=-=-=-=-=-=

Como hemos mencionado justo en el apartado anterior, lo que mas se complica
de todo esto es el razonamiento. Tanto es asi, que diferenciamos cuatro
tipos distintos de razonamiento:

     * Formal: Se realiza mediante la manipulacion sintactica de las
	       estructuras de datos, con el objetivo de deducir nuevas
	       estructuras mediante unas reglas de inferencia predefinidas
	       (Gramatica generativa)
     * Procedural: El razonamiento se produce de modo implicito segun la
	       ejecucion de determinados fragmentos de codigo. Es como
	       cuando un sistema operativo asigna la prioridad de las
	       tareas en la cola de procesos.
     * Por analogia: Es un razonamiento comun en el ser humano, pero
	       dificil de implantar como tarea automatica. Es el que
	       tanto le gustaba a Socrates explicar, con ejemplos como
               el de la botella. Basicamente conocido como silogismos.
     * Generalizacion y abstraccion: Se trata de abstraer el conocimiento
	       partiendo de otros conocimientos mas simples. El ejemplo que
               se me ocurre en este momento es, creo, facil de entender.
               Tenemos que Windows 95 es malo. Y Windows 98 es malo. Se que
               Windows 95 y Windows 98 son de Microsoft. Por lo que puedo
               abstraer que Microsoft es malo. ;)


TIPOS DE REPRESENTACION
=-=-=-=-=-=-=-=-=-=-=-=

Por regla general, se divide la representacion en dos partes, haciendo asi
mas facil su estudio.

Asi, por un lado tenemos la representacion del problema en si, lo que gusta
en llamarse Conocimiento declarativo, o el que. Y para que luego digan que
somos radicales, se representa con K.

Por otro lado esta el camino a seguir para resolver el problema. Algo asi
como el como (como me gusta liaros ;) ). Tambien se denomina inferencia,
y en este caso somos menos radicales y lo representamos con I.

El conocimiento declarativo se subdivide en tres partes:

	* Hechos (H) - Pues eso, los hechos. Las cosas que son ciertas en
	  un momento dado. Es la memoria a corto plazo.
	* Reglas (R) - La forma en la que se interrelaciona el conocimiento.
	  Es la memoria a largo plazo, y nos permiten obtener nuevos
	  conocimientos en base a los que ya tenemos.
	* Metaconocimiento (M) - Es un apoyo a las reglas de inferencia para
	  determinar que reglas han de utilizarse sobre otras en situaciones
	  dadas.


RESUMIENDO
=-=-=-=-=-

Como veis, esto de la intelgencia artificial, si bien es un tema muy
interesante y atractivo, se torna en tedioso en el aspecto puramente
teorico. Y eso que solo hemos tratado algunos aspectos muy basicos.

En este campo, podemos entrar dentro de los algoritmos geneticos, de las
redes neurales (algonus siguen obsesionados con llamarlas neuronales. No
vamos a entrar en polemica sobre eso). Y entonces si que se os quedaria la
pantalla a cuadros. Los lios que se montan para explicarlo.

Y todo para que?

Algunas personas piensan que la intelgencia artificial solo sirven para que
los investigadores se entretengan, o aprendan algo. Incluso los hay que
se empe~an en defender que simlemente es tirar el dinero.

Pero que les pareceria saber que gracias a la inteligencia artificial se
mejoran los diagnosticos en los hospitales (aunque en algunos no se note),
se mejoran los procesos de produccion, e incluso, se mejora nuestra
seguridad.

Hace tiempo, en la Comunidad de Madrid se instalaron unos peque~os
aparatos destinados a la deteccion de incendios forestales, actuando por
reconocimiento de patrones en conjunto con un buen sistema experto. Al
principio tuvo algunos fallos, por los que fue severamente criticado.

Pero despues de un periodo de entrenamiento adecuado se ha convertido en
uno de los mejores sistemas de teledeteccion de incendios que existe.


NUESTRO SISTEMA EXPERTO
=-=-=-=-=-=-=-=-=-=-=-=

En SET 17 incluimos el codigo de un peque~o sistema experto. Este codigo
tenia algunos fallos que han sido corregidos en la nueva version. Y como
seguramente queden algunos por ahi, pues si los encontrais, dad parte de
ellos.

Aqui teneis el codigo:

<++> set_018/experto/experto.c
/* experto.c by Falken para SET
 *
 * SET - Saqueadores Edicion Tecnica, 1998-99
 *
 * Sistema experto basico de proposito general que ofrece multiples
 * soluciones y ademas muestra el razonamiento seguido.
 * Basado en el fuente incluido en el libro 'Utilizacion de C en inteligencia
 * artificial' de Herbert Schildt, y publicado por Osborne/McGrawHill
 *
 *    1-99:
 *       - Mejora en el formato de archivo .dat
 *	 - Adaptacion de codigo para portabilidad a otros sistemas.
 *
 *    Por hacer:
 *       - Depurar codigo.
 *       - Posibilidad de multiples archivos .dat
 *       - Mejorar la inferencia.
 *       - Mejorar la interfaz.
 *       - Soporte de parametros en linea de comandos.
 *
 * UNIX/Linux: gcc -o experto experto.c
 * DOS: DJGPP
 * Windows: Cygnus
 *
 * EXPERTO
 *
 */

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

struct atributo {
	char atrib [80];
	struct atributo *siguiente;
	} at;

struct objeto {
	char nombre [80];
	struct atributo *alista;	/* Apuntar a la lista de atributos */
	} ob;

struct objeto_rechazado {
	char nombre [80];
	char atrib [80];		/* Atributo que causo el rechazo */
	char condicion;			/* Era necesario o se descarto por
					   una deduccion previa */
	} rj;

struct objeto_rechazado r_base [MAX];
struct objeto base_c [MAX];		/* Base de conocimiento */

int n_pos = -1;				/* Posicion en la base de
					   conocimiento */
int r_pos = -1; 			/* Posicion en la lista de
					   rechazos */

struct atributo *si, *no;		/* listas de tiene y no tiene */
struct atributo	*siguientesi, *siguienteno;

main ()
{
	char ch;

	no=si=0x00;
	do {
		libera_lista();
		ch=menu();
		switch(ch) {
			case 'i': introduce();
				  break;
			case 'p': pregunta();
				  break;
			case 's': salva();
				  break;
			case 'c': carga();
				  break;
		}
	} while (ch != 'x');
	return (0);
}

libera_lista()
{
	struct atributo *p;

	while (si) {
		p = si -> siguiente;
		free (si);
		si = p;
	}

	while (no) {
		p = no -> siguiente;
		free (no);
		no = p;
	}
        return (0);
}

/*
 * Ahora codificamos la funcion encargada de crear la base de conocimiento
 */

introduce()
{
	int t;
	struct atributo *p, *anterior_p;

	for (;;) {
		t = obtiene_siguiente();
		if (t == -1) {
			printf ("Fuera de la lista.\n");
			return;
		}
		printf ("Nombre del objeto: ");
		gets (base_c[t].nombre);

		if (!*base_c[t].nombre) {
			n_pos--;
			break;
		}

		p = (struct atributo *) malloc(sizeof(at));
		if (p == 0x00) {
			printf ("No hay memoria suficiente.\n");
			return;
		}
		base_c[t].alista = p;
		printf ("Introduce los atributos del objeto. ENTER para salir\n");
		for (;;) {
			printf (">> ");
			gets (p->atrib);
			if (!p->atrib[0]) break;
			anterior_p = p;
			p->siguiente = (struct atributo *) malloc(sizeof(at));
			p = p->siguiente;
			p->siguiente = 0x00;
			if (p == 0x00) {
				printf ("No hay memoria suficiente.\n");
				return;
			}
		}
		anterior_p->siguiente = 0x00;
	}
	return;
}

/*
 * Ahora codificamos la funcion encargada de realizar las preguntas al
 * Sistema Experto.
 */

pregunta ()
{
	int t;
	char ch;
	struct atributo *p;

	for (t=0;t<=n_pos;t++) {
		p = base_c[t].alista;
		if (intenta(p, base_c[t].nombre)) {
			printf ("%s concuerda con la actual descripcion\n", base_c[t].nombre);
			printf ("sigo (S/N): ");
			ch = tolower(getchar());
			getchar();
			printf ("\n");
			if (ch == 'n') return;
		}
	}
	printf ("No se ha(n) encontrado (mas) objeto(s)\n");
	return;
}

/*
 * Esta funcion se encarga de comprobar un objeto.
 */

intenta (struct atributo *p, char *ob)
{
	char respuesta;
	struct atributo *a, *t;

	if (!sigueno(p)) return 0;
	if (!siguesi(p)) return 0;

	while (p) {
		if (preg (p->atrib)) {
			printf ("es/ha/tiene %s? ", p->atrib);
			respuesta = tolower(getchar());
			getchar();
			printf ("\n");

			a = (struct atributo *) malloc(sizeof(at));
			if (!a) {
				printf ("No hay memoria suficiente.\n");
				return (0);
			}
			a->siguiente = 0x00;
			switch(respuesta) {
				case 'n': strcpy (a->atrib, p->atrib);
					  if (!no) {
						no = a;
						siguienteno = no;
					  }
					  else {
						siguienteno->siguiente = a;
						siguienteno = a;
					  }
					  return (0);
				case 's': strcpy (a->atrib,p->atrib);
					  if (!si) {
						si = a;
						siguientesi = si;
					  }
					  else {
						siguientesi->siguiente = a;
						siguientesi = a;
					  }
					  p = p->siguiente;
					  break;
				case 'p': razonando (ob);
					  break;
			}
		}
		else p = p->siguiente;
	}
	return 1;
}

/*
 * Busca un atributo que no tenga el objeto y que este en la lista
 */


sigueno (struct atributo *p)
{
	struct atributo *a, *t;
	a = no;
	while (a) {
		t = p;
		while (t) {
			if (!strcmp(t->atrib,a->atrib))
				return 0;
			t = t->siguiente;
		}
		a = a->siguiente;
	}
	return 1;
}

/*
 * Comprueba que tenga los atributos seleccionados
 */

siguesi (struct atributo *p)
{
	struct atributo *a, *t;
	char ok;

	a = si;
	while (a) {
		ok = 0x00;
		t = p;
		while (t) {
			if (!strcmp(t->atrib,a->atrib))
				ok = 0x01;
			t = t->siguiente;
		}
		if (!ok) return 0;
		a = a->siguiente;
	}
	return 1;
}

/*
 * Comprueba si el atributo se pregunto con anterioridad
 */

preg (char *atrib)
{
	struct atributo *p;

	p = si;
	while (p && strcmp(atrib, p->atrib))
		p = p->siguiente;

	if (!p) return 1;
	else return 0;
}

/*
 * Esta funcion muestra el motivo por el que se sigue una determinada linea
 * de conocimiento.
 */

 razonando (char *ob)
 {
	struct atributo *t;
	int i;

	printf ("Intentando %s\n", ob);
	if (si)
		printf ("es/tiene/ha :\n");
	t = si;
	while (t) {
		printf ("%s\n", t->atrib);
		t = t->siguiente;
	}
	if (no)
		printf ("No es/tiene/ha :\n");
	t = no;
	while (t) {
		printf ("%s\n", t->atrib);
		t = t->siguiente;
	}

	for (i=0;i<=r_pos;i++) {
		printf ("%s rechazado porque ", r_base[i].nombre);
		if (r_base[i].condicion == 'n')
			printf ("%s no es un atributo.\n", r_base[i].atrib);
		else
			printf ("%s es un atributo requerido.\n", r_base[i].atrib);
	}
	return (0);
}

 /*
  * Situar el objeto rechazado en la base de datos
  */

rechaza (char *ob, char *at, char cond)
{
	r_pos++;

	strcpy(r_base[r_pos].nombre, ob);
	strcpy(r_base[r_pos].atrib, at);
	r_base[r_pos].condicion = cond;
	return (0);
}

/*
 * Conseguir el siguiente indice libre del array de la base de conocimiento
 */

obtiene_siguiente()
{
	n_pos++;
	if (n_pos < MAX) return n_pos;
	else return -1;
}

/*
 * Aqui va la codificacion del menu de opciones
 */

menu()
{
	char ch;

	printf ("(I)ntroduce (P)regunta (S)alva (C)arga e(X)it\n");
	do {
		printf ("Selecciona una opcion: ");
		ch = tolower(getchar());
		getchar();
	} while (!esta_en (ch, "ipscx"));
	printf ("\n");
	return ch;
}

/*
 * Salvar la base de conocimiento
 */

salva ()
{
	int t, x;
	struct atributo *p;
	FILE *fp;

	if ((fp = fopen("experto.dat", "w")) == 0) {
		printf ("No puedo crear el archivo\n");
		return;
	}
	printf ("Salvando la base de conocimientos\n");

	for (t=0;t<=n_pos;++t) {
	   for (x=0;x<sizeof(base_c[t].nombre);x++)
	      if (base_c[t].nombre[x])
		 putc (base_c[t].nombre[x], fp);
	      else
	      {
		 putc ('\n', fp);
		 break;
	      }
	   p = base_c[t].alista;
	   while (p)
	   {
	      for (x=0;x<sizeof(p->atrib);x++)
		 if (p->atrib[x])
		    putc(p->atrib[x], fp);
		 else
		 {
		    putc ('\n', fp);
		    break;
		 }
	      p = p->siguiente;
	   }
	   putc ('\n', fp);
	}
	putc (0, fp);
	fclose (fp);
	return;
}

/*
 * Cargar una base de conociminto previamente almacenada
 */

carga()
{
	int t, x;
	struct atributo *p, *anterior_p;
	FILE *fp;

	if ((fp = fopen("experto.dat", "r")) == 0) {
		printf ("No puedo abrir el archivo.\n");
		return;
	}
	printf ("Cargando la base de conocimientos\n");

	ini_basec();

	for (t=0;t<MAX;++t) {
	   if ((base_c[t].nombre[0] = getc(fp)) == 0)
	      break;
	   for (x=1;x<sizeof(base_c[t].nombre);x++)
	      if ((base_c[t].nombre[x] = getc(fp)) == '\n')
	      {
		 base_c[t].nombre[x] = 0x00;
		 break;
	      }
	   base_c[t].alista = (struct atributo *) malloc(sizeof(at));
	   if (!base_c[t].alista)
	   {
	      printf ("No hay memoria suficiente.\n");
	      break;
	   }

	   p = base_c[t].alista;
	   for (;;)
	   {
	      for (x=0;x<sizeof(p->atrib);x++)
		 if ((p->atrib[x] = getc(fp)) == '\n')
		 {
		    p->atrib[x] = 0x00;
		    break;
		 }

	      if (!p->atrib[0])
	      {
		 anterior_p->siguiente=0x00;
		 break;
	      }

	      p->siguiente = (struct atributo *) malloc(sizeof(at));
	      if (!p->siguiente)
	      {
		 printf ("No hay memoria suficiente.\n");
		 break;
	      }
	      anterior_p = p;
	      p = p->siguiente;
	   }
	}
	fclose (fp);
	n_pos = t - 1;
	return;
}

/*
 * Funcion para inicializar la base de conocimiento
 */

ini_basec()
{
	int t;
	struct atributo *p, *p2;

	for (t=0;t<=n_pos;t++) {
		p = base_c[t].alista;
		while (p) {
			p2 = p;
			free (p);
			p = p2->siguiente;
		}
	}
	return (0);
}

esta_en (char ch, char *s)
{
	while (*s)
		if (ch == *s++)
			return 1;
	return 0;
}
<-->


Como apreciareis, hay algunas modificaciones.

Y ahora algunas aclaraciones. Muchos de vosotros os preguntareis que narices
tiene que ver esto con el hacking. Bueno, las aplicaciones que le deis a
un programa, un aparato o un objeto dependen de vuestra imaginacion, y de
ahi es de donde nace (solo nace) el hacking.

Para que os hagais una idea. Como creeis que funcionan los buenos programas
de auditoria de seguridad? Vamos, el funcionamiento de programas como
SATAN, SAINT o Nessus (los clasicos Tiger y COPS... no tanto)?

Muy simple. Son sistemas expertos. Cuanto mejor sea el sistema experto,
y mas completa este la base del conocimiento, mejor sera el diagnostico. Eso
creo que ya lo dejamos claro en el numero anterior.

Pero si la base de conocimiento se compone de fallos de seguridad detectados
en diferentes sistemas, aplicaciones, etc., y el motor de inferencia es el
adecuado, tenemos una herramienta util para auditar la seguridad.

Y si a esa herramienta la complementamos con otras de chequeo que le
proporcionen datos para establecer un criterio o elaborar nuevo conocimiento,
tendremos un programa que deberian tener todos los administradores.

Bueno, ya solo queda despedirnos hasta el proximo numero.

Have P/Hun
Falken