Attaques d’inférence sur des bases de données
géolocalisées

Classification des attaques par inférence

Dans cette section, nous présentons une description détaillée des objectifs d’un adversaire lors de l’exécution d’une attaque par inférence sur des jeux de données géolocalisées. Nous supposons que l’adversaire est en possession d’un ensemble des données géolocalisées. Wernke et al. [WSDR12] présentent une classification en fonction de la connaissance préalable que l’adversaire peut avoir et qui sert également comme entrée pour l’attaque. Notamment, ils classent les attaques selon le type d’entré de l’attaque: la localisation singulière qui déduit la position ou l’identité d’un utilisateur en se basant sur une seule trace de mobilité; le contexte lié, qui combine des sources de données externes avec la trace de la mobilité pour acquérir des connaissances sur les utilisateurs; les localisations multiples qui tentent de corréler un ensemble des traces de mobilité pour découvrir des nouvelles informations sur l’utilisateur et la combinaison des localisations multiples et du contexte lié, qui est une combinaison des attaques susmentionnées. Les auteurs présentent également l’attaque de compromission d’une tierce entité de confiance, qui se réfère plus à un moyen de se procurer des données de localisation que d’une attaque visant briser la vie privé. Par ailleurs, dans notre classement, nous supposons que l’adversaire a accès à un ou plusieurs ensembles des données géolocalisées. Ces données constituent l’entrée pour les attaques par inférence, sous la forme de chaîne de Markov mobilité, comme connaissance préalable (cf. Section ??). Les tableaux en Annexe B montrent le résumé des attaques par inférence existantes dans la littérature ainsi que le type de données utilisées comme entrée. La Figure 1 résume la classification des attaques par inférence. La principale attaque par inférence est l’identification des points d’intérêt, ce qui permet ensuite de prédire les mouvements, l’extraction de la sémantique des POIs, désanonymizer (relier les enregistrements) et/ou découvrir des liens sociaux. Nous considérons que les attaques par inférence sont effectuées hors ligne. Un adversaire attaquant une base de données géolocalisées peut avoir diver objectifs allant de l’identification de la maison de la victime à la reconstruction de son réseau social. Plus précisément, les objectifs possibles, des attaques par inférence sont détaillés dans les paragraphes suivants. Identifier des endroits importants. Nous considérons que l’identification des lieux importants, appelé points d’intérêt (POI), caractérisent la mobilité d’un individu [KSBW04]. Un POI peut être par exemple le domicile ou le lieu de travail d’un individu ou des endroits comme un centre de sport, le théâtre ou le siège d’un parti politique. Révéler les POIs d’un individu particulier est susceptible d’entraîner une violation de sa vie privée, car ces données peuvent être utilisées pour déduire des informations sensibles telles que les loisirs, les croyances religieuses, les préférences politiques ou même des maladies potentielles [LFK07]. Par exemple, si une personne a visité un centre médical spécialisé dans un type spécifique de la maladie, alors on peut déduire qu’il a une probabilité non négligeable d’avoir cette maladie. Prédire les mouvements. Cette attaque prédit les habitudes de déplacement des individus tels que leurs emplacements passés, présents et futurs. Selon certains travaux récents [KSBW04, MD01], nos mouvements sont facilement prévisibles par nature. Par exemple, les auteurs de ces documents ont estimé à 93 % la chance de prédire correctement les futur emplacements d’un individu après une certaine période d’entraînement sur son schémas de mobilité [SQBB10]. Désanonymiser. L’objectif de l’attaque de désanonymisation est de relier les registres de la même personne qui peuvent être contenus dans des différents ensembles de données géolocalisées, que ce soit anonyme ou sous différents pseudonymes. Ce type d’attaque peut êtsre considéré comme l’équivalent du risque de divulgation statistique où la vie privée est mesurée selon le risque de lier le record de la même personne dans deux bases de données différentes (par exemple, en établissant qu’un individu particulier dans le registre de vote est aussi un patient spécifique d’un hôpital [Swe02]). Dans un contexte géolocalisé, l’objectif de cette attaque est d’associer les mouvements d’Alice (contenus par exemple dans le jeu de données A) avec le suivi de ses emplacements de son téléphone portable (enregistrés dans un autre ensemble de données B

Chaîne de Markov de mobilité

Une chaîne de Markov de mobilité (CMM) [GKNndPC11a] modèle le comportement de la mobilité d’un individu comme un processus stochastique discret dans lequel la probabilité de passer d’un état (i.e., POI) á un un autre ne dépend que de l’état précédemment visité et de la distribution de probabilité sur les transitions entre états. Plus précisément, une CMM est composée de: • Un ensemble d’états P = {P1,…Pn}, dans lequel chaque état est un POI fréquent (classés par ordre décroissant d’importance), il y peut avoir une exception par rapport au dernier état pn qui peut correspondre à l’ensemble composé de tous les POI peu fréquentés. Les POIs sont extraits en exécutant un algorithme de clustering sur les traces de mobilité d’un individu. Ces états sont associés à un lieu, et généralement ils ont aussi une signification sémantique intrinsèque. Par conséquent, les étiquettes sémantiques telles que “maison” ou “travail” peuvent souvent être déduites et attachées à ces états. • Transitions, comme ti,j , représentant la probabilité de passer de l’état pi à l’état Pj . Une transition d’un état à lui-même n’est possible que si l’individu a une probabilité non nulle de passer d’un état à un emplacement occasionnel avant de revenir à cet état. Par exemple, un individu peut quitter la maison pour aller à la pharmacie et ensuite revenir à son domicile. Dans cet exemple, il est probable que la pharmacie ne soit pas extraite comme un POI par l’algorithme de clustering, sauf si la personne se rend à ce lieu sur une base régulière et y reste pendant un temps considérable. Il faut noter que plusieurs modèles de mobilité basés sur les chaînes de Markov ont été proposés dans le passé [GKNndPC11a, AS03], y compris l’utilisation de modèles de Markov cachés pour extraire la sémantique des POIs [YCP+ 11a]. En un mot, la construction d’une CMM est un processus en deux étapes. Pendant la première phase, un algorithme de clustering est exécuté pour extraire les POI des traces de mobilité. Par exemple, dans le travail de Gambs et al. [GKNndPC11a], un algorithme de clustering appelé Density-Joinble Cluster (DJ-Cluster) a été utilisé (nous nous appuyons sur le même algorithme dans ce travail), mais bien sûr d’autres algorithmes de clustering sont possibles. Dans la deuxième phase, les transitions entre ces POIs sont calculées et intégrées dans le CMM. DJ-Cluster prend en entrée un ensemble des traces de mobilité en plus de trois paramètres: le nombre minimal de points M inP ts nécessaires pour créer un cluster, le rayon maximum r du cercle dans lequel les points d’un cluster doivent être délimités et le nombre minimal de jours pour considérer un point d’intérêt à être fréquents. DJ-Cluster fonctionne en trois phases. Pendant la première phase, qui correspond à une étape de prétraitement, toutes les traces de mobilité dans lequel l’individu se déplace à une vitesse supérieure à une petite valeur prédéfinie ainsi que des traces redondantes sont supprimées. En conséquence, seules les traces statiques sont conservées. La deuxième phase consiste dans le clustering elle-même: toutes les traces restantes sont traitées afin d’extraire les clusters qui ont au moins M inP ts des points à l’intérieur d’un rayon r du centre du cluster. Enfin, la dernière phase fusionne tous les groupes qui ont au moins une trace en commun. Une fois les POIs (i.e., les états de la chaîne de Markov) découverts, les probabilités des transitions entre les états peuvent être calculées. Pour réaliser F-5 Résumé cela, la piste des traces de mobilité est examinée dans l’ordre chronologique et chaque trace de mobilité est étiquetée avec une étiquette, soit le numéro d’identification d’un état particulier de la CMM, soit la valeur “inconnu”. Enfin, quand toutes les traces de mobilité ont été étiquetées, les transitions entre états sont comptées et normalisées par le nombre total de transitions afin d’obtenir les probabilités de chaque transition. Une CMM peut être représentée par une matrice de transition ou un graphe (cf., Figure 2) dans lequel les nœuds correspondent à des états et les flèches représentent les transitions entre les états et leur probabilité associée. Lorsque la CMM est représentée comme une matrice de transition de taille n × n, les lignes et les colonnes correspondent à des états de la CMM tandis que la valeur de chaque cellule est la probabilité de transition associée entre les états correspondants.

Prédire les mouvements

Afin de prédire le prochain emplacement sur la base des n dernières positions dans le modèle CMM, nous calculons une forme modifiée de la matrice de transition dont les lignes représentent les n dernières positions visitées. Ainsi, l’algorithme de prédiction a besoin en entrée des n derniers précédents endroits visités en plus du modèle de mobilité CMM. L’algorithme trouve la ligne correspondant à ces n emplacements précédents et recherche la transition la plus probable (les jeux décisifs sont rompus arbitrairement). S’il y a plus d’une colonne avec la même probabilité maximale, nous choisissons au hasard l’une d’entre elles. F-6 4. Prédire les mouvements

Evaluation expérimentale

Dans cette sous-section, nous présentons les expériences menées pour évaluer la précision de l’algorithme de prédiction et la prédicatabilité théorique d’utilisateurs. Dans ces expériences, nous avons utilisé trois ensembles de données différents: Arum (phonétique), Geolife et synthétique, dont les caractéristiques sont résumées dans le Tableau 1.2 de la Section 1.2.4. Afin d’évaluer l’efficacité de nos prédicteurs de localisation, nous calculons deux mesures: la précision et la prédicatabilité. La précision Acc est le rapport entre le nombre de prédictions correctes pcorrect et le nombre total de prédictions ptotal: P rcision = pcorrectes/ptotal. (1) La prédicatabilité pred est une mesure théorique qui représente la mesure dans laquelle la mobilité d’un individu est prévisible en fonction de son CMM (dans le même esprit que le travail de Barabasi et co-auteurs [SQBB10]). Par exemple, si la prédiction de l’emplacement sait que Bob était au travail (W) et qu’il est actuellement à la maison (H), la probabilité de faire une proposition réussie est théoriquement égale à la transition de probabilité sortant maximale, qui est 84 % pour cet exemple particulier (voir le Tableau 4.3). Plus formellement, la prédicatabilité P red d’une CMM particulier (et donc une personne en particulier) est calculé comme la somme des produits entre chaque élément du vecteur stationnaire π du modèle CMM, ce qui correspond à la probabilité d’être dans un état particulier (pour l, le nombre total d’états de cette CMM) et la probabilité sortant maximal (Pmax_out) de l’état k e : P red = l ∑ k=1 (π(k) × Pmax_out(k, ∗)). (2) Dans nos expériences, nous avons divisé chaque ensemble des traces de mobilité en deux groupes de même taille: l’ensemble d’apprentissage, utilisé pour construire la CMM, et l’ensemble d’entraînement, utilisé pour évaluer la précision du prédicteur. Enfin, nous calculons aussi le score moyen de la prédicatabilité pour chaque utilisateur en fonction de la CMM La Figure 3 montre les résultats obtenus pour un utilisateur à partir de l’ensemble de données Geolife avec n allant de 1 à 4 . Comme prévu, la précision s’améliore lorsque n augmente mais elle semble se stabiliser ou même diminuer légèrement lorsque n > 2. En outre, alors que sans surprise la précision de la prévision est généralement meilleure sur l’ensemble d’entraînement que sur l’ensemble de test , cette différence n’est pas significative. Cela semble indiquer que le comportement de mobilité d’un individu est similaire entre la deuxième partie de son ensemble de traces (le jeu de test) et la première partie de la trace (l’ensemble d’entraînement). Cela n’est pas nécessairement le cas si le comportement d’un utilisateur change naturellement en raison d’un changement important dans sa vie. Enfin, la Figure 4 affiche les résultats obtenus pour tous les utilisateurs des trois ensembles de données différents. Pour résumer, les résultats montrent de façon constante que la précision et la prédicatabilité sont optimales (ou presque optimales) lorsque n = 2, avec une précision et prédicatabilité allant de 70% à 95%. Comme nous pouvons le voir dans les deux métriques dans les ensembles de données Arum (Phonetic) et Geolife où ont tendance à suivre la même forme de la courbe décrite à la Figure 3. Le meilleur score est obtenu lorsque nous utilisons une CMM de deuxième ordre et en diminuant lorsque n tend F-7 Résumé à augmenter. Néanmoins, pour l’ensemble de données synthétique le score des deux indicateurs augmente lorsque n devient plus grand parce que nous observons les mêmes événements particuliers.