US 10,242,223 B2Granted

Access controlled graph query spanning

AssigneeMicrosoft Technology Licensing, LLC

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

Life of this patent

Estimating the term…

patentgrep

Loading patent…

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.

Claims20

Dependent claims

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.

6 more elements

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.

4 more elements

A method for controlling access to nodes in a relational graph at query time, comprising:

associating a node with an entity, wherein the node represents the entity in the relational graph;
identifying security contexts for the entity that control access to the entity;
storing the security contexts that deny access to the entity in a deny list in the node;
storing the security contexts that grant access to the entity in a permit list in the node;
in response to receiving a request to access the node that includes a plurality of security contexts associated with a subject from which the graph query was received, determining whether the deny list includes one security context of the plurality of security contexts;
in response to determining that the deny list does not include any security contexts of the plurality of security contexts, determining whether the permit list includes one security context of the plurality of security contexts;
in response to determining that the permit list includes one security context of the plurality of security contexts, granting access to the node;
in response to determining that the deny list includes the subject security context or to determining that the permit list does not include the subject security context, denying access to the node;
observing a frequency at which given security contexts grant or deny access to the nodes in the relational graph;
and
sorting the deny list and the permit list based on the frequency.

8 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/444,314Filed 27 Feb 2017
Published: US 2018/0247073 A130 Aug 2018
Granted: 26 Mar 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification9 codes

G06F 21/6227
To a system of files or objects, e.g. local or distributed file system or database: where protection concerns the structure of data, e.g. records,…
G06F 16/9024
Indexing; Data structures therefor; Storage structures: graphs; Linked lists
G06F 16/9535
Querying, e.g. by the use of web search engines: search customisation based on user profiles and personalisation
G06F 21/62
Protecting data: protecting access to data via a platform, e.g. using keys or access control rules