source: libros/maquetacion/capitulo8/capitulo8.tex @ 6fc3dc2

\chapter{Sistema de medici\'on de anonimato}
\chapterauthors{Rodolfo Sumoza
\chapteraffil{Fundación Centro Nacional de Desarrollo e Investigación en Tecnologías Libres}
}

% Se crea un ambiente bibunit para el cual se creará la bibliografía
\begin{bibunit}[unsrt]

%\section{Sistema de medición alternativo}


\textbf{Resumen}

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. 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. 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. 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).

%\subsection{Introducción}
\section{Introducción}
Los sistemas de medición utilizados para cuantificar los niveles 
de Anonimato de los sistemas, mecanismos y herramientas aun se 
consideran un problema abierto. 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. 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. En este trabajo, se propone utilizar como alternativa 
dos índices para la medición del Anonimato, que explícitamente representen 
sus principales características. 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).


En Pfiztmann et al. \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. 
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. 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.

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}. Esta propuesta fue discutida en los trabajos 
de Díaz et al. \cite{rlsm:diaz01} y Serjantov et al. \cite{rlsm:serj01}, 
y desde entonces ha sido utilizada como base de medición en varios otros 
trabajos como el de Deng et al. \cite{rlsm:yuxin}, Edman et al. 
\cite{rlsm:combinatorial} y Gierlichs et al. \cite{rlsm:revisiting}. 
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. 

%\subsection{Trabajos Relacionados}
\section{Trabajos Relacionado}
Se han hecho varias propuestas para cuantificar el grado o nivel de 
anonimato provisto por los sistemas anónimos. En \cite{rlsm:reiter} 
definen el grado de Anonimato como $1 - p$, donde $p$ es la probabilidad 
asignada por el atacante a un sujeto particular. En \cite{rlsm:berthold} 
definen el grado de anonimato como $A=\log_2(N)$, donde $N$ es el 
número de sujetos (usuarios) del sistema. 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. 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}). 
Ninguna de las propuestas anteriores representa explícitamente el 
tamaño del conjunto anónimo y el índice de uniformidad. 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 $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. 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. 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. 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 $N=100$ sujetos, el segundo tiene $N=200$ sujetos, el tercero 
tiene $N=400$ sujetos y el cuarto tiene $N=800$ sujetos, los grados 
de Anonimato utilizando la entropía son: $6.6438$, $7.6438$, $8.6438$, 
$9.6438$, respectivamente. Estos escenarios, con la misma distribución 
de probabilidad y con diferente $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.
\begin{comment}
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. Esa es una restricción fuerte que no se ve justificada.
Lo que se muestra en torno al asunto sólo llega a requerir que sea una
función creciente.
\end{comment}

%\subsection{Propuesta}
\section{Propuesta}

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: $N$ o $1/N$, 
donde $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. 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).

%\subsubsection{Raíz del Error Cuadrático Medio - RSME}
\subsection{Raíz del Error Cuadrático Medio - RSME}

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. En análisis de regresión, es una cantidad observada 
dada un muestra en particular, y depende de dicha muestra. 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. Ésta también es una 
cantidad observada, y varía según la muestra y según el espacio fuera 
de la muestra probado.

\begin{equation}
RSME=\frac{\sqrt{(\bar{X}-X)^{2}}}{n(n-1)}
\end{equation}

En este caso, se propone utilizar $p_{i}=\frac{1}{N}$ (probabilidades en 
una distribución uniforme) para representar $\bar{X}$, y $p_{i}$, 
la probabilidad asignada por el atacante, se representa con $X$. Esta 
medida permite establecer la "distancia" de la distribución de 
probabilidad del atacante a la distribución uniforme. 

\begin{equation}
RSME_a=\frac{\sqrt{\displaystyle\sum_{i=1}^N (\frac{1}{N}-p_{i})^{2}}}{N(N-1)}
\end{equation}

Si un sistema tiene un $RSME_a\approxeq1$, esto quiere decir que 
provee un muy bajo nivel de anonimato.
Si otro sistema tiene un $RSME_a\approxeq0$, quiere decir que provee 
un buen nivel de anonimato. Pero también se debe observar el tamaño 
del conjunto anónimo para tomar un visión real del sistema.

%\subsubsection{Divergencia de Jennesen-Shannon}
\subsection{Divergencia de Jennesen-Shannon}

La divergencia de Jensen-Shannon es un método popular para medir 
la similitud entre dos o más distribuciones de probabilidad. Se basa 
en la divergencia de Kullback-Leibler, con la notable y útil diferencia 
que siempre da como resultado un valor finito. La raíz cuadrada 
de la divergencia de Jensen-Shannon es el índice que se propone para 
representar el índice de uniformidad en Anonimato.

\begin{equation}
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
\end{equation}

\begin{equation}
JSD_a(P_{1},P_{2})=\sqrt{JSD(P_{1},P_{2})}
\end{equation}

donde $\pi_i$ son lo pesos para la distribuciones de 
probabilidad $P_1,P_2$, en este caso $\pi_i=1, \nabla i=\{1,2\}$, 
y $H(P)$ es la entropía de Shannon para la distribución $P$. Es este 
caso, $P_1$ es una distribución uniforme y $P_2$ es la distribución 
de probabilidad del atacante.

Con este resultado se obtienen dos índices para representar el grado o 
nivel de Anonimato:


%\subsubsection{Resultados}
\subsection{Resultados}
\begin{description}
  \item[Opción 1:] Grado de Anonimato ($AD$) utilizando RMSE para medir 
el índice de uniformidad de la distribución de probabilidad 
y $1/N$ para medir el tamaño del conjunto anónimo.\\
  \begin{center}$AD =  1 / N \pm MSE_a$\end{center}
  \item[Opción 2:] Grado de Anonimato ($AD$) utilizando JSD para 
medir el índice de uniformidad de la distribución de probabilidad 
y $1/N$ para medir el tamaño del conjunto anónimo.\\
  \begin{center}$AD =  1 / N \pm JSD_a$\end{center}
\end{description}

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.

%\begin{thebibliography}{}

%\bibitem{terminology}
%Pfitzmann, A.,  Hansen, M.: Anonymity, Unobservability, and Pseudonymity: A Consolidated Proposal for Terminology. http://dud.inf.tu-dresden.de/Anon\_Terminology.shtml, (2000)

%\bibitem{diaz01}
%Diaz, C., Seys, S., Claessens J., Preneel, B.: Towards measuring anonymity. In: Proceedings of Privacy Enhancing Technologies Workshop (PET'02) - Springer LNCS 2482. pp. 54-68, (2002)

%\bibitem{serj01}
%Serjantov, A., Danezis, G.: Towards an Information Theoretic Metric for Anonymity. In: Proceedings of Privacy Enhancing Technologies Workshop (PET'02) - Springer LNCS 2482. (2002)

%\bibitem{shannon}
%Shannon, C.: The mathematical theory for communicactions. In: Bell Systems Technical Journal. pp. 30:50-64, (1948)

%\bibitem{yuxin}
%Deng, Y., Pang, J., Wu, P.: Measuring Anonymity with Relative Entropy. In: Proceedings of the 4th International Workshop on Formal Aspects in Security and Trust (FAST'06), Lecture Notes in Computer Science 4691. pp. 65-79, Springer, (2007)

%\bibitem{combinatorial}
%Edman, M., Sivrikaya, F., Yener, B.: A Combinatorial Approach to Measuring Anonymity. In: In Intelligence and Security Informatics. pp. 356-363, (2007)

%\bibitem{revisiting}
%Gierlichs, B., Troncoso, C., Diaz, C., Preneel, B., Verbauwhede, I.: Revisiting A Combinatorial Approach Toward Measuring Anonymity. In: Workshop on Privacy in the Electronic Society (WPES 2008), V. Atluri and M. Winslett (Eds.), pp. 111-116,  ACM Press, (2008)

%\bibitem{berthold}
%Berthold, O., Pfitzmann, A., Standtke, R.: The Disavantages of Free Mix Routes and How to overcome them. In: Hannes Federath (Ed.), Proceedings of Privacy Enhancing Technologies Workshop (PET'01), Lecture Notes in Computer Science. pp. 30-45, Springer-Verlag, (2001)

%\bibitem{reiter}
%Reiter, M., Rubin, A.: Crowds: Anonymity for Web Transactions. In: ACM Transactions on Information and System Security. vol. 1, no. 1, (1998)

%\bibitem{vernier}
%Vernier, D., and Gastineau, J.: What are Mean Squared Error and Root Mean Squared Error?. Article \#104. http://www.vernier.com/ (2011)

%\bibitem{jianhua}
%Jianhua, L.: Divergences Measures Based in Shannon Entropy. IEEE Transactions on Information Theory. vol. 37, no. 1 (1991)


%\end{thebibliography}




% el siguiente comando establece la ubicación de las referencias
\putbib[bibliografia]

% el siguiente comando cierra el ambiente bibunit para la cual se generan las
% referencias.
\end{bibunit}