Generating Minimality-Attack-Resistant Data

• US 20110321169A1
• Filed: 06/29/2010
• Published: 12/29/2011
• Est. Priority Date: 06/29/2010
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cormode, Graham, Li, Tiancheng, Srivastava, Divesh
• Granted Patent: US 8,631,500 B2
• Time in Patent Office: Days
• US Class Current: 726/26
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

The present disclosure is directed to systems, methods, and computer-readable storage media for generating data and data sets that are resistant to minimality attacks. Data sets having a number of tuples are received, and the tuples are ordered according to an aspect of the tuples. The tuples can be split into groups of tuples, and each of the groups may be analyzed to determine if the group complies with a privacy requirement. Groups that satisfy the privacy requirement may be output as new data sets that are resistant to minimality attacks.

Claims

1. A computer-implemented method for generating data that is resistant to minimality attacks, the method comprising computer-implemented operations for:

receiving a data set at an anonymization engine, the data set comprising a plurality of tuples;

ordering the tuples in the data set according to an aspect of the tuples;

generating a plurality of groups of the tuples, wherein each group satisfies a privacy requirement.

2. The method of claim 1, further comprising partitioning the tuples into buckets, the buckets comprising a predefined number of tuples.

3. The method of claim 2 further comprising:

selecting a bucket of the plurality of buckets as a group;

determining if the group satisfies a privacy requirement; and

taking an action based upon the determining.

4. The method of claim 3, wherein the privacy requirement comprises l-diversity, and the predefined number of tuples comprises l.

5. The method of claim 3, wherein taking the action comprises:

determining if additional buckets of the buckets are available, in response to determining that the group does satisfy the privacy requirement; and

outputting a new data set comprising the group, in response to determining that the additional buckets are not available.

6. The method of claim 3, wherein taking the action comprises:

determining if first additional buckets of the buckets are available, in response to determining that the group does not satisfy the privacy requirement; and

outputting the data set, in response to determining that the first additional buckets are not available.

7. The method of claim 6 further comprising:

merging an additional bucket of the additional buckets into the group to obtain a new group, in response to determining that the additional buckets are available;

determining if the new group satisfies the privacy requirement;

determining if second additional buckets are available, in response to determining that the new group does satisfy the privacy requirement; and

outputting a new data set comprising the new group, in response to determining that the second additional buckets are not available.

8. The method of claim 7, further comprising:

identifying a noncompliant group that does not satisfy the privacy requirement; and

removing the noncompliant group before outputting the new data set.

9. The method of claim 3, wherein taking the action comprises:

determining if additional buckets of the plurality buckets are available, in response to determining that the group does satisfy the privacy requirement;

selecting a new group, in response to determining that the additional buckets are available;

determining if the new group satisfies the privacy requirement; and

taking an action based upon the determining.

10. The method of claim 1, further comprising:

splitting the data set into a plurality of data set groups;

determining if a selected data set group of the plurality of data set groups satisfies a privacy requirement; and

taking an action based upon the determining.

11. The method of claim 10, further comprising merging the plurality of data set groups together to obtain the data set and outputting the data set, in response to determining that the selected data set group does not satisfy the privacy requirement.

12. The method of claim 10, further comprising:

selecting a data set group of the plurality of data set groups;

determining if the data set group of the plurality of data set groups satisfies the privacy requirement; and

splitting the data set group of the plurality of data set groups, in response to determining that the group of the plurality of groups does satisfy the privacy requirement.

13. The method of claim 5, wherein:

the tuples comprise sensitive data and non-sensitive data, the sensitive data comprising quasi-identifiers and sensitive attributes;

the aspect of the tuples comprises the non-sensitive data; and

the new data set further comprises the quasi-identifiers and the sensitive attributes.

14. The method of claim 1, wherein the data set comprises data collected from a telecommunications network.

15. A system for generating data that is resistant to minimality attacks, the system comprising a processor for executing computer-executable instructions stored in a memory, the execution of which cause the system to:

receive a data set comprising a plurality of tuples, each of the tuples comprising sensitive data and non-sensitive data;

order the tuples in the data set according to the non-sensitive data; and

generate a plurality of groups of the tuples, wherein each group satisfies a privacy requirement.

16. The system of claim 15, wherein execution of the computer-executable instructions cause the system to:

partition the tuples into a plurality of buckets, each of the plurality of buckets comprising a predefined number of tuples;

select a bucket of the plurality of buckets as a group;

determine if the group satisfies a privacy requirement; and

take an action based upon the determining.

17. The system of claim 15, wherein execution of the computer-executable instructions cause the system to:

split the data set into a plurality of data set groups;

determine if a selected data set group satisfies a privacy requirement; and

take an action based upon the determining.

18. A computer-readable storage medium comprising computer-executable instructions, executable by an anonymization engine to provide a method for generating data resistant to minimality attacks, the method comprising:

receiving a data set at an anonymization engine, the data set comprising a plurality of tuples comprising sensitive data and non-sensitive data;

ordering the tuples in the data set according to the non-sensitive data; and

generating a plurality of groups of the tuples, wherein each group satisfies a privacy requirement.

19. The computer-readable storage medium of claim 18, wherein the method further comprises:

partitioning the tuples into a plurality of buckets, each of the plurality of buckets comprising a predefined number of tuples;

selecting a bucket of the plurality of buckets as a group;

determining if the group satisfies a privacy requirement;

in response to determining that the group does satisfy the privacy requirement;

determining if additional buckets of the plurality of buckets are available;

outputting a new data set comprising the group, in response to determining that the additional buckets are not available; and

in response to determining that the group does not satisfy the privacy requirement, outputting the data set.

20. The computer-readable storage medium of claim 18, wherein the method further comprises:

splitting the data set into a first plurality of data set groups;

selecting a data set group of the first plurality of data set groups;

determining the data set group of the first plurality of data set groups satisfies a privacy requirement;

in response to determining that the data set group of the first plurality of data set groups does not satisfy the privacy requirement, merging the first plurality of data set groups together to obtain the data set and outputting the data set;

in response to determining that the data set group of the first plurality of data set groups does satisfy the privacy requirement, recursively splitting the data set group of the first plurality of data set groups into a second plurality of data set groups, and determining if the second plurality of data set groups satisfies the privacy requirement.