# US 2024/0179188 A1 · Authorization policy analysis

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

- Number: US 2024/0179188 A1
- Document ID: US20240179188A1
- Status: Published application
- Kind: A1
- Application number: 18/070,371
- Filed: 2022-11-28
- Published: 2024-05-30
- Earliest claimed: 2022-11-28
- Assignees: Amazon Technologies, Inc.
- Applicants: Amazon Technologies, Inc.
- Inventors: Emina TORLAK; Kyle HEADLEY; Michael W. HICKS; Neha RUNGTA; Andrew Marshall WELLS
- Web page: https://patentgrep.com/patent/US20240179188A1

## CPC

- H04L 63/205: {involving negotiation or determination of the one or more network security mechanisms to be used, e.g. by negotiation between the client and the server or between peers or by selection according to the capabilities of the entities involved (negotiation of communication capabilities H04L69/24)}
- H04L 63/104: {Grouping of entities}
- H04L 63/20: {for managing network security; network security policies in general (filtering policies H04L63/0227)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A system and method for authorization policy analysis. A policy analyzer answers first-order questions about authorization policies by reducing the policies to Satisfiability modulo theories (SMT). Input to the analyzer includes a policy to be analyzed and a schema for that policy. If the policy passes strict validation against the schema, then the analyzer symbolically evaluates the policy to encode its semantics as an SMT expression. The SMT expression is used for formulate a desired query about policy behavior such as, for example, if there is any input on which two policies both evaluate to true. The reduction to SMT produces a quantifier-free formula in a combination of decidable theories to support large scale deployments. This reduction is achieved by focusing the analysis on policies that pass strict validation, rather than attempting to analyze arbitrary policies.

## Claims

### Claim 1

A method performed by one or more electronic devices in a provider network, the method comprising:
encoding a set of terms from an authorization policy, wherein the authorization policy comprises:
(a) an effect;
(b) an authorization policy head that selects principals, actions, or resources to which the authorization policy applies;
(c) one or more optional conditional clauses that further refine the circumstances under which the authorization policy applies; and
(d) at least one expression in terms of one or more entities in the entity hierarchy;
inputting a Satisfiability Modulo Theories (SMT) formula to SMT solver, the SMT formula translated from the encoding of the authorization policy and from optional concrete constraints on the form of an entity hierarchy;
receiving an output from the SMT solver indicating whether the SMT formula is satisfiable or unsatisfiable;
determining, based on the output from the SMT solver indicating whether the SMT formula is satisfiable or unsatisfiable, an answer to a first-order question about a behavior of the authorization policy; and
causing display of information indicating the answer.

### Claim 2 (depends on 1)

The method of claim 1, wherein encoding the set of terms from the authorization policy to yield the encoding of the authorization policy is further based on:
validating the authorization policy as strictly typed based on an authorization policy schema.

### Claim 3 (depends on 1)

The method of claim 1, wherein the authorization policy governs access to resources of a provider network application implemented using the provider network.

### Claim 4

A method performed by one or more electronic devices, the method comprising:
encoding a set of terms from an authorization policy to yield an encoding of the authorization policy, wherein the authorization policy comprises:
(a) an effect;
(b) an authorization policy head that selects principals, actions, or resources to which the authorization policy applies; and
(c) one or more optional conditional clauses that further refine the circumstances under which the authorization policy applies;
inputting a Satisfiability Modulo Theories (SMT) formula to SMT solver, the SMT formula translated from the encoding of the authorization policy;
receiving an output from the SMT solver indicating whether the SMT formula is satisfiable or unsatisfiable;
determining, based on the output from the SMT solver indicating whether the SMT formula is satisfiable or unsatisfiable, an answer to a first-order question about a behavior of the authorization policy; and
causing display of information indicating the answer.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
using optional concrete constraints on the form of an entity hierarchy to generate the SMT formula
wherein the authorization policy further comprises at least one expression in terms of one or more entities in the entity hierarchy.

### Claim 6 (depends on 4)

The method of claim 4, wherein encoding the set of terms from the authorization policy to yield the encoding of the authorization policy is further based on:
validating the authorization policy as strictly typed based on an authorization policy schema.

### Claim 7 (depends on 4)

The method of claim 4, further comprising:
generating a symbolic authorization request based on an authorization request schema of an authorization policy schema;
generating a symbolic entity store based on an entity schema of the authorization policy schema;
wherein the authorization request schema specifies a set of entity types of a respective set of variables that comprise an authorization request that conforms to the authorization request schema; and
wherein the entity schema specifies a set of nominal entity types, a set of attribute record types of the set of nominal entity types, and a set of allowed ancestor entity types of the set of nominal entity types that comprise an entity hierarchy that conforms to the entity schema.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
generating the symbolic authorization request based on the authorization request schema and further based on assigning:
(a) the set of entity types of the respective set of variables that comprise an authorization request that conforms to the authorization request schema to
(b) a set of symbolic variables;
wherein each symbolic variable of the set of symbolic variables represents an arbitrary value of a respective assigned entity type.

### Claim 9 (depends on 7)

The method of claim 7, further comprising:
generating the symbolic entity store based on the entity schema and further based on generating a set of symbolic functions based on the entity schema;
wherein each symbolic function of the set of symbolic functions either:
(a) maps arbitrary entities of a respective entity type to arbitrary attribute records of an attribute record type of the respective entity type, or
(b) maps arbitrary entities of a respective entity type to arbitrary entities of one or more allowed ancestor entity types of the respective entity type.

### Claim 10 (depends on 4)

The method of claim 4, wherein encoding the set of terms from the authorization policy to yield the encoding of the authorization policy is further based on:
encoding an initial set of terms from the authorization policy based on an authorization policy schema;
collecting a set of one or more sub-expressions of the authorization policy, the set of one or more sub-expressions comprising a set of entity literals and entity-valued attribute accesses;
generating a set of one or more assumption terms corresponding to one or more terns, of the initial set of terms, that encode the authorization policy; and
combining the initial set of terms and the set of one or more assumption terms in the set of terms that encode the authorization policy.

### Claim 11 (depends on 10)

The method of claim 10, wherein generating the set of one or more assumption terms is based on generating an assumption term that constrains an ancestor relation to be irreflexive on a term.

### Claim 12 (depends on 10)

The method of claim 10, wherein generating the set of one or more assumption terms is based on generating an assumption term that requires an ancestor relation to be transitive and antisymmetric on a pair of terms.

### Claim 13 (depends on 4)

The method of claim 4, further comprising:
obtaining an authorization policy schema and the authorization policy via a command line interface, a graphical user interface, or a software development kit.

### Claim 14 (depends on 4)

The method of claim 4, further comprising:
receiving the output from the SMT solver indicating that the SMT formula is satisfiable;
wherein the output of the SMT solver comprises a witness; and
causing display of information indicating the witness.

### Claim 15 (depends on 4)

The method of claim 4, wherein an authorization policy schema and the authorization policy are defined for a provider network application implemented using the provider network.

### Claim 16

A system comprising:
a first set of one or more electronic devices to implement an authorization policy analysis service in a provider network, the authorization policy analysis service comprising instructions which when executed cause the authorization policy analysis service to perform:
receiving an authorization policy;
encoding a set of terms from the authorization policy, wherein the authorization policy comprises:
(a) an effect;
(b) an authorization policy head that selects principals, actions, or resources to which the authorization policy applies; and
(c) one or more optional conditional clauses that further refine the circumstances under which the authorization policy applies;
inputting a Satisfiability Modulo Theories (SMT) formula to SMT solver, the SMT formula translated from the encoding of the authorization policy, and optionally, concrete constraints on the form of the entity hierarchy and query context over which the policy operates; and
receiving an output from the SMT solver indicating whether the SMT formula is satisfiable or unsatisfiable;
determining, based on the output from the SMT solver indicating whether the SMT formula is satisfiable or unsatisfiable, an answer to a first-order question about a behavior of the authorization policy; and
causing display of information indicating the answer;
a second set of one or more electronic devices to implement an authorization policy analysis service in a provider network, the authorization policy analysis service comprising instructions which when executed cause the authorization policy analysis service to perform:
storing the authorization policy; and
sending the authorization policy to the authorization policy analysis service.

### Claim 17 (depends on 16)

The system of claim 16, wherein encoding the set of terms from the authorization policy is further based on:
validating the authorization policy as strictly typed based on an authorization policy schema.

### Claim 18 (depends on 16)

The system of claim 16, the authorization policy analysis service further comprising instructions which when executed cause the authorization policy analysis service to perform:
generating a symbolic authorization request based on an authorization request schema of an authorization policy schema;
generating a symbolic entity store based on an entity schema of the authorization policy schema;
wherein the authorization request schema specifies a set of entity types of a respective set of variables that comprise an authorization request that conforms to the authorization request schema;
wherein the entity schema specifies a set of nominal entity types, a set of attribute record types of the set of nominal entity types, and a set of allowed ancestor entity types of the set of nominal entity types that comprise an entity hierarchy that conforms to the entity schema; and
obtaining an authorization policy schema and the authorization policy via a command line interface, a graphical user interface, or a software development kit.

### Claim 19 (depends on 16)

The system of claim 16, the authorization policy analysis service further comprising instructions which when executed cause the authorization policy analysis service to perform:
receiving the output from the SMT solver indicating that the SMT formula is satisfiable;
wherein the output of the SMT solver comprises a witness; and
causing display of information indicating the witness.

### Claim 20 (depends on 16)

The system of claim 16, wherein the authorization policy governs access to resources of a provider network application implemented using the provider network.
