Differentially private database permissions system

1. A method of providing database security, comprising:

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

establishing a set of permissions of the client with respect to the data in the database, wherein the set of permissions comprises a first permission at a first Position of a permissions hierarchy;

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 on the identified dataset;

identifying permissions necessary to perform the specified operation on the identified dataset using a set of mutually recursive functions, wherein the identified permissions comprise a second permission at a second position of the permissions hierarchy;

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 based on the positions of the first and second permissions in the permissions hierarchy; 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. 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 of the client with respect to the data in the database wherein the set of permissions comprises a first permission at a first position of a permissions hierarchy;

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 on the identified dataset;

identifying permissions necessary to perform the specified operation on the identified dataset using a set of mutually recursive functions, wherein the identified permissions comprise a second permission at a second position of the permissions hierarchy;

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 based on the positions of the first and second permissions in the permissions hierarchy; and

selectively executing the query responsive to the determination.

8. The non-transitory computer-readable storage medium of claim 7 , 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.

9. The non-transitory computer-readable storage medium of claim 8 , 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.

10. The non-transitory computer-readable storage medium of claim 8 , 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.

11. The non-transitory computer-readable storage medium of claim 7 , 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.

12. The non-transitory computer-readable storage medium of claim 7 , 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.

13. 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 of the client with respect to the data in the database wherein the set of permissions comprises a first permission at a first position of a permissions hierarchy;

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 on the identified dataset;

identifying permissions necessary to perform the specified operation on the identified dataset using a set of mutually recursive functions, wherein the identified permissions comprise a second permission at a second position of the permissions hierarchy;

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 based on the positions of the first and second permissions in the permissions hierarchy; and

selectively executing the query responsive to the determination.

14. The system of claim 13 , 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.

15. The system of claim 14 , 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.

16. The system of claim 14 , 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.

17. The system of claim 13 , 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.

18. The system of claim 13 , 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.