Safe mode for inverse query evaluations

• US 20070078829A1
• Filed: 10/05/2005
• Published: 04/05/2007
• Est. Priority Date: 10/05/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Diplan, Pompiliu, Madan, Umesh, Stern, Aaron, Eppley, Geary
• Granted Patent: US 7,899,817 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8373 Query execution
• CPC Class Codes: G06F 21/52 during program execution, e.g. stack integrity ; Preventing unwanted data erasure; Buffer overflow

Abstract

Embodiments herein prevent or mitigate attacks on inverse query engines by providing safe mode routines that allow for the acceptance of third party messages and/or query expressions, as well as prevent trusted sources from accidental attacks. The mitigations fall into two categories: compile-time and runtime. Compile-time mitigations prevent query expressions from being accepted and compiled that are susceptible to known attacks. For example, the complexity of query expressions may be limited to functions with linear runtimes; constant memory usage; or ones that do not create large strings. Further, language constructs for the criteria in the query expression may not allow for nested predicates complexities. Runtime mitigations, on the other hand, monitor the data size and processing lengths of messages against the various query expressions. If these runtime quotas are exceeded, an exception or other violation indication may be thrown (e.g., abort), deeming the evaluation as under attack.

Claims

1. In an inverse query engine configured to evaluate messages against query expressions executed in a runtime safe mode, a method of mitigating attacks on the inverse query engine by comparing monitored runtime data for the messages against quota restrictions, the method comprising:

receiving a message that includes one or more inputs used in runtime evaluation of the message against query expressions for determining if the one or more inputs satisfy the criteria thereof;

monitoring the runtime evaluation of the one or more inputs for collecting runtime data used in determining if the evaluation overly consumes processing time, memory resources, or both;

accessing one or more runtime quotas, which define a threshold of tolerable limits in terms of data size, processing lengths, or both; and

comparing the runtime data against the one or more runtime quotas for determining if an exception or other violation indication will be thrown based on one or more runtime data values that exceed the threshold limits of the one or more runtime quotas.

2. The method of claim 1, wherein the one or more runtime quotas defined by the processing lengths include processing duration for the message, a node count for the runtime evaluation, or both.

3. The method of claim 1, wherein the one or more runtime quotas defined by the data size include a limitation of a data size of the message, data size of one or more inputs, or both.

4. The method of claim 3, wherein the data size of the message limits the number of inputs in the message, the number of total bytes in the message, or both, and the data size of the one or more inputs limits the number of sub-inputs of the one or more inputs, the number of characters in the one or more inputs, or both.

5. The method of claim 4, wherein the data size of the one or more inputs is limited by a string length of the concatenation of the sub-inputs.

6. The method of claim 1, wherein the one or more runtime quotas are configurable.

7. The method of claim 6, wherein the message is received by a third party, and wherein the runtime quotas are dynamically adjusted based on an unreliability confidence level of the message as determined by historical data about other messages received from the third party.

8. The method of claim 1, wherein the message is considered unreliable and an exception is thrown that causes one or more of terminating the evaluation, raising an alert to a system administrator, or both.

9. The method of claim 1, wherein the inverse query engine is an XPath engine and the message is an XML document.

10. A computer program product that includes computer readable media having stored thereon computer executable instructions that, when executed by a processor, can cause the inverse query engine to perform the method of claim 1.

11. In an inverse query engine configured to evaluate messages against criteria for a query expression, a method of evaluating the reliability of the query expression by comparing complexities of the criteria against acceptable limitations when compiling the query expression in a safe mode, the method comprising:

receiving a query expression that includes one or more criteria for applying against inputs of messages;

prior to compiling the query expression, determining the complexities of the one or more criteria in terms of criteria functions, language constructs, or both; and

comparing the complexities of the one or more criteria with one or more complexity limitations that define the reliability of criteria in terms of execution time, memory consumption, or both;

for determining whether the query expression should be compiled for evaluation against the inputs of the messages.

12. The method of claim 11, wherein the one or more complexity limitations further defines the reliability of criteria in terms of operators that combine the criteria functions, language constructs, or both.

13. The method of claim 11, wherein the one or more complexity limitations further defines the reliability of criteria in terms of node-set operations that search for node-set equality, relations, or both.

14. The method of claim 11, wherein the one or more complexity limitations further defines the reliability of the criteria in terms of union operators, which form a union of two node-sets.

15. The method of claim 11, wherein the one or more complexity limitations defines the reliability of the criteria in terms of functions that have, or do, one or more of the following:

non-linear runtimes;

non-constant memory usage;

or create large strings.

16. The method of claim 15, wherein the language constructs include one or more of the functions.

17. The method of claim 11, wherein the complexity limitations do not allow the language constructs to have nested predicates.

18. The method of claim 11, wherein the query expression is received from a third party and the complexity limitations are dynamically adjustable based on a degree of trust for the third party.

19. The method of claim 11, wherein the complexity limitations are adjustable based on the composite complexity of all functions and language constructions within the query expression.

20. A computer program product that includes computer readable media having stored thereon computer executable instructions that, when executed by a processor, can cause the inverse query engine to perform the method of claim 11.