Data anonymity and truthfulness

Abstract

Nowadays, the vast adoption of technology, has enabled users to share many aspects of their personal lives. Social networks, GPS-enabled smartphones and portable health sensors are only some examples of data acquisition technologies. Although, the identity of users is removed prior to data publishing, data can still lead to privacy breaches. For instance, a person's identity, home address, financial data or even the medical history or lifestyle preferences may be identified. On the other hand, such data are extremely useful in several studies, such as demographical studies, human behaviour analysis and medical studies. Thus, transforming these data to protect users, in a way that the data remain meaningful, is crucial.Several anonymity methods have been proposed for protecting data, such as k-anonymity, l-diversity, k^m-anonymity and differential privacy. These methods can be applied either in relational datasets (e.g., datasets holding the demographics of a user) or in set-valued datasets (e.g., datasets holding the items bought by a person). As anonymity in relational data is widely studied, we focus our research on anonymity of set-valued datasets such as medical and trajectory datasets. We also formalize the notion of RT-datasets, which are datasets holding both relational and set-valued data (e.g., the demographics and diagnosis of patients).For trajectories datasets, we propose several methods to achieve anonymity and minimize the loss in data utility after anonymization. Initially, we present an approach adapting k^m-anonymity to trajectory data using distance-based generalization. We also develop an effective and efficient anonymization algorithm, which is based on the apriori principle. Then, we propose two more algorithms, preserving different data characteristics, including location distance and semantic similarity, as well as user-specified utility requirements, which must be satisfied to ensure that the released data can be meaningfully analyzed. We also propose a novel framework for anonymizing trajectory data that prevents the disclosure of both identity and sensitive location information, while retaining data utility. Our framework involves: (i) selecting similar trajectories, by employing Z-ordering or data projections on frequent subtrajectories, (ii) organizing the selected trajectories into carefully constructed clusters, and (iii) anonymizing each cluster separately. Finally, we propose four methods, offering protection from attackers controlling a set of disjoint locations. Our methods, employ suppression and splitting, transform the trajectories, and prevent such attackers from inferring locations unknown to them with high certainty. Our methods for the anonymization of trajectory datasets cover a wide range of attacks and a offer broad type of anonymity protection. As we outline in our experimental analysis, our methods protect the privacy of users and are efficient. At the same time they minimally distort the original dataset, thus, they allow useful and meaningful analysis and mining. Next, we focus on RT-datasets. Preserving the privacy and utility on RT-datasets is challenging, as it requires (i) guarding against malicious users, whose knowledge spans both attribute types, (ii) minimizing the overall information loss, and (iii) preserving data truthfulness. Existing anonymization techniques are not applicable to such datasets, and the problem cannot be tackled based on popular, multi-objective optimization strategies. Thus, we propose the first approach to address this problem. Based on this approach, we develop two frameworks to offer privacy, with bounded information loss in one attribute type and minimal information loss in the other. To realize each framework, we propose privacy algorithms that effectively preserve data utility, as verified by extensive experiments.We finally present a prototype system, called SECRETA, in order to assist users with limited background knowledge, to use and evaluate anonymity methods. In more detail, SECRETA allows users, to evaluate a specific algorithm, compare multiple algorithms, and combine algorithms for anonymizing datasets. The analysis of the algorithms is performed, in an interactive and progressive way, and results, attribute statistics and various data utility indicators, can be presented graphically.

Σήμερα, η καθολική υιοθέτηση της τεχνολογίας, παρέχει στους χρήστες τη δυνατότητα να διαμοιράζουν πολλές πτυχές της ζωής τους. Τα κοινωνικά δίκτυα, τα έξυπνα τηλέφωνα (smartphones) με ενσωματωμένο GPS και οι φορητοί βιομετρικοί αισθητήρες αποτελούν μόνο μερικά παραδείγματα τεχνολογιών καταγραφής δεδομένων. Παρά το γεγονός ότι τα ονόματα των χρηστών αφαιρούνται πριν από τη δημοσίευση των δεδομένων, τα δημοσιευμένα δεδομένα μπορούν να οδηγήσουν σε παραβιάσεις της ιδιωτικότητάς τους. Για παράδειγμα, η ταυτότητα ενός ατόμου, η διεύθυνση κατοικίας του, τα οικονομικά του στοιχεία ή ακόμα και το ιατρικό ιστορικό μπορούν να προσδιοριστούν. Από την άλλη πλευρά, τα δεδομένα αυτά είναι εξαιρετικά χρήσιμα σε διάφορες μελέτες, όπως δημογραφικές μελέτες, μελέτες ανάλυσης της ανθρώπινης συμπεριφοράς καθώς και ιατρικές μελέτες. Έτσι, η μετατροπή αυτών των δεδομένων για την προστασία των χρηστών, κατά τρόπο ώστε τα δεδομένα να παραμένουν χρήσιμα στους ερευνητές, είναι ζωτικής σημασίας. Αρκετές μέθοδοι ανωνυμίας έχουν προταθεί για την προστασία των δεδομένων, όπως η k-anonymity, η l-diversity, k^m-anonymity και η differential privacy. Αυτές οι μέθοδοι μπορούν να εφαρμοστούν είτε σε σχεσιακά δεδομένα (π.χ., δεδομένα που περιλαμβάνουν τα δημογραφικά στοιχεία) ή σε δεδομένα συναλλαγών (π.χ., σύνολα δεδομένων που περιλαμβάνουν όλα τα αντικείμενα που αγόρασε ή οι τοποθεσίες που επισκεύθηκε κάποιο άτομο). Καθώς η ανωνυμία σε σχεσιακά δεδομένα έχει μελετηθεί ευρέως, εστιάζουμε την έρευνά μας σε μεθόδους που αφορούν δεδομένα συναλλαγών, με έμφαση στα γεωχωρικά δεδομένα. Επίσης εισαγάγουμε την έννοια των RT-συνόλων δεδομένων, τα οποία είναι σύνολα δεδομένων που περιέχουν και σχεσιακά δεδομένα καθώς και δεδομένα συναλλαγών (π.χ., δημογραφικά στοιχεία και διαγνώσεις ασθενών). Σε σύνολα δεδομένων τροχιών, προτείνουμε διάφορες μεθόδους για να επιτευχθεί η ανωνυμία και να ελαχιστοποιηθεί η απώλεια της χρησιμότητας των δεδομένων μετά την ανωνυμοποίηση τους. Αρχικά, παρουσιάζουμε μια προσέγγιση η οποία υιοθετεί την μέθοδο k^m-anonymity σε δεδομένα τροχιών, χρησιμοποιώντας γενίκευση με βάση την απόσταση. Επίσης αναπτύσσουμε έναν αποτελεσματικό και αποδοτικό αλγόριθμο ανωνυμίας, ο οποίος βασίζεται στην αρχή Apriori. Προτείνουμε δύο ακόμα αλγορίθμους, οι οποίοι διατηρούν διαφορετικά χαρακτηριστικά των δεδομένων. Τα χαρακτηριστικά αυτά είναι η ελαχιστοποίηση των αποστάσεων μεταξύ σημείων, καθώς και η ικανοποίηση διαφόρων απαιτήσεων χρησιμότητας (οι κανόνες αυτοί ορίζονται από το χρήστη). Η ικανοποίηση αυτών των απαιτήσεων διασφαλίζει ότι τα δεδομένα που παράγονται είναι χρήσιμα και η ανάλυσή τους θα παρέχει ουσιαστικά αποτελέσματα.Ακολούθως, προτείνουμε ένα νέο πλαίσιο για την ανωνυμοποίηση των δεδομένων τροχιών, το οποίο αποτρέπει την αποκάλυψη της ταυτότητας καθώς και ευαίσθητων πληροφοριών για τις θέσεις τον ατόμων, διατηρώντας παράλληλα τη χρησιμότητα των δεδομένων.Το πλαίσιό μας αυτό περιλαμβάνει: (α) την επιλογή παρόμοιων τροχιών, με τη χρησιμοποίηση είτε Z-ordering είτε με προβολές των σημείων στις πιο συχνά εμφανίσιμες υποτροχιές, (β) την οργάνωση των επιλεγμένων τροχιών σε προσεκτικά κατασκευασμένες ομάδες, και (γ) την ανωνυμοποίηση κάθε ομάδας ξεχωριστά.Τέλος, παρουσιάζουμε τέσσερις μεθόδους, για την προστασία από χρήστες, οι οποίοι ελέγχουν διαφορετικά σετ από σημεία. Οι μέθοδοί μας, χρησιμοποιώντας διαγραφή σημείων ή διαχωρισμό τροχιών, μετασχηματίζουν τις τροχιές, ώστε να αποτρέψουν αυτούς τους χρήστες να ανακαλύψουν στοιχεία επισκεψιμότητας για σημεία που δεν ελέγχουν.Στη συνέχεια, εστιάζουμε στα RT-σύνολα δεδομένων. Η διαφύλαξη της ιδιωτικότητας και της χρησιμότητας στα RT-σύνολα δεδομένων είναι δύσκολη, καθώς απαιτεί (α) την προστασία από κακόβουλους χρήστες, των οποίων η γνώση εκτείνεται και στους δύο τύπους χαρακτηριστικών, και (β) τη διατήρηση της μέγιστης χρηστικότητας του ανώνυμου συνόλου δεδομένων. Οι υπάρχουσες τεχνικές ανωνυμίας δεν μπορούν να εφαρμοστούν σε τέτοια σύνολα δεδομένων, και το πρόβλημα δεν μπορεί να αντιμετωπιστεί με βάση τις δημοφιλής, στρατηγικές βελτιστοποίησης πολλαπλών στόχων. Έτσι, προτείνουμε μια πρώτη προσέγγιση για την αντιμετώπιση αυτού του προβλήματος. Με βάση αυτή την προσέγγιση, έχουμε αναπτύξει δύο πλαίσια τα οποία προστατεύουν την ιδιωτικότητα, οριοθετώντας την απώλεια πληροφορίας στον έναν τύπο χαρακτηριστικού και διατηρώντας τη μέγιστη δυνατή πληροφορία στο άλλο. Για την εφαρμογή κάθε πλαισίου, προτείνουμε αλγορίθμους που διατηρούν αποτελεσματικά τη χρηστικότητα των δεδομένων, όπως δείχνουμε και με εκτενή πειράματα. Παρουσιάζουμε τέλος ένα ολοκληρωμένο σύστημα, το SECRETA, προκειμένου να επιτρέψουμε σε χρήστες με ελάχιστες τεχνικές γνώσεις, να χρησιμοποιήσουν και να αξιολογήσουν τις διαθέσιμες μεθόδους ανωνυμίας. Συγκεκριμένα, το SECRETA επιτρέπει στους χρήστες να αξιολογήσουν μια μέθοδο ανωνυμίας, να συγκρίνουν μεταξύ τους διαφορετικές μεθόδους καθώς και να συνδυάσουν μεθόδους για την προστασία συνόλων δεδομένων. Η ανάλυση των μεθόδων γίνεται με ένα διαδραστικό και προοδευτικό τρόπο, και τα αποτελέσματα, συμπεριλαμβανομένων των στατιστικών για διαφορετικά χαρακτηριστικά των δεδομένων καθώς και διαφόρων δεικτών της χρησιμότητας τους, συνοψίζονται και παρουσιάζονται γραφικά.