SYSTEM AND METHOD FOR EVALUATING A REVERSE QUERY

• US 20170244711A1
• Filed: 05/08/2017
• Published: 08/24/2017
• Est. Priority Date: 12/30/2010
• Status: Active Grant

• Current Assignee: Axiomatics AB
• Original Assignee: Axiomatics AB
• Inventors: RISSANEN, Erik, GIAMBIAGI, Pablo
• Granted Patent: US 10,158,641 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 2221/2141 Access rights, e.g. capability lists, access control lists, access tables, access matrices
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources

Abstract

Real-time techniques for determining all access requests to an attribute-based access control policy which evaluate to a given decision, “permit” or “deny”. The policy is enforced to control access to one or more resources in a computer network. In one embodiment, a method includes: (i) receiving a reverse query and a set of admissible access requests, each of which includes one or more attributes in the policy and values of these; (ii) extracting attributes to which all access requests in the set assign identical values; (iii) reducing the ABAC policy by substituting values for the extracted attributes; (iv) caching the policy as a simplified policy; (v) translating the simplified policy and the given decision into a satisfiable logic proposition; (vi) deriving all solutions satisfying the proposition; and (vi) extracting, based on the solutions, all access requests from the set for which the policy yields the given decision.

Claims

1-18. -18. (canceled)

19. A computer-implemented method for real-time evaluation of a reverse query to an attribute-based access control (ABAC) policy (P) which is enforced to control access to one or more resources in a computer network, said method comprising the steps of:

i) receiving a reverse query indicating a given access decision (d), which is one of permit access and deny access, and a subset (R) of access requests which is defined by constraints over the set of possible access requests;

ii) constructing a partial request (r_partial) from the subset (R) of access requests;

iii) reducing the ABAC policy in accordance with the partial request;

iv) caching the ABAC policy after said reducing, as a simplified policy (P′

);

v) translating the cached simplified policy (P′

) and the given decision (d) into a satisfiable logic proposition in Boolean variables (v_i, i=1, 2, . . . ), including replacing, by a Boolean variable, any Boolean expression in the policy representing a comparison of an attribute and a fixed value, or into a representation of the satisfiable logic proposition; and

vi) deriving all variable assignments (c_j=[v₁=x_j1, v₂=x_j2, . . . ], j=1, 2, . . . ) satisfying the logic proposition.

20. The method of claim 19, wherein the ABAC policy (P) comprises functional expressions dependent on attributes, wherein the ABAC policy is evaluable for an access request if the access request assigns a value to at least one of the attributes.

21. The method of claim 19, further comprising:

vii) processing the variable assignments satisfying the logic proposition on the basis of a correlation between each Boolean variable and the comparison which it replaces; and

viii) controlling access to the one or more resources in the computer network based on the access decision resulting from the evaluation of the ABAC policy.

22. The method of claim 19, wherein step ii includes examining the subset (R) of access requests in order to determine:

a first set (D) of attributes that are associated with exactly the same set of values in all requests of the subset (R);

a second set (A) of attributes that are absent in all requests of the subset (R); and

a third set (U) of all other attributes not included in any of the first set (D) of attributes and the second set (A) of attributes.

23. The method of claim 22, wherein step iii includes using the sets (D, A, U) of attributes to generate a partial access request, which:

assigns, to each attribute in the first set (D) of attributes, the exact set of values associated to it by any request in the subset (R); and

leaves all attributes in the third set (U) undefined.

24. The method of claim 23, wherein the partial access request further (V) marks all attributes in the second set (A) as not present.

25. The method of claim 19, wherein step iv includes caching the simplified policy (P′

) represented with a tree structure,

wherein step v includes, whenever a sub-tree in the tree structure represents a Boolean expression but at least one of its children evaluates to a non-Boolean value, replacing the whole sub-tree by a variable (v_i).

26. The method of claim 25, wherein, in step v, the variable replacing the sub-tree comprises two associated Boolean variables for representing more than two possible values of the sub-tree.

27. The method of claim 26, the possible values being “

true”

, “

false” and

“

indeterminate”

.

28. The method of claim 19, wherein step v includes storing the correlation between each variable (v_i) and the sub-tree which it replaces.

29. The method of claim 19, wherein step vii includes assessing, for each request (r) in the subset (R) of requests, whether it corresponds to any of the variable assignments satisfying the logic expression;

and, if it does, extracting this access request.

30. The method of claim 19, wherein step vi is performed by means of a SAT solver implemented in hardware and/or a computer executing software.

31. The method of claim 19,

wherein step v further includes representing at least part of the simplified policy (P′

) as a binary decision diagram; and

wherein step vi includes deriving all paths in the binary decision diagram evaluating to either true or false.

32. The method of claim 19, wherein step iii includes:

determining an implicit reference defined by a value of one of the extracted attributes together with the ABAC policy; and

fetching, in accordance with this implicit reference, at least one attribute value from a remote source.

33. A non-transitory computer-readable storage medium storing computer-executable instructions for performing a method of claim 19.

34. A computer system configured for real-time evaluation of a reverse query to an attribute-based access control (ABAC) policy which is enforced to control access to one or more resources in a computer network,

wherein the reverse query indicates a given access decision (d), which is one of permit access and deny access, and a subset (R) of access requests which is defined by constraints over the set of possible access requests, the computer system comprising:

a data memory operable to store one or more ABAC policies;

a partial request generation means operable to construct a partial request (r_partial) from the subset (R) of access requests;

a policy decision partial evaluation means connected to the partial request generation means and to the data memory, and operable to reduce the ABAC policy (P) in accordance with the partial request (r_partial), thereby yielding a simplified policy (P′

);

a translation means, connected to the policy decision means and operable to translate the simplified policy (P′

), and the given decision (d) into a satisfiable logic proposition (F) in Boolean variables (vi, i=1, 2, . . . ), wherein the translation means is configured to replace, by a Boolean variable, any Boolean expression in the policy representing a comparison of an attribute and a fixed value or into a representation of the satisfiable logic proposition;

an analyzing means, connected to the translation means and operable to derive all variable assignment (c_j=[v₁=x_j1, v₂=x_j2, . . . ], j=1, 2, . . . ) satisfying the logic proposition.

35. The method of claim 34, wherein the ABAC policy (P) comprises functional expressions dependent on attributes, wherein the ABAC policy is evaluable for an access request if the access request assigns a value to at least one of the attributes.

36. The system of claim 34, further comprising:

a conversion means connected to the analyzing means, and operable to process the sequence ([c₁, . . . , c_k]) of conditions satisfying the logic proposition on the basis of a correlation between each Boolean variable and the comparison which it replaces; and

a controller controlling access to the one or more resources in the computer network based on the access decision resulting from the evaluation of the ABAC policy.