Changeset 969cb45 in libros for maquetacion/capitulo8/capitulo8.tex
- Timestamp:
- Oct 16, 2014, 8:55:14 AM (10 years ago)
- Branches:
- revisionfinal
- Children:
- 22dcb0c
- Parents:
- 772329b
- git-author:
- Dhionel Díaz <ddiaz@…> (14/10/14 11:55:35)
- git-committer:
- aaraujo <aaraujo@…> (16/10/14 08:55:14)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
maquetacion/capitulo8/capitulo8.tex
r6fc3dc2 r969cb45 1 1 \chapter{Sistema de medici\'on de anonimato} 2 \chapterauthors{Rodolfo Sumoza 3 \chapteraffil{Fundación Centro Nacional de Desarrollo e Investigación en Tecnologías Libres} 4 } 2 \chapterauthors{Rodolfo Sumoza \chapteraffil{Fundación Centro Nacional de Desarrollo e Investigación en Tecnologías Libres} } 5 3 6 4 % Se crea un ambiente bibunit para el cual se creará la bibliografía … … 10 8 11 9 12 \textbf{Resumen} 13 14 Este trabajo propone el uso de un sistema de medición para anonimato 15 basado en las características de sus propiedades principales: el índice 16 de uniformidad de la distribución de probabilidad y el tamaño del conjunto 17 anónimo. En las propuestas previas, la medida más ampliamente utilizada 18 es la entropía, un índice utilizado y propuesto en la Teoría de la 19 Información, el cual tiene algunos inconvenientes con respecto a la 20 medición del Anonimato según la propiedades mencionadas, en primer 21 lugar dichas propiedades no se representan directa y explícitamente 22 con este índice, y al ser un índice logarítmico, no representa de 23 forma adecuada comportamientos lineales en el Anonimato. Para medir 24 el índice de uniformidad se propone utilizar el criterio del 25 error cuadrático mínimo y como segunda propuesta se plantea 26 utilizar el criterio de divergencia de Jensen-Shannon. Para 27 medir el tamaño del conjunto anónimo se propone utilizar una 28 función de N (número de entes del conjunto anónimo). 10 \textbf{Resumen} 11 12 Este trabajo propone el uso de un sistema de medición para anonimato basado en las características de sus propiedades principales: el índice de uniformidad de la distribución de probabilidad y el tamaño del conjunto anónimo. 13 En las propuestas previas, la medida más ampliamente utilizada es la entropía, un índice utilizado y propuesto en la Teoría de la Información, el cual tiene algunos inconvenientes con respecto a la medición del Anonimato según la propiedades mencionadas, en primer lugar dichas propiedades no se representan directa y explícitamente con este índice, y al ser un índice logarítmico, no representa de forma adecuada comportamientos lineales en el Anonimato. 14 Para medir el índice de uniformidad se propone utilizar el criterio del error cuadrático mínimo y como segunda propuesta se plantea utilizar el criterio de divergencia de Jensen-Shannon. 15 Para medir el tamaño del conjunto anónimo se propone utilizar una función de N (número de entes del conjunto anónimo). 29 16 30 17 %\subsection{Introducción} 31 \section{Introducción} 32 Los sistemas de medición utilizados para cuantificar los niveles 33 de Anonimato de los sistemas, mecanismos y herramientas aun se 34 consideran un problema abierto. Se han propuesto algunas alternativas 35 para este propósito, y la que más ampliamente se ha utilizado es la 36 que se basa en una medida utilizada en la Teoría de la Información: 37 la entropía. Sin embargo ésta no representa explícitamente las características 38 fundamentales del Anonimato: el tamaño del conjunto anónimo y el 39 índice de uniformidad de la distribución de probabilidad vinculada 40 al conjunto anónimo. En este trabajo, se propone utilizar como alternativa 41 dos índices para la medición del Anonimato, que explícitamente representen 42 sus principales características. Por un lado el tamaño del conjunto anónimo 43 puede ser representado a través de una función de N (el número de entes 44 que componen al conjunto) y el índice de uniformidad puede ser representado 45 utilizando uno de los siguientes indicadores: el Error Cuadrático 46 Medio (RMSE por sus siglas en inglés) o el criterio de divergencia de 47 Jensen-Shannon (CDJs por sus siglas en inglés). 48 49 50 En Pfiztmann et al. \cite{rlsm:terminology} establecieron una 51 terminología ampliamente utilizada para estandarizar los términos 52 utilizados en el contexto del Anonimato, en la cual ésta establece 53 que un sujeto es anónimo cuando no puede ser diferenciado de los otros 54 sujetos pertenecientes al mismo conjunto, denominado el conjunto anónimo. 55 Describiendo el Anonimato en estos términos, se establece que sus niveles 56 se incrementan si el tamaño del conjunto anónimo crece y cuando la 57 distribución de probabilidad que establece un atacante sobre los 58 miembros de ese conjunto anónimo tiende a ser uniforme. La 59 proximidad de una distribución de probabilidad cualquiera a una 60 distribución uniforme es a lo que se le denomina el índice de 61 uniformidad de la distribución de probabilidad. 62 63 En la mayoría de la documentación hasta ahora difundida se utiliza 64 como medida de referencia una obtenida de la Teoría de la Información: 65 la entropía, y puede verse su representación tal como la definió Shannon 66 en \cite{rlsm:shannon}. Esta propuesta fue discutida en los trabajos 67 de Díaz et al. \cite{rlsm:diaz01} y Serjantov et al. \cite{rlsm:serj01}, 68 y desde entonces ha sido utilizada como base de medición en varios otros 69 trabajos como el de Deng et al. \cite{rlsm:yuxin}, Edman et al. 70 \cite{rlsm:combinatorial} y Gierlichs et al. \cite{rlsm:revisiting}. 71 Sin embargo, esta medida no representa explícitamente las características 72 que describen al Anonimato y que fueron explicadas previamente, 73 particularmente el índice de uniformidad. 18 \section{Introducción} 19 Los sistemas de medición utilizados para cuantificar los niveles de Anonimato de los sistemas, mecanismos y herramientas aun se consideran un problema abierto. 20 Se han propuesto algunas alternativas para este propósito, y la que más ampliamente se ha utilizado es la que se basa en una medida utilizada en la Teoría de la Información: la entropía. 21 Sin embargo ésta no representa explícitamente las características fundamentales del Anonimato: el tamaño del conjunto anónimo y el índice de uniformidad de la distribución de probabilidad vinculada al conjunto anónimo. 22 En este trabajo, se propone utilizar como alternativa dos índices para la medición del Anonimato, que explícitamente representen sus principales características. 23 Por un lado el tamaño del conjunto anónimo puede ser representado a través de una función de N (el número de entes que componen al conjunto) y el índice de uniformidad puede ser representado utilizando uno de los siguientes indicadores: el Error Cuadrático Medio (RMSE por sus siglas en inglés) o el criterio de divergencia de Jensen-Shannon (CDJs por sus siglas en inglés). 24 25 26 En Pfiztmann et al. 27 \cite{rlsm:terminology} establecieron una terminología ampliamente utilizada para estandarizar los términos utilizados en el contexto del Anonimato, en la cual ésta establece que un sujeto es anónimo cuando no puede ser diferenciado de los otros sujetos pertenecientes al mismo conjunto, denominado el conjunto anónimo. 28 Describiendo el Anonimato en estos términos, se establece que sus niveles se incrementan si el tamaño del conjunto anónimo crece y cuando la distribución de probabilidad que establece un atacante sobre los miembros de ese conjunto anónimo tiende a ser uniforme. 29 La proximidad de una distribución de probabilidad cualquiera a una distribución uniforme es a lo que se le denomina el índice de uniformidad de la distribución de probabilidad. 30 31 En la mayoría de la documentación hasta ahora difundida se utiliza como medida de referencia una obtenida de la Teoría de la Información: la entropía, y puede verse su representación tal como la definió Shannon en \cite{rlsm:shannon}. 32 Esta propuesta fue discutida en los trabajos de Díaz et al. 33 \cite{rlsm:diaz01} y Serjantov et al. 34 \cite{rlsm:serj01}, y desde entonces ha sido utilizada como base de medición en varios otros trabajos como el de Deng et al. 35 \cite{rlsm:yuxin}, Edman et al. 36 \cite{rlsm:combinatorial} y Gierlichs et al. 37 \cite{rlsm:revisiting}. 38 Sin embargo, esta medida no representa explícitamente las características que describen al Anonimato y que fueron explicadas previamente, particularmente el índice de uniformidad. 74 39 75 40 %\subsection{Trabajos Relacionados} 76 \section{Trabajos Relacionado} 77 Se han hecho varias propuestas para cuantificar el grado o nivel de 78 anonimato provisto por los sistemas anónimos. En \cite{rlsm:reiter} 79 definen el grado de Anonimato como $1 - p$, donde $p$ es la probabilidad 80 asignada por el atacante a un sujeto particular. En \cite{rlsm:berthold} 81 definen el grado de anonimato como $A=\log_2(N)$, donde $N$ es el 82 número de sujetos (usuarios) del sistema. Este grado solo depende del 83 número de usuarios del sistema, y no toma en cuenta la información 84 que el atacante puede obtener a través de la observación del sistema 85 o por otros medios. En \cite{rlsm:diaz01} y \cite{rlsm:serj01} proponen 86 medir la información que obtiene el atacante, considerando el conjunto 87 completo de usuarios la probabilidad que le asigna, y para ello 88 como medida proponen la entropía utilizada en la Teoría de Información 89 (usan la entropía definida por Shannon en \cite{rlsm:shannon}). 90 Ninguna de las propuestas anteriores representa explícitamente el 91 tamaño del conjunto anónimo y el índice de uniformidad. Además en 92 \cite{rlsm:diaz01} proponen utilizar un grado de anonimato normalizado, 93 pero esta medida puede alcanzar su máximo nivel de anonimato 94 con un $N=2$ (tamaño del conjunto anónimo), contradiciendo una de 95 las características fundamentales del Anonimato definida en 96 \cite{rlsm:terminology}: Los niveles de Anonimato se incrementan 97 si se incrementa el tamaño del conjunto anónimo y el índice de 98 uniformidad de la distibución de probabilidad. En \cite{rlsm:yuxin}, 99 \cite{rlsm:combinatorial}, \cite{rlsm:revisiting} utilizan la entropía 100 de Shannon con un enfoque diferente pero adoleciendo de los mismos 101 problemas. Cuando utilizan la entropía, están utilizando una 102 función logarítmica, lo que significa que no se tienen grados de 103 medición lineales para comparar los sistemas. Por ejemplo, si se tienen 104 4 sistemas, y los atacantes no tienen ninguna información de sus usuarios, 105 esto quiere decir, que le asignan una distribución de probabilidad 106 uniforme a cada conjunto anónimo, esto es si el primer sistema 107 tiene $N=100$ sujetos, el segundo tiene $N=200$ sujetos, el tercero 108 tiene $N=400$ sujetos y el cuarto tiene $N=800$ sujetos, los grados 109 de Anonimato utilizando la entropía son: $6.6438$, $7.6438$, $8.6438$, 110 $9.6438$, respectivamente. Estos escenarios, con la misma distribución 111 de probabilidad y con diferente $N$ (el doble del conjunto anterior) 112 debería tener el doble del grado de Anonimato comparando cada uno con 113 el siguiente, pero esto no sucede debido a que la entropía utiliza 114 una función logarítmica y no lineal. 41 \section{Trabajos Relacionado} 42 Se han hecho varias propuestas para cuantificar el grado o nivel de anonimato provisto por los sistemas anónimos. 43 En \cite{rlsm:reiter} definen el grado de Anonimato como 44 $1 - 45 p$, donde 46 $p$ es la probabilidad asignada por el atacante a un sujeto particular. 47 En \cite{rlsm:berthold} definen el grado de anonimato como 48 $A=\log_2(N)$, donde 49 $N$ es el número de sujetos (usuarios) del sistema. 50 Este grado solo depende del número de usuarios del sistema, y no toma en cuenta la información que el atacante puede obtener a través de la observación del sistema o por otros medios. 51 En \cite{rlsm:diaz01} y \cite{rlsm:serj01} proponen medir la información que obtiene el atacante, considerando el conjunto completo de usuarios la probabilidad que le asigna, y para ello como medida proponen la entropía utilizada en la Teoría de Información (usan la entropía definida por Shannon en \cite{rlsm:shannon}). 52 Ninguna de las propuestas anteriores representa explícitamente el tamaño del conjunto anónimo y el índice de uniformidad. 53 Además en \cite{rlsm:diaz01} proponen utilizar un grado de anonimato normalizado, pero esta medida puede alcanzar su máximo nivel de anonimato con un 54 $N=2$ (tamaño del conjunto anónimo), contradiciendo una de las características fundamentales del Anonimato definida en \cite{rlsm:terminology}: Los niveles de Anonimato se incrementan si se incrementa el tamaño del conjunto anónimo y el índice de uniformidad de la distibución de probabilidad. 55 En \cite{rlsm:yuxin}, \cite{rlsm:combinatorial}, \cite{rlsm:revisiting} utilizan la entropía de Shannon con un enfoque diferente pero adoleciendo de los mismos problemas. 56 Cuando utilizan la entropía, están utilizando una función logarítmica, lo que significa que no se tienen grados de medición lineales para comparar los sistemas. 57 Por ejemplo, si se tienen 4 sistemas, y los atacantes no tienen ninguna información de sus usuarios, esto quiere decir, que le asignan una distribución de probabilidad uniforme a cada conjunto anónimo, esto es si el primer sistema tiene 58 $N=100$ sujetos, el segundo tiene 59 $N=200$ sujetos, el tercero tiene 60 $N=400$ sujetos y el cuarto tiene 61 $N=800$ sujetos, los grados de Anonimato utilizando la entropía son: 62 $6.6438$, 63 $7.6438$, 64 $8.6438$, 65 $9.6438$, respectivamente. 66 Estos escenarios, con la misma distribución de probabilidad y con diferente 67 $N$ (el doble del conjunto anterior) debería tener el doble del grado de Anonimato comparando cada uno con el siguiente, pero esto no sucede debido a que la entropía utiliza una función logarítmica y no lineal. 115 68 \begin{comment} 116 En este punto cabe preguntar porqué el concepto de grado de anonimato 117 se considera que debe estar asociado con una función lineal del tamaño 118 del conjunto. Esa es una restricción fuerte que no se ve justificada. 119 Lo que se muestra en torno al asunto sólo llega a requerir que sea una 120 función creciente. 69 En este punto cabe preguntar porqué el concepto de grado de anonimato se considera que debe estar asociado con una función lineal del tamaño del conjunto. 70 Esa es una restricción fuerte que no se ve justificada. 71 Lo que se muestra en torno al asunto sólo llega a requerir que sea una función creciente. 121 72 \end{comment} 122 73 123 74 %\subsection{Propuesta} 124 \section{Propuesta} 125 126 Se propone utilizar dos índices para medir el Anonimato, cada uno 127 para establecer los niveles de cada característica fundamental del 128 Anonimato: Uno para medir el tamaño del conjunto anónimo: $N$ o $1/N$, 129 donde $N$ es el número de sujetos o elementos, y uno para medir el 130 índice de uniformidad de la función de distribución de probabilidad 131 asignada por el atacante. Para medir el índice de uniformidad se 132 proponen utilizar una de las siguientes dos métricas: La raíz del 133 error cuadrático medio (RSME) o el criterio de divergencia de 134 Jennsen-Shannon (DJS). 75 \section{Propuesta} 76 77 Se propone utilizar dos índices para medir el Anonimato, cada uno para establecer los niveles de cada característica fundamental del Anonimato: Uno para medir el tamaño del conjunto anónimo: 78 $N$ o 79 $1/N$, donde 80 $N$ es el número de sujetos o elementos, y uno para medir el índice de uniformidad de la función de distribución de probabilidad asignada por el atacante. 81 Para medir el índice de uniformidad se proponen utilizar una de las siguientes dos métricas: La raíz del error cuadrático medio (RSME) o el criterio de divergencia de Jennsen-Shannon (DJS). 135 82 136 83 %\subsubsection{Raíz del Error Cuadrático Medio - RSME} 137 \subsection{Raíz del Error Cuadrático Medio - RSME} 138 139 Este término se utiliza para estimar el error de la varianza, este 140 es el error residual de la suma de los cuadrados divididos por el 141 grado de libertad. En análisis de regresión, es una cantidad observada 142 dada un muestra en particular, y depende de dicha muestra. Además, 143 este término es referido al error fuera de la muestra: el valor medio 144 de las desviaciones cuadráticas de las predicciones de los valores de 145 verdad, sobre un espacio fuera de la muestra, generado por un modelo 146 estimado sobre un espacio muestral particular. Ésta también es una 147 cantidad observada, y varía según la muestra y según el espacio fuera 148 de la muestra probado. 149 150 \begin{equation} 151 RSME=\frac{\sqrt{(\bar{X}-X)^{2}}}{n(n-1)} 152 \end{equation} 153 154 En este caso, se propone utilizar $p_{i}=\frac{1}{N}$ (probabilidades en 155 una distribución uniforme) para representar $\bar{X}$, y $p_{i}$, 156 la probabilidad asignada por el atacante, se representa con $X$. Esta 157 medida permite establecer la "distancia" de la distribución de 158 probabilidad del atacante a la distribución uniforme. 159 160 \begin{equation} 161 RSME_a=\frac{\sqrt{\displaystyle\sum_{i=1}^N (\frac{1}{N}-p_{i})^{2}}}{N(N-1)} 162 \end{equation} 163 164 Si un sistema tiene un $RSME_a\approxeq1$, esto quiere decir que 165 provee un muy bajo nivel de anonimato. 166 Si otro sistema tiene un $RSME_a\approxeq0$, quiere decir que provee 167 un buen nivel de anonimato. Pero también se debe observar el tamaño 168 del conjunto anónimo para tomar un visión real del sistema. 84 \subsection{Raíz del Error Cuadrático Medio - RSME} 85 86 Este término se utiliza para estimar el error de la varianza, este es el error residual de la suma de los cuadrados divididos por el grado de libertad. 87 En análisis de regresión, es una cantidad observada dada un muestra en particular, y depende de dicha muestra. 88 Además, este término es referido al error fuera de la muestra: el valor medio de las desviaciones cuadráticas de las predicciones de los valores de verdad, sobre un espacio fuera de la muestra, generado por un modelo estimado sobre un espacio muestral particular. 89 Ésta también es una cantidad observada, y varía según la muestra y según el espacio fuera de la muestra probado. 90 91 \begin{equation} 92 RSME=\frac{\sqrt{(\bar{X}-X)^{2}}}{n(n-1)} 93 \end{equation} 94 95 En este caso, se propone utilizar 96 $p_{i}=\frac{1}{N}$ (probabilidades en una distribución uniforme) para representar 97 $\bar{X}$, y 98 $p_{i}$, la probabilidad asignada por el atacante, se representa con 99 $X$. 100 Esta medida permite establecer la "distancia" de la distribución de probabilidad del atacante a la distribución uniforme. 101 102 \begin{equation} 103 RSME_a=\frac{\sqrt{\displaystyle\sum_{i=1}^N (\frac{1}{N}-p_{i})^{2}}}{N(N-1)} 104 \end{equation} 105 106 Si un sistema tiene un 107 $RSME_a\approxeq1$, esto quiere decir que provee un muy bajo nivel de anonimato. 108 Si otro sistema tiene un 109 $RSME_a\approxeq0$, quiere decir que provee un buen nivel de anonimato. 110 Pero también se debe observar el tamaño del conjunto anónimo para tomar un visión real del sistema. 169 111 170 112 %\subsubsection{Divergencia de Jennesen-Shannon} 171 \subsection{Divergencia de Jennesen-Shannon} 172 173 La divergencia de Jensen-Shannon es un método popular para medir 174 la similitud entre dos o más distribuciones de probabilidad. Se basa 175 en la divergencia de Kullback-Leibler, con la notable y útil diferencia 176 que siempre da como resultado un valor finito. La raíz cuadrada 177 de la divergencia de Jensen-Shannon es el índice que se propone para 178 representar el índice de uniformidad en Anonimato. 179 180 \begin{equation} 181 JSD(P_{1},P_{2})=H\left(\displaystyle\sum_{i=1}^2 \pi_i P_i\right)-\displaystyle\sum_{i=1}^2 \pi_i P_i 182 \end{equation} 183 184 \begin{equation} 185 JSD_a(P_{1},P_{2})=\sqrt{JSD(P_{1},P_{2})} 186 \end{equation} 187 188 donde $\pi_i$ son lo pesos para la distribuciones de 189 probabilidad $P_1,P_2$, en este caso $\pi_i=1, \nabla i=\{1,2\}$, 190 y $H(P)$ es la entropía de Shannon para la distribución $P$. Es este 191 caso, $P_1$ es una distribución uniforme y $P_2$ es la distribución 192 de probabilidad del atacante. 193 194 Con este resultado se obtienen dos índices para representar el grado o 195 nivel de Anonimato: 113 \subsection{Divergencia de Jennesen-Shannon} 114 115 La divergencia de Jensen-Shannon es un método popular para medir la similitud entre dos o más distribuciones de probabilidad. 116 Se basa en la divergencia de Kullback-Leibler, con la notable y útil diferencia que siempre da como resultado un valor finito. 117 La raíz cuadrada de la divergencia de Jensen-Shannon es el índice que se propone para representar el índice de uniformidad en Anonimato. 118 119 \begin{equation} 120 JSD(P_{1},P_{2})=H\left(\displaystyle\sum_{i=1}^2 \pi_i P_i\right)-\displaystyle\sum_{i=1}^2 \pi_i P_i 121 \end{equation} 122 123 \begin{equation} 124 JSD_a(P_{1},P_{2})=\sqrt{JSD(P_{1},P_{2})} 125 \end{equation} 126 127 donde 128 $\pi_i$ son lo pesos para la distribuciones de probabilidad 129 $P_1,P_2$, en este caso 130 $\pi_i=1, \nabla 131 i=\{1,2\}$, y 132 $H(P)$ es la entropía de Shannon para la distribución 133 $P$. 134 Es este caso, 135 $P_1$ es una distribución uniforme y 136 $P_2$ es la distribución de probabilidad del atacante. 137 138 Con este resultado se obtienen dos índices para representar el grado o nivel de Anonimato: 196 139 197 140 198 141 %\subsubsection{Resultados} 199 \subsection{Resultados} 200 \begin{description} 201 \item[Opción 1:] Grado de Anonimato ($AD$) utilizando RMSE para medir 202 el índice de uniformidad de la distribución de probabilidad 203 y $1/N$ para medir el tamaño del conjunto anónimo.\\ 204 \begin{center}$AD = 1 / N \pm MSE_a$\end{center} 205 \item[Opción 2:] Grado de Anonimato ($AD$) utilizando JSD para 206 medir el índice de uniformidad de la distribución de probabilidad 207 y $1/N$ para medir el tamaño del conjunto anónimo.\\ 208 \begin{center}$AD = 1 / N \pm JSD_a$\end{center} 209 \end{description} 210 211 En ambos casos, el índice de uniformidad y el tamaño son 212 expresados por separado pero no tiene el problema de linealidad 213 de las otras métricas. 142 \subsection{Resultados} 143 \begin{description} 144 \item[Opción 1:] 145 Grado de Anonimato 146 ($AD$) utilizando RMSE para medir el índice de uniformidad de la distribución de probabilidad y 147 $1/N$ para medir el tamaño del conjunto anónimo.\\ 148 \begin{center}$AD 149 = 1 / N \pm 150 MSE_a$\end{center} 151 \item[Opción 2:] 152 Grado de Anonimato 153 ($AD$) utilizando JSD para medir el índice de uniformidad de la distribución de probabilidad y 154 $1/N$ para medir el tamaño del conjunto anónimo.\\ 155 \begin{center}$AD 156 = 1 / N \pm 157 JSD_a$\end{center} 158 \end{description} 159 160 En ambos casos, el índice de uniformidad y el tamaño son expresados por separado pero no tiene el problema de linealidad de las otras métricas. 214 161 215 162 %\begin{thebibliography}{} … … 255 202 256 203 % el siguiente comando establece la ubicación de las referencias 257 \putbib[bibliografia]204 \putbib[bibliografia] 258 205 259 206 % el siguiente comando cierra el ambiente bibunit para la cual se generan las
Note: See TracChangeset
for help on using the changeset viewer.