Access controlled graph query spanning

Patent metadata

Field	Value
Publication number	US-10242223-B2
Application number	US-201715444314-A
Country	US
Kind code	B2
Filing date	Feb 27, 2017
Priority date	Feb 27, 2017
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

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 for controlling access to nodes in a relational graph at query time, comprising:
receiving a graph query from a subject, including a subject security context, to span the nodes of the relational graph;
in response to reaching an access controlled node as part of spanning the relational graph according to the graph query:
determining whether the access controlled node denies access to the subject based on the subject security context, including:
querying a deny Approximate Membership Query (AMQ) filter of the access controlled node with the subject security context, the deny AMQ filter including security contexts that deny access to the access controlled node as denying members;
in response to the deny AMQ filter indicating that the subject security context is not present in the denying members, determining whether the subject security context grants access to the access controlled node;
in response to the deny AMQ filter indicating that the subject security context is present in the denying members, querying a deny list of the access controlled node with the subject security context, the deny list including the security contexts that deny access to the access controlled node;
in response to the deny list indicating that the subject security context is not present, determining whether the subject security context grants access to the access controlled node; and
in response to the deny list indicating that the subject security context is present, denying access to the access controlled node while spanning the relational graph according to the graph query.

2. The method of claim 1 , wherein determining whether the subject security context grants access to the access controlled node further comprises:
querying a permit AMQ filter of the access controlled node with the subject security context, the permit AMQ filter including security contexts that grant access to the access controlled node as permitting members;
in response to the permit AMQ filter indicating that the subject security context is not present in the permitting members, denying access to the access controlled node while spanning the relational graph according to the graph query;
in response to the permit AMQ filter indicating that the subject security context is present in the permitting members, querying a permit list of the access controlled node with the subject security context, the permit list including the security contexts that grant access to the access controlled node;
in response to the permit list indicating that the subject security context is not present, denying access to the access controlled node while spanning the relational graph according to the graph query; and
in response to the permit list indicating that the subject security context is present, spanning the access controlled node as part of spanning the relational graph according to the graph query.

3. The method of claim 2 , wherein determining whether the subject security context grants access to the access controlled node further comprises:
prior to querying the permit AMQ filter, determining whether the access controlled node includes the permit AMQ filter;
in response to determining that the access controlled node includes the permit AMQ filter, querying the permit AMQ filter; and
in response to determining that the access controlled node does not include the permit AMQ filter, querying the permit list without querying the permit AMQ filter.

4. The method of claim 1 , wherein determining whether the subject security context denies access to the access controlled node further comprises:
prior to querying the deny AMQ filter, determining whether the access controlled node includes the deny AMQ filter;
in response to determining that the access controlled node includes the deny AMQ filter, querying the deny AMQ filter; and
in response to determining that the access controlled node does not include the deny AMQ filter, querying the deny list without querying the deny AMQ filter.

5. The method of claim 1 , wherein the subject security context includes a plurality of security contexts including:
personal security contexts, based on a user and user groups of the subject;
machine security contexts, based on a computing device and software settings of the subject; and
access point security contexts, based on a location and connection type of the subject.

6. The method of claim 5 , wherein an order in which the plurality of security contexts used in queries is based on an observed frequency at which individual security contexts grant and deny access to access controlled nodes in the relational graph.

7. The method of claim 1 , wherein determining whether the access controlled node denies access to the subject based on the subject security context further comprises converting the subject security context into a numeric representation according to a hashing algorithm.

8. A method for controlling access to nodes in a relational graph at query time, comprising:
observing determinations of whether to grant access to the nodes of the relational graph based on security contexts associated with the nodes;
identifying frequencies at which the security contexts are used to grant or deny access to the nodes;
receiving a graph query, from a subject, to span the relational graph, the graph query including a plurality of security contexts associated with the subject;
sorting the plurality of security contexts associated with the subject in the graph query into an order according to the identified frequencies;
executing the graph query on the relational graph; and
querying an access controlled node, during execution of the graph query, to determine whether the plurality of security contexts associated with the subject grant access to the access controlled node, wherein the access controlled node is queried with the plurality of security contexts associated with the subject according to the order.

9. The method of claim 8 , wherein identifying frequencies at which the security contexts are used to grant or deny access to the nodes further comprises:
identifying granting frequencies at which the security contexts grant access to the nodes;
identifying denying frequencies at which the security contexts deny access to the nodes;
sorting permitting security contexts included in permit lists associated with the nodes according to the frequencies at which the security contexts grant access; and
sorting denying security contexts included in deny lists associated with the nodes according to the frequencies at which the security contexts deny access.

10. The method of claim 8 , wherein querying an access controlled node further comprises:
querying a deny Approximate Membership Query (AMQ) filter, to determine whether at least one of the plurality of security contexts is a member of the deny AMQ filter;
in response to the deny AMQ filter indicating that at least one of the plurality of security contexts is a member of the deny AMQ filter, querying a deny list of denying security contexts associated with the access controlled node to determine whether to grant access to the access controlled node; and
in response to the deny list indicating that at least one of the plurality of security contexts is a member of the deny list, determining not to grant access to the access controlled node.

11. The method of claim 10 , further comprising:
in response to the deny AMQ filter indicating that not one of the plurality of security contexts is a member of the deny AMQ filter, querying a permit AMQ filter, to determine whether at least one of the plurality of security contexts is a member of the permit AMQ filter;
in response to the perm

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/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

• G06F21/62 Primary

  Protecting access to data via a platform, e.g. using keys or access control rules · 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

• H04L63/101

  Access control lists [ACL] · CPC title