TL;DR
This paper introduces a novel privacy-preserving method for hierarchical data, addressing the limitations of existing techniques in preventing similarity attacks. By employing fuzzy set theory to assign multi-level sensitivity to data attributes, they propose a new privacy model, (alev, k)-anonymity, and an algorithm to achieve it, demonstrating improved security and data utility compared to prior methods.
What Problem Does This Paper Address?
In today's data-driven world, organizations increasingly need to publish semi-structured and hierarchical data for research and decision-making. However, this data often contains sensitive personal information that must be anonymized to protect individual privacy. Traditional anonymization methods, like k-anonymity and l-diversity, have been effective for relational data but struggle with the complex structure of hierarchical data. Furthermore, existing methods for hierarchical data, such as ClusTree, can be vulnerable to "similarity attacks." These attacks exploit the fact that even if an attacker cannot pinpoint an exact sensitive value, they can infer a range of sensitive values with high probability, thus compromising privacy. This paper tackles this challenge by proposing a more robust privacy model and anonymization approach specifically designed for hierarchical data, aiming to mitigate similarity attacks and enhance overall data privacy.
Methods
The core innovation of this paper lies in its use of fuzzy set theory to assign multi-level sensitivity to data attributes.
- Fuzzy Set Theory for Sensitivity Levels: Instead of treating sensitive attribute values as discrete or binary, the authors use fuzzy sets to partition numerical and categorical attribute values into five levels: low, very low, middle, very high, and high. For numerical attributes, this involves defining membership functions (using trapezoidal distributions) that map values to these levels. For categorical attributes, frequencies of values are used to derive numerical representations, which are then subjected to the same fuzzy partitioning.
- Multi-Level Sensitivity: These value levels are then transformed into sensitivity levels. The paper notes that the relationship between value level and sensitivity level can be inverse (e.g., higher GPA is less sensitive) or direct (e.g., higher income is more sensitive). This multi-level sensitivity is crucial for differentiating the privacy protection needed for various attributes.
- (alev, k)-anonymity Model: Based on these multi-level sensitivities, the authors propose a new privacy model called (alev, k)-anonymity for hierarchical data. This model requires that for any equivalence class in the anonymized data, there are at least k records, and the frequency of sensitive values within each sensitivity level i does not exceed k times alev[i]. This constraint directly addresses the similarity attack by controlling the distribution of sensitive values across different sensitivity levels.
- Anonymization Algorithm: The paper presents a two-part anonymization algorithm:
- MLevAnonytree: This algorithm handles the anonymization of two hierarchical data records or class representatives. It involves checking for union-compatibility and then either suppressing subtrees or generalizing QI values to satisfy the (alev, k)-anonymity constraint, minimizing information loss.
- MLevCluTree: This algorithm anonymizes the entire hierarchical dataset using a clustering approach. It iteratively builds equivalence classes by selecting records that minimize information loss when added to an existing class, ensuring the (alev, k)-anonymity property is met.
Datasets
The authors experimented with two synthetic datasets that were previously used in [16]. These datasets were synthetically modeled based on real information of graduates from Sabanci University in Turkey.
- Dataset A: Has two levels (h=2), structured as (major program, year of birth) → courses, containing 1000 students and approximately 20 courses per student.
- Dataset B: Has three levels (h=3), structured as (major program, year of birth) → courses → teachers, also with 1000 students, approximately 20 courses per student, and one to two teachers per course.
The paper does not introduce new benchmark datasets.
Key Insights and Ideas
- Fuzzy Sets for Nuanced Privacy: The paper highlights the power of fuzzy set theory in moving beyond binary or discrete classifications of sensitive data. By allowing for degrees of membership in sensitivity levels, it provides a more granular and realistic approach to privacy.
- Multi-Level Sensitivity is Key to Resisting Similarity Attacks: The core insight is that simply ensuring a certain number of distinct sensitive values (like in l-diversity) is insufficient. Differentiating the sensitivity of these values and controlling their distribution across these levels is crucial for preventing attackers from inferring probabilistic information.
- Hierarchical Data Demands Specialized Models: The work underscores that standard privacy models for relational data are not directly applicable to hierarchical structures. The proposed (alev, k)-anonymity model and the MLevAnonytree/MLevCluTree algorithms are tailored to the nested nature of hierarchical data.
- Trade-off Between Security and Utility: The experimental results clearly show that while the proposed approach offers stronger privacy protection and lower information loss (better utility), it comes at a slightly higher computational cost. This is presented as an acceptable trade-off for offline anonymization processes.
Key Results
The experimental results demonstrate the effectiveness of the proposed MLevClusTree algorithm compared to the existing Clustree method:
- Data Utility (Information Loss): MLevClusTree consistently shows lower information loss than Clustree across both datasets and varying values of k. For instance, on Dataset B (h=3), the information loss is notably lower, indicating better data utility.
- Data Security (Dissimilarity Degree): The MLevClusTree algorithm achieves a higher dissimilarity degree of equivalence classes compared to Clustree. This indicates that the anonymized data is more resistant to similarity attacks and offers stronger privacy protection.
- Efficiency (Execution Time): The execution time for MLevClusTree is slightly higher than Clustree, especially as k increases. This is attributed to the additional checks required to ensure sensitive values do not exceed the given thresholds across different sensitivity levels. However, the authors deem this increase acceptable for offline anonymization.
Limitations and Future Work
- Computational Cost: While the authors state the increased execution time is acceptable for offline processes, it remains a limitation. Future work could focus on optimizing the anonymization algorithms for greater efficiency.
- Parameter Selection: The paper uses fuzzy sets to partition values into five levels and defines sensitivity levels. The choice of five levels and the specific parameters for fuzzy set membership functions might be further explored or adapted for different domains.
- Generalization of Fuzzy Sets: The paper mentions that for categorical attributes, frequency is used to derive numerical values for fuzzy partitioning. Further research could explore more sophisticated methods for converting categorical data into fuzzy representations.
- Real-World Datasets: The experiments were conducted on synthetic datasets. Evaluating the proposed approach on diverse real-world hierarchical datasets would provide more comprehensive validation.
Summary updated