Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
Le modèle de l-diversité
Comme énoncé ci-dessus, le modèle de l-diversité permet de contrer des attaques par liaison d’attributs. Il vient renforcer le k-anonymat en évitant, dans le cas où le QI d’une victime est connu, de cibler un enregistrement d’une table publiée et donc, de ce fait, de révéler de façon directe des données sensibles de la victime. Le principe de la l-diversité défini dans (Machanavajjhala et al. 2007) est le suivant :
Définitions : Une classe d’équivalence respecte la l-diversité s’il existe au moins l valeurs «bien représentées » pour l’attribut sensible. Une table respecte la l-diversité si chacune de ses classes d’équivalence respectent la l-diversité.
Notons que, derrière cette définition de la l-diversité, se cachent plusieurs dimensions selon l’interprétation donnée à l’expression « bien représentées » et au fait que l’on puisse disposer, dans une table, d’un ou plusieurs attributs sensibles. (Machanavajjhala et al. 2007) distinguent ainsi différentes dimensions ou modèles associés à la l-diversité. Le modèle le plus simple est le modèle « distinct l-diversity » que l’on nommera « l-diversité distincte ». Ce modèle n’accorde pas d’importance au terme « bien ». Il se concentre sur le reste de la définition c’est-à-dire l’obtention de classes d’équivalences l-diverses. Ainsi, dans ce modèle, on fait en sorte que, pour un attribut sensible, il existe au moins l valeurs représentées de cet attribut sensible au sein de tout groupe d’individu partageant le même QI. A titre d’exemple, le Tableau 4 possède la « 3-diversité distincte » (et le 4-anonymat) car chaque classe d’équivalence contient au moins trois valeurs distinctes de l’attribut ‘maladie’. Cependant, le Tableau 5 ne possède pas la « 3-diversité distincte » car la deuxième classe d’équivalence contient seulement deux valeurs distinctes de l’attribut sensible ‘maladie’. Cependant, il satisfait la « 2-diversité distincte ».
Le modèle de t-proximité
Bien qu’une table puisse être protégée par le principe de la l-diversité, il est possible pour un adversaire d’obtenir des informations au sujet d’un attribut sensible dès lors qu’il dispose d’informations sur la distribution globale de cet attribut. Pour contrer cela, la t-proximité (« t-closeness ») a été proposée par (N. Li, Li, et Venkatasubramanian 2007). Sachant qu’il est impossible d’empêcher un adversaire d’avoir des informations sensibles globales sur une population, le principe de la t-proximité a pour objectif de limiter la capacité de cet adversaire à déduire des informations sensibles sur des individus ciblés. Pour ce faire, il fait en sorte que la distribution de l’attribut sensible au sein de n’importe quelle classe d’équivalence soit proche de la distribution globale de l’attribut. En d’autres termes, il introduit le concept de distance entre ces deux distributions et propose que cette distance ne dépasse pas le seuil t. Ainsi, plus t est petit, plus la possibilité d’inférence de l’adversaire est réduite. D’où la définition suivante de ce principe proposée dans (N. Li, Li, et Venkatasubramanian 2007):
Définition 2: Une classe d’équivalence satisfait la t-proximité si la distance entre la distribution d’un attribut sensible dans cette classe et la distribution de l’attribut dans la table entière ne dépasse pas un seuil t. Une table satisfait la t-proximité si toutes ses classes d’équivalence satisfont la t-proximité.
Pour la mise en œuvre de ce principe, la distance EMD (Earth Mover’s Distance) est celle privilégiée dans la littérature. Son calcul diffère selon que l’attribut sensible est catégoriel ou continu. Il est détaillé dans (Rubner, Tomasi, et Guibas 2000).
Le modèle de δ-Présence
Le modèle de δ-Présence a été mis en œuvre dans l’objectif de contrer les attaques par «lien de tables». En effet, la publication de plusieurs tables anonymes par des éditeurs différents étant possible, on ne peut exclure la possibilité de rapprochement entre elles dès lors qu’elles partagent des valeurs de QI. Certains rapprochements peuvent mener à la divulgation de données sensibles. A titre d’exemple, supposons que le Tableau 2 sur les maladies a été publié au même titre que le Tableau 6 sur les catégories professionnelles.
Les techniques d’anonymisation de micro-données
Les données contenues sous forme agrégée dans des tables ont pendant longtemps constitué les sorties traditionnelles des organismes nationaux de statistique. Ainsi, la recherche sur la protection de ce type de données est la plus ancienne et la plus établie (Dalenius 1977). Elle a été essentiellement menée par la communauté des statisticiens travaillant sur le contrôle de divulgation statistique, connu sous le terme de SDC (Statistical Disclosure Control) et/ou sous celui de SDL (Statistical Disclosure Limitation).
En revanche, la protection des micro-données est plus récente. La recherche liée à la définition et la mise en œuvre des techniques d’anonymisation pour ce type de données bénéficie ainsi non seulement de l’apport de la communauté de statisticiens mais aussi de la communauté des informaticiens s’intéressant à la préservation de la vie privée à des fins de fouille de données connue sous le nom de PPDM (Privacy Preserving Data Mining) ou encore à la préservation de la vie privée à des fins de publication connue sous le nom de PPDP (Privacy Preserving Data Publishing). Le PPDM est un domaine de recherche visant à étendre les techniques traditionnelles de fouille de données de telle sorte à pouvoir manipuler des données où l’information sensible a été masquée (Aïmeur 2009) (Vaghashia et Ganatra 2015) (Verykios et al. 2004). Le PPDP étudie comment immuniser les données contre les attaques de la vie privée (Amita S., 2014) (Kiran et Kavya 2012). Une description des travaux de ces trois disciplines (SDC/SDL, PPDM, PPDP) est fournie dans plusieurs revues de la littérature dont (Hussien A.E.E.A., 2013) (B.M.Y, 2015).
Comme notre recherche ne requiert pas la présentation exhaustive de toutes les techniques recensées dans la littérature, nous nous concentrons, dans cette section, sur celles fréquemment citées. Ces dernières sont appliquées sur des attributs quasi-identifiants ou sensibles.
Nous allons donc décrire les principes généraux de quelques techniques en les illustrant au travers d’un exemple. Pour ce faire, nous exploitons le Tableau 7. Il représente un extrait de données originales médicales. La table est constituée de huit attributs : sexe, âge, profession, statut marital, âge, nombre de jours d’hospitalisation (JH), le taux de cholestérol et la température. Les quatre premiers attributs sont catégoriels et les autres sont continus.
La micro-agrégation (Defays et Nanopoulos 1992)
La micro-agrégation fait partie de la famille de techniques de SDC. Elle est appliquée à des micro-données continues. Elle contribue au renforcement du k-anonymat en faisant en sorte que les enregistrements correspondent à des groupes d’au moins k individus appelés micro-agrégats. Pour satisfaire la confidentialité des données, les valeurs originales sont remplacées par une mesure centrale (généralement la moyenne ou la médiane) du micro-agrégat auquel elles appartiennent. Ainsi, la micro-agrégation est réalisée en deux grandes étapes : le partitionnement et l’agrégation. Au cours du partitionnement, les groupes d’enregistrements sont construits de telle sorte que les enregistrements soient voisins dans le même groupe et que leur nombre dans chaque groupe soit au moins égal à k. Cette étape doit mettre en place des groupes aussi homogènes que possible. Dans la seconde étape, un opérateur d’agrégation est calculé pour chaque groupe. Ensuite, chaque enregistrement est remplacé par la valeur agrégée calculée pour le groupe auquel il appartient.
A titre d’exemple, nous allons appliquer la micro-agrégation à l’attribut ‘cholestérol’ dans le Tableau 7. La première étape consiste à diviser les enregistrements en groupes homogènes selon l’attribut âge afin de satisfaire le 3-anonymat. Par conséquent, nous trions les enregistrements selon l’attribut âge et nous constituons des groupes dont chacun doit contenir au minimum trois enregistrements comme le montre le tableau souvant.
La technique « Anatomy » (Xiao et Tao 2006)
Comme la technique de « bucketization », Anatomy permet de créer des tables l-diverses. Cette technique a été proposée dans l’objectif de contrer les désavantages de la généralisation. Anatomy casse le lien entre le QI et les attributs sensibles en créant deux tables séparées à partir d’une table originale. La première contient les valeurs du QI et des attributs non-sensibles (voir Tableau 13). La seconde contient les données sensibles. Pour établir le lien entre les deux tables, elle fait partager aux deux tables un attribut commun qui mentionne l’appartenance d’un tuple à un groupe (voir Tableau 14).
De façon informelle, Anatomy partitionne la table originale en groupes en adoptant une certaine stratégie de partitionnement. Ensuite, elle affecte à chaque partition un identifiant puis crée les deux tables et ajoute à chaque tuple des deux tables l’identifiant de partition adéquat.
Algorithmes et outils de généralisation de micro-données
Au cours de ces dernières années, une attention particulière a été accordée aussi bien par les statisticiens que par les informaticiens à la protection de la vie privée. Beaucoup de recherches ont ainsi ciblé la proposition de techniques et d’algorithmes diminuant le risque de ré-identification de données sensibles tout en maintenant leur utilité. Comme précisé dans le chapitre précédent, ces contributions se concentrent sur le contrôle statistique et/ou sur la publication des données et/ou sur la fouille de données. Dans ces trois contextes, la technique de généralisation semble être l’une des plus explorées. Elle est mise en œuvre via plusieurs algorithmes. Ces algorithmes ont non seulement l’objectif de préservation de la vie privée mais aussi celui de la qualité des données anonymisées qu’ils fournissent. Ils mettent tous en œuvre a minima le k-anonymat. Ils sont implémentés, pour certains d’entre eux, dans des logiciels commerciaux ou encore dans des prototypes issus de la recherche et dont l’utilisation n’est pas aussi triviale qu’on pourrait le penser.
Pour éviter que le processus de transformation des données par généralisation ne dégrade trop la précision de celles-ci et ne remette en cause, par-là, leur utilité, la plupart de ces algorithmes utilisent, au cours de leur processus, une métrique permettant d’orienter le codage des données. Ces métriques de guidage sont nommées dans (B. C. M. Fung et al. 2010) « search metrics ». Elles sont le plus souvent associées à un seul algorithme.
D’autres métriques de qualité ou d’évaluation existent, appelées « data metrics » (B. C. M. Fung et al. 2010). Elles permettent, comme leur nom l’indique, de mesurer la qualité des données de la table anonyme en la comparant à la qualité des données de la table originale.
Parmi ces deux types de métriques (de guidage ou de qualité), on distingue des métriques de compromis, des métriques pour tout usage que Fung appelle « general metrics » ou encore des métriques à usage spécifique. Une métrique pour tout usage, comme son nom l’indique, peut être utilisée quand l’on ne connaît pas l’usage des micro-données anonymisées. Une métrique de compromis, quant à elle, sert à établir un équilibre souhaité entre l’utilité des données et la préservation de la vie privée.
Dans ce chapitre, nous décrivons les algorithmes de généralisation de micro-données les plus connus. Ils sont au nombre de neuf : « μ-argus », « Datafly », l’algorithme de Samarati, « Incognito », « Bottom up généralisation », « Top Down spécialisation », « Median Mondrian », « Infogain Mondrian » et « LSD Mondrian ». Pour certains d’entre eux, la métrique de guidage associée est explicitée. Cette section est suivie par une description de quelques métriques d’évaluation proposées dans la littérature ainsi que par un état de l’art sur les outils d’anonymisation les implémentant. Une synthèse conclut ce chapitre.
Les algorithmes de généralisation de micro-données
Afin d’illustrer les neuf algorithmes, nous utilisons une table originale de laquelle a été supprimé préalablement l’identifiant des individus. Hormis l’identifiant, cette table est constituée de trois attributs sexe, code postal et niveau d’étude formant le quasi-identifiant (QI) et d’un attribut sensible appelé Salaire (Tableau 24). Chaque attribut du QI possède une hiérarchie de généralisation. La Figure 7, la Figure 8 et la Figure 9 représentent respectivement la hiérarchie de généralisation de l’attribut sexe, du code postal et du niveau d’étude. Dans ces figures, les niveaux de généralisation ont été identifiés par la première lettre de l’attribut correspondant à la généralisation et par un nombre mentionnant la position du niveau dans la hiérarchie. A titre d’exemple, pour la hiérarchie de la Figure 8, la valeur « 1305* » est au niveau « Z1 » de cette hiérarchie. Aussi, la valeur « Seconde » se trouvant dans la hiérarchie de la Figure 9 est au niveau « E0 » de cette hiérarchie. Une description détaillée des déroulements des neuf algorithmes sur la table originale (Tableau 24) est présentée dans l’annexe A.
L’algorithme Incognito (LeFevre, DeWitt, et Ramakrishnan 2005)
Incognito est également fondé sur un treillis. Cependant, le treillis est construit de manière itérative et incrémentale afin d’atteindre une plus grande efficacité. En d’autres termes, à la première itération, Incognito construit tous les treillis liés à un attribut du QI. Chaque treillis correspond à une hiérarchie de généralisation. Ces différents treillis sont nettoyés en supprimant tous les nœuds qui ne conduisent pas à une généralisation k-anonyme. A l’itération 2, Incognito construit, par fusion des treillis résultant de l’étape précédente, les treillis à deux attributs et, comme dans l’étape précédente, il procède à leurs nettoyages. Ce processus se poursuit de façon itérative jusqu’à ce que le treillis regroupant tous les attributs du QI soit construit et nettoyé.
A titre d’exemple, l’itération 1 de Incognito, appliquée au Tableau 24, fournira autant de treillis que d’attributs du QI (trois dans notre cas : un treillis pour le sexe, un autre pour le code postal et un autre pour le niveau d’étude). Tous les nœuds du premier treillis (c’est-à-dire S1 et S0) sont conservés car ils permettent de déduire une généralisation 2-anonyme. Ce qui n’est pas le cas des nœuds Z0 et E0 des deux autres treillis. Par conséquent, pour construire les treillis de l’itération 2 (c’est-à-dire le treillis fondé sur les attributs sexe et code postal, celui fondé sur l’attribut sexe et niveau d’étude ainsi que celui fondé sur les attributs code postal et niveau d’étude), Incognito ne considère que les treillis précédents satisfaisant le k-anonymat. Autrement dit, il exclut les nœuds Z0 et E0. Ainsi, pour le premier groupe d’attributs, on obtient le treillis suivant (voir Figure 15) :
La suite du déroulement pas à pas de cet algorithme est donnée dans l’annexe A de cette thèse. Notons que la construction par fusion des treillis dans Incognito repose sur trois propriétés citées et prouvées dans (LeFevre, DeWitt, et Ramakrishnan 2005).
Notons aussi que, bien que plus rapide que Samarati, Incognito est de complexité exponentielle, qu’il s’agisse du temps d’exécution ou de l’espace mémoire, relativement à la taille des données (Ayala-Rivera et al. 2014). Par conséquent, l’utilisation de ces deux algorithmes sur de gros volumes de données n’est pas conseillée. La Figure 16 correspond à l’algorithme Incognito tel que présenté dans (LeFevre, DeWitt, et Ramakrishnan 2005).
L’algorithme « Top down specialization » (B. C. Fung, Wang, et Yu 2005)
Comme la généralisation ascendante, la spécialisation descendante, communément appelée TDS ou algorithme « Top down specialization », est destinée à rendre les données propices à la classification. Cependant, contrairement à l’algorithme « bottom up généralization », TDS suit un parcours de la racine vers les feuilles des hiérarchies de généralisation.
Partant du principe qu’une généralisation maximale de toutes les valeurs de la table originale (c’est-à-dire dans laquelle toutes les valeurs sont remplacées par les valeurs des racines des hiérarchies de généralisation) permet de préserver le k-anonymat, mais affecte la qualité des données de la table résultante, l’algorithme effectue des itérations pour trouver et appliquer des spécialisations valides et bénéfiques, c’est-à-dire celles qui, non seulement, préservent le k-anonymat (contrainte de validité), mais qui génèrent aussi le moins de perte d’information, offrant ainsi une meilleure qualité pour la classification.
Soit S une spécialisation, notée aussi a{si}. S est la tâche consistant à remplacer, dans la table à anonymiser, la valeur « a » par l’une des valeurs filles « si » de {si} se trouvant dans la hiérarchie de généralisation. Elle est considérée comme valide si elle respecte le k-anonymat et si elle renvoie le meilleur score par application de la métrique de compromis IG/AL (InformationGain/Anonymityloss). Cette métrique permet de réaliser le compromis entre le gain d’information et la perte d’anonymat dus à la spécialisation.
Evaluation de la qualité d’une anonymisation de micro-données par généralisation
Comme mentionné en introduction de ce chapitre, en plus des métriques de guidage qui permettent d’orienter le codage des données, d’autres métriques existent. Il s’agit notamment de celles qui permettent d’évaluer la qualité des micro-données anonymes en la comparant à celle des données originales.
L’absence d’une mesure standard, qui serait largement acceptée par la communauté de chercheurs (Kiran et Kavya 2012), nous amène, dans cette section, à présenter les plus utilisées, sans toutefois pouvoir les lister toutes.
Métrique de complétude des données
Cette métrique trouve son utilité dans le cas où l’utilisation d’un algorithme peut générer des suppressions globales, donc une perte de données concernant certains individus. Elle mesure la complétude de la table anonyme relativement à la table originale par calcul du taux de suppressions effectuées. A titre d’exemple, si une table originale dispose de 100 tuples représentant autant d’individus et que l’anonymisation de cette table via un algorithme de généralisation a généré une table anonyme de 95 tuples, alors on pourra dire que l’anonymisation a permis de conserver 95% des données originales.
Métrique DM (Bayardo et Agrawal 2005)
Le k-anonymat, de par sa définition, oblige k individus à partager le même QI. Cette contrainte d’anonymat affecte négativement l’utilité des données. En effet, plus la taille de la classe d’équivalence est grande, plus l’utilité des données est amoindrie. Le rôle de la métrique DM (Discernability Metric) est d’informer l’éditeur des données sur la qualité des données résultant du degré de différenciation des individus. Ainsi, cette métrique affecte, à chaque tuple t, dans la table anonyme une pénalité déterminée par la taille de la classe d’équivalence représentant t et fait la somme des pénalités calculées.
Soit E l’ensemble des classes d’équivalence d’une table k-anonymisée. Ei est une des classes d’équivalence de E. La métrique DM peut être exprimée plus formellement de la façon suivante: DM Ei 2 Ei
A titre d’exemple, considérons la table originale disposant de 10 classes d’équivalence (Tableau 24). Sur les 10 classes, 8 sont composées d’un seul tuple et 2 de 2 tuples ; ce qui donne une valeur de DM pour cette table de 16 (=8*12+ 2*22). Si aucun tuple ne partageait la même valeur du QI avec un autre, DM aurait été de 12. Si tous les tuples partageaient la même valeur de QI, DM vaudrait 144 (=12*12). Le degré de non différenciation entre les tuples de la table résultante de l’application de l’algorithme Datafly (Tableau 36) est égal à 31 (=3*32+ 22 ) donc plus élevé que celui de la table originale.
|
Table des matières
Résumé en anglais
Table des matières
Liste des tableaux
Liste des figures
Liste des annexes
Chapitre 1 Introduction
1. Contexte et problématique de la thèse
2. Résumé des contributions de la thèse
Chapitre 2 : L’anonymisation de micro-données à des fins de publication
1 Notions préliminaires
2 L’anonymisation de micro-données
3 Modèles d’attaque de micro-données publiées
4 Modèles de protection de la vie privée
4.1 Le modèle de k-anonymat
4.2 Le modèle de l-diversité
4.3 Le modèle de t-proximité
4.4 Le modèle de δ-Présence
5. Les techniques d’anonymisation de micro-données
5.1 La généralisation (Samarati 2001)
5.2 La suppression (Lawrence H. 1980)
5.3 La micro-agrégation (Defays et Nanopoulos 1992)
5.4 La technique de « bucketization » (Martin et al. 2007)
5.5 La technique « Anatomy » (Xiao et Tao 2006)
5.6 La technique de “Slicing” (T. Li et al. 2012)
5.7 La permutation ou technique de “Swapping” (Dalenius et Reiss 1982)
5.8 Le recodage global (Domingo-Ferrer et Torra 2001), (Domingo-Ferrer et Torra 2002)
5.9 Les techniques de « Top Coding » et de « Bottom Coding » (Domingo-Ferrer et Torra 2001) (DomingoFerrer et Torra 2002)
5.10 Le bruit aléatoire (Brand 2002)
6. Synthèse
7. Conclusion
Chapitre 3 Algorithmes et outils de généralisation de micro-données
1. Les algorithmes de généralisation de micro-données
1.1. L’algorithme μ-Argus (Burton et al. 1997)
1.2. L’algorithme Datafly (Sweeney 1997)
1.3. L’algorithme de Samarati (Samarati 2001)
1.4. L’algorithme Incognito (LeFevre, DeWitt, et Ramakrishnan 2005)
1.5. L’algorithme « Bottom up generalization »
1.6. L’algorithme « Top down specialization » (B. C. Fung, Wang, et Yu 2005)
1.7. L’algorithme Median Mondrian (LeFevre, DeWitt, et Ramakrishnan 2006)
1.8. Les algorithmes « InfoGain Mondrian » et « LSD Mondrian »
1.9 Evaluation de la performance des algorithmes de généralisation
2. Evaluation de la qualité d’une anonymisation de micro-données par généralisation
2.1. Métrique de complétude des données
2.2 Métrique DM (Bayardo et Agrawal 2005)
2.3 Métrique CAVG (LeFevre, DeWitt, et Ramakrishnan 2006)(normalized average equivalence class size metric)
2.4 La métrique de précision PREC
2.5 La métrique GenILoss (Iyengar 2002) (Ayala-Rivera et al. 2014)
2.6 La métrique de classification (Iyengar 2002)
3. Les outils d’anonymisation de micro-données par généralisation
3.1 μ-argus
3.2 L’outil CAT
3.3 L’outil TIAMAT
3.4 L’outil SECRETA
3.5 L’outil PARAT
3.6 ARX Data Anonymization Tool [9]
4. Synthèse sur les algorithmes de généralisation de micro-données
4.1 Caractérisation des algorithmes de généralisation
4.2 Etude des résultats d’expérimentation des algorithmes
5. Synthèse sur les outils dédiés à la généralisation de micro-données
6. Conclusion
Chapitre 4 Notre proposition de guidage informatif pour la technique de généralisation et ses algorithmes
1. Intérêt de l’abstraction des algorithmes d’anonymisation
2. Notre processus d’abstraction des algorithmes d’anonymisation
2.1 Nos abstractions par paramétrage des algorithmes de généralisation
2.2 Notre processus de généralisation appliqué aux abstractions d’algorithmes
3. Validation des abstractions
4. Conclusion
Chapitre 5 Construction de l’Ontologie Pour l’Anonymisation de Micro-données (OPAM)
1. Etat de l’art sur la construction d’ontologies de domaine
1.1 La méthode « TOVE » (Gruninger et Fox 1995)
1.2 La méthodologie “METHONDOLOGY” (Fernández-López 1999)
1.3 La méthodologie “DILIGENT”
1.4 Le cadre méthodologique NeOn (Suárez-Figueroa, Gómez-Pérez, et Fernández-López 2012)
1.5 Discussion
2. Notre approche de construction d’OPAM
3. Phase d’acquisition des connaissances
4. Phase de conceptualisation
5. Formalisation et implémentation d’OPAM
6. Conclusion
Chapitre 6 Approche guidée pour l’anonymisation de micro-données
1. Présentation générale de MAGGO
2. Rappels sur l’approche AHP et la régression statistique
2.1 L’approche AHP
2.2 La régression
3. Etape de chargement et qualification du contexte de l’anonymisation
4. Etape de déduction et suggestion de signatures d’algorithmes candidates
4.1 Construction des signatures pertinentes
4.2 Evaluation théorique globale des signatures pertinentes
5. Conclusion
Chapitre 7 Conception, mise en œuvre et évaluation de MAGGO
1. Présentation du prototype
1.1 Principales composantes de la plateforme
1.2 Les outils et les technologies utilisées
1.3 Description des modules
2. Les interfaces de la plateforme
3. Evaluation de l’approche
3.1 Modèle d’utilisabilité
3.2 Procédure
3.3 Résultats
4. Conclusion
Chapitre 8 conclusion
Chapitre 9 Liste des publications de cette thèse
Bibliographie
Télécharger le rapport complet
