Abducing assertion to support access query

• US 8,010,560 B2
• Filed: 12/21/2007
• Issued: 08/30/2011
• Est. Priority Date: 12/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Becker, Moritz Y., Mackay, Jason F.
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Rahman; Mohammad N
• Application Number:
  US11/962,746
• Publication Number:
  US 20090164469A1
• Time in Patent Office: 1,348 Days
• Field of Search: 707 4- 9, 707/783
• US Class Current: 707/783
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6281 at program execution time, where the protection is within the operating system

Abstract

Logical abduction is used to derive the premises that support an access query. In a logic-based access-control system, a query, as to one or more principals'"'"' right to access one or more resources, is a statement that can be either true or false. The statement evaluates to true if the principal is allowed to access the resource under the existing set of assertions. Assertions that, if made, would cause the statement to be true can be abduced from the query and from the policy against which the truth of the query is to be judged. The abduced assertions can be used to assist in making the appropriate assertions to cause the query to evaluate to true so that access to the resource can be granted.

Claims

1. One or more computer-readable storage media comprising computer-executable instructions to perform a method of facilitating access to a resource, the method comprising:

creating a first answer set that comprises a first assertion, a first variable, and a first constraint that have been chosen, said first answer set satisfying one or more conditions comprising;

that a first set of assertions that comprises or is derived from said first answer set will, when presented to a guard that controls access to the resource, cause said guard to find that a query evaluates to true under a policy implemented by said guard;

creating a second answer set that comprises a second assertion, a second variable, and a second constraint that have been chosen, said second answer set satisfying one or more conditions comprising;

that a second set of assertions that comprises or is derived from said second answer set will, when presented to said guard, cause said guard to find that said query evaluates to true under said policy;

determining that said first answer set is not subsumed by said second answer set; and

providing a solution that comprises said first answer set.

2. The one or more computer-readable storage media of claim 1, wherein said first answer set comprises a first set of assumptions abduced from information that comprises said query, wherein said second answer set comprises a second set of assumptions abduced from said information, and wherein said determining comprises:

comparing a first cardinality of said first set of assumptions with a second cardinality of said second set of assumptions.

3. The one or more computer-readable storage media of claim 1, wherein said determining comprises:

determining whether there is a substitution under which;

a first literal that is derived from said first answer set,

is logically equivalent to

a second literal that is derived from said second answer set, with said second variable substituted according to said substitution.

4. The one or more computer-readable storage media of claim 1, wherein said first answer set comprises a third set of one or more abduced assertions that comprise said first assertion, wherein said second answer set comprises a fourth set of one or more abduced assertions that comprise said second assertion, wherein said third set involves a first collection of one or more variables that comprise said first variable, wherein said fourth set involves a second collection of one or more variables that comprise said second variable, and wherein said determining comprises:

determining whether there is a substitution under which;

said fourth set,

is a superset of, or the same set as

said third set, with said first collection of one or more variables substituted according to said substitution.

5. The one or more computer-readable storage media of claim 1, wherein said first answer set comprises a third set of one or more constraints that comprise said first constraint, wherein said second answer set comprises fourth set of one or more constraints that comprise said second constraint, wherein said third set involves a first collection of one or more variables that comprise said first variable, wherein said fourth set involves a second collection of one or more variables that comprise said second variable, and wherein said determining comprises:

determining whether there is a substitution under which;

set third set,

satisfies a constraint-subsumption condition with respect to

set fourth set, with said second collection of one or more variables substituted according to said substitution.

6. The one or more computer-readable storage media of claim 1, wherein said first answer set comprises a third set of one or more abduced assertions that comprise said first assertion, wherein said second answer set comprises a fourth set of one or more abduced assertions that comprise said second assertion, said fourth set of one or more abduced assertions involving a plurality of variables that comprise said second variable, and wherein said determining comprises:

dividing said fourth set into clusters of assertions based on which assertions in said fourth set have variables in common; and

for each one of the clusters, determining whether there is a substitution under which said one of the clusters and said third set are both true.

7. The one or more computer-readable storage media of claim 1, wherein said first answer set comprises a third set of abduced assertions that comprise said first assertion and that involve a plurality of variables comprising said first variable, and wherein the method further comprises:

substituting constants for ungrounded variables in said third set to create a fourth set, a relationship between said constants and said ungrounded variables being a revert-substitution;

dividing said fourth set into clusters of assertions based on which assertions in said fourth set have variables in common;

for each one of the clusters, if said one of the clusters implies the fourth set with said one of the clusters removed, then removing said one of the clusters from the fourth set; and

applying said revert-substitution to said fourth set.

8. The one or more computer-readable storage media of claim 1, wherein said first answer set comprises a third set of abduced assertions that comprise said first assertion that involve a plurality of variables and a fourth set of constraints on said plurality of variables, said plurality of variable comprising said first variable, said fourth set of constraints comprising said first constraint, and wherein the method further comprises:

removing, from said fourth set, a member of said fourth set that is implied by the other members of said fourth set.

9. A method of managing access to a resource, the method comprising:

abducing, from first information that comprises (a) a query and (b) a policy implemented by a guard that controls access to the resource, a first answer set that comprises a first assertion set, said first answer set comprising a first assertion, a first variable, and a first constraint that have been chosen, said first assertion set comprising said first assertion;

receiving, by said guard, a second assertion set that comprises either (a) said first assertion set, or (b) a third assertion set that is derived from said first assertion set by substituting at least one variable in place of at least one principal named in said first assertion set;

determining, by said guard, that said query is true under said policy in the presence of second information that comprises said second assertion set; and

based on said determining, allowing an entity to access the resource.

10. The method of claim 9, wherein said abducing further comprises:

creating one or more sub-goals such that said query is true when each of the one or more sub-goals is met;

creating a second answer set under which a first one of said sub-goals is true under said policy;

determining that said second answer set is subsumed by a fourth answer set; and

creating said first answer set based on said fourth answer set.

11. The method of claim 10, wherein said second answer set has a first assumption set having a first number of assumption(s), wherein said fourth answer set has a second assumption set having a second number of assumption(s), and wherein said determining that said second answer set is subsumed by said fourth answer set comprises:

determining that said first number is greater than or equal to said second number.

12. The method of claim 10, wherein said second answer set comprises a first collection of one or more variables, wherein said fourth answer set comprises a second collection of one or more variables, and wherein said determining that said second answer set is subsumed by said fourth answer set comprises:

determining whether a substitution, which defines relationships among variables, exists such that one or more conditions involving said second answer set and said fourth answer set are satisfied when said substitution is applied to said first collection and said second collection.

13. The method of claim 9, wherein the method further comprises:

receiving, from a person, a fourth assertion set that comprises one or more assertions,

wherein said first information further comprises (c) said fourth assertion set, and wherein said second information comprises said fourth assertion set.

14. The method of claim 9, further comprising:

using a filter to determine whether said query has abducible sub-goals and to govern what types of assertions may be included in said first answer set.

15. The method of claim 9, wherein said first information further comprises (c) a fourth assertion set received from a person, and wherein the method further comprises:

determining whether said query is deducible from said third assertion set, said policy, or a combination thereof.

16. system comprising:

one or more data remembrance components;

one or more processors;

a set of executable components that are stored in at least one of said one or more data remembrance components and that execute on at least one of said one or more processors, the set of executable components comprising;

a first executable component that abduces a first answer set from information that comprises (a) a query, and (b) a policy that governs access to a resource, said first answer set satisfying a condition that said query is true under said policy in the presence of a set of one or more assertions that is consistent with said first answer set, said first answer set comprising a first assertion, a first variable, and a first constraint that have been chosen; and

a second executable component makes a determination whether said first answer set is subsumed by a second answer set, said second answer set comprising a second assertion, a second variable, and a second constraint that have been chosen; and

a communications component through which said system provides said first answer set, said second answer set, or both said first answer set and said second answer set.

17. The system of claim 16, wherein said second executable component makes said determination based on one or more factors that comprise:

a comparison of a first cardinality of a first abduced assumption set in said first answer set with a second cardinality of a second abduced assumption set in said second answer set; and

whether there exists a substitution that satisfies criteria comprising;

that a first literal represented by said first answer set is logically equivalent to a second literal represented by said second answer set when said substitution is applied to variables in said first answer set and said second answer set;

that said first abduced assumption set is contained within said second abduced assumption set when said substitution is applied to variables in said first abduced assumption set and said second abduced assumption set;

that a first constraint set of said first answer set satisfies a constraint-subsumption relationship with a second constraint set of said second answer set.

18. The system of claim 16, wherein said set of executable components further comprises:

a third executable component that limits what types of assertions said first executable component may abduce, or which abduced assertions said first executable component may include in said first answer set.

19. The system of claim 16, wherein said second executable component makes said determination based on one or more factors that comprise:

whether there exists a substitution under which said first answer set stands in a defined relationship to said second answer set when variables in said first answer set and said second answer set are substituted according to said substitution.

20. The system of claim 16, wherein said first answer set comprises said first constraint which constrains one or more variables in said first answer set, wherein said second answer set comprises said second constraint which constrains one or more variables in said second answer set, and wherein said second executable component makes said determination based on one or more factors that comprise:

whether satisfaction of said second constraint implies satisfaction of said first constraint.