# US 2019/0171840 A1 · Access controlled graph query spanning

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0171840 A1
- Document ID: US20190171840A1
- Status: Published application
- Kind: A1
- Application number: 16/268,783
- Filed: 2019-02-06
- Published: 2019-06-06
- Earliest claimed: 2017-02-27
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Tor KREUTZER; Steffen VIKEN VALVAG; Dag Steinnes EIDESEN; Amund Kronen JOHANSEN; Peter Dahle HEEN; Jan-Ove Almli KARLBERG; Jon MELING; Age KVALNES
- Web page: https://patentgrep.com/patent/US20190171840A1

## CPC

- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 21/62: Protecting access to data via a platform, e.g. using keys or access control rules
- G06F 21/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}
- H04L 63/10: {for controlling access to devices or network resources}
- H04L 63/101: {Access control lists [ACL]}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim at position 1

-20. (canceled)

### Claim 21

A method for controlling access to one or more nodes in a relational graph, comprising:
receiving a graph query including a subject security context;
determining whether a node in the relational graph denies access to the node, the determining including determining at least one of (a) whether a deny Approximate Membership Query (AMQ) filter denies access to the node, or (b) whether a query deny list denies access to the node; and
denying access to the node if it is determined that the node denies the access.

### Claim 22 (depends on 21)

The method of claim 21, further comprising permitting access to the node if it is determined that the node does not deny the access.

### Claim 23 (depends on 21)

The method of claim 21, further comprising:
determining whether the node in the relational graph permits access to the node, the determining including determining at least one of (a) whether a permit Approximate Membership Query (AMQ) filter permits access to the node, or (b) whether a query permit list permits access to the node; and
permitting access to the node if it is determined that node permits the access.

### Claim 24 (depends on 23)

The method of claim 23, further comprising denying access to the node if it is determined that the node does not permit the access.

### Claim 25 (depends on 21)

The method of claim 21, wherein determining whether the deny Approximate Membership Query (AMQ) filter denies access to the node includes querying the deny Approximate Membership Query (AMQ) filter with the subject security context, the deny AMQ filter including security contexts that deny access to the node as denying members.

### Claim 26 (depends on 21)

The method of claim 21, wherein determining whether the query deny list denies access to the node includes querying the deny list with the subject security context, the deny list including security contexts that deny access to the node.

### Claim 27 (depends on 23)

The method of claim 23, whether determining whether the permit Approximate Membership Query (AMQ) filter permits access to the node includes querying the permit AMQ filter with the subject security context, the permit AMQ filter including security contexts that grant access to the node as permitting members.

### Claim 28 (depends on 23)

The method of claim 23, wherein determining whether the query permit list permits access to the node includes querying the permit list with the subject security context, the permit list including security contexts that grant access to the node.

### Claim 29

A method for controlling access to nodes in a relational graph, comprising:
identifying frequencies at which security contexts are used to grant or deny access to the nodes in the relational graph;
sorting permit lists and deny lists based on the identified frequencies;
receiving a graph query on the relational graph;
obtaining one or more security contexts for a subject; and
ordering the security contexts for the subject, based on the identified frequencies.

### Claim 30 (depends on 29)

The method of claim 29, wherein the frequencies are identified via one of a count-min sketch or a counting Bloom filter.

### Claim 31 (depends on 29)

The method of claim 29, wherein the frequencies are identified on a periodic basis or in response to a user command.

### Claim 32 (depends on 29)

The method of claim 29, wherein in the sorting, more frequently observed security contexts are placed ahead of less frequently observed security contexts.

### Claim 33 (depends on 29)

The method of claim 29, wherein the graph query includes at least one security context for the subject, and the obtaining is based on the at least one security context for the subject.

### Claim 34 (depends on 29)

The method of claim 29, wherein the ordering sets a query order by which security contexts are tested against at least one of an Approximate Membership Query (AMQ) filter or a list.

### Claim 35

A system for controlling access to one or more nodes in a relational graph, comprising:
a memory storing a program; and
a computer processor operating under control of the program to:
receive a graph query including a subject security context,
determine whether a node in the relational graph denies access to the node, by determining at least one of (a) whether a deny Approximate Membership Query (AMQ) filter denies access to the node, or (b) whether a query deny list denies access to the node, and
deny access to the node if it is determined that the node denies the access.

### Claim 36 (depends on 35)

The system of claim 35, further comprising:
a user interface coupled to the computer processor, the user interface providing user-input commands to the computer processor for controlling the computer processor.

### Claim 37 (depends on 35)

The system of claim 35, wherein the computer processor also is controllable by the program to permit access to the node if it is determined that the node does not deny the access.

### Claim 38 (depends on 35)

The system of claim 35, wherein the computer processor also is controllable by the program to determine whether the node in the relational graph permits access to the node, by determining at least one of (a) whether a permit Approximate Membership Query (AMQ) filter permits access to the node, or (b) whether a query permit list permits access to the node.

### Claim 39 (depends on 38)

The system of claim 38, wherein the computer processor also operates under control of the program to deny access to the node if it is determined that the node does not permit the access.

### Claim 40 (depends on 35)

The system of claim 35, wherein, in determining whether the deny Approximate Membership Query (AMQ) filter denies access to the node, the computer processor operates under control of the program to query the deny Approximate Membership Query (AMQ) filter with the subject security context, the deny AMQ filter including security contexts that deny access to the node as denying members.