Access controlled graph query spanning

Patent metadata

Field	Value
Publication number	US-11748506-B2
Application number	US-202217661636-A
Country	US
Kind code	B2
Filing date	May 2, 2022
Priority date	Feb 27, 2017
Publication date	Sep 5, 2023
Grant date	Sep 5, 2023

Abstract

Controlling access to nodes in a relational graph at query time by using an approximate membership query (AMQ) filter and ordered queries based on historic grants or denials of access according to security context enables a more efficient querying of the relational graph while preserving access controls. Security contexts that grant or deny access to a node are stored in an associated AMQ filter and are queried according to the subject's security context in an order based on the frequency at which the security contexts have previously granted or denied access to nodes in the relational graph.

First claim

We claim:

1. A method comprising:
receiving a graph query including a security context for accessing nodes in a relational graph, wherein the relational graph comprises a first node that is connected to a second node via an edge representing a relationship between the first node and the second node;
determining the first node representing the security context denies access to the second node in the relational graph by determining at least one of:
a deny filter denies access to the second node; or
a query deny list denies access to the second node; and

denying access to the second node.

2. The method of claim 1 , wherein the security context corresponds to a personal security context for a user, the personal security context indicating one or more security groups to which the user belongs.

3. The method of claim 1 , wherein the security context corresponds to a machine security context, the machine security context indicating a device or type of device.

4. The method of claim 1 , wherein the security context corresponds to an access security context, the access security context indicating a geographic location, a network, or network settings.

5. The method of claim 1 , wherein determining the first node denies access to the second node comprises:
querying an index structure for the relational graph to determine potential nodes from which to initiate the graph query.

6. The method of claim 1 , wherein a schema for the first node indicates that access to the second node is determined based on whether data in the security context corresponds to an entry in the deny filter or the query deny list.

7. The method of claim 1 , wherein the deny filter is an Approximate Member Query (AMQ) filter.

8. The method of claim 7 , wherein the AMQ filter provides a probabilistic response as to whether a given security context is included as a member in the AMQ filter.

9. The method of claim 8 , wherein members in the AMQ filter are prevented access to the second node.

10. The method of claim 1 , wherein the query deny list comprises a plurality of security contexts.

11. The method of claim 10 , wherein the plurality of security contexts are denied access to the second node.

12. A system comprising:
a processor; and
memory coupled to the processor, the memory comprising computer executable instructions that, when executed by the processor, perform operations comprising:
receiving a graph query including a security context for accessing nodes in a relational graph, wherein the relational graph comprises a first node that is connected to a second node via an edge representing a relationship between the first node and the second node;
determining the first node representing the security context denies access to the second node in the relational graph by determining at least one of:
a deny filter denies access to the second node; or
a query deny list denies access to the second node; and

denying access to the second node.

13. The system of claim 12 , wherein determining the first node denies access to the second node comprises:
querying the deny filter to determine whether the security context is a member of the deny filter; and
if it is determined that the security context is a member of the deny filter, querying the query deny list to determine whether the security context is a member of the query deny list.

14. The system of claim 13 , wherein determining the first node denies access to the second node further comprises:
if it is determined that the security context is not a member of the deny filter, determining whether the first node is associated with a permit filter for the second node.

15. The system of claim 14 , wherein:
in response to determining that the first node is associated with the permit filter for the second node, querying the permit filter to determine whether the security context is a member of the permit filter.

16. The system of claim 15 , wherein:
in response to determining that the security context is a member of the permit filter, denying access to the second node.

17. The system of claim 12 , wherein:
after denying access to the second node, the graph query continues to attempt to span the relational graph without accessing the second node.

18. The system of claim 12 , wherein the security context comprises at least two of:
a personal security context for a user;
a machine security context indicating; or
an access security context.

19. A device comprising:
memory comprising computer executable instructions that, when executed, perform operations comprising:
receiving a graph query including a security context for accessing nodes in a relational graph, wherein the relational graph comprises a first node that is connected to a second node via an edge representing a relationship between the first node and the second node;
determining the first node representing the security context denies access to the second node in the relational graph by determining at least one of:
a deny filter denies access to the second node; or
a query deny list denies access to the second node; and

denying access to the second node.

20. The device of claim 19 , wherein determining the first node denies access to the second node comprises:
accessing an index for the relational graph to determine nodes from which to initiate the graph query.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kreutzer Tor
• Viken Valvag Steffen
• Eidesen Dag Steinnes
• Johansen Amund Kronen
• Heen Peter Dahle
• Karlberg Jan-Ove Almli
• Meling Jon
• Kvalnes Age

Classifications

• G06F21/6227 Primary

  where protection concerns the structure of data, e.g. records, types, queries · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F21/62 Primary

  Protecting access to data via a platform, e.g. using keys or access control rules · CPC title

• G06F21/6209

  to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself · CPC title