Safe mode for inverse query evaluations

• US 7,899,817 B2
• Filed: 10/05/2005
• Issued: 03/01/2011
• Est. Priority Date: 10/05/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Eppley, Geary L., Stern, Aaron A., Diplan, Pompiliu, Madan, Umesh
• Primary Examiner(s): Le; Debbie
• Assistant Examiner(s): Tran; Bao G
• Application Number:
  US11/245,322
• Publication Number:
  US 20070078829A1
• Time in Patent Office: 1,973 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 707/2, 707/102, 707/203, 707/100, 707/10, 707/999.003, 707/999.004, 707/706, 707/713, 707/722, 707/758, 707/781, 715255-272, 715/210, 717/131, 706/56, 726/22, 726/26
• US Class Current: 707/731
• 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. At computer system, the computer system including a processor, the computer system also including an inverse query engine configured to evaluate messages against query expressions, a method of mitigating Denial Of Service (“

DOS”

) attacks against the inverse query engine, the method comprising;

tuning one or more thresholds for use in a runtime safe mode to provide a desired level of safety for the inverse query engine that balances permitted query expression functionality against the susceptibility of the inverse query engine to Denial of Service (“

DOS”

) attacks;

receiving a message from a third party, the message including a plurality of message inputs used in runtime evaluation of the message against query expressions, wherein each query expression include a series of queries that comprise one or more conditions, criteria, or rules that must be satisfied by one or more inputs for a query to evaluate to true, and wherein the runtime evaluation of the message determines which of the message inputs satisfy at least one of the query expressions;

the processor dynamically adjusting the tuned one or more thresholds based on a known reliability of the third party, the known reliability based on historical data about the monitoring of other messages receives from the third party;

initiating runtime evaluation of the message inputs against the query expressions to produce query results;

a runtime evaluation module externally monitoring the ongoing runtime evaluation of message inputs against the query expressions to detect a DOS attack on the inverse query engine, including;

accessing a portion of query results;

comparing the query results against the dynamically adjusted tuned one or more thresholds; and

based on the comparison, the processor determining that the accessed portion of query results has caused at least one of the dynamically adjusted tuned one or more thresholds to be exceeded;

in response to determining that at least one of the dynamically adjusted tuned one or more thresholds has been exceeded;

indicating a violation with respect to the received message; and

stopping the inverse query engine from further evaluating the message against the query expressions.

2. The method of claim 1, wherein the one or more thresholds define processing lengths including 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 thresholds define data size including 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 thresholds are configurable.

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

8. A computer program product for use at a computer system, the computer system including an inverse query engine to evaluate messages against query expressions the computer program product for implementing a method of mitigating Denial of Service (“

DOS”

) attacks against the inverse query engine, the computer program product comprising one or more computer storage devices having stored thereon computer-executable instructions that, when executed at a processor, cause the computer system to perform the method including the following;

tune one or more thresholds for use in a runtime safe mode to provide a desired level of safety for the inverse query engine that balances permitted query expression functionality against the susceptibility of the inverse query engine to Denial of Service (“

DOS”

) attacks;

receive a message from a third party, the message including a plurality of message inputs used in runtime evaluation of the message against query expressions, wherein each query expression include a series of queries that comprise one or more conditions, criteria, or rules that must be satisfied by one or more inputs for a query to evaluate to true, and wherein the runtime evaluation of the message determines which of the message inputs satisfy at least one of the query expressions;

dynamically adjust the tuned one or more thresholds based on a known reliability of the third party, the known reliability based on historical data about the monitoring of other messages receives from the third party;

initiate runtime evaluation of the message inputs against the query expressions to produce query results;

externally monitor, at a runtime evaluation module, the ongoing runtime evaluation of message inputs against the query expressions to detect a DOS attack on the inverse query engine, including;

access a portion of the query results;

compare the query results against the dynamically adjusted tuned one or more thresholds; and

based on the comparison, determine that the access portion of query results has caused at least one of the dynamically adjusted tuned one or more thresholds to be exceeded;

in response to determining that at least one of the dynamically adjusted tuned one or more thresholds has been exceeded;

indicate a violation with respect to the received message; and

stop the inverse query engine from further evaluating the message against the query expressions.