.NET Regular Expression Backtrack ReDos check.

README.md

This is ReDos checking for .NET C#.

Based on Backtracking in .NET Regular Expressions | Microsoft Learn and WEB+BDB PRESS Vol.130.

In C#, Regex engine implement with VM (NFA) so develop has responsibility for it's quality of matching. .NET 7 introduce opt-in DFA Regex engine with RegexOptions.NonBackTracking.

See [Regular Expression behavior | Microsoft Learn)[https://learn.microsoft.com/en-us/dotnet/standard/base-types/details-of-regular-expression-behavior] for why .NET Regex is using NFA.

However, there are ReDos vulnerability on VM (NFA) engine. This sample shows back track effect and mitigation.

• NotBacktrack: No backtrack pattern and input.
• BacktrackInput: Has backtrack pattern and input.
• BacktrackInput30: Has backtrack pattern and 30 charactor length input.
• BacktrackInput31: Has backtrack pattern and 31 charactor length input.
• BacktrackInput31b: Has backtrack pattern and 31 charactor length input, missed result increase effect.
• ComplexBacktrackMatch: Complex backtrack pattern and input. Match effect with backtrack even result is matched.
• ComplexBacktrackMissed: Complex backtrack pattern and input. More effect then match when missed.
• NoLookBehindAssertion: Email input and backtrack, no mitigation.
• LookBehindAssertion: Email input and LookBegind backtrack mitigation.
• NoLookAheadAssertion: Input and backtrack, no mitigation.
• LookAheadAssertion: Unput and LookAhead backtrack mitigation.

Mitigation pattern

• Session level timeout: In general Dos can mitigate with session level timeout. It can offer with Middleware or something similar.
• Use DFA match implemenation: DFA generally worth match speed or memory effiency, but it guaranteed match complete in liner time. .NET 7 will introduce DFA with RegexOptions.NonBacktracking. Other languages supported with re2(C++), regexp(Go) and regex(Rust). See RegexOptions.Constrained · Issue #57891 · dotnet/runtime and Add RegexOptions.NonBacktracking by stephentoub · Pull Request #60607 · dotnet/runtime for .NET 7 DFA detail.
• Restrict input length: Accept only shorter input can ignore ReDos impact. However exponential ReDos may have X sec impact on 100 letter and around.
• ReDos detection: recheck is one of libary detect ReDos.
• Don't use Regular expression: You know, trim space doesn't need regular expressions.
• Regex Timeout: .NET C# Regex has timeout option like new Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1));, also Ruby 3.2 plan it.
• Selective memorize: Using Selective Memorization to Defeat Regular Expression Denial of Service(ReDos) explains correct cache can make regular expression linear, but it describe M-NFA consume memory.

Regex_Backtrack_ReDos.cs

BenchmarkRunner.Run<BenchmarkRegex>();

[BenchmarkDotNet.Attributes.MemoryDiagnoser]
public class BenchmarkRegex
{
    [Benchmark]
    public void NotBacktrack()
    {
        string input = "needing a reed";
        string pattern = @"e{2}\w\b";
        Regex.Matches(input, pattern); // matched
    }

    [Benchmark]
    public void BacktrackInput()
    {
        string input = "Essential services are provided by regular expressions.";
        string pattern = ".*(es)";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // matched
    }

    [Benchmark]
    public void BacktrackInput30()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // matched
    }

    [Benchmark]
    public void BacktrackInput31()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // matched
    }
    
    [Benchmark]
    public void BacktrackInput31b()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // missed
    }

    [Benchmark]
    public void ComplexBacktrackMatch()
    {
        string pattern = "^(a+)+$";
        string input = "aaaaaa";
        Regex.Match(input, pattern); // match
    }

    [Benchmark]
    public void ComplexBacktrackMissed()
    {
        string pattern = "^(a+)+$";
        string input = "aaaaa!";
        Regex.Match(input, pattern); // missed
    }

    [Benchmark]
    public void NoLookBehindAssertion()
    {
        string input = "[email protected]";
        string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // matched
    }

    [Benchmark]
    public void LookBehindAssertion()
    {
        string input = "[email protected]";
        string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
        Regex.Match(input, behindPattern, RegexOptions.IgnoreCase); // matched
    }

    [Benchmark]
    public void NoLookAheadAssertion()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // missed
    }
    [Benchmark]
    public void LookAheadAssertion()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
        Regex.Match(input, aheadPattern, RegexOptions.IgnoreCase); // missed
    }
}

Regex_Backtrack_ReDos_NET7.cs

BenchmarkRunner.Run<BenchmarkRegex>();

[BenchmarkDotNet.Attributes.MemoryDiagnoser]
public class BenchmarkRegex
{
    [Benchmark]
    public void Normal()
    {
        string input = "needing a reed";
        string pattern = @"e{2}\w\b";
        Regex.Matches(input, pattern); // matched
    }

    [Benchmark]
    public void BacktrackInput()
    {
        string input = "Essential services are provided by regular expressions.";
        string pattern = ".*(es)";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // matched
    }

    [Benchmark]
    public void BacktrackInput30()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // matched
    }

    [Benchmark]
    public void BacktrackInput31()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // matched
    }
    
    [Benchmark]
    public void BacktrackInput31b()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // missed
    }

    [Benchmark]
    public void ComplexBacktrackMatch()
    {
        string pattern = "^(a+)+$";
        string input = "aaaaaa";
        Regex.Match(input, pattern); // match
    }

    [Benchmark]
    public void ComplexBacktrackMissed()
    {
        string pattern = "^(a+)+$";
        string input = "aaaaa!";
        Regex.Match(input, pattern); // missed
    }

    [Benchmark]
    public void BacktracNoLookBehindAssertion()
    {
        string input = "[email protected]";
        string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // matched
    }

    [Benchmark]
    public void BacktracLookBehindAssertion()
    {
        string input = "[email protected]";
        string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
        Regex.Match(input, behindPattern, RegexOptions.IgnoreCase); // matched
    }

    [Benchmark]
    public void BacktracNoLookAheadAssertion()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase); // missed
    }
    [Benchmark]
    public void BacktrackLookAheadAssertion()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
        Regex.Match(input, aheadPattern, RegexOptions.IgnoreCase); // missed
    }

    /// <summary>/////////////////////////////////</summary>

    [Benchmark]
    public void NonBacktrack()
    {
        string input = "needing a reed";
        string pattern = @"e{2}\w\b";
        Regex.Matches(input, pattern, RegexOptions.NonBacktracking); // matched
    }

    [Benchmark]
    public void NonBacktrackInput()
    {
        string input = "Essential services are provided by regular expressions.";
        string pattern = ".*(es)";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase | RegexOptions.NonBacktracking); // matched
    }

    [Benchmark]
    public void NonBacktrackInput30()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase | RegexOptions.NonBacktracking); // matched
    }

    [Benchmark]
    public void NonBacktrackInput31()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase | RegexOptions.NonBacktracking); // matched
    }

    [Benchmark]
    public void NonBacktrackInput31b()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        string pattern = "^(a|a)*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase | RegexOptions.NonBacktracking); // missed
    }

    [Benchmark]
    public void ComplexNonBacktrackMatch()
    {
        string pattern = "^(a+)+$";
        string input = "aaaaaa";
        Regex.Match(input, pattern,  RegexOptions.NonBacktracking); // match
    }

    [Benchmark]
    public void ComplexNonBacktrackMissed()
    {
        string pattern = "^(a+)+$";
        string input = "aaaaa!";
        Regex.Match(input, pattern, RegexOptions.NonBacktracking); // missed
    }

    [Benchmark]
    public void NonBacktrackNoLookBehindAssertion()
    {
        string input = "[email protected]";
        string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase | RegexOptions.NonBacktracking); // matched
    }

    [Benchmark]
    public void NonBacktrackLookBehindAssertion()
    {
        // NotSupportedException: RegexOptions.NonBacktracking is not supported in conjunction with expressions containing: 'positive lookahead (?= pattern) or positive lookbehind (?<= pattern)'.
        string input = "[email protected]";
        string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
        Regex.Match(input, behindPattern, RegexOptions.IgnoreCase | RegexOptions.NonBacktracking); // matched
    }

    [Benchmark]
    public void NonBacktrackNoLookAheadAssertion()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
        Regex.Match(input, pattern, RegexOptions.IgnoreCase | RegexOptions.NonBacktracking); // missed
    }
    [Benchmark]
    public void NonBacktrackLookAheadAssertion()
    {
        // NotSupportedException: RegexOptions.NonBacktracking is not supported in conjunction with expressions containing: 'positive lookahead (?= pattern) or positive lookbehind (?<= pattern)'.
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
        Regex.Match(input, aheadPattern, RegexOptions.IgnoreCase | RegexOptions.NonBacktracking); // missed
    }
}

Regex_Backtrack_ReDos_NET7_Compile.cs

BenchmarkRunner.Run<BenchmarkRegex>();

[BenchmarkDotNet.Attributes.MemoryDiagnoser]
public class BenchmarkRegex
{
    // Compile
    private Regex NfaMatchInput = new("^(a|a)*$", RegexOptions.IgnoreCase | RegexOptions.Compiled);
    private Regex NfaComplex = new("^(a+)+$");
    private Regex NfaEmail = new(@"^[0-9A-Z]([-.\w]*[0-9A-Z])?@", RegexOptions.IgnoreCase | RegexOptions.Compiled);
    private Regex NfaEmailLookBehind = new(@"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@", RegexOptions.IgnoreCase | RegexOptions.Compiled);
    private Regex NfaNoLookAhead = new(@"^(([A-Z]\w*)+\.)*[A-Z]\w*$", RegexOptions.IgnoreCase | RegexOptions.Compiled);
    private Regex NfaLookAhead = new(@"^((?=[A-Z])\w+\.)*[A-Z]\w*$", RegexOptions.IgnoreCase | RegexOptions.Compiled);

    private Regex DfaMatchInput = new("^(a|a)*$", RegexOptions.NonBacktracking | RegexOptions.IgnoreCase | RegexOptions.Compiled);
    private Regex DfaComplex = new("^(a+)+$", RegexOptions.NonBacktracking);
    private Regex DfaEmail = new(@"^[0-9A-Z]([-.\w]*[0-9A-Z])?@", RegexOptions.NonBacktracking | RegexOptions.IgnoreCase | RegexOptions.Compiled);
    private Regex DfaLookAhead = new(@"^(([A-Z]\w*)+\.)*[A-Z]\w*$", RegexOptions.NonBacktracking | RegexOptions.IgnoreCase | RegexOptions.Compiled);

    [Benchmark]
    public void BacktrackInput31b()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        NfaMatchInput.Match(input); // missed
    }

    [Benchmark]
    public void ComplexBacktrackMatch()
    {
        string input = "aaaaaa";
        NfaComplex.Match(input); // match
    }

    [Benchmark]
    public void ComplexBacktrackMissed()
    {
        string input = "aaaaa!";
        NfaComplex.Match(input); // missed
    }

    [Benchmark]
    public void BacktracNoLookBehindAssertion()
    {
        string input = "[email protected]";
        NfaEmail.Match(input); // matched
    }

    [Benchmark]
    public void BacktracLookBehindAssertion()
    {
        string input = "[email protected]";
        NfaEmailLookBehind.Match(input); // matched
    }

    [Benchmark]
    public void BacktracNoLookAheadAssertion()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        NfaNoLookAhead.Match(input); // missed
    }
    [Benchmark]
    public void BacktrackLookAheadAssertion()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        NfaLookAhead.Match(input); // missed
    }

    /// <summary>/////////////////////////////////</summary>

    [Benchmark]
    public void NonBacktrackInput31b()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        DfaMatchInput.Match(input); // missed
    }

    [Benchmark]
    public void ComplexNonBacktrackMatch()
    {
        string input = "aaaaaa";
        DfaComplex.Match(input); // match
    }

    [Benchmark]
    public void ComplexNonBacktrackMissed()
    {
        string input = "aaaaa!";
        DfaComplex.Match(input); // missed
    }

    [Benchmark]
    public void NonBacktrackNoLookBehindAssertion()
    {
        string input = "[email protected]";
        DfaLookAhead.Match(input); // matched
    }

    [Benchmark]
    public void NonBacktrackNoLookAheadAssertion()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        DfaLookAhead.Match(input); // missed
    }
}

Regex_Backtrack_ReDos_NET7_SourceGenerator.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text.RegularExpressions;

BenchmarkRunner.Run<BenchmarkRegex>();
BenchmarkRunner.Run<BenchmarkRegexMissed>();

public partial class Nfa
{
    [GeneratedRegex(@"^(a+)+$", RegexOptions.IgnoreCase)]
    public static partial Regex Regex();

    public void Match(string input)
    {
        Regex().Match(input);
    }
}

public partial class Dfa
{
    [GeneratedRegex(@"^(a+)+$", RegexOptions.IgnoreCase | RegexOptions.NonBacktracking)]
    public static partial Regex Regex();

    public void Match(string input)
    {
        Regex().Match(input);
    }
}

[BenchmarkDotNet.Attributes.MemoryDiagnoser]
public class BenchmarkRegex
{
    private Regex NfaComplex = new("^(a+)+$", RegexOptions.Compiled);
    private Regex DfaComplex = new("^(a+)+$", RegexOptions.NonBacktracking | RegexOptions.Compiled);
    private Nfa NfaSourceGen = new Nfa();
    private Dfa DfaSourceGen = new Dfa();

    [Benchmark]
    public void NoCompileNfa()
    {
        string input = "aaaaaa";
        Regex.Match(input, "^(a+)+$"); // match
    }

    [Benchmark]
    public void NoCompileDfa()
    {
        string input = "aaaaaa";
        Regex.Match(input, "^(a+)+$", RegexOptions.NonBacktracking); // match
    }

    [Benchmark]
    public void StaticNfa()
    {
        string input = "aaaaaa";
        NfaComplex.Match(input); // match
    }

    [Benchmark]
    public void StaticDfa()
    {
        string input = "aaaaaa";
        DfaComplex.Match(input); // match
    }

    [Benchmark]
    public void SourceGeneeratorNfa()
    {
        string input = "aaaaaa";
        NfaSourceGen.Match(input); // match
    }

    [Benchmark]
    public void SourceGeneeratorDfa()
    {
        string input = "aaaaaa";
        DfaSourceGen.Match(input); // match
    }
}

[BenchmarkDotNet.Attributes.MemoryDiagnoser]
public class BenchmarkRegexMissed
{
    private Regex NfaComplex = new("^(a+)+$", RegexOptions.Compiled);
    private Regex DfaComplex = new("^(a+)+$", RegexOptions.NonBacktracking | RegexOptions.Compiled);
    private Nfa NfaSourceGen = new Nfa();
    private Dfa DfaSourceGen = new Dfa();

    [Benchmark]
    public void NoCompileNfa()
    {
        string input = "aaaaa!";
        Regex.Match(input, "^(a+)+$"); // match
    }

    [Benchmark]
    public void NoCompileDfa()
    {
        string input = "aaaaa!";
        Regex.Match(input, "^(a+)+$", RegexOptions.NonBacktracking); // match
    }

    [Benchmark]
    public void StaticNfa()
    {
        string input = "aaaaa!";
        NfaComplex.Match(input); // match
    }

    [Benchmark]
    public void StaticDfa()
    {
        string input = "aaaaa!";
        DfaComplex.Match(input); // match
    }

    [Benchmark]
    public void SourceGeneeratorNfa()
    {
        string input = "aaaaa!";
        NfaSourceGen.Match(input); // match
    }

    [Benchmark]
    public void SourceGeneeratorDfa()
    {
        string input = "aaaaa!";
        DfaSourceGen.Match(input); // match
    }
}

Regex_Benchmark_NET6.md

// * Summary *

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000 AMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores .NET SDK=6.0.401 [Host] : .NET 6.0.9 (6.0.922.41905), X64 RyuJIT

Method	Mean	Error	StdDev	Gen 0	Allocated
NotBacktrack	19.19 ns	0.176 ns	0.165 ns	0.0052	88 B
BacktrackInput	316.12 ns	2.619 ns	2.450 ns	0.0148	248 B
BacktrackInput30	894.44 ns	3.515 ns	3.288 ns	0.0591	992 B
BacktrackInput31	929.89 ns	8.522 ns	7.972 ns	0.0591	992 B
BacktrackInput31b	1,416.29 ns	8.396 ns	7.853 ns	-	-
ComplexBacktrackMatch	146.52 ns	1.313 ns	1.228 ns	0.0148	248 B
ComplexBacktrackMissed	1,844.12 ns	18.889 ns	17.669 ns	-	-
NoLookBehindAssertion	162.40 ns	1.755 ns	1.641 ns	0.0148	248 B
LookBehindAssertion	116.71 ns	1.009 ns	0.943 ns	0.0124	208 B
NoLookAheadAssertion	353,101,000.00 ns	1,735,451.384 ns	1,538,432.448 ns	-	1,632 B
LookAheadAssertion	328.39 ns	0.607 ns	0.507 ns	-	-

// * Legends * Mean : Arithmetic mean of all measurements Error : Half of 99.9% confidence interval StdDev : Standard deviation of all measurements Gen 0 : GC Generation 0 collects per 1000 operations Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B) 1 ns : 1 Nanosecond (0.000000001 sec)

Regex_Benchmark_NET7.md

// * Summary *

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000 AMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores .NET SDK=7.0.100-rc.1.22431.12 [Host] : .NET 7.0.0 (7.0.22.42610), X64 RyuJIT

Method	Mean	Error	StdDev	Median	Gen 0	Allocated
Normal	20.66 ns	0.189 ns	0.177 ns	20.64 ns	0.0052	88 B
BacktrackInput	240.62 ns	1.939 ns	1.814 ns	240.09 ns	0.0148	248 B
BacktrackInput30	871.01 ns	6.829 ns	6.388 ns	869.75 ns	0.0591	992 B
BacktrackInput31	909.90 ns	9.415 ns	7.862 ns	908.61 ns	0.0591	992 B
BacktrackInput31b	1,369.18 ns	7.100 ns	6.641 ns	1,367.38 ns	-	-
ComplexBacktrackMatch	142.26 ns	1.460 ns	1.365 ns	141.97 ns	0.0148	248 B
ComplexBacktrackMissed	1,707.41 ns	12.625 ns	10.543 ns	1,711.03 ns	-	-
BacktracNoLookBehindAssertion	180.49 ns	1.124 ns	0.996 ns	180.25 ns	0.0148	248 B
BacktracLookBehindAssertion	117.23 ns	1.018 ns	0.952 ns	117.22 ns	0.0124	208 B
BacktracNoLookAheadAssertion	339,042,766.67 ns	1,872,116.398 ns	1,751,178.840 ns	338,861,100.00 ns	-	-
BacktrackLookAheadAssertion	261.63 ns	5.268 ns	7.722 ns	257.05 ns	-	-
NonBacktrack	21.17 ns	0.326 ns	0.305 ns	21.24 ns	0.0052	88 B
NonBacktrackInput	3,636.84 ns	11.047 ns	10.334 ns	3,633.64 ns	0.0572	960 B
NonBacktrackInput30	2,328.36 ns	3.263 ns	2.893 ns	2,328.35 ns	0.0229	384 B
NonBacktrackInput31	2,423.09 ns	6.134 ns	5.738 ns	2,422.79 ns	0.0229	384 B
NonBacktrackInput31b	229.96 ns	0.769 ns	0.720 ns	229.81 ns	-	-
ComplexNonBacktrackMatch	856.61 ns	3.627 ns	3.028 ns	855.53 ns	0.0229	384 B
ComplexNonBacktrackMissed	78.34 ns	0.206 ns	0.193 ns	78.37 ns	-	-
NonBacktrackNoLookBehindAssertion	871.71 ns	6.130 ns	5.734 ns	871.20 ns	0.0343	576 B
NonBacktrackLookBehindAssertion	NA	NA	NA	NA	-	-
NonBacktrackNoLookAheadAssertion	186.66 ns	3.445 ns	6.212 ns	184.32 ns	-	-
NonBacktrackLookAheadAssertion	NA	NA	NA	NA	-	-

Benchmarks with issues: BenchmarkRegex.NonBacktrackLookBehindAssertion: DefaultJob BenchmarkRegex.NonBacktrackLookAheadAssertion: DefaultJob // * Warnings * MultimodalDistribution BenchmarkRegex.BacktrackLookAheadAssertion: Default -> It seems that the distribution can have several modes (mValue = 2.93)

Regex_Benchmark_NET7_Compile.md

// * Summary *

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000 AMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores .NET SDK=7.0.100-rc.1.22431.12 [Host] : .NET 7.0.0 (7.0.22.42610), X64 RyuJIT

Method	Mean	Error	StdDev	Gen 0	Allocated
BacktrackInput31b	241.08 ns	0.576 ns	0.511 ns	-	-
ComplexBacktrackMatch	136.32 ns	1.469 ns	1.374 ns	0.0148	248 B
ComplexBacktrackMissed	1,699.49 ns	17.283 ns	14.432 ns	-	-
BacktracNoLookBehindAssertion	71.09 ns	1.381 ns	1.591 ns	0.0148	248 B
BacktracLookBehindAssertion	56.77 ns	1.124 ns	1.104 ns	0.0124	208 B
BacktracNoLookAheadAssertion	81,288,132.65 ns	244,769.091 ns	216,981.424 ns	-	-
BacktrackLookAheadAssertion	101.73 ns	0.227 ns	0.213 ns	-	-
NonBacktrackInput31b	218.98 ns	0.528 ns	0.468 ns	-	-
ComplexNonBacktrackMatch	826.32 ns	1.586 ns	1.406 ns	0.0229	384 B
ComplexNonBacktrackMissed	68.33 ns	0.100 ns	0.084 ns	-	-
NonBacktrackNoLookBehindAssertion	62.51 ns	0.085 ns	0.079 ns	-	-
NonBacktrackNoLookAheadAssertion	169.93 ns	0.608 ns	0.539 ns	-	-

// * Legends * Mean : Arithmetic mean of all measurements Error : Half of 99.9% confidence interval StdDev : Standard deviation of all measurements Gen 0 : GC Generation 0 collects per 1000 operations Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B) 1 ns : 1 Nanosecond (0.000000001 sec)

Regex_Benchmark_NET7_SourceGenerator.md

// * Summary *

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22000.978/21H2) AMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores .NET SDK=7.0.100-rc.1.22431.12 [Host] : .NET 7.0.0 (7.0.22.42610), X64 RyuJIT AVX2 [AttachedDebugger] DefaultJob : .NET 7.0.0 (7.0.22.42610), X64 RyuJIT AVX2

Method	Mean	Error	StdDev	Gen0	Allocated
NoCompileNfa	134.12 ns	0.697 ns	0.652 ns	0.0148	248 B
NoCompileDfa	790.81 ns	8.166 ns	7.638 ns	0.0229	384 B
StaticNfa	62.86 ns	0.393 ns	0.368 ns	0.0148	248 B
StaticDfa	787.48 ns	3.003 ns	2.809 ns	0.0229	384 B
SourceGeneeratorNfa	64.47 ns	0.266 ns	0.249 ns	0.0148	248 B
SourceGeneeratorDfa	790.16 ns	3.100 ns	2.748 ns	0.0229	384 B

Missed

Method	Mean	Error	StdDev	Allocated
NoCompileNfa	1,834.93 ns	36.326 ns	48.494 ns	-
NoCompileDfa	79.93 ns	1.042 ns	0.975 ns	-
StaticNfa	351.56 ns	1.263 ns	1.182 ns	-
StaticDfa	68.79 ns	0.705 ns	0.660 ns	-
SourceGeneeratorNfa	381.19 ns	2.976 ns	2.638 ns	-
SourceGeneeratorDfa	70.60 ns	0.436 ns	0.408 ns	-

Regex_ReDos_SimpleTest_NET6.cs

void Main()
{
    Console.WriteLine("EDA Exponent");
    ReDosSample.EDAExponentReDos();

    Console.WriteLine("\nIDA Sqrt");
    ReDosSample.IDASqrtReDos();
}

public class ReDosSample
{
    // EDA Structure
    public static void EDAExponentReDos()
    {
        const string pattern = @"^(a|a)*$";

        foreach (var i in new[] {1, 25, 30, 50, 100, 1000})
        {
            var input = Repeat('a', i) + "b";
            ConsoleTime.Start();
            Regex.Match(input, pattern);
            ConsoleTime.End(i.ToString());
        }
    }

    // IDA Structure
    public static void IDASqrtReDos()
    {
        const string pattern = @"^a*a*$";
        foreach (var i in new[] { 10000, 20000, 40000, 80000 })
        {
            var input = Repeat('a', i) + "b";
            ConsoleTime.Start();
            Regex.Match(input, pattern);
            ConsoleTime.End(i.ToString());
        }

    }

    public static class ConsoleTime
    {
        private static Stopwatch _sw = new Stopwatch();
        public static void Start()
        {
            _sw.Start();
        }

        public static void End(string text)
        {
            Console.WriteLine($"{text}: {_sw.Elapsed.TotalMilliseconds}");
            _sw.Reset();
            _sw.Stop();
        }
    }

    private static string Repeat(char charactor, int num)
    {
        var sb = new StringBuilder();
        for (uint i = 0; i < num; i++)
            sb.Append(charactor);
        return sb.ToString();
    }
}

/*
EDA Exponent
1: 0.7216
25: 0.0027
30: 0.0017
50: 0.0025
100: 0.0048
1000: 0.0433

IDA Sqrt
10000: 0.0242
20000: 0.0423
40000: 0.0839
80000: 0.1749
*/

Regex_ReDos_SimpleTest_NET7rc.cs

void Main()
{
    Console.WriteLine("EDA Exponent (NFA)");
    ReDosSample.EDAExponentReDos();

    Console.WriteLine("\nIDA Sqrt (NFA)");
    ReDosSample.IDASqrtReDos();

    Console.WriteLine("\nIDA Sqrt (DFA)");
    ReDosSample.EDAExponentialDFA();

    Console.WriteLine("\nIDA Sqrt (DFA)");
    ReDosSample.IDASqrtDFA();
}

public class ReDosSample
{
    // EDA Structure (VM - NFA)
    public static void EDAExponentReDos()
    {
        const string pattern = @"^(a|a)*$";
        foreach (var i in new[] {1, 25, 30, 50, 100, 1000})
        {
            var input = Repeat('a', i) + "b";
            ConsoleTime.Start();
            Regex.Match(input, pattern);
            ConsoleTime.End(i.ToString());
        }
    }

    // IDA Structure (VM - NFA)
    public static void IDASqrtReDos()
    {
        const string pattern = @"^a*a*$";
        foreach (var i in new[] { 10000, 20000, 40000, 80000 })
        {
            var input = Repeat('a', i) + "b";
            ConsoleTime.Start();
            Regex.Match(input, pattern);
            ConsoleTime.End(i.ToString());
        }
    }

    // EDA Structure (DFA)
    public static void EDAExponentialDFA()
    {
        const string pattern = @"^(a|a)*$";
        foreach (var i in new[] {1, 25, 30, 50, 100, 1000})
        {
            var input = Repeat('a', i) + "b";
            ConsoleTime.Start();
            // RegexOptions.NonBacktracking introduce on .NET 7
            Regex.Match(input, pattern, RegexOptions.NonBacktracking);
            ConsoleTime.End(i.ToString());
        }
    }

    // IDA Structure (DFA)
    public static void IDASqrtDFA()
    {
        const string pattern = @"^a*a*$";
        foreach (var i in new[] { 10000, 20000, 40000, 80000 })
        {
            var input = Repeat('a', i) + "b";
            ConsoleTime.Start();
            Regex.Match(input, pattern, RegexOptions.NonBacktracking);
            ConsoleTime.End(i.ToString());
        }
    }

    public static class ConsoleTime
    {
        private static Stopwatch _sw = new Stopwatch();
        public static void Start()
        {
            _sw.Start();
        }

        public static void End(string text)
        {
            Console.WriteLine($"{text}: {_sw.Elapsed.TotalMilliseconds}");
            _sw.Reset();
            _sw.Stop();
        }
    }

    private static string Repeat(char charactor, int num)
    {
        var sb = new StringBuilder();
        for (uint i = 0; i < num; i++)
            sb.Append(charactor);
        return sb.ToString();
    }
}