Potential Vulnerability: Regular expression Denial of Service - ReDoS

[ganpatgutte]

Hello,

I came across a potential denial of service vulnerability, if a malicious expression is used the regular expression could run indefinite and may result in denial of service error.

internal class Detector
{
	private readonly ParserSettings _settings;

	private static readonly Regex IdentifiersDetectionRegex = new Regex(@"(?<id>@?[\p{L}\p{Nl}_][\p{L}\p{Nl}\p{Nd}\p{Mn}\p{Mc}\p{Pc}\p{Cf}_]*)", RegexOptions.Compiled);

	private static readonly string Id = IdentifiersDetectionRegex.ToString();
	private static readonly string Type = Id.Replace("<id>", "<type>");
	private static readonly Regex LambdaDetectionRegex = new Regex($@"(\((((?<withtype>({Type}\s+)?{Id}))(\s*,\s*)?)+\)|(?<withtype>{Id}))\s*=>", RegexOptions.Compiled);

	private static readonly Regex StringDetectionRegex = new Regex(@"(?<!\\)?"".*?(?<!\\)""", RegexOptions.Compiled);
	private static readonly Regex CharDetectionRegex = new Regex(@"(?<!\\)?'.{1,2}?(?<!\\)'", RegexOptions.Compiled);

Solution: Restricting or adding some timeout while declaring regex would help avoid the denial of service issue.

your thoughts please!

[davideicardi]

Thank you @ganpatgutte for the report.
By default I think that regular expression are not enabled, see here. This problem is only when someone reference the regular expression type. Right?

Or do you see cases where some injected text could cause this vulnerability?

[madsuhrenholt]

Hi @davideicardi
I have an issue currently, where the "foreach (Match match in LambdaDetectionRegex.Matches(expression))" in the Detector times out, but my expression, and any of my expressions does not contain any lambda parameters. Also I do have not set the Lambda expression to true.
Do you see any issues with adding a check which only detects lambda parameters if the Lambda Expression setting is set to true?

Eg.

var lambdaParameters = new Dictionary<string, Identifier>();
if (_settings.LambdaExpressions)
{
// find lambda parameters
foreach (Match match in LambdaDetectionRegex.Matches(expression))
{
...

[davideicardi]

@madsuhrenholt
Do you have a particular complex expression? Maybe there is some bug that cause the timeout?
Can you share it for debugging?

Adding a feature flag anyway can be an option, maybe with the opposite behavior: the feature flag can be used to disable the check..

[madsuhrenholt]

Hi @davideicardi

This is the expression.

IF(MARGINAL_REFERENCE_PRICE>MARGINAL_PRICE,IF(REFERENCE_PRICE_WITH_PRICESTATE!=null, REFERENCE_PRICE_WITH_PRICESTATE, REFERENCE_PRICE_WITH_PRICESTATE_1),MARGINAL_COMPENSATION_PRICE)

I do not think there is a bug in the expression itself, as after we have bypassed the lambda expression check, it works fine, and we are able to parse the expression.

It seems like it is the length of the expression, in regards to characters, which is causing the issue, because we also tried the to run with the same logic, just with fewer letters, and there it is fast:
"IF(a>b,IF(c!=null, c, d),e)"

[davideicardi]

@ganpatgutte Sorry, I just reread your message and realized I previously misunderstood your report. The problem lies in the built-in detector. Do you know which kind of expression might cause this issue?

[metoule]

@madsuhrenholt can you please add a full reproduction? I've executed the following code:

var target = new Interpreter();
var code = "IF(MARGINAL_REFERENCE_PRICE>MARGINAL_PRICE,IF(REFERENCE_PRICE_WITH_PRICESTATE!=null, REFERENCE_PRICE_WITH_PRICESTATE, REFERENCE_PRICE_WITH_PRICESTATE_1),MARGINAL_COMPENSATION_PRICE)";
var detectedIdentifiers = target.DetectIdentifiers(code);
Assert.That(detectedIdentifiers.UnknownIdentifiers, Is.EqualTo(new[] { "IF", "MARGINAL_REFERENCE_PRICE", "MARGINAL_PRICE", "REFERENCE_PRICE_WITH_PRICESTATE", "REFERENCE_PRICE_WITH_PRICESTATE_1", "MARGINAL_COMPENSATION_PRICE" }));

and it finishes relatively quickly (about 500ms on .NET framework 4.6.2 and about 153ms on .NET9).