Differentially private database permissions system

• US 10,430,605 B1
• Filed: 11/29/2018
• Issued: 10/01/2019
• Est. Priority Date: 11/29/2018
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: LeapYear Technologies, Inc. (Snowflake Inc)
• Inventors: Nerurkar, Ishaan, Hockenbrocht, Christopher, Spies, David
• Primary Examiner(s): King, John B
• Application Number:
  US16/205,034
• Time in Patent Office: 306 Days
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 2221/2113 Multi-level security, e.g. mandatory access control
• CPC Class Codes: G06F 2221/2141 Access rights, e.g. capability lists, access control lists, access tables, access matrices
• CPC Class Codes: G06F 2221/2145 Inheriting rights or properties, e.g., propagation of permissions or restrictions within a hierarchy
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

A differentially private system receives a request from a client to perform a query on data stored in a database. The differentially private system establishes a set of permissions of the client with respect to the data in the database. The differentially private system deconstructs the query into query components. The query components include at least one relation that identifies a dataset in the database and at least one expressions specifying an operation to be performed in the identified dataset. The differentially private system identifies permissions necessary to perform the specified operation on the identified dataset. The differentially private system determines whether the established permissions grants of the client include the identified permissions necessary to perform the specified operation on the identified dataset. The differentially private system selectively executes the query responsive to the determination.

Claims

1. A method of providing differentially private database security, comprising:

receiving a request from a client to perform a query on data stored in a database;

establishing a set of permissions granted to the client with respect to the data in the database, wherein the set of permissions comprises a private compute permission granting permission to perform differentially private operations on specified data in the database;

deconstructing the query into query components, wherein the query components comprise at least one relation identifying a dataset in the database and at least one expression specifying an operation to be performed in the identified dataset;

identifying permissions necessary to perform the specified operation on the identified dataset, wherein the identified permissions comprise the private compute permission and the identified dataset comprises the specified data;

determining whether the established set of permissions granted to the client includes the identified permissions necessary to perform the specified operation on the identified dataset using a set of mutually recursive functions to check whether the established set of permissions granted to the client includes the identified permissions necessary to perform expressions on relations indicated by the deconstructed query components; and

selectively executing the query responsive to the determination.

2. The method of claim 1, wherein establishing the set of permissions of the client with respect to the database comprises:

accessing a data store storing data describing a discrete set of permissions granted to the client, the discrete set of permissions including explicit permissions granted to the client and implicit permissions granted to the client responsive to the explicit permissions, the data store further storing data indicating whether each permission in the discrete set of permissions is explicitly or implicitly granted to the client;

wherein determining whether the established set of permissions grants of the client include the identified permissions necessary to perform the specified operation comprises determining whether the discrete set of permissions includes the identified permissions.

3. The method of claim 2, further comprising:

receiving an instruction explicitly granting a permission to the client;

determining a set of implicit permissions implicitly granted to the client responsive to the explicitly-granted permission; and

modifying data in the data store to indicate that the explicitly-granted permission is explicitly granted to the client and the set of implicit permission are implicitly granted to the client.

4. The method of claim 2, further comprising:

receiving an instruction revoking an explicitly granted permission from the client;

revoking a set of implicit permissions implicitly granted to the client responsive to the explicitly-granted permission; and

modifying data in the data store to indicate revocation of the explicitly-granted permission and revocation of the set of implicit permissions.

5. The method of claim 1, wherein selectively executing the query responsive to the determination comprises:

blocking the query responsive to determining that the established set of permissions does not grant the client the identified permissions necessary to perform the specified operation on the specified query; and

allowing the query responsive to determining that the established set of permissions does grant the client the identified permissions necessary to perform the specified operation on the specified query.

6. The method of claim 1, wherein the relation identifies a pair of columns in the database and the expression specifies a compare operation comparing a value in a first column of the pair to a value in a second column of the pair, and wherein determining whether the established set of permissions grants of the client include the identified permissions necessary to perform the specified operation on the identified dataset comprises:

identifying a first set of obfuscation keys associated with the first column and a second set of obfuscation keys associated with a second column of the pair;

determining whether the first set of obfuscation keys and the second set of obfuscation keys have an obfuscation key in common; and

determining that the established set of permissions grants of the client are the identified permissions necessary to perform the specified operation responsive to determining that the first set of obfuscation keys and the second set of obfuscation keys have an obfuscation key in common.

7. The method of claim 1, wherein the determining comprises determining that the established set of permissions granted to the client includes the identified permissions necessary to perform the specified operation on the identified dataset and the selectively executing comprises executing a differentially private operation upon the specified data.

8. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations, the operations comprising:

receiving a request from a client to perform a query on data stored in a database;

establishing a set of permissions granted to the client with respect to the data in the database, wherein the set of permissions comprises a private compute permission granting permission to perform differentially private operations on specified data in the database;

deconstructing the query into query components, wherein the query components comprise at least one relation identifying a dataset in the database and at least one expression specifying an operation to be performed in the identified dataset;

identifying permissions necessary to perform the specified operation on the identified dataset, wherein the identified permissions comprise the private compute permission and the identified dataset comprises the specified data;

determining whether the established set of permissions granted to the client includes the identified permissions necessary to perform the specified operation on the identified dataset using a set of mutually recursive functions to check whether the established set of permissions granted to the client includes the identified permissions necessary to perform expressions on relations indicated by the deconstructed query components; and

selectively executing the query responsive to the determination.

9. The non-transitory computer-readable storage medium of claim 8, wherein establishing the set of permissions of the client with respect to the database comprises:

accessing a data store storing data describing a discrete set of permissions granted to the client, the discrete set of permissions including explicit permissions granted to the client and implicit permissions granted to the client responsive to the explicit permissions, the data store further storing data indicating whether each permission in the discrete set of permissions is explicitly or implicitly granted to the client;

wherein determining whether the established set of permissions grants of the client include the identified permissions necessary to perform the specified operation comprises determining whether the discrete set of permissions includes the identified permissions.

10. The non-transitory computer-readable storage medium of claim 9, the operations further comprising:

receiving an instruction explicitly granting a permission to the client;

determining a set of implicit permissions implicitly granted to the client responsive to the explicitly-granted permission; and

modifying data in the data store to indicate that the explicitly-granted permission is explicitly granted to the client and the set of implicit permission are implicitly granted to the client.

11. The non-transitory computer-readable storage medium of claim 9, the operations further comprising:

receiving an instruction revoking an explicitly granted permission from the client;

revoking a set of implicit permissions implicitly granted to the client responsive to the explicitly-granted permission; and

modifying data in the data store to indicate revocation of the explicitly-granted permission and revocation of the set of implicit permissions.

12. The non-transitory computer-readable storage medium of claim 8, wherein selectively executing the query responsive to the determination comprises:

blocking the query responsive to determining that the established set of permissions does not grant the client the identified permissions necessary to perform the specified operation on the specified query; and

allowing the query responsive to determining that the established set of permissions does grant the client the identified permissions necessary to perform the specified operation on the specified query.

13. The non-transitory computer-readable storage medium of claim 8, wherein the relation identifies a pair of columns in the database and the expression specifies a compare operation comparing a value in a first column of the pair to a value in a second column of the pair, and wherein determining whether the established set of permissions grants of the client include the identified permissions necessary to perform the specified operation on the identified dataset comprises:

identifying a first set of obfuscation keys associated with the first column and a second set of obfuscation keys associated with a second column of the pair;

determining whether the first set of obfuscation keys and the second set of obfuscation keys have an obfuscation key in common; and

determining that the established set of permissions grants of the client are the identified permissions necessary to perform the specified operation responsive to determining that the first set of obfuscation keys and the second set of obfuscation keys have an obfuscation key in common.

14. A system, comprising:

a processor for executing computer program instructions; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations, the operations comprising;

receiving a request from a client to perform a query on data stored in a database;

establishing a set of permissions granted to the client with respect to the data in the database, wherein the set of permissions comprises a private compute permission granting permission to perform differentially private operations on specified data in the database;

deconstructing the query into query components, wherein the query components comprise at least one relation identifying a dataset in the database and at least one expression specifying an operation to be performed in the identified dataset;

identifying permissions necessary to perform the specified operation on the identified dataset, wherein the identified permissions comprise the private compute permission and the identified dataset comprises the specified data;

determining whether the established set of permissions granted to the client include the identified permissions necessary to perform the specified operation on the identified dataset using a set of mutually recursive functions to check whether the established set of permissions granted to the client includes the identified permissions necessary to perform expressions on relations indicated by the deconstructed query components; and

selectively executing the query responsive to the determination.

15. The system of claim 14, wherein establishing the set of permissions of the client with respect to the database comprises:

accessing a data store storing data describing a discrete set of permissions granted to the client, the discrete set of permissions including explicit permissions granted to the client and implicit permissions granted to the client responsive to the explicit permissions, the data store further storing data indicating whether each permission in the discrete set of permissions is explicitly or implicitly granted to the client;

wherein determining whether the established set of permissions grants of the client include the identified permissions necessary to perform the specified operation comprises determining whether the discrete set of permissions includes the identified permissions.

16. The system of claim 15, the operations further comprising:

receiving an instruction explicitly granting a permission to the client;

determining a set of implicit permissions implicitly granted to the client responsive to the explicitly-granted permission; and

modifying data in the data store to indicate that the explicitly-granted permission is explicitly granted to the client and the set of implicit permission are implicitly granted to the client.

17. The system of claim 15, the operations further comprising:

receiving an instruction revoking an explicitly granted permission from the client;

revoking a set of implicit permissions implicitly granted to the client responsive to the explicitly-granted permission; and

modifying data in the data store to indicate revocation of the explicitly-granted permission and revocation of the set of implicit permissions.

18. The system of claim 14, wherein selectively executing the query responsive to the determination comprises:

blocking the query responsive to determining that the established set of permissions does not grant the client the identified permissions necessary to perform the specified operation on the specified query; and

allowing the query responsive to determining that the established set of permissions does grant the client the identified permissions necessary to perform the specified operation on the specified query.