Departament d’Enginyeria Informàtica i M atemàtiques

Implementación de un sistema para preservar la privacidad de los usuarios de los motores de búsqueda en Internet mediante una red social

TITULACIÓN: Enginyeria técnica en telecomunicacions, especialitat telemàtica.

AUTOR: Alejandro Avilés Fernández DIRECTOR: Jordi Castellà Roca FECHA: Diciembre 2010

Resumen

La privacidad es un valor abstracto de los que se supone un derecho fundamental para cualquier persona. No obstante a esta concesión, al igual que otros muchos derechos fundamentales, no se ve libre de de ataques y violaciones por parte de terceras personas. Este proyecto aborda el tema de la privacidad en Internet, concretamente los motores de búsqueda. Éstos nos permiten encontrar información mediante una serie de algoritmos de búsqueda. Dichos motores, para ofrecer un servicio de calidad, deben diferenciar mediante un proceso de desambiguación a que se refiere el usuario con una búsqueda concreta (por ejemplo diferenciar el planeta Mercurio del elemento de la tabla periódica con el mismo nombre), y esto lo consiguen mediante la creación de perfiles de usuario. En mayo de 2006, AOL publicó un archivo que contenía todas las búsquedas realizadas por 658.000 de sus usuarios en los tres últimos meses. Cada usuario fue identificado sólo con un código numérico para proteger su identidad. Sin embargo, algunos investigadores analizando únicamente el registro de búsquedas usuarios supuestamente anónimos, fueron capaces de identificar a algunos de éstos. Por lo tanto, los motores de búsqueda tienen la posibilidad de vulnerar el derecho a la privacidad filtrando nuestros perfiles. Hasta el día de hoy, diversas propuestas han sido llevadas a la práctica con tal de enmascarar de diferentes maneras nuestras búsquedas y así alterar estos perfiles, pero con el inconveniente de mermar la calidad o el tiempo de respuesta del servicio de búsqueda. En este proyecto se ha implementado un método alternativo que hace uso de las redes sociales. A partir de ésta se han realizado una serie de tests y simulaciones para verificar su viabilidad.

Abstract

Privacy is an abstract concept to which all humans are entitled. However, as other rights, it’s not free against three parties attacks and violations. This project deals with Internet privacy, specifically the point related with search engines. The search engines, in order to offer an accurate service, must be able to tell between searches by a disambiguation process (for example, differentiate if the word Mercury refers to the planet or the element), and to achieve this goal they build user’s profiles. In May 2006, AOL published a file with all the searches that 658.000 users had made in the last three months. Each user was identified by a numeric code in order to protect his privacy. However, some people were able to identify some users with simply analyzing the data stored in the search register. Therefore, search engines may jeopardize our privacy filtering our user’s profile. Until today, many ways to mask our searches had been implemented, but they add the disadvantage of reducing the quality of service and increasing the response time. An alternative method that uses social networks had been implemented in this project. A series of tests and simulations had been done in order to verify its viability.

Resum

La privadesa es un valor abstracte que suposa un dret fonamental per a qualsevol persona. No obstant a aquesta concessió, de la mateixa manera que molts altres drets fonamentals, no es veu lliure d’atacs i violacions per part de terceres persones. Aquest projecte aborda el tema de la privadesa a Internet, concretament la dels motors de cerca. Aquests ens permeten trobar informació mitjançant una sèrie d’algoritmes de cerca. Aquests motors, per oferir un servei de qualitat, han de diferenciar mitjançant un procés de desambiguació a que es refereix l’usuari amb una cerca concreta (per exemple diferenciar el planeta Mercuri del element de la taula periòdica amb el mateix nom), i això s’aconsegueix mitjançant la creació de perfils d’usuari. Al maig de 2006, AOL va publicar un fitxer que contenia totes les cerques realitzades per 659.000 dels seus usuaris en els tres últims mesos. Cada usuari va ser identificat nomes per un codi numèric per protegir la seva identitat. Malgrat això, alguns investigadors analitzant únicament el registre de cerques d’usuaris suposadament anònims, van ser capaços d’identificar a alguns d’aquestos. Per la qual cosa, els motors de cerca tenen la possibilitat de vulnerar el dret a la privadesa filtrant els nostres perfils. Fins al dia d’avui, diverses propostes han estat portades a la practica amb la finalitat d’emmascarar de diferents maneres les nostres cerques i així alterar aquests perfils, amb l’inconvenient de disminuir la qualitat o el temps de resposta del servei de cerca. En aquest projecte s’ha implementat un mètode alternatiu que fa us de les xarxes socials. A partir d’aquest s’han realitzat una sèrie de tests i simulacions per verificar la seva viabilitat.

Índice de contenidos 1.

INTRODUCCIÓN .........................................................................................................................10 1.1. OBJETIVOS............................................................................................................................................13 1.2. JUSTIFICACIÓN .....................................................................................................................................13

2.

DISEÑO ........................................................................................................................................14 2.1. ARQUITECTURA...................................................................................................................................14 2.2. IDENTIFICANDO ADVERSARIOS.........................................................................................................15 2.3. DISEÑO DEL PROTOCOLO ...................................................................................................................15

2.3.1. 2.3.2. 2.3.3. 3.

Función Ψ. Determinación del nivel de exposición ............................... 16 Función Υ. Determinación del nivel de egoísmo ................................... 16 Valor de γ................................................................................................ 17

DECISIONES DE DISEÑO .....................................................................................................19 3.1. LENGUAJE DE PROGRAMACIÓN .........................................................................................................19 3.2. COMUNICACIONES ..............................................................................................................................20 3.3. DISEÑO: COMPONENTES....................................................................................................................21 3.4. IMPLEMENTACIÓN ..............................................................................................................................22

3.4.1. 3.4.2. 3.4.3. 3.4.4.

Servidor .................................................................................................. 22 Cliente..................................................................................................... 22 Clase para gestionar los usuarios on-line ............................................... 23 Base de datos .......................................................................................... 24

4.

JUEGO DE PRUEBAS..................................................................................................................26 4.1. CONEXIÓN AL SERVIDOR ....................................................................................................................26 4.2. NIVEL DE EXPOSICIÓN, FUNCIÓN Ψ.................................................................................................28 4.3. ESTIMACIÓN DE VECINOS ..................................................................................................................30 4.4. DETECTANDO USUARIOS EGOÍSTAS, FUNCIÓN Y ...........................................................................31

5.

SIMULACIONES Y RESULTADOS ...........................................................................................33 5.1. NÚMERO DE USUARIOS ......................................................................................................................33 5.2. NÚMERO DE AMIGOS Y LISTA DE AMIGOS........................................................................................33 5.3. ENTORNO DE LA SIMULACIÓN...........................................................................................................39 5.4. RESULTADOS .......................................................................................................................................39

5.4.1. 5.4.2.

Resultados de la red de 48 usuarios........................................................ 40 Resultados de la red de 96 usuarios........................................................ 43

6.

CONCLUSIONES ..........................................................................................................................45

7.

BIBLIOGRAFÍA............................................................................................................................46

8.

ANEXO 1: CUADRO RESUMEN DE LAS SIMULACIONES PARA LA RED SOCIAL DE 48 USUARIOS ..............................................................................................................................47

9.

ANEXO 2: CUADRO RESUMEN DE LAS SIMULACIONES PARA LA RED SOCIAL DE 96 USUARIOS ..............................................................................................................................49

Índice de figuras Figura 1 Esquema general de los componentes.............................................................. 21 Figura 2 Esquema de Interacción entre clases................................................................ 25 Figura 3 Escenario de pruebas........................................................................................ 26 Figura 4, Ejemplo de inicialización del servidor............................................................ 26 Figura 5. Ejemplo de conexión de un usuario al servidor .............................................. 27 Figura 6. Ejemplo del estado del servidor ...................................................................... 27 Figura 7. Estado inicial de un usuario ............................................................................ 28 Figura 8. Ejemplo 1 de búsqueda siguiendo el protocolo............................................... 28 Figura 9. Ejemplo 2 de búsqueda siguiendo el protocolo............................................... 29 Figura 10. Ejemplo 3 de búsqueda siguiendo el protocolo............................................. 29 Figura 11. Ejemplo 4 de búsqueda siguiendo el protocolo............................................. 29 Figura 12. Estado inicial de la estimación de vecinos.................................................... 30 Figura 13. Actualización de la estimación de vecinos.................................................... 30 Figura 14. Actualización de la estimación de vecinos.................................................... 31 Figura 15. Actualización de la estimación de vecinos.................................................... 31 Figura 16. Interacción entre dos usuarios utilizando el protocolo.................................. 31 Figura 17 Evolución de la probabilidad de aceptar una búsqueda tras 20 peticiones. ... 32 Figura 18 Evolución de la probabilidad de aceptar una búsqueda tras 40 peticiones .... 32 Figura 19 Evolución de la probabilidad de aceptar una búsqueda tras 150 peticiones .. 32 Figura 20 Distribución de usuarios red 48 usuarios ....................................................... 35 Figura 21 Distribución individual de usuarios por nombre de amigos .......................... 35 Figura 22 Distribución de usuarios red 96 usuarios. ...................................................... 37 Figura 23 Distribución individual por nombre de amigos.............................................. 38 Figura 24. Gráfico sobre el reenvío de búsquedas.......................................................... 42 Figura 25. Gráfico sobre las peticiones enviadas al motor de búsqueda........................ 43 Figura 26. Gráfico sobre el reenvío de búsquedas.......................................................... 44

Índice de tablas Tabla 1 Resultado simulaciones para diferentes valores de γ ........................................ 18 Tabla 2 Nomenclatura de los nombres de usuario.......................................................... 24 Tabla 3 Relación de búsquedas enviadas a Usuario_1 ................................................... 30 Tabla 4 Distribución de usuarios .................................................................................... 34 Tabla 5 Distribución de usuarios .................................................................................... 37 Tabla 6 Entorno de la simulación ................................................................................... 39 Tabla 7. Resumen de las simulaciones en la red de 48 usuarios .................................... 40 Tabla 8. Detalle sobre el número de saltos..................................................................... 40 Tabla 9. Conexiones del usuario con más saltos ............................................................ 41 Tabla 10. Conexiones del usuario con menos saltos ...................................................... 41 Tabla 11. Datos sobre el reenvío de búsquedas.............................................................. 42 Tabla 12. Datos sobre las peticiones enviadas al motor de búsqueda ............................ 42 Tabla 13. Resumen de las simulaciones en la red de 96 usuarios .................................. 43 Tabla 14 Detalle sobre el número de saltos.................................................................... 43 Tabla 15. Datos sobre el reenvío de búsquedas.............................................................. 44 Tabla 16 Datos sobre las peticiones enviadas al motor de búsqueda ............................. 44

Introducción

1. Introducción Hoy en día, nuestra sociedad se encuentra inmersa en un proceso de globalización cuya más significativa muestra se halla en Internet. Millones de datos son procesados cada día desde cualquier rincón del planeta por millones de usuarios. Entre tanta información almacenada una de las herramientas más necesarias en la red es aquella capaz de encontrar lo que cada usuario desea. Los motores de búsqueda son la respuesta de las compañías a esta necesidad. Se han convertido en la página principal de la mayoría de los navegadores y en un recurso habitual de millones de usuarios. Gracias a ellos, podemos realizar búsquedas de información concreta, obteniendo como resultado un listado de enlaces hacia páginas web que contienen esta información. Con tal de mejorar su servicio, los buscadores son capaces de almacenar datos sobre las búsquedas de los usuarios y crear perfiles. Estudios estadísticos demuestran que el 68% de los usuarios que utilizan estos servicios de búsquedas se quedan con resultados mostrados en la primera página y que además, el 92% de los usuarios solo miran la información de las tres primeras páginas de resultados. Los buscadores, con tal de ofrecer un mejor servicio, deben mostrar los enlaces más interesantes en estas primeras páginas. Sin embargo no es fácil conocer cuales son los enlaces que desean los usuarios. Un ejemplo lo tenemos cuando buscamos la palabra mercurio que puede referirse al elemento de la tabla periódica o al planeta del sistema solar. La palabra desambiguación hace referencia al proceso de identificar el sentido correcto cuando una palabra tiene varios significados. El proceso de desambiguación requiere el conocimiento de los intereses del usuario o el contexto de la búsqueda. Ambos pueden deducirse a partir de lo que llamaremos perfil del usuario. Por ejemplo, si un determinado usuario ha hecho una búsqueda de “sistema solar” antes de “mercurio”, el motor de búsqueda almacenara esta información en el perfil de usuario y gracias a eso, puede asumir que “mercurio” se refiere al planeta y no al elemento de la tabla periódica. Acorde con todo esto, el buscador pondrá los resultados que hacen referencia al planeta mercurio en las primeras páginas. Aunque el uso de perfiles mejora la experiencia del usuario, contienen información que puede considerarse privada y personal. Si un determinado usuario ha buscado un sitio concreto, puede referirse al lugar donde vive. Si ha buscado el nombre de alguna enfermedad, se puede pensar que él o alguien cercano a él sufre esa enfermedad. Esta situación puede resultar una amenaza para la privacidad de los usuarios, y el perfil puede ser usado en su contra. Un ejemplo de esta situación lo tenemos en el escándalo de AOL, donde 20 millones de búsquedas echas por 658000 usuarios fueron publicadas. Pese a mostrar las búsquedas de cada usuario con una identificación que no les relacionaba, las búsquedas hechas constataban lo mencionado anteriormente. Búsquedas de familiares, enfermedades, los propios nombres o incluso maneras de herir a personas o a si mismos entre otros ejemplos, demuestra que los motores de búsqueda no pueden proteger debidamente la privacidad de los usuarios, y estos deberían usar algún tipo de mecanismo para evitar que los buscadores tengan un perfil “detallado”. No obstante, para que las herramientas de búsqueda sigan siendo efectivas, debe existir un balance, un equilibrio, entre la 10

Introducción privacidad y la calidad del servicio. Si un usuario quiere tener un grado de privacidad muy alto, seguramente recibirá un servicio deficiente. Por el contrario, si desea un servicio muy eficiente, su privacidad se verá mermada. A día de hoy, podemos encontrar varias soluciones al problema planteado. Para explicarlas, podemos definir cuatro niveles de privacidad diferentes: Pseudo identidad, identidad de grupo, sin identidad, y sin información personal. El primer nivel , pseudo identidad, es el utilizado por AOL al publicar su lista de búsquedas, identificando al usuario con un número que en principio no le relaciona, pero que al examinar con detalle las búsquedas realizadas por esa misma identificación, podemos extraer información privada. Este nivel no evita que el motor de búsqueda cree un perfil de usuario y no garantiza la privacidad del usuario. La identidad de grupo se basa en la idea de compartir un perfil de usuario único para todo un grupo. El motor de búsqueda no puede identificar a que usuario pertenece cada búsqueda, solo crear un perfil para todo el grupo. Ganamos privacidad, pero reducimos ligeramente la calidad del servicio. Podemos implementar esta solución de tres maneras: Utilizando un Proxy para construir el grupo, enviar búsquedas aleatorias, enviando búsquedas echas por otros usuarios. El primer método tiene un claro problema. El motor de búsqueda no puede crear un perfil de usuario, pero el Proxy sí puede hacerlo, por lo que a nivel de usuario no nos garantiza privacidad. Respecto al envío de búsquedas aleatorias, en la actualidad tenemos dos implementaciones para Firefox: TrackMeNot: Envía búsquedas aleatorias cuando la actividad del usuario es baja con el fin de no afectar al usuario en horas de trabajo. Este método proporciona privacidad al usuario ocultado sus intereses con otros falsos. No obstante, este método añade tráfico a la red, y reduce la efectividad del servicio. Además, el buscador podría separar las búsquedas falsas de las autenticas analizando la franja horaria del usuario, p.e. se pueden separar las horas laborales y deducir que las búsquedas realizadas fuera de estos horarios son hechas por TrackMeNot. De la misma manera, analizando el tiempo entre búsquedas podemos llegar a la misma conclusión. GooPIR: Envía búsquedas falsas juntamente con las auténticas. De esta manera el buscador no puede diferenciar que búsquedas son las verdaderas y no puede crear un perfil de usuario auténtico. El diseño de este método no introduce tráfico en la red ni en el buscador. Sin embargo es incapaz, debido a su arquitectura, de enviar frases completas. Los usuarios únicamente pueden buscar palabras. Con respecto al envío de búsquedas por parte de otros usuarios, tenemos dos maneras de implementar este método. El primer sistema usa sectores de memoria compartidos por un grupo de usuarios para almacenar las búsquedas y leer sus respuestas. No hay conexión

11

Introducción entre usuarios. Las búsquedas y sus respectivas respuestas deben estar encriptadas para conseguir confidencialidad. Cuando un usuario realiza una consulta, la cifra y la guarda en un sector de memoria compartida. A continuación, cuando otro usuario quiere realizar una consulta propia, accede a ese sector de memoria y se encuentra con la consulta del primer usuario. Entonces, envía la consulta al WSE y guarda la respuesta cifrada en el mismo sector. Con este método, no se requiere una compañía externa que cree los grupos, pero se debe usar un protocolo de enrutamiento específico para preservar la privacidad de los usuarios al acceder al medio. Los principales defectos de este sistema son que debe ser capaz de manipular un volumen de información muy grande. Los usuarios deben analizar el sector de memoria compartido de manera regular, introduciendo tráfico considerable en la red. Otro método es el UPP (useless user profile). En este método, un usuario no envía directamente sus búsquedas, esta tarea debe realizarla otro usuario dentro del grupo. De esta manera, el buscador no podrá generar un perfil real de cada usuario. Un punto importante de este sistema es que ningún usuario debe saber de quien proviene la búsqueda. Esto se consigue mediante un protocolo criptográfico. Además, se requiere una arquitectura cliente-servidor. El nodo central escucha las peticiones, y al recibir un numero n determinado, crea un nuevo grupo y envía las IP y los números de puertos a cada cliente. Entonces, los miembros del grupo establecen una red de conexiones entre ellos sin el nodo central. En diferentes test en entornos reales, este sistema tarda 5.2 segundos con un grupo de tres usuarios y una clave de 1024 bits. Entre los diferentes lastres de este sistema, destaca que los grupos deben ser creados. Esto supone un retardo añadido. Se requiere un número grande de usuarios con tal de obtener un tiempo de respuesta aceptable. El siguiente nivel de privacidad, Sin identidad, plantea los siguientes aspectos: El buscador no puede acceder a la identidad del usuario y no puede generar un perfil. Todas las implementaciones de este método utilizan un canal anónimo de comunicación. El ejemplo más claro de este método es el Tor Project, con diversos plugins implementados para Firefox. La principal desventaja de este método es el tiempo de respuesta. Una búsqueda mediante Tor es 25 veces más lenta que una búsqueda directa. Otro ejemplo de no identificado, es el private information retreival (PIR), que permite a los usuarios eliminar información en un servidor. Este método requiere la colaboración de los buscadores, que no tienen ningún interés en proteger la privacidad de los usuarios a costa de incrementar el coste computacional y la comunicación con ellos. Y por ultimo, tenemos el nivel de privacidad Sin información personal: La identidad del usuario y la descripción de los datos que él desea no son accesibles para el buscador. Este método proporciona el mejor nivel de privacidad, pero añade un coste computacional y de comunicación que no lo hacen usable a la práctica. Además de los métodos explicados, existe un método más simple para mantener la privacidad de los usuarios: Acceder a Internet usando una dirección IP dinámica y utilizar un navegador sin el uso de cookies. No obstante, no podemos controlar la

12

Introducción política de renovación de dirección IP del operador, que puede dar y renovar direcciones IP a partir de las relaciones de IP/MAC. También existe el hecho de que ciertos usuarios requieren direcciones IP estáticas y que un navegador sin cookies pierde su funcionalidad en un gran número de aplicaciones web.

1.1.

Objetivos

En este proyecto, implementaremos la solución propuesta en [1] que mantiene la efectividad de los motores de búsqueda a la vez que preserva la privacidad de los usuarios. El protocolo usa las redes sociales para enmascarar las búsquedas. Una red social es una comunidad de usuarios donde pueden compartir datos y servicios. Los usuarios están conectados los unos con los otros directamente sin necesidad de un nodo central, de manera similar a una red P2P, y únicamente conociendo a sus “vecinos” inmediatos. Por este motivo no es necesario crear grupos. Serán los propios amigos por defecto que tenga el usuario en dicha red los que formaran el grupo. Además, el sistema aprovecha que las relaciones sociales implican, en su mayoría, que las personas comparten ciertos intereses, por lo que el perfil que el motor de búsqueda intentará crear no quedará muy afectado y podrá ser usado para proporcionar un servicio eficaz al grupo. En el protocolo propuesto en [1] cuando un usuario realiza una búsqueda la envía directamente al buscador o la redirige a uno de sus vecinos de la red social. El receptor de la búsqueda a su vez, tendrá que decidir si es él el que la publica al buscador o la vuelve a reenviar a otros usuarios. Así, la búsqueda ira pasando de usuario en usuario hasta que alguien decida enviarla. De esta manera, el buscador no puede diferenciar a quien pertenece cada búsqueda.

1.2.

Justificación

Las propuestas existentes no ofrecen una solución completa, ya sea por: 1. El elevado tiempo de respuesta (soluciones basadas en el Tor Project). 2. La sobrecarga a los motores de búsqueda (TrackMeNot). 3. La imposibilidad de buscar frases (GooPIR). La implementación de [1] permitirá evaluar su viabilidad mediante el análisis de los requisitos funcionales y los costes computacionales y de comunicación.

13

Diseño

2. Diseño En este apartado se describe el funcionamiento del protocolo propuesto en [1].

2.1.

Arquitectura

Las entidades más importantes de nuestro proyecto son: •

Usuarios (Un). Envían peticiones al buscador. Su principal motivación es proteger su privacidad individual.

•

Motor de búsqueda (Web Search Engine, WSE). Es el servidor que mantiene la base de datos. Puede ser, por ejemplo, Google, Yahoo, Microsoft Live Search entre otros. Estas entidades no tienen por que querer preservar la privacidad de sus usuarios.

El esquema planteado, requiere que los usuarios se organicen en redes sociales. El protocolo debe mantener la privacidad de un usuario frente al buscador, aprovechando el concepto de vecino de los usuarios on-line de la red social. De esta manera, un usuario U genera una petición de búsqueda y puede enviarla directamente al WSE o reenviarla a sus vecinos (un vecino representa una relación directa en la red social). El vecino que recibe la petición, puede enviarla al WSE o volver a reenviarla a uno de sus propios vecinos. La petición va siendo reenviada hasta que alguien decide enviarla al buscador. Vamos a considerar un grupo G formado por el usuario U y sus vecinos. Si las búsquedas realizadas por todos los usuarios de G son distribuidas a través de él, el perfil de U se distorsiona con búsquedas que no le pertenecen. De esta manera, el perfil de U y el usuario U no pueden ser relacionados por el buscador. Por consiguiente, su privacidad no se ve amenazada. Debemos cumplir dos objetivos: 1. El protocolo debe ofrecer un tiempo de respuesta aceptable. Los grupos ya están creados de antemano, por lo que el protocolo se ve librado de esta tarea, traduciéndose en una reducción significativa del tiempo. No usaremos canales anónimos como Tor. 2. El WSE no debe ser capaz de obtener un perfil de usuario preciso. No obstante, los perfiles deben ser útiles hasta cierto nivel, con tal de seguir ofreciendo un buen servicio. En nuestro esquema, el WSE crea un perfil de usuario no detallado, conteniendo búsquedas de otros usuarios de su red social. Asumimos que en una red social, ciertos miembros compartirán intereses similares con sus vecinos directos. El perfil estará distorsionado pero seguirá siendo útil hasta cierto nivel para el WSE.

14

Diseño Como último punto, con tal de evitar que algunos vecinos abusen del sistema creado por el protocolo (usuarios que nunca envíen peticiones de otros usuarios por ejemplo), existirá un mecanismo de recompensa. Los usuarios que no cooperen serán eliminados del sistema.

2.2.

Identificando adversarios.

En el sistema propuesto en [1] existen tres adversarios: 1. Motor de búsqueda (WSE): Es el adversario principal de nuestro escenario. Almacena perfiles de usuario para sus propios intereses. El buscador conoce quien (La dirección IP, cookies…) hace cada búsqueda. Esta información se guarda durante un determinado periodo de tiempo. Por ejemplo, Google la guarda durante 9 meses. 2. Usuarios deshonestos: Son usuarios que pueden crear un perfil mediante las búsquedas de los otros usuarios. Estos usuarios saben quien les ha enviado las búsquedas. 3. Usuarios egoístas: No siguen del todo el protocolo. Utiliza a los demás usuarios para publicar sus búsquedas pero no acepta búsquedas de los demás.

2.3.

Diseño del protocolo

Vamos a tomar como ejemplo a un usuario Ui, que quiere enviar una búsqueda q siguiendo nuestro esquema. Ui tiene k vecinos en la red social, (N1,…, Nk). Al ejecutar el protocolo para realizar la búsqueda, seguiríamos los siguientes pasos: •

Ui decide si enviar la búsqueda directamente al buscador o a un determinado vecino. Para tomar esta decisión, el protocolo se basara en el nivel de privacidad alcanzado por Ui. La función Ψ devolverá el usuario (un vecino o el mismo Ui) que debe enviar la búsqueda. En la siguiente sección veremos esta función con detalle. Si Ψ determina que debe ser el mismo usuario el que envíe la búsqueda, el protocolo termina aquí. En caso contrario, seguimos con la ejecución.

•

Vamos a suponer que la función Ψ decide enviar al vecino Ni la búsqueda q para proteger la privacidad de Ui. Entonces, Ui reenvía q a Ni y le pide a este que la acepte. Ni a su vez, aceptara o rechazara la búsqueda en función del nivel de egoísmo de Ui respecto a Ni. De esta tarea se encargará la función Υ, que decidirá si Ni debe aceptar q o no. Esta función la veremos con detalle mas adelante. Pueden ocurrir dos cosas: o Ni acepta q, ejecuta la función Ψ para decidir si envía la petición al buscador o la reenvía a un vecino. En ambos casos, una vez realizada la búsqueda, Ni enviará la respuesta A al usuario Ui.

15

Diseño o Ni rechaza q, Ui decide mediante Ψ quien es el siguiente candidato para enviar q. Este proceso se repite hasta que alguien decida aceptar q, o hasta que el candidato sea Ui, que enviará la búsqueda él mismo. •

Supongamos que un usuario Uj acepta q de un vecino Ul y la envía al buscador. El usuario Uj recibirá la respuesta A y la reenviara a Ul, que no tiene que ser el usuario original (puede ser un vecino de un vecino de Ui por ejemplo). Este proceso se repetirá hasta que la respuesta A llegue al usuario Ui que generó originalmente q. Aquí el protocolo termina.

2.3.1. Función Ψ. Determinación del nivel de exposición Siguiendo con el protocolo, U genera una búsqueda q. Como ya hemos dicho anteriormente, U ejecuta Ψ para decidir a quien de su lista de vecinos debe enviar q. El propósito de Ψ es preservar la privacidad de U. Con tal de realizar esta función, Ψ hace una estimación del numero de búsquedas generadas por U que cada vecino “probablemente” ha enviado al buscador. Sea αi el número de búsquedas (generadas por U) enviadas al buscador por un vecino al que llamaremos N. Hay que tener en cuenta que solo podemos realizar una estimación, ya que U no puede conocer con certeza si las búsquedas aceptadas por N han sido enviadas hacia el buscador por este, o reenviadas a otro vecino. De todas maneras, U conoce el número de búsquedas que N ha aceptado. A este número le llamaremos τi. Así, el cálculo de la estimación quedaría: αi = τi/ número de vecinos de N En principio, no podemos conocer el número de vecinos de N. La estimación de este número la haremos siguiendo el método número 3 del trabajo [1]. Este método, utiliza el número de búsquedas que cada vecino Ni ha intentado enviar a U. Entonces, asumiremos que el vecino que ha enviado más búsquedas a U tiene únicamente una conexión directa, el segundo vecino, tendrá dos conexiones, y así sucesivamente. La idea de esta estimación es que los vecinos con más conexiones directas enviaran menos búsquedas a cada conexión (siendo U una de ellas). El nivel de privacidad de un usuario dependerá de si αi se mantiene prácticamente igual para todos los miembros de la red. Por lo tanto, esta función devolverá el usuario con αi más pequeño.

2.3.2. Función Υ. Determinación del nivel de egoísmo Para calcular el nivel de egoísmo, vamos a considerar el siguiente escenario: Un usuario U recibe una petición q de un vecino al que llamaremos N. U ejecutará la función Υ para decidir si acepta o no dicha búsqueda. El objetivo de esta función es castigar a los usuarios que actúen saltándose el protocolo. La función Υ será un mecanismo que funcionará de la siguiente manera: 16

Diseño

•

Inicialmente, U asignará a cada vecino una probabilidad p (100% al inicializarse) de aceptar búsquedas de este. La nomenclatura que utilizaremos para explicar el calculo de esta probabilidad durante el transcurso del uso del protocolo será pU,N (probabilidad de que U acepte una búsqueda de N).

•

Entonces, si U recibe una búsqueda q del usuario N, U aceptara la búsqueda con una probabilidad pU,N .

•

Si U acepta la búsqueda: 1. N incrementa su propia probabilidad de aceptar búsquedas de U: pN,U = p N,U + 2· γ Donde γ es una constante definida por el sistema, de la q hablaremos mas adelante. 2. U decrementa la probabilidad de aceptar búsquedas de N: pU,N = pU,N – γ

•

Si U rechaza q, entonces N decrementa la probabilidad de aceptar búsquedas de U: pN,U = pN,U - γ

Ambas operaciones se hacen con tal de incentivar a los usuarios para aceptar búsquedas de sus vecinos. Un usuario concreto U1 que reenvíe varias búsquedas a un mismo usuario U2 sin a cambio aceptar búsquedas (usuario egoísta) al final tendrá una probabilidad pU2,U1 = 0. Si U sigue con esta conducta, al final le pasara lo mismo con todos los usuarios, y se vera forzado a enviar las búsquedas a Google directamente, poniendo en peligro su privacidad, que justamente es lo que intentamos evitar mediante el uso de este protocolo. Decrementando γ por rechazar y aumentando γ·2 por aceptar, conseguimos que el protocolo castigue más a los usuarios que sistemáticamente rechazan todas las búsquedas en vez de a los que aceptan y rechazan búsquedas de manera alternativa.

2.3.3. Valor de γ Para darle un valor a esta constante en nuestro sistema, nos basaremos en las simulaciones extraídas de [1]. Las simulaciones para diferentes valores de γ, se han hecho en una red social de 400 usuarios, con un 10% de usuarios egoístas, donde cada usuario ha generado 971 búsquedas. Para cada γ se han hecho 1000 tests y se ha calculado la media de estos resultados, dando origen a la tabla siguiente:

17

Diseño

γ % Usuarios egoístas expuestos 0.00 2,5% 0,01 97,5% 0,02 100% 0,03 100% 0,04 100% 0,06 100% 0,08 100% 0,10 100%

% Usuarios honestos expuestos 55,8% 46,3% 44,1% 48,0% 48,3% 48,8% 53,0% 69,4%

Tabla 1 Resultado simulaciones para diferentes valores de γ

Si extraemos conclusiones de esta tabla, vemos que el resultado óptimo se da cuando la constante vale 0.02 (2%). Para valores más pequeños, disminuimos el número de usuarios egoístas que se ven afectados. Para valores más grandes, seguimos teniendo el mismo número de usuarios egoístas afectados y además, el porcentaje de usuarios honestos afectados aumenta.

18

Decisiones de diseño

3. Decisiones de diseño En este apartado, hablaremos sobre las decisiones de diseño tomadas para implementar el protocolo [1] así como de los criterios que nos han llevado a tomar estas decisiones.

3.1.

Lenguaje de programación

Para la implementación del protocolo [1], debemos usar un lenguaje de programación que cumpla una serie de requisitos mínimos vistos en el apartado anterior, impuestos por las características de la arquitectura de éste. El protocolo aprovecha las relaciones entre usuarios extraídas de redes sociales para generar los grupos. La principal implicación de este hecho, es que nos encontraremos con diferentes usuarios, accediendo desde diferentes dispositivos y sistemas operativos y por lo tanto, el código del protocolo debe ser ejecutable para cualquiera de estos usuarios si queremos obtener el mayor número posible de usuarios participando. Por ello, el lenguaje escogido debe ser multiplataforma. Con el mismo fin, obtener el mayor número de usuarios participando en el protocolo, el lenguaje escogido debe estar ampliamente extendido. Debido a estos factores, los principales candidatos son los lenguajes Java y C. Como lenguaje de programación para la implementación del protocolo, hemos escogido el lenguaje Java por una de sus características más importantes, el ser multiplataforma. Java está diseñado para soportar aplicaciones que serán ejecutadas en los más variados entornos de red, desde Unix a Windows Nt, pasando por Mac, estaciones de trabajo, móviles, PDA, etc., sobre arquitecturas distintas y con sistemas operativos diversos. Además, Java especifica los tamaños de sus tipos de datos básicos y el comportamiento de sus operadores aritméticos, de manera que los programas son iguales en todas las plataformas (Máquina Virtual Java, JVM). Todas estas características son básicas a la hora de implementar un protocolo pensado para hacer uso de las redes sociales, si tenemos en cuenta el hecho que hoy en día, el uso de Internet está tan extendido que podemos conectarnos desde casi cualquier lugar y no solamente a través de un ordenador personal o uno portátil si no que cada vez encontramos más dispositivos portátiles con capacidad de conexión a la red(móviles, PDAs, Consolas portátiles etc.), independientemente del sistema operativo. Por ello, el protocolo debe ser compatible con cualquiera de estos dispositivos y sistemas operativos, siendo JAVA el candidato idóneo.

19

Decisiones de diseño

3.2.

Comunicaciones

Una vez escogido el lenguaje de programación, solo nos queda elegir las herramientas que este nos ofrece para implementar el protocolo [1]. Dos opciones interesantes que nos ofrece el lenguaje JAVA son JXTA y los sockets. JXTA es un conjunto de protocolos peer-to-peer (P2P) que permiten conectar diferentes dispositivos de red (teléfonos móviles, PDA, ordenadores personales) entre si para comunicarse y colaborar como peers, compartiendo recursos y servicios. Los protocolos JXTA son independientes de cualquier lenguaje de programación, y existen múltiples implementaciones para diferentes entornos. JXTA nos permite construir servicios y aplicaciones siguiendo la arquitectura P2P. Al ser los protocolos independientes tanto del lenguaje de programación como de los protocolos de transporte, nos permite que dispositivos con software completamente diferente puedan interactuar entre si. La red JXTA consiste en una serie de nodos interconectados, llamados peers. Se pueden auto-organizar en grupos, que compartan una serie de servicios comunes, como compartir documentos, aplicaciones chat etc. La manera de compartir recursos y servicios en JXTA es mediante la publicación y descubrimiento de anuncios, en forma de documentos XML. No hay que olvidar el objetivo principal que persigue protocolo [1]: ofrecer no solo una nueva solución al problema de la privacidad en relación con los motores de búsqueda, sino también que esta sea más rápida y eficiente que las actuales. Con este fin, otra opción que se nos presenta para la implementación es basarnos directamente en sockets, lo que nos permitiría controlar las conexiones entre usuarios con mayor flexibilidad. Un socket es una un concepto abstracto que permite comunicar dos programas entre si e intercambiar flujos de datos que se define por una dirección IP, un protocolo de transporte y el número de puerto. Conociendo la dirección IP de un amigo, podremos establecer una conexión directa y transmitirle nuestra búsqueda. Así, pese a que los sockets sean en general una arquitectura cliente-servidor, podemos obviar tanto el nodo central (el servidor de la red social) como servidores DNS para la ejecución del protocolo y en cambió realizar conexiones directas entre vecinos, lo que nos acercaría más a la arquitectura de una red P2P como es el JXTA pero realizando las conexiones de una manera mucho más directa.

20

Decisiones de diseño

3.3.

Diseño: Componentes

Servidor: Es una entidad que simula el servicio de usuarios de una red social, como podría ser Windows Live Messenger o Facebook. En una red social, encontramos una serie de usuarios unidos entre ellos mediante relaciones de amistad o interés de algún tipo. No todos los usuarios son visibles entre ellos, únicamente aquellos con una relación directa. Esto es verdad para el primer caso, Windows Live, no obstante en Facebook nos encontramos con el hecho que si podemos conocer la lista de los amigos de una de nuestras conexiones directas pero teniendo en cuenta los diferentes niveles de privacidad configurables desde una cuenta de Facebook, a efectos prácticos nos encontramos con que únicamente podemos interactuar de manera completa con nuestras conexiones directas. Un usuario, al conectarse a la red social, primero lo hace al nodo central (en este caso nuestro servidor) para notificar que a partir de ese momento esta online y a su vez, recibir información sobre que usuarios de su circulo de amistad están conectados. El servidor, debe acceder a una pequeña base de datos en la que almacenará los contactos que tiene cada usuario. Base de datos: Contendrá una tabla donde almacenará datos sobre los usuarios. Solo debe ser accesible al servidor de la red social, por lo que los usuarios no interactuarán directamente con ella. Cliente: Equivale tanto a un usuario de la red social como a un usuario del motor de búsqueda. El cliente, emula la conexión al nodo central de las redes sociales para confeccionar la lista de usuarios de nuestro grupo de amistades conectados y sus direcciones IP. Una vez realizada esta operación, el cliente se encargará básicamente de tres tareas: • • •

Aceptar o rechazar peticiones de búsquedas, siguiendo el protocolo. Procesar búsquedas según el protocolo, ya sean propias o externas. Enviar peticiones de búsqueda a Google y recibir los resultados.

En la Figura 1, podemos ver la interacción entre los componentes.

Figura 1 Esquema general de los componentes

21

Decisiones de diseño

3.4.

Implementación

Una vez visto el funcionamiento del protocolo pasaremos a su implementación en Java mediante sockets. Crearemos una clase servidor, que nos proporcionará una lista de los usuarios conectados en cada momento, simulando así una lista de usuarios como podría ser la que ofrecen servicios como Messenger o Facebook, totalmente independiente del protocolo.

3.4.1. Servidor Esta clase implementa un simulador de un servidor externo de la red social. Esta parte del código, se encarga únicamente de recibir notificaciones de conexiones y desconexiones de los usuarios y acceder a la base de datos para almacenar datos útiles de los usuarios, como su dirección IP. Los usuarios establecen una conexión con el servidor, y este les proporciona la lista de usuarios conectados que pertenecen a su grupo de amistades directas. Para ello, deberá acceder a una base de datos en la que estarán almacenadas dichas relaciones. Esta clase, está implementada a partir de un ejemplo sencillo de servidor socket tcp multihilo. Este servidor es solo un emulador de un servicio de una red social, por lo que simplemente nos interesa recibir el estado de los usuarios y separarlos por grupos de amigos sin hacer hincapié en la seguridad de éste. La clase servidor se encarga de: • Inicializar un socket del tipo Server, que estará escuchando en un bucle por el puerto indicado (el 1984). • A partir de esta situación, el servidor se limita a escuchar en espera de alguna petición por parte de cliente. Esta petición puede ser cualquiera de las siguientes: o Petición de conexión o Actualización o Petición de desconexión • En el caso de realizarse una conexión con el servidor, se crea un hilo nuevo que se encarga de diferenciar el tipo de petición a tratar y actuar en consecuencia. • Si se trata de una petición de conexión, el servidor realiza las siguientes tareas: o Identifica al usuario de la petición. o Accede a la base de datos y carga los datos de este usuario. o Establece un diálogo en el que transmite al usuario la lista de los usuarios conectados que pertenezcan a su grupo de amistades. o Actualiza el estado del usuario que a partir de ahora parecerá como “conectado”. • Si recibe una desconexión actualiza la lista de usuarios conectados. • En las peticiones de actualización por parte de los clientes, lo único que hace es reenviar la información sobre la lista de usuarios conectados.

3.4.2. Cliente La clase cliente, por su parte, gestiona la conexión/desconexión individual de un usuario con el servidor para así confeccionar un array con la lista de los usuarios conectados que

22

Decisiones de diseño participarán en el protocolo y sus respectivas direcciones IP. No obstante, el cliente, una vez recibida la lista de usuarios conectados, debe ser capaz de escuchar peticiones de otros usuarios y enviar sus propias peticiones. Por lo tanto, lo primero que hace el hilo principal de esta clase es abrir un hilo paralelo de la clase receptor, que estará a la espera de recibir conexiones de otros usuarios y gestionar estas peticiones según dicte el protocolo en cada caso. Seguidamente, abre una conexión con el servidor indicándole que a partir de ahora estará conectado y disponible para los demás usuarios. Para ello recibe una lista de los usuarios online de su grupo de amistades. Al inicializarse, la clase cliente: • •

• •

Crea un hilo secundario que queda a la espera de peticiones de otros usuarios del protocolo. Inicia un dialogo con el servidor de la red social: o Le indica al servidor que este usuario pasa a estar conectado o Recibe del servidor la lista de usuarios conectados que forman parte de su lista de amigos Crea un objeto de la clase users_online donde almacena la lista de usuarios conectados e inicializa los valores por defecto del protocolo. Queda en espera de que el usuario genere alguna búsqueda.

3.4.3. Clase para gestionar los usuarios on-line La clase users_online, nos permite identificar a cada usuario y además, darle los atributos necesarios para ejecutar el protocolo en cuestión: • Nombre • Dirección IP, • Identificador numérico • El estado del usuario (conectado/desconectado). Cada usuario genera un array de users_online donde almacena los datos de los usuarios de su lista de amigos. Las siguientes variables que hemos definido son las que nos permiten hacer uso del protocolo de búsqueda que estamos implementando. Para cada amigo, tendremos: • • • • •

La estimación de búsquedas que ha enviado por nosotros (en principio no podemos saber si todas las que acepta son enviadas por él o simplemente las reenvía a otro). El total de búsquedas aceptadas por el usuario El total de búsquedas que este usuario nos ha enviado a nosotros. La probabilidad de aceptar una búsqueda de este usuario. Un flag que nos indicará si el usuario ha rechazado nuestra búsqueda y nos permitirá saltárnoslo en los siguientes intentos.

Y además, como variables de nuestro propio usuario tendremos: •

La media de número de saltos que realizan las búsquedas.

23

Decisiones de diseño •

La media de tiempo que se tarda desde el envío de la búsqueda hasta que recibimos la respuesta.

Esta información se almacena para evaluar el funcionamiento del protocolo implementado. En una versión final no se almacenaría esta información porque afectaría a la privacidad de los usuarios.

3.4.4. Base de datos Con tal de manipular cómodamente la base de datos y sus tablas, hemos creado una serie de scripts en Java, que nos permite resetear todos los usuarios, asignar puertos por grupos etc. Dentro de la base de datos, se ha creado una tabla para cada red social con una serie de campos, algunos de ellos propios de una red social y otros en cambio únicamente existen con el fin de llevar a cabo simulaciones. Los campos son los siguientes: Nombre_usuario: El nombre del usuario de la red social, equivale a su vez a un usuario del motor de búsqueda. En principio puede tener cualquier valor, no obstante, para facilitar el acceso a los datos y evitar colisiones, utilizaremos la nomenclatura “Usuario_X”, donde X será un numero del 1 al valor máximo de usuarios en la red social en concreto, así, podremos identificar al usuario por este parámetro (No ocurre así en entornos reales, donde es posible que un usuario comparta nombre con otro, y se distinga de él por algún otro tipo de identificador único para cada usuario). En nuestro caso, nos encontramos que las diferentes redes tendrán como nombre de usuario: Red social 1 Red social 2

Usuario_1-Usuario_48 Usuario_1-Usuario_96

Tabla 2 Nomenclatura de los nombres de usuario

Amigos: Una lista con el nombre de los amigos del usuario. La lista no es mas que un texto, donde separamos los usuarios por el carácter “;”. Por ejemplo, si el usuario uno es amigo del dos y del tres, en su campo amigos, aparecerá: “Usuario_1;Usuario_2;Usuario_3;”. Se ha optado por agregar el propio usuario a su lista de amigos, aunque este no entra en el cómputo del número total de amigos. La lista de amigos se genera de manera aleatoria a partir de unos parámetros que explicaremos más adelante. Estado: Campo que puede adquirir dos valores, 0 ó 1, conectado/desconectado. Por defecto encontraremos un 0. El servidor, una vez recibida una notificación de conexión por parte de un usuario, pone el estado a 1. Así, el servidor solo nos devolverá de nuestra lista de amigos aquellos que tengan su estado a 1. Dir_ip: Dirección IP del usuario. En las simulaciones, trabajaremos con la IP local. En entornos reales, este campo almacenaría la IP pública. Este campo se actualiza cada vez que alguien accede al servidor de la red social.

24

Decisiones de diseño Puerto: Para las simulaciones, deberemos trabajar con varios usuarios en una misma máquina. Será necesario que cada uno establezca su propio socket por un puerto diferente. En este campo, almacenaremos el puerto por el que escucha ese determinado usuario. Los puertos van en grupos variables, de 8, 16, 33, 66 puertos por máquina, empezando siempre a partir del 1986. Id: Valor único que identifica a un usuario. Num_amigos: Cantidad numérica de amigos que tiene este usuario. Se genera aleatoriamente a partir de unos parámetros que explicaremos más adelante. En la figura siguiente podemos observar el esquema general de las interacciones que tienen lugar entre las diferentes clases.

Figura 2 Esquema de Interacción entre clases

25

Juego de pruebas

4. Juego de pruebas En este juego de pruebas, construiremos un escenario sencillo de cuatro usuarios: Usuario_1, Usuario_2, Usuario_3 y Usuario_4 interconectados entre ellos tal como se indica en la Figura 3 Escenario de pruebas:

Figura 3 Escenario de pruebas

Este sencillo escenario tiene como misión comprobar el funcionamiento de las diferentes funciones del protocolo, esto es, la función Y, función, y la estimación de vecinos.

4.1.

Conexión al servidor

El primer paso es la conexión de todos los usuarios al nodo central de la red social y reciban información sobre sus amigos conectados. El nodo central se ejecuta en el servidor tal y como se muestra en la Figura 4. En esta fase se muestran mensajes de debug de manera que se puede ver su interacción con los usuarios en todo momento.

Figura 4, Ejemplo de inicialización del servidor

26

Juego de pruebas En la figura siguiente, tenemos un ejemplo de cómo un usuario se conecta al servidor y recibe su lista de amigos. Al no haber más que un usuario conectado, su lista se limita simplemente a él mismo.

Figura 5. Ejemplo de conexión de un usuario al servidor

Finalmente, en la Figura 6. Ejemplo del estado del servidor podemos observar el estado del servidor una vez se han conectado todos los usuarios que forman parte del escenario.

Figura 6. Ejemplo del estado del servidor

27

Juego de pruebas

4.2.

Nivel de exposición, Función Ψ

Partiendo del escenario anterior, una vez están todos los usuarios conectados, comprobamos el funcionamiento de la función del protocolo haciendo que Usuario_1 envíe una serie de búsquedas. Tal como hemos explicado anteriormente, el nivel de exposición no es mas que la estimación de búsquedas que ha enviado cada usuario. Una vez un usuario ha aceptado una petición de búsqueda, no podemos saber si éste la enviará directamente a Google o la volverá a reenviar a otro usuario de su lista de amigos. Con tal de calcular el nivel de exposición, la función se encarga de calcular el cuociente entre el número de búsquedas que ha aceptado un usuario y la estimación del número de vecinos. En este test se puede observar la evolución de los niveles de exposición de los contactos de Usuario_1. La estimación de vecinos está fijada en este test, ya que Usuario_1 no recibirá peticiones, solamente las enviará, por lo que el nivel de exposición variará únicamente por el número de búsquedas que acepten sus contactos.

Figura 7. Estado inicial de un usuario

En la anterior (Figura 7) vemos que todos los usuarios tienen el mismo nivel de exposición inicial, cero. En este caso, cuando el Usuario_1 genere una nueva búsqueda, se la enviará al primer usuario de la lista. En la Figura 8 vemos como efectivamente se envía la búsqueda al primer usuario de la lista, el Usuario_4, y se actualiza el nivel de exposición.

Figura 8. Ejemplo 1 de búsqueda siguiendo el protocolo

La siguiente búsqueda generada, deberá ser para el Usuario_3, siguiente en la lista. En la Figura 9 podemos ver como se le envía dicha búsqueda y se actualiza el nivel de exposición. Pese a haber enviado el mismo numero de búsquedas que el usuario 4 (una búsqueda cada uno) los niveles de exposición son diferentes debido a la estimación de vecinos.

28

Juego de pruebas

Figura 9. Ejemplo 2 de búsqueda siguiendo el protocolo

Después de enviar una búsqueda cada usuario, observamos que Usuario_4 vuelve a ser el primero de la lista con un nivel de exposición más bajo, y se le obliga a enviar las dos siguientes peticiones a este usuario, tal como vemos en la Figura 10 y Figura 11. De esta manera, hemos comprobado que los niveles de exposición son calculados satisfactoriamente y vemos como el protocolo tiende a enviar búsquedas con mas frecuencia a aquellos usuarios que a priori tienen más conexiones directas (numero de amigos) y a la vez protege a aquellos usuario con menos conexiones.

Figura 10. Ejemplo 3 de búsqueda siguiendo el protocolo

Figura 11. Ejemplo 4 de búsqueda siguiendo el protocolo

29

Juego de pruebas

4.3.

Estimación de vecinos

En esta prueba, modificamos los clientes de los usuarios 2, 3 y 4 de tal manera que únicamente envían búsquedas al Usuario_1 para testear la estimación de vecinos. Tal como hemos explicado, el protocolo no conoce el número de vecinos que tiene cada conexión directa, por lo tanto, para calcular este dato hacemos una estimación. Asumiremos que un usuario con pocos amigos, nos enviará más búsquedas que aquellos usuarios que tengan un número más elevado de conexiones. Por lo tanto, estimaremos una sola conexión para aquel usuario que más búsquedas nos envía, dos conexiones para el segundo usuario con más búsquedas, y así hasta completar nuestra lista de usuarios. Nos encontramos con la situación inicial observada en la Figura 12.

Figura 12. Estado inicial de la estimación de vecinos

A partir de esta situación, el usuario 1 recibirá cuatro búsquedas del usuario 2, tres búsquedas del usuario 3 y solamente una búsqueda del usuario 4, tal como vemos en la siguiente tabla: Nº Usuario 1 2 3 4

Búsquedas enviadas al usuario 1 0 4 3 1

Tabla 3 Relación de búsquedas enviadas a Usuario_1

Según el funcionamiento del protocolo, al usuario 2 se le asignará una sola conexión directa por ser el usuario que más búsquedas nos ha enviado. En la Figura 13 podemos ver la estimación de vecinos de todos los contactos del usuario 1 después del envío de las búsquedas.

Figura 13. Actualización de la estimación de vecinos

30

Juego de pruebas Si ahora el usuario 4 envía dos búsquedas más, haciendo un total de 3 búsquedas, el protocolo reasigna el número de vecinos antes de realizar la siguiente búsqueda. El resultado lo podemos observar en la figura siguiente:

Figura 14. Actualización de la estimación de vecinos

Finalmente, el usuario 4 envía una última búsqueda, haciendo un total de 4 búsquedas.

Figura 15. Actualización de la estimación de vecinos

4.4.

Detectando usuarios egoístas, Función Y

Se ha modificado el escenario de tal manera que solamente están conectados a la red social los usuarios 1 y 2. De esta manera, el usuario 1 solo podrá enviar búsquedas al usuario 2 o a si mismo. Análogamente, el usuario 2 solo podrá enviar búsquedas al usuario 1 o a si mismo. Con esta situación el usuario 1 únicamente envía búsquedas de manera que podemos observar el funcionamiento de la función Y del protocolo en el cliente del usuario 2. El usuario 1 ha generado 20 búsquedas. Si observamos los niveles de exposición en la figura 14, vemos que 14 búsquedas han sido redirigidas al usuario dos y solamente seis han sido hechas directamente por el usuario uno. A su vez, el usuario dos ha ido disminuyendo la probabilidad de aceptar búsquedas del usuario uno, a razón de un 2% por búsqueda reenviada, tal como indica la función Y del protocolo.

Figura 16. Interacción entre dos usuarios utilizando el protocolo

31

Juego de pruebas El usuario 1 genera otras 20 búsquedas. De estas 20 nuevas búsquedas, el usuario 1 se ha visto obligado a enviar 9 él mismo y las otras 11 han sido enviadas al usuario 2, que ha seguido bajando la probabilidad de aceptar búsquedas.

Figura 17 Evolución de la probabilidad de aceptar una búsqueda tras 20 peticiones.

Tras otras 20 búsquedas por parte del usuario 1, 11 han sido enviadas por él mismo, y 9 han sido enviadas por el usuario 2.

Figura 18 Evolución de la probabilidad de aceptar una búsqueda tras 40 peticiones

Tras 150 búsquedas, vemos como el usuario 1 se ha visto obligado a enviar 100 por si mismo, al comportarse de manera egoísta, quedando su privacidad expuesta frente al motor de búsqueda.

Figura 19 Evolución de la probabilidad de aceptar una búsqueda tras 150 peticiones

32

Simulaciones y resultados

5. Simulaciones y resultados En esta sección trataremos primero el diseño de las simulaciones, tanto aquellos aspectos relacionados con la red social como son el número de usuarios que componen las redes sociales generadas y distribución de las conexiones directas de estos usuarios como los aspectos propios de la simulación: Número de simulaciones, número de búsquedas y el entorno donde se lleva a cabo la simulación. Tras definir las condiciones de las simulaciones, presentaremos los resultados y las conclusiones que se pueden extraer. Las simulaciones iniciales, no mostradas en este proyecto, han servido para detectar y corregir diversos errores en la implementación que afectaban directamente al funcionamiento del protocolo y otro tipo de errores que de otra manera no hubiésemos advertido que afectaban al rendimiento y eficiencia de los clientes.

5.1.

Número de usuarios

Para las simulaciones, hemos construido cuatro redes sociales. En [1], se especifican unos tamaños de 50, 100, 200 y 400 usuarios respectivamente. En este proyecto, se han modificado estos tamaños, haciéndolos múltiples de 6, con tal de repartir el trabajo por igual entre maquinas (las simulaciones se llevan a cabo en un cluster de 6 máquinas). Por lo tanto, las redes sociales para las simulaciones serán de 48 y 96 usuarios respectivamente. Se han obviado las redes de mayor tamaño debido a limitaciones de recursos en el entorno de simulación.

5.2.

Número de amigos y lista de amigos

Cada usuario tendrá entre 1 y 10 amigos. Siguiendo un modelo de distribución powerlaw [2], en concreto la distribución de Pareto explicada en [REF], asignaremos de manera aleatoria el número de amigos con una relación aproximada del 80% entre 1 y 5 amigos y el 20% entre 5 y 10. Así, para generar las listas de amigos, primero le asignaremos a cada usuario un numero aleatorio que cumpla los requisitos anteriores y lo almacenaremos en el campo num_amigos de la tabla. Primeo generamos un número aleatorio entre 0 y 100. Si el numero es más pequeño que 80, le asignaremos un número de amigos aleatorio entre 1 y 5. Si en cambio el número esta comprendido entre 80 y 100, le asignaremos un número de amigos aleatorio entre 6 y 10. Después generaremos la lista de amigos de la siguiente manera: • •

De la tabla de la base de datos, leeremos todos los usuarios y los almacenaremos en dos arrays, uno ordenado y otro desordenado aleatoriamente. A partir de estos arrays, le iremos añadiendo a la lista de amigos de cada usuario, uno de los usuarios del array aleatorio. Antes de añadirlo a la lista,

33

Simulaciones y resultados comprobaremos que tanto nuestra lista de amigos como su lista no estén llenas. Si cumplimos la condición, añadiremos a este usuario a nuestra lista, y nos añadiremos a la suya. Dada la aleatoriedad del sistema para asignar el número de amigos y luego rellenar la lista de amigos de cada usuario siguiendo ese criterio, es necesario que una pequeña parte del código examine de nuevo el resultado de la red social, indicando si la lista de algún usuario es incorrecta. En ese caso es posible hacer una corrección manual en la base de datos para solucionar dicho error, que no obstante en ninguna de las redes sociales que hemos generado ha sobrepasado el número de dos usuarios incorrectos. A continuación, podemos ver el porcentaje de la distribución del número de amigos según la distribución de Pareto y la distribución individual del número de amigos de cada usuario para las diferentes redes sociales que hemos generado. Simulación Red de 48 usuarios

Numero de amigos Total usuarios asignados 1

11

2

13

3

5

4

1

5

10

6

5

7

1

8

0

9

1

10

1

Total

48

Tabla 4 Distribución de usuarios

34

Simulaciones y resultados

En la Figura 20 podemos ver el porcentaje de usuarios que tienen un nivel alto de conexiones directas (6-10) y los que tienen un nivel bajo (1-5).

17%

1-5 Amigos 6-10 Amigos

83%

Figura 20 Distribución de usuarios red 48 usuarios

2% 0% 2%

2%

10%

23%

1 amigo 2 amigos 3 amigos 4 amigos 5 amigos 6 amigos 21%

7 amigos 8 amigos 9 amigos 10 amigos 28% 2% 10%

Figura 21 nos muestra detalladamente el porcentaje de usuarios según el número de amigos (conexiones directas) que estos tengan.

35

Simulaciones y resultados

2% 0% 2%

2%

10%

23%

1 amigo 2 amigos 3 amigos 4 amigos 5 amigos 6 amigos 21%

7 amigos 8 amigos 9 amigos 10 amigos 28% 2% 10%

Figura 21 Distribución individual de usuarios por nombre de amigos

36

Simulaciones y resultados Simulación Red de 96 usuarios

Numero de amigos Total usuarios asignados 1

20

2

15

3

14

4

11

5

15

6

6

7

1

8

1

9

6

10

7

Total

96

Tabla 5 Distribución de usuarios

22%

1-5 Amigos 6-10 Amigos

78%

Figura 22 Distribución de usuarios red 96 usuarios.

37

Simulaciones y resultados

7% 21%

6% 1% 1%

1 6%

2 3 4 5 6 7 16%

16%

8 9 10

11%

15%

Figura 23 Distribución individual por nombre de amigos.

38

Simulaciones y resultados Se han configurado una serie de simulaciones utilizando las redes sociales de 48 y 96 usuarios con dos objetivos clave: • •

Calcular la media de tiempo de una consulta utilizando el protocolo Calcular la media del número de saltos que da una búsqueda al ser reenviada

Como objetivo secundario, intentaremos extraer otras conclusiones como la posibilidad de hallar nodos marginados por el protocolo y por lo tanto, expuestos al motor de búsqueda. Se han llevado a cabo 10 simulaciones con cada red social, en las que cada usuario generaba 800 búsquedas para la red de 48 usuarios y 600 búsquedas para la red de 96 usuarios. Todos los usuarios se rigen completamente según el protocolo, por lo que no encontraremos usuarios egoístas.

5.3.

Entorno de la simulación

Las simulaciones se han llevado a cabo en un cluster de seis máquinas. La relación de las maquinas y su función la podemos ver en la tabla siguiente: Nombre de host doc sleepy dopey sweezy grumpy bashful

IP 192.168.0.1 192.168.0.38

Funciones Gateway del cluster, Clientes del 1 al 8, Clientes del 1 al 16. Servidor Red Social(base datos) Clientes del 9 al 16 y Clientes del 17 al 32 192.168.0.50 Clientes del 17 al 24 y Clientes del 33 al 48 192.168.0.117 Clientes del 25 al 32 y Clientes del 49 al 64 192.168.0.123 Clientes del 33 al 40 y Clientes del 65 al 80 192.168.0.244 Clientes del 41 al 48 y Clientes del 81 al 96 Tabla 6 Entorno de la simulación

5.4.

Resultados

En este apartado se presentan los resultados obtenidos en el entorno de simulación explicado en el apartado anterior. Debemos tener en cuenta que los tiempos obtenidos únicamente deben servirnos para considerar los costes computacionales, ya que, al encontrarse todos los usuarios en la misma red local, y hacer sus conexiones al motor de búsqueda desde el mismo punto los costes de comunicación no serán aplicables. Diferentes simulaciones nos han dado un tiempo de búsqueda directa a Google por parte del host doc de entre 350 y 450 ms. Los tiempos de otras propuestas comentadas anteriormente se deben tomar como referencia. El UPP (useless user profile) [1], obtiene respuestas con un promedio de 5.2 segundos con un grupo de tres usuarios y una clave de 1024 bits. El método de Sectores de memoria compartidos, recibe su mejor respuesta a los 5.85 segundos. Y finalmente,

39

Simulaciones y resultados la búsqueda mediante Tor es 25 veces más lenta que una búsqueda directa (si tenemos en cuenta el tiempo de respuesta del host doc, equivale a más de 10 segundos).

5.4.1. Resultados de la red de 48 usuarios En esta sección trataremos de extraer conclusiones a partir de los resultados obtenidos en las simulaciones de la red de 48 usuarios. Para ello, mostraremos la media de tiempo de respuesta y los saltos por búsqueda, además de los niveles de privacidad alcanzados. Media del numero de saltos Media de tiempo(ms) Total búsquedas generadas 2,04 585,55 38196 Tabla 7. Resumen de las simulaciones en la red de 48 usuarios

El protocolo implementado en este proyecto en la red de 48 usuarios, obtiene unos tiempos de respuesta que rondan el medio segundo (585 ms). Ya hemos dicho que este tiempo puede ser engañoso ya que no procede de un entorno real, no obstante, el margen del que disponemos si lo comparamos con los otros métodos es amplio, alrededor de 5 segundos. Si ahora tenemos en cuenta el promedio del número de saltos que realizan las búsquedas (2,04 saltos), vemos que de hecho nuestras búsquedas no viajan demasiado por la red, por lo que podemos estimar que el tiempo de comunicación no será elevado en sobremanera. A los 585 ms obtenidos de los costes computacionales más los costes de comunicación con Google, deberemos añadir el tiempo de los viajes de ida y vuelta de la petición de búsqueda entre los usuarios, que serán variables según el tipo de conexión y ubicación de los usuarios. A continuación, se muestran en una tabla los usuarios con un promedio de saltos mayor y un promedio inferior respectivamente: Numero máximo de saltos Numero mínimo de saltos

2,90 Usuario_29 1,31 Usuario_21 Tabla 8. Detalle sobre el número de saltos

Si recordamos el promedio de saltos (2,04), vemos que tanto el usuario que promedia un número de saltos mayor como el menor, no se alejan demasiado de este. Esto nos indica que el protocolo garantiza un nivel de comunicación bastante equilibrado, sin encontrarnos usuarios con un número de saltos desproporcionados, ni usuarios que necesiten un numero elevado de saltos en sus peticiones incrementando notablemente su coste de comunicación ni usuarios con un numero de saltos inferior a 1 (esto implicaría que estos usuarios son obligados a enviar la mayoría de búsquedas por si mismos). Podemos verificar el número de amigos que tienen estos usuarios (conexiones directas) y al número de amigos que tienen a su vez sus amigos (conexiones de segundo nivel). Por parte del usuario con un número de saltos mayor, nos encontramos la siguiente situación:

40

Simulaciones y resultados

Usuario_29, Lista de amistades Nombre de usuario Número de conexiones directas Usuario_17 10 Usuario_19 2 Usuario_22 2 Usuario_25 5 Usuario_28 5 Usuario_43 5 Tabla 9. Conexiones del usuario con más saltos

La mayoría de las conexiones del usuario 29 tienen un número elevado de conexiones, haciendo muy posible que su búsqueda se vea involucrada en numerosas ramificaciones por culpa de la arquitectura de la red social. No obstante, el promedio es aceptable en este caso. Usuario_21, lista de amistades Nombre de usuario Número de conexiones Usuario_24 6 Tabla 10. Conexiones del usuario con menos saltos

El usuario 21 tiene solamente una conexión directa a la que redirigir las búsquedas, no obstante, esta conexión tiene un número elevado de conexiones (recordemos que el máximo de conexiones es de 10), por lo que a priori no nos encontramos exentos de posibles ramificaciones de nuestra búsqueda. Era de esperar que el número mínimo de saltos lo hubiésemos encontrado en un usuario con una sola conexión directa con un numero de conexiones directas limitado, como por ejemplo dos, comprometiendo a los usuarios con una sola conexión directa y con solo dos conexiones secundarias. Una vez más podemos decir que el protocolo actúa con eficacia, evitando que se produzcan este tipo de situaciones. Más pruebas en simulaciones de redes sociales diseñadas con el propósito de detectar nodos aislados nos darían más seguridad al afirmar que el protocolo actuara con la misma eficacia independientemente de la estructura de la red social. Para obtener un nivel de privacidad óptimo, el motor de búsqueda no debe ser capaz de crear un perfil detallado sobre un usuario. Conseguir este objetivo requiere de dos puntos relativos a las búsquedas totales generadas por un usuario: • •

Debe redirigir un porcentaje mínimo a otros usuarios. Debe enviar un porcentaje mínimo de búsquedas de otros usuarios.

La siguiente tabla nos muestra valores relacionados con las búsquedas que han sido reenviadas siguiendo el protocolo. Para esto, en las simulaciones se han contabilizado como búsquedas reenviadas aquellas que se ha decidido redirigir siguiendo el protocolo y que no han sido denegadas. Debemos añadir que en principio, siguiendo el protocolo de manera explicita, una búsqueda redirigida no excluye que finalmente sea enviada por nosotros. Al no haber manera de saber de donde proviene una búsqueda que ha dado más de un salto, una conexión directa de un vecino del usuario que genera la búsqueda puede a su vez reenviar la búsqueda al usuario original sin saberlo. Este caso implicaría

41

Simulaciones y resultados un número mínimo de 3 saltos. El promedio de saltos (2,04) nos hace pensar que esta situación no ocurre con regularidad, por lo que podemos contabilizar el número de búsquedas reenviadas como búsquedas generadas por un usuario que no ha enviado al motor de búsqueda directamente.

Media Búsquedas reenviadas Max búsquedas reenviadas Min búsquedas reenviadas

Porcentaje respecto al total de búsquedas generadas(800) 582,54 72,82% 737,00 92,13% Usuario_11 341,00 42,63% Usuario_20

Tabla 11. Datos sobre el reenvío de búsquedas

El porcentaje medio de búsquedas redirigidas es del 73% aproximadamente. Esto nos deja únicamente con un 27% de búsquedas propias enviadas al motor de búsqueda. El siguiente gráfico nos muestra el porcentaje de usuarios según el porcentaje de búsquedas reenviadas.

4% 13%

Más del 60% Entre 50 y 60% Menos del 50%

83%

Figura 24. Gráfico sobre el reenvío de búsquedas

El usuario que más búsquedas ha reenviado, es el usuario 11 con un porcentaje del 92%. El que menos, es el usuario 20, con un 42%. Vemos que más del 90% de los usuarios reenvía más de la mitad de sus búsquedas. Estos resultados reflejan la consecución de la primera condición para obtener un nivel de privacidad, reenviar las búsquedas a otros usuarios. A continuación analizaremos los datos hacen referencia a la segunda condición, enviar búsquedas a Google que no nos pertenezcan. En la siguiente tabla podemos observar los datos extraídos de las simulaciones. Media Búsquedas enviadas a google Max búsquedas a google Min búsquedas a google

795,75 2,08% 1144,00 3,00% Usuario_41 602,00 1,58% Usuario_7

Tabla 12. Datos sobre las peticiones enviadas al motor de búsqueda

El porcentaje ideal que indicaría que se cumple una distribución equitativa de las búsquedas es del 2,08%. En el siguiente gráfico podemos ver los usuarios que superan o

42

Simulaciones y resultados están por debajo de esta media. El porcentaje mínimo es del 1,58%, inferior en un 0,5% al ideal.

40% Usuarios que superan la media Usuarios que no superan la media 60%

Figura 25. Gráfico sobre las peticiones enviadas al motor de búsqueda

Por último, fijémonos en el usuario 20, el que menos búsquedas ha redirigido a otros usuarios y en el usuario 7, que es el que menos búsquedas ha enviado al motor de búsqueda. El primero, ha enviado a Google 1055 búsquedas, un valor que supera la media. El segundo, ha redirigido el 85 % de las búsquedas a otros usuarios. Por lo tanto, la privacidad de los dos usuarios que marcan los mínimos en una de las condiciones, compensan en la otra condición.

5.4.2. Resultados de la red de 96 usuarios A continuación, compararemos los resultados obtenidos en la red de 48 usuarios con los obtenidos en la red de 96 usuarios. Media del numero de saltos Media de tiempo(ms) Total búsquedas generadas 2,45 581,72 62772 Tabla 13. Resumen de las simulaciones en la red de 96 usuarios

En esta red la media de saltos es ligeramente superior. Si tenemos en cuenta el diseño de la red social visto en el apartado 3, vemos que la red de 96 usuarios tiene un porcentaje mayor de usuarios con más de 5 conexiones. Debemos considerar que el número de saltos en un entorno real se vera afectado por el tipo de distribución que siga la red social, entendiendo como distribución en este caso el número de conexiones que tenga cada usuario. La media de tiempo sin embargo, no se ve afectada.

Numero máximo de saltos Numero mínimo de saltos

3,16 Usuario 79 1,43 Usuario 11

Tabla 14 Detalle sobre el número de saltos

43

Simulaciones y resultados Una vez más, el usuario con un número de saltos mínimo corresponde a uno con una sola conexión directa y el usuario con mayor número de saltos tiene un número medio de conexiones directas, pero un número elevado de conexiones secundarias (4 y 30 respectivamente).

Media Búsquedas reenviadas Max búsquedas reenviadas Min búsquedas reenviadas

Porcentaje respecto al total de generadas(660) 496,92 75,29% 640,00 96,96% 296,00 44,84%

Usuario 66 Usuario 11

Tabla 15. Datos sobre el reenvío de búsquedas

El porcentaje tanto del promedio de búsquedas reenviadas como el máximo y el mínimo son similares al de la red de 48 usuarios (72%, 92% y 42% respectivamente). El usuario 66, el que más búsquedas ha reenviado tiene 10 conexiones directas mientras que el usuario 11 tiene una sola conexión.

11% 2%

Más del 60% Menos del 50% Entre el 50 y 60%

87%

Figura 26. Gráfico sobre el reenvío de búsquedas

Media Búsquedas enviadas a google Max búsquedas a google Min búsquedas a google

653,88 1008,00 407,00

1,04% 1,6% Usuario 93 0,64% Usuario 75

Tabla 16 Datos sobre las peticiones enviadas al motor de búsqueda

44

Conclusiones

6. Conclusiones Una de las primeras cosas que este proyecto nos ha obligado a tener en cuenta y a ser conscientes de ello, es el hecho de cuanto se ve comprometida nuestra privacidad hoy en día. Una manera personal de entender el concepto de privacidad es pensar que todo el mundo tiene derecho a compartir solamente aquello que quiera compartir y únicamente con aquel o aquellos con quien quiera compartirlo. Este concepto nos brinda una falsa sensación de control sobre nuestra privacidad, ya que, en ocasiones sin darnos cuenta, esta puede verse comprometida al utilizar ciertas herramientas. Un claro ejemplo precisamente es el que trata este proyecto y el trabajo [1] del que parte. El uso de un motor de búsqueda hoy en día es imprescindible para encontrar aquello que puntualmente necesitamos en la red, y esto nos obliga a poner nuestra privacidad en peligro frente a la entidad que controla dicho motor. Pese a que la ley de protección de datos y otras normas impiden sacar provecho de nuestros datos personales y venderlos a terceros, de la misma manera que va contra la ley robar, por ejemplo, dinero en un banco, y no por ello prescindiremos del uso de cajas fuertes, debemos proteger al menos en cierto grado nuestra privacidad siempre que esto sea posible. La aportación de este proyecto ha servido como un primer paso para evaluar la viabilidad del protocolo propuesto en [1]. Tanto el tiempo de los costes computacionales como el promedio de número de saltos que realizan las búsquedas son muy satisfactorios en comparación con otros métodos desarrollados con la misma finalidad que el protocolo, lo que nos hace ser optimistas de cara a futuras pruebas, ya en entornos reales, en los que podremos sumar a los costes computacionales, los costes derivados de la comunicación. Teniendo en cuenta que el margen con otros métodos es de aproximadamente 4,5 segundos y que el promedio de número de saltos de las búsquedas, entre 2 y 3, nos hace pensar que estos costes de comunicación, añadidos a los calculados en las simulaciones, serán inferiores. Otro de los posibles futuros objetivos que ha quedado fuera de este proyecto, es el de integrar el protocolo como complemento de alguna red social, como Facebook o Live Messenger y así sacar provecho de sus protocolos de comunicación y de los grupos creados por estos servicios. No obstante, esta integración a priori no es inmediata, ya que por ejemplo, el protocolo de Live Messenger por definición nos obliga a pasar siempre por un nodo central para la comunicación con cualquiera de nuestros amigos y esto, además de añadir costes de comunicación, nos obliga a utilizar algún sistema criptográfico ya que, este ultimo nodo, puede ser no confiable. La versión final del cliente es totalmente operativa, siempre y cuando se configure correctamente las tablas NAT de los routers de los diferentes nodos y se disponga de un nodo central que simule una red social. A nivel personal, este proyecto ha supuesto un reto que además de mejorar considerablemente mi nivel de programación en Java, me ha proporcionado una madurez, o al menos una primera toma de contacto, sobre la importancia que tiene no solo el hecho de ser preciso a la hora de plasmar la idea de un protocolo e implementarlo, si no además la necesidad de marcarse una serie de objetivos y diseñar la mejor manera de comprobar que estos se han alcanzado.

45

Bibliografía

7. Bibliografía [1]

Alexandre Viejo, Jordi Castellà-Roca “Using Social Networks to Distort Users’ Profiles Generated by Web Search Engines”, 11 Octubre 2009

[2]

http://en.wikipedia.org/wiki/Pareto_distribution

[3]

http://onjava.com/

[4]

http://es.wikipedia.org/

[5]

http://ubunturoot.wordpress.com/2007/11/06/comandos-basicos-para-linux/

[6]

http://doc.ubuntu-es.org/MySQL

[7]

http://www.eng.hawaii.edu/Tutor/vi.html#start

[8]

Miguel Ángel Sanz Santos, “Comandos básicos MySQL”

[9] JXTA Java Standard Edition v2.5: Programmers Guide, September 10, 2007

46

Anexo 1

8. Anexo 1: Cuadro resumen de las simulaciones para la red social de 48 usuarios

Usuario 1 Usuario 2 Usuario 3 Usuario 4 Usuario 5 Usuario 6 Usuario 7 Usuario 8 Usuario 9 Usuario 10 Usuario 11 Usuario 12 Usuario 13 Usuario 14 Usuario 15 Usuario 16 Usuario 17 Usuario 18 Usuario 19 Usuario 20 Usuario 21 Usuario 22 Usuario 23 Usuario 24 Usuario 25 Usuario 26 Usuario 27 Usuario 28 Usuario 29 Usuario

Búsqueda Búsqueda Salto Reenviada Porcentaj s s Porcentaje s Tiempo s e a google propias busc. propias amigos 1,91 578,60 566,00 70,75 681,00 234,00 34,36 2 1,80 584,83 590,00 73,75 735,00 210,00 28,57 3 1,97 578,79 581,00 72,63 750,00 219,00 29,20 2 1,54 579,28 445,00 55,63 754,00 355,00 47,08 1 2,05 578,98 587,00 73,38 908,00 213,00 23,46 2 1,92 579,64 592,00 74,00 886,00 208,00 23,48 2 2,53 585,53 680,00 85,00 602,00 120,00 19,93 5 1,67 581,68 480,00 60,00 654,00 320,00 48,93 1 1,87 579,84 477,00 59,63 885,00 323,00 36,50 1 2,08

583,58

632,00

79,00

894,00

168,00

18,79

3

2,41

586,04

737,00

92,13

611,00

63,00

10,31

9

2,42

590,15

629,00

78,63

737,00

171,00

23,20

3

2,19

590,26

565,00

70,63

1120,00

235,00

20,98

2

2,48

584,37

600,00

75,00

1116,00

200,00

17,92

2

2,27

581,45

601,00

75,13

724,00

199,00

27,49

3

2,34

589,47

553,00

69,13

605,00

247,00

40,83

2

2,38

587,03

699,00

87,38

762,00

101,00

13,25

10

1,50

596,12

466,00

58,25

807,00

334,00

41,39

2

2,45

590,63

670,00

83,75

661,00

130,00

19,67

5

1,34

580,05

341,00

42,63

1055,00

459,00

43,51

1

1,31

581,54

360,00

45,00

903,00

440,00

48,73

1

2,48

585,52

514,00

64,25

752,00

286,00

38,03

2

2,12

586,88

509,00

63,63

618,00

291,00

47,09

1

1,89

581,95

667,00

83,38

640,00

133,00

20,78

6

2,77

593,72

681,00

85,13

775,00

119,00

15,35

5

2,28

586,31

548,00

68,50

687,00

252,00

36,68

2

1,86

581,02

660,00

82,50

837,00

140,00

16,73

6

2,86

584,98

695,00

86,88

764,00

105,00

13,74

5

2,90 1,54

585,72 582,62

706,00 699,00

88,25 87,38

735,00 720,00

94,00 101,00

12,79 14,03

6 7

47

Anexo 1 30 Usuario 31 Usuario 32 Usuario 33 Usuario 34 Usuario 35 Usuario 36 Usuario 37 Usuario 38 Usuario 39 Usuario 40 Usuario 41 Usuario 42 Usuario 43 Usuario 44 Usuario 45 Usuario 46 Usuario 47 Usuario 48 Total Media Max Min

1,69

583,57

515,00

64,38

630,00

285,00

45,24

2

1,77

587,42

544,00

68,00

681,00

256,00

37,59

2

1,83

580,19

668,00

83,50

753,00

132,00

17,53

5

2,50

585,07

700,00

87,50

671,00

100,00

14,90

6

1,65

583,84

672,00

84,00

669,00

128,00

19,13

5

1,85

581,71

666,00

83,25

639,00

134,00

20,97

5

1,62

585,77

519,00

64,88

1065,00

281,00

26,38

1

2,37

588,23

667,00

83,38

907,00

133,00

14,66

5

1,61

591,78

441,00

55,13

866,00

359,00

41,45

1

1,80

583,50

436,00

54,50

812,00

364,00

44,83

1

1,64

585,20

521,00

65,13

1144,00

279,00

24,39

1

2,58

597,49

622,00

77,75

677,00

178,00

26,29

3

2,61

607,19

706,00

88,25

843,00

94,00

11,15

5

1,57

593,73

498,00

62,25

791,00

302,00

38,18

1

1,83

581,86

576,00

72,00

794,00

224,00

28,21

6

1,94

583,98

590,00

73,75

908,00

210,00

23,13

4

1,84

578,48

564,00

70,50

870,00

236,00

27,13

5

2,21

590,67 28106,2 1 585,55 607,19 578,48

527,00

65,88

1098,00

273,00

24,86

2

38196,00 795,75 1144,00 602,00

10438,00 217,46 459,00 63,00

27,48 48,93 10,31

98,07 2,04 2,90 1,31

27962,00 582,54 737,00 341,00

48

Anexo 2

9. Anexo 2: Cuadro resumen de las simulaciones para la red social de 96 usuarios Usuario 1 Usuario 2 Usuario 3 Usuario 4 Usuario 5 Usuario 6 Usuario 7 Usuario 8 Usuario 9 Usuario 10 Usuario 11 Usuario 12 Usuario 13 Usuario 14 Usuario 15 Usuario 16 Usuario 17 Usuario 18 Usuario 19 Usuario 20 Usuario 21 Usuario 22 Usuario 23 Usuario 24 Usuario 25 Usuario 26 Usuario 27 Usuario 28 Usuario 29 Usuario 30 Usuario 31 Usuario 32 Usuario 33 Usuario 34 Usuario 35 Usuario 36 Usuario 37 Usuario 38 Usuario 39 Usuario 40 Usuario 41 Usuario 42 Usuario 43 Usuario 44 Usuario 45 Usuario 46 Usuario 47 Usuario 48

Búsquedas Búsquedas Saltos Tiempo Reenviadas % a google propias % amigos 1,92 579,54 579,00 87,73 707,00 81,00 12,27 10 1,87 578,06 353,00 53,48 606,00 307,00 46,52 1 2,18 577,53 541,00 81,97 601,00 119,00 18,03 5 2,50 583,77 545,00 82,58 559,00 115,00 17,42 5 2,13 584,55 574,00 86,97 703,00 86,00 13,03 10 2,66 584,25 543,00 82,27 591,00 117,00 17,73 5 2,03 581,70 391,00 59,24 523,00 269,00 40,76 1 2,44 579,77 499,00 75,61 687,00 161,00 24,39 3 2,51 582,70 551,00 83,48 653,00 109,00 16,52 5 2,58 578,30 493,00 74,70 653,00 167,00 25,30 3 1,43 573,50 296,00 44,85 756,00 364,00 55,15 1 2,33 577,28 426,00 64,55 691,00 234,00 35,45 2 2,38 577,84 514,00 77,88 504,00 146,00 22,12 4 2,30 575,50 413,00 62,58 489,00 247,00 37,42 1 2,88 583,94 571,00 86,52 659,00 89,00 13,48 6 2,88 583,34 584,00 88,48 708,00 76,00 11,52 9 3,02 580,43 528,00 80,00 597,00 132,00 20,00 3 3,08 581,88 567,00 85,91 673,00 93,00 14,09 6 3,10 584,78 569,00 86,21 620,00 91,00 13,79 5 2,86 578,85 491,00 74,39 634,00 169,00 25,61 3 2,26 581,20 373,00 56,52 686,00 287,00 43,48 1 3,15 585,09 618,00 93,64 637,00 42,00 6,36 9 2,61 583,51 533,00 80,76 541,00 127,00 19,24 5 2,49 576,75 535,00 81,06 773,00 125,00 18,94 4 2,31 583,42 473,00 71,67 584,00 187,00 28,33 3 2,25 579,30 621,00 94,09 669,00 39,00 5,91 10 2,48 582,19 500,00 75,76 586,00 160,00 24,24 3 2,60 587,40 586,00 88,79 628,00 74,00 11,21 9 1,44 576,56 321,00 48,64 698,00 339,00 51,36 1 2,71 581,63 526,00 79,70 589,00 134,00 20,30 4 2,62 576,71 439,00 66,52 646,00 221,00 33,48 2 2,76 582,76 562,00 85,15 616,00 98,00 14,85 6 2,33 585,61 449,00 68,03 692,00 211,00 31,97 2 1,73 579,08 365,00 55,30 573,00 295,00 44,70 1 2,82 582,22 543,00 82,27 623,00 117,00 17,73 4 1,94 580,57 443,00 67,12 524,00 217,00 32,88 2 2,77 583,07 492,00 74,55 568,00 168,00 25,45 3 2,37 589,21 565,00 85,61 735,00 95,00 14,39 10 1,90 582,20 361,00 54,70 579,00 299,00 45,30 1 2,43 593,19 432,00 65,45 527,00 228,00 34,55 2 2,57 580,61 497,00 75,30 602,00 163,00 24,70 3 2,63 588,45 578,00 87,58 642,00 82,00 12,42 6 2,32 580,58 445,00 67,42 730,00 215,00 32,58 2 2,63 583,73 517,00 78,33 639,00 143,00 21,67 4 2,14 581,23 503,00 76,21 661,00 157,00 23,79 5 2,25 585,00 445,00 67,42 572,00 215,00 32,58 2 2,44 580,24 536,00 81,21 688,00 124,00 18,79 5 2,56 579,68 527,00 79,85 658,00 133,00 20,15 5

49

Anexo 2 Usuario 49 2,19 584,41 Usuario 50 2,17 579,46 Usuario 51 1,89 577,53 Usuario 52 2,23 579,59 Usuario 53 2,49 580,78 Usuario 54 2,42 587,89 Usuario 55 1,66 573,96 Usuario 56 2,34 579,24 Usuario 57 2,35 575,23 Usuario 58 2,46 594,13 Usuario 59 1,97 575,42 Usuario 60 2,64 576,71 Usuario 61 2,14 579,13 Usuario 62 2,82 583,42 Usuario 63 3,07 584,79 Usuario 64 2,37 580,58 Usuario 65 2,18 581,31 Usuario 66 3,10 580,36 Usuario 67 2,06 582,71 Usuario 68 2,84 597,37 Usuario 69 2,60 579,09 Usuario 70 2,38 580,92 Usuario 71 2,80 583,34 Usuario 72 3,00 585,88 Usuario 73 2,16 578,25 Usuario 74 2,97 581,34 Usuario 75 2,52 576,11 Usuario 76 2,28 576,14 Usuario 77 1,98 577,79 Usuario 78 3,11 583,65 Usuario 79 3,16 584,06 Usuario 80 2,77 589,78 Usuario 81 3,02 599,90 Usuario 82 2,95 581,89 Usuario 83 2,94 583,85 Usuario 84 1,84 575,64 Usuario 85 2,76 587,39 Usuario 86 1,81 574,51 Usuario 87 1,91 578,57 Usuario 88 1,74 576,28 Usuario 89 2,87 585,27 Usuario 90 2,21 576,88 Usuario 91 2,83 592,50 Usuario 92 2,89 585,84 Usuario 93 1,87 572,83 Usuario 94 2,71 586,65 Usuario 95 2,11 576,96 Usuario 96 2,58 581,35 Total 234,75 55845,31 Media 2,45 581,72 Max 3,16 599,90 Min 1,43 572,83

431,00 395,00 386,00 508,00 521,00 484,00 333,00 385,00 533,00 494,00 441,00 569,00 535,00 571,00 626,00 495,00 503,00 640,00 398,00 608,00 448,00 530,00 550,00 618,00 482,00 546,00 434,00 479,00 501,00 583,00 550,00 479,00 562,00 515,00 518,00 335,00 592,00 413,00 386,00 412,00 601,00 458,00 565,00 561,00 413,00 634,94 422,00 447,00 47703,94 496,92 640,00 296,00

65,30 59,85 58,48 76,97 78,94 73,33 50,45 58,33 80,76 74,85 66,82 86,21 81,06 86,52 94,85 75,00 76,21 96,97 60,30 92,12 67,88 80,30 83,33 93,64 73,03 82,73 65,76 72,58 75,91 88,33 83,33 72,58 85,15 78,03 78,48 50,76 89,70 62,58 58,48 62,42 91,06 69,39 85,61 85,00 62,58 96,20 63,94 67,73

50

664,00 545,00 702,00 565,00 731,00 620,00 654,00 519,00 622,00 575,00 779,00 777,00 644,00 755,00 640,00 618,00 646,00 511,00 914,00 609,00 525,00 674,00 663,00 715,00 700,00 608,00 407,00 718,00 636,00 640,00 589,00 595,00 663,00 819,00 947,00 750,00 691,00 584,00 842,00 606,00 670,00 623,00 782,00 697,00 1008,00 720,00 717,00 813,00 62772,00 653,88 1008,00 407,00

229,00 34,70 265,00 40,15 274,00 41,52 152,00 23,03 139,00 21,06 176,00 26,67 327,00 49,55 275,00 41,67 127,00 19,24 166,00 25,15 219,00 33,18 91,00 13,79 125,00 18,94 89,00 13,48 34,00 5,15 165,00 25,00 157,00 23,79 20,00 3,03 262,00 39,70 52,00 7,88 212,00 32,12 130,00 19,70 110,00 16,67 42,00 6,36 178,00 26,97 114,00 17,27 226,00 34,24 181,00 27,42 159,00 24,09 77,00 11,67 110,00 16,67 181,00 27,42 98,00 14,85 145,00 21,97 142,00 21,52 325,00 49,24 68,00 10,30 247,00 37,42 274,00 41,52 248,00 37,58 59,00 8,94 202,00 30,61 95,00 14,39 99,00 15,00 247,00 37,42 25,06 3,80 238,00 36,06 213,00 32,27 15656,06 2372,13 163,08 24,71 364,00 55,15 20,00 3,03

2 1 1 4 3 3 1 1 5 3 2 9 5 7 10 3 4 10 1 10 2 5 4 8 2 4 1 2 4 5 4 2 5 3 3 1 9 1 1 1 9 2 6 5 1 6 1 2