CONCEALING SENSITIVE PATTERNS FROM LINKED DATA GRAPHS

• US 20150186653A1
• Filed: 12/30/2013
• Published: 07/02/2015
• Est. Priority Date: 12/30/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kotoulas, Spyros, Sbodio, Marco Luca, Gkoulalas-Divanis, Aris, Lopez Garcia, Vanessa
• Granted Patent: US 9,268,950 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 21/60 Protecting data

Abstract

A method, system and computer program product for preventing sensitive pattern disclosures from Linked Data graphs. The proposed method (i) receives as input a Linked Data graph and a set of query patterns that correspond to sensitive knowledge that needs to be concealed, and (b) minimally distorts the Linked Data graph to generate a sanitized counterpart (graph) in which only the non-sensitive patterns can be discovered. The method supports a variety of utility functions, which it optimizes during the graph sanitization process. The resulting, sanitized graph can be subsequently used for publishing and/or querying purposes.

Claims

1. A method to conceal sensitive patterns from Linked Data Graphs comprising:

receiving at a hardware processor, data representing a Linked Data graph form (data graph G) and a set of patterns S to be concealed in said data graph G;

identifying one or more bindings in graph G which lead to the discovery of the patterns S; and

removing each of the one or more bindings in the data graph G to form a new data graph G′

such that the patterns discoverable in G, cannot be discovered in graph G′

said hardware processor configured to perform said identifying and binding breaking in said data graph.

2. The method of claim 1, wherein said one or more bindings are removed in a manner to optimize a given utility function.

3. The method of claim 2, further comprising:

de-referencing (Uniform Resource Indicators) URIs in the Linked Data graph G;

computing inferences from the de-referenced Linked Data graph G structure;

extracting said patterns from said Linked Data graph G based on said computed inferences; and

computing for each pattern in a set S its bindings in the Linked Data graph G; and

removing each computed binding by suppressing one or more of;

nodes/links between nodes from the graph G based on said given utility function.

4. The method of claim 3, further comprising:

iteratively repeating said de-referencing, inferences computing and said node/link suppressing until all the patterns in said set S are non-discoverable in said new Linked Data graph G′

.

5. The method of claim 3, wherein said de-referencing URIs in the Linked Data graph G and computing inferences are repeated for up to r times.

6. The method of claim 1, wherein said patterns are based upon one of:

a priori knowledge of a user and data mining for patterns in graph G as specified by a user.

7. The method of claim 2, wherein said patterns are represented as queries whose answers yield the patterns, one or more said queries representing patterns not to be concealed in said graph being answerable in said new Linked Data graph G′

with a maximal utility based on the utility function.

8. A system for concealing sensitive patterns from Linked Data Graphs comprising:

a memory storage device;

a hardware processor programmed with instructions from said memory storage device to configure said hardware processor to;

receive data representing a Linked Data graph form (data graph G);

receive data representing a set of patterns to be concealed in said data graph G;

identify one or more bindings in data graph G which lead to the discovery of the patterns; and

remove each of the one or more bindings in the data graph G to form a new data graph G′

such that said patterns discoverable in G, cannot be discovered in graph G′

.

9. The system of claim 8, wherein said hardware processor is further configured to:

remove the bindings in a manner to optimize a given utility function.

10. The system of claim 9, wherein said hardware processor is further configured to:

de-reference (Uniform Resource Indicators) URIs in the Linked Data graph G;

compute inferences from the de-referenced Linked Data graph G structure;

extract said patterns from said Linked Data graph G based on said computed inferences;

compute for each pattern in a set S its bindings in the Linked Data graph G; and

remove each computed binding by suppressing one or more of;

nodes/links, from the graph based on said given utility function.

11. The system of claim 10, wherein the URI de-referencing, inferences computing and said node/link suppressing are iteratively repeated until all the patterns in set S are non-discoverable in said new Linked Data graph G′

.

12. The system of claim 11, wherein said de-referencing URIs in the Linked Data graph G and computing inferences are repeated for up to r times.

13. The system of claim 8, wherein said patterns are based upon one of:

a priori knowledge of a user and data mining for patterns in graph G as specified by a user.

14. The system of claim 8, wherein said patterns are represented as queries whose answers yield the patterns, one or more said queries representing patterns not to be concealed in said graph being answerable in said new Linked Data graph G′

, with a maximal utility based on the given utility function.

15. A computer program product to conceal sensitive patterns from Linked Data Graphs comprising:

a storage medium, wherein said storage medium is not a propagating signal, said storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising;

receiving data representing a Linked Data graph form (data graph G);

receiving data representing a set of patterns to be concealed in said data graph G, identifying one or more bindings in data graph G which lead to the discovery of the patterns; and

removing each of the one or more bindings in the said data graph G to form a new data graph G′

such that said sensitive patterns discoverable in G, cannot be discovered in graph G′

.

16. The computer program product of claim 15, wherein the one or more bindings are removed in a manner to optimize a given utility function.

17. The computer program product of claim 16, wherein said method further comprises:

de-referencing (Uniform Resource Indicators) URIs in the Linked Data graph G;

computing inferences from the de-referenced Linked Data graph G structure;

extracting said patterns from said Linked Data graph G based on said computed inferences;

computing for each pattern in a set S its bindings in the Linked Data graph G; and

removing each computed binding by suppressing one or more of;

nodes/links, from the graph based on said utility function.

18. The computer program product of claim 17, further comprising:

iteratively repeating said de-referencing, inferences computing and said node/link suppressing until all the patterns in said set S are non-discoverable in said new Linked Data graph G′

.

19. The computer program product of claim 17, wherein said de-referencing URIs in the Linked Data graph G and computing inferences are repeated for up to r times.

20. The computer program product of claim 15, wherein said patterns are represented as queries whose answers yield the patterns, one or more said queries representing patterns not to be concealed in said graph of queries being answerable in said new Linked Data graph G′

with a maximal utility based on the given utility function.