1、Anatomy: Simple and Effective Privacy Preservation,Israel Chernyak DB Seminar (winter 2009),Example,Hospital wants to release patients medical records Attribute Disease is sensitive. Age, Sex, and Zipcode are the quasi-identifier (QI) attributes.,Generalization,A widely-used technique for preserving
2、 privacy. Tuples are divided into QI-groups. QI-values are transformed into less specific forms. Tuples in the same QI-group cannot be distinguished by their QI-values.,Introduction,Anatomy a technique for publishing sensitive data. Protects privacy. Allows effective data analysis. More effective th
3、an the conventional generalization. Permits aggregate reasoning with average error below 10%. Lower than the errors produced by generalization by orders of magnitude.,Measuring the degree of privacy preservation,Two notions, k-anonymity and l-diversity, have been proposed to measure the degree of pr
4、ivacy preservation.,K-anonymity,A table is k-anonymous if each QI-group involves at least k tuples The next table is 4-anonymous.Even with a large k, k-anonymity may still allow an adversary to infer the sensitive value of an individual with extremely high confidence.,Where k-anonymity fails,4-anony
5、mous table Last group has no privacy Background knowledge attacks are still possible.,L-diversity,A table is l-diverse if, in each QI-group, at most 1/l of the tuples possess the most frequent sensitive value.,Defects of Generalization in Analysis,Generalization helps preserve privacy. In terms of l
6、-diversity. A trade-off exists between: Keeping the sensitive data private. Publishing records for research and analysis.,Defects of Generalization in Analysis an example,A researcher wants to estimate the result of the following query:,Defects of Generalization in Analysis an example (cont.),Defect
7、s of Generalization in Analysis an example (cont.),Recall that the answer we got was 0.1, which, however, is 10 times smaller than actual query result. Caused by the fact that the data distribution in R1 significantly deviates from uniformity. Nevertheless, given only the generalized table, we canno
8、t justify any other distribution assumption. This is an inherent problem of generalization preventing an analyst from correctly understanding the data distribution inside each QI-group.,Anatomy,Anatomy vs. Generalization,Anatomy announces the QI values directly. Permits more effective analysis than
9、generalization.,Anatomy vs. Generalization example (cont.),Given the previous query:We proceed to calculate the probability p that a tuple in the QI-group falls in Q.,Anatomy vs. Generalization example (cont.),No assumption about the data distribution is necessary Because the distribution is precise
10、ly released.,Actual answer,Privacy Preservation,Anatomy provides a convenient way for the data publisher to find out for each tuple t: The sensitive values that an adversary can associate with t. The probability of association.,Pneumonia,Dyspepsia,flu,?,?,?,p1=0.5,p2=0.5,Conclusion,Given a pair of Q
11、IT and ST, an adversary can correctly reconstruct any tuple with a probability at most 1/l. Therefore, the adversary can correctly infer the sensitive value of any individual with probability at most 1/l.,Anatomy vs. Generalization,Anatomy, isnt an all-around winner: Anatomy releases the QI-values d
12、irectly. Intuitively, it may provide a higher probability breach than generalization. Nevertheless, such probability is always bounded by 1/l As long as the background knowledge of an adversary isnt stronger than the level allowed by the l-diversity model.,Assumptions weve made so far,Assumption 1:
13、The adversary has the QI-values of the target individual. Assumption 2: The adversary knows that the individual is definitely involved in the data. In fact, usually both assumptions are satisfied in practical privacy-attacking processes.,Assumptions - conclusion,In general, if both assumptions are t
14、rue, anatomy provides as much privacy control as generalization The privacy of a person is breached with a probability at most 1/l.,Anatomy where its privacy fails,An adversary that can make the first assumption (knowing the QI-values) But not the second (existence of target in database) The overall
15、 breach probability:,Anatomy where its privacy fails (cont.),Each member can be involved with equal likelihood,P(Alice is in the table) = 4/5,P(Alice is in the table) = 1,Nevertheless, the upper bound for this is still 1/l,Privacy in generalization vs privacy in anatomy - conclusion,Although general
16、ization has the above advantage over anatomy, the advantage cannot be leveraged in computing the published data. This is because the publisher cannot predict or control the external database to be utilized by an adversary, and therefore, must guard against an “accurate” external source that does not
17、 involve any person absent in the published data.,Anatomizing Algorithm group creation phase,Anatomizing Algorithm hashing tuples,23, M, 11000, pneumonia,27, M, 13000, dyspepsia,35, M, 59000, dyspepsia,59, M, 12000, pneumonia,61, F, 54000, flu,65, F, 25000, gastritis,65, F, 25000, flu,70, F, 30000,
18、bronchitis,pneumonia,dyspepsia,flu,gastritis,bronchitis,Anatomizing Algorithm group creation phase,Property 1: At the end of the group creation phase each non-empty bucket has only one tuple. Only if at most n/l tuples are associated with the same As value.,Anatomizing Algorithm group creation (l=2)
19、,pneumonia,dyspepsia,flu,gastritis,bronchitis,23, M, 11000, pneumonia,59, M, 12000, pneumonia,27, M, 13000, dyspepsia,35, M, 59000, dyspepsia,61, F, 54000, flu,65, F, 25000, flu,65, F, 25000, gastritis,70, F, 30000, bronchitis,Anatomizing Algorithm residue-assignment phase,Property 2: the set S (com
20、puted at line 11) always includes at least one QI-group. Property 3: after the residue-assignment phase, each QI-group has at least l tuples, and all tuples in each QI-group have distinct As values.,Anatomizing Algorithm populating the tables,Reconstruction error,We model each tuple t as a probabili
21、ty density function:Note that both x and t are tuples, so x=t means xi=ti for all i.,Reconstruction error (cont.),Given an approximation probability density function , the error from the actual probability density function is:A good publication method should minimize the following reconstruction err
22、or (RCE):,Algorithm error bounds,If the cardinality n of T (the original table) is a multiple of l, the QIT and ST computed by Anatomize achieve the lower bound of RCE. n(1-1/l) Otherwise, the RCE of the anatomized tables is higher than the lower bound by a factor at most 1 + 1/n .,Summary,Privacy v
23、s publication for research a serious concern. Existing method (generalization) allows privacy, but doesnt allow very accurate research. Anatomy a method that provides both good privacy (in terms of l-diversity) and allows for accurate research.,Summary (cont.),A nearly-optimal algorithm for anatomiz
24、ing tables. Achieves the minimal possible error (or close to it). Complexity is linear. Simple and can be implemented easily. Experiments have shown that Anatomy has an average error of below 10%, as opposed to over 100% error of generalization. Only the case with a single sensitive attribute is investigated (the rest is left to future work). Background knowledge of attacker is neglected.,
