TL;DR
This paper tackles the challenge of "indirect attribute disclosure" in anonymized datasets, where seemingly innocuous attributes, when combined with external knowledge, can reveal sensitive information. They introduce novel privacy definitions (QS l-diversity and QS t-closeness) and a two-phase algorithm that combines generalization and suppression to protect against these sophisticated attacks.
What Problem Does This Paper Address?
Data anonymization aims to protect individual privacy while allowing data sharing for analysis. Traditional methods focus on preventing "identity disclosure" (linking records to individuals) and "direct attribute disclosure" (revealing sensitive attributes directly). However, a subtler threat exists: "indirect attribute disclosure." This occurs when attributes that are not sensitive on their own (quasi-sensitive attributes) can be linked with external, publicly available knowledge to infer sensitive information about an individual. For example, a patient's symptoms (like "coughing" and "headache") might not be sensitive, but when combined with a public database linking symptom sets to diseases, it could reveal that the patient has a specific illness. Existing privacy models like k-anonymity, l-diversity, and t-closeness primarily address direct attribute disclosure and struggle with this indirect leakage.
Methods
The authors propose a two-phase approach:
- QI Generalization: This phase uses standard generalization techniques (like Mondrian generalization) to achieve k-anonymity on the quasi-identifier (QI) attributes. This step reduces the number of unique QI groups, thereby simplifying the subsequent privacy protection phase.
- QS Suppression: This is the core novel contribution. For the quasi-sensitive (QS) attributes, they introduce two new privacy definitions:
- QS l-diversity: An extension of l-diversity that accounts for the probability of linking QS attribute values to sensitive labels, ensuring a minimum level of diversity in potential inferred sensitive information within a QI group.
- QS t-closeness: An extension of t-closeness that bounds the difference between an attacker's prior belief (before seeing the data) and posterior belief (after seeing the anonymized data) about an individual's sensitive label, based on QS attributes.
A greedy heuristic algorithm with adaptive tailset reordering is proposed for QS suppression. This algorithm explores a search tree of possible attribute suppressions, prioritizing branches that offer a significant privacy improvement (increase in l' for QS l-diversity) with minimal cost (increase in suppression cost). The algorithm aims to find an optimal solution within a given time bound.
Datasets
The experiments were conducted using:
- A dataset augmented from the Adult dataset (UCI Machine Learning Repository) with 3000 tuples. This dataset was modified to include 8 QI attributes and 9 synthesized QS terms per tuple.
- An external table with 3000 pieces of knowledge labels, linking random QS terms to sensitive information. The appearance of these terms in tuples followed a Poisson distribution.
Key Insights and Ideas
- The subtle threat of quasi-sensitive attributes: The paper highlights that privacy is not just about hiding directly sensitive information but also about preventing inferences from seemingly benign data when combined with external context.
- Formalizing indirect disclosure: The introduction of QS l-diversity and QS t-closeness provides a formal framework to reason about and quantify privacy risks arising from quasi-sensitive attributes and external knowledge.
- Effectiveness of the two-phase approach: Combining QI generalization with QS suppression offers a practical way to achieve robust privacy guarantees against indirect disclosure, balancing privacy and data utility.
- Adaptive suppression is key: The proposed QS suppression algorithm's adaptive nature, prioritizing promising branches and updating solutions, is crucial for efficiently finding good anonymization strategies within practical time limits.
Key Results
- The proposed QS suppression algorithm significantly outperforms a baseline DFS algorithm in terms of removal cost, especially when considering varying parameters like
landcfor QS (c,l)-diversity. - The two-phase anonymization approach provides bounded privacy guarantees for QS t-closeness.
- Experiments show that as
k(for k-anonymity) increases, the average removal cost generally decreases, indicating that generalization can reduce the burden on the suppression phase. - The paper demonstrates a flexible tradeoff between privacy and utility, allowing users to tune parameters like
t(for QS t-closeness) to achieve desired levels of privacy and information loss.
Limitations and Future Work
- Limitations: The paper acknowledges that the proposed QS suppression algorithm is greedy in its initial steps, though it aims for optimality by updating the best solution found. Practical time bounds are used to manage execution time.
- Future Work: The authors suggest several directions:
- Exploring alternative information loss metrics for term removal.
- Extending the algorithm to handle other attacks, such as minimality attacks.
- Investigating methods for constructing external knowledge bases.
Summary updated