IndexOutOfRangeException in RegexInterpreter caused by not always resizing its stack appropriately

[danmoseley]

From fuzzing, these are 3 distinct stacks, with relatively-reduced patterns. Note, the inputs are almost anything - not specially crafted. the examples below are in the interpreter, but I've seen similar crashes/stacks when using compiled mode.

RegexRunner, the base class, maintains several stacks (as managed arrays) and allows its derived classes (RegexInterpreter and CompiledRegexRunner) to push and pop from them. They are responsible for calling EnsureStorage() on RegexRunner to enlarge them if that may be necessary. Both do this in certain places, but not all the places they push to them, and the paths below cause the end of the runtrack (backtracking) stack to be hit.

It's not clear to me what the right fix is here: it seems the author assumed that only certain paths would need the check. The simplest thing would be to remove responsibility from the derived classes and check on every push, if that isn't measurably slower. EnsureStorage() would have to stay, as it's part of the public contract (for precompiled regex assemblies)

These bugs are not regressions - they repro in .NET Framework. So clearly, low priority.

================
Regex.IsMatch("x", @"(?:){93}");

System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at System.Text.RegularExpressions.RegexInterpreter.TrackPush(Int32 i1)
   at System.Text.RegularExpressions.RegexInterpreter.Go()
   at System.Text.RegularExpressions.RegexRunner.Scan(Regex regex, String text, Int32 textbeg, Int32 textend, Int32 textstart, Int32 prevlen, Boolean quick, TimeSpan timeout)
   at System.Text.RegularExpressions.Regex.Run(Boolean quick, Int32 prevlen, String input, Int32 beginning, Int32 length, Int32 startat)
   at System.Text.RegularExpressions.Regex.IsMatch(String input)
   at X.Main() in C:\proj\test\tester.cs:line 12
================
================
Regex.IsMatch("x", @"(?<!a*(?:a?)+?)");

System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at System.Text.RegularExpressions.RegexInterpreter.Backtrack()
   at System.Text.RegularExpressions.RegexInterpreter.Go()
   at System.Text.RegularExpressions.RegexRunner.Scan(Regex regex, String text, Int32 textbeg, Int32 textend, Int32 textstart, Int32 prevlen, Boolean quick, TimeSpan timeout)
   at System.Text.RegularExpressions.Regex.Run(Boolean quick, Int32 prevlen, String input, Int32 beginning, Int32 length, Int32 startat)
   at System.Text.RegularExpressions.Regex.IsMatch(String input)
   at X.Main() in C:\proj\test\tester.cs:line 12
================
================
Regex.IsMatch("xxxx", @"()(?>\1+?).\b");

System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at System.Text.RegularExpressions.RegexInterpreter.Go()
   at System.Text.RegularExpressions.RegexRunner.Scan(Regex regex, String text, Int32 textbeg, Int32 textend, Int32 textstart, Int32 prevlen, Boolean quick, TimeSpan timeout)
   at System.Text.RegularExpressions.Regex.Run(Boolean quick, Int32 prevlen, String input, Int32 beginning, Int32 length, Int32 startat)
   at System.Text.RegularExpressions.Regex.IsMatch(String input)
   at X.Main() in C:\proj\test\tester.cs:line 12
================

Tagging subscribers to this area: @eerhardt, @dotnet/area-system-text-regularexpressions
See info in area-owners.md if you want to be subscribed.

Issue Details

---

From fuzzing, these are 3 distinct stacks, with relatively-reduced patterns. Note, the inputs are almost anything - not specially crafted. the examples below are in the interpreter, but I've seen similar crashes/stacks when using compiled mode.

RegexRunner, the base class, maintains several stacks (as managed arrays) and allows its derived classes (RegexInterpreter and CompiledRegexRunner) to push and pop from them. They are responsible for calling EnsureStorage() on RegexRunner to enlarge them if that may be necessary. Both do this in certain places, but not all the places they push to them, and the paths below cause the end of the runtrack (backtracking) stack to be hit.

It's not clear to me what the right fix is here: it seems the author assumed that only certain paths would need the check. The simplest thing would be to remove responsibility from the derived classes and check on every push, if that isn't measurably slower. EnsureStorage() would have to stay, as it's part of the public contract (for precompiled regex assemblies)

These bugs are not regressions - they repro in .NET Framework. So clearly, low priority.

================
Regex.IsMatch("x", @"(?:){93}");

System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at System.Text.RegularExpressions.RegexInterpreter.TrackPush(Int32 i1)
   at System.Text.RegularExpressions.RegexInterpreter.Go()
   at System.Text.RegularExpressions.RegexRunner.Scan(Regex regex, String text, Int32 textbeg, Int32 textend, Int32 textstart, Int32 prevlen, Boolean quick, TimeSpan timeout)
   at System.Text.RegularExpressions.Regex.Run(Boolean quick, Int32 prevlen, String input, Int32 beginning, Int32 length, Int32 startat)
   at System.Text.RegularExpressions.Regex.IsMatch(String input)
   at X.Main() in C:\proj\test\tester.cs:line 12
================
================
Regex.IsMatch("x", @"(?<!a*(?:a?)+?)");

System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at System.Text.RegularExpressions.RegexInterpreter.Backtrack()
   at System.Text.RegularExpressions.RegexInterpreter.Go()
   at System.Text.RegularExpressions.RegexRunner.Scan(Regex regex, String text, Int32 textbeg, Int32 textend, Int32 textstart, Int32 prevlen, Boolean quick, TimeSpan timeout)
   at System.Text.RegularExpressions.Regex.Run(Boolean quick, Int32 prevlen, String input, Int32 beginning, Int32 length, Int32 startat)
   at System.Text.RegularExpressions.Regex.IsMatch(String input)
   at X.Main() in C:\proj\test\tester.cs:line 12
================
================
Regex.IsMatch("xxxx", @"()(?>\1+?).\b");

System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at System.Text.RegularExpressions.RegexInterpreter.Go()
   at System.Text.RegularExpressions.RegexRunner.Scan(Regex regex, String text, Int32 textbeg, Int32 textend, Int32 textstart, Int32 prevlen, Boolean quick, TimeSpan timeout)
   at System.Text.RegularExpressions.Regex.Run(Boolean quick, Int32 prevlen, String input, Int32 beginning, Int32 length, Int32 startat)
   at System.Text.RegularExpressions.Regex.IsMatch(String input)
   at X.Main() in C:\proj\test\tester.cs:line 12
================

Author:	danmoseley
Assignees:	-
Labels:	area-System.Text.RegularExpressions, untriaged
Milestone:	-

[danmoseley]

Actually, I only debugged the first case. It's possible that one or both of the others are due to attempting to read out of bounds, rather than write. It's also conceivable that there are other variations, but these are the only 3 distinct stacks.

[stephentoub]

This no longer repros for the 1st or 3rd cases. It still repros for the second.

Regex.IsMatch("x", @"(?<!a*(?:a?)+?)");