Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Dans les environnements pervasifs, le constant changement du contexte d'utilisation des applications et des services distribués (i.e., des ressources) impose de nouvelles exigences pour la définition des solutions de contrôle d'accès. Celles-ci concernait notamment la sensibilité au contexte et la mise en œuvre distribuée des politiques d'accès. Pour prendre en compte ces besoins, nous proposons une famille de modèles de contrôle d'accès, appelé CxtBAC (Context-Based Access Control), qui se compose de huit modèles conceptuels et permet d'explorer les informations contextuelles caractérisant les entités suivantes : le propriétaire de la ressource, l'environnement, l'utilisateur et la ressource elle-même. Contrairement aux propositions existantes, basées sur le modèle RBAC (Role-Based Access Control), la famille de modèle proposé est centrée sur la notion de contexte et non de rôle. Par conséquent, les décisions d'accès aux ressources protégées sont prises en considérant les informations contextuelles qui caractérisent la situation des entités impliquées. Pour décrire les règles d'accès, les permissions sont associées à des contextes d'accès et les utilisateurs sont associés dynamiquement à ces dernières. Les modèles proposés sont indépendants du langage de spécification de la politique de sécurité. Dans le cadre de cette thèse, nous proposons une solution pour la mise en ?uvre basée sur un formalisme d'ontologies.

Vu que les tags RFID sont actuellement en phase de large déploiement dans le cadre de plusieurs applications (comme les paiements automatiques, le contrôle d'accès à distance, et la gestion des chaînes d'approvisionnement), il est important de concevoir des protocoles de sécurité garantissant la protection de la vie privée des détenteurs de tags RFID. Or, la conception de ces protocoles est régie par les limitations en termes de puissance et de calcul de la technologie RFID, et par les modèles de sécurité qui sont à notre avis trop forts pour des systèmes aussi contraints que les tags RFID. De ce fait, on limite dans cette thèse le modèle de sécurité; en particulier, un adversaire ne peut pas observer toutes les interactions entre tags et lecteurs. Cette restriction est réaliste notamment dans le contexte de la gestion des chaînes d'approvisionnement qui est l'application cible de ce travail. Sous cette hypothèse, on présente quatre protocoles cryptographiques assurant une meilleure collaboration entre les différents partenaires de la chaîne d'approvisionnement. D'abord, on propose un protocole de transfert de propriété des tags RFID, qui garantit l'authentification des tags en temps constant alors que les tags implémentent uniquement des algorithmes symétriques, et qui permet de vérifier l'authenticité de l'origine des tags. Ensuite, on aborde le problème d'authenticité des produits en introduisant deux protocoles de sécurité qui permettent à un ensemble de vérificateurs de vérifier que des tags "sans capacité de calcul" ont emprunté des chemins valides dans la chaîne d'approvisionnement. Le dernier résultat présenté dans cette thèse est un protocole d'appariement d'objets utilisant des tags "sans capacité de calcul", qui vise l'automatisation des inspections de sécurité dans la chaîne d'approvisionnement lors du transport des produits dangereux. Les protocoles introduits dans cette thèse utilisent les courbes elliptiques et les couplages bilinéaires qui permettent la construction des algorithmes de signature et de chiffrement efficaces, et qui minimisent donc le stockage et le calcul dans les systèmes RFID. De plus, la sécurité de ces protocoles est démontrée sous des modèles formels bien définis qui prennent en compte les limitations et les contraintes des tags RFID, et les exigences strictes en termes de sécurité et de la protection de la vie privée des chaines d'approvisionnement.

L'émergence de terminaux mobiles personnels, capables à la fois de communiquer et de se positionner, entraîne de nouveaux usages et services personnalisés. Néanmoins, ils impliquent une collecte importante de données à caractère personnel et nécessitent des solutions adaptées en termes de sécurité. Les utilisateurs n'ont pas toujours conscience des informations personnelles et sensibles qui peuvent être déduites de leurs utilisations. L'objectif principal de cette thèse est de montrer comment des mécanismes cryptographiques et des techniques d'anonymisation de données peuvent permettre de concilier à la fois le respect de la vie privée, les exigences de sécurité et l'utilité du service fourni. Dans une première partie, nous étudions les accréditations anonymes avec vérification par clé. Elles permettent de garantir l'anonymat des utilisateurs vis-à-vis du fournisseur de service : un utilisateur prouve son droit d'accès, sans révéler d'information superflue. Nous introduisons des nouvelles primitives qui offrent des propriétés distinctes et ont un intérêt à elles-seules. Nous utilisons ces constructions pour concevoir trois systèmes respectueux de la vie privée : un premier système d'accréditations anonymes avec vérification par clé, un deuxième appliqué au vote électronique et un dernier pour le paiement électronique. Chaque solution est validée par des preuves de sécurité et offre une efficacité adaptée aux utilisations pratiques. En particulier, pour deux de ces contributions, des implémentations sur carte SIM ont été réalisées. Néanmoins, certains types de services nécessitent tout de même l'utilisation ou le stockage de données à caractère personnel, par nécessité de service ou encore par obligation légale. Dans une seconde partie, nous étudions comment rendre respectueuses de la vie privée les données liées à l'usage de ces services. Nous proposons un procédé d'anonymisation pour des données de mobilité stockées, basé sur la confidentialité différentielle. Il permet de fournir des bases de données anonymes, en limitant le bruit ajouté. De telles bases de données peuvent alors être exploitées à des fins d'études scientifiques, économiques ou sociétales, par exemple. / The emergence of personal mobile devices, with communication and positioning features, is leading to new use cases and personalized services. However, they imply a significant collection of personal data and therefore require appropriate security solutions. Indeed, users are not always aware of the personal and sensitive information that can be inferred from their use. The main objective of this thesis is to show how cryptographic mechanisms and data anonymization techniques can reconcile privacy, security requirements and utility of the service provided. In the first part, we study keyed-verification anonymous credentials which guarantee the anonymity of users with respect to a given service provider: a user proves that she is granted access to its services without revealing any additional information. We introduce new such primitives that offer different properties and are of independent interest. We use these constructions to design three privacy-preserving systems: a keyed-verification anonymous credentials system, a coercion-resistant electronic voting scheme and an electronic payment system. Each of these solutions is practical and proven secure. Indeed, for two of these contributions, implementations on SIM cards have been carried out. Nevertheless, some kinds of services still require using or storing personal data for compliance with a legal obligation or for the provision of the service. In the second part, we study how to preserve users' privacy in such services. To this end, we propose an anonymization process for mobility traces based on differential privacy. It allows us to provide anonymous databases by limiting the added noise. Such databases can then be exploited for scientific, economic or societal purposes, for instance.

Les nouvelles technologies introduisent de nouveaux problèmes et risques. Par exemple, les internautes sont constamment tracés et profilés sur l'Internet. Ce profilage permet aux divers sites de personaliser et ainsi d'améliorer le service qu'ils fournissent à chaque internaute. Cependant ce profilage introduit aussi des problèmes d'intimité et de protection de la vie privée. Il est d'ailleurs reconnu que ces données personnelles sont souvent échangées, voire vendues, et qu'il existe une vraie economie des données personnelles. Cet thèse étudie comment ces données personnelles, et en particulier les historique Web - c'est à dire la liste des sites Internet visités par un internaute-, sont collectées, échangées et vendues. Elle propose une analyse de la vie privée des systèmes de vente aux enchères des publicités ciblés. Elle montre comment les différents acteurs de la publicité en ligne collectent et s'echangent les données personnelles, et étudie les risques pour les Internautes. Elle propose également une analyse économique et montre, notamment, que les données sont bradées pour quelques millièmes de dollars. / New medias introduce new problems and risks. There are important security and privacy considerations related to online interactions. Users browsing the Web leave a constant trail of traces referring to their Web actions. A large number of entities take advantage of this data to constantly improve how the Web services function, often offering rich personalization capabilities -- to achieve this, user data is needed. To obtain user data, Web users are being tracked and profiled. Having user data may help enhancing functionality and usability, but it also has the potential of introducing complex privacy problems, related to data collection, storing and processing. The incentives to gather user data are of economical nature: user data is monetized. We start with a description of privacy problems and risks, highlighting their roots in technology changes; users must constantly struggle to adapt to changes. The legal frameworks relating to privacy are about to change: Web companies will have to adopt to new realities. First part of this thesis is devoted to measuring the consequences of private data leaks and tracking. We show how Web browsing history convey insight relating to user interests. We study the risks of Web browsing history leaks. We point out that browsing history is to large extent unique; we perform this basing on a dataset of more than 350k partial history fingerprints. The consequence here is that if browsing histories are personally identifiable information (PII), the upcoming European privacy legal frameworks could potentially result in strict guidelines for their collection, storing and processing. The tracking measurement of third-party resources confirms the popular notion that most of the tracking is carried by US-based companies. This creates interesting information asymmetries, which are of great importance, especially if user data could be simply equated to financial and economical benefits. Second part discusses value of privacy. We study the emerging technology of Real-Time Bidding (RTB), online real-time auctions of ad spaces. We highlight that during the auction phase, bidders in RTB obtain user information such as the visited Web site or user location and they pay for serving ads. In other words, user data flows are strictly related to financial flows. User data is thus monetized. We expose an interesting design characteristic of RTB which allows us to monitor a channel with winning bids -- dynamically established fees bidders pay for displaying their ads. We perform a detailed measurement of RTB and study how this price for user information varies according to such aspects like time of day, user location and type of visited Web site. Using data obtained from real users, we also study the effect of user profiles. Users are indeed treated differently, based on their previously visited Web sites (browsing history). We observed variability in prices of RTB ads, based on those traits. The price for user information in RTB is volatile and typically is in the range of $0.0001-$0.001. This study also had a decidedly important transparency part. We introduced a Web browser extension allowing to discover the price that bidders in RTB pay. This demonstrates how the user awareness could be improved. In part three, we continue the transparency trail. We point out that Web browsers allow every Web site (or third-party resources they include) to record the mouse movements of their visitors. We point out that recent advances in mouse movement analysis points to the notion that mouse movements can potentially be used to recognize and track Web users across the Web; mouse movement analysis can also be used to infer users' demographics data such as age. We highlight the existence of mouse movement analytics -- third-party scripts specializing in mouse movement collections. We also suggest that Web browser vendors should consider including permissions for accessing the API enabling these kind of recordings.

Les médias et de nombreuses études scientifiques évoquent fréquemment la notion de vie privée en lien avec des exemples de cyber attaques. Le vol par des hackers de 12 millions d’identifiants d’utilisateurs Apple en 2012 illustre que les objets communicants sont des maillons vulnérables exploités par les hackers pour accéder aux données personnelles des usagers. Dans cette thèse, nous allons étendre la notion de vie privée aux objets eux-mêmes, au-delà des utilisateurs, en montrant que dans des réseaux de capteurs sans fil où les communications ont lieu de machine à machine, la connaissance des adresses fixes des différents appareils constituant le réseau représente une source d’information permettant de déduire beaucoup d’éléments de contexte et d’environnement.Actuellement, tous les standards de communication sans fil intègrent la capacité de sécuriser les données transportées, y compris les protocoles de communication dédiés aux réseaux de capteurs, conçus pour fonctionner en milieu contraint et à basse consommation. Cependant, l’en-tête des trames envoyées sur l’air comportant les informations nécessaires au routage et au bon fonctionnement du réseau, figure toujours en texte clair. La collecte de ces métadonnées par écoute passive représente un danger pour les environnements et les applications qui font usage de ces réseaux.Le travail mené dans cette thèse a pour objectif d’explorer comment de simples attaques passives sur des réseaux meshés basés sur le standard IEEE 802.15.4, visant à collecter et exploiter les métadonnées de ces trames échangées sur l’air, permettent d’inférer des informations critiques sur le réseau lui-même, l’environnement dans lequel il est déployé et les comportements des personnes qui en font usage. Plusieurs solutions visant à dissimuler les adresses des nœuds du réseau sont ensuite étudiées. Ces solutions sont de deux types : soit elles rendent anonymes les dispositifs empêchant de remonter à la source des messages, soit elles reposent sur l’utilisation de pseudonymes permettant de conserver la possibilité d’auditer le trafic.Afin d’évaluer les caractéristiques et les performances de ces solutions, un simulateur a été mis en œuvre afin de reproduire le comportement d’un réseau de capteurs meshés embarquant l’OS Contiki. Ce simulateur a permis d’évaluer la solution la plus prometteuse issue de l’état de l’art, nommée MT6D, en comparant ses performances avec un réseau de référence ne dissimulant pas les métadonnées. Cette analyse a fait ressortir certains inconvénients, en particulier l’augmentation importante des trames de contrôle nécessaires au routage, et a permis d’élaborer les spécifications d’une solution plus optimale pour l’embarqué.Nous avons ainsi introduit Ephemeral, qui présente la capacité de dissimuler les adresses des dispositifs dans les messages envoyés sur l’air, par l’usage de pseudonymes, sans augmenter la quantité de trames de contrôle indispensables au routage. Une fois mis en œuvre avec le simulateur afin de valider les performances théoriques attendues, Ephemeral est déployé en environnement réel sur un réseau de capteurs IEEE 802.15.4 équipant un bâtiment. Ce retour d’expérimentation permet de confirmer qu’Ephemeral constitue une solution économe du point de vue de la consommation d’énergie et de la bande passante du réseau, pour masquer les identifiants des dispositifs impliqués dans les communications. / Privacy notion is frequently linked with cyber attack examples by media and scientific researches. In 2012, the hacking of 12 millions Apple user identifiers demonstrates that connected objects represent leaks exploited by hackers to access to user personal data. In this thesis, we will extend the privacy notion to the objects. To do this, we will show that in wireless sensor networks where communications are carried out from machine-to-machine, the knowledge of the static addresses of the devices within the network discloses information allowing deduction about elements of context and environment.Nowadays, the wireless communication standards provide security mechanisms whatever the communication protocols used including the low power ones designed to run on constrained environment. However, the frame header that comprises necessary information for routing and for the proper functioning of the network is always sent in clear text. Collecting and gathering these metadata by eavesdropping is dangerous for the environments and applications based on these networks.The work carried out in this thesis aims to explore how simple passive attacks on meshed networks based on IEEE 802.15.4 used to collect and exploit metadata allow to infer critical information about the network, the environment where the network is deployed and the behavior of users. Two kinds of solutions to hide the node addresses are studied. The first one provides anonymity for the devices. In the second kind of solutions, pseudonyms are used by nodes enabling the capability to audit the traffic within the network.To evaluate the characteristics and the performances of the solutions, a simulator has been used to reproduce the behavior of a meshed wireless sensor network embedding Contiki OS. This simulator allows to compare the performances of MT6D the most promising solution of our state of the art with that of a reference network do not mask the metadata. With this analyze, we can highlight some drawbacks and more especially the control frames overhead needed for the routing. We give the necessary specifications to deploy the most optimal solution for the embedded devices.Thus we propose Ephemeral that allows hiding device addresses provided in the sent frames by using pseudonyms without overhead on the control frames. After deployment in the simulation environment to evaluate expected theoretical performances, Ephemeral has been tested in real environment. The network is made up of twenty IEEE 802.15.4 sensor nodes deployed on a building. The results show that Ephemeral is an efficient low power and bandwidth-saving solution to hide device identifiers used in wireless communications.

Cette thèse porte sur un espace public urbain situé dans le quartier populaire des Quatre- Chemins à la frontière de Pantin et Aubervilliers. Elle s’intéresse secondairement à l’espace public local dessiné par les politiques publiques communales à l’attention des immigrés à Aubervilliers. Son objectif est de décrire comment des immigrés d’Afrique subsaharienne prennent place dans ces deux espaces. La thèse met au jour l’existence pour chaque espace public d’un opérateur de neutralisation. Celui-ci suspend localement la possibilité de rapporter les conduites des immigrés à leur culture supposée en les identifiant sur une base raciale. Dans l’espace public urbain, cet opérateur fonctionne différemment suivant plusieurs classes d’interaction. Dans l’espace public des politiques publiques, son bon fonctionnement dépend en grande partie de l’action de la municipalité et de sa capacité à éviter que l’on ne crée localement un problème de l’immigration. Cette ligne d’action est le fruit d’un héritage d’une histoire singulière du communisme municipal local. La thèse tente par la suite d’étudier plusieurs petits groupes d’immigrés venant des grandes villes d’Afrique de l’ouest et occupant durablement le quartier et notamment les cafés. Le quartier leur offrant à la fois une protection contre les discriminations et les incitant à partager durablement l’espace commun, ils prennent ici place en racontant peu à peu à d’autres ce qu’ils sont ; en rendant visible à l’attention du public des éléments de leur vie privée, en la mettant en scène. La thèse vise à comprendre le sens de ces mises en scène. Elle y voit le retour ambigu de la figure du travailleur immigré. Elle dévoile également la fragilité de la protection qu’offre l’espace du café pour éloigner de son esprit la dureté des relations conjugales. / This PHD deals with a public place located in a Parisian suburb named Les Quatre-Chemins. The neighborhood is divided into two areas. The main one is part of Aubervilliers and the second one of Pantin, two cities of la Seine Saint-Denis (93). Quatre- Chemins is very poor and a lot of migrants from different waves of recent migrations live here. As it is full of food shops, drugstores and coffee shops, and as it hosts a subway station, urban life is very intense there. Secondly, the PHD deals with a second public sphere composed by the residents who apply to different social and cultural local policies dedicated to migrants in the city of Aubervilliers. The goal of the PHD is to reveal how sub-Saharan African migrants take place in these two public places and talk about themselves and their private life. How they define what is public and what is private and how they present the private part of their lives. The PHD reveals that in both public spaces, the cultural background of these migrants is neutralized in first place. This means that a few unconscious tricks work so that it seems impossible for the audience to interpret the acts of migrants as something which would be completely determined by their supposed belonging to an assigned migrant community. They can then act as individuals. In the urban public place of Les Quatre-Chemins, the neutralizing operator is composed by different interactional situations. Quatre-Chemins is then close to what Elijah Anderson calls a “cosmopolitan canopy”. In the political and local public space, the neutralizing effect is due to a political and ideological position of the municipality itself. Then, the PHD aims to understand how distinct groups of African migrants from different big cities of Senegal, Ivory Coast and Mali, take place in the streets and coffee shops of Les Quatre- Chemins. How they interact with different people who don’t come from the same regions and how they present themselves, their ethnical background, their working conditions and their private lives.

La question de la sécurité privée est un sujet d'actualité. Ce secteur en pleine expansion a fait l'objet de réglementations ces dernières décennies. Sa particularité tient en la privatisation d'un domaine régalien de l'intervention étatique. La sécurité privée pose ainsi la problématique du traitement de la mission de sécurité. Si le secteur privé investit de plus en plus le domaine de la sécurité, il se différencie du secteur public. La participation du secteur privé s'effectue par voie contractuelle qui obéit pour partie de ses aspects au droit commun, malgré l'objectif de maintien de l’ordre public. / The issue of private security is a hot topic. This rapidly expanding sector has been the subject of regulations in recent decades. Its peculiarity lies in the privatization of a sovereign domain reserved for state intervention. Private security then poses the problem of processing the security mission. We note that the private sector is investing more and more in the field of security while differentiating itself from the public sector. The participation of the private sector is done by contract which obeys most of its aspects in common law.

Les réseaux sociaux en ligne (OSNs) recueillent une masse de données à caractère privé. Le recueil de ces données ainsi que leur utilisation relèvent de nouveaux enjeux économiques et évoquent plusieurs questionnements notamment ceux relatifs à la protection de la vie privée. Notre thèse propose certaines réponses.Dans le premier chapitre nous analysons l'impact du partage des données personnelles de l'utilisateur sur sa vie privée. Tout d'abord, nous montrons comment les intérêts d'un utilisateur -- à titre d'exemple ses préférences musicales -- peuvent être à l'origine de fuite d'informations sensibles. Pour ce faire, nous inférons les attributs non divulgués du profil de l'utilisateur en exploitant d'autres profils partageant les même ''goûts musicaux''. Notre approche extrait la sémantique des intérêts en utilisant Wikipedia, les partitionne sémantiquement et enfin regroupe les utilisateurs ayant des intérêts semblables. Nos expérimentations réalisées sur plus de 104 milles profils publics collectés sur Facebook et plus de 2000 profils privés de bénévoles, montrent que notre technique d'inférence prédit efficacement les attributs qui sont très souvent cachés par les utilisateurs.Dans un deuxième temps, nous exposons les conséquences désastreuses du partage des données privées sur la sécurité. Nous nous focalisons sur les informations recueillies à partir de profils publics et comment celles-ci peuvent être exploitées pour accélérer le craquage des mots de passe. Premièrement, nous proposons un nouveau « craqueur » de mot de passe basé sur les chaînes de Markov permettant le cassage de plus de 80% des mots de passe, dépassant ainsi toutes les autres méthodes de l'état de l'art. Deuxièmement, et afin de mesurer l'impact sur la vie privée, nous proposons une méthodologie qui intègre les informations personnelles d'un utilisateur afin d'accélérer le cassage de ses mots de passe.Nos résultats mettent en évidence la nécessité de créer de nouvelles méthodes d'estimation des fuites d'informations personnelles, ce que nous proposons : il s'agit d'une méthode formelle pour estimer l'unicité de chaque profil en étudiant la quantité d'information portée par chaque attribut public.Notre travail se base sur la plate-forme publicitaire d'estimationd'utilisateurs de Facebook pour calculer l'entropie de chaque attribut public. Ce calcul permet d'évoluer l'impact du partage de ces informations publiquement. Nos résultats, basées sur un échantillon de plus de 400 mille profils publics Facebook, montrent que la combinaison de sexe, ville de résidence et age permet d'identifier d'une manière unique environ 18% des utilisateurs.Dans la deuxième section de notre thèse nous analysons les interactions entre la plate-forme du réseau social et des tiers et son impact sur à la vie privée des utilisateurs.Dans une première étude, nous explorons les capacités de « tracking » des réseaux sociaux Facebook, Google+ et Twitter. Nous étudions les mécanismes qui permettent à ces services de suivre d'une façon persistante l'activité web des utilisateurs ainsi que d'évaluer sa couverture. Nos résultats indiquent que le « tracking » utilisé par les OSNs couvre la quasi-totalité des catégories Web, indépendamment du contenu et de l'auditoire.Finalement, nous développons une plate-forme de mesure pour étudier l'interaction entre les plates-formes OSNs, les applications sociales et les « tierces parties » (e.g., fournisseurs de publicité). Nous démontrons que plusieurs applications tierces laissent filtrer des informations relatives aux utilisateurs à des tiers non autorisés. Ce comportement affecte à la fois Facebook et RenRen avec une sévérité variable :22 % des applications Facebook testées transmettent au moins un attribut à une entité externe. Quant à, RenRen, nous démontrons qu'il souffre d'une faille majeure causée par la fuite du jeton d'accès dans 69 % des cas. / Sharing information between users constitutes the cornerstone of the Web 2.0. Online Social Networks (OSN), with their billions of users, are a core component of this new generation of the web. In fact, OSNs offer innovative services allowing users to share their self-generated content (e.g., status, photos etc.) for free. However, this free access is usually synonymous with a subtle counterpart: the collection and usage of users' personal information in targeted advertisement. To achieve this goal, OSN providers are collecting a tremendous amount of personal, and usually sensitive, information about their users. This raises concerns as this data can be exploited by several entities to breach user privacy. The primary research goals of this thesis are directed toward understanding the privacy impact of OSNs.Our first contribution consists in demonstrating the privacy threats behind releasing personal information publicly. Two attacks are constructed to show that a malicious attacker (i.e., any external attacker with access to the public profile) can breach user privacy and even threaten his online security.Our first attack shows how seemingly harmless interests (e.g., music interests) can leak privacy-sensitive information about users. In particular, we infer their undisclosed (private) attributes using the public attributes of other users sharing similar interests. Leveraging semantic knowledge from Wikipedia and a statistical learning method, we demonstrated through experiments ---based on more than 104K Facebook profiles--- that our inference technique efficiently predicts attributes that are very often hidden by users.Our second attack is at the intersection of computer security and privacy. In fact, we show the disastrous consequence of privacy breach on security by exploiting user personal information ---gathered from his public profile--- to improve the password cracking process.First, we propose a Markov chain password cracker and show through extensive experiments that it outperforms all probabilistic password crackers we compared against. In a second step, we systematically analyze the idea that additional personal information about a user helps in speeding up password guessing. We propose a methodology that exploits this information in the cracking process and demonstrate that the gain can go up to 30%.These studies clearly indicate that publicly disclosing personal information harms privacy, which calls for a method to estimate this loss. Our second contribution tries to answer this question by providing a quantitative measure of privacy. We propose a practical, yet formally proved, method to estimate the uniqueness of each profile by studying the amount of information carried by public profile attributes. To achieve our goal, we leverage Ads Audience Estimation platform and an unbiased sample of more than 400K Facebook public profiles. Our measurement results show that the combination of gender, current city and age can identify close to 55% of users to within a group of 20 and uniquely identify around 18% of them.In the second part of this thesis, we investigate the privacy threats resulting from the interactions between the OSN platform and external entities. First, we explore the tracking capabilities of the three major OSNs (i.e., Facebook, Google+ and Twitter) and show that ``share-buttons'' enable them to persistently and accurately track users' web activity. Our findings indicate that OSN tracking is diffused among almost all website categories which allows OSNs to reconstruct a significant portion of users' web profile and browsing history.Finally, we develop a measurement platform to study the interaction between OSN applications --- of Facebook and RenRen --- and fourth parties. We show that several third party applications are leaking user information to ``fourth'' party entities such as trackers and advertisers. This behavior affects both Facebook and RenRen with varying severity.