Denial of Service from comparison of user input against expensive regex¶
ID: cs/redosKind: path-problemSecurity severity: 7.5Severity: errorPrecision: highTags: - security - external/cwe/cwe-1333 - external/cwe/cwe-730 - external/cwe/cwe-400Query suites: - csharp-code-scanning.qls - csharp-security-extended.qls - csharp-security-and-quality.qls
Click to see the query in the CodeQL repository
Matching user input against a regular expression which takes exponential time in the worst case can allow a malicious user to perform a Denial of Service (”DoS”) attack by crafting input that takes a long time to execute.
Most regular expression engines, including the C# standard library implementation, are designed to work with an extended regular expression syntax. Although this provides flexibility for the user, it can prevent the engine from constructing an efficient implementation of the matcher in all circumstances. In particular, the “worst case time complexity” (see the references) of certain regular expressions may be “exponential”. This would allow a malicious user to provide some input which causes the regular expression to take a very long time to execute.
Typically, a regular expression is vulnerable to this attack if it applies repetition to a sub-expression which itself is repeated, or contains overlapping options. For example,(a+)+ is vulnerable to a string such asaaaaaaaaaaaaaaaaaaaaaaaaaaab. More information about the precise circumstances can be found in the references.
Recommendation¶
Modify the regular expression to avoid the exponential worst case time. If this is not possible, then a timeout should be used to avoid a denial of service. For C# applications, a timeout can be provided to theRegex constructor. Alternatively, apply a global timeout by setting theREGEX_DEFAULT_MATCH_TIMEOUT application domain property, using theAppDomain.SetData method.
Example¶
The following example shows a HTTP request parameter that is matched against a regular expression which has exponential worst case performance. In the first case, it is matched without a timeout, which can lead to a denial of service. In the second case, a timeout is used to cancel the evaluation of the regular expression after 1 second.
usingSystem;usingSystem.Web;usingSystem.Text.RegularExpressions;publicclassReDoSHandler:IHttpHandler{publicvoidProcessRequest(HttpContextctx){stringuserInput=ctx.Request.QueryString["userInput"];// BAD: User input is matched against a regex with exponential worst case behaviornewRegex("^([a-z]*)*$").Match(userInput);// GOOD: Regex is given a timeout to avoid DoSnewRegex("^([a-z]*)*$",RegexOptions.IgnoreCase,TimeSpan.FromSeconds(1)).Match(userInput);}}
References¶
Wikipedia:ReDoS.
Wikipedia:Time complexity.
Common Weakness Enumeration:CWE-1333.
Common Weakness Enumeration:CWE-730.
Common Weakness Enumeration:CWE-400.